结构体和共同体2

1、课程c语言一日一学第门课一结构体与共用体11.7用指针处理链表11.7.1链表概述链表是一种常见的重要的数据结构，是动态地进行存储分配的一种结构。链表的组成: 头指针：存放一个地址，该地址指向一个元素结点：用户需耍的实际数据和链接节点的指针head124913561475用结构体建立链表：code:struct studentint num：float score；struct student *next ；英中成员num和score用來存放结点中的冇用数据（用户需要用到的数据）,next是指针类型的成员, 它指向struct student类型数据（这就是next所在的结构体类型）num10

2、1011010310107score89. 59085next11.7.2简单链表code:#include <stdio.h>#define null 0 struet studentlong num;float score;struct student *next;；main ()struct student a,b,cr *head,*p;a num=99101; a.score=89 5;b num=99103; b score=90;c. num=99107; c.score=85;head=&a;anext=&b;b.next=&c;c next

3、=null;p=head;doprintf (,f%ld %5 . ifnfl, p->num,p->score);p=p->next;)while(p!=null);运行结果：code:1010189.51010390.01010785.0程序分析：开始时使head指向a结点，a.next指向b结点,b.next指向c结点,这就构成链表关系。“c.next=null” 的作用是使c.next不指向任何冇用的存储单元。在输出链表时耍借助p,先使p指向a结点，然后输出a 结点中的数据，up=p->next,*是为输出下一个结点作准备。p->next的值是b结点的地址

4、，因此执行 “p=p->next”后p就指向b结点，所以在下一次循坏吋输出的是b结点中的数据。11.7.3处理动态链表所需的函数库函数捉供动态地开辟和释放存储单元的冇关两数：(1) malloc 函数其函数原型为code:void *malloc(unsigned int size);其作用是在内存的动态存储区中分配一个长度为size的连续空间。此两数的值(即“返回值”)是一个指向 分配域起始地址的指针(类型为void)。如果此函数未能成功地执行(例如内存空间不足)，则返冋空指 针(null)ocalloc函数其两数原型为void *calloc (unsigned n , unsign

5、ed size)淇作用是在内存的动态存储区中分配n个长 度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，返回null。用calloc两数可以为一维数组开辟动态存储空间，n为数组元素个数，毎个元素长度为size(3) free 函数其两数原型为void free (void *p)淇作用是释放由p指向的内存区，使这部分内存区能被其他变戢使用。 p是最近一次调用calloc或malloc函数时返i口【的值。free函数无返冋值.以前的c版木提供的malloc和calloc函数得到的是指向字符型数据的指针。ansi c提供的malloc和 calloc函数规定为void

