一、线性表
线性表的基本概念
数据结构的三要素:逻辑结构、数据的运算、存储结构(物理结构)
线性表的定义
线性表是具有相同数据类型的n(n>=0)个元素的有限序列。
![image-20210726165542066](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165542.png)
线性表的基本操作
![image-20210714142852531](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210714142852.png)
什么时候要传入参数的引用“&”?
一种是值类型,使用时会直接复制原值,修改参数不会影响原值
![image-20210726165629504](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165629.png)
一种是引用类型,使用时操作的是原值,修改时直接修改原值!(C语言不支持这种引用类型!)
![image-20210726165653031](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165653.png)
为什么要实现对数据结构的基本操作?
- 团队合作编程,你定义的数据结构要让别人能够很方便的使用(封装)
- 将常用的操作/运算封装称函数,避免重复工作,降低出错风险。
总结
![image-20210726165707503](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165707.png)
注意⚠️:位序是用1开始计算的!!!
二、顺序表
顺序表的基本概念
![image-20210726165751315](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165751.png)
顺序表的定义
![image-20210726165814325](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165814.png)
顺序表的初始化
静态分配
![image-20210726165934947](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165935.png)
具体实现:
![image-20210726165957878](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726165957.png)
//初始化(静态分配)
void InitList(SqList &L){
for (int i = 0; i < MaxSize; i++) {
L.data[i]=0;//将所有元素的初始值默认设置为0
//这一步其实可以省略,但是省略之后,有可能受到内存中"脏数据"的影响
}
L.length=0;
}
问题反思
- 如果“数组”存满留怎么办?
可以放弃治疗,顺序表长刚开始确定后就无法更改(存储空间是静态的)
- 如果一开始就声明一个很大的内存空间呢?会存在什么问题?
浪费,会造成大量的浪费。
动态分配
![image-20210726170057124](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170057.png)
具体实现方式
![image-20210726170149840](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170149.png)
//初始化(动态方式)
bool InitList(SeqList &L){
//用 malloc 函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
if (L.data==NULL)
//要细心呀,这里不小心写成了赋值语句,但是没有报错,找了半天错误!
return false;
//(int *) 是指针的强制类型转换
L.length=0;
L.MaxSize=InitSize;
return true;
}
总结
![image-20210726170235236](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170235.png)
![image-20210726170253436](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170253.png)
顺序表的基本操作
插入
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
![image-20210726170337008](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170337.png)
详细实现方式:
![image-20210726170413544](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170413.png)
优化之后:
![image-20210726170444785](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170444.png)
bool ListInsert(SqList &L,int i,int e){
//判断插入的位置是否合法,
if (i<1||i>L.length+1)
return false;
//判断表是否存满了
if (L.length>=MaxSize)
return false;
//后面的元素后移
for (int j = L.length; j >=i ; j--) {
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
return true;
}
插入操作的时间复杂度分析
![image-20210726170529928](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170529.png)
删除
![image-20210726170624021](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170624.png)
//删除
bool ListDelete(SqList &L,int i,int &e){
//判断i的位置是否合法
if(i<0||i>L.length){
return false;
}
//取出将要被删除的数
e=L.data[i-1];
//将其后的数据前移
for (int j = i; j <=L.length ; j++) {
L.data[j-1]=L.data[j];
}
//线性表长度减一
L.length--;
return true;
}
删除操作的时间复杂度分析
![image-20210726170650571](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170650.png)
总结反思
![image-20210726170800756](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170800.png)
查找
按位查找
GetElem(L,i):按位查找操作,获取表L中第i个位置的元素的值
静态分配状态下的实现方式
![image-20210726170924353](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726170924.png)
动态分配状态下的实现方式
![image-20210726171023978](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171024.png)
用指针加数组下标的方式取数据的时候,数组类型决定着取数据时取几个字节!!
//按位查找
int GetElem(SeqList L,int i){
//判断是否越界
if (i<0||i>L.length)
return -1;
return L.data[i-1];
}
按位查找的时间复杂度分析
![image-20210726171108725](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171108.png)
按值查找
//按值查找
int LocateElem(SeqList L,int e){
//循环出查找
for (int i = 0; i <L.length ; i++) {
if (L.data[i]==e)
return i+1; //返回位序
}
return -1;
}
结构类型的比较
![image-20210726171356300](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171356.png)
注意:考研初试中华,手写代码可以直接用“==”,无论是ElemType是基本数据类型还是结构类型,手写代码主要考察学生是否理解算法思想,不会严格要求代码完全可运行
有的学校复试考《C语言程序设计》,那么。。。也许就要语法严格一些!
按值查找的时间复杂度
![image-20210726171428131](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171428.png)
总结反思
![image-20210726171447192](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171447.png)
三、单链表
![image-20210726171938045](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171938.png)
![image-20210726171956844](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726171956.png)
什么是单链表?
![image-20210726172046492](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726172046.png)
单链表的定义
![image-20210726172308710](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726172308.png)
别名
![image-20210726172355951](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726172356.png)
![image-20210726173031900](C:/Users/king/AppData/Roaming/Typora/typora-user-images/image-20210726173031900.png)
注释:或者可以理解为指向头节点的指针既可以表示整个单链表也可以表示头节点,为了便于区分才建议使用 typedef 进行重命名,以方便区别其不同的含义
头插法建立单链表
![image-20210726173037377](C:/Users/king/AppData/Roaming/Typora/typora-user-images/image-20210726173037377.png)
单链表的基本操作
单链表的初始化
不带头节点的单链表的初始化
![image-20210726173251759](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173251.png)
带头节点的单链表的初始化
![image-20210726173316379](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173316.png)
两者区别是什么?
![image-20210726173350478](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173350.png)
总结
![image-20210726173409650](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173409.png)
插入和删除
![image-20210726173426154](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173426.png)
插入
按位序插入(带头节点的单链表)
![image-20210726173553880](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173553.png)
具体实现
分析在表头插入
![image-20210726173606226](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173606.png)
分析为什么不能颠倒
![image-20210726173627335](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173644.png)
分析在表中插入
![image-20210726173755324](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173755.png)
分析在表尾插入
![image-20210726173814139](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726173822.png)
分析插入位置超出表长
![image-20210726174510989](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726174511.png)
总结
![image-20210726174524978](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726174525.png)
按位插入(不带头节点)
![image-20210726174651203](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726174651.png)
具体实现
![image-20210726174722358](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726174722.png)
结论:不带头节点的单链表,写代码更不方便,除非特别声明,默认推荐使用带头节点的实现方式,还有要注意在考试中带头、不带头都有可能考察,注意审题。
指定节点的后插操作
![image-20210726174829417](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726174829.png)
指定节点的前插操作
通过传入头指针实现前插
![image-20210726174907717](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726174907.png)
先进行后插,然后交换前后数据,以此实现前插
![image-20210726175051748](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175051.png)
![image-20210726175109994](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175110.png)
删除
带有头节点版本
![image-20210726175540485](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175540.png)
具体实现
![image-20210726175558302](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175558.png)
删除指定结点
![image-20210726175752937](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175752.png)
![image-20210726175620098](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175620.png)
如果P是最后一个节点,咋办?
只能从表头表头依次寻找前驱,时间复杂度O(n)
![image-20210726175657466](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726175657.png)
单链表的局限性:无法逆向检索!!
封装的好处
![image-20210726180212442](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180212.png)
总结
![image-20210726180022284](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180022.png)
查找
按位查找(带头节点)
![image-20210726180424982](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180425.png)
按值查找(带头节点)
![image-20210726180601573](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180601.png)
求表的长度(带头节点)
![image-20210726180633120](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180633.png)
总结
![image-20210726180647007](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180647.png)
单链表的建立方法
![image-20210726180722977](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180723.png)
PS:找不到对象就娶一个数据元素吧!哈哈
尾插法
第一种方法:
![image-20210726180756970](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180757.png)
问题:时间复杂度太高!!可以用一个指针记录最后一个数据元素的位置来优化时间。
优化之后:
![image-20210726180831940](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180832.png)
头插法
![image-20210726180918378](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180918.png)
具体实现:
![image-20210726180959158](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726180959.png)
总结
![image-20210726181011287](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726181011.png)
四、双链表
![image-20210726183619952](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183619.png)
单链表VS双链表
![image-20210726183634075](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183634.png)
双链表基本操作
初始化
![image-20210726183648351](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183648.png)
插入
![image-20210726183702070](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183702.png)
优化之后
![image-20210726183719251](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183719.png)
删除
![image-20210726183736686](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183736.png)
遍历
![image-20210726183755465](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183755.png)
总结反思
![image-20210726183805516](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183805.png)
五、循环链表
![image-20210726183828015](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183828.png)
循环单链表
![image-20210726183837306](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183837.png)
具体实现:
![image-20210726183919767](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183919.png)
优势:
![image-20210726183938049](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183938.png)
![image-20210726183945708](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183945.png)
循环双链表
![image-20210726183959302](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726183959.png)
初始化
![image-20210726184007969](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184008.png)
插入
![image-20210726184017781](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184017.png)
删除
![image-20210726184031060](C:/Users/king/AppData/Roaming/Typora/typora-user-images/image-20210726184031060.png)
总结反思
![image-20210726184109253](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184109.png)
六、静态链表
![image-20210726184147026](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184147.png)
什么是静态链表?
![image-20210726184225973](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184226.png)
定义一个静态链表
方法1:
![image-20210726184303172](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184303.png)
方法2:
![image-20210726184338410](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184338.png)
验证方法2的定义方法
![image-20210726184446751](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184446.png)
基本操作
![image-20200620162512284](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184539.jpeg)
总结反思
![image-20200620162709709](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184543.jpeg)
七、线性表章节复习反思
![image-20210726184719982](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184720.png)
逻辑结构对比
![image-20210726184743873](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184743.png)
存储结构对比
![image-20210726184757954](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184758.png)
基本操作对比
![image-20210726184809121](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184809.png)
初始化(创建)
![image-20210726184828780](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184828.png)
销毁
增加/删除
![image-20210726184923124](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184923.png)
查找
![image-20210726184934771](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726184934.png)
总结
具体使用时,需要根据具体场景去选择
开放式答题的思路
![image-20210726185015579](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726185015.png)