《数据结构与算法》课件 第3章 链表

第三章链表3.1线性表的链式存储一、线性链表的概念二、线性链表及其结点的结构定义三、线性链表的运算3.2链式栈与链式队列一、链式栈二、链式队列3.3循环链表一、循环链表的结构二、循环链表的基本运算第三章链表3.4多重链表一、多重链表的结构二、双向链表三、稀疏矩阵的十字链表表示3.5广义表一、广义表的概念二、广义表的存储表示三、广义表的运算§3.1线性表的链式存储结构--链表一、链表结构每一个元素称作是结点，由两部分组成：存放元素值的部分和存放后继地址的部分。结点结构示意图如下：元素值data下一元素的地址next特点：逻辑上相邻的元素在物理位置不一定相邻，其相互之间的关系是靠其中的后继地址来表示的结构描述如下：typedefstructSNode{ElemTypedata;structSNode*next;//指向结构体类型指针}*LinkList;动态链表：根据实际需要临时分配头指针：在一个链表中，指向表头结点的指针，用Linklisthead表示(1)head=NULL//线性链表为空(2)若head非空时，则可用(*head).data表示结点的数据域,或使用headdata表示。那么结点的指针域呢？课本中默认为带头结点的线性链表注意：(1)带头结点的单链表head为空的条件headnext=NULL//即第一个结点为空(2)线性链表通过指针反映元素之间相邻的逻辑关系，取得第i个数据元素必须从头指针出发寻找，所以它是非随机存取的存储结构1、初始化：LinkListLinkedListInit(){SNode*L;L=(SNode*)malloc(sizeof(SNode));L-next=NULL;returnL;}二、链表运算的实现2、求长度intlist_length(LinkListL){intn=0;LinkListp=L-next;while(p!=NULL){n++;p=p-next;}returnn;}211830754256∧pppk0123p4p5p6pL3、查找元素的实现按值：已知数值大小思考：按序号查找应怎样描述算法？LinkListLinkListLocate(LinkListL,ElemTypex){SNode*p;p=L-next;while(p!=NULL&&p-data!=x)p=p-next;returnp;}aiai-1prexS①②s=(SNode*)malloc(sizeof(SNode));sdata=x;snext=prenext;prenext=s;}4、插入算法实现voidLinkedListInsert(LinkListL,LinkListp,ElemTypex){pre=L;while(pre!=NULL&&pre-next!=p)pre=pre-next;if(!pre){printf(“不存在*p节点”)；exit(0);}aiai-1Pai+1……..……..q用P指向第i-1个数据元素方法一：q=pnext;pnext=qnext;方法二：pnext=pnextnext;注意：无论是哪种方法，最后都要释放ai的存储空间5、删除算法的实现voidLinkListDelete(LinkListL,inti)voidLinkListDel(LinkListL,inti){p=L;j=1;while(p-next&&ji){p=p-next;j++;}if(p-next==NULL){printf(“删除位置不正确”);exit(0);}q=p-next;p-next=q-next;free(q);}头插法：在建立链表的过程中，将每个读入的数据装入结点后插入到链表的表头LinkListLinkedListCreat(){LinkListL;L=(Linklist)malloc(sizeof(SNode));L-next=NULL;read(x);while(x!=flag){p=(SNode*)malloc(sizeof(SNode));p-data=x;p-next=L-next;L-next=p;read(x);}}6、建立单链表LinkListLinkedListCreat(){LinkListL;L=(Linklist)malloc(sizeof(SNode));L-next=NULL;r=L;read(x);while(x!=flag){p=(SNode*)malloc(sizeof(SNode));p-data=x;r-next=p;r=p;read(x);}r-next=NULL;returnL;}思考：采用尾插法建立应怎样实现？？？intjudge(SNode*L){SNode*p=L-next;if(p==NULL)exit(0);while(p-next!=NULL)if(p-datap-next-data)p=p-next;elsereturn0;return1;}三、链表结构的应用例1：设计算法，判断链表L1中的元素是否递增，是返回1，否则返回0。例2：在递增有序的单链表L中插入元素x,使其仍保持有序分析：此问题的求解实际上为插入算法的实现，不同之处在于需要确定位置。算法实现：1）判断当前链表是否适合插入一个元素2）确定插入位置3）将元素x插入到指定的位置voidinsert(LinkListL,ElemTypex){LinkListu,P=L;P=P-next;while(P-next!=NULL&&P-next-datax)P=P-next;if(P-next==NULL||P-next-datax){u=(SNode*)malloc(sizeof(SNode));u-data=x;P-next=u-next;P-next=u;}}讨论1：链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可(P-next=head;)。这种形成环路的链表称为单循环链表。特点：1、从任一结点出发均可找到表中其他结点。2、操作仅有一点与单链表不同：循环条件单链表-----p!=NULL或p-next!=NULL循环链表-----p!=head或p-next!=head附加：其他形式的链表结构a2a1an…head讨论2：单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可(例如用*next和*prior;)。这种有两个指针的链表称为双向链表。其特点是可以双向查找表中结点。•对双向循环链表中任一结点的指针，有：p==p→prior→next==p→next→prior•置空表：p→prior=p;p→next=p;(A)非空双向循环链表(B)空表双向循环链表存储结构的描述structNode{ElemTypedata;structNode*prior,*next;};priordatanext思考：在双循环链表中应如何进行插入和删除操作？1.在单链表中，已知p指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行()A.link(s)←link(p)，link(p)←sB.link(q)←s，link(s)←pC.link(p)←link(s)，link(s)←pD.link(p)←s，link(s)←p2.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为:rlink(p)←q,llink(p)←llink(q),llink(q)←p,_________。（空白处为一条赋值语句）()A.rlink(q)←pB.rlink(llink(q)←pC.rlink(llink(p))←pD.rlink(rlink(p)←p练习1、链表中逻辑上相邻的元素在物理上（）相邻。2、已知带头结点的单链表L，指针p指向链表中的一个节点，指针q指向链表外的节点，在指针p的后面插入q的语句序列（）3、设某非空单链表，要删除指针p所指的结点的直接后继结点，则需要执行下述语句序列：p=q-next；（）；free（p）；4、线性表的存储有顺序存储和（）存储两种。5、线性表中哪些元素只有一个直接前驱和一个直接后继？A首元素b尾元素c中间的元素d所有的元素6、线性表的各元素之间是（）关系A层次b网状c有序d集合7、在单链表中一个结点有（）个指针，在双向链表中的一个结点有（）指针73#5某百货公司仓库中，有一批电视机，按其价格由高到低的顺序存储在计算机中，经常发生的操作是入库和出库。现在又新到m台价格为h元的电视机需入库，请你为仓库管理系统设计一种数据结构，并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：数据元素是（数量，价格），数据元素之间的价格不同。因为经常进行入库、出库操作，即插入、删除，故使用线性链表。结点数据结构示意图为：价格Pi数量Ni指针域link数据域data价格由高到底的顺序存储：P1…Pi-1Pi…PkP1N1Pi-1Ni-1PiNiPkNk^若：Pi-1hPihm多项式链表的相加AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x183.2链栈——栈的链式存储结构不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。类型定义：typedefstructSNode{ElemTypedata;structSNode*next;}*LinkStack;LinkStacks;•栈空条件：s=NULL•栈满条件：无/无FreeMemory可申请s进栈操作：voidPush_L(LinkStacks，ElemTypee){p=(LinkStack)malloc(sizeof(SNode));}p-data=e;p-next=s;s=p;退栈操作voidPop_L(LinkStacks,SElemType&e){if(s)free(p);}{e=s-data;p=s;s=s-next;}3.2.2链队列——队列的链式存储结构两个指针：队头指针front指向头结点队尾指针rear指向尾结点•初始态：队空条件头指针和尾指针均为NULLfront==rear=NULLstructSNode{//元素结点ElemTypedata;SNode*next;};struct{SNode*front;//队头指针SNode*rear;//队尾指针}LinkQueue;LinkQueueQ;Q.front——指向队头结点Q.rear——指向队尾结点队列运算指针变化状况空队列voidEnQueue(LinkQueueQ,ElemTypee){p=(SNode)malloc(sizeof(SNode));p-data=e;}链队列的插入（入队在队尾进行）p-next=NULL;Q.rear-next=p;Q.rear=p;VoidDeQueue(LinkQueueQ,ElemType&e){if(Q.front!=Q.rear){p=Q.front;e=p-data;Q.front-next=p-next;free(p);}}链队列的删除（出队在队头操作）if(Q.rear==p)Q.rear=NULL;3.5广义表•广义表的基本概念•广义表的链接存储结构•广义表的2种基本运算•广义表的应用举例一、基本概念广义表是线性表的推广。线性表中的元素仅限于原子项(单个数据元素)，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表(另一个线性表)。(如果ai是单个数据元素,则称ai为广义表的原子)1．广义表的定义广义表是n≥0个元素a0，a1，…，an-1的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为GL=(a0,a1,…,an-1)，其中GL为广义表的名字