删除链表结点.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,11.7,用指针处理链表,11.7.4,建立动态链表,所谓建立动态链表是指在程序执行过程中从,无到有地建立起一个链表，即一个一个地开辟结,点和输入各结点数据，并建立起前后相链的关系,例,11.5,写一函数建立一个有,3,名学生数据的单向动,态链表,.,算法如图,图,11-12,11.7,用指针处理链表,算法的实现：,我们约定学号不会为零，如果输入的学号为,，则表示建立链表的过程完成，该结点不应连,接到链表中。,如果输入的,p1-num,不等于，则输入的是第,一个结点数据（,n=1,），令,head,p1,，即把,p1,的值,赋给,head,，也就是使,head,也指向新开辟的结点,p1,所指向的新开辟的结点就成为链表中第一个结点,图,11-13,11.7,用指针处理链表,算法的实现：,再开辟另一个结点并使,p1,指向它，接着输入该,结点的数据,.,如果输入的,p1-num,，则应链入第个结点,（,n=2),将新结点的地址赋给第一个结点的,next,成员,.,接着使，也就是使指向刚才建,立的结点,图,11-14,11.7,用指针处理链表,算法的实现：,再开辟一个结点并使,p1,指向它，并输入该结点的,数据,.,在第三次循环中，由于（），又,将的值赋给,-,，也就是将第,个结点连接到第个结点之后，并使,，使指向最后一个结点,.,图,11-15,11.7,用指针处理链表,算法的实现：,再开辟一个新结点，并使,p1,指向它，输入该结,点的数据。由于,p1-num,的值为，不再执行循环,，此新结点不应被连接到链表中,.,将,NULL,赋给,p2-next.,建立链表过程至此结束，,p1,最后所指的结点,未链入链表中，第三个结点的,next,成员的值,为,NULL,，它不指向任何结点。,图,11-16,11.7,用指针处理链表,建立链表的函数如下,:,#include,#include,#define NULL 0,/,令,NULL,代表，用它表示,“,空地址,#define LEN sizeof(struct student),/,令,LEN,代表,struct/student,类型数据的长度,struct student,long num;,float score;struct student*next;,;int n;,/n,为全局变量，本文件模块中各函数均可使用它,11.7,用指针处理链表,struct student*creat(),struct student*head;,struct student*p1,*p2;,n=0;,p1=p2=(struct student*)malloc(LEN);,scanf(%ld,%f,head=NULL;,while(p1-num!=0),n=n+1;,if(n=1),head=p1;,else,p2-next=p1;,p2=p1;,p1=(struct student*)malloc(LEN);,scanf(%ld,%f,p2-next=NULL;,/*,将新节点的,next,指针赋值,NULL,，即作为表尾*,/,return(head);,P1=(struct student*)malloc(sizeof(struct student),11.7,用指针处理链表,11.7.5,输出链表,首先要知道链表第一个结点的地址，也就是,要知道,head,的值。然后设一个指针变量,p,先指向,第一个结点，输出所指的结点，然后使后移,一个结点，再输出，直到链表的尾结点。,图,11-17,11-18,11.7,用指针处理链表,例,1,9,编写一个输出链表的函数,print.,void print(struct student*head),struct student*p;,printf(nNow,These%d records are:n,n);,p=head;,if(head!=NULL),do,printf(%ld%5.1fn,p-num,p-score);,p=p-next;,while(p!=NULL);,11.7,用指针处理链表,11.7.6,对链表的删除操作,从一个动态链表中删去一个结点，并不是真,正从内存中把它抹掉，而是把它从链表中分离开,来，只要撤销原来的链接关系即可。,图,11-19,11.7,用指针处理链表,例,11.10,写一函数以删除动态链表中指定的结点,.,解题思路,:,从,p,指向的第一个结点开始，检查该结点中的,num,值是否等于输入的要求删除的那个学号。如果,相等就将该结点删除，如不相等，就将,p,后移一个,结点，再如此进行下去，直到遇到表尾为止。,11.7,用指针处理链表,可以设两个指针变量,p1,和,p2,，先使,p1,指向,第一个结点,.,如果要删除的不是第一个结点，则使,p1,后,移指向下一个结点,(,将,p1-next,赋给,p1),，在此,之前应将,p1,的值赋给,p2,，使,p2,指向刚才检查,过的那个结点,11.7,用指针处理链表,注意：,要删的是第一个结点（的值等于的值，如图,1-,0,（）那样），则应将,-,赋给。这时指向原来的第二个结点。第一个结点虽然仍存在，但它已与链表脱离，因为链表中没有一个结点或头指针指向它。虽然还指向它，它仍指向第二个结点，但仍无济于事，现在链表的第一个结点是原来的第二个结点，原来第一个结点已,“,丢失,”,，即不再是链表中的一部分了。,11.7,用指针处理链表,图,11-20,11.7,用指针处理链表,注意：,如果要删除的不是第一个结点，则将,-,赋给,-,，见图,1,0,（）。,-,原来指向指向的结点（图中第二个结点），现在,-,改为指向,-,所指向的结点（图中第三个结点）。所指向的结点不再是链表的一部分。,还需要考虑链表是空表（无结点）和链表中找不到要删除的结点的情况。,11.7,用指针处理链表,图,11-20,11.7,用指针处理链表,算法：,图,11-21,删除结点的函数,del:,struct student*del,(struct student*head,long num),struct student*p1,*p2;,if(head=NULL),/*原表为空，找不到删除节点*/,printf(nlist null!n);,return(head),;,p1=head;,while,(num!=p1-num&p1-next!=NULL),/*顺序查找要删除的节点*/,p2=p1;,p1=p1-next;,if(num=p1-num),/*判断是否是删除的节点*/,if(p1=head),/*判断删除的是不是首节点*/,head=p1-next;,else,p2-next=p1-next;,/*指向删除节点的下一节点*/,printf(delete:%ldn,num);,n=n-1;,else printf(%ld,n,ot been found!n,num);,/*在链表中未找到删除节点*/,return(head);,