第十一讲 链表.ppt

用结构体指针处理链表 一、链表概述 链表是一种最常见的数据结构，它动态地进行存储分配。 数组：必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。 链表有单向链表、双向链表、环形链表等形式。以单向链表为例、 链表有一个“头指针”head，它指向链表的第一个元素。 链表的一个元素称为一个“结点”（node）。结点中包含两部分内容，第一部分是结点数据本身，如图中的Ａ、Ｂ、Ｃ、Ｄ所示。结点的第二部分是一个指针，它指向下一个结点。 最后一个结点称为“表尾”，表尾结点的指针为空（NULL）。 在链表中插入一个结点，比如，在结点Ａ后插入结点P，只需使Ｐ指向Ｂ，使Ａ指向Ｐ。 在链表中删除一个结点，比如删除结点C，只需使Ｂ指向Ｄ，并删除结点C所占内存。 因此，链表的插入、删除非常方便。 链表结点数据可以用结构体来描述，例如、 　　　　　struct student　　　　　{　　　　　　int 　num;　　　　　　float score; /* 指向下一结点 */　　　　　　struct student *next; 　　　　　} ； 链表需要动态地进行存储分配，在Ｃ语言中，使用以下函数进行动态存储分配和释放。 1、void * malloc(size_t size)　 2、void * calloc(size_t n, size_t size) 3、void free(void * ptr) 　　 二、建立链表 　写一个函数creat()，建立一个有5个学生的单向链表。 分析建立过程： 设：链表结构为：　　　　struct student　　　　{　　　　　long　num;　　　　　float score;　　　　　struct student *next;　　　　}; 当输入的num等于零时，表示建立过程结束。 定义以下变量：　　　struct student *head; /* 表头 */　　　struct student *p1;　 /* 新建结点 */　　　struct student *p2;　 /* 表尾结点 */ 通过以上分析，可以得到创建链表的算法，其中，n=1表示创建的是第一个结点。 应考虑以下情况： １、找到需要删除的结点，用p1指向它。并用p2指向p1的前一个结点。 ２、要删除的结点是头结点。 ３、要删除的结点不是头结点 根据以上情况分析，得到删除一个结点的算法： 2、将p0插入第一个结点之前 3、将p0插入表尾结点之后 4、找到应插入的位置 　应插入的位置：p1之前、p2之后。 　在链表中，各结点按成员num（学号）由小到大顺序存放，从第一个结点开始，把待插入结点p0-num与每一个结点p1-num比较，若(p0-num) (p1-num)，则p1移到下一个结点。同时，p2也移到下一个位置。 根据以上分析，得出插入算法：