《C语言新教材PPT课堂课件-补充-链表》由会员分享，可在线阅读，更多相关《C语言新教材PPT课堂课件-补充-链表（41页珍藏版）》请在金锄头文库上搜索。
1、补补补补充充充充1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.1 1.1 链链表表概概述述 链表是一种常见的重要的数据结构,是动态地进行存储分配的一种结构。链表的组成：头指针：存放一个地址，该地址指向一个元素 结点：用户需要的实际数据和链接节点的指针图11 1 1 1用用用用指指指指针针针针处处处处理理理理链链链链表表表表 用结构体建立链表：struct student int num； float score； struct student *next ；; 其中成员num和score用来存放结点中的有用数据（用户需要用到的数据），next是指针类型的成员，它
2、指向struct student类型数据（这就是next所在的结构体类型）图21 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.2 1.2 简简单单链链表表 #include #define NULL 0 struct student long num; float score; struct student *next; ; main() struct student a,b,c,*head,*p; a. num=99101; a.score=89.5; b. num=99103; b.score=90; c. num=99107; c.score=85; hea
3、d=&a; a.next=&b; b.next=&c; c.next=NULL; p=head; do printf(%ld %5.1fn,p-num,p-score); p=p-next; while(p!=NULL); 运运行行结结果果：99101 89.599103 90.099107 85.0 1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表程序分析： 开始时使head指向a结点，a.next指向b结点，b.next指向c结点，这就构成链表关系。“c.next=NULL” 的作用是使c.next不指向任何有用的存储单元。在输出链表时要借助p，先使p指向a结点，然
4、后输出a结点中的数据，“p=p-next” 是为输出下一个结点作准备。p-next的值是b结点的地址，因此执行“p=p-next”后p就指向b结点，所以在下一次循环时输出的是b结点中的数据。1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.31.3处处理理动动态态链链表表所所需需的的函函数数 库函数提供动态地开辟和释放存储单元的有关函数：(1)malloc函数其函数原型为void *malloc(unsigned int size);其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的值（即“返回值”）是一个指向分配域起始地址的指针（类型为void
5、）。如果此函数未能成功地执行（例如内存空间不足），则返回空指针(NULL)。 1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 (2) calloc函数 其函数原型为void *calloc（unsigned ，unsigned size）;其作用是在内存的动态存储区中分配个长度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，返回NULL。 用calloc函数可以为一维数组开辟动态存储空间，n为数组元素个数，每个元素长度为Size。1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 (3) free函数 其函数原型为vo
6、id free（void *p）;其作用是释放由指向的内存区，使这部分内存区能被其他变量使用。是最近一次调用calloc或malloc函数时返回的值。free函数无返回值。 以前的版本提供的malloc和calloc函数得到的是指向字符型数据的指针。 ANSI 提供的malloc和calloc函数规定为void类型。 1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.4 1.4 建建立立动动态态链链表表 所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系例 写一函数建立一个有3名学生数据的单向动
7、态链表。算法如图图31 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 算法的实现： 我们约定学号不会为零，如果输入的学号为，则表示建立链表的过程完成，该结点不应连接到链表中。 如果输入的p1-num不等于，则输入的是第一个结点数据（n=1），令headp1，即把p1的值赋给head，也就是使head也指向新开辟的结点p1所指向的新开辟的结点就成为链表中第一个结点图41 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 算法的实现： 再开辟另一个结点并使p1指向它，接着输入该结点的数据.如果输入的p1-num，则应链入第个结点（n=2), 将新结点的地
8、址赋给第一个结点的next成员.接着使，也就是使指向刚才建立的结点图51 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 算法的实现：再开辟一个结点并使p1指向它，并输入该结点的数据。在第三次循环中，由于（），又将的值赋给-，也就是将第个结点连接到第个结点之后，并使，使指向最后一个结点.图6 1 1 1 1 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 算法的实现： 再开辟一个新结点，并使p1指向它，输入该结点的数据。由于p1-num的值为，不再执行循环，此新结点不应被连接到链表中.将NULL赋给p2-next.建立链表过程至此结束，p1最后所指的结点未链入链
9、表中，第三个结点的next成员的值为NULL，它不指向任何结点。图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/n为为全全局局变变量量，本本文文件件模模
10、块块中中各各函函数数均均可可使使用用它它用用用用指指指指针针针针处处处处理理理理链链链链表表表表 struct student *creat() struct student *head; struct student *p1,*p2; n=0; p1=p2=( struct student*) malloc(LEN); scanf(%ld,%f,&p1-num,&p1-score); 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
11、); scanf(%ld,%f,&p1-num,&p1-score); p2-next=NULL; return(head);用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.5 1.5 输输出出链链表表 首先要知道链表第一个结点的地址，也就是要知道head的值。然后设一个指针变量p,先指向第一个结点，输出所指的结点，然后使后移一个结点，再输出，直到链表的尾结点。 图8,9用用用用指指指指针针针针处处处处理理理理链链链链表表表表 例例 编编写写一一个个输输出出链链表表的的函函数数print.print. void print(struct student *head) struct
12、 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); 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.6 对对链链表表的的删删除除操操作作 从一个动态链表中删去一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离开来，只要撤销原来的链接关系即可。图10用用用用指指指指针针针针处处处处理理理理链链链链表表表表 例例 写写一一函函数数以以删删除除动动态态链链表
13、表中中指指定定的的结结点点. .n 解题思路: 从p指向的第一个结点开始，检查该结点中的num值是否等于输入的要求删除的那个学号。如果相等就将该结点删除，如不相等，就将p后移一个结点，再如此进行下去，直到遇到表尾为止。用用用用指指指指针针针针处处处处理理理理链链链链表表表表 可以设两个指针变量p1和p2，先使p1指向第一个结点 。 如果要删除的不是第一个结点，则使p1后移指向下一个结点(将p1-next赋给p1)，在此之前应将p1的值赋给p2 ，使p2指向刚才检查过的那个结点 。用用用用指指指指针针针针处处处处理理理理链链链链表表表表 注意： 要删的是第一个结点（的值等于的值，如图1-0（）那
14、样），则应将-赋给。这时指向原来的第二个结点。第一个结点虽然仍存在，但它已与链表脱离，因为链表中没有一个结点或头指针指向它。虽然还指向它，它仍指向第二个结点，但仍无济于事，现在链表的第一个结点是原来的第二个结点，原来第一个结点已“丢失” ，即不再是链表中的一部分了。用用用用指指指指针针针针处处处处理理理理链链链链表表表表 注意： 如果要删除的不是第一个结点，则将-赋给-，见图1（）。-原来指向指向的结点（图中第二个结点），现在-改为指向-所指向的结点（图中第三个结点）。所指向的结点不再是链表的一部分。还需要考虑链表是空表（无结点）和链表中找不到要删除的结点的情况。用用用用指指指指针针针针处处处
15、处理理理理链链链链表表表表 图11 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 算法：图12 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 删删除除结结点点的的函函数数del:del:struct student *del(struct student *head,long num) struct student *p1,*p2; if (head=NULL)printf(nlist null!n);goto end; p1=head; while(num!=p1-num & p1-next!=NULL) p2=p1;p1=p1-next;if(num=p1-num)
16、 if(p1=head) head=p1-next; else p2-next=p1-next; printf(delete:%ldn,num); n=n-1; else printf(%ld not been found!n,num);end;return(head); 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 1.71.7对对链链表表的的插插入入操操作作 对链表的插入是指将一个结点插入到一个已有的链表中。为了能做到正确插入，必须解决两个问题： 怎样找到插入的位置； 怎样实现插入。用用用用指指指指针针针针处处处处理理理理链链链链表表表表 先用指针变量p0指向待插入的结点，p1
17、指向第一个结点。将p0-num与p1-num相比较，如果p0-nump1- num ，则待插入的结点不应插在p1所指的结点之前。此时将p1后移，并使p2指向刚才p1所指的结点。用用用用指指指指针针针针处处处处理理理理链链链链表表表表 再将p1-num与p0-num比,如果仍然是p0-num大，则应使p1继续后移，直到p0-p1- num为止。这时将p0所指的结点插到p1所指结点之前。但是如果p1所指的已是表尾结点，则p1就不应后移了。如果p0- num比所有结点的num都大，则应将p0所指的结点插到链表末尾。 如果插入的位置既不在第一个结点之前，又不在表尾结点之后，则将p0的值赋给p2-nex
18、t，使p2-next指向待插入的结点，然后将p1的值赋给p0-next，使得p0-next指向p1指向的变量。 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 如果插入位置为第一个结点之前(即p1等于head时)，则将p0赋给head，将p1赋给p0-next如果要插到表尾之后，应将p0赋给p1-next，NULL赋给p0-next图13 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 算法：图14 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 例例 插插入入结结点点的的函函数数insertinsert如如下下。 struct student *insert(s
19、truct student *head, struct student *stud)struct student *p0,*p1,*p2; p1=head;p0=stud; if(head=NULL) head=p0; p0-next=NULL;elsewhile(p0-nump1-num) & (p1-next!=NULL) p2=p1; p1=p1-next; if(p0-numnum) if(head=p1) head=p0; else p2-next=p0; p0-next=p1; else p1-next=p0; p0-next=NULL; n=n+1; return(head);
20、用用用用指指指指针针针针处处处处理理理理链链链链表表表表 11.7.8 11.7.8 对对链链表表的的综综合合操操作作 将将以以上上建建立立、输输出出、删删除除、插插入入的的函函数数组组织织在在一一个个C C程程序序中中，用用函函数数作作主主调调函函数数。 void main() struct student *head,stu;long del_num; prinf(intput records:n) ; head=creat();print(head);printf ( n intput the deleted number:n); scanf (%ld,&del_num) ;head=d
21、el(head,del_num);print(head);printf ( n intput the deleted number:n); scanf (%ld,&stu.num,&stu.score) ;head=insert(head,&stu);print(head); 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 此此程程序序运运行行结结果果是是正正确确的的。它它只只删删除除一一个个结结点点，插插入入一一个个结结点点。但但如如果果想想再再插插入入一一个个结结点点，重重复复写写上上程程序序最最后后4 4行行，共共插插入入两两个个结结点点，运运行行结结果果却却是是错错误误的的。
22、Input recordsInput records：（建建立立链链表表）1010，1010，1010，用用用用指指指指针针针针处处处处理理理理链链链链表表表表 Now,these 3 records are：101010101010 intput the deleted number ：10103 （删除）：1010Now,these 4 records are：10101010 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 input the inserted record （插入第一个结点）1010210102，9090Now,these 3 records are：1010
23、10101010input the inserted record （插入第二个结点）1010410104，9999Now,these 4 records are：1010101010101010 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 出出现现以以上上结结果果的的原原因因是是： stu是一个有固定地址的结构体变量。第一次把stu结点插入到链表中，第二次若再用它来插入第二个结点，就把第一次结点的数据冲掉了，实际上并没有开辟两个结点。为了解决这个问题，必须在每插入一个结点时新开辟一个内存区。我们修改main函数，使之能删除多个结点（直到输入要删的学号为0），能插入多个结点（直到
24、输入要插入的学号为0）。 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 main() struct student *head,*stu; long del_num;printf(input records:n); head=creat(); print (head); printf(ninput the deleted number:); scanf(%ld,&del_num); while (del_num!=0)head=del(head,del_num);print (head);printf (input the deleted number:);scanf(%ld,&d
25、el_num); printf(ninput the inserted record:);stu=(struct student *) malloc(LEN); scanf(%ld,%f,&stu-num,&stu-score); while(stu-num!=0)head=insert(head,stu); printf(input the inserted record:);stu=(struct student *)malloc(LEN); scanf(%ld,%f,&stu-num,&stu-score); 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 stu定义为指针变量
26、，在需要插入时先用malloc函数开辟一个内存区，将其起始地址经强制类型转换后赋给stu，然后输入此结构体变量中各成员的值。对不同的插入对象，stu的值是不同的，每次指向一个新的struct student变量。在调用insert函数时，实参为head和stu，将已建立的链表起始地址传给insert函数的形参，将stu（即新开辟的单元的地址）传给形参stud，返回的函数值是经过插入之后的链表的头指针（地址） 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 运运行行结结果果： ：10，10，10， ， ：10 10 10 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 int
27、put the deleted number 10103 （删除）：1010Now,these 4 records are1010 9 91010 intput the deleted number 10103 （删除）：10105 5Now,these 4 records are1010 9 9 用用用用指指指指针针针针处处处处理理理理链链链链表表表表 intput the deleted number:0input the inserted record 1010410104，8787Now,these 3 records are10101 99.010101 99.010104 8710104 87 input the inserted record 1010610106，6565Now,these 3 records are10101 99.010101 99.010104 8710104 8710106 65.0 10106 65.0
