第3章_1线性结构.ppt

西安交通大学 计算机教学实验中心 2013 * 插入操作和删除如何进行？ 插入？ 【思考题】老师领着的小朋友的队伍中，如果有一个同学要加入到队伍中（插入新结点），该如何操作？ 删除？ 【思考题】老师领着的小朋友的队伍中，如果队伍中有一个同学要离开（删除结点），又该如何操作？ 西安交通大学 计算机教学实验中心 2013 * 插入操作 ① 找到第i-1个结点的指针p。 ② 建立新结点s，在新结点的指针域中保存第i个结点的地址。 ③ 第i-1个结点的指针域保存新结点的地址。 西安交通大学 计算机教学实验中心 2013 * 删除操作 ① 如果第i个结点存在，则找到第i个结点和第i-1个结点的指针p和q。 ② 将第i+1个结点的指针保存到第i-1个结点的指针域中，这样就可以将第i个结点从链表中断开。 ③ 释放第i个结点所占的空间。 西安交通大学 计算机教学实验中心 2013 * （2）其它形式的链表 单向循环链表 将单链表尾结点的指针由NULL改为指向头结点，首尾连接形成一个环形，简称为单循环链表 西安交通大学 计算机教学实验中心 2013 * （2）其它形式的链表 双向链表 每个结点的指针域中再增加一个指针，使其指向该结点的直接前趋结点 这样构成的链表中有两个不同方向的链 西安交通大学 计算机教学实验中心 2013 * （2）其它形式的链表 双向循环链表 将双向链表的头结点的前趋指针指向尾结点 将尾结点的后继指针指向头结点。 西安交通大学 计算机教学实验中心 2013 * 3. 什么是栈？ 定义 栈是仅在一端进行插入和删除操作的特殊线性表； 这一端称为栈顶，另一端称为栈底。 特点： 后进先出 西安交通大学 计算机教学实验中心 2013 * 栈的结构 西安交通大学 计算机教学实验中心 2013 * 栈的主要操作与应用 主要操作 建空栈。 入栈 ：在栈顶加入新的元素。 出栈 ：将栈顶元素删除。 读栈顶元素：只读出栈顶元素，但不出栈。 问题：若进栈序列为1，2，3，4，且进栈过程中可以出栈，则不可能的出栈序列是（ ？ ）。 (A) 1，4，3，2 (B) 3，1，4，2 (C) 2，3，4，1 (D) 3，4，2，1 栈的应用 括号匹配检查、引号匹配检查、表达式求解、树和图的遍历、递归算法等。 西安交通大学 计算机教学实验中心 2013 * 汉诺塔问题 汉诺塔又称河内塔，汉诺塔问题源于印度一个古老传说的益智玩具。 “上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。 上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。” 西安交通大学 计算机教学实验中心 2013 * 汉诺塔问题的计算 据专家推导：移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。 真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭了。 f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，平均每 18446744073709551615584554049253.855年 西安交通大学 计算机教学实验中心 2013 * 4. 什么是队列 西安交通大学 计算机教学实验中心 2013 * 什么是队列 在日常生活中 体育课排队、会议进场排队 买票排队、上车排队 看病排队、参观排队 取钱要排队、交钱要排队 喝水排队 吃饭排队 排队时要遵守的原则 后来的人只能排在队伍的后面(增加元素)不能插队 排在前面的人得到服务后就可以离开了（删除） 先进来的先出去 西安交通大学 计算机教学实验中心 2013 * 什么是队列 定义 队列是只能在一端进行插入操作、在另一端进行删除操作的特殊线性表。 允许删除元素的一端称为队头，允许插入元素的一端称为队尾。 特点： 先进先出 西安交通大学 计算机教学实验中心 2013 * 队列的主要操作 判断队列是否满。 判断队列是否为空。 入队：在队尾插入元素。 出队：在队头删除元素。 取队头元素，但不出队。 队列在计算机中的应用 进程管理、打印作业管理、通信管理、遍历算法等 队列如何存储？ 小结问题 1.以相同的概率查找长度为n的顺序表中的数据，问平均查找长度是多少？当概率不同的时候呢？能写出一般公式吗？ 2.有一队列，经过如下操作后，队列的状态是怎样的，画出示意图，标明哪是队头，哪是队尾？出队的元素是什么？ ①开始队列为空； ②入队数据A、E、F、B、C； ③做两次出队操作； ④入队H 3.