南县建设局网站,域名主机 网站建设,东莞网站推广多少钱,万网做网站怎么样别丢了你的勇敢 前言#xff1a;
自今日起#xff0c;我们正式越过C语言的大山#xff0c;走向了数据结构的深山#xff0c;现如今摆在我们面前的第一个坎就是顺序表#xff0c;我们需要了解顺序表的定义#xff0c;并且知道#xff0c;如何对其进行增删查改#xff0… 别丢了你的勇敢 前言
自今日起我们正式越过C语言的大山走向了数据结构的深山现如今摆在我们面前的第一个坎就是顺序表我们需要了解顺序表的定义并且知道如何对其进行增删查改之后我们需要在此处基础上写出一份通讯录代码ok顺序表启动
1.什么是顺序表
1.1线性表 线性表 linear list 是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 线性表指的是具有部分相同特性的⼀类数据结构的集合 1.2顺序表 顺序表是一种线性表的数据结构它是由一组具有相同特性的数据元素按照一定的顺序排列而成的。顺序表的底层结构是数组对数组的封装实现了常⽤的增删改查等接口。 顺序表可以使用数组来实现也可以使用动态数组来实现。 顺序表分为静态顺序表和动态顺序表 静态顺序表是使用固定长度的数组来存储元素数组的长度在创建时就确定了无法改变。静态顺序表的优点是访问元素的时间复杂度为O(1)缺点是插入和删除元素的时间复杂度较高。 图片来自比特就业课官网链接https://www.bitejiuyeke.com 动态顺序表是使用可以动态开辟的数组来存储元素数组的长度可以根据需要进行动态调整。动态顺序表的优点是可以灵活地插入和删除元素缺点是访问元素的时间复杂度为O(1)。 顺序表是一种常见的数据结构它在实际中被广泛使用常见的应用场景包括数组、字符串等。 图片来自比特就业课官网链接https://www.bitejiuyeke.com
动态顺序表和静态顺序表的使用是极其相似的只是静态的顺序表建立在栈区动态顺序表通过动态内存分配建立于堆区由于动态涉及了动态内存分配难度会稍稍高一些所以我们今天的增删查改直接是以动态顺序表为对象如果你能明白了这个那静态顺序表也是同样的原理也是可以写出来的。
2、 动态顺序表的实现
2.1头文件
⭐️ 我先把头文件列出来让各位先知道我们要实现的内容有什么 # define INIT_CAPACITY 4 typedef int SLDataType; // 动态顺序表 -- 按需申请 typedef struct SeqList { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 }SL; //初始化顺序表 void SLInit (SL* ps); // 销毁顺序表 void SLDestroy (SL* ps); // 打印顺序表内容 void SLPrint (SL* ps); // 扩容 void SLCheckCapacity (SL* ps); //尾 部插⼊ 数据 void SLPushBack (SL* ps, SLDataType x); //尾 部删除 数据 void SLPopBack (SL* ps); // 头部插⼊ 数据 void SLPushFront (SL* ps, SLDataType x); // 头部删除 数据 void SLPopFront (SL* ps); // 指定位置插⼊ 数据 void SLInsert (SL* ps, int pos, SLDataType x); // 指定位置 删除数据 void SLDelete(SL* ps, int pos); // 指定位置修改 数据 void SLModify(SL* ps, int pos,SLDataType x); // 指定位置查找 数据 void SLSearch(SL* ps, int pos, SLDataType x); 2.2具体分析
ok然后咱们从上到下挨个分析
2.2.1 #define INIT_CAPACITY 4 这是一个宏定义也是我们初始化默认通讯录的初始容量即四个单位空间
2.2.2 typedef int SLDataType; 这是用typedef给int换了个名字这时候肯定有人会问了为啥不直接用int
⭐️ 原因如下
我们的顺序表是对数组的封装但我们不能确实是什么类型的数组如果我直接用int那后面代码里也都是int可假如我后来想给这个数组换成char类型呢那我就要把所有int都改为char于是乎我们直接用typedef创建一个类型名之后代码也都用这个类型名这样我之后想修改就只需要把
typedef int SLDataType改为typedef char SLDataType就ok了
这点在我们之后写通讯录时会体现出来 2.2.3 typedef struct SeqList { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 }SL; 这是一个结构体SLDataType*是顺序表中存储的元素类型size是当前顺序表的存储数据数量 capacity是顺序表的存储数据数量最大值。 2.2.4 void SLInit (SL* ps); 这是对顺序表的初始化我们传一个顺序表变量进去该函数对其进行初始化具体如下 给ps-a开辟了4个单位空间 将通讯录目前数据数量设置为0 容量设置为4 void SLInit(SL* ps) { ps-a (SLDataType*)malloc(CAPACITY * sizeof(SLDataType)); ps-size 0; ps-capacity 4; } 2.2.5 void SLDestroy (SL* ps); 有初始化就有销毁当我们要退出程序时要对顺序表的内容进行销毁这时候有人要问了程序退出不是会自动销毁吗为什么还要再写一个函数呢 ✨答我们使用了动态内存开辟有开辟就要有释放当你不用它时就释放它是一个好的代码习惯不然如果一直想着靠结束代码时释放空间以后当你写项目时就容易忘记及时释放空间导致内存泄漏。 ✨具体如下 把之前的空间释放掉 把通讯录目前的数据数量设置为0 把通讯录容量设置为0 void SLDestroy(SL* ps) { free(ps-a); ps-a NULL; ps-size 0; ps-capacity 0; 2.2.6 void SLPrint (SL* ps); 这个是打印顺序表的信息直接遍历数组挨个打印就可以 循环控制条件依靠顺序表中的ps-size就可以 void SLPrint(SL* ps) { for (int i 0; i ps-size; i) printf(%d , ps-a[i]); } 2.2.7 void SLCheckCapacity (SL* ps); 要知道我们给顺序表设置的初始容量只有4个单位在你不断输入数据的情况下他很快就会满于是我们就需要设置一个函数用来给顺序表扩容 直接调用realloc函数就可以 这里我们的扩容方式是直接将容量扩大到现在容量的2倍 为什么不是扩大一个固定的数呢 假如我们每次扩2个或3个那很容易就会不够扩容很频繁导致性能消耗如果一次扩1000个2000个又很容易空间浪费但如果我们以倍数扩容随着空间越来越大每次增加的空间也会越来越大这样扩容就不会很频繁浪费空间也不会很多我们通常是采用2倍扩容或1.5倍扩容至于为什么是这俩数字就涉及到数学原理了我能力有限无法作答。去找你数分的朋友吧 void SLCheckCapacity(SL* ps) { SLDataType* p (SLDataType*)realloc(ps-a, 2 * ps-capacity * sizeof(SLDataType)); if (p NULL) { perror(realloc fail); exit(1); } ps-a p; ps-capacity * 2; } 这里有个小知识点别忘了realloc会自动释放之前的空间所以不用free了 2.2.8 void SLPushBack(SL* ps, SLDataType x); ☄️这个是尾插
在增加之前判断一下顺序表是不是满了如果满了就调用扩容函数再来一个尾插也就是在数组最后面加入元素之后直接在末尾加上该元素即可 void SLPushBack(SL* ps, SLDataType x) { if (ps-size 1 ps-capacity) SLCheckCapacity(ps); ps-a[ps-size] x; (ps-size); } 2.2.9 void SLPopBack (SL* ps); ☄️ 这个是尾删 尾删之前要判断一下顺序表是不是空的如果是就打印提示信息若不是就把最后一个元素设置其值为0然后把顺序表的当前数据数量减一 void SLPopBack(SL* ps) { if (ps-size - 1 0) { printf(顺序表空了无法删除\n); //perror(SLPopFront Fail); return ; } ps-a[ps-size - 1]0; (ps-size)--; } 2.2.10 void SLPushFront (SL* ps, SLDataType x); ☄️这个是头插比尾插麻烦一些 第一步还是检验顺序表是不是满了第二步我们要通过循环把所有元素集体向后移动一个单位然后在空出来的第一个位置插入我们要插的值。记得ps-size void SLPushFront(SL* ps, SLDataType a) { if (ps-size 1 ps-capacity) SLCheckCapacity(ps); for (int i 1; i ps-size; i) { ps-a[i] ps-a[i - 1]; } (ps-size); ps-a[0] a; } 2.2.11 void SLPopFront (SL* ps); ☄️ 这个是头删 第一步检验顺序表是不是为空第二步通过循环把元素集体向前移动一个单位从而覆盖掉第一个元素第三步ps-size-- void SLPopFront(SL* ps) { if (ps-size - 1 0) perror(SLPopFront Fail); for (int i 0; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-a[ps-size - 1] 0; (ps-size)--; } 2.2.12 void SLInsert (SL* ps, int pos, SLDataType x); ☄️ 指定位置之前插⼊数据 第一步检查是否需要扩容第二步通过循环让下标pos及pos之后的元素集体后移一个单位第三步把数据放入下标为pos的地方 void SLInsert(SL* ps, int pos, SLDataType x) { if (ps-size 1 ps-capacity) SLCheckCapacity(ps); for (int i ps-size; i pos; i--) ps-a[i] ps-a[i - 1]; ps-a[pos] x; ps-size; } 2.2.13 void SLDelete(SL* ps, int pos); ☄️ 指定位置删除数据 第一步检查顺序表是否为空第二步通过循环把下标pos之后的元素向前移动一个单位从而覆盖掉pos对位空间的值第三步ps-size-- void SLDelete(SL* ps, int pos) { if (ps-size - 1 0) { printf(顺序表空了\n); //perror(SLPopFront Fail); return; } for (int i pos; i ps-size - 1; i) ps-a[i] ps-a[i 1]; ps-size--; } 2.2.14 void SLModify(SL* ps, int pos,SLDataType x); ☄️这个是修改数据 先判断下标是否有效 若有效则修改数据 void SLModify(SL* ps, int pos,SLDataType x) { if (pos ps-size) printf(要修改的元素不存在\n); else ps-a[pos] x; } 2.2.15 void SLSearch(SL* ps, int pos, SLDataType x); ☄️查找数据 先判断下标是否有效 若有效则打印数据 { if (pos ps-size) printf(要查找的元素不存在\n); else printf(%d\n,ps-a[pos]); } ok至此我们知道了什么是顺序表顺序表的增删查改四种功能我们也都实现了可以说是迈出了相当大的一步下一次我们将会在此基础上实现通讯录 我先把要求放下面了感兴趣的朋友可以自己动手试试哦 . 基于动态顺序表实现通讯录 C语⾔基础要求结构体、动态内存管理、顺序表、⽂件操作 1、功能要求 1⾄少能够存储100个⼈的通讯信息 2能够保存⽤⼾信息名字、性别、年龄、电话、地址等 3增加联系⼈信息 4删除指定联系⼈ 5查找制定联系⼈ 6修改指定联系⼈ 7显⽰联系⼈信息 当然了与这次的顺序表不同的是我们下次还会用到文件操作来保存你存入的数据毕竟写完就丢也太离谱了。 ok那么今天在数据结构的第一场战役就打完了倘若你觉得我的博客对你有帮助就请点个免费的赞支持一下吧。
