第3章 链接表

.,主要内容,普通高等教育“十一五”国家级规划教材,第3章链接表,3.1链表3.2链栈3.3链队列,返回目录,3.4字符串的链式存储3.5链表应用举例,.,3.1链表,3.1.1单链表3.1.2循环链表作业,.,线性表的顺序存储的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点。为避免大量结点的移动，本节将介绍线性表的另一种存储方法链式存储结构，并将这种用链式方式存储的线性表简称为链表（LinkedList）。,概述,.,从实现角度：动态链表、静态链表从链接方式角度：单链表、循环链表、双链表,链表的分类,链接存储是最常用的存储方法之一，它不仅可以用来表示线性表，而且可以用来表示各种非线的数据结构。,链表是用一组不连续的存储单元来存放线性表中的数据，因此链表中结点的逻辑次序和物理次序不一定相同。因此，在存储每个数据元素值的同时，还要存储指示其后继结点的地址信息，这两部分信息组成的存储映象称为结点。,.,单链表：单链表又称为线性链表，是线性表的一种最简单的链式存储结构。在单链表中的每一个结点都包含两部分内容：存放每一个数据元素本身的数据信息的数据域和存放其直接后继存储位置的指针域（地址域）。单链表中结点的结构如下：,数据域,指针域,.,例线性表（zhao,qian,sun,li,zhou,wu,zheng,wang）,43,13,1,NULL,37,7,19,25,头指针,.,头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空,表示线性表为空,.,3.1.1单链表,typedefstructnodedatatypedata;structnode*next;linklist;,1.单链表的定义和存储结构,定义：一个链表由n个结点组成,每个结点中有一个存储数据的值域和一个存储另一个结点地址的指针域。由于链表的每个结点只有一个链域，故将这种链表称为单链表。,.,通常用头指针head来标识一个单链表的开始头结点:表的第一个结点的data域不存数据空表:head-next=NULL（也可用表示空NULL）存储空间动态分配:p=malloc(sizeof(linklist)释放p所指的结点:free(p),单链表的链式存储结构示意图,.,2.单链表的基本操作(1)建立单链表方法一：头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,.,a,b,c,d,.,在线性表la中存放数据（5,4,8,6）,时间复杂度为O(n),.,具体算法如下：linklist*creatlistbefore()datatyped;linklist*p,*s,*head;head=malloc(sizeof(linklist);head-next=NULL;p=head;printf(pleaseinputthecharacter!(enter-return);rewind(stdin);scanf(%c,.,2.单链表的基本操作(1)建立单链表方法二：从表尾到表头逆向建立。头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。,.,a,b,c,.,linklist*creatlistafter()datatyped;linklist*p,*s,*head;head=malloc(sizeof(linklist);head-next=NULL;p=head;printf(pleaseinputthecharacter!(enter-return);rewind(stdin);scanf(%c,.,（2）插入运算后插操作,x,s-next=p-next,p-next=s,S=malloc(sizeof(linklist),.,前插操作,x,s-next=p,q-next=s,S=malloc(sizeof(linklist),.,在单链表L的第i个元素之前插入一个元素x。实现思想：（1）找到第i-1个元素（2）在i-1个元素之后插入x,.,head,时间复杂度为O(n),voidinsert(linklist*head,inti,datatypex)linklist*p,*s;intj=1;p=head;while(p,单链表中插入元素示意图,p,.,单链表中插入元素示意图,s-data=x;s-next=p-next;p-next=s;,.,(3)按值查找,算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的地址，否则继续向后查找，直到链表结束为止。找不到时返回空。,时间复杂度为O(n)。,linklist*search(head,x)linklist*head;datatypex;linklist*p;p=head-next;while(p!=NULL,.,查找运算,.,(4)删除运算,p-next=p-next-next;,.,删除运算方法一:在指定位置进行删除。,voiddelete1(linklist*head,inti)intj=1;linklist*q,*p;p=head;while(jnext;j+;if(p=NULL)printf(位置参数不正确!n);elseq=p-next;/*q指向要删除的结点*/p-next=q-next;/*将p之后的结点删除*/free(q);,删除单链表的第i个元素实现思想:找到第i-1个元素删除第i个元素,.,算法演示,时间复杂性为O(n)。,.,p,q,ai-1,ai,ai+1,p-next=q-next;Free(q);,.,删除运算方法二:根据所给条件找到位置再进行删除。,voiddelete(head,x)linklist*head;datatypex;linklist*p,*s;p=head;while(p-next!=NULL,.,3.1.2循环链表,1.循环单链表：对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头结点地址存于该指针域，则使得链表头尾结点相连，就构成了循环单链表。,空表,非空表,.,2.循环双向链表,结点,空表,非空表,循环双向链表：将最后一个结点的空指针域（next域）用来保存头结点地址，而用头结点的prior域保存最后一个结点的地址，用这种结点组成的链表称为循环双向链表。,.,3.静态链表,对于某些高级语言若没有指针类型，就不能动态生成结点，此时也可以借助一维数组来描述线性链表。,#defineMAX链表的最大长度typedefstructdatatypedata;intnext;snode;/*结点类型*/snodeslMAX;,该数组的定义如下：,.,静态链表,数组sl就表示一种链表，该链表的结点中也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组的下标)，称之为静态指针，这种链表就称之为静态链表，空指针用0表示，而sl.next0中存放的是第一个结点的起始地址。,静态链表如图所示,.,作业,1.简述链表的定义和链表的分类。2.做教材习题中的以下题目。单项选择题：(1),(2),(3),(8),(9),(10)填空题：(1),(2),(3),(5),(6),(7),(9),(10)应用题：(1)3.试写一算法求带头结点的单链表L的长度。4.已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值为x的结点插人表中，使L仍然有序。5.试写一算法对带头结点的单链表实现就地逆置。,.,3.2链栈,1.链栈的定义链栈：用链式存储结构实现的栈。(只允许在表头进行插入和删除运算的单链表)栈顶指针:单链表的头指针。,链栈的类型定义如下：typedefstructnodedatatypedata;structnode*next;*linkstack;linkstackhs;/*hs为链栈栈顶指针*/,.,2.链栈的运算进栈,进栈的算法:voidpush(linkstackhs,datatypex)linkstacks;s=malloc(sizeof(linkstack);s-data=x;s-next=hs;hs=s;,hs,s,x,an+1,hs,.,出栈,voidpop(linkstackhs,datatype*x)linkstackp;if(hs=NULL)printf(栈空);else*x=hs-data;p=hs;hs=hs-next;free(p);,an,.,hs,d,an+1,*X=d,p,hs,.,作业,1.简述链栈的定义。2.做教材习题中的以下题目。单项选择题：(4),(6)填空题：(4)应用题：(2),.,3.3链队列,1.链队列的定义链队列：链式存储的队列(只允许在表尾进行插入和在表头进行删除运算的单链表)。头指针：front尾指针：rear,.,typedefstructnodedatatypedata;structnode*next;linkqueue;typedefstructlinkqueue*front,*rear;lqueue;lqueue*hq;/*hq链队列指针变量*/,链队列的类型定义如下：,.,2.链队列的运算,voidinsertq(lqueue*hq,datatypex)linkqueue*p;p=malloc(sizeof(linkqueue);p-data=x;p-next=NULL;if(hq-rear=NULL)hq-front=p;hq-rear=p;elsehq-rear-next=p;hq-rear=p;,an,front,rear,p,hp,进队,.,出队,voiddeleteq(lqueue*hq,datatype*x)linkqueue*p;if(hq-front=NULL)printf(队空);elsep=hq-front;hq-front=p-next;*x=p-data;free(p);if(hq-front=NULL)hq-rear=hq-front;,an,front,rear,hp,*X=a1,.,作业,1.简述链队列的定义。2.做教材习题中的以下题目。单项选择题：(5),(7)填空题：(8)应用题：(3),.,3.4字符串的链式存储,typedefstructnodecharch;structnode*next;linkstring;,由于串结构的特殊性结构中的每个数据元素是一个字符，所以在用链表存储字符串时，存在一个结点大小的问题，每个结点可以存放一个字符，也可以存放多个字符。,.,块链结构:下图是结点大小为4的链表。由于字符串的长度不一定是结点大小的整倍数，则链表的最后一个结点不一定会占满，此时补上#或其他非串字符值（通常#不属于串的字符集，是一个特殊的符号）。,尾指针tail：指示最后一个结点len：存储串的实际长度,.,#defineMAX结点块的最大值typedefstructnodecharchMAX;structnode*next;cnode;typedefstructintlen;cnode*head,*tail;lstring;,块链结构的结点描述如下：,.,结点存储密度=,结点存储密度,结点大小选择的是否合理，直接影响存储空间的利用率。,串所占存储空间,结点实际分配的存储空间,.,作业,1.1个字符串用链式结构存储有几种方式？2.做教材习题中的以下题目。应用题：(5),.,3.5链表应用举例,例3-1试写一算法，求带结点的单链表的长度,单链表的长度是指单链表中结点的个数。求单链表表长的基本操作是移动指针，将指针从表头移动到表尾。在指针移动过程中，累计扫描过的结点数即为表长。由此需要设一个指针p，顺链向后移动；还要设一个整型变量j，作为计数器。指针p的初始值指向头结点，计数器j的初始值为0。,.,intLength_linkList(linklist*l)linklist*p；intj=0;p=l;/*p指向头结点*/while(p-next)p=p-next;j+/*p所指的是第j个结点*/returnj;,.,3.5链表应用举例,例3-2有一单链表l，其头结点指针head，编写一算法将其倒置。即实现如下图的操作。(a)为倒置前，(b)为倒置后。,(a),(b),.,算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。,voidreverse(linklist*head)linklist*p,*q;p=head-next;head-next=NULL;while(p)q=p;p=p-next;q-next=head-next;head-next=q;,.,例3-3已知单链表h，写一算法，删除其中所有重复的结点。算法思路：用指针p指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之；p指向下一个；依此类推，p指向最后结点时算法结束。参考算法如下：,.,voiddel(linklist*h)linklist*p,*q,*r;p=h-next;while(p)q=p;while(q-next)if(q-next-data=p-data)r=q-next;q-next=r-next;free(r);elseq=q-next;p=p-next;,.,例3-4创建一个以正序排列的链表，链表节点为一个整形数据，插入一个元素，删除一个元素，均保持链表的正序。在执行完每个操作后将其输出。,/*创建链表函数*/linklist*creatlist()datatyped;linklist*p,*s,*head;head=malloc(sizeof(linklist);head-next=NULL;printf(pleaseinputtheinteger!(0-return);scanf(%d,while(p-next!=NULL)if(p-next-datanext;elsebreak;s-next=p-next;p-next=s;scanf(%d,.,插入一个元素，标志链表的正序性。,voidinsert(head,x)linklist*head;datatypex;linklist*p,*s;s=malloc(sizeof(linklist);s-data=x;p=head;while(p-next!=NULL)if(p-next-datanext;elsebreak;s-next=p-next;p-next=s;printf(%