C语言简单实现动态顺序表

                                         C语言简单实现动态顺序表

我们首先了解一下何为顺序表。

顺序表是在计算机内存中以​​数组​​​的形式保存的线性表，是指用一组地址连续的​​存储单元​​​依次存储​​数据元素​​的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

静态实现：结构体内部只需两个成员，其中一个为固定大小(MAX)的数组，用来存放我们的数据。数组大小我们可以通过在头文件中改变MAX的值来改变。

动态实现：在内存中开辟一块空间，可以随我们数据数量的增多来扩容。

下面只介绍动态实现。

头文件：SeqList.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

#define DEFAULT_SZ 2
#define INC 2

typedef int DataType;

typedef struct SeqList
{
  DataType *data;
  int sz;
  int capacity;
}SeqList, *pSeqList;

void InitSeqList(pSeqList ps);             //初始化
void Checkcapacity(pSeqList ps);            //检查是否需要扩容
void DestroySeqList(pSeqList ps);           //销毁顺序表
void PushBack(pSeqList ps, DataType d);    //尾部压入元素
void PopBack(pSeqList ps);                 //尾部删除
void Display(const pSeqList ps);           //打印
void PushFront(pSeqList ps, DataType d);   //头部压入元素
void PopFront(pSeqList ps);                //头部删除元素
int Find(pSeqList ps, DataType d);         //寻找一个元素
void Insert(pSeqList ps, DataType d, int pos);   //指定位置插入
void Remove(pSeqList ps, DataType d);       //删除第一次出现的d
void RemoveAll(pSeqList ps, DataType d);    //删除所有的d
void Reverse(pSeqList ps);                  //逆序顺序表
void Sort(pSeqList ps);                     //排序
int BinarySearch(pSeqList ps, DataType d);  //二分查找d


#endif //__SEQLIST_H__      

SeqList.c

#include"SeqList.h"

void InitSeqList(pSeqList ps)
{
  ps->sz = 0;
  //memset(ps->data, 0, sizeof(ps->data));
  ps->data = malloc(DEFAULT_SZ*sizeof(DataType));
  if (ps->data == NULL)
  {
    perror("use malloc");
    exit(EXIT_FAILURE);
  }
  memset(ps->data, 0, sizeof(ps->data));
        ps->capacity = DEFAULT_SZ;
}

void Checkcapacity(pSeqList ps)
{
  if (ps->sz == ps->capacity)
  {
    DataType *ptr = realloc(ps->data, sizeof(DataType)*(ps->capacity + INC));
    if (ptr == NULL)
    {
      perror("use realloc");
      exit(EXIT_FAILURE);
    }
    else
    {
      ps->data = ptr;
    }
    ps->capacity +=INC;
  }
}

void PushBack(pSeqList ps, DataType d)
{
  assert(ps != NULL);
  Checkcapacity(ps);
  ps->data[ps->sz] = d;
  ps->sz++;
}

void PopBack(pSeqList ps)
{
  assert(ps != NULL);
  if (ps->sz == 0)
  {
    return;
  }
  ps->sz--;
}

void Display(const pSeqList ps)
{
  assert(ps != NULL);
  int i = 0;
  for (i = 0; i < ps->sz; i++)
  {
    printf("%d ", ps->data[i]);
  }
  printf("\n");
}

void PushFront(pSeqList ps, DataType d)
{
  assert(ps != NULL);
  int i = 0;
  Checkcapacity(ps);
  memmove(ps->data+1, ps->data, sizeof(DataType)*(ps->sz));
  ps->data[0] = d;
  ps->sz++;  
}

void PopFront(pSeqList ps)          
{
  assert(ps != NULL);
  int i = 0;
  //memmove(ps->data, ps->data + 1, sizeof(DataType)*(ps->sz));
  if (ps->sz == 0)
  {
    return;
  }
  for (i = 0; i < ps->sz - 1; i++)           //避免越界
  {
    ps->data[i] = ps->data[i + 1];
  }
  ps->sz--;
}

int Find(pSeqList ps, DataType d)
{
  assert(ps != NULL);
  int i = 0;
  for (i = 0; i < ps->sz; i++)
  {
    if (ps->data[i] == d)
    {
      return i;
    }
  }
  return -1;
}

void Insert(pSeqList ps, DataType d, int pos)
{
  assert(ps != NULL);
  int i = 0;
  Checkcapacity(ps);
  for (i = ps->sz; i >pos; i--)
  {
    ps->data[i] = ps->data[i-1];
  }
  ps->data[pos] = d;
  ps->sz++;
}

