搜索
§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用指针处理链表建立链表的函数如下:#includestdio.h#includemalloc.h#defineNULL0//令NULL代表０，用它表示“空地址#defineLENsizeof(structstudent)//令LEN代表struct//student类型数据的长度structstudent{longnum;floatscore;structstudent*next;};intn;//n为全局变量，本文件模块中各函数均可使用它§11.7用指针处理链表structstudent*creat(){structstudent*head;structstudent*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);head=NULL;while(p1-num!=0){n=n+1;if(n==1)head=p1;elsep2-next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);}p2-next=NULL;/*将新节点的next指针赋值NULL，即作为表尾*/return(head);}P1=(structstudent*)malloc(sizeof(structstudent))§11.7用指针处理链表11.7.5输出链表首先要知道链表第一个结点的地址，也就是要知道head的值。然后设一个指针变量p,先指向第一个结点，输出ｐ所指的结点，然后使ｐ后移一个结点，再输出，直到链表的尾结点。图11-17,11-18§11.7用指针处理链表例１1．9编写一个输出链表的函数print.voidprint(structstudent*head){structstudent*p;printf(\nNow,These%drecordsare:\n,n);p=head;if(head!=NULL)do{printf(%ld%5.1f\n,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:structstudent*del(structstudent*head,longnum){structstudent*p1,*p2;if(head==NULL)/*原表为空，找不到删除节点*/{printf(\nlistnull!\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;elsep2-next=p1-next;/*指向删除节点的下一节点*/printf(delete:%ld\n,num);n=n-1;}elseprintf(%ldnotbeenfound!\n,num);/*在链表中未找到删除节点*/return(head);}