实用数据结构电子教案链表省公共课一等奖全国赛课获奖课件.pptx

数据结构第三章 链表第1页第三章 链表 知 识 点单链表结点形式、组织方法和特点 单链表基本运算和对应算法 循环链表组织方法和基本运算算法 双链表结点形式、组织方法和特点 双链表基本运算和对应算法 次序表与链表比较，各自优、缺点 链表应用 用十字链表表示稀疏矩阵第三章 链表第2页难 点 双链表插入、删除运算算法利用链接结构特点设计有效算法，处理与链表结构相关应用问题 要 求 熟练掌握以下内容:单链表结构特点、基本运算并能设计简单算法循环链表结构特点、基本运算并能设计简单算法双链表结构特点、基本运算并能设计简单算法 了解以下内容：用十字链表表示稀疏矩阵 链接堆栈，链接队列应用以及一元多项式加法应用实例 第三章 链表第3页第三章目录3.1 单链表及其运算3.2 循环链表与双向链表 3.3 链表应用举例3.4 表示稀疏矩阵十字链表3.5 应用举例及分析小 结习题与练习第三章 链表第4页3.1.1 单链表1.结点:在链式存放结构中，结点不但存放数据元素值，还附加一个指针（链），用来指向该结点直接后继结点。其中，data部分称为数据域，用于存放线性表一个元素，next部分称为指针域或链域，用于存放一个指针，即存放该结点直接后继结点地址。第三章 链表第5页2.单链表全部结点经过指针链接而组成线性表称为单链表。线性表（a1，a2，an，）单链表可直观地画成：head是单链表头指针，指向开始结点a1,an是终端结点，其指针域为空，不指向任何结点。一个单链表由头指针head唯一标识和确定，所以，可用头指针来命名单链表。第三章 链表第6页3.单链表类型定义 假设线性表中数据元素类型为datatype，单链表类型定义以下：typedef struct node*pointer;struct node datatype data;pointer next;typedef pointer linklist;一个结点是由两个域data和next组成统计,data是结点数据域，next是结点链域。第三章 链表第7页4.指针概念 假设p是一个pointer类型，应正确区分指针型变量、指针、指针所指结点和结点内容这四个亲密相关不一样概念：p值（假如有话）是一个指针，即是一个所指结点地址。该指针（若不是NULL）指向某个node型结点用*p来标识。结点*p是由两个域组成统计，这两个域分别用pdata域和pnext域来标识，它们各有自己值，pdata值是一个数据元素，pnext值是一个指针。第三章 链表第8页3.1.2 单链表基本运算 1.遍历(Traversal)：依据已给表头指针，按由前向后次序访问单链表各个结点。在实际应用中遍历是对单链表最基本运算，比如，当要打印或显示出各个结点数值域值、计算单链表长度(即结点数目)或寻找某一个结点时都需要遍历单链表。假设head是单链表头指针，计算一个已建立好单链表结点个数算法以下：第三章 链表第9页计算结点个数算法int length(node*head)/*求表head长度*/int count=0;/*计数器置初值*/node*p=head;/*p指向头结点*/while(p!=NULL)p=p-next;count+;return(count);/*返回表长值*/第三章 链表第10页算法分析此算法关键是while循环语句，开始时p指针指向头结点，每一循环都修改指针值，让它指向下一个结点，同时将计数链表长度变量count加1。这么每循环一次就向后推移一个结点，直到p所指结点*p链域值为NULL为止。空指针NULL起标志作用，若无此标志，尾结点链域值为“无定义”，上述算法中while语句在做最终一次判断时将出现“运行错”，这是应予防止。第三章 链表第11页2.插入 所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x结点。实现插入算法主要完成三个基本操作：1)在单链表上找到插入位置，即找到第i个结点。能够用遍历方法，即从表头起顺次访问单链表结点，直至找到第i个结点。2)生成一个以x为值新结点。可经过C库函数malloc(size)来产生。3)将新结点链入单链表中。需要改变相关结点指针，以下面图所表示。第三章 链表第12页 假设指针p指向单链表中第i个结点，指针s指向已生成新结点，链入新结点操作以下：将新结点*s链域指向结点*p后继结点 (即s-next=p-next)；将结点*p链域指向新结点(即p-next=s)。第三章 链表第13页插入算法 void insert(node*head,int i,x)node*s,*p;int j;s=(node*)malloc(sizeof(node);/*生成新结点*/s-data=x;if(i=0)/*假如i=0,则将s所指结点插入到表头*/s-next=NULL;head=s;else p=head;j=1;/*查找第i个结点，由p所指向*/第三章 链表第14页插入算法续 while(p!=NULL&jnext;if(p!=NULL)/*把新结点插入其后*/s-next=p-next;p-next=s;else printf(“未找到！n”);第三章 链表第15页3.删除当需要从单链表上删除结点时，就要经过删除运算来完成。删除单链表上一个其值为x结点主要操作是：1)用遍历方法在单链表上找到该结点；2)从单链表上删除该结点。欲从单链表上删除一个结点，需修改该结点前一个结点指针，以下面图所表示。第三章 链表第16页 假设指针q指向待删除结点前一个结点，指针p指向要删除结点，删除该结点操作以下：将该结点前一个结点*q链域指向*p后继结点（即q-next=p-next）。第三章 链表第17页删除算法void delete(node*head,int x)node*p,*q;if(head=NULL)printf(“链表下溢！n”);/*判空*/if(head-data=x)/*如表头结点值等于x*/p=head;head=head-next;free(p);else q=head;/*从第二个结点开始查找*/p=head-next;第三章 链表第18页删除算法续 while(p!=NULL&p-data!=x)q=p;p=p-next;if(p!=NULL)/*找到该结点，删除*/q-next=p-next;free(p);else printf(“未找到！n”);返回第三章 链表第19页3.2.1 循环链表循环链表（circular linked list）是一个首尾相接链表，将单链表表尾结点原来空指针改为指向表头结点，就成为循环链表。循环链表并不多占存放单元，但从循环链表任一个结点出发都能够访问到此链表每一个结点，因为当访问到表尾结点后又能返回到头结点。第三章 链表第20页1.带头指针循环链表通常在循环链表表头结点前面再加一个空结点,也叫空表头结点。表空时空表头结点指针指向其本身，以下面图所表示为空循环链表。空表头结点除指针以外数据域是没有用，但为了将此结点与普通结点相区分，经常是将其赋以一个尤其数据，以与普通结点相区分。第三章 链表第21页2.带尾指针循环链表另一个方法是不设头指针而改设尾指针，这么不论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点位置是rear-next-next。第三章 链表第22页3.2.2 双链表 双向链表中每个结点除了有向后指针外，还有指向其前一个结点指针，这么形成链表中有两条不一样方向链，所以从某一结点均可向两个方向访问。双链表结点形式为：其中链域prior和next分别指向本结点直接前趋和直接后继结点。第三章 链表第23页假如循环链表结点再采取双向指针，就成为双向循环链表。第三章 链表第24页双链表较单链表即使要多占用一些存放单元，但对其插入和删除操作以及查找结点前趋和后继都非常方便。双链表结构是一个对称结构，设指针p指向双链表某一结点，则双链表对称性可用下式来表示：p=(p-prior)-next=(p-next)-prior 即结点*p地址既存放在其前趋结点 *(p-prior)后继指针域中，又存放在它后继结点*(p-next)前趋指针域中。第三章 链表第25页1.双链表插入设要在p所指结点前面插入一个新结点*q，则需要修改4个指针：q-prior=p-prior;q-next=p;(p-prior)-next=q;p-prior=q;第三章 链表第26页2.双链表删除设p指向待删除结点，则删除该结点步骤为：(p-prior)-next=p-next;(p-next)-prior=p-prior;这两个语句执行次序能够颠倒，执行这两个语句之后，可调用free(p),将*p结点释放。返回第三章 链表第27页3.3.1 链堆栈链堆栈是栈链接存放表示，它是只允许在表头进行插入和删除运算单链表。它与普通单链表没有什么不一样，只是将头指针head改称为栈顶指针top。第三章 链表第28页链堆栈入栈算法 在栈顶指针是top链堆栈中插入一个值为x结点算法：void push(node*top,int x)node*s;s=(node*)malloc(sizeof(node);/*建立一个结点指针*/s-data=x;s-next=top;top=s;第三章 链表第29页链堆栈出栈算法int pop(node*top)int x;node*p;if(top=NULL)printf(“栈为空!n”);else x=top-data;p=top;top=top-next;free(p);return(x);第三章 链表第30页3.3.2 链队列链队列需要两个指针，其中队首指针front指向链表表头，队尾指针rear指向链表表尾。普通插入时只修改队尾结点指针和队尾指针rear，删除时只修改队首指针front。当将第一个元素插入空队列或删除了最终一个元素而使队列为空时，front和rear都需要修改。第三章 链表第31页链队列插入算法void insert(node*front,rear,int x)node*s;s=(node*)malloc(sizeof(node);s-data=x;s-next=NULL;if(rear=NULL)/*处理空队列情况*/front=s;rear=s;else rear-next=s;rear=s;第三章 链表第32页链队列删除算法int delete(node*front,rear)node*p;int x;if(front=NULL)printf(“空队列!n”);else x=front-data;p=front;if(front=rear)front=NULL;rear=NULL;else front=front-next;free(p);return(x);第三章 链表第33页3.3.3 一元多项式算术运算设一个一元多项式为1.假如用数组来表示一元多项式，以各项指数作为下标，将各个系数存入一维数组中。第三章 链表第34页2.用单链表表示一元多项式将单链表每个结点对应着一元多项式中一个非零项，它由三个域组成，分别表示非零项系数、指数和指向下一个结点指针。设两个一元多项式为:求此两一元多项式之和C(x)=A(x)+B(x)。第三章 链表第35页3.运算规则将二个一元多项式中全部指数相同项系数相加，相加后，若和不为零，则组成“和一元多项式”中一项；若和为零，则“和一元多项式”中无此项；全部指数不相同项均抄到“和一元多项式”中。第三章 链表第36页返回第三章 链表第37页3.4 表示稀疏矩阵十字链表在十字链表中，矩阵每个非零元素对应着一个含有五个域结点，这五个域分别为该非零元素在稀疏矩阵中行号、列号、元素数值以及两个指针，其中一个指针指向同一列下一个非零元素结点，另一个指针指向同一行右边一个非零元素结点。第三章 链表第38页将每行非零元素结点链接成循环链表，又将每列非零元素结点链接成循环链表，就组成了十字形链接结构。对于每行、每列循环链表都有一个空表头结点，以利于元素插入和删除运算。这些空表头结点行号、列号都标成零，方便和其它结点相区分。整个十字链表有一个总空表头结点，在普通结点标以行号、列号之处，此结点是标出矩阵行数m和列数n。有一个指针HM指向这个总空表头结点。第三章 链表第39页例：稀疏矩阵M及其对应十字链表如图所表示。第三章 链表第40页第三章 链表第41页空表头结点结构因各列、各行空表头结点中行号和列号都是零，且每列空表头结点只用到向下指针，每行空表头结点只用到向右指针，故可将这组空表头结点适用。因为数值域也没有用，可将空表头结点数值域改为一个指针域，将各个空表头结点也链接成一个循环链表。返回第三章 链表第42页例3.1有一个单链表L(最少有一个结点)，其头结点指针为head，编写一个函数将L逆置，即最终一个结点变成第1个结点，原来倒数第二个结点变成第二个结点如此等等。解：本题采取算法是，从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理结点，q指向p下一个结点，r指向q下一个结点，q、r作用是为了预防倒置指针时，下一个结点丢失而设置，有了这三个指针，就能够方便地实现指针倒置。最终将第一个结点next域置为NULL，并将头指针指向最终一个结点，这么到达了本题要求。第三章 链表第43页例3.1算法void invert(node*head)node*p,*q,*r;p=head;q=p-next;while(q!=NULL)/*没有后继时停顿*/r=q-next;q-next=p;p=q;q=r;head-next=NULL;head=p;第三章 链表第44页例3.2有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后链表仍保持是循环链表形式。解：先分别找到两个链表表尾，将head2放入链表head1表尾，将两个链表链接起来，然后将head1放入原head2链表表尾，组成新循环链表。第三章 链表第45页例3.2算法link(node*head1,head2)node*p,*q;p=head1;while(p-next!=head1)p=p-next;q=head2;while(q-next!=head2)q=q-next;p-next=head2;q-next=head1;第三章 链表第46页例3.3给出在双链表中第i个结点(i0)之后插入一个元素为x结点函数。解：在前面双链表一节中，已经给出了在一个结点之前插入一个新结点方法，在一个结点之后插入一个新结点思想与前面是一样。第三章 链表第47页例3.3算法void insert(dnode*head,int i,x)dnode*s,*p;int j;s=(dnode*)malloc(sizeof(dnode);/*建立一个待插入结点，由s指向*/s-data=x;if(i=0)/*如i=0,将s所指结点插入到表头后返回*/s-next=head;head-prior=s;head=s;第三章 链表第48页例3.3算法续 else p=head;/*查找第i个结点，由p指向*/j=1;while(p!=NULL&jnext;if(p!=NULL)/*若查找成功，把s插入到p之后*/if(p-next=NULL)/*若p是最终一个结点，则直接把s结点链入*/第三章 链表第49页例3.3算法续 p-next=s;s-next=NULL;s-prior=p;else s-next=p-next;p-next-prior=s;p-next=s;s-prior=p;else printf(“未找到!n”);返回第三章 链表第50页小结单链表 循环链表双向链表 双向循环链表 十字链表 返回第三章 链表第51页习题与练习一、基础知识题1.试比较次序表与链表优缺点。2.试分析单链表与双链表优缺点。3.为何在单循环链表中设置尾指针比设置头指针更加好？4.写出在循环双链表中p所指结点之后插入一个s所指结点操作。5.写出在单链表中p所指结点之前插入一个s所指结点操作。6.请利用链表来表示下面一元多项式 第三章 链表第52页二、算法设计题1.有一个有n个结点单链表，设计一个函数将第i-1个结点与第i个结点交换，但指针不变。2.设计一个函数，查找单链表中数值为x结点。3.已知一个单链表，编写一个删除其值为x结点前趋结点算法。4.已知一个单链表，编写一个函数从此单链表中删除自第i个元素起length个元素。第三章 链表第53页5.已知一个递增有序单链表，编写一个函数向该单链表中插入一个元素为x结点，使插入后该链表依然递增有序。6.已知一个单链表，编写一个函数将此单链表复制一个拷贝。7.有一个共10个结点单链表，试设计一个函数将此单链表分为两个结点数相等单链表。8.与上题相同单链表，设计一个函数，将此单链表分成两个单链表，要求其中一个仍以原表头指针head1作表头指针，表中次序包含原线性表第一、三等奇数号结点；另一个链表以head2为表头指针，表中次序包含原单链表第二、四等号结点。第三章 链表第54页9.已知一个指针p指向单循环链表中一个结点，编写一个对此单循环链表进行遍历算法。10.已知一个单循环链表，编写一个函数，将全部箭头方向取反。11.在双链表中，若仅知道指针p指向某个结点，不知头指针，能否依据p遍历整个链表？若能，试设计算法实现。12.试编写一个在循环双向链表中进行删除操作算法，要求删除结点是指定结点p前趋结点。返回第三章 链表第55页谢谢收看 返回第三章 链表第56页