免费做自己的网站ppt内容素材大全免费

当前位置： 首页 > news >正文

免费做自己的网站,ppt内容素材大全免费,北京网站优化厂家,市场监督管理局待遇如何目录 1.线性表的概念 2.线性表的基本操作 3.存储线性表的方式 #xff08;1#xff09;顺序表 •顺序表的概念 •顺序表的实现 静态分配#xff1a; 动态分配#xff1a; 顺序表的插入#xff1a; 顺序表的删除#xff1a; 顺序表的按位查找#xff1a; 顺序…目录 1.线性表的概念 2.线性表的基本操作 3.存储线性表的方式 1顺序表 •顺序表的概念 •顺序表的实现 静态分配 动态分配 顺序表的插入 顺序表的删除 顺序表的按位查找 顺序表的按值查找 顺序表的特点 2单链表 •单链表的实现 不带头结点的单链表 带头结点的单链表 单链表的插入 ▴按位序插入带头结点 ▴按位序插入不带头结点 ▴指定结点的后插操作 ▴指定结点的前插操作 单链表的删除 ▴按位序删除带头结点 ▴按位序删除不带头结点 ▴指定结点的删除 单链表的查找 ▴按位查找 ▴按值查找 单链表的长度 单链表的两种建立方法 ▴尾插法建立单链表 ▴头插法建立单链表 3双链表 • 双链表的实现 双链表的初始化 双链表的插入 双链表的删除 双链表的销毁 双链表的遍历 4循环链表 • 循环单链表 • 循环双链表 5静态链表 •静态链表的相关概念 •静态链表的定义 •静态链表的相关基本操作 6顺序表和链表的对比 1.逻辑结构 2.物理结构存储结构 3.数据运算/基本操作 •初始化 •销毁 •增删 •查找 •总结 1.线性表的概念 线性表是具有相同数据类型的n(n0)个数据元素的有限序列其中n为表长当n0时线性表是一个空表。若用L命名线性表则其一般表示为 L(a1,a2,…,ai,ai1,…,an) 注 1.这里的“相同”是指每个数据元素所占空间一样大同时强调有限序列例如所有整数按递增次序排列虽然有次序但是对象是所有整数所以不是线性表。 2.ai是线性表中的“第i个”元素线性表中的位序位序从1开始数组下标从0开始。 3.a1是表头元素an是表尾元素。4.除第一个元素外每个元素有且仅有一个直接前驱除最后一个元素外每个元素有且仅有一个直接后继。 2.线性表的基本操作 初始化销毁增删改查 •InitList(L)初始化表。构造一个空的线性表L分配内存空间。 •DestroyList(L)销毁操作。销毁线性表并释放线性表L所占用的内存空间。 •Listlnsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e。 •ListDelete(Li,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。 关于: 对于下面的代码 在main函数中定义了一个变量x1接着调用test()test(int x)中的“x”其实是main函数中“x”的复制品两个x是不同的数据占用不同的内存空间所以test()中定义的x的值其实修改的是复制品x的值并没有修改main()中变量x的值。 所以输出的结果中调用test后x1。 对比下面这段代码 test(int x)参数x为引用类型所以test()中操作的参数“x”与main()中的“x”是同一份数据占用同一个空间所以在test()中对x的修改会影响到main()中x的值即对参数的修改带回到了main()中。 3.存储线性表的方式 1顺序表 •顺序表的概念 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。 设线性表第一个元素的存放位置是 LOC(L)由于每个数据元素在物理上连续存放并且每个数据元素所占空间大小相同。所以有 •顺序表的实现 静态分配 #define MaxSize 10 //定义最大长度 typedef struct{ ElemType data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度 }SqList; //顺序表的类型定义(静态分配方式)/这里的ElemType指的是元素的类型可以是int也可以是struct这取决于顺序表存储的数据类型/ 具体地看个示例  #includestdio.h #define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度 }SqList; //顺序表的类型定义(静态分配方式)//初始化一个顺序表 void InitList(SqList L){for(int i0;iMaxSize;i)L.data[i]0; //将所有数据元素设置为默认初始值L.length0; //顺序表初始长度为0
}int main(){SqList L; //声明一个顺序表表示在内存中分配存储顺序表L的空间包括:MaxSize*sizeof(ElemType)和 存储 length 的空间InitList(L); //初始化顺序表return 0; } 若没有设置默认数据元素的默认值 #includestdio.h #define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度 }SqList; //顺序表的类型定义(静态分配方式)//初始化一个顺序表 void InitList(SqList L){L.length0; //顺序表初始长度为0
}int main(){SqList L; InitList(L); //初始化顺序表//违规打印整个data数组for(int i0;iMaxSize;i)printf(data[%d]%d\n,i,L.data[i]);return 0; } 打印结果如下 不同的计算机中运行此代码结果都会不同这是因为内存中会遗留“脏数据”。虽然声明顺序表之后系统会分配一块内存空间但是这片内存空间之前存放的是什么我们是不知道的所以如果不设置默认值的话之前的脏数据就会遗留下来。 其实不设置默认初始值是可以的只要将iMaxSize改为iL.length就是不从第一个元素访问到最后一个元素而是从第一个元素访问到实际存储的最后一个元素。例如当前没有存储任何数据那么系统就不会打印任何值。 #includestdio.h #define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度 }SqList; //顺序表的类型定义(静态分配方式)//初始化一个顺序表 void InitList(SqList L){L.length0; //顺序表初始长度为0
}int main(){SqList L; InitList(L); //初始化顺序表for(int i0;iL.length;i)printf(data[%d]%d\n,i,L.data[i]);return 0; } 静态分配中顺序表的内存空间是固定的若设置的内存空间过小那么数组很容易被存满如果过大则浪费内存空间。所以可以采用动态分配。 动态分配 //malloc和free函数的头文件 #includestdlib.h #define InitSize 10 typedef struct{int *data; //指示动态分配数组的指针这里是整型指针int MaxSize;int length; }SeqList;//使用malloc和free动态申请和释放内存空间 void InitList(seqList L){L.data(int *)malloc(InitSize*sizeof(int)); //malloc函数的参数指明要分配多大的连续内存空间 //malloc函数返回一个指针需要强制转型定义的数据类型指针在这里就是(int *)L.length0;L.MaxSizeInitSize; }void IncreaseSize(SeqList L,int len){int *pL.data;L.data(int *)malloc(L.MaxSizelen)*sizeof(int);for(int i0;iL.length;i){L.data[i]p[i];}L.MaxSizeL.MaxSizelen;free(p);
}int main(){SeqList L;InitList(L);IncreaseSize(L,5);return 0;}在IncreaseSize中 int *pL.data表示p指针与data指针指向同一个内存空间 L.data(int *)malloc(L.MaxSizelen)sizeof(int)表示新分配一个内存空间此空间包括原来顺序表的最大长度以及新增加的长度len。同时将data指针指向这个内存空间。  for(int i0;iL.length;i){         L.data[i]p[i];     }     L.MaxSizeL.MaxSizelen; 表示将原来的数据复制到新的区域中并且改变最大长度为新增内存空间的长度 free(p)表示释放原来的内存空间归还给系统。由于p变量是局部变量所以执行完free(p)之后存储p变量的内存空间也会被回收。 至此就实现了动态增加数组长度的操作。由于需要将旧数据复制到新的内存空间所以会增加时间开销。 顺序表的插入 之前讲过在第i个位置上插入元素需要将i及以后的元素都往后移动一位。这里是基于“静态分配的代码。 #include stdio.h#define MaxSize 10typedef struct {int data[MaxSize];int length; } SqList;void InitList(SqList L) {L.length 0; }// 在L的位序i中插入元素e 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–)L.data[j] L.data[j - 1]; // 将第i个元素及之后的元素后移L.data[i - 1] e; // 在位置i上放入eL.length; // L长度加1return true; }int main() {SqList L;InitList(L);for (int i 0; i 5; i) {ListInsert(L, i 1, i 1); // 插入元素自动更新长度}printf(插入前的顺序表为:\n);for (int i 0; i L.length; i) {printf(%d , L.data[i]);}printf(\n);ListInsert(L, 3, 99); // 在第3位插入元素99printf(插入后的顺序表为:\n);for (int i 0; i L.length; i) {printf(%d , L.data[i]);}printf(\n);return 0; }实现结果 插入操作的时间复杂度最深层循环语句的执行次数与问题规模 n的关系是多少呢 注问题规模n就是线性表的表长L.length 最好情况新元素插入到表尾不需要移动元素 in1循环0次最好时间复杂度O(1) 最坏情况新元素插入到表头需要将原有的n个元素全都向后移动 i1循环n次最坏时间复杂度O(n) 平均情况假设新元素插入到任何一个位置的概率相同即i1,2,3,…,length1的概率都是p 1/n1 i1循环n次i2时循环n-1次i3循环n-2次…in1时循环0次 循环n次的概率是p循环n-1的概率也是p依此类推将p提出来就是 p[n(n-1)(n-2)·····0]O(n) 顺序表的删除 删除表与插入表的操作相反就是将要删除的元素的后面的元素往前移动一位并且length值减1 #includestdio.h #define MaxSize 10 typedef struct{int data[MaxSize];int length; } SqList;void InitList(SqList L){L.length 0; }bool ListDelete(SqList L,int i,int e){if(i1 || iL.length)return false;eL.data[i-1];for(int ji;jL.length;j) //将被删除的元素赋给eL.data[j-1]L.data[j]; //将第i个位置后的位置前移L.length–; //线性表长度减1return true; }int main() {SqList L;InitList(L);printf(顺序表为:\n); for (int i 0; i 5; i) {L.data[i] i 1;printf(%d , L.data[i]);L.length;}int e-1; //声明一个变量e初始值设为-1if(ListDelete(L,3,e))printf(\n已删除第3个元素删除元素值%d\n,e); elseprintf(位序i不合法删除失败\n);printf(删除元素后的顺序表为:\n); for(int i0;iL.length;i){printf(%d ,L.data[i]);}return 0;
}实现结果 注意 1 bool ListDelete(SqList L,int i,int e)这里的参数e一定要是引用类型的即删除e再把e的值返回。 首先在main()中声明一个变量e初始值为-1 接着调用ListDelete()时会把要删除的变量的值复制到e变量所对应的内存区域中即 eL.data[i-1]; 最后for循环将删除元素之后的元素依次往前移动并且length值减1 2 删除操作中i位置后的元素往前移是先从前面的元素往前移动的而插入操作中是先从后面的元素往后移动的。这个应该很好理解。 删除操作的时间复杂度是多少呢 最好情况删除表尾元素不需要移动其他元素 in循环0次最好时间复杂度O(1) 最坏情况删除表头元素需要将后续的n-1个元素全都向前移动i1循环 n-1次最坏时间复杂度0(n) 平均情况假设删除任何一个元素的概率相同即i1,2,3,…,length的概率都是p1/n i1循环 n-1次i2 时循环 n-2 次i3循环 n-3 次…in时循环0次 平均时间复杂度O(n) 写代码要注意 1.题目中的i是位序i从1开始还是数组下标i从0开始例如第3个元素其实数组下标为2。 2.算法要有健壮性注意判断i的合法性。 顺序表的按位查找 //静态分配方式 #define MaxSize 10 typedef struct{int data[MaxSize];int length; } SqList;ElemType GetElem(SqList L,int i){return L.data[i-1]; }//动态分配 #define InitSize 10 typedef struct{ElemType *data;int MaxSize;int length; } SeqList;ElemType GetElem(SeqList L,int i){return L.data[i-1]; }对于ElemType *data如果一个ElemType 占6B,即 sizeof(ElemType)6指针 data 指向的地址为 2000。 如图所示计算机会根据指针所指向数据类型的空间大小计算每个数组下标对应哪些字节的数据。 例如int型变量 这就可以解释L.data(int *)malloc(InitSize*sizeof(int))使用malloc分配内存空间时需要强制转换数据类型虽然指针指向的是同一个地址但是指针指向的数据类型定义错误访问元素的时候也会出现错误。 按位查找的时间复杂度O(1)由于顺序表的各个数据元素在内存中连续存放因此可以根据起始地址和数据元素大小立即找到第i个元素这也体现了顺序表随机存取的特性。 顺序表的按值查找 #define InitSize 10 typedef struct{ElemType *data;int MaxSize;int length; } SeqList;ElemType LocateElem(SeqList L,ElemType e){for(int i0;iL.length;i)if(L.data[i]e)return i1; //数组下标为i的元素值等于e,返回其位序i1return 0; //退出循环说明查找失败}注意“”不能比较两个结构体类型 需要依次对比各个分量比较两个结构体是否相等  按值查找的时间复杂度 最好情况目标元素在表头 循环1次最好时间复杂度O(1) 最坏情况目标元素在表尾 循环n次最坏时间复杂度O(n) 平均情况假设目标元素出现在任何一个位置的概率相同都是1/n 目标元素在第1位循环1次在第2位循环2次…在第n位循环n次 平均时间复杂度为O(n) 顺序表的特点 ①随机访问即可以在 O(1)时间内找到第i个元素。 ②存储密度高每个节点只存储数据元素。 ③拓展容量不方便(即便采用动态分配的方式实现拓展长度的时间复杂度也比较高)。 ④插入、删除操作不方便需要移动大量元素。 2单链表 逻辑结构为线性表的数据物理上也能采用链式存储的方式。 顺序表 优点:可随机存取存储密度高 缺点:要求大片连续空间改变容量不方便 单链表 优点:不要求大片连续空间改变容量方便 缺点:不可随机存取要耗费一定空间存放指针 •单链表的实现 struct LNode{ //定义单链表结点类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 };//增加一个新的结点:在内存中申请一个结点所需空间并用指针p指向这个结点 struct LNode *p(struct LNode *)malloc(sizeof(struct LNode));每次写代码时都要写struct LNode比较麻烦可以使用typedef关键字对数据类型重命名 typedef struct LNode LNode 这样 struct LNode *p(struct LNode *)malloc(sizeof(struct LNode)); 可以写为 LNode *p(LNode *)malloc(sizeof(LNode)); 以下两个代码都表示定义了一个struct LNode的数据类型接着将struct LNode重命名为LNode并且用LinkList表示指向struct LNode的指针。 struct LNode{ElemType data;struct LNode *next;}; typedef struct LNode LNode; typedef struct LNode *LinkList;//更简洁地 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList; 要表示一个单链表时只需声明一个头指针L指向单链表的第一个结点 LNODE * L; //声明一个指向单链表第一个结点的指针 或者 LinkList L;typedef struct LNode{ //定义单链表节点类型ElemType data; //每个节点存放一个数据元素struct LNode *next; //指针指向下一个节点
}LNode,LinkList;//这里用LNode 和 LinkList 表示都可以只是前面用LNode*强调返回的是一个结点后面用LinkList强调返回的是一个单链表 LNode * GetElem(LinkList L,int i){int i;LNode *pL-next;if(i0)return L;if(i1)return NULL;while(p!NULL ji){pp-next;j;}return p; }不带头结点的单链表 typedef struct LNode{ElemType data;struct Lnode *next; }LNode,*LinkList;//初始化一个空的单链表 bool InitList(LinkList L){L NULL; //空表暂时还没有任何结点,设为NULL的目的是防止遗留的脏数据return true; }void test(){LinkList L; //声明一个单链表指针InitList(L); }//判断单链表是否为空 bool Empty(LinkList L){if(L NULL)return true;elsereturn false; } //或者直接写为 bool Empty(LinkList L){return(LNULL); } 带头结点的单链表 typedef struct LNode{ElemType data;struct Lnode *next; }LNode,*LinkList;//初始化一个空的单链表 bool InitList(LinkList L){L(LNode *)malloc(sizeof(LNode)); if(LNULL)return false;L-nextNULL; //头结点之后暂时还没有节点return true; }void test(){LinkList L; //声明一个单链表指针InitList(L); }//判断单链表是否为空 bool Empty(LinkList L){if(L-next NULL)return true;elsereturn false; } //或者直接写为 bool Empty(LinkList L){return(L-next NULL); } 注头结点是不存储数据的设置头结点只是为了后续处理更加方便。因为不带头结点的话对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理也需要用不同的代码逻辑。 单链表的插入 ▴按位序插入带头结点 带头结点插入时若想在i1时插入一个新的结点那么就可以将头结点看作“第0个”结点使用和后续结点一样的处理逻辑不带头结点则不行。 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;//在第i个位置插入元素e(带头结点) bool ListInsert(LinkList L,int i,ElemType e){if(i1)return false;LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点p L; //L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji-1){ //循环找到第 i-1 个结点 //因为要在第i个位置插入所以要找到第i-1个结点在i-1个结点后插入pp-next;j;}if(pNULL) //i值不合法return false;LNode s(LNode)malloc(sizeof(LNOde));s-datae;s-nextp-next;p-nexts; //将结点s连到p之后return true; //插入成功 } 如果i1即插在表头 因为i1不满足ji-1不会跳到while(p!NULL ji-1) LNode s(LNode)malloc(sizeof(LNOde));//申请一个结点空间 s-datae;//将参数e放到这一结点空间中 s-nextp-next;//s指向结点的next指针等于p结点next指针指向的位置 p-nexts;//p结点的next指针指向新结点 这种情况因为i1while循环直接被跳过所以时间复杂度为O(1)这也是最好时间复杂度。 如果i5那么就是在第四个结点后插入 s-nextp-next; //s的next指针指向p的next指针由于p结点的next指针指向的是NULL所以s的next指针也指向NULL p-nexts;//最后p的next指针指向新的结点 将新结点插到表尾即最坏时间复杂度为O(n) 平均时间复杂度也为O(n) 如果i6那么在while循环中j5时pNULL就会进入if循环跳出循环 if(pNULL)    //i值不合法         return false; 注 s-nextp-next;        ① p-nexts;          ② 两句不能颠倒如果先让p的next指针指向s即执行②再让s的next指针指向p的next指针就会出现如下情况 ▴按位序插入不带头结点 不带头结点的插入中不存在“第0个”结点所以i1时需要特殊处理 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;//在第i个位置插入元素e(不带头结点) bool ListInsert(LinkList L,int i,ElemType e){if(i1)return false;if(i1){//插入第一个结点的操作与其他结点操作不同LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextL;Ls; //头指针指向新结点return true; }LNode *p; int j1; //这里j1p L; while(p!NULL ji-1){ pp-next;j;}if(pNULL) //i值不合法return false;LNode s(LNode)malloc(sizeof(LNOde));s-datae;s-nextp-next;p-nexts; //将结点s连到p之后return true; //插入成功 } 如果i1  首先申请一个新的结点放入参数e         LNode *s(LNode *)malloc(sizeof(LNode));         s-datae; 接着将新节点的next指针指向L所指向的结点         s-nextL; 最后修改头指针L使L指向新的结点         Ls; 所以如果不带头结点则插入、删除第1个元素时需要更改头指针LLs如果带头结点的话头指针永远都是指向头结点的。 后续i1的情况与带头结点的处理是相同的只是需要注意int j1即p指针刚开始指向的是第一个结点 而带头结点刚开始指向的是第“0”个结点 ▴指定结点的后插操作 由于单链表只能往后寻找所以单链表p结点后的元素都是可知的利用循环的方式可以知道后续元素的值。而p结点前的值是不知道的。 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;//后插操作:在p结点之后插入元素e bool InsertNextNode(LNode *p,ElemType e){if (pNULL)return false;LNode *s (LNode *)malloc(sizeof(LNode));if(sNULL) //内存分配失败(如内存不足)return false;s-data e; //用结点s保存数据元素es-nextp-next;p-nexts; //将结点s连到p之后return true; } 时间复杂度为O(1) 实现后插操作后,可以直接写为 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;//后插操作:在p结点之后插入元素e bool InsertNextNode(LNode *p,ElemType e){if (pNULL)return false;LNode *s (LNode *)malloc(sizeof(LNode));if(sNULL) //内存分配失败(如内存不足)return false;s-data e; //用结点s保存数据元素es-nextp-next;p-nexts; //将结点s连到p之后return true; }//在第i个位置插入元素e(带头结点) bool ListInsert(LinkList L,int i,ElemType e){if(i1)return false;LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点p L; //L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji-1){ //循环找到第 i-1 个结点 //因为要在第i个位置插入所以要找到第i-1个结点在i-1个结点后插入pp-next;j;}return InsertNextNode(p,e); /*if(pNULL) //i值不合法return false;LNode s(LNode)malloc(sizeof(LNOde));s-datae;s-nextp-next;p-nexts; //将结点s连到p之后return true; //插入成功 */ } ▴指定结点的前插操作 之前说过单链表只知道p结点后的元素那么如何找到p的前驱结点呢 可以传入头指针 bool InsertPriorNode(LinkList L,LNode *p,ElemType e) 传入头指针后整个链表的信息就都能知道了。具体操作是遍历整个单链表找到结点p的前驱节点在前驱结点后插入元素e 时间复杂度为O(n) 如果没有传入头结点可以这样实现 //前插操作:在p结点之前插入元素 e bool InsertPriorNode(LNode *p,ElemType e){if (pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode));if(sNULL)//内存分配失败return false,s-nextp-next;p-nexts; //新结点 s连到 p 之后s-datap-data;p-datae; //将p中元素复制到s中return true; //p 中元素覆盖为 e首先申请一个新的结点并把这一结点作为p结点的后继节点 接着将p结点(p指针指向的结点)存放的元素x复制到新的结点中s-datap-data; 最后将要新插入的元素e覆盖原来p结点存放的元素x 这样即使没有传入头结点也可以完成前插操作。 并且这一实现方式的实现方式是O(1)而上一种实现方式是O(n)。 王道书中的写法是这样的但是思路是一致的。 //前插操作:在p结点之前插入结点 s bool InsertPriorNode(LNode *p,LNode *s){if(pNULL sNULL)return false;s-nextp-next;p-nexts; //s连到p之后ElemType tempp-data; //交换数据域部分p-datas-data;s-datatemp;return true; } 单链表的删除 注对于删除结点的操作只探讨带头结点的情况 ▴按位序删除带头结点 具体地将头结点看作第0个结点找到第 i-1 个结点将其指针指向第 i1 个结点并释放第i个结点。 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;bool ListDelete(LinkList L,int i,ElemType e){if(i1)return false;LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点p L; //L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji-1){ //循环找到第 i-1 个结点pp-next; j;}if(pNULL) //i值不合法return false;if(p-next NULL) //第i-1个结点之后已无其他结点return false;LNode *qp-next; //令q指向被删除结点e q-data; //用e返回元素的值p-nextq-next; //将*q结点从链中“断开”free(q); //释放结点的存储空间return true; //删除成功 }如果i4经过while循环后p会指向第3个结点i-1个结点 将q指针指向p结点的next元素即第i个结点LNode *qp-next 接下来会把q指针指向的结点中的元素复制给变量eeq-data 最后将p的next指针指向q的next指针并且释放q p-nextq-next; free(q); ▴按位序删除不带头结点 不带头结点的删除若删除第一个元素那么需要更改头指针和不带头结点的操作类似 typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;bool ListDelete(LinkList L,int i,ElemType e){if(i1)return false;if (i 1) {if (L NULL) // 判断链表是否为空return false;LNode *q L;e q-data;L L-next; // 将头指针指向第一个结点的下一个结点free(q); // 释放第一个结点的内存空间return true;}LNode *p; int j1;p L; while(p!NULL ji-1){ //循环找到第 i-1 个结点pp-next; j;}if(pNULL) //i值不合法return false;if(p-next NULL) //第i-1个结点之后已无其他结点return false;LNode *qp-next; //令q指向被删除结点e q-data; //用e返回元素的值p-nextq-next; //将*q结点从链中“断开”free(q); //释放结点的存储空间return true; //删除成功 }删除操作的最坏平均时间复杂度O(n) 最好时间复杂度O(1) ▴指定结点的删除 如果要删除结点p需要修改前驱结点的next指针 可以传入头指针循环寻找p的前驱也可以进行类似于前插的操作 //删除指定结点 p bool DeleteNode (LNode *p){if (pNULL)return false;LNode *qp-next; //令q指向*p的后继结点p-datap-next-data; //和后继结点交换数据域p-nextq-next; //将*q结点从链中“断开”free(q); //释放后继结点的存储空间return true; } 声明结点q指向p的后继结点LNode *qp-next;   把p结点后继结点的数据复制到p结点中p-datap-next-data; 将p结点的next指针指向q结点之后的位置p-nextq-next; 将q结点释放将内存归还给系统free(q); 时间复杂度O(1) 若删除的结点时最后一个结点那么代码执行到p-data p-next-data 就会出错因为找不到p结点的后继结点这样的话只能从表头开始依次寻找p的前驱时间复杂度:O(n)。 单链表的查找 ▴按位查找 //按位查找返回第 1个元素(带头结点) LNode * GetElem(LinkList L,int i){if(i0)return NULL;LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点p L; //L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji){ //循环找到第 1 个结点pp-next; j;}return p; } ①如果p的值0那么会跳过while循环 ②如果i的值大于链表的实际长度例如i8最后返回NULL 按位查找平均时间复杂度O(n) 王道书是这样写的实现效果是一样的 LNode * GetElem(LinkList L,int i){int j1;LNode *pL-next;if(i0) //当i的值为0时返回头节点return L;if(i1)return NULL;while(p!NULL ji){pp-next;j;} return p; } 只是p结点刚开始是指向第1个节点而不是第0个节点 有了查找的功能按位插入和按位删除中的查找操作就可以直接调用这个函数实现 //后插操作:在p结点之后插入元素e bool InsertNextNode(LNode *p,ElemType e){if (pNULL)return false;LNode *s (LNode *)malloc(sizeof(LNode));if(SNULL) //内存分配失败(如内存不足)return false;s-data e; //用结点s保存数据元素es-nextp-next;p-nexts; //将结点s连到p之后return true; }//在第i个位置插入元素e(带头结点) bool ListInsert(LinkList L,int i,ElemType e){if(i1)return false;LNode *pGetElem(L,i-1); //找到第i-1个结点return InsertNextNode(p,e); //p后插入新元素e }//删除第i个位置的元素e bool ListDelete(LinkList L,int i,ElemType e){if(i1)return false;LNode *pGetElem(L,i-1);if(pNULL) //i值不合法return false;if(p-next NULL) //第i-1个结点之后已无其他结点return false;LNode *qp-next; //令q指向被删除结点e q-data; //用e返回元素的值p-nextq-next; //将*q结点从链中“断开”free(q); //释放结点的存储空间return true; //删除成功 }▴按值查找 //按值查找找到数据域e 的结点 LNode *LocateElem(LinkList L,ElemType e){LNode *p L-next; //从第1个结点开始查找数据域为e的结点while(p ! NULL p-data ! e)p p-next;return p; //找到后返回该结点指针否则返回NULL如果返回NULL表示不存在要查找的值 } 按值查找的时间复杂度为O(n) 单链表的长度 //求表的长度 //带头结点 int Length(LinkList L){int len 0;//统计表长LNode p L; // 遍历链表统计节点个数while(p-next ! NULL){p p-next;len;}return len; }//不带头结点 int Length(LinkList L) {int len 0; // 统计链表长度LNode p L;if (p NULL) {return len;}while (p ! NULL) {len;p p-next;}return len; }求表的长度时间复杂度O(n)  单链表的两种建立方法 ▴尾插法建立单链表 就是每次取一个数据元素插入到表尾 typedef struct LNode{int data;struct LNode *next; }LNode,*LinkList;//初始化一个单链表(带头结点) bool InitList(LinkList L){L(LNode *)malloc(sizeof(LNode)); //分配一个头结点if(LNULL)//内存不足分配失败return false;L-next NULL;//头结点之后暂时还没有节点return true;// 尾部插入节点带头结点 LinkList TailInsert(LinkList L) {L (LinkList)malloc(sizeof(LNode)); // 建立头结点L-next NULL; // 头结点的next指针初始化为NULLint x;LNode *s, *r L; // r为表尾指针printf(请输入节点的值输入9999表示结束\n);scanf(%d, x); // 输入结点的值while (x ! 9999) { // 输入9999表示结束s (LNode *)malloc(sizeof(LNode));s-data x;r-next s; // 将新节点链接到链表尾部r s; // 更新表尾指针scanf(%d, x);}r-next NULL; // 将表尾节点的next指针设置为NULLreturn L; }// 尾部插入节点不带头结点 LinkList TailInsert(LinkList L) {L NULL; // 初始化链表为空int x;LNode *s, *r NULL; // r为表尾指针printf(请输入节点的值输入9999表示结束\n);scanf(%d, x); // 输入结点的值while (x ! 9999) { // 输入9999表示结束s (LNode *)malloc(sizeof(LNode));s-data x;s-next NULL;if (L NULL) {L s; // 第一个节点直接作为链表头} else {r-next s; // 将新节点链接到链表尾部}r s; // 更新表尾指针scanf(%d, x);}return L; } 这里假设输入的值为10也就是x10首先申请一个新的结点并用s指针指向这一新结点 接着让这一新结点的值为xs-datax; 并且让r指向的结点的next指针指向向sr-nexts; 最后让r指针指向srs;表示现在的表尾为s指向的结点即r指针永远指向链表最后一个结点 依次类推若最后用户输入9999那么r-nextNULL,最后返回这一链表 尾插法时间复杂度为O(n) ▴头插法建立单链表 头插法每插入一个元素就是对头结点的后插操作 typedef struct LNode{int data;struct LNode *next; }LNode,*LinkList;//初始化一个单链表(带头结点) bool InitList(LinkList L){L(LNode *)malloc(sizeof(LNode)); //分配一个头结点if(LNULL)//内存不足分配失败return false;L-next NULL;//头结点之后暂时还没有节点return true;//头插法带头结点 LinkList HeadInsert(LinkList L){ //逆向建立单链表LNode s;int x;L(LinkList)malloc(sizeof(LNode)); //创建头结点L-nextNULL; //初始为空链表scanf(%d,x);while(x!9999){ //和后插操作一样的逻辑只是每次都是对头结点进行后插操作s(LNode)malloc(sizeof(LNode));//创建新结点s-datax;s-nextL-next;L-nexts; //将新结点插入表中L为头指针scanf(%d,x);}return L; }//头插法不带头结点 LinkList HeadInsert(LinkList L) {L NULL; // 初始化链表为空LNode *s;int x;scanf(%d, x);while (x ! 9999) {s (LNode *)malloc(sizeof(LNode)); // 创建新结点s-data x;s-next L; // 将新结点插入链表头部L s; // 更新链表头指针为新结点scanf(%d, x);}return L; }注意对于L-nextNULL 在尾插法中不写这一句不会有影响因为元素是插在链表的尾部但是使用头插法就一定不能缺这句代码 若没有写这句话头结点的next指针可能指向未知的区域 接下来执行s-nextL-next; 最后头结点指向新的结点 其他新结点插入的情况类似最后的结点的next指针会指向未知的结点 所以无论再写尾插法还是头插法都建议初始化单链表将头指针指向NULL即 L-nextNULL; 使用头插法产生的结果是输入元素的逆序 如果需要单链表逆置就可以用头插法。 3双链表 单链表无法逆向检索所以找前驱结点会比较麻烦双链表可以双向检索就不会存在这个问题 双链表在单链表的基础上加入了一个指针prior,指向前驱结点  typedef struct DNode{ //定义双链表结点类型ElemType data; //数据域struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinklist;• 双链表的实现 双链表的初始化 typedef struct DNode{ //定义双链表结点类型ElemType data; //数据域struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinklist;//初始化双链表 bool InitDLinkList(DLinklist L){L(DNode *)malloc(sizeof(DNode)); //分配一个头结点if(LNULL) //内存不足分配失败return false;L-prior NULL; //头结点的 prior 永远指向 NULLL-next NULL; //头结点之后暂时还没有节点return true; }void testDLinkList(){ //初始化双链表DLinklist L;InitDLinkList(L); }//判断双链表是否为空(带头结点) bool Empty(DLinklist L){if(L-next NULL) return true;elsereturn false; } 双链表的插入 //在p结点之后插入s结点 bool InsertNextDNode(DNode *p,DNode *s){if(pNULL || SNULL) //非法参数return false;s-nextp-next;if(p-next ! NULL) //如果p结点有后继结点p-next-priors;s-priorp;p-nexts; return true; } ① 首先将s的next指针指向p的next指针指向的结点s-nextp-next; ② 如果p没有后继结点直接跳到接下来步骤③。如果有后继节点就将p结点的后继结点的前项指针指向sp-next-priors; ③ 接下来将s的前项指针指向p结点s-priorp; ④ 最后将p的后项指针指向s结点p-nexts; 修改指针时要注意顺序例如 如果按④ ①执行 首先p的next指针指向s结点 再让s的next指针指向p的next指针指向的结点 当我们进行按位插入时只需要从头结点开始找到某个位序的前驱结点然后对前驱结点进行后插操作接口。但我们想在某点前做前插操作由于双链表的特性我们可以很方便地找到某一点地前驱结点接着对前驱结点执行后插操作即可。 所以其他的插入操作都可以转换为用后插实现。 双链表的删除 //删除p结点的后继结点 bool DeleteNextDNode(DNode *p){if(pNULL)return false;DNode *q p-next; //找到p的后继结点qif(qNULL) //p没有后继return false;p-nextq-next;if (q-next!NULL) //q结点不是最后一个结点q-next-priorp;free(q); //释放结点空间return true; } 声明q指针指向p的后继结点。如果p没有后继即qNULL返回false否则 ① p结点的next指针会指向q结点的next指针指向的位置也就是指向q的后继结点 p-nextq-next; 如果q不是最后一个结点修改q的后继结点的前项指针执行②如果q是最后一个结点就会直接执行③ ② q节点的后继结点的前项指针指向p结点 q-next-priorp; ③ 释放q结点free(q) q是最后一个结点直接执行③的结果 双链表的销毁 void DestoryList(DLinklist L){ //循环释放各个数据结点while(L-next ! NULL)DeleteNextDNode(L); //删除头结点的后继结点free(L); //最后释放头结点LNULL; //头指针指向NULL } 双链表的遍历 //后向遍历 while (p!NULL){ //对结点p做相应处理如打印p p-next; }//前向遍历 while (p!NULL){ //对结点p做相应处理p p-prior; }//若只想处理数据结点不想处理头结点 while (p-prior!NULL){ //如果p结点的前项指针指的是NULL的话表明p指针此时指向的是头结点p p-prior; }双链表不可随机存取按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n) 4循环链表 • 循环单链表 之前学习的单链表最后一个结点的next指针指向的是NULL而循环单链表最后一个结点的next指针指向的是头结点。 所以初始化单链表时要将头结点的指针指向自己 typedef struct LNode{ElemType data;struct LNode *next; }LNode, *LinkList;//初始化一个循环单链表 bool InitList(LinkList L){L(LNode *)malloc(sizeof(LNode)); //分配一个头结点if (LNULL) //内存不足分配失败return false;L-next L; //头结点next指向头结点return true; }//判断循环单链表是否为空 bool Empty(LinkList L){if(L-next L)return true;elsereturn false; }//判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L,LNode *p){if (p-nextL)return true;elsereturn false; } 对于单链表而言从一个结点出发只能找到后续的各个结点。对于循环单链表而言从一个结点出发可以找到其他任何一个结点。 对于单链表而言从头结点找到尾部时间复杂度为O(n)对于循环单链表而言如果指针L不指向头结点而是指向尾部结点那么从尾结点出发找到头部结点只需要O(1)的时间复杂度。并且如果需要对链表尾部进行操作也可以在O(1)的时间复杂度找到操作的位置。  如果应用场景中需要经常对表头或表尾进行操作使用循环单链表时可以让L指向表尾元素。这样的话如果想在表尾进行插入删除时就需要修改L。 • 循环双链表 双链表表头结点的 prior指向 NULL表尾结点的next指向NULL。 循环双链表表头结点的prior指向表尾结点表尾结点的next指向头结点。 所以初始化双链表时需要让头结点的前项指针和后项指针都指向头结点自己也就是头结点既是第一个结点也是最后一个结点。 typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode, *DLinklist;//初始化空的循环双链表 bool InitDLinkList(DLinklist L){L(DNode *)malloc(sizeof(DNode)); //分配一个头结点if(LNULL) //内存不足分配失败return false;L-prior L; //头结点的 prior 指向头结点L-next L; //头结点的 next 指向头结点return true; }//判断循环双链表是否为空 bool Empty(DLinklist L){if(L-next L)return true;elsereturn false; }//判断结点p是否为循环双链表的表尾结点 bool isTail(DLinklist L,DNode *p){if(p-next L)return true;elsereturn false; }void testDLinkList(){//初始化循环双链表DLinklist L;InitDLinkList(L); } 双链表的插入 //在p结点之后插入s结点 bool InsertNextDNode(DNode *p,DNode *s){s-nextp-next; //将结点*s插入到结点*p之后p-next-priors;s-priorp;p-nexts; } 对于普通的双链表会出现错误 当p结点刚好是表尾结点时p-next-priors;这句代码会出现错误因为p结点没有后继结点了。 但如果使用的是循环双链表这个逻辑就是对的因为即便p结点是表尾结点他的next指针指向的结点是非空的将p的后继结点的前项指针指向s是没问题的。 双链表的删除 双链表的删除同理 ∥删除p的后继结点q p-nextq-next; q-next-piorp; free(q); 普通的双链表中执行q-next-priorp;会出现错误。而使用循环双链表则没有问题 5静态链表 •静态链表的相关概念 单链表中的各个结点是离散分布在内存中的各个角落每个结点会存放一个数据元素以及指向下一个结点的指针地址。 静态链表则分配一整片连续的内存空间各个结点集中安置。每个结点会存放一个数据元素以及下一个结点的数组下标游标。 在静态链表中0号结点充当“头结点”头结点中不存放数据元素而头结点的下一个结点被存放在了数据下标为2的位置。再往后的结点就是数组下标为1的结点以此类推。所以静态链表中的数组下标游标和单链表中的指针作用是相同的。 区别是指针指明的是下一个结点的地址而游标指明的是下一个结点的数据下标。 在单链表中表尾结点的指针是指向NULL的而在静态链表中表尾结点指向-1表示静态链表后没有其他结点了。 因为静态链表中各个结点是连续存放的如果每个数据元素4B每个游标4B(每个结点共8B)。设起始地址为 addr。那么数组下标为2的结点的存放地址就是addr8*2。 这样就能把静态链表中的数组下标映射为某个数组下标对应结点的实际存放位置。 •静态链表的定义 #define Maxsize 10 //静态链表的最大长度 struct Node{ //静态链表结构类型的定义ElemType data; //存储数据元素int next; //下一个元素的数组下标 };void testSLinkList(){struct Node a[Maxsize]; //数组a作为静态链表 } 王道书上是这样写的 #define Maxsize 10 typedef struct {ElemType data;int next; }SLinkList[Maxsize]; //等价于 #define Maxsize 10 struct Node{ElemType data;int next; }; typedef struct Node SLinkList[Maxsize]; //可用 sLinkList 定义“一个长度为 MaxSize 的Node 型数组”//当我们声明一个SLinkList a时,其实是声明了一个数组 //这个数组的元素个数为MaxSize每个数组元素就是一个Struct Node结构体 void testSLinkList(){SLinkList a; } //等价于 void testSLinkList(){struct Node a[MaxSize]; } //使用“SLinkList a”的写法强调的是a是静态链表 •静态链表的相关基本操作 1初始化静态链表将a[0]的next设为-1。在内存中没有存放数据的地方其实都存放着脏数据可以在初始化时让其它结点的next为某个特殊值用来表示结点空闲。例如-2若某个结点的游标是-2则表明这一结点时空闲的可以用这个结点存放新的数据元素。 2查找从头结点出发挨个往后遍历结点。所以查找某个位序的结点的平均时间复杂度为O(n) 3插入 ① 找到一个空的结点存入数据元素。 ② 从头结点出发找到位序为i-1的结点。 ③ 修改新结点的next。 ④ 修改i-1号结点的next。 4删除 ① 从头结点出发找到前驱结点。 ② 修改前驱结点的游标。 ③ 被删除结点 next 设为 -2。 总结 虽然静态链表的存储空间是一整片的连续的存储空间但是这片空间内逻辑上相邻的数据元素在物理上可以不相邻各个数据元素之间逻辑关系是由游标来指明的。 优点增、删操作不需要大量移动元素只要修改相关数据元素的游标即可。 缺点不能随机存取只能从头结点开始依次往后查找容量固定不可变只要声明了一个静态链表他所能存放的最大容量就被固定了。 适用场景:①不支持指针的低级语言②数据元素数量固定不变的场景(如操作系统的文件分配表FAT) 6顺序表和链表的对比 1.逻辑结构 顺序表和链表在逻辑上都是线性结构的都属于线性表。 2.物理结构存储结构 顺序表 顺序表采用了顺序存储的方式并且各个数据元素的大小相等由于这两个条件只需要知道顺序表的起始地址就可以找到第i个元素存放的位置。也就是顺序表具有随机存取的特性。 并且顺序表中的各个结点只需要存储各个元素本身不需要存储其他的冗余信息。因此顺序表存储密度高。 顺序存储的结构要求系统分配大片连续的存储空间所以分配空间时不方便。改变容量也不方便。 链表 若采用链式存储的方式实现线性结构由于各个结点可以离散地存放在内存空间中所以要添加一个元素时只需要用malloc函数动态申请一小片空间即可这样分配空间就比较方便。由于各个结点的存储空间不要求连续因此改变容量也较为方便。 但是链式存储中要查找第i个结点时只能从表头开始遍历寻找所以不可随机存取。并且由于各个结点除了存储数据元素外还需要花费一定空间存储指针所以存储密度较低。 3.数据运算/基本操作 •初始化 顺序表 1.由于顺序表初始化需要一整片的内存空间所以需要预分配大片连续空间若分配空间过小则之后不方便拓展容量;若分配空间过大则浪费内存资源。 2.若顺序表采用静态分配那么静态数组的容量是固定的。即便采用动态分配的方式更改动态数组的容量也需要移动大量的元素时间代价高。 链表 1.初始化链表时只需分配一个头结点(也可以不要头结点只声明一个头指针)之后方便拓展。 采用链表存储空间更加灵活。 •销毁 顺序表 1.首先将length0这步操作只是在逻辑上把顺序表置空。但是顺序表占用的存储空间还没有回收。 2.若采用静态分配就意味着顺序表占用的存储空间是通过声明静态数组的方式请求系统分配的。这种情况下系统会自动回收空间。 3.若采用动态分配的方式也就是使用malloc函数申请的一片内存空间那么就需要用free函数手动释放空间。因为malloc函数申请的空间属于内存的堆区堆区的内存空间系统不会自动回收。 L.data (ElemType *)malloc(sizeof(ElemType)*InitSize)free(L.data); 链表 通过free函数利用循环依次删除各个结点。 注malloc和free必须成对存在。 •增删 顺序表 1.由于顺序表中的各个元素在内存中是相邻并且有序的所以在插入/删除元素要将后续元素都后移/前移。 2.顺序表的插入时间复杂度和删除时间复杂度都是O(n)时间开销主要来自移动元素。若数据元素很大则移动的时间代价很高。 链表 1.插入/删除元素只需修改指针即可。 2.链表的时间复杂度也为 O(n)时间开销主要来自查找目标元素。查找元素的时间代价相比于移动大量元素的时间代价更低。 所以虽然顺序表和链表的插入删除操作时间复杂度都为O(n)但是实际上链表的效率比顺序表高得多。 •查找 顺序表 1.顺序表具有随机存取的特性采用按位查找的时间复杂度为O(1)。 2.采用按值查找时间复杂度为O(n)若表内元素有序采用安值查找那么可在O(log2n)时间内找到采用折半查找等方式。 链表 1.链表只能从第一个数据元素开始依次遍历查找按位查找时间复杂度为O(n)。 2.按值查找也只能从第一个数据元素依次往后遍历时间复杂度为O(n)。 所以查找操作中顺序表效率高很多。 •总结 1.如果线性表表长难以估计并且经常需要增加/删除元素那么就使用链表。 2.如果线性表表长可预估查询(搜索)操作比较多。那么就采用顺序表。