数据结构

2024-03-12 09:06| 来源: 网络整理| 查看: 265

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

系列文章目录

数据结构——顺序表的C语言代码实现数据结构——八种链表的C语言代码实现数据结构——栈的C语言代码实现数据结构——队列的C语言代码实现数据结构——堆的C语言代码实现

文章目录系列文章目录前言一、基础知识1.顺序表的概念（Sequential List）2.常用的接口函数3.realloc（）函数使用细节4.assert( )函数二、代码实现1.SepList.h（1）引用函数库（2）定义动态顺序表（3）接口函数声明 2.SepList.c（1）引用头文件（2）初始顺序表（3）检测顺序表容量是否足够（4）顺序表的尾插法（5）顺序表的尾删法使用if判断的温和法使用assert（）断言的暴躁法（6）全部删除（7）头插法（8）头删法（9）查找某个数值的位置（10）指定位置插入（11）指定位置删除（12）打印函数 3.test.c（1）引用头文件（2）各种测试函数（3）主函数三、总结

前言

使用C语言实现顺序表，重点实现动态顺序表。加强模块化实现功能的能力，了解并熟练使用realloc（），assert（）等函数。

一、基础知识 1.顺序表的概念（Sequential List）

鬼话：顺序表就是把线性表中的所有元素按照其逻辑顺序，依次储存到从指定的储存位置开始的一块连续的储存空间中。人话：自我理解，特殊的数组！即将连续的数据存储在数组中，注意连续性，不可跳跃式存储。

2.常用的接口函数

在进行数据结构的代码实现时，最常用的接口函数便是：增、删、查、改。增：尾插、头插、指定位置插入；删：尾删、头删、指定位置删除；查：遍历查找；改：先找后改；

3.realloc（）函数使用细节

realloc（）函数： void* realloc (void* ptr, size_t size); 注意： 1.返回值是void*，实际使用中应合理使用强制类型转换； 2.size_t size 是字节数，即所需要开辟的空间大小，此处应和calloc（）结合记忆，注意区别！ 3.引用戳此处，查看realloc函数标准形式 realloc（）是C语言中最常用的扩容或缩容函数，其改变已开辟的内存空间大小的工作实质是: 在已有空间的末尾寻找空余的连续空间，若末尾的空余空间足够开辟，则便在此处进行开辟，返回的指针为原指针，即所开辟的空间的起始地址没有发生改变；若末尾的空余空间不足以开辟，则对已开辟空间所存储的内容进行拷贝，然后在内存的其它位置寻找足够大的连续空间进行开辟，而原有空间被系统释放，故此时该函数的返回值不再是原指针，即所开辟的空间的起始地址发生了改变；但实际使用时，未避免引用过多指针，常使用以下方式进行操作：

(DataType*) ptr=(DataType*)realloc(p,sizeof(DataType)*size_t); if(ptr!=NULL) p=ptr; 4.assert( )函数

assert（）函数：

void assert (int expression);

戳此处，查看assert()函数标准形式注意引用条件为真，继续向下执行；条件为假，终止程序。

二、代码实现 1.SepList.h （1）引用函数库 #include #include #include （2）定义动态顺序表

建议遵循命名规则，将动态数组命名为arr等名字，p总是带来误解，但我懒得改了。。。

typedef int SLDataType; //便于更改所存储数据的类型 typedef struct SeqLIst { SLDataType* p; int size; int capacity; }SL; （3）接口函数声明

注意在设计接口函数时应使用传址的参数

//初始顺序表 void SeqListInit(SL* ps); //顺序表的尾插法 void SeqListPushBack(SL* ps, SLDataType n); //顺序表的尾删法 void SeqListPopBack(SL* ps); //顺序表的头插法 void SeqListPushFront(SL* ps, SLDataType n); //顺序表的头删法 void SeqListPopFront(SL* ps); //查找顺序表中的数据位置 int Find(SL* ps,SLDataType n); //指定位置插入 void SeqListInsert(SL* ps, int location, SLDataType n); //指定位置删除 void SeqListDelete(SL* ps, int location); //检测顺序表容量是否足够 void CheckCapacity(SL* ps); //接口函数测试函数 void PrintSeqList(SL* ps); //删除顺序表 void DestroySeqList(SL* ps); 2.SepList.c

此文件用于实现各接口函数。

