欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
编辑
专栏跑道二
➡️ 24 Network Security -LJS
编辑
编辑
编辑
专栏跑道三
➡️ MYSQL REDIS Advance operation
编辑
专栏跑道四
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
编辑
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
编辑
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
编辑
上节回顾
目录
（13）：给定一个含n个整数的数组Q,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数
（12）：已知一个整数序列A=（a0,a1,an-1），其中若存在则称x为A的主元素。
（11）：一个长度为L的升序序列S，处在第L/2个位置的数称为S的中位数，例如，若序列则S1的中位数是15，两个序列的中位数是11，现在有两个等长升序A和B
（10） ：一个长度为L的升序序列S，处在第L/2个位置的数称为S的中位数，例如，若序列则S1的中位数是15，两个序列的中位数是11，现在有两个等长升序A和B
数据结构王道第2章之顺序表
顺序表的定义和基本操作
定义：
基本操作：
- 用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
基本操作：
- InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
- DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
- ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
- ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
- LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
- GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
- Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
- PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
- Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
- 什么时候要传入参数的引用“&”： 对参数的修改结果需要“带回来”，是引用类型而不是值类型
顺序表的实现-静态分配 
编辑
顺序表的静态分配初始化
// 定义最大长度 typedef struct{ ElemType data[MaxSize]; // 用静态的“数组”存放数据元素 int length; // 顺序表的当前长度 }SqList;
typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList &L) { // 可以省略，但可能由于遍历时用到MaxSize有脏数据，要用length遍历 for (int i = 0; i < MaxSize; i ++ ) L.data[i] = 0; L.length = 0; // 不可省略，顺序表初始长度为0 } int main() { SqList L; // 声明一个顺序表 InitList(L); // 初始化顺序表 return 0; }
如果“数组”存满了怎么办：
可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的），同时如果提前初始化太多的空间而不用，又会造成资源的浪费，因此动态分配应运而生。
动态申请和释放内存空间：
- C：malloc、free函数
- L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);
- malloc函数返回一个指针， 空间需要强制转型为你定义的数据元素类型指针
- malloc函数的参数，指明要分配多大的连续内存空间
- C++： new、delete关键字
顺序表的实现-动态分配：
顺序表的实现：
- 随机访问，即可以在O(1)时间内找到第i个元素。
- 存储密度高，每个结点只存储数据元素
- 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
- 插入、删除操作不方便，需要移动大量元素
顺序表的动态分配初始化代码
// 顺序表的初始长度 typedef struct { ElemType *data; // 指示动态分配数组的指针，这个指针指向顺序表中第一个数据元素 int MaxSize; // 顺序表的最大容量 int length; // 顺序表的当前长度 } SeqList; // 顺序表的类型定义（动态分配方式）
// 动态申请和释放空间 // 在C语言中的函数分别是malloc和free函数 // malloc函数是申请一整片连续的内存空间，且会return一个指向这一整片存储空间开始地址的指针，需要强制转型为你定义的数据元素类型的指针 // L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize); // malloc和free包含在<stdlib.h>头文件中 // 在C++语言中分别是new和delete这两个关键字
- 这样就可以让顺序表的容量可变
- 虽然动态分配可以使顺序表的大小可以灵活改变，但是时间开销还是比较大的（复制元素）
- 注意malloc和free是一对函数
- free函数会把p这个指针所指向的这一整片的存储空间给释放掉，归还给系统，然后由于p是局部于这个函数的变量，函数结束后，存储p这个变量的存储空间会被系统自动回收
编辑
typedef struct { int *data; int MaxSize; int length; } SeqList; void InitList(SeqList &L) { L.data = (int *)malloc(sizeof(int) * InitSize); L.MaxSize = InitSize; L.length = 0; } void IncreaseSize(SeqList &L, int len) { int *p = L.data; L.data = (int *)malloc(sizeof(int) * (L.MaxSize + len)); for (int i = 0; i < L.length; i ++ ) L.data[i] = p[i]; L.MaxSize = L.MaxSize + len; free(p); } int main() { SeqList L; InitList(L); // ...往顺序表中随意随便插入几个元素 IncreaseSize(L, 5); return 0; }
顺序表的特点
- 随机访问，即可以在O ( 1 ) O(1)O(1)时间内找到第i个元素（不论是静态分配还是动态分配代码都是d a t a [ i − 1 ] data[i - 1]data[i−1]
- 存储密度高，每个节点只存储数据元素（链表还要存指针）
- 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
- 插入、删除操作不方便，需要移动大量元素
顺序表的插入删除
顺序表的基本操作-插入：
- ListInsert(&L, i, e) ：插入操作，在表L中的第i个位置（位序）插入指定元素i
- 本节代码建立在顺序表的“静态分配”实现方式之上，“动态分配”也雷同。
- 时间复杂度的平均情况 ：p = 1 / ( n + 1 ) p=1/(n+1)p=1/(n+1)；i=1，循环n次，i=2，循环n-1次…；平均循环次数= n p + ( n − 1 ) ∗ p + . . . + 1. p = n ∗ ( n + 1 ) / 2 ∗ 1 / ( n + 1 ) = n / 2 =np+(n-1)*p+...+1.p=n*(n+1)/2*1/(n+1)=n/2=np+(n−1)∗p+...+1.p=n∗(n+1)/2∗1/(n+1)=n/2
typedef struct { int data[MaxSize]; int length; } SqList; bool ListInsert(SqList &L, int i, int e) { if (i < 1 || i > L.length + 1) // 判断i的范围是否有效 return false; if (L.length == MaxSize) // 当前存储空间已满，不能插入 return false; for (int j = L.length; j >= i; j -- ) // 将第i个元素及之后的元素后移 L.data[j] = L.data[j - 1]; L.data[i - 1] = e; // 在位置i处放e L.length ++ ; // 长度加1 return true; // 反馈 } int main() { SqList L; InitList(L); // ...插入一些元素 ListInsert(L, 5, 5); return 0; }
增加i的合法性判断： 
顺序表的基本操作——删除 
bool ListDelete(SqList &L, int i, int &e) { if (i < 1 || i > L.length) // 判断i的范围是否有效 return false; e = L.data[i - 1]; // 将被删除的元素赋给e for (int j = i; j < L.length; j ++ ) // 将第i个位置后的元素前移 L.data[j - 1] = L.data[j]; L.length -- ; // 线性表长度减一 return true; } int main() { SqList L; InitList(L); // ...插入一些元素 int e = -1; // 用变量e把删除的元素“带回来” if (ListDelete(L, 3, e)) printf("已删除第3个元素，删除元素值为=%d\n", e); else printf("位序i不合法，删除失败"); }
- ListDelete(&L, i, &e) ：删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值
- 因为要返回e，所以这要有一个引用操作，因此，在这个函数中操作的变量e，在内存中其实对应的是同一份数据
- 在删除操作中是先移动前面的元素再移动后面的元素，而在插入操作中要把元素往后移时，先把后面的元素往后移，然后再移前面的元素
插入和删除的时间复杂度：
- 最好时间复杂度= O(1)
- 最坏时间复杂度= O(n)
- 平均时间复杂度= O(n)
顺序表的查找
顺序表的按位查找： 
顺序表的按位查找代码
// 静态分配实现顺序表，动态分配实现的顺序表也是如此 ElemType GetElem(SqList L, int i) { // 判断i合法性 return L.data[i - 1]; }
- GetElem(L, i) ：按位查找操作。获取表L中第i个位置的元素的值
- 正是如此，在初始化顺序表时候malloc需要强制转换为与数据元素的数据类型相对应的指针
- 时间复杂度= O(1)
- 随机存取：由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，
顺序表的按值查找： 
顺序表的按值查找代码
typedef struct { ElemType *data; int MaxSize; int length; } SeqList; ElemType LocateElem(SeqList L, ElemType e) { for (int i = 0; i < L.length; i ++ ) if (L.data[i] == e) return i + 1; // 返回位序 return 0; }
- LocateElem(L, e) ：按值查找操作，在表L中查找具有给定关键字值的元素
- 结构类型的数据元素也能用 == 比较吗：不能！（C++可以用 == 的重载来实现）
- 更好的办法：定义一个函数
- 依次对比各个分量来判断两个结构体是否相等
- 最好时间复杂度= O(1)
- 最坏时间复杂度= O(n)
- 平均时间复杂度= O(n)
结构类型的比较
- 在C语言中，结构类型的比较不能直接用“==”，需要依次对比各个分量来判断两个结构体是否相等；如果C++，则可以用重载 “= =“。
- 但是，《数据结构》考研初试中，手写代码可以直接用“= =”，无论ElemType是基本数据类型还是结构类型。但是有的学校考《C语言程序设计》，那么也许语言就要严格一些。最好还是看一下相关的历年真题。
