计算机软件技术基础 数据结构与算法（3）.

Presentation on theme: "计算机软件技术基础 数据结构与算法（3）."— Presentation transcript:

1 计算机软件技术基础 数据结构与算法（3）

2 数据结构研究的内容

3 2.3 栈和队列 2.3.1 栈（Stack） 2.3.2 队列（Queue） 1. 定义 1. 定义 2. 逻辑结构 2. 逻辑结构
3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式

4 2.3.1 栈 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 即栈顶
栈 1. 定义 限定只能在表的一端进行插入和删除运算的线性表。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构 与线性表相同，仍为一对一( 1:1)关系。 用顺序栈或链栈存储均可，但以顺序栈更常见 只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则。 关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。 基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。

5 栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶; 表头(即 a1 端)称为栈底。
例如： 栈 S= (a1 , a2 , a3 , ……….,an-1 , an ) a1称为栈底元素 an称为栈顶元素 插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈。 强调：插入和删除都只能在表的一端（栈顶）进行！ 想一想：要从栈中取出a1，应当如何操作？

6 Q1：堆栈是什么？它与一般线性表有什么不同？
堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 一般线性表 堆栈 逻辑结构：1: 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出 “进”＝插入=压入=PUSH（an+1) “出”＝删除=弹出=POP(an)

7 Q2：顺序表和顺序栈的操作有何区别？ 栈顶top 以线性结构 S= (a1 , a2 , …. , an-1 , an )为例 a1 a2
ai an …… 顺序表S a1 a2 …… an 顺序栈S ai 栈底 栈顶top 表头 表尾 低地址 高地址 S[i] an+1 低地址 高地址 写入：S[i] = ai 读出：e = S[i] 压入(PUSH): S[top++] = an+1 弹出( POP) : e = S[--top] 前提：一定要预设栈顶指针top

8 顺序栈S 栈顶top an+1 an ai …… a2 栈底 a1 栈为空的条件 ：top＝0;
低地址 高地址 an+1 栈底 栈顶top 栈为空的条件 ：top＝0; 栈满的条件 ： top = MAXSIZE;

9 Q3：为什么要设计堆栈？它有什么独特用途？
调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。 下面用2个例子来帮助理解堆栈：

10 例1：一个栈的输入序列为1、2、3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？
答： 可以通过穷举所有可能性来求解： ① 1入1出， 2入2出，3入3出， 即123； ② 1入1出， 2、3入，3、2出， 即132； ③ 1、2入，2出， 3入，3、1出， 即231； ④ 1、2入，2、1出，3入3出， 即213； ⑤ 1、2、3入，3、2、1出， 即321； 合计有5种可能性。

11 顺序栈的存储表示（教材76） #define MAXSIZE 100 //栈的最大容量
typedef char ElemType; //数据元素为字符型 typedef struct { ElemType Stack[MAXSIZE]; //利用数组存储栈的元素 int top; //栈顶指针 }SeqStack;

12 顺序栈入栈函数Push( ) 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） A B A C B A top D top C top
高地址M A B A C B A top D top C top B top A 低地址L top 核心语句： top=L; 顺序栈入栈函数Push( ) viod Push(ElemType e) { if (top>M){上溢} else s[top++]=e; } Push (A); Push (B); Push (C); Push (D);

13 顺序栈出栈操作——例如从栈中取出‘B’ D C B A top D C B A top top D C A B D C B A top
低地址L 高地址M D C B A top top D C A B D C B A top 核心语句： Pop ( ); 顺序栈出栈函数POP( ) Elemtype Pop( ) { if(top=L) { 下溢 } else { e=s[--top]; return(e);} } Pop ( ); Printf( Pop () );

14 链栈的表示 栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈。 链栈的构造方式— 以头指针为栈顶，在头指针处插入或删除。
设链式栈的栈顶指针为 top，指向位于栈顶的结点： data next ┌─┬─┐ top ─→│B │││栈顶 └─┴┼┘ data next ↓ ┌─┬─┐ ┌─┬─┐ top＝NULL top ─→│A │∧│ 栈顶 │A │∧│栈底 └─┴─┘(栈底) └─┴─┘ (1) 置为空栈 (2) 压入元素 A之后 (3) 压入元素 B之后

15 3.3.2 队列 队列定义 逻辑结构 存储结构 运算规则 实现方式 尾部插入 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
队列 队列定义 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 首部删除 存储结构 运算规则 实现方式 逻辑结构 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作：入队或出队，建空队列，判队空或队满等操作。

16 问：为什么要设计队列？它有什么独特用途？
队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（FIFO）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 队首 队尾 在队尾插入元素称为入队；在队首删除元素称为出队。 问：为什么要设计队列？它有什么独特用途？ 答： 离散事件的模拟（模拟事件发生的先后顺序）； 操作系统中的作业调度（一个CPU执行多个作业）； 3. 简化程序设计。

17 1.链队列 因简单而先介绍 链队列类型定义： 关于整个链队的总体描述 typedef struct {
Qnode *front ; //队首指针 Qnode *rear ; //队尾指针 } LinkQueue; 关于整个链队的总体描述 链队中任一结点的结构 结点类型定义： typedef Struct QNode{ QElemType data; //元素 Struct QNode *next; //指向下一结点的指针 }Qnode;

18 rear Q p front ^ ^ ^ 链队示意图： a1 a2 a3 (队首) (队尾) 讨论： 空链队的特征？ front=rear
S D ^ 讨论： 空链队的特征？ front ^ rear front=rear ② 链队会满吗？ 一般不会，因为删除时有free动作。除非内存不足！ ③ 怎样实现链队的入队和出队操作？ 完整操作函数见教材P93 入队（尾部插入）：rear->next=S; rear=S; 出队（头部删除）：front->next=p->next;

19 front rear e 顺序队示意图： 讨论： a1 a2 a3 data a4 Q ① 空队列的特征？ 约定：front=rear
用base做数组名 顺序队示意图： 讨论： a1 a2 a3 data a4 . 99 Q front ① 空队列的特征？ 约定：front=rear (队首) ② 队列会满吗？ 极易装满！因为数组通常有长度限制，而其前端空间无法释放。 (队尾) rear 队尾后地址 e ③ 怎样实现入队和出队操作？核心语句如下： 有缺陷 假溢出！ 入队(尾部插入)： Q[rear]=e; rear++ ; 出队(头部删除)： e=Q[front]; front++;

20 1 2 3 循环队列（臆造） 顺序队列 N-1 1 2 3 front . a1 a2 front a1 a3 rear rear a2
1 2 3 N-1 rear front 循环队列（臆造） 顺序队列 a3 a2 a1 front rear 1 2 3 . N-1 新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！ 解决方案： 浪费一个单元，则队满特征可改为front=(rear+1)%N；

21 循环队列的入队和出队操作 队列表示 Element Q[n]; int front=0, rear=0; 入队算法
if (front == (rear+1)%n) /* 队列满 */ else { Q[rear] = x; rear = (rear+1)%n; } 出队算法 if (front == rear) { /* 空队列 */ } else x = Q[front]; front = (front+1)%n;

22 小 结 线性表、栈、队的异同点： 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO； 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 第3节 结束 ② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。