(6.43)-第42课（9.4节-用指针处理链表）

用指针处理链表结构体和共同体引例：选择合适的数据结构来存放一批学生的学号及考试成绩，以便进一步处理分析：由于学生人数未知，用静态数据结构不合适。用链表处理较恰当概念：链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构用链表处理该问题的基本思路：将各学生的数据进行离散存放，来一个学生就分配一小块内存（结点）。并将各结点用指针依次连接起来链表有一个“头指针”变量，它存放一个地址，该地址指向链表中的第一个元素链表中每一个元素称为“结点”每个结点都应包括两个部分：数据域：用户需要用的实际数据指针域：下一个结点的地址结点1结点2结点nNULLhead……头指针head指向第一个结点每个结点应包含下一结点的开始地址。对于两个相邻的结点p1、p2，p1是p2的直接前驱结点，p2是p1的直接后继结点最后一个结点中的指针为空，称为“链尾”，其指针部分存放NULL这样的链表称为单向链表NULLhead……p1p2a1a2∧anhead…带头结点的线性链表a1a2∧ana3head…不带头结点的线性链表链表中的结点必须是结构体类型，其中一个成员是指针类型，这个指针类型指向它所在的结构体类型例如：structstudent{intnum;floatscore;structstudent*next;};

num

score

next数据域指针域链表的基本操作创建链表：从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系遍历链表：从头结点开始，逐个访问链表里的每个结点，完成相关操作插入结点：在结点ki-1与ki之间插入一个新的结点k’，使结点个数增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k’成为ki-1的后继、ki的前驱删除结点：删除结点ki，使结点个数减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继建立动态链表n=n+1n==1head=p1p2

next=p1真假(把p1所指结点作为第一个结点)(把p1所指结点连接到表尾)p2=p1(p2移到表尾）再开辟一个新结点，使p1指向它读入一个学生数据给p1所指结点表尾结点的指针变量置NULL开辟一个新结点，并使p1,p2指向它读入一个学生数据给p1所指向的结点head=NULL,n=0当读入的p1

num不是零算法分析程序实现#include<stdio.h>#include<stdlib.h>#defineNULL0#defineLENsizeof(structstudent)structstudent{intnum;floatscore;structstudent*next;};//声明结点类型intn;//n为全局变量，用于存储链表中结点的个数structstudent*creat(void)//定义函数，此函数返回一个指向链表头的指针{structstudent*head,*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);//开辟一个新单元scanf(“%d,%f”,&p1

num,&p1

score);//输人第1个学生的学号和成绩head=NULL;while(p1

num!=0){n=n+1;if(n==1)head=p1;elsep2

next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf(“%d,%f”,&p1

num,&p1

score);//输人其他学生的学号和成绩}p2

next=NULL;return(head);}输出链表（遍历）p=head，使p指向第一个结点

输出p所指向的结点p=p

next当p指的不是表尾算法分析假真p指向的不是尾结点程序实现voidprint(structstudent*head)//定义print函数

{structstudent*p;//在函数中定义structstudent类型的变量pprintf("\nNow,These%drecordsare:\n",n);p=head;//使p指向第一个结点

if(head!=NULL)//若不是空表

do{printf("%d%5.1f\n",p->num,p->score);//输出一个结点中的学号与成绩

p=p->next;//p指向下一个结点

}while(p!=NULL);//当p不是“空地址”

}不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系删除结点

算法分析程序实现structstudent*del(structstudent*head,intnum){structstudent*p1,*p2;if(head==NULL)//若是空链表{printf(“\nlistnull!\n”);return(head);;}p1=head;//使p1指向第一个结点

//p1指向的不是所要找的结点且后面还有结点while(num!=p1

num&&p1

next!=NULL){p2=p1;p1=p1

next;}//p1后移一个结点

if(num==p1

num)//若找到了{if(p1==head)//若p1指向的是首结点,把第二个结点地址赋予headhead=p1

next;else//否则将下一结点地址赋给前一结点的指针项p2

next=p1

next;printf(“delete:%d\n”,num);n=n-1;}//结点数减1else//若找不到该结点

printf(“%ldnotbeenfound!\n”,num);return(head);}将一个结点插入到已有的链表中。插入操作不应破坏原链接关系；插入的结点应该在它该在的位置插入结点

算法分析否程序实现structstudent*insert(structstudent*head,structstudent*stud){structstudent*p0,*p1,*p2;p1=head;//使p1指向第一个结点p0=stud;//p0指向要插入的结点if(head==NULL)//原来的链表是空表{head=p0;p0

next=NULL;}//使p0指向的结点作为头结点else{while((p0

num>p1

num)&&(p1

next!=NULL))

{

p2=p1;//使p2指向刚才p1指向的结点p1=p1

next;}

//p1后移一个结点if(p0

num<=p1

num)

{

if(head==p1)head=p0;

//插到原来第一个结点之前elsep2

next=p0;//插到p2指向的结点之后p0

next=p1;}

else{p1

next=p0;p0

next=NULL;}//插到最后的结点之后}n=n+1;//结点数加1return(head);}主函数voidmain(){structstudent*head,*stu;intdel_num;printf("inputrecords:\n");head=creat();//调用create函数，创建链表print(head);//调用print函数，输出链表printf(“\n输入要删除的学号:");scanf("%d",&del_num);//输入要删除的学号

while(del_num!=0)//可以多次删除，直到输入的学号等于0为止

{head=del(head,del_num);//调用del函数，删除相应的结点

print(head);printf("输入要删除的学号:");scanf("%d",&del_num);}printf(“\n输入要插入的学生信息:");stu=(structstudent*)malloc(LEN);//创建新节点scanf(“%d,%f”,&stu->num,&stu->score);//输入要插入的学生信息

while