void Remove(pSeqList ps, DataType d)
{
  assert(ps != NULL);
  int ret = Find(ps,d);
  if (ret != -1)
  {
    memmove(ps->data+ret, ps->data+ret+1, sizeof(DataType)*(ps->sz - ret-1));
    ps->sz--;
  }
}

void RemoveAll(pSeqList ps, DataType d)
{
  assert(ps != NULL);
  int ret = 0;
  while (ret != -1)
  {
    Remove(ps, d);
    ret = Find(ps, d);
  }
}

void Reverse(pSeqList ps)
{
  if (ps->sz == 0)
  {
    return;
  }
  int left = 0;
  int right = ps->sz - 1;
  while (left < right)
  {
    int tmp = ps->data[left];
    ps->data[left] = ps->data[right];
    ps->data[right] = tmp;
    left++;
    right--;
  }
}

void Sort(pSeqList ps)
{
  int i = 0;
  int j = 0;
  for (i = 0; i < ps->sz - 1; i++)
  {
    for (j = 0; j < ps->sz - 1 - i; j++)
    {
      if (ps->data[j]>ps->data[j + 1])
      {
        int tmp = ps->data[j];
        ps->data[j] = ps->data[j + 1];
        ps->data[j + 1] = tmp;
      }
    }
  }
}

int BinarySearch(pSeqList ps, DataType d)
{
  if (ps->sz == 0)
  {
    return 0;
  }
  DataType left = 0;
  DataType right = ps->sz - 1;
  while (left <= right)
  {
    DataType mid = ((left + right) >> 1);
    if (d>ps->data[mid])
    {
      left = mid + 1;
    }
    else if (d < ps->data[mid])
    {
      right = mid - 1;
    }
    else
      return mid;
  }
  return -1;
}

void DestroySeqList(pSeqList ps)
{
  free(ps->data);
  ps->data = NULL;
  ps->sz = 0;
  ps->capacity = 0;
}      

为了更容易测试，我们分几个函数来测试函数的功能。

test.c

#include"SeqList.h"

void test1()
{
  SeqList my_list;
  InitSeqList(&my_list);
  //尾部操作
  PushBack(&my_list, 1);
  PushBack(&my_list, 2); 
  PushBack(&my_list, 3);
  Display(&my_list);

  PopBack(&my_list);
  Display(&my_list);

  DestroySeqList(&my_list);
}
void test2()
{
  SeqList my_list;
  InitSeqList(&my_list);
  //头部操作
  PushFront(&my_list, 2);
  PushFront(&my_list, 3);
  PushFront(&my_list, 4);

  Display(&my_list);
  PopFront(&my_list);
  Display(&my_list);

  DestroySeqList(&my_list);
}
void test3()
{
  SeqList my_list;
  InitSeqList(&my_list);
  //寻找与指定位置插入
  PushFront(&my_list, 2);
  PushFront(&my_list, 3);
  PushFront(&my_list, 4);
  Display(&my_list);
  int ret = 0;
  ret = Find(&my_list, 3);
  if (ret == -1)
  {
    printf("没找到\n");
  }
  else
  {
    printf("找到了，下标为：%d\n", ret);
    Insert(&my_list, 6, ret);
    printf("插入后顺序表为：");
    Display(&my_list);
  }
  DestroySeqList(&my_list);
}
void test4()
{
  SeqList my_list;
  InitSeqList(&my_list);
  PushFront(&my_list, 1);
  PushFront(&my_list, 2);
  PushFront(&my_list, 3);
  PushFront(&my_list, 2);
  PushFront(&my_list, 4);
  PushFront(&my_list, 3);
  PushFront(&my_list, 4);
  Display(&my_list);
  //删除第一次出现的d
  Remove(&my_list, 3);
  printf("删除成功:\n");
  Display(&my_list);
  //删除全部d
  RemoveAll(&my_list, 2);
  printf("删除成功:\n");
  Display(&my_list);
  DestroySeqList(&my_list);
}

void test5()
{
  SeqList my_list;
  InitSeqList(&my_list);
  PushFront(&my_list, 1);
  PushFront(&my_list, 3);
  PushFront(&my_list, 2);
  PushFront(&my_list, 7);
  PushFront(&my_list, 9);
  Display(&my_list);
  //逆序 排序 二分查找
  Reverse(&my_list);
  Display(&my_list);
  Sort(&my_list);
  Display(&my_list);
  int ret = BinarySearch(&my_list, 3);
  if (ret == -1)
  {
    printf("没找到\n");
  }
  else
  {
    printf("找到了，下标为：%d\n", ret);
  }
  DestroySeqList(&my_list);
}
int main()
{
  test5();
  system("pause");
  return 0;
}