6、类型。11.7.4建立动态链表所谓建立动态链表是指在程序执行过程中从无到冇地建立起一个链表，即一个一个地开辟结点和输入各结 点数据，并建立起前后相链的关系例11.5写一函数建立一个有3名学生数据的单向动态链表.算法如图开辟一个新结点，并使p1.p2指向它读入一个学生数据给p1所指的结点head = null,n = 0当读入的pl anu m不是零n = n+ 1head = pl (把pl所指 的结点作为 第一个结点)p2 >next = pl (把pl所指 的结点连接 到表尾p2 = pl （p2移到表尾）再开辟一个新结点，使p1指向它读入一个学生数据给pl所指结点表尾结点的指针变量

7、置n ull算法的实现：我们约定学号不会为零，如果输入的学号为0,则表示建立链表的过程完成，该结点不应连接到链表中。如果输入的p1->num不等于0,则输入的是第一个结点数据(n=1),令head=p1,即把p1的值赋给 head,也就是使head也指向新开辟的结点p1所指向的新开辟的结点就成为链表中第一个结点head(n = l)算法的实现：再开辟另一个结点并使p1指向它，接着输入该结点的数据.pl(a)(n-2)pl(b)(n切算法的实现：再开辟一个结点并使p1指向它，并输入该结点的数据.(b)算法的实现：再开辟一个新结点，并使p1指向它，输入该结点的数据。由于p1->num的

8、值为0,不再执行循环，此 新结点不应被连接到链表中.(a)(b)建立链表的两数如下：code:#include <stdio.h>#include <malloc.h>#define null 0 /令null代表0,用它表示“空地址#define len sizeof (struct student)/令 len 代表 struct /student 类型数据d勺长度struct studentlong num;float score;struct student *next; ； int n; /n为全局变说，本文件模块中各函数均可使用它struct student

9、 *creat ()struct student *head;struct student *pl,*p2;n=0;pl=p2=( struct student*) malloc(len);scanf (f,%ldr %f n, &pl->numz &pl->score);head=null;while(pl->num!=0)n=n+l;if (n=l)head=pl;elsep2->next=pl;p2=pl;pl= (struct student*)malloc(len);scanf%f,f z &pl->num, &pl-&g

10、t;score);p2->next=null;11.7.5输出链表首先要知道链表第一个结点的地址，也就是要知道head的值。然后设一个指针变量p,先指向第一个结 点，输出p所指的结点，然后使p后移一个结点，再输出，直到链表的尾结点。p=head使瞒向第-个触m假输岀p所指丽结点p指向下-个结点当p指向的不是表尾headnulnul例11.9编写一个输出链表的函数print.code:void print (struet student *head)struct student *p;printf(hnnow,these %d records are:nh,n);p=head;if (he

11、ad!=null)doprintf (,f%ld %5 ifnn, p->num, p->score);p=p->next;while(p!=null);11.7.6对链表的删除操作从一个动态链表中删去一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离开來，只要 撤销原来的链接关系即可。例门.10写一函数以删除动态链表中指定的结点.解题思路：从p指向的第一个结点开始，检查该结点中的num值是否等于输入的要求删除的那个学号。如果相等就 将该结点删除，如不相等，就将p后移一个结点，再如此进行下去，直到遇到表尾为止。可以设两个指针 变量p1和p2,先使p1指向第一个结点.如

12、果要删除的不是第一个结点，则使p1后移指向下一个结点（将 p1->next赋给p1）,在此之前应将p1的值赋给p2 ,使p2指向刚才检査过的那个结点注意：要删的是第一个结点（p 1的值等于h e a d的值，如图1 1-20 （ a ）那样），则应将p 1 -> n e x t赋给h e a do这时h e a d指向原来的第二个结点。第一个结点虽然仍存在，但它已与链表脱离，因 为链表中没冇一个结点或头指针指向它。虽然p 1还指向它，它仍指向第二个结点，但仍无济于事，现在 链表的第一个结点是原來的第二个结点，原來第一个结点已“丢失”，即不再是链表中的一部分了。 如果要删除的不是第一

13、个结点，则将p l->n e x t赋给p 2->n e x t，见图1 120（d）. p 2->n e x t原来指向p 1指向的结点（图中第二个结点），现在p 2->n e x t改为指向p 1 -> n e x t 所指向的结点（图中第三个结点）。p 1所指向的结点不再是链表的一部分。还需要考虑链表是空表（无结点）和链表中找不到要删除的结点的诸况。1010(op2(d)算法:输出当numhpl >num以及pl所指的结点不是表尾结点'空表”p2 = pl （p2后移一个位置）p1 = p1 >next （pl后移一个位置）p1是要删除的

14、结点是否是p1所指是头结点head = p 1 >next(删除头结点)p2 >next = p >next (删除个结点)输出“找不到”的信息删除结点的两数del:code:struct student *del(struct student *headzlong num) struct student *plz *p2;if (head=null)printf (flnlist null!nfl);goto end;pl=head;while(num!=pl->num && pl->next!=null)p2=pl;pl=pl->next

15、;if(num=pl->num)if (pl=head)head=pl->next;elsep2->next=pl->next;printf (,fdelete:%ldnf,z num);elseprintf (,f%ld not been found! nf, num);end;return (head);11.7.7对链农的插入操作对链表的插入是指将一个结点插入到一个已有的链表屮。为了能做到正确插入，必须解决两个问题： 怎样找到插入的位置； 怎样实现插入。先用指针变量po指向待插入的结点，p1指向第一个结点将po->num与p1->num相比较，如果po

16、->num >p1-> num ,则待插入的结点不应插在p1所指的结点之前。此时将p1后移，并使p2指向刚才p1所指 的结点再将p1->num与po->num比，如果仍然是po->num大，则应使p1继续后移,直到po->p1-> num 为止。这时将po所指的结点插到p1所指结点之前。但是如果p1所指的已是表尾结点，则p1就不应后移 / o如果p0-> num比所冇结点的num都大，贝9应将po所指的结点插到链衣末尾。如果插入的位置既不 在第一个结点之前，乂不在表尾结点之后，则将po的值赋给p2->next,使p2->next

17、指向待插入的结点， 然后将p1的值赋给po->next,使得po->next指向p1指向的变量lp,算法:p 1 = head po = s t ticl来的 杏将po所 指的结点 作为惟一 结点当po >num>p 1 anum 以及 pl所扌旨的不足表尼结点向 pl 位:st卩1向后移一个结点po 一 >n ti m wp 1 >n u rn一fia1 tfr |nj 头纟电aj&否p i >ncxt = po po >ne xt = n u l丄 (插到表尾之后h c a <1 = po po >ne xt=pl(插到农

18、头之的p2 一 >ncxt=popo >>ncx t=pl(mi到衣中 |wj>n = n + w11.11插入结点的函数insert如下。code:struet student *insert(struct student *head, struct student *stud)struct student *p0,*pl,*p2;pl=head;po=stud;if (head=null)head=po;po->next=null;elsewhile(po->num>pl->num) &&!=null)p2=pl;pl=pl-

19、>next;if (po->num<=pl->num)if(head=pl)head=po;else p2->next=po; po->next=pl;elsepl->next=po; po->next=null;n=n+l;return(head);void main()struct student *headz stu;long del_num; prinf (rrintput records : n");head=creat ();print(head);printf (” n intput the deleted number:

20、 nrr); scant (rr%ldr,/ &del_num) ;head=del (head, del_num); print(head);printf (” n intput the deleted number: nrr); scanf (n%ldr, &stu num, &stu score);head=insert(head,&stu);print(head);此程序运行结果是正确的。它只删除一个结点，插入一个结点。但如果想再插入一个结点，重复写上程 序最后4行，共插入两个结点，运行结果却是错误的。code:input records：（建立链表）1

21、0 101 ,90 /10 103 ,98 /10 105 ,76 /0 ,0 ,/now,these3records are：10 1 0 1 9 0 010 1 0 3 9 8 010 1 0 5 7 6 0intput the deleted number : 10103 (删除)delete： 10 103znow,these 4 records are：10 1 0 1 9 0 010 1 0 5 7 6 0input the inserted record (插入第一个结，点)10102, 90/now,these 3records are：10 1 0 1 9 0 010 1 0

22、 2 9 0 010 1 0 5 7 6 . 0input the inserted record (插入第二个结点)10104, 99/now,these 4records are：10 10190010 10499 .010 10499010 10499 .0出现以上结果的原因是：stu是一个冇固定地址的结构体变戢。第一次把stu结点插入到链表中，第二次若再用它来插入第二个结 点，就把第一次结点的数据冲掉了，实际上并没有开辟两个结点。为了解决这个问题，必须在每插入一个 结点时新开辟一个内存区。我们修改main函数，使之能删除多个结点（直到输入要删的学号为0）,能插 入多个结点（直到输入要插

23、入的学号为0）。code:main ()struct student *head,*stu;long del_num;printf(ninput records:nm);head=creat();print (head);printf(hninput the deleted number:h); scanf (fl%ldl,z &del_num);while (del_num!=0)head=del(head,del_num);print (head);printf (,finput the deleted number: h; scanf (fl%ld,f z &del_nu

24、m);printf(”ninput the inserted record:m; stu= (struct student *) malloc(len);scanf (,%ldz %f hz &stu->numz &stu->score);while(stu->num!=0)head=insert(head,stu);printf(ninput the inserted record:n);scanf(n%ld,%f&stu->num,&stu->score);stu定义为指针变量，在需要插入时先用malloc函数开辟一个内存区，将英起始地址经强制类型转换后 赋给stu,然后输入此结构体变戢中各成员的值。对不同