c语言数据结构:顺序表(增,删,查,改)

1.顺序表的概念及其结构

1.1线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是?种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的?条直线。

但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表的分类

2.1 顺序表和数组的区别

?顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

所以可以这么说,顺序表的本质就是一个数组.

2.2 如何声明和构建一个顺序表

静态顺序表因为不常用,这里便不进行介绍了,感兴趣的可自行去了解

重点是动态顺序表

typedef struct seqlist
{
?? ?sldatatype* arr; ?//顺序表本质是个数组,这里定义一个指针arr用于对顺序表进行操作
?? ?int capacity; ? ? ? ?//顺序表可存储的最大元素个数?
?? ?int size; ? ? ? ? ? ? ? ?//size指的是当前顺序表(数组)存储的元素个数
}sl;//sl是此顺序表的类型

举个例子来更好的了解capacity和size,如果说capacity是一个碗,那么size就是这个碗里面盛的饭

3.顺序表的基础操作(增,删,查,改)

3.1 顺序表的初始化

void slinit(sl *ps)
{//传值的本质是形参是实参的值的拷贝
?? ?ps->arr = NULL;//此时的结构体变量还没有初始化,所以没有具体的值,所以应该传址
?? ?ps->size = ps->capacity = 0;
}

为什么这里使用的是传址的方式void slinit(sl *ps)

传址的方式更为常用,因为这样可以减少时空复杂度
特别是在需要对结构体变量进行修改操作或者结构体变量较大时，传址方式可以提高程序的效率和可读性。
或者这么说,顺序表的本质是个数组,传参是指针才方便操作嘛

3.2 在进行各项基础操作前检验内存是否足够的函数

//此函数的作用是判断内存是否足够,是否需要扩容
void slcheckcapacity(sl* ps)
{
?? ?//若空间不够,扩容
? ? //使用三目操作符更简洁:
?? ?if (ps->size == ps->capacity)//当前已使用空间等于最初给的最大容量
?? ?{
?? ??? ?//因为之前是有capacity的初始化为0操作,所以直接2被扩容是无效的,所以这里要对其进行最大容量初始化不为0操作
?? ??? ?int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
?? ??? ?//保证初始空间不为以后创建一个tmp指针变量用realloc函数对ps所指向的空间进行扩容操作
?? ??? ?sldatatype* tmp = (sldatatype*)realloc(ps->arr, newcapacity * sizeof(sldatatype));//对数组arr进行扩容,扩容后的空间大小一般是扩容前的空间二倍大小
?? ??? ?if (tmp == NULL)//扩容失败
?? ??? ?{
?? ??? ??? ?perror("realloc fail");
?? ??? ??? ?exit(1);
?? ??? ?}
?? ??? ?//扩容成功,realloc函数不需要手动free,因为它以经帮你做好了
?? ??? ?ps->arr = tmp;
?? ??? ?ps->capacity = newcapacity;
?? ?}
}

3.3 顺序表的尾插操作

void slpushback(sl* ps, sldatatype x)
{
?? ?assert(ps != NULL);

? ??slcheckcapacity(ps);
?? ?//若空间足够,直接插入
?? ?ps->arr[ps->size] = x;//向着数组arr中尾插元素x,size是数组当前的大小
?? ?ps->size++;//有效数据个数随之++
}

3.4顺序表的头插操作

//将头后面的所有数据都向前挪动一位
void slpopfront(sl* ps)
{
?? ?assert(ps);
?? ?assert(ps->size);

?? ?for (int i = 0;i<ps->size-1;i++)//最后一个有效数据是ps->arr[size-1]
?? ?{
?? ??? ?ps->arr[i] =ps->arr[i + 1] ;//将ps->arr[i + 1] 的元素赋值给?? ?ps->arr[i]
?? ?}
?? ?ps->size--;
}

3.4顺序表的头插操作

//将所有的数据都往后移一位,使顺序表头部空出一个位置
void slpushfront(sl* ps, sldatatype x)
{
?? ?assert(ps);
?? ?slcheckcapacity(ps);

?? ?//旧数据往后挪一位
?
?? ?for (int i = ps->size; i >0; i--)
?? ?{
?? ??? ?ps->arr[i]=ps->arr[i - 1];//将前面的数据ps->arr[i - 1]赋值给后面的数据ps->arr[i]以达到元素后移的目的
?? ?}
?? ?ps->arr[0] = x;
?? ?ps->size++;
?
}

3.4 顺序表的头插操作

//将所有的数据都往后移一位,使顺序表头部空出一个位置
void slpushfront(sl* ps, sldatatype x)
{
?? ?assert(ps);
?? ?slcheckcapacity(ps);

?? ?//旧数据往后挪一位
?
?? ?for (int i = ps->size; i >0; i--)
?? ?{
?? ??? ?ps->arr[i]=ps->arr[i - 1];//将前面的数据ps->arr[i - 1]赋值给后面的数据ps->arr[i]以达到元素后移的目的
?? ?}
?? ?ps->arr[0] = x;
?? ?ps->size++;
}

3.5 顺序表的尾删操作

void slpopback(sl *ps)
{
?? ?//顺序表及其内部数据都不可为空,如果顺序表存储的数据为空,那么它就无法进行删除操作
?? ?//就是capacity和size都不可以为空
?? ?assert(ps);
?? ?assert(ps->size);

?? ?//顺序表不为空
?? ?ps->size--;
}

3.6 顺序表的头删操作

//将头后面的所有数据都向前挪动一位
void slpopfront(sl* ps)
{
?? ?assert(ps);
?? ?assert(ps->size);

?? ?for (int i = 0;i<ps->size-1;i++)//最后一个有效数据是ps->arr[size-1]
?? ?{
?? ??? ?ps->arr[i] =ps->arr[i + 1] ;//将ps->arr[i + 1] 的元素赋值给?? ?ps->arr[i]
?? ?}
?? ?ps->size--;
}?

3.7 顺序表的指定位置之前插入操作

void slinsert(sl* ps, int pos, sldatatype x)//pos是指定位置
{
?? ?assert(ps);
?? ?assert(pos >= 0 && pos <= ps->size);
?? ?slcheckcapacity(ps);

?? ?for (int i=ps->size;i>=pos;i++)
?? ?{
?? ??? ?ps->arr[i] = ps->arr[i - 1];//后移操作,将前一个值赋值给后面一个值
?? ?}
?? ?ps->arr[pos] = x;
?? ?ps->size++;
}

?

3.8 顺序表的指定位置删除操作

void slerase(sl* ps, int pos)
{
?? ?assert(ps);
?? ?//pos之后的数据前挪一位
?? ?assert(pos >= 0 && pos <= ps->size);
?? ?for (int i=pos;i<ps->size;i++)
?? ?{
?? ??? ?ps->arr[i] = ps->arr[i + 1];
?? ?}
?? ?ps->size--;
}
?

完整代码:?登录 - Gitee.com

?