C语言_链表ppt课件

科学和谐创新自主,王艳春,C语言链表,.,2,单链表,单链表,单链表的定义单链表的基本操作遍历（递归和非递归遍历）插入（插入4种情况，重点）建立删除将一个链表排序将两个有序链表合并将一个链表逆置约瑟夫问题,1、单链表的定义,最简单的是单链表，单链表中每个节点由两个字段组成：数据字段和指针字段，数据字段表示元素的本身信息，指针字段指明下个元素的位置。单链表用来表示线性结构。例如线性表（a1,a2,an)可以表示为：C语言定义链表的结构如下typedefstructNodeintdata;structNode*next;NODE;,带有头节点的单链表,一般各种资料表示链表有两种，一种是带头节点的，一种是使用头指针的（不带头节点的）。带头节点的就是有一个专门的头节点h，它的后继指向链表的第一个元素。使用头指针的没有专门的头节点，只有一个指针h指向链表的第一个元素,.,6,单链表的遍历,2、链表的遍历（显示链表）,设head为链表的头指针，首先从head所指的节点开始打印，沿着链的方向向右遍历，直到到最后一个节点，下面是一个打印链表的递归函数。voidlprint(NODE*head)if(head!=NULL)printf(“%dt”,head-data);lprint(head-next);许多问题中，有时候为了操作方便，需要在第一个节点之前增加一个特殊的节点，称为头节点，它的data字段不含信息或根据问题的需要存放特殊信息。,2、链表的遍历（显示链表）,一个非递归算法以下函数disp()用于显示头节点为*h的链表的所有节点数据域。voiddisp(structNode*h)structNode*p=h;printf(输出链表:);if(p=NULL)printf(空表n);elsewhile(p-next!=NULL)printf(%4d,p-data);p=p-next;printf(%4dn,p-data);,.,9,单链表的插入,3、链表的插入(头指针的情况下）,对于插入有以下几种情况在一个空链表上插入一个元素。（即要插入位置前方和后方均无元素）从链表表头处插入一个元素（即要插入的位置前方无元素，后方有元素）从链表结尾处处插入一个元素（即要插入的位置后方五元素，前方有元素）从链表的中间插入（即要插入的位置前方和后方均有元素）其中第三种情况可以按照第四种情况处理，但有一定特殊性所以将其分开注意：产生新的节点必须用malloc或者calloc开辟空间,在空链表上插入一个元素,实现的语句：p-next=NULL;h=p;,在链表的表头插入一个元素,完成插入后表头指针要指向新的表头节点实现的语句：p-next=h;h=p;,在链表结尾出插入一个元素,不涉及头节点的变动首先要用一个循环语句找到qq=h;while(q-next!=NULL)q=q-next;然后执行插入语句：q-next=p;p-next=NULL;,在链表中间插入一个元素,这种情况不涉及头节点的变动假如被插入位置的后方特征是数据项为x则可以执行循环语句q=h;while(q-next-data!=x)q=q-next;确保找到被插入地方的前方节点q,然后执行插入语句：p-next=q-next;q-next=p;注意语句顺序,3、链表的插入(有单独头节点的情况下）,由于增加了表头节点，不用象没有头节点的情况时，区分是否插入点在表头，所以对于插入只有两种情况从链表结尾处处插入一个元素（即要插入的位置后方五元素，前方有元素）从链表的中间插入（即要插入的位置前方和后方均有元素）其中第一种情况可以按照第二种情况处理，但有一定特殊性（语句的顺序可以换）所以将其分开,在链表结尾出插入一个元素,首先要用一个循环语句找到qq=h;while(q-next!=NULL)q=q-next;然后执行插入语句：p-next=NULL;q-next=p;,在链表中间插入一个元素,假如被插入位置的后方特征是数据项为x则可以执行循环语句q=h;while(q-next-data!=x)q=q-next;确保找到被插入地方的前方节点q,然后执行插入语句：p-next=q-next;q-next=p;注意语句顺序,4、链表的建立,链表的建立就是链表从无到有的过程建立一个头节点，并指向NULL，就建立了一个空的链表建立有n个元素的链表有三个阶段建立头节点并指向NULL（建立了一个空的链表）插入第一个元素（插入的第一种情况）在表头或者表尾连续插入其他n-1个元素（反复执行插入的第二，第三种情况）,建立带有单独头节点的链表，先建立头节点structNode*create()structNode*head,*p,*q;intn;head=(structNode*)malloc(sizeof(structNode);head-next=NULL;/第一阶段，建立一个头节点，并指向NULLp=head;while(1)printf(请输入一个正整数,0代表结束:);scanf(%d,.,20,单链表的删除,链表的删除,对于只有头指针的链表分为两种情况删除的是第一个节点，即紧跟头节点的节点删除的不是第一个节点对于有头节点的链表的删除就比较简单，有两种情况，两种情况可以合并为一种注意侠义的删除仅仅指脱离链表前驱后继的关系，并不是真正删除那个节点。如果被脱离的那个节点确实没有用处了，应该用free收回内存。,链表的删除（只有有单独头指针）删除的是第一个节点，即头节点指向的元素时,首先要用一个指针记录删除前的头节点p=h;然后执行修改头指针的语句：h=h-next;如果删除的节点没有用处的话应该释放空间free(p);,链表的删除（只有有单独头指针）删除的是中间节点时,首先要找到p以及p的前驱q然后执行删除语句：q-next=p-next;当p为第一个元素时候，p的前驱是h即q=h;注意上面一步仅仅是将p指向的那个节点脱离链表，并没有将那个节点删除如果这时候p指向的那个节点已经没有用处了，应该回收那个节点占用的内存free(p);,链表的删除（有单独头节点）,首先要找到p以及p的前驱q然后执行删除语句：q-next=p-next;当p为第一个元素时候，p的前驱是h即q=h;注意上面一步仅仅是将p指向的那个节点脱离链表，并没有将那个节点删除如果这时候p指向的那个节点已经没有用处了，应该回收那个节点占用的内存free(p);整个过程和只有头指针的第二种情况完全一样,.,25,单链表的排序,链表的排序（按照升序排列）,不同于数组，链表的排序不用改变每个节点里面的值，只需要改变节点和节点之间的连接关系。思路1,类似选择排序，每次找出最小的，脱离原链表，插入在新链表的末尾先把最小的元素的那个节点找出来，删除在原链表的位置，自己作为新的链表的头节点把最小的元素的那个节点找出来，删除在原链表的位置，插入在新链表头节点的后面。然后在原链表中依次找到最小的那个节点，在原链表中删除，插入在新的链表中，插入的位置在新链表上次插入的那个节点之后。思路2，类似冒泡排序如果相邻元素无序，则交换，注意现在链表中交换是要改变节点的连接关系，而不是改变节点。相邻元素交换应该为先执行删除操作，再执行插入操作,排序步骤的图示（有头节点的情况）,排序步骤的图示（有头节点的情况）,voidsort(structNode*h)structNode*p,*h1,*q,*pmin,*pminpre,*newp;h1=(structNode*)malloc(sizeof(structNode);/新的头节点newp=h1;while(*h)-next!=NULL)/当老链表没有元素节点的时候才完毕pmin=(*h)-next;pminpre=*h;q=pmin;p=pminpre;while(q-next!=NULL)/当老链表遍历一趟完毕，找到这一趟的最小值q=q-next;p=p-next;if(q-datadata)pmin=q;pminpre=p;pminpre-next=pmin-next;/原链表中删除节点pminnewp-next=pmin;/新链表的末尾增加节点pminnewp=pmin;newp-next=NULL;*h=h1;/老的头节点赋值为新的头节点，想一想为什么形参要定义为Node*h而不Node*h,链表的排序,上述是对有头节点的链表排序对于仅有头指针的链表（无头节点的链表）排序要稍微复杂一些，这是由于仅有头指针链表删除一个节点的时候，要区分是不是第一个节点，是第一个节点的话要修改头指针。,.,31,单链表的逆置,将一个链表逆置,思路：将原链表元素按照顺序取出来（删除和原链表脱离的关系，但并不删除节点），然后插入在新链表的第一个元素的位置上。对于仅有头指针和有头节点两种情况程序会有些差别：1、有头节点的时候，每次在头节点后执行插入操作即可。2、仅有头指针的时候，每次在头指针前面插入元素，然后更新头指针。,将一个链表逆置图示（有头节点的情况）,将一个链表逆置代码（有头节点的情况）,reverse(structNode*head)structNode*p,*newhead,*p1;p=(*head)-next;newhead=head;newhead-next=NULL;while(p!=NULL)p1=p;/p1为每次取出的节点p=p-next;/读取下一个节点p1-next=newhead-next;/插入在新链表的表头的前面newhead-next=p1;*head=newhead;/将新的表头赋值给形参的表头,将一个链表逆置过程的图示（只有头指针情况）,将一个链表逆置(仅有头指针的情况),思路：将原链表第一个元素取出来（删除和原链表脱离的关系，但并不删除节点），然后作为新链表的表头节点，用一个新的头指针指向它。然后按照顺序将原链表的每个节点取出，插入在新链表头节点的前面，同时更新新链表的头节点指针指向的位置（即执行在链表的表头插入一个元素）reverse(structNode*head)structNode*p,*newhead,*p1;p=*head;newhead=NULL;while(p!=NULL)p1=p;/p1为每次取出的节点p=p-next;/读取下一个节点p1-next=newhead;/插入在新链表的表头的前面newhead=p1;/更新新链表的表头位置*head=newhead;/将新的表头赋值给形参的表头,.,37,两个有序单链表的合并,将两个有序链表合并,思路：建立一个新个头节点，分别在两个链表遍历，每次比较应该插入哪个节点，然后加入到新链表的末尾。,将两个有序链表合并图示,将两个有序链表合并图示,将两个有序链表合并图示,将两个有序链表合并图示,代码,/将两个有序链表合并structNode*unite(structNode*h1,structNode*h2)structNode*p1,*p2,*p3,*h3,*add;h3=(structNode*)mallo