C语言程序设计_李学刚_电子课件14单元5 构造类型程序设计_链表.ppt

《C语言程序设计_李学刚_电子课件14单元5 构造类型程序设计_链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.7链表主讲人张静常州信息职业技术学院2、掌握链表的建立、插入和删除算法3、能利用链表编写应用程序4、能够独立思考编写代码，并基本熟练在VC6.0环境下进行程序的调试和测试知识/能力目标1、了解动态存储分配和链表的基本概念（一）动态存储分配我们把由程序员控制存储分配方法，根据需要临时分配存储单元用以存放有用的数据，当数据不用时又可以随时释放存储单元的过程称为动态存储分配。一、动态存储分配及链表的概念数组的特点2．向数组中插入或删除一个元素时，该元素后的所有元素都要向后或向前移动，增加了对内存的访问量；且当数据无用时，不能及时释放存储空间为其他变量所用；1．系统为数组分配一片连续

2、的存储空间；对数组元素的访问非常方便，只要指定其下标就可以；3．用数组存放数据时，必须事先定义固定的长度，在某些情况下可能会出现比较严重的内存浪费现象。一、动态存储分配及链表的概念（二）链表链表能够弥补数组存在的上述缺陷。0012FF20H03101李晗……0012FF32H03102王丽丽……0012FF5CH03108吴婷……NULLhead0012FF20H0012FF32H0012FF5CH头指针，存放开始结点的地址开始结点（头结点）尾结点，指针域为空数据区，存放本结点的数据指针区，指向下一结点结点图5-16一个简单的单向链表typedefstructnode{charn

3、um[10];charname[20];…structstudentnext;}NODE;（一）分配内存空间malloc()函数二、用于动态存储分配的函数调用形式(类型说明符)malloc(size)作用在内存的动态存储区开辟一块长度为size个字节的连续区域。若成功分配，则函数的返回值为该区域的首地址，否则返回空指针。示例longp；p=(long)malloc(8)；把开辟的8个字节的存储空间转换为long型，并把该空间的起始地址赋给指针变量p，使p指向该空间。（二）realloc()函数二、用于动态存储分配的函数调用形式(类型说明符)realloc(指针变量ptr,size

4、)作用将指针变量ptr指向的存储空间（用malloc()分配的）的大小改为size个字节。说明当用函数malloc()分配的存储空间的大小需要改变时，使用该函数。（三）calloc()函数二、用于动态存储分配的函数调用形式(类型说明符)calloc(n,size)作用在内存的动态存储区开辟n个大小为size个字节的连续区域。若成功分配，则函数的返回值为该区域的首地址，否则返回空指针。示例structstudentstu[30]；stu[0]=(structstudent)calloc(30,sizeof(structstudent))；把申请的30sizeof(structstu

5、dent)个字节的存储空间转换为structstudent结构体类型并赋给结构体指针数组元素stu[0]，使stu[0]指向开辟的存储空间的首地址。（四）free()函数二、用于动态存储分配的函数调用形式free(指针变量ptr)作用释放指针变量ptr指向的存储空间。示例structstudentp；p=(structstudent)malloc(sizeof(structstudent))；………free(p)；ANSIC标准要求在使用动态存储分配函数时，要在程序的前面使用编译预处理命令#include"stdlib.h"，还有许多编译系统是使用命令#include"alloc

6、.h"。（一）链表的建立1．头插法建不带头结点的单链表三、链表的建立、插入和删除sahead(1)将头指针置为NULL(2)生成一个新结点S(3)将结点的值写入数据域(4)将head的值写入结点的指针域(5)将新结点的地址s赋给head(6)重复(2)-(5),建立多个结点^说明：头插法建立的单链表结点的次序与数据输入的次序相反，即最先输入的是链表的尾结点，最后输入的是链表的开始结点。scheada^bLinkListCreatListF(void){//返回单链表的头指针DataTypech;LinkListhead;//头指针ListNodes;//工作指针head=NULL

7、;//链表开始为空printf("请输入链表各结点的数据(字符型):");while((ch=getchar())!=''){if((s=(ListNode)malloc(sizeof(ListNode))==NULL){printf("不能分配内存空间!");exit(0);}s->data=ch;s->next=head;head=s;}returnhead;}算法实现2．尾插法建带头结点的单链表sa(1)建立一个头结点，将头指针和指向尾结点的指针指向头结点(2)生成