第十三章__链表操作.ppt

本章目标 动态存储分配 链表的结点结构 建立一个简单单向链表 动态存储分配与内存释放 链表的特点 链表补充内容(双向链表) 1.双向链表的定义及特点 2.双向链表的建立 3.双向链表的插入 4.双向链表的删除 (resource/sample_13/example_4.c) 课后练习 创建两个链表a,b,.每个链表中的结点包括学号,成绩.要求把两个链表合并,按学号升序排列 第十三章 链 表 操 作 魏华吉 理解动态存储分配 理解链表 掌握动态链表的操作 (建立,输出、插入和删除) 由程序员控制的存储分配方法，根据需要临时分配内存单元以存放有用数据，当不用时，又可以释放存储单元，以便其用于分配给其它数据使用 链表 链表是动态进行存储分配的一种结构。若干数据(每个数据组称为一个结点)按一定的原则连接起来 链表的逻辑结构 在链表中，用一个专门的指针HEAD指向链表中第一 个数据元素的结点（即存放第一个数据元素的存储 结点的序号）。链表中最后一个元素后面已没有结 点元素，因此，链表中最后一个结点的指针域为空 结点结构体类型的定义 在C语言中，定义链表结点结构的一般形式如下： struct 结构体名 { 数据成员表； struct 结构体名 *指针变量名； }； 定义结点： struct student { long num; float score; struct student *next; }a,b,c,*head; 建立链表： head=a; a.next=b;b.next=c; c.next=0; 动态分配函数 格式：void *malloc(size) 功能：分配成功则返回相应内存的入口地址 p=(struct stu *)malloc(sizeof(struct stu)) 内存释放函数 格式：void free(void *block) 例如：free(p) 1.链表所占内存区大小不固定,各结点在内存中的次序可以是任意的 2.链表每一个结点内必须包括一个指针项,指向下一结点 3.必须用malloc函数动态开辟单元,且开辟的结点只能用指针方法访问 4.单向链表的访问只能从头指针开始,顺序进行 5.单向链表最后一个结点的指针项必须是NULL 6.若断开链表中某一个结点,其后的所有结点虽在内存中存在,但无法访问 h=(struct stu *)malloc(sizeof(struct stu)); h-next=NULL; p=(struct stu *)malloc(sizeof(struct stu)); p-next=h.next; h-next=p; h 动态链表的建立与输出 struct stu { int num; float score; struct stu *next; } *p,*h; ∧ A ∧ p h ∧ A p h ∧ B 动态链表的插入 ∧ B A C p h q q=(struct stu *)malloc(sizeof(struct stu)); q-next=p-next; p-next=q; 动态链表的删除 q=p-next; p-next=q-next; free(q) a c d b e a c d b e p q