摘要：博客主页的江湖背景的江湖背景欢迎关注点赞收藏留言本文由原创，首发首发时间年月日最新更新时间年月日坚持和努力一定能换来诗与远方本篇代码地址代码地址代码地址作者水平很有限，如果发现错误，请留言轰炸哦万分感谢感谢感谢目录线性表可以理
?博客主页：kikoking的江湖背景
?欢迎关注?点赞?收藏⭐️留言?
?本文由 kikokingzz 原创，CSDN首发！
?首发时间：?2021年11月18日?
?最新更新时间：?2021年11月18日?
✉️坚持和努力一定能换来诗与远方！
?本篇代码地址：代码地址
?作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢感谢感谢！
目录
?♀️女侠：今天就带你领略领略江湖中最易但却意义最不易的一类数据结构
??林轩：好家伙，为何最易，为何最不易？
?♀️女侠：对我来说顺序表是个小case，你还没学，这我不清楚；不过人生啊～
??林轩：人生什么？
?♀️女侠：人生可不是顺序表～你会慢慢领略到的，我们先往下看：
?♀️女侠：学习一种数据结构，我们首先要了解它的两个方面
??林轩：啥玩意？
?♀️女侠：逻辑结构与数据结构
??林轩：啥玩意？
?♀️女侠：前两节课听了就忘是吧！
?♀️女侠：先去补课！
........
?♀️女侠：补完课了吧，那就让我们先从顺序表的逻辑结构开始说起
✨✨✨我是分割线✨✨✨
线性表——（可以理解为顺序表的逻辑结构）
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长
当n=0时，线性表是一个空表
若用L命名线性表，其一般表示为（a1,a2,a3.........ai,ai+1,......an）
1.a1是唯一的“第一个”数据元素——表头元素
2.an 是唯一的“最后一个”数据元素——表尾元素
3.逻辑特性：除第一个元素以外，；除最后一个元素外，每个元素仅有一个直接后继
特点：
1.表中元素个数有限
2.每个元素占用相同大小存储空间
3.表中元素具有逻辑上的顺序性，表中元素有其先后次序
4.表中元素具有抽象性，仅讨论元素间的逻辑关系
线性表的抽象数据类型
✨✨✨我是分割线✨✨✨
顺序表——（线性表的顺序存储）
它是用一组地址连续的存储单元（数组）依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
特点：
1.表中元素的逻辑顺序与物理顺序相同
2.具有随机存储的特点：每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数
3.线性表中元素的位序是从1开始的，而数组元素的下标是从0开始的
✨✨✨我是分割线✨✨✨
?♀️女侠：那么接下来我们挨个实现顺序表的功能
??林轩：好！
✨✨✨我是分割线✨✨✨
⚡️1.定义一个数据元素
typedef int DataType;//将int重定义为DataType//下次想更改数据类型的时候只需要更改前面的int就可以，无需改变整个程序typedef struct SeqList //定义一个顺序表的结构体{ DataType* a;//指示动态分配数组的指针 DataType size;//数组中有效数据的个数 DataType capacity;//数组的容量}SEQ;// 将SeqList这个结构体重定义为SEQ，为了后续方便写程序
⚡️2.初始化顺序表SeqListInit
void SeqListInit(SEQ* pq)//初始化顺序表{ assert(pq);//断言如果为真，就成功通过 //如果为假，即pq为空，则不通过 //断言的好处：不用分析，直接告诉你哪里出错了 pq->a = NULL; pq->size = 0; pq->capacity = 0;}
⚡️3.销毁顺序表SeqListDestroy
void SeqListDestroy(SEQ* pq)//销毁顺序表{ free(pq->a);//释放动态数组空间 pq->a = NULL;//将指示动态数组的指针置空 pq->size = 0;//将有效数据个数置0 pq->capacity = 0;//将容量个数置0}
⚡️4.打印顺序表SeqListPrint
void SeqListPrint(SEQ* pq) //打印顺序表{ assert(pq);//声明；防止pq空指针 for (int i = 0; i < pq->size; ++i) { printf("%d", pq->a[i]);//防止pq空指针 } printf("/n");}
⚡️5.动态扩容顺序表SeqCheckCapacity
void SeqCheckCapcity(SEQ* pq)//检测动态数组是否需要扩容{ assert(pq); //满了，需要扩容 if (pq->size == pq->capacity) { int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2; //如果动态容量为0，那么将其分配4个空间；否则将其扩容为原先的两倍 DataType* newA = realloc(pq->a, sizeof(DataType) * newcapacity); //为其申请一个新的空间，大小为原先的两倍 //realloc是对已经有的空间进行扩容，检查后面有没有足够空间，没有则重新开辟一块新空间 if (newA == NULL)//如果新空间的地址为空 { printf("realloc fail/n");//申请空间失败 exit(-1); } pq->a = newA;//将新申请的地址赋予给指针a pq->capacity = newcapacity;//将新申请的空间赋予给capacity }}
⚡️6.尾插数据·SeqListPushBack
void SeqListPushBack(SEQ* pq, DataType x){ assert(pq);//声明，预防空指针 SeqCheckCapcity(pq);//检测动态数组是否需要扩容 pq->a[pq->size] = x;//尾插数据}
⚡️7.头插数据·SeqListPushFront
void SeqListPushFront(SEQ* pq, DataType x)//头插数据{ assert(pq);//声明，防止空指针 SeqCheckCapcity(pq);//检测动态数组是否需要扩容 for(int i=pq->size;i>0;--i) { pq->a[i]=pq->a[i-1];//从后往前，挨个向后移动一位 } pq->a[0]=x;//将x赋给第一位 pq->size++;//顺序表有效长度+1}
⚡️8.任意位置插入数据·SeqListInsert
void SeqListInsert(SEQ*pq,int pos,DataType x)//pos为数组的下标，插在第pos个数组下标初{ assert(pq); assert(pos>=0&&pos<=pq->size);//保证pos的值最小为0，最大为pq->size SeqCheckCapcity(pq); for(int i=pq->size;i>pos;--i) { pq->a[i]=pq->a[i-1];//从后往前，挨个向后移动一位，留出数组下标为pos处的空位 } pq->a[pos]=x; pq->size++;}
⚡️9.尾删·SeqListPopBack
void SeqListPopBack(SEQ*pq){ assert(pq);//防止空指针 assert(pq->size>0); //声明顺序表中有效数据至少有1位才可以进行尾删 --pq->size;}
⚡️10.头删·SeqListPopFront
void SeqListPopFront(SEQ*pq){ assert(pq); assert(pq->size>0); for(int i=0;isize-1;++i) { pq->a[i]=pq->a[i+1]; } --pq->size;}
⚡️11.任意位置删除·SeqListDelet
void SeqListDelete(SEQ* pq,int pos)//删除数组下标为pos的值{ assert(pq); assert(pos>=0&&possize);//保证删除的数组下标由0-(pq->size-1) for(int i=pos;i size-1;++i) { pq->a[i]=pq->a[i+1];//从前往后，挨个前移 } --pq->size;}
⚡️12.按值查找·SeqListFind
int SeqListFind(SEQ*pq,DataType x)//按值查找，返回其对应的第一个数组下标值{ assert(pq); for(int i=0;isize;++i) { if(pq->a[i]==x) return i; } return -1;}
⚡️13.按位修改·SeqListModify
void SeqListModify(SEQ* pq,int pos,DataType x){ assert(pq); assert(pos>=0&&possize);//限制修改范围 pq->a[pos]=x;}
✨✨✨我是分割线✨✨✨
⚡️时间复杂度
时间复杂度的计算细节在这篇文章交代清楚了，如果下面有所不理解，建议先快速看完这篇
?1.插入操作的时间复杂度
最好情况：在表尾插入，原数组元素不移动，时间复杂度为O(1)
最坏情况：在表头插入，原数组元素全部后移（从后往前挨个后移），时间复杂度为O(n)
一般来说所求时间复杂度即为最坏时间复杂度：O(n)
?2.删除操作的时间复杂度
最好情况：删除表尾元素，原数组元素不移动，时间复杂度为O(1)
最坏情况：删除表头元素，原数组元素全部前移（从前往后挨个前移），时间复杂度为O(n)
一般来说所求时间复杂度即为最坏时间复杂度：O(n)
?3.按值查找的时间复杂度
最好情况：查找的元素在表头，时间复杂度为O(1)
最坏情况：查找的元素在表尾，需要遍历到尾，时间复杂度为O(n)
一般来说所求时间复杂度即为最坏时间复杂度：O(n)
✨✨✨我是分割线✨✨✨
源代码总体实现
?SeqList.h
#define _CRT_SECURE_NO_WARNINGS 1#include#include #include typedef int DataType;//将int重定义为DataType//下次想更改数据类型的时候只需要更改前面的int就可以，无需改变整个程序typedef struct SeqList //定义一个顺序表的结构体{ DataType* a;//指示动态分配数组的指针 DataType size;//数组中有效数据的个数 DataType capacity;//数组的容量}SEQ;// 将SeqList这个结构体重定义为SEQ，为了后续方便写程序void SeqListInit(SEQ* pq);void SeqListDestroy(SEQ* pq);void SeqListPrint(SEQ* pq);void SeqCheckCapcity(SEQ* pq);void SeqListPushBack(SEQ* pq, DataType x);void SeqListPushFront(SEQ* pq, DataType x);void SeqListInsert(SEQ*pq,int pos,DataType x);void SeqListPopBack(SEQ*pq);void SeqListPopFront(SEQ*pq);void SeqListDelete(SEQ*pq,int pos);int SeqListFind(SEQ*pq,DataType x);void SeqListModify(SEQ*pq,int pos,DataType x);
?SeqList.c
void SeqListInit(SEQ* pq)//初始化顺序表{ assert(pq);//断言如果为真，就成功通过 //如果为假，即pq为空，则不通过 //断言的好处：不用分析，直接告诉你哪里出错了 pq->a = NULL; pq->size = 0; pq->capacity = 0;}void SeqListDestroy(SEQ* pq)//销毁顺序表{ free(pq->a);//释放动态数组空间 pq->a = NULL;//将指示动态数组的指针置空 pq->size = 0;//将有效数据个数置0 pq->capacity = 0;//将容量个数置0}void SeqListPrint(SEQ* pq) //打印顺序表{ assert(pq);//声明；防止pq空指针 for (int i = 0; i < pq->size; ++i) { printf("%d", pq->a[i]);//防止pq空指针 } printf("/n");}void SeqCheckCapcity(SEQ* pq)//检测动态数组是否需要扩容{ assert(pq); //满了，需要扩容 if (pq->size == pq->capacity) { int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2; //如果动态容量为0，那么将其分配4个空间；否则将其扩容为原先的两倍 DataType* newA = realloc(pq->a, sizeof(DataType) * newcapacity); //为其申请一个新的空间，大小为原先的两倍 if (newA == NULL)//如果新空间的地址为空 { printf("realloc fail/n");//申请空间失败 exit(-1); } pq->a = newA;//将新申请的地址赋予给指针a pq->capacity = newcapacity;//将新申请的空间赋予给capacity }}void SeqListPushBack(SEQ* pq, DataType x){ assert(pq);//声明，预防空指针 SeqCheckCapcity(pq);//检测动态数组是否需要扩容 pq->a[pq->size] = x;//尾插数据 pq->size++;}void SeqListPushFront(SEQ* pq, DataType x)//头插数据{ assert(pq);//声明，防止空指针 SeqCheckCapcity(pq);//检测动态数组是否需要扩容 for(int i=pq->size;i>0;--i) { pq->a[i]=pq->a[i-1]; } pq->a[0]=x; pq->size++;}void SeqListInsert(SEQ*pq,int pos,DataType x)//pos为数组的下标，插在第pos个数组下标初{ assert(pq); assert(pos>=0&&pos<=pq->size);//保证pos的值最小为0，最大为pq->size SeqCheckCapcity(pq); for(int i=pq->size;i>pos;--i) { pq->a[i]=pq->a[i-1];//从后往前，挨个向后移动一位，留出数组下标为pos处的空位 } pq->a[pos]=x; pq->size++;}void SeqListPopBack(SEQ*pq){ assert(pq);//防止空指针 assert(pq->size>0); //声明顺序表中有效数据至少有1位才可以进行尾删 --pq->size;}void SeqListPopFront(SEQ*pq){ assert(pq); assert(pq->size>0); for(int i=0;isize-1;++i) { pq->a[i]=pq->a[i+1]; } --pq->size;}void SeqListDelete(SEQ* pq,int pos)//删除数组下标为pos的值{ assert(pq); assert(pos>=0&&pos size);//保证删除的数组下标由0-(pq->size-1) for(int i=pos;i size-1;++i) { pq->a[i]=pq->a[i+1];//从前往后，挨个前移 } --pq->size;}int SeqListFind(SEQ*pq,DataType x)//按值查找，返回其对应的第一个数组下标值{ assert(pq); for(int i=0;i size;++i) { if(pq->a[i]==x) return i; } return -1;}void SeqListModify(SEQ* pq,int pos,DataType x){ assert(pq); assert(pos>=0&&pos size);//限制修改范围 pq->a[pos]=x;}
? test.c
#include"SeqList.h"void menu(){ printf("*********************/n"); printf("1.尾插数据 2.头插数据/n"); printf("3.尾删数据 4.头删数据/n"); printf("5.查找数据 6.打印数据/n"); printf("0.退出程序 /n"); printf("*********************/n");}int main(){ SEQ s; SeqListInit(&s); int option = 0; int x = 0; do { menu(); scanf("%d", &option); switch (option) { case 1: printf("请输入数据，以-1结束：/n"); while (1) { printf("请输入："); scanf("%d", &x); if (x == -1) break;//跳出当前while循环 SeqListPushBack(&s, x); } break; case 2: printf("请输入数据，以-1结束：/n"); while (1) { printf("请输入："); scanf("%d", &x); if (x == -1) break;//跳出当前while循环 SeqListPushFront(&s, x); } break; case 3: SeqListPopBack(&s); break; case 4: SeqListPopFront(&s); break; case 5: printf("输入想要查找的数字:"); scanf("%d", &x); int num =SeqListFind(&s, x); printf("你想要查找的数字在数组中的下标为%d/n", num); break; case 6: SeqListPrint(&s); break; default: break; } } while (option != 0); return 0;}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123916.html
摘要：它在单链表的基础上优化了很多，例如尾插法等就不用了逐个遍历链表节点，直接就可以找到链表的为节点，实现与添加的新节点连接。文件在文件中实现双向链表的测试，测试双向链表的功能。 ...
摘要：文章首发于公众号一件风衣在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基础，在中，和就可以看作是线性表的实现。 文章首发于公众号一件风衣（ID：yijianfengyi） 在编程中，我们常使用一组有顺序的数据来表示某个有意义的数据，这种一组元素的序列的抽象，就是线性表，简称表，是很多复杂数据结构的实现基...
摘要：线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。链表之单链表线性表的定义，它是一些元素的序列，维持着元素之间的一种线性关系。 线性表学习笔记，python语言描述-2019-1-14 线性表简介 在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含...
摘要：链表都有一个头指针，一般以来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表的特性，使其在某些操作上比数组更加高效。例如当进行插入和删除操作时，链表操作的时间复杂度仅为。 ...
阅读 2825·2021-11-24 10:47
阅读 2326·2021-11-19 09:40
阅读 3591·2021-11-02 14:43
阅读 1959·2021-09-26 10:15
阅读 1837·2021-09-08 09:35
阅读 345·2019-08-30 12:45
阅读 2656·2019-08-29 17:04
阅读 3099·2019-08-26 14:05
