数据结构之顺序表

时间：2023-01-27 20:02:42

顺序表(SeqList)是在计算机内存中以数组形式保存的线性数据结构，同时具有连续的物理存储空间。元素在顺序表中的位置称为索引(inde

x)。顺序表大致分为静态顺序表和动态顺序表，前者的容量一经定义就无法改变，后者可随时进行容量调整。动态顺序表在数组的基础上具有容量检测和调整等其他功能接口，使数组的使用更加丰富和方便。


逻辑结构

顺序表的逻辑结构为线性结构，各个元素在逻辑结构上相邻。

数据结构之顺序表


物理结构

顺序表的物理结构为线性结构，各个元素在内存中相邻存放。

数据结构之顺序表


顺序表定义

#define DEFAULT_CAPA 20//初始容量
#define EXP_SZ 20//增容大小

typedef int SeqListDataTp;//顺序表数据类型

typedef struct SeqList
{
SeqListDataTp* data;
int size;//记录当前数据数量
int capacity;//记录当前最大容量
}SeqList;

void SeqListInit(SeqList* sl);
void SeqListPushBack(SeqList* sl, const SeqListDataTp x);
void SeqListPopBack(SeqList* sl);
void SeqListPushFront(SeqList* sl, const SeqListDataTp x);
void SeqListPopFront(SeqList* sl);
int SeqListSz(SeqList* sl);
bool SeqListEmpty(SeqList* sl);
int SeqListFind(SeqList* sl, const SeqListDataTp aim);
void SeqListModify(SeqList* sl, const int pos, const SeqListDataTp aim);
void SeqListDel(SeqList* sl, const int pos);
void SeqListInsert(SeqList* sl, const int pos, const SeqListDataTp x);
void SeqListClear(SeqList* sl);
void SeqListDestory(SeqList* sl);


接口实现


小组件

容量检查和调整。该组件会在顺序表容量不足时进行扩容操作，在容量冗余时进行缩容操作，以达到尽量节省空间的目的。

void CheckCap(SeqList* sl)
{
assert(sl);
if (sl->size == sl->capacity)
  {
SeqListDataTp* tmp = (SeqListDataTp*)realloc(sl->data,
sizeof(SeqListDataTp) * (EXP_SZ + sl->capacity));
if (tmp == NULL)
    {
perror("Check::realloc");
    }
else
    {
sl->data = tmp;
sl->capacity += EXP_SZ;
    }
  }
else if (sl->capacity - sl->size > EXP_SZ)
  {
SeqListDataTp* tmp = (SeqListDataTp*)realloc(sl->data,
sizeof(SeqListDataTp) * (sl->size + EXP_SZ));
if (tmp == NULL)
    {
perror("Check::realloc");
    }
else
    {
sl->data = tmp;
sl->capacity = sl->size + EXP_SZ;
    }
  }
}

初始化顺序表

void SeqListInit(SeqList* sl)
{
assert(sl);
sl->data = (SeqListDataTp*)malloc(sizeof(SeqListDataTp) *
DEFAULT_CAPA);
if (sl->data == NULL)
  {
perror("SeqListInit::malloc:");
  }
else
  {
sl->size = 0;
sl->capacity = DEFAULT_CAPA;
  }
}

头部插入/删除

void SeqListPushBack(SeqList* sl, const SeqListDataTp x)//头插
{
assert(sl);
CheckCap(sl);//容量检查和调整
sl->data[sl->size] = x;
sl->size++;
}

void SeqListPopBack(SeqList* sl)//头删
{
assert(sl);
if (sl->size == 0)//顺序表为空
  {
printf("NULL\n");
return;
  }
sl->data[sl->size - 1] = 0;
sl->size--;
CheckCap(sl);
}

尾部插入/删除

void SeqListPushFront(SeqList* sl, const SeqListDataTp x)
{
assert(sl);
CheckCap(sl);
memmove(sl->data + 1, sl->data, 
sizeof(SeqListDataTp) * sl->size);
sl->data[0] = x;
sl->size++;
}

void SeqListPopFront(SeqList* sl)
{
assert(sl);
if (sl->size == 0)
  {
printf("NULL\n");
return;
  }
memmove(sl->data, sl->data + 1,
sizeof(SeqListDataTp) * sl->size);
sl->data[sl->size - 1] = 0;
sl->size--;
CheckCap(sl);
}

显示当前数据个数

int SeqListSz(SeqList* sl)
{
assert(sl);
return sl->size;
}

判断是否为空

bool SeqListEmpty(SeqList* sl)
{
assert(sl);
return sl->size == 0;
}

显示当前最大容量

int SeqListCap(SeqList* sl)
{
assert(sl);
return sl->capacity;
}

寻找指定的值

int SeqListFind(SeqList* sl, const SeqListDataTp aim)
{
for (int i = 0; i < sl->size; i++)
  {
if (sl->data[i] == aim)
    {
return i;
    }
  }
return -1;//找不到返回-1
}

在指定位置插入数据

void SeqListInsert(SeqList* sl, const int pos, const SeqListDataTp x)
{
assert(sl);
assert(pos <= (sl->size - 1));
CheckCap(sl);
memmove(sl->data + pos + 1, sl->data + pos,
sizeof(SeqListDataTp) * (sl->size - pos));
sl->data[pos] = x;
sl->size++;
}

修改指定位置的数据

void SeqListModify(SeqList* sl, const int pos, const SeqListDataTp aim)
{
assert(sl);
sl->data[pos] = aim;
}

删除指定位置的数据

void SeqListDel(SeqList* sl, const int pos)
{
assert(sl);
if (sl->size == 0)
  {
printf("NULL\n");
return;
  }
memmove(sl->data + pos, sl->data + pos + 1,
sizeof(SeqListDataTp) * (sl->size - pos - 1));
sl->data[sl->size - 1] = 0;
sl->size--;
CheckCap(sl);
}

清理顺序表

void SeqListClear(SeqList* sl)
{
assert(sl);
memset(sl->data, 0, sizeof(SeqListDataTp) * sl->size);
sl->size = 0;
CheckCap(sl);
}

销毁顺序表

void SeqListDestory(SeqList* sl)
{
assert(sl);
free(sl->data);
sl->data = NULL;//置空，避免产生野指针
sl->size = 0;
sl->capacity = 0;
}

顺序表的缺陷

从上面顺序表的实现中可以看到，顺序表有以下缺陷：

  1. 顺序表增容会有一定的性能消耗，且顺序表存在空间浪费现象
  2. 进行头部插入/删除操作时，需要移动其他所有数据，效率较低（O(N)）。这个问题其实是顺序表的存储结构造成的。
标签：

相关文章