C程序设计第四版Chap9(链表)-谭浩强

1、第第9 9章章 结构体结构体9.1 9.1 结构体类型结构体类型9.2 9.2 结构体变量定义及成员引用结构体变量定义及成员引用9.3 9.3 结构体变量的初始化结构体变量的初始化9.4 9.4 结构体数组结构体数组9.5 9.5 结构体指针结构体指针9.6 9.6 单向链表概念单向链表概念9.7 9.7 单向链表建立、查找、遍历、插入、删除单向链表建立、查找、遍历、插入、删除9.8 typedef9.8 typedef定义类型别名定义类型别名单向链表概念单向链表概念 链表是一种常见的重要数据结构(Data Structure)。它动态进行存储空间分配。 数组的大小需要事先确定。定小了，存储空

2、间不够用；定大了，浪费空间；而链表可以根据链表可以根据实际需要进行动态地伸缩实际需要进行动态地伸缩。 数组在中间插入、删除一个元素时的处理开销较大，而链表可以高效处理插入、删除链表可以高效处理插入、删除。 单向链表概念单向链表概念 例子：例子：1249A1356B1475C1021DNULLhead1249135614751021单向链表概念单向链表概念 链表有一个“头指针”变量，一个链表使用“头指针”来标识。“头指针”为NULL时表示空链表。 链表的每个元素称为“结点”，它由实际元素数据和指向下一结点的指针两部分组成。最后一个节点指向NULL，表示链表的尾部。 要访问每个元素，必须从“头指针

3、”开始，一个一个地访问结点，直至找到所要访问的结点。单向链表概念单向链表概念 例例 结点表示的例子 struct student int num; double score; struct student *next; ;单向链表概念单向链表概念 这里讨论的链表是单向链表。 除此之外，还有双向链表，单向循环链表，双向循环链表等。第第9章章 结构体结构体9.1 9.1 结构体类型结构体类型9.2 9.2 结构体变量定义及成员引用结构体变量定义及成员引用9.3 9.3 结构体变量的初始化结构体变量的初始化9.4 9.4 结构体数组结构体数组9.5 9.5 结构体指针结构体指针9.6 9.6 单向链

4、表概念单向链表概念9.7 9.7 单向链表建立、查找、遍历、插入、删除单向链表建立、查找、遍历、插入、删除9.8 typedef9.8 typedef定义类型别名定义类型别名单向链表建立单向链表建立 在程序运行过程中，使用malloc函数一个一个地申请每个结点所需的空间，并加入到链表中。单向链表建立单向链表建立 例例 动态建立包含动态建立包含n n个学生数据的链表，输出这些个学生数据的链表，输出这些学生的信息。学生的信息。单向链表建立单向链表建立 例例 方法：方法： 1.建立空链表，head=NULL 2.申请结点所需空间，输入学生信息 3.将结点放到链表的尾部或头部 4.重复第2步和第3步，

5、直至输入结束 单向链表建立单向链表建立 例例struct student struct student int num; int num; double score; double score; struct student struct student * *next; next; ; #include #include 单向链表建立单向链表建立 例例struct studentstruct student* * create( ) / create( ) /添加在尾部添加在尾部，返回头指针，返回头指针 struct student struct student * *head=NULL,h

