申嵌视频-linux c语言程序开发班1嵌入式收费版编程入门初级基础提高自学学习视频教程高级篇第四章链表

1、上章顾常见的数据结构的形式算法的时间复杂度是如何计算的算法的空间复杂度是什么em/回第章链表em/四预习检查线性链表循环链表双向链表em/课程目标本章概述本章主要介绍运用结构体构造链表，以及链表的相应的操作本章目标熟练构造和掌握链表及相关添加，查找，删除操作。重点掌握链表的构造以及相关操作。难点链表的em/本章结构em/双向循环链表数据结构与算法初步单向链表操作4.1链表单链表单链表上基本运算的实现循环链表双向链表静态链表单链表的应用实例em/4.1.1 单链表单链表的概述动态进行分配的一种结构在内存中不连续存放头节点：指向第一个元素节点：链表中的每一个元素（结构体）两部分：实际数据和下一个节

2、点地址尾指针定义typedef struct nodedaype data;struct node *next; LNode，*LinkList；/* 指向本结点类型的指针是实现链表的基础*/em/4.1.1 单链表单链表的概述动态进行分配的一种结构在内存中不连续存放头节点：指向第一个元素节点：链表中的每一个元素（结构体）两部分：实际数据和下一个节点地址尾指针定义typedef struct nodedaype data;struct node *next; LNode，*LinkList；/* 指向本结点类型的指针是实现链表的基础*/em/4.1.1 单链表头指针来标识一个单链表，如单链表L

