语言程序设计链表课件.ppt

《语言程序设计链表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§11.7用结构体指针处理链表一、链表概述链表是一种最常见的数据结构，它动态地进行存储分配。数组：必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。链表有单向链表、双向链表、环形链表等形式。以单向链表为例、链表有一个“头指针”head，它指向链表的第一个元素。链表的一个元素称为一个“结点”（node）。结点中包含两部分内容，第一部分是结点数据本身，如图中的Ａ、Ｂ、Ｃ

2、、Ｄ所示。结点的第二部分是一个指针，它指向下一个结点。最后一个结点称为“表尾”，表尾结点的指针为空（NULL）。在链表中插入一个结点，比如，在结点Ａ后插入结点P，只需使Ｐ指向Ｂ，使Ａ指向Ｐ。在链表中删除一个结点，比如删除结点C，只需使Ｂ指向Ｄ，并删除结点C所占内存。因此，链表的插入、删除非常方便。链表结点数据可以用结构体来描述，例如、structstudent　　　　　{　　　　　　int　num;　　　　　　floatscore;　　　　　　structstudent*next;/*指向下一结点*/　　　　　}；链表需要动态地进行存储分配，在Ｃ语言中，使用以下函数进行动

3、态存储分配和释放。1、void*malloc(size_tsize)　在动态存储区分配长度为size的连续空间，并返回指向该空间起始地址的指针。若分配失败（系统不能提供所需内存），则返回NULL。2、void*calloc(size_tn,size_tsize)　　在动态存储区分配n个长度为size的连续空间，并返回指向该空间起始地址的指针。若分配失败（系统不能提供所需内存），则返回NULL。3、voidfree(void*ptr)　　释放ptr指向的内存空间。ptr是malloc()或calloc()函数返回的值。注意、（１）上述函数的原型在alloc.h和stdlib.h

4、中定义。在程序中必须包含这两个头文件。（２）size_t是专用于描述内存大小和计数值的数据类型，等于unsignedint。二、建立链表[例11.7]　写一个函数creat()，建立一个有5个学生的单向链表。分析建立过程：设：链表结构为：　　　　structstudent　　　　{　　　　　long　num;　　　　　floatscore;　　　　　structstudent*next;　　　　};当输入的num等于零时，表示建立过程结束。定义以下变量：　　　structstudent*head;/*表头*/　　　structstudent*p1;　/*新建结点*/

5、　　　structstudent*p2;　/*表尾结点*/通过以上分析，可以得到创建链表的算法，其中，n=1表示创建的是第一个结点。程序：#include"stdio.h"#include"alloc.h"#include"stdlib.h"structstudent{　long　num;　floatscore;　structstudent*next;　};#defineLENsizeof(structstudent)/*注意，"#defineNULL0"不需要，因为，NULL已在stdio.h中定义*/intn;structstudent*creat()/*创建链

6、表，并返回表头指针*/{　structstudent*head;/*表头*/　structstudent*p1;　/*新建结点*/　structstudent*p2;　/*表尾结点*/n=0;/*结点数为0*/　head=NULL;/*还没有任何结点，表头为指向空*/　p1=(structstudent*)malloc(LEN);/*创建一个新结点p1*/　p2=p1;/*表尾p2也指向p1*/scanf("%ld,%f",&p1->num,&p1->score);/*读入第一个结点的学生数据*/while(p1->num!=0)/*假设num=0表示输入结束*/　

7、{　　n=n+1;　　if(n==1)head=p1;　　/*第一个新建结点是表头*/　　else　　　　p2->next=p1;/*原表尾的下一个结点是新建结点*/p2=p1;/*新建结点成为表尾*/p1=(structstudent*)malloc(LEN);/*新建一个结点*/　　scanf("%ld,%f",&p1->num,&p1->score);/*读入新建结点的学生数据*/　}free(p1);/*对于num=0的结点，未加入链表，应删除其空间