[其它考试]第11章结构体链表new.ppt

1. 链表概述 1) 动态数据结构概念 数组和结构体是定长数据结构 链表是连成一行的数据项集合，每一个数据 项(元素)称为结点，可以在链表中的任意位置进 行结点插入或删除操作，使链表数据项的个数随 之增加或减少。 用指针处理链表 * 2) 链表的构成 单向链表图示： 0701 89.5 0702 90 0703 85 head 其中： ? head是指针变量，存放链表的头指针； ?各结点是相同的结构体类型，该类型有三个成员； ?各结点应包含一个指针成员存放下一结点的地址； ?各结点存储有可能不连续，但各结点逻辑上连续。 1048 1370 2800 1370 2800 NULL 1048 首结点 结点 尾结点 头指针 * 3) 结点的构成 上图每个结点具有如下结构体类型： struct student { int num; float score; struct student *next; }; 其中： ?成员num、score用于存放一个结点的具体数据； ?成员next是指针类型，用于存放下一结点地址， 最后一个结点的next 成员存放空指针NULL； ?成员next是指向与自身同一类型的结构，这种结 构称为自引用结构。(只有指针成员可自引用) * struct student { int num; 　 float score; 　 struct student *next; }a,b,c; 10101 89.5 10103 90 10107 85 a b c a.next=b; b.next=c; num score next 建立简单的静态链表 NULL c.next=NULL; head head=a; 例建立一个如图所示的简单链表，它由3个学生数据的结点组成，要求输出各结点中的数据。 10101 89.5 10103 90 10107 85 a结点 b结点 c结点 num score next 解题思路： 10101 89.5 10103 90 10107 85 a结点 b结点 c结点 num score next head head=a; a.next=b; b.next=c; NULL c.next=NULL; #include stdio.h struct student { int num; float score; struct student *next; }; void main() { struct student a,b,c,*head,*p; a. num=10101; a.score=89.5; b. num=10103; b.score=90; c. num=10107; c.score=85; head=a; a.next=b; b.next=c; c.next=NULL; } 10101 89.5 10103 90 10107 85 a结点 b结点 c结点 num score next head NULL p p p p=NULL;结束 printf(“%ld%5.1f\n”,p-num,p-score); p=p-next; p=head; while(p!=NULL) { } 课堂练习 求出前面建立的链表中所有结点成绩的平均值. 建立动态链表 所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。 * 0701 89.5 0702 90 0703 85 head 1048 1370 2800 1370 2800 NULL 1048 NULL 建立动态链表 例： 写一函数建立一个有3名学生数据的单向动态链表。 * struct Student { int num; float score; struct student *next; }; #define LEN sizeof(struct Student) 定义3个指针变量：head,p1和p2，它们都是用来指向struct Student类型数据 struct Student *head,*p1,*p2; * head保存头结点的地址 p1保存新创建结点的地址 p2保存尾结点的地址 0701 89.5 0702 90 0703 85 head 1048 1370 2800