3、、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中，头指针为“NULL”则表示一个空表内存分配函数：void * malloc(unsignedsize)void * calloc(unsigned n,unsigned size)分配成功返回指向起始地址的指针分配不成功返回NULL内存函数void free(void *p)申请链表空间p=malloc(sizeof(LNode)；em/4.1.1 单链表带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头设置表头结点的目的:简化链表操作的实现非空表空表em/a1an4.1.2.单链表上基本运算的实现建立单链表

4、求表长查找操作删除em/4.1.2.1建立单链表在链表的头部结点建立单链表newnode-next = newnode;newnodenewnode（后）/em4.1.2.1建立单链表在链表的头部算法如下：结点建立单链表LinkList Creat_LinkList1( )LinkList L=NULL；/*空表*/ Lnode *s;x;/*设数据元素的类型为*/scanf(%d,&x); while (x!=flag)s=malloc(sizeof(LNode); s-data=x;s-next=L; L=s; scanf (%d,&x);return L;em/4.1.2.1建立单链表在

5、单链表的尾部结点建立单链表newnode-next = p-next;p-next = newnode；newnodenewnodepp(前)(后)em/4.1.2.1建立单链表在链表的尾部结点建立单链表算法如下：LinkList Creat_LinkList2( )LinkList L=NULL;Lnode*s,*r=NULL;/ r为哨兵指针x;/*设数据元素的类型为*/scanf(%d,&x); while (x != flag)s=malloc(sizeof(LNode); s-data=x;if (L=NULL) L=s; /*第一个结点的处理*/else r-next=s;/*其它

6、结点的处理*/r=s;/*r 指向新的尾结点*/scanf(%d,&x);if ( r!=NULL) r-next=NULL; /*对于非空表，最后结点的指针域放空指针*/嵌入return L;4.1.2.1建立单链表在链表中间newnode-next = p-next; p-next = newnode ；newnodepnewnodep(前)(后)em/4.1.2.2 求表长节点的链表算法思路：设一个移动指针和计数器，初始化后，所指结点后面若还有结点，向后移动，计数器加1。算法如下：Length_LinkList1 (LinkList L)Lnode * p=L; j=0;while (p

7、-next)/* p指向头结点*/p=p-next; j+/* p所指的是第 j 个结点*/return j;.u.em/4.1.2.2 求表长不节点的链表算法思路：设一个移动指针和计数器，初始化后，所指结点后还有结点，向后移动，计数器加1。算法如下：Length_LinkList2 (LinkList L)Lnode * p=L; j;if (p=NULL) return 0; /*空表的情况*/j = 1;/*在非空表的情况下，p所指的是第一个结点*/;while (p-next )p=p-next; j+return j;4.1.2.2 查找操作按序号查找算法思路：从链表的第一个元素结点

8、起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第个结点时返回空 。算法如下：Lnode * Get_LinkList(LinkList L,i);/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/Lnode * p=L; j=0;while (p-next !=NULL & jnext; j+;if (j=i)return p;elsereturn NULL;4.1.2.2 查找操作按值查找即定位算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空 。算法如下

9、：Lnode * Locate_LinkList( LinkList L, daype x)/*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/Lnode * p=L-next;while ( p!=NULL & p-data != x) p=p-next;return p;em/4.1.2.3后插结点q-next = p-next;p-next = q;前后qqqqem/4.1.2.3运算算法如下：Insert_LinkList( LinkList L,/*在单链表L的第i个位置上i, daype x)值为x的元素*/Lnode * p,*s; p=Get_LinkList(L

10、,i-1); if (p=NULL)/*查找第i-1个结点*/prf(参数i错);return 0; /*第i-1个不存在不能 else */s=malloc(sizeof(LNode); /*申请、填装结点*/ s-data=x;s-next=p-next; p-next=sreturn 1;/*新结点在第i-1个结点的后面*/上4.1.2.4 删除在单链表中删除ai结点q = p-next;p-next = q-next;删除前p ai删除后pqem/ai+1ai-1Ai+1aiAi-14.1.2.4 删除在单链表中删除ai结点:算法如下Del_LinkList(LinkList L， i

11、)LinkList p,s;/*删除单链表L上的第i个数据结点*/p=Get_LinkList(L,i-1); if (p=NULL) /*查找第i-1个结点*/prf(第i-1个结点不存在);return -1; else if (p-next=NULL) prf(第i个结点不存在);return 0; else s=p-next; /*s指向第i个结点*/p-next=s-next;/*从链表中删除*/*s */free(s);/*return 1;嵌4.1.3 循环链表特点:可以从表中任意结点开始遍历整个链表不用头指针而用一个指向尾结点的指针R来标识节点的单循环链表HH(a)非空表(b)

12、空表图2.16结点的单循环链表em/ana14.1.3 循环链表单循环链表H1 、H2的连接操作链表若用尾指针R1 、R2来标识将H2的第一个数据结点接到H1的尾结点操作语法p= R1 next;/*保存R1 的头结点指针*/R1-next=R2-next-next;/*头尾连接*/free(R2-next);R2-next=p;/*第二个表的头结点*/*组成循环链表*/R2pR1bna1an 接em/b14.1.4 双向链表特点一个指向前驱的指针域一个指向后驱的指针域一个数据域双向链表定义表达:typedef structdlnodedaype data;struct dlnode *pri

13、or,*next;DLNode,*DLinkList;em/priordatanext4.1.4 双向链表链表表现模式Ha2a1an(a)非空表H(b)空表图2.19结点的双循环链表em/4.1.5 单链表应用举例例一已知单链表H，写一算法将其倒置。即实现如图2.22的操作。(a)为倒置前，(b)为倒置后。(a)H(b)H单链表的倒置em/297618452525451876294.1.6 单链表应用举例例一算法表达:void reverse (Linklist H)LNode *p;p=H-next; /*p指向第一个数据结点*/ H-next=NULL; /*将原链表置为空表H*/ whi

14、le (p)q=p;p=p-next;q-next=H-next; H-next=q;/*将当前结点插到头结点的后面*/em/4.1.6 单链表应用举例例二已知单链表L，写一算法，删除其重复结点，即实现如图2.23的操作。(a)为删除前，(b)为删除后(a)H(b)H删除重复结点em/18151010151815104.1.6 单链表应用举例例二算法实现void pur_LinkList(LinkList H) LNode *p,*q,*r;p=H-next; /*p指向第一个结点*/ if(p=NULL) return;while (p-next)q=p;while (q-next)/* 从*p的后继开始找重复结点*/if (q-next-data=p-data)r=q-next; /*找到重复结点，用r指向，删除*r */q-next=r-next; free(r); /*if*/ else-next; /*while(q-next)*/p=p-next;/*p指向下一个，继续*/ /*while(p-next)*/阶段小节 单链表的特点 单链表的创建，、查找和删除 循环链表与双向链表特点 实现链表的逆转e