（1）引用头文件 #include"SeqList.h" （2）初始顺序表 //初始顺序表 void SeqListInit(SL* ps) { (*ps).p = NULL; ps->capacity = 0; ps->size = 0; } （3）检测顺序表容量是否足够 //检测顺序表容量是否足够 void CheckCapacity(SL* ps) { //进行扩容，两种情况：1.没有开辟空间；2.容量用尽 if (ps->size == ps->capacity) { int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* ptr = (SLDataType*)realloc(ps->p, sizeof(SLDataType) * Newcapacity); if (ptr != NULL) //扩容成功 ps->p = ptr; else { printf("realloc fail !"); //异常退出，终止程序，使用return的话，只是退出该函数 exit(-1); } ps->capacity = Newcapacity; } } （4）顺序表的尾插法 //顺序表的尾插法 void SeqListPushBack(SL* ps, SLDataType n) { CheckCapacity(ps); ps->p[ps->size] = n; ps->size += 1; } （5）顺序表的尾删法使用if判断的温和法 void SeqListPopBack(SL* ps) { if(ps->size>0) ps->size--; } 使用assert（）断言的暴躁法

何为暴躁？ assert（条件）条件为假，直接终止函数！

void SeqListPopBack(SL* ps) { assert(ps->size>0) ps->size--; } （6）全部删除 //删除顺序表 void DestroySeqList(SL* ps) { free(ps->p); //防止该指针成为野指针 ps->p = NULL; ps->capacity = ps->size = 0; } （7）头插法 //顺序表的头插法 void SeqListPushFront(SL* ps, SLDataType n) { CheckCapacity(ps); //用前值覆盖后值，实现整体后移，必须从后向前两两操作 ps->size += 1; int end = ps->size - 1; while (end > 0) { //实现插入前的数组的整体后移 ps->p[end] = ps->p[end - 1]; end--; } ps->p[0] = n; } （8）头删法 //顺序表的头删法 void SeqListPopFront(SL* ps) { assert(ps->size > 0); //将已有数组整体前移 int head = 0; while (head size - 1) { ps->p[head] = ps->p[head + 1]; head++; } ps->size--; } （9）查找某个数值的位置 int Find(SL* ps, SLDataType n) { if (ps->size == 0) { printf("顺序表为空!\n"); exit(-1); } int tem = 0; while (tem size) { if (ps->p[tem] == n) { return tem; } tem++; } printf("顺序表中没有该值！\n"); return -1; } （10）指定位置插入

注意判断所要插入的位置，进而合理使用已有的接口函数，该程序设计中输入的位置是从1开始的！

//指定位置插入 void SeqListInsert(SL* ps, int location,SLDataType n) { //因为输入的位置是从1开始数的 int L = location - 1; //确保所要插入的位置合法 assert(L>=0&&Lsize); //确保顺序表不为空 assert(ps->size > 0); CheckCapacity(ps); //如果插入位置在头部 if (L == 0) { SeqListPushFront(ps, n); } //如果插入位置在尾部 else if (L == ps->size) { SeqListPushBack(ps, n); } //如果插入位置在已有数组内部 else { ps->size++; int temend = ps->size - 1; while (temend > L) { ps->p[temend] = ps->p[temend - 1]; temend--; } ps->p[L] = n; } } （11）指定位置删除 //指定位置删除 void SeqListDelete(SL* ps, int location) { int L = location - 1; //确保输入的位置合法 assert(L>=0&&Lsize-1); //确保顺序表不为空 assert(ps->size > 0); if (L == 0) { SeqListPopFront(ps); } else if (L == ps->size - 1) { SeqListPopBack(ps); } else { int temend = L; while (temend size - 1) { ps->p[temend] = ps->p[temend+1]; temend++; } ps->size -= 1; } } （12）打印函数 //接口函数测试 void PrintSeqList(SL* ps) { int i = 0; for (i = 0; i size; i++) { printf("%d ", ps->p[i]); } } 3.test.c

该文件用于存放主函数，本程序只研究如何代码实现顺序表，故多为测试语句，不具有参考价值。具体使用时，可在此处代码实现菜单功能！

（1）引用头文件 #include"SeqList.h" （2）各种测试函数

该处无参考价值，大家随意设置

void testSeqList() { SL sl; SeqListInit(&sl); SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); /*SeqListPopBack(&sl,5); SeqListPushFront(&sl, 0);*/ //用来测试接口函数 PrintSeqList(&sl); DestroySeqList(&sl); } void testSeqListPushFront() { SL sl; SeqListInit(&sl); SeqListPushFront(&sl, 1); SeqListPushFront(&sl, 2); SeqListPushFront(&sl, 3); SeqListPushFront(&sl, 4); SeqListPopFront(&sl); //int ret=Find(&sl, 2); PrintSeqList(&sl); /* printf("\n"); printf("%d", ret);*/ SeqListDelete(&sl,3); PrintSeqList(&sl); } （3）主函数

亦无实际价值

int main() { //testSeqList(); testSeqListPushFront(); return 0; } 三、总结

数据结构的学习在于实际操作，大学课堂的教学偏向于理论学习，如若只是浅尝辄止地了解一些名词概念毫无作用，故特此逐一实现数据结构的C语言代码，进而鞭策自己迎难而上！与君共勉！

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