链表课件讲解.pptx

;学习目标;主要内容;8.2链表;例如：

char*pc;

pc=(char*)malloc(100);

表示开辟100个字节的内存空间

开辟空间的首地址强制转换为“char*”型

注意：malloc()函数并不能初始化所分配的内存空间，开辟的内存空间一般都是随机数;2.开辟内存空间函数calloc()

函数原型为：

void*calloc(int,int);

一般调用形式：

(类型说明符*)calloc(n,size);

功能：在内存动态存储区中分配n块长度为size字节的连续内存区域；

返回值：开辟区域的首地址；“(类型说明符*)”用于函数返回值的强制类型转换;calloc()函数与malloc()函数的区别

?calloc()一次可以分配n块区域，每块区域的长度都为size个字节。

例如：structstu*ps;

ps=(structstu*)calloc(2,sizeof(structstu));

sizeof(structstu)是求structstu型结构体数据的长度

功能：按structstu的长度分配2块连续的内存区域，并将该内存区域的首地址强制转换为structstu结构体指针类型，并将该地址赋给指针变量ps。;calloc()函数与malloc()函数的区别

?calloc()函数会将所开辟内存空间中的每一位都初始化为零，malloc()函数并不能初始化所分配的内存空间。

为字符类型或整数类型的元素分配内存，那么这些元素将保证会被初始化为0

为指针类型的元素分配内存，那么这些元素通常会被初始化为空指针NULL

为实型数据分配内存，则这些元素会被初始化为浮点型的零;3.释放内存空间函数free()

该函数的调用形式：

free(ptr);

功能：释放指针变量ptr所指向的内存空间，该空间是由malloc()或calloc()函数开辟的。

;二.链表简介;头指针;结点结构体类型定义如下

structnode //结点类型名

{

chardata; //数据域

structnode*next; //指针域

};

如存储学生相关的信息的结点定义

structStuNode

{

charnum[10]; //学号

charname[20]; //姓名

floatscore; //分数

structStuNode*next; //指针域

};;对链表的基本操作有建立链表、输出链表、查找结点、插入结点和删除结点等。

1.建立链表

建立单向链表的主要步骤：读取数据、申请存放新结点的存储空间、将数据存入结点空间、将新结点添加到链表中，重复上述操作直至结束。;2.输出整个链表

输出整个链表即从链表??头指针开始，按顺序依次访问链表中的各个数据结点，每访问到一个数据结点时就将该结点数据域中的内容输出。当访问到链表中的最后一个结点时，由于其指针域为空，所以可依此作为条件结束输出。;【例8-9】建立并输出一个学生数据的单向链表。学生数据包括：学号、姓名和成绩。

;3.查找结点

从链表的头指针开始，按顺序依次访问链表中的各个数据结点，查找关键字与当前结点数据域中内容,相等则查找成功，输出；如不等则移动指针查看下一结点。如访问到最后一个结点时仍未找到，则结束查找，提示不存在。;4.插入结点

开辟新结点用指针s指向，并将要插入的数据data存入新结点空间的数据域中，插入过程如图;5.删除结点

删除结点必须先查找到该结点及其直接前驱结点，并分别用指针指向，删除过程如图。删除后free(s)回收被删除结点的内存空间