6、ead=NULL,* *p,p,* *tail;tail;p=tail=(struct studentp=tail=(struct student* *)malloc(sizeof(struct student);)malloc(sizeof(struct student);scanf(%d%lf,&p-num,&p-score);scanf(%d%lf,&p-num,&p-score);while (p-num)while (p-num) if (head=NULL) head=p; else tail-next=p;if (head=NULL) head=p

7、; else tail-next=p; tail=p; tail=p;p=(struct studentp=(struct student* *)malloc(sizeof(struct student);)malloc(sizeof(struct student); scanf(%d%lf,&p-num,&p-score); scanf(%d%lf,&p-num,&p-score); tail-next=NULL; free(p);tail-next=NULL; free(p); return head; return head; 单向链表建立单向链表建立 例

8、例struct studentstruct student* * create( ) / create( ) /添加在头部添加在头部，返回头指针，返回头指针 struct student struct student * *head=NULL,head=NULL,* *p;p;p=(struct studentp=(struct student* *)malloc(sizeof(struct student);)malloc(sizeof(struct student);scanf(%d%lf,&p-num,&p-score);scanf(%d%lf,&p-num,&a

9、mp;p-score);while (p-num)while (p-num) p-next=head;head=p; p-next=head;head=p;p=(struct studentp=(struct student* *)malloc(sizeof(struct student);)malloc(sizeof(struct student); scanf(%d%lf,&p-num,&p-score); scanf(%d%lf,&p-num,&p-score); free(p); free(p); return head; return head; 单向

10、链表查找、遍历单向链表查找、遍历查找：确定某个值的节点是否存在遍历：从头到尾逐个查看节点单向链表查找单向链表查找 例例 int found(struct studentint found(struct student* * head,int number) head,int number) while (head)while (head) if (head-num=number) return 1; if (head-num=number) return 1; head = head-next;head = head-next; return 0; return 0; 单向链表遍历单向链表遍历

11、 例例void print(struct studentvoid print(struct student* * head) head) while (head)while (head) printf(%dt%5.1fn,head-num, printf(%dt%5.1fn,head-num, head-score); head-score);head = head-next;head = head-next; 单向链表的删除操作单向链表的删除操作被删除节点的位置： - 第一个节点 - 中间节点 - 最后一个节点 单向链表的删除操作单向链表的删除操作 例例 struct studentstru

12、ct student* * del(struct student del(struct student* * head) head) struct student struct student * *tmp;tmp;if (head=NULL) if (head=NULL) printf(n list null!n); return head; printf(n list null!n); return head; tmp = head;tmp = head;head = head-next; head = head-next; free(tmp); free(tmp);return head

13、;return head; 单向链表的删除操作单向链表的删除操作 例例 struct studentstruct student* * del(struct student del(struct student* * head,int num) head,int num) struct student struct student * *p1,p1,* *p2;p2;if(head=NULL) if(head=NULL) printf(n list null!n); return head; printf(n list null!n); return head; p1=head;p1=head

14、;while (num!=p1-num & p1-next)while (num!=p1-num & p1-next) p2=p1;p1=p1-next; p2=p1;p1=p1-next; if (num=p1-num) if (num=p1-num) if (p1=head) head=p1-next; else p2-next=p1-next;if (p1=head) head=p1-next; else p2-next=p1-next; printf(delete: %dn,num); printf(delete: %dn,num); free(p1);free(p1)

15、; else printf(%d not found!n,num); else printf(%d not found!n,num); return head;return head; 单向链表的插入操作单向链表的插入操作要插入节点的位置： - 头部 - 中间 - 尾部 单向链表的插入操作单向链表的插入操作 例例 struct studentstruct student* * insert(struct student insert(struct student* * head,int number) head,int number) struct student struct student

16、 * *tmp=malloc(sizeof(struct tmp=malloc(sizeof(struct student); student); tmp-num = number; tmp-next = NULL; tmp-num = number; tmp-next = NULL;if (head=NULL) return head = tmp;if (head=NULL) return head = tmp;tmp-next = head;tmp-next = head;head = tmp;head = tmp; return head; return head; 单向链表的插入操作单

17、向链表的插入操作 例例struct studentstruct student* * insert(struct student insert(struct student* * head,struct student head,struct student* * ps) ps) struct student struct student * *p1=head,p1=head,* *p2;p2;ifif (head=NULL) head=ps; ps-next=NULL; (head=NULL) head=ps; ps-next=NULL; elseelse while (ps-num p1-num & p1-next)while (ps-num p1-num & p1-ne