C程序设计第九章ppt西工大.ppt

1,第9章链表,快速排序法A1AN,2,关键数据,一趟快速排序：将所有比关键数据小的数据放在它左边，所有比关键数据大的数据放在它右边,i=1，j=N,3,3456781233719,i,j,1）利用j从后向前扫描，找到第一个比关键数据小的数，交换,1956781233734,i,j,2）利用i从前向后扫描，找到第一个比关键数据大的数，交换,1934781233756,i,j,3）重复（1）即利用j从后向前扫描，找到第一个比关键数据小的数，交换,1977812333456,4,1977812333456,1973412337856,1973312347856,条件i=right)return;while(i=temp,6,intmain()inta7=17,2,6,12,1,9,5;inti;quicksort(a,0,6);/*排好序的结果*/for(i=0;inext=p-next，p-next=s。重复步骤加入更多结点。,31,9.2.1创建单链表,采用头插法创建单链表的算法如下：,1voidCreateLinkF(LinkList*L,intn,void(*input)(ElemType*)2/头插法创建单链表，调用input输入函数输入数据3LinkLists;4*L=(LinkList)malloc(sizeof(LNode);5(*L)-next=NULL;/初始时为空表6for(;n0;n-)/创建n个结点链表7s=(LinkList)malloc(sizeof(LNode);8input(/头结点之后1112,指向头节点的头指针,32,9.2.1创建单链表,1voidCreateLinkF(LinkList*L,intn,void(*input)(ElemType*),参数L表示将要创建出来的单链表指针，之所以是LinkList类型的指针类型（即指针的指针），其原因是需要将链表返回到调用函数中。n表示创建链表时需要输入的元素数目，由实际应用中的具体要求确定。,33,9.2.1创建单链表,图9.5头插法建立的单链表L,运行时若输入5个元素：1、2、3、4、5，则调用建立的单链表如图所示。,LinkListL;CreateLinkF(/创建单链表L,34,9.2.1创建单链表,（2）尾插法建立链表CreateLinkR(4p=*L=(LinkList)malloc(sizeof(LNode);5for(;n0;n-)/创建n个结点链表6s=(LinkList)malloc(sizeof(LNode);7input(/尾结点11,36,9.2.1创建单链表,图9.6尾插法建立的单链表L,运行时若输入5个元素：1、2、3、4、5，则调用CreateLinkR(/数据域structtagNODE*next;/指针域LNODE，*LinkList;/LNode为单链表结构体类型，LinkList为单链表指针类型,数据域包含两个个成员，代表学生信息结点中的学号、英语成绩。next成员表示指针域，存放另一个结点的地址，是链表中的组织者。,链表的建立操作,40,通过第7章介绍的内存动态分配技术可以产生新结点的内存单元，例如：调用malloc、realloc内存分配函数或free释放函数时，在程序中需要文件包含命令：,LinkListp;/链表指针p=(LinkList)malloc(sizeof(LNode);/分配LNode类型内存单元且将地址保存到p中,#include,链表的建立操作,41,第一步：新节点加入链表过程,核心问题：维护链表结构，假定有一个LNODE类型的对象指针L，通过将一个新结点的地址赋给L的最后一个节点的link成员，则可以通过尾节点的link成员（next）“链接”到新结点上，重复这个过程可以得到完整链表结构。,链表的建立操作,新产生一个节点,新节点指针q,尾指针p,42,第二步更新尾指针，使得始终指向当前链表中最后一个节点,链表的建立操作,新产生一个节点,新节点指针q,尾指针p,第三步如果未到链表末尾，重复第一步和第二步,总结：建立过程中始终需要有一个节点指针指向当前链表中最后一个节点的位置,动态单链表的建立完整过程1）定义与节点同类型的链表头指针变量L并赋值0，表示链表在建立之前是空的；2)定义与节点同类型的工作指针变量p、q。,链表的建立操作,3)开辟第一个节点的存储区域，输入第一个节点数据；并使L、p、q指向第一个节点，,L,q,实现代码：Len=sizeof(LNODE);q=(LinkLlist)malloc(len);scanf(%ld,%f,链表的建立操作,4)开辟下一节点的存储区域，使q指向新节点并输入新节点数据，然后使上一节点的next成员指向新节点；,L,q,1048,实现代码q=(LinkList)malloc(len);scanf(%ld,%f,/更新尾指针,1370,1370,链表的建立操作,3)重复第4步，建立并链接多个节点直至所需长度，将末尾节点的next成员赋值0。,L,p2,NULL,10481370,实现代码q=(LinkList)malloc(len);scanf(%ld,%f,/末尾节点next赋值0,链表的建立操作,采用尾插法创建单链表的算法如下：,1voidCreateLinkR(LinkListL,intn)2/尾插法创建单链表3LinkListp,q;4p=L=(LinkList)malloc(sizeof(LNode);5for(;n0;n-)/创建n个结点链表6q=(LinkList)malloc(sizeof(LNode);7scanf(“%d,%f”,/尾结点11,生成新节点,更新尾指针,实现建立链表过程,链表的建立操作,48,9.2.1创建单链表,（3）初始化链表InitList(4(*L)-next=NULL;/初始时为空表5,49,9.2.1创建单链表,（4）判断链表是否为空表ListEmpty(L)检测一个链表是否为空表的算法如下：,1intListEmpty(LinkListL)/检测L是否为空表2/若L为空表返回TRUE，否则返回FALSE3returnL-next=NULL;4,50,9.2.2创建双链表,双链表每个结点有两个指针域，next指向直接后继结点，prev指向前驱结点。建立双链表的过程与单链表相似，只是需要再处理prev指针，建立前向链即可。,51,9.2.2创建双链表,采用头插法创建双链表的算法如下：,1voidCreateLinkF(DLinkList*L,intn,void(*input)(ElemType*)2/头插法创建双链表，调用input输入函数输入数据3DLinkLists;4*L=(DLinkList)malloc(sizeof(DNode);5(*L)-prev=(*L)-next=NULL;6for(;n0;n-)/创建n个结点链表7s=(DLinkList)malloc(sizeof(DNode);8input(1213,52,9.2.2创建双链表,采用尾插法创建双链表的算法如下：,1voidCreateLinkR(DLinkList*L,intn,void(*input)(ElemType*)2/尾插法创建双链表，调用input输入函数输入数据3DLinkListp,s;4p=*L=(DLinkList)malloc(sizeof(DNode);5(*L)-prev=(*L)-next=NULL;6for(;n0;n-)/创建n个结点链表7s=(DLinkList)malloc(sizeof(DNode);8input(1112,53,9.2.2创建双链表,构造一个空的双链表（即没有数据结点）的算法如下：,1voidInitList(DLinkList*L)/构造一个空的单链表L23*L=(DLinkList)malloc(sizeof(DNode);4(*L)-prev=(*L)-next=NULL;5,54,9.3链表的运算,双链表与单链表的基本运算大多数是相同的，本节仅讨论单链表的情形。,55,9.3.1链表的遍历,（1）链表遍历ListTraverse(L,visit()与数组不同，链表不是用下标而是用指针运算查找数据元素的。通过链表的头结点L可以访问开始结点p=L-next，令p=p-next，即p指向直接后继结点，如此循环可以访问整个链表中的全部结点，这就是链表的遍历（traverse）。链表的输出、销毁、查找和逆序等运算都需要遍历链表。链表遍历算法的实现步骤为：令指针p指向L的开始结点。若p为0，表示已到链尾，遍历结束。令p指向直接后继结点，即p=p-next。重复步骤直至遍历结束。,【例】建立并输出有3名学生数据的单链表。#include/包含NULL定义#defineN3structtagSTU/全局结构体类型定义longnum;floatscore;structtagSTU*next;/自引用结构体指针;intmain(),intmain()structtagSTU*head,*p1,*p2;inti,len;head=NULL;/head初始化len=sizeof(structtagSTU);/求类型长for(i=1;inum,/标记末尾节点,intmain()for(i=1;inext;/p1指向下一节点printf(num=%ld,score=%5.2fn,p1-num,p1-score);return0;/main,SX09-10,更适用的链表输出：p1=head;while(p1!=NULL)/适用于任意节点数链表printf(num=%ld,score=%5.2fn,p1-num,p1-score);p1=p1-next;注：本形式的链表输出具有通用性，可适应由于删除或插入节点引起的链表长度的变化。,60,9.4结点的插入与删除,链表中每个结点都有指针域指向其前后结点，在进行结点插入和删除时，不能仅仅只对该结点进行操作，还要考虑其前后结点。,61,9.4.1单链表插入结点,插入结点操作是指将一个新结点插入到已知的链表中。插入位置可能在头结点、尾结点或者链表中间，插入操作前需要定位插入元素的位置和动态分配产生新结点。假设将新结点s插入到单链表的第i个结点位置上。方法是先在单链表中找到第i-1个结点p，在其后插入新结点s，如图（a）所示。为了插入结点s，先让结点s的指针域指向结点p的后一个结点（即p-next），如图（b）所示；然后修改结点p的指针域，令其指向结点s，如图（c）所示，从而实现3个结点指向关系的变化。,62,9.4.1单链表插入结点,图9.8单链表插入结点示意,63,9.4.1单链表插入结点,图9.8单链表插入结点示意,64,9.4.1单链表插入结点,图9.8单链表插入结点示意,65,9.4.1单链表插入结点,图9.8单链表插入结点示意,总结：插入节点需要知道插入点之前的节点位置p。,66,9.4.1单链表插入结点,实现上述步骤的C语言语句如下：请注意，这两个表达式的顺序不能颠倒。因为若先修改结点p的指针域指向结点s，结点p的后一个结点（p-next）就此从链表中断开，再让结点s的指针域指向结点p的后一个结点已成错误的。在单链表中第i个位置上插入元素e的新结点s的算法如下：,s-next=p-next,p-next=s;/结点插入算法,节点的插入插入可分为随意插入和按顺序插入，随意插入包括插入到头部、尾部或中间指定位置；按顺序插入是指按某关键字的顺序插入，而在插入前链表必须已按该关键字进行了排序。按顺序插入的步骤：开辟待插入节点的存储区域并输入数据；2)查找插入位置：从链表首节点开始按关键字成员与待插入节点相同成员进行比较，直到确定了插入位置；,3)将插入位置前一节点的“链节”成员赋给待插入节点的“链节”成员；4)将待插入节点的指针赋给前一节点“链节”成员；若：插入点在链头，先将头指针赋给插入节点的指针域，再将待插入节点的指针赋给头指针变量。,head,1048,104813701012,1012,2680,2680,1048,2030,2030,【例】在上例增加“按学号插入节点的函数”插入函数：structtagSTU*insert(structtagSTU*head)structtagSTU*p0,*p1,*p2;longn;intlen;len=sizeof(structtagSTU);p0=(structtagSTU*)malloc(len);/申请新节点printf(Enternum,scoretoinsert:);scanf(%ld,%f,/从首节点开始查找,p1=head;/插入在头部if(nnum)p0-next=head;head=p0;elsedo/查找插入位置p2=p1;p1=p1-next;while(p1!=NULL/insert,SX09-12,71,9.4.2单链表删除结点,结点删除操作是指将链表中的某个结点从链表中删除。删除位置可能在头结点、尾结点或者链表中间，删除操作后需要释放删除结点的内存空间。将链表中第i个结点删去的方法是先在单链表中找到第i-1个结点p，再删除其后的结点，如图（a）所示。若要删除结点p的后一个结点（即p-next），只需要将p的指针域指向p-next的后一个结点（即p-next-next），如图（b）所示。,72,9.4.2单链表删除结点,图9.9单链表删除结点示意,73,9.4.2单链表删除结点,图9.9单链表删除结点示意,第一步：将予删除节点后一个节点连到d前一个节点,74,9.4.2单链表删除结点,图9.9单链表删除结点示意,第二步：将予删除节点的内存空间释放,free(d);/释放结点,实现分析：需要保存访问节点的前一个节点的位置，指针p。,75,9.4.2单链表删除结点,实现上述步骤的C语言语句如下：,p-next=p-next-next;/结点删除算法,76,9.4.2单链表删除结点,1intListDelete(LinkList*L,ElemType*ep)2/删除第i个结点,并由*ep返回其值3LinkListp=NULL,q=*L;/q指向头结点4while(q!=NULL/操作成功返回真（1）14,77,约瑟夫问题，又称为约瑟夫环。据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。问题：站在哪个位置上可以成为最后剩下的那个人？,链表的删除操作,例题：有N个人围坐一圈，从第一个开始报数，凡是报到3就退出圈子，请找出最后一个留在圈子里的序号？,数组的声明和引用,问题解决思路：利用循环链表解题，不断循环，删除逢3的节点，直到最后剩一个节点核心问题：删除节点,78,分析：结点删除操作是指将链表中的某个结点从链表中删除。删除操作后需要释放删除结点的内存空间。,79,9.1.1链表的概念,首先设计一种称为结点（node）的数据类型：这个结构体类型中，data成员表示数据域，代表结点的数据信息。,typedefstructtagNODE/结点数据类型intdata;/数据域structtagNODE*next;/指针域NODE;,next成员表示指针域，存放另一个结点的地址，是链表中的组织者。,80,P,Num=1,Num=2,Num=3,删除,81,剩余数为1？,删除当前节点,计数等于3,计数加1,更新剩余数,否,输出剩余节点序号,是,是,否,单链表删除结点,问题解决流程图表示,82,9.4.2单链表删除结点,1voidsearch(LinkList*L，intN)2/约瑟夫环3LinkListp=*L;intsum=N;intNum=1/p指向首结点4while(sum!=1)/直到剩余1个结点5Num+;/计数加一6if(Num=3)q=p-next;p=p-next-next;free(q);Num=1;sum-;/释放计数为3的节点78*L=p;9,【例】创建一个链表,当输入数据小于等于0时创建结束，先输出原始链表，然后将这个链表按反转重新排列，即将链头当链尾，链尾当链头，输出反转后的链表。输入格式:123497620输出格式:原始表:12-34-9-7-6-2反转表:2-6-7-9-34-12注意:输入以0表示数据结束,建立链表要具有通用第一个输出为12,第二个为-34,因此需做计数,#include#includetypedefstructtagDATAintn;structtagDATA*next;NODE;intmain()NODE*head,*create(),*reverse(NODE*head);voidplink(NODE*head,char*);head=create();/调建立链表函数plink(head,“原始表:”);/调输出链表