课程名称数据结构07

1、课程名称 数据结构07 授课题目链式线性结构 环行链表授课日期2003 年 10 月 8 日授课班级生物医学工程授课时数4授课方式理论课授课重点、难点1. 掌握链式表的定义与特点2. 掌握链式栈的操作要点3. 掌握链式队列的操作要点4. 掌握向前链表的几种常用操作5. 掌握环行链表的操作要点授课内容、教具与时间分配授课内容、教具与时间分配2.2 几种链接表2.2.0 链接式线性表一、 定义：如果线性表中逻辑上相邻的元素在计算机中物理存储位置不一定相邻，而是用指针相链接的结点序列，这种线性表称为链接式线性表。 优点：1. 当进行插入或删除操作时，避免了大量元素的移动。 2. 若事先不容易估计表长

2、时，链接式线性表可节省内存。 二、链接式线性表的结点成员 struct node xxxx info link 数据域 链域 char info; 三、申请结点和释放结点 struct node *link; typedef struct node NODE; NODE *ptr;ptr=(NODE *)mallc(sizeof(NODE);/*ptr=NULL 表示栈满，即内存用完，很少发生*/free(ptr); /*调用 I/O 库函数 free ，ptr 是指向待释放结点的指针*/四、主要操作：不同的结构有不同的操作2.2.1 链接式栈 p38 top一、 图解 实际上就是 p17 的

3、单向链表，仅画法不同。 当 top=NULL，称为栈空。初值 top=NULL。 栈顶指针 二、入栈操作：1. 申请结点 ptr=(NODE *)malloc(sizeof(NODE) 初值为 （图解） 2. 数据域赋值 ptr->info=arg 3. 结点链入栈 ptr->link=top : 4. 提升栈顶指针 top=ptr :三、出栈操作：1. 保留原栈顶指针 ptr=top : （图解） 2. 下降栈顶指针 top=ptr->link 3. 提取原栈顶数据 var=ptr->info 4. 释放结点 free(ptr) 四、对p.38 lstack.c 的说

4、明 1. #include "llist" 编译预处理。 2. main() 中有二个循环语句 入栈：当遇到 'n' ，循环终止。可不考虑栈满，即内存用完。 出栈：当栈空，top=NULL ，循环终止。3. 定义外部指针变量 top ，供 push(arg) 和 pop() 共享。 NODE *top=NULL; /*赋初值*/4. 入栈函数 push(arg) 执行入栈操作。5. 出栈函数 pop() 执行出栈操作。6. 执行 输入：abcde 输出：edcba 。2.2.2 链接式排队(队列） p39一、定义 队首 队尾 同 p30二、主要操作：入队、出

5、队和判断队列空。三、实现方法： 1. 链接式排队 图解 front rear 队首指针 front 指向队首 (顺序式队列有队首标志,是指向队首前的一个位置) 队尾指针 rear 指向队尾2. 队列空 front=rear=NULL 不需要判别队列满四、队列的基本操作1. 入队函数：insert(arg)2. 出队函数：delete()五、链接式队列程序 lqueue.c (40) 的说明1. #include "llist.h" 编译预处理。2. 主程序中包含二个循环语句： 入队：输入一行字符，链成队列，遇 'n' 停止循环。可不考虑队列满。 出队：显示出

6、队字符。遇队列空，停止循环。3. 定义队首、队尾指针，供 insert 和 delete 共享。 NODE *front=NULL,*rear=NULL； /*队首、队尾指针赋初值*/4. 入队函数 insert 图解：链入新数据(1) 申请结点 ptr=(NODE *)malloc(sizeof(NODE)(2) 结点数据域赋值 prt->info=arg(3) 结点链域赋值 ptr->link=NULL(4) 将新申请的结点链入。根据队列是否空，用二种不同的链入方法。 if (front=NULL) front=ptr; /*若队列空*/ else rear->link=

7、ptr; /*队列不空，链入队尾*/(5) 修改队尾指针 rear=ptr; /*队列空或不空*/5. 出队函数 delete 图解：输出队首结点的数据(1) 若是空队列，返回 '0'。(2) 保存队首指针 ptr=front 。(3) 移动队首指针，指向下一个结点 front=ptr->link 。(4) 数据出队 var=ptr->info 。(5) 释放结点 free(ptr) 。(6) 如果删除了最后一个结点,成为空队列，队首指针front=ptr->link为 NULL，队尾指针也应为NULL 。 if (front=NULL) rear=NULL;

8、(7) 返回出队数据 。6. 执行 输入：abcde 输出：abcde 。 2.2.3 向前链表 p41 一、定义 p41 图解 头指针 头结点 第一个结点 head 数据域闲置 链域存放指针，表空链域为NULL二、基本操作有五种： 添加、查找、插入、删除和遍历 。三、对向前链表程序 list.c (p41) 的说明1. #include "llist.h" 编译预处理 。2. NODE *search() ； /* 是在主函数 main 之外说明 */3. 用开关语句选择各种操作 。4. 生成链表函数 init() 图解 键盘输入：abcde e b a 输出显示：edc

9、ba head5. 添加函数 append() 图解 arg 添加在头结点之后6. 查找函数 search() 因为有返回值，调用前要说明。 查找成功，返回结点指针。不成功，返回 NULL 。7. 插入函数 insert(argf,argr) 图解 调用 search ，查找数据域为 argf 的结点，在其后插入 argr 。 插入成功，返回 0 。不成功，返回 -1 。8. 删除函数 delete(arg) 图解 定义二个指针 NODE *ptr1,*ptr2； ptr1 和 ptr2 同步向前扫描每个结点 ptr2=ptr1； ptr1=ptr1->link； 如找到 ptr1-&g

10、t;info=arg；则删除该结点 ptr2->link=ptr1->link； 并释放该结点 free(ptr1)； 删除成功，返回 0 。 找不到 arg ，删除失败，返回 -1 。9. 遍历函数 travel 输入：abcde 输出：edcba2.3 环形链表 p44 图解 生成：如果使向前链表最后一个结点的链指向表头结点，便可得到一个环形链表。 特点：在环形链表中，可以把表头结点作为普通结点存放数据。 标识：用指针 rignt 指向环形链表的右端，标识这个环形链表。right->link 所指的结点是右端。 当 right=NULL ，链表空。 2.3.1 关于环形链

11、表的操作一、程序 circular.c 有五种基本操作。right 的初值为 0 。 左端添加函数 appendl 右端添加函数 appendr 左端删除函数 delete 链反向函数 reverse 遍历函数 travel 二、对环形链表程序p.45 circular.c 的说明1. 主函数 main 调用 init ，生成环形链表 开关语句选择各种操作2. 定义指针 right 为外部变量。3. 生成环形链表函数 init 调用 appendr 右端输入： abcde 调用 travel 左端输出： abcde 先进先出4. 右端添加函数 appendr 调用 appendl， 左端添加；

12、 然后改变 right 指向，相当于右端添加。(图解)5. 左端添加函数 appendl 申请结点， 数据域赋值。 原先是空表，左端添加后自成循环； 原先不是空表，结点入链。(图解)6. 左端删除函数 deletel 原先是空表，return('0')。 原先不是空表，提取左端结点的指针和数据域值。 如果有二个及以上结点，用 right->link=ptr->link，删除左结点。 如果原先只有一个结点，用 right=NULL 删除后成为空链表。(图解) 释放被删结点 返回被删结点数据7. 链表反向函数 reverse 原先是空表，不做反向操作 辅助指针初始定位

13、ptr1=right ，ptr2=right->link。 do 保留指针 ptr=ptr2->link; 反向 ptr2->link=ptr1; 向前移动一个结点 ptr1=ptr2;ptr2=ptr; ptr2 指向的最后一个结点反向后，再同步移到下一个结点， 使 ptr1=right ，停止循环。8. 遍历函数 travel 空表不操作 非空表，从左结点开始，逐个输出结点数据域值。授课内容、教具与时间分配小结、复习、思考题、参考书思考题：1、键入链接式排队程序 p40 lqueue.c ，执行之。2、复制向前链表程序 p41 list.c ，执行之。3、编写函数 insertah 使之能在向前链表已知结点之前插入新结点，把 insertah 加入 ，执行之。4、