顺序表—C语言实现数据结构
本期带大家一起来用C语言代码实现顺序表🌈🌈🌈
文章目录
一、顺序表的概念✅
顺序表是一段物理地址连续的存储单元，依次存储数据元素的线性结构。分为静态顺序表与动态顺序表。 🍊 🍋 🍒
二、顺序表的结构✅
静态顺序表：使用定长数组用来存储数据
优点：操作简单，代码实现容易
缺点：定长数组很受限制，数组开小了不够用，开大了又浪费
动态顺序表：使用动态开辟的数组进行存储数据
优点：数组可以根据自己的需求进行调解
缺点：代码过于复杂
三、顺序表的实现（动态顺序表）✅
这里先建立三个文件：
1️⃣ ：SeqList.h文件，用于函数声明
2️⃣ ：SeqList.c文件，用于函数的定义
3️⃣ ：Test.c文件，用于测试函数
建立三个文件的目的： 将顺序表作为一个项目来进行书写，方便我们的学习与观察。
一、🔶定义顺序表结构体🔶
顺序表结构体里面的成员基本的有
指向动态开辟的空间的指针a🐸
当前顺序表当中存储的数据个数size🐸
以及顺序表当前的容量capacity🐸
typedef int SLTDataType;typedef struct SListNode
{SLTDataType* a;int size;int capacity;}SL;
这里我们使用typedef对我们所存储的数据，以及顺序表结构体重命名，方便我们后续修改 🍊 🍋 🍒
二、🔶接口的实现🔶
1.接口：初始化结构体（SLInit）🎈💡
这里我们对结构体里面的内容进行初始化
初始化为容量为4，所存储的数据个数为0，并且利用malloc函数进行动态开辟
void SLInit(SL* psl)
{assert(psl);psl->a = (SLTDataType*)malloc(sizeof(SLTDataType) * 4);if (psl->a == NULL){perror("psl::null");return;}psl->capacity = 4;psl->size = 0;}2.接口：扩容顺序表🎈💡
我们往顺序表当中添加数据的时候，需要判断顺序表当中数据的个数是否达到了最大容量
如果达到了最大容量，则进行扩容🍗 🍖
void SLCheckCapacity(SL* psl)
{if (psl->size == psl->capacity){SLTDataType* tmp = (SLTDataType*)realloc(psl->a,sizeof(SLTDataType) * psl->capacity * 2);if (tmp == NULL){perror("realloc:null");return;}psl-> a= tmp;psl->capacity *= 2;}
}
3.接口：头插数据🎈💡
当我们需要在顺序表的开头第一个位置插入数据的时候，我们需要进行如下操作🍗 🍖 🍝
错误想法：
这里是引用但是当我们从前面往后面进行覆盖的话，那么原来的数据都会被覆盖掉，所以这是一个错误的想法🍗 🍖 🍝
正确想法：
void STLpushfront(SL* psl, SLTDataType s)
{SLCheckCapacity(psl);for (int i = 0; i < psl->size; i++){psl->a[psl->size - i] = psl->a[psl->size - i - 1];}psl->a[0] = s;psl->size++;
}
4.接口：尾插数据🎈💡
尾插数据相对于头插数据来说是比较简单的🚀 🛸 🚁
首先我们需要先检查顺序表当中的有效数据是否已经达到了当前的容量然后
只需要将我们需要插入的数据插在顺序表当中有效数据的后面一个就行
同时让我们顺序表当中的有效数据加一即可 🍗 🍖 🍝
void STLpushback(SL* psl,SLTDataType s)
{SLCheckCapacity(psl);psl->a[psl->size] = s;psl->size++;}
5.接口：头删数据🎈💡
我们删除数据的时候，需要将头部的数据进行删除
这时候我们需要采取覆盖的原理来实现
void SLPopFront(SL* psl)
{if (psl->size == 0){printf("顺序表当中数据为空\\n");return;}for (int i = 0; i < psl->size; i++){psl->a[i] = psl->a[i + 1];}psl->size--;}6.接口：尾删数据🎈💡
尾删数据的话同尾插数据的原理是一样的
只需要将顺序表当中的有效数据的个数进行变化就行🚀 🛸 🚀 🛸
void SLPopBack(SL* psl)
{if (psl->size == 0){printf("顺序表当中数据为空\\n");return;}psl->size--;
}7.接口：在指定位置插入数据（SLInsert）🎈💡
当然，添加数据的话不仅仅局限于我们的头插和尾插数据
还可以是在指定下标pos进行插入数据
函数的原型：void SLInsert(SL* ps, int pos, SLDateType x)
注意：要实现这一功能，我们依然需要一个end下标，数据从后往前依次后挪，直到pos下标移动完毕🚀 🛸
另外，别忘了检查容量。
我们首先需要找到当前顺序表最后一个位置的数据
然后将前面的数据赋给后一个位置⌛️ ⏳
直到找到我们的pos位置，将我们需要添加的数据添加到顺序表当中
同样在开始的时候需要检查是否扩容
void SLInsert(SL* psl, int pos, SLTDataType x)
{assert(psl);assert(pos <= psl->size && pos >= 0);SLCheckCapacity(psl);int end = psl->size;while ( end>pos){psl->a[end] = psl->a[end - 1];end--;}psl->a[pos] = x;psl->size++;}
函数拓展：该功能其实也可以实现头插和尾插，所以我们可以在头插和尾插中复用该功能
// 头插
void SeqListPushFront(SL* ps, SLDataType x)
{SeqListInsert(ps, 0, x);
}// 尾插
void SeqListPushBack(SL* ps, SLDataType x)
{SeqListInsert(ps, ps->sz, x);
}
8.接口：在指定位置删除数据🎈💡
同我们的在指定位置添加数据一样
当我们需要在指定位置删除数据的时候⌛️ ⏳
我们需要传入一个下标pos进行删除的操作
然后我们需要将从下标开始的数据改为下标+1的数据
例如 a=a+1
void SLErase(SL* psl, int pos)
{assert(psl);assert(pos >= 0 && pos < psl->size);for (int i = pos; i < psl->size - 1; i++){psl->a[i] = psl->a[i + 1];}psl->size--;}
函数拓展：该功能其实也可以实现头删和尾插=删，所以我们可以在头删和尾插】删中复用该功能
// 头删
void SeqListPopFront(SL* ps)
{SeqListErase(ps, 0);
}// 尾删
void SeqListPopBack(SL* ps)
{SeqListErase(ps, ps->sz - 1);
}
9.接口：查找某一个数据的位置（SLFind）🎈💡
查找顺序表当中是否存在某个数据
如果存在的话就返回所对应的下标
不存在的话则返回-1
int SLFind(SL* psl, SLTDataType x)
{for (int i = 0; i < psl->size; i++){if (psl->a[i] == x)return i;}return -1;
}10.接口：修改指定下标的数据🎈💡
首先判断传入的下标是否合法❓❓❓
合法的话则将对应下标的数据修改
void SLModify(SL* psl, int pos, SLTDataType x)
{assert(psl);assert(0 < pos && pos < psl->size);psl->a[pos] = x;
}
接口11：打印函数（SLprint）🎈💡
主要利用顺序表当中有效数据的个数进行数据的打印🌎 🌍
void SLprint(SL* psl)
{assert(psl);for (int i = 0; i < psl->size; i++){/*printf("%d ", *(psl->a + i));*/printf("%d ", psl->a[i]);}printf("\\n");}
接口12：销毁（SLDestory）🎈💡
由于我们的顺序表是动态开辟出来的的
所以我们需要在结束程序的时候需要将开辟出来的空间进行销毁
避免内存泄漏🌎 🌍
void SLDestroy(SL* psl)
{assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;}四、顺序表的应用小项目✅
顺序表实现通讯录
五、感谢与交流✅
🌹🌹🌹如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的，疑惑的话，或者什么比较好的建议的话，可以发到评论区，
我们一起解决，共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯
