C语言顺序表
风＆646 人气:0线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构，也就是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式的形式存储。
顺序表
顺序表是用一段物理连续地址的存储单元依次存储数据元素的线性结构，一般情况采用数组存储。在数组上面完成数据的增删查改。
一般情况下，顺序表可以分为一下两种：
1.静态顺序表：使用定长数组存储元素。
2.动态顺序表：使用动态开辟的数组存储。
顺序表接口实现
静态顺序表只适用于确定知道需要存储多少数据的场景。静态顺序表不够灵活。所以我们基本都使用动态顺序表，根据需要空间的多少来分配大小，所有下面我们实现动态顺序表。
先定义一个结构体：
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size; //存储数据个数
int capacity; //容量空间大小
}SeqList;
1.顺序表初始化
void SeqListInit(SeqList* ps);
void SeqListInit(SeqList* ps)
{
assert(ps); //检查指针的有效性
ps->a = NULL; //不知道开多大的空间，就先赋值NULL
ps->capacity = ps->size = 0;
}
我们在给ps->a开辟空间的时候，还可以以如下方式开辟，这样甚至更简单一点(开辟完空间后需要检查空间的有效性)，但这两种都可以。
STDataType*tmp=(STDataType*)malloc(sizeof(SeqList)*2);
2.顺序表空间增容
//检查空间，如果满了，就进行增容
void SeqListCheckCapacity(SeqList* ps);
void SeqListCheckCapacity(SeqList* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = realloc(ps->a, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
printf("CheckCapacity::%s\n", strerror(errno));//若空间开辟失败，则打印开辟失败的原因
exit(-1);//若空间开辟失败，则直接终止程序
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}1.此处realloc空间，如果容量不够，我们就将容量扩展为原来的两倍，但是我们一开始初始化的空间有可能是0，所以我们应该把这种情况考虑进去。
2.realloc空间可能因为一些原因而失败，所以要对开辟的空间进行检查，即判断申请的空间是否为空（NULL）。
3.顺序表打印
//顺序表打印
void SeqListPrint(SeqList* ps);
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0;i < ps->size;++i)//依次遍历，打印出每一个信息
{
printf("%d ", ps->a[i]);
}
printf("\n");
}4.尾插数据
//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
void SeqListPushBack(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}5.尾删数据
//顺序表尾删
void SeqListPopBack(SeqList* ps);
void SeqListPopBack(SeqList* ps)
{
assert(ps);
if (ps->size > 0)//防止尾删将数据删完了，size出现负数
{
ps->size--;
}
}注意：size减的时候一定要加条件限制，防止下标出现负数。
6.头插数据
//顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x);
void SeqListPushFront(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);//检查空间容量
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}7.头删数据
//顺序表头删
void SeqListPopFront(SeqList* ps);
void SeqListPopFront(SeqList* ps)
{
assert(ps);
//依次挪动数据覆盖删除
if (ps->size > 0)//确保有数据可删除，防止下标出现负数
{
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
}注意：头删一定要保证下标大于0，不然删掉一个下标减一下，当下标减为负数的时候，程序就会出错。头删的时候数据从前向后数据依次向前覆盖一位。
8.在pos下标处插入数据
//顺序表在pos位置插入数据
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
assert(ps);
if (pos > ps->size)
{
printf("pos越界\n");
return;
}
SeqListCheckCapacity(ps);
size_t end = ps->size;
while (end > pos)
{
ps->a[end] = ps->a[end - 1];
--end;
}
ps->a[pos] = x;
ps->size++;
}这里需要特别注意一下下标的问题，如下图：
在这里循环有两种写法，一种如上，还有一种就是下边这种。
int end =ps->size-1;
while(end>=(int)pos)
{
ps->a[end+1]=ps->a[end];
--end;
}注意:对比以上两种写法，我们注意到了pos和end的类型。因为坐标不可能为负数，所以pos为size_t类型。对于第二种情况：int end=ps->size-1时，循环执行到最后end的值会变为-1，但pos的类型为size_t，所以当end与pos比较的时候，会发生整形提升，使无符号的end整形提升为有符号的数字和pos比较，所以while条件成立，会继续循环，导致越界访问内存。对于这种我们的解决方法是将pos强制转换为int类型，如上诉代码。
对于第一种情况： int end=ps->size,循环执行到最后end的值为0，为无符号数，因此刚好完美的进行了移动覆盖，不会出现越界访问的情况。所以我们推荐使用第一种方法。
9.删除pos下标处数据
//顺序表删除pos位置的数据
void SeqListErase(SeqList* ps, size_t pos);
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
if (pos >= ps->size)
{
printf("pos越界\n");
return;
}
size_t begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}10.数据查找
依次遍历数据查找，若找到了对应的数据，则返回它的下标。若找不到，则返回-1.
//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x);
int SeqListFind(SeqList* ps, SLDataType x)
{
assert(ps);
for (int i = 0;i < ps->size;++i)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}11.顺序表摧毁
当我们使用动态申请空间时，使用完后，一定要释放动态开辟的内存。否则可能会造成内存泄漏。
//顺序表销毁
void SeqListDestroy(SeqList* ps);
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}加载全部内容