第8章 链表与动态空间管理.pptxVIP

董卫军;;;程序内存储空间的分配与管理;栈区：由编译器自动分配与释放，主要用于存放函数的参数，局部变量等对象的值。;数据段：由只读数据段、已初始化的读写数据段和未初始化段三部分组成。;2.静态和动态存储方式;⑵动态存储方式

动态存储方式指在程序运行期间根据需要进行动态的分配存储空间的方式。程序运行时在动态存储区为其分配空间。;⑴静态存储分配;inta=0;全局初始化在数据区

char*p1;全局未初始化在数据区

voidmain()

{intb,s[10],*p2;局部在栈

staticintc=0；局部（静态）在数据区

p1=(char*)malloc(20);20字节的区域在堆

?

};数据区：保存全局变量和静态变量等对象

栈区：保存调用函数的动态变量等对象

堆区：保存动态生成的变量等对象;;动态空间的申请与释放;格式：

void*malloc(unsignedsize)；;double*p;

p=(double*)malloc(10*sizeof(double))；;;free()函数用于释放由malloc()函数申请的内存空间，被释放的空间通常被送入可用存储区池。

格式：

voidfree(void*p)；;例如：;malloc()函数是用于动态申请存储区。

free()函数是释放已经不用的存储区域。

由这两个函数就可以实现对“堆区”进行动态分配及管理。

注意：使用malloc()和free()函数时，必须包含头文件malloc.h。;;链表的概念;链存储结构由一系列结点组成，结点可以在程序运行时动态申请获得。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储相关结点地址的链域。;链域;2.结点的定义;单链表;循环链表;在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。;链表是通过利用指向链表的第一个结点的“头指针”访问整个链表中的结点。

链表的最后一个结点的链域通常被设置为NULL。

链表中的每一个结点都是需要时申请，不需要时释放。

链表的结点只有一个指针域，则可以形成单链表。若有两个指针域，则可以形成双链表。;4.链表的创建;尾插法建表：将新结点插到当前链表的表尾上。为此需增加一个尾指针变量r，使之始终指向当前链表的表尾结点。;例：用尾插法建立带表头的单链表,实现人员记录。;;;voidmain()

{ intnumber;/*保存人数的变???*/

structnode*head;

number=N;

head=creat(number);

?

free(head);

};动态申请空间打破了先定义再使用的限制。

链表结点是需要时申请，不需要时释放。;;1.元素的查询;structnode

{ intnum;/*num为关键字*/

?

structnode*link;

};;;2.结点的删除;双链表中删除结点方法;例：设计一个函数，实现在带表头的单链表中删除某个元素，其结点结构如下，关键字为num。;两种情况：

①要删除的结点是头指针所指的结点则直接操作；

②不是头结点，要依次往下找。

另外要考虑：空表和找不到要删除的结点的情况。;需要两个临时指针：

一个用于判断指向的结点是不是要删除的结点，如：s指针;

另一个始终指向s的前面一个结点,如：p：指针。;;;通过前面的查找和删除操作介绍，应注意以下两点：

在单链表上查找元素、删除结点，应设置临时指向结点类型的指针，用于遍历结点时记录。

链表不具有按序号随机访问的特点，只能从头指针开始一个一个顺序进行。;;链表结点的插入;s;s;a1;例：设计一个函数，实现在带表头的单链表中插入一个结点，其结点结构如下：;;;3.插入原则

①插入操作不应破坏原链接关系；

②插入的结点应该在它该在的位置。;需要两个或三个临时指针：

一个用于指向待插的结点，如：s指针

另两个用于指向要插入结点处的前后结点,如：p、q指针