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

Slides:



Advertisements
Similar presentations
数据结构的引入. 通讯录管理 社团机构管理 校园导航管理 通讯录管理 社团机构管理 校园导航管理.
Advertisements

二级基础知识 第一章 数据结构与算法 全国计算机等级考试. 1.1 算法  一、算法的概念 解决问题准确而完整的描述。  特征:可行性、确定性、有穷性、拥有足够的 情报。  要素:对数据运算操作(算术、逻辑)通过指 令序列程序来实现、算法的控制结构(执行顺 序)。  算法设计方法: 列举法:列举所有可能.
一、算法的基本概念 二、数据结构 三、栈和队列 四、排序方法 五、二叉树
问题的提出: 例1 把十进制整数转换为二至十六之间的任一进制数输出。
数据结构 复 习.
实用数据结构基础 第3章 栈.
第五讲 队列.
第三章 堆疊與佇列的基本應用 3-1 簡介堆疊(Stack) 3-2 迷宮問題研究 3-3 佇列(queue)的介紹
第3章 栈和队列 3.1 栈 3.2 队列 3.3 应用.
第3章 栈和队列.
第6章 佇列(Queues) 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列.
主要内容: 1.第一部分 概述 2.第二部分 线性表、栈、队列
第三章 栈和队列 Stack and Queue
第三章栈和队列 栈 队列 递归.
佇列 (Queue).
佇列與推疊 (Queue and Stack)
資料結構 第5章 佇列.
数据结构.
第十章 基本数据结构 链表结构 栈结构 队列结构 主讲:李祥 时间:2015年10月.
Chap 3 堆疊與佇列 Stack and Queue.
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
第3章 顺序存储结构的表、堆栈和队列 3.1 顺序存储结构 3.2 表和顺序表 3.3 堆栈和顺序堆栈 3.4 队列和顺序队列
Ch.3 栈和队列 黄刘生 中国科学技术大学计算机系 国家高性能计算中心(合肥)
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
线性表小结 元素之间的线性关系 顺序表 顺序表:元素相邻存储 单链表:后继指针链接 一维数组 给定下标随机存取
本 章 说 明 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队 列 本 章 小 结 返回主目录.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
第3章 栈和队列(二) 1/.
第三章 栈和队列 栈和队列是两种重要的数据结构。
第3章 栈和队列 丽水学院工学院.
1、栈及其实现 2、栈的应用 3、队列及其实现 4、优先级队列 5、链式队列 6、队列应用
第3章 堆栈和队列 堆栈 堆栈应用 队列 队列应用 优先级队列 主要知识点.
Chapter 6 队列(QUEUES).
第三章 栈与队列 £3.1 栈 £3.3 队列 £3.2 栈的应用举例 £3.1.1 栈的定义 £3.1.2 栈的顺序存储结构
指针与引用 概念 指针从本质上讲就是存放变量地址 的一个变量,在逻辑上是独立的,它可以被改变,包括其所指向的地址的改变和其指向的地址中所存放的数据的改变。 引用是一个别名,它在逻辑上不是独立的,它 的存在具有依附性,所以引用必须在一开始就被初始化,而且其引用的对象在其整个生命周期中是不能被改变的(自始至终只能依附于同一个变量)。
第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列.
第3章 栈和队列(一).
第三章 栈和队列.
数据结构 Data Structure 中南大学 主讲人:王国军,郑瑾 中南大学信息院计科系
資料結構與C++程式設計進階 堆疊與佇列(Stack & Queue) 講師:林業峻 CSIE, NTU 6/ 21, 2010.
第一章 绪论.
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
第3章 栈和队列 3.1 栈 本章主题:栈和队列的应用 教学目的:掌握栈和队列的应用方法,理解栈的重要作用
数 据 结 构 刘家芬 Sept 2012.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
第三章 栈和队列.
資料結構 第4章 堆疊.
严蔚敏、吴伟民编著 清华大学出版社 学习网站:
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
数据结构概论 第3章 栈和队列 董黎刚 浙江工商大学信电学院 2019年2月25日.
第四章 栈和队列 4.1栈 4.2栈的应用 4.3队列 4.3队列应用.
第三章 栈和队列 第二部分 队列(Queue) 2019/4/8.
顺序表的删除.
数据结构习题课 信息学院 赵明 2005年秋.
队列及其实现.
Chap2 Stack & Queue.
单链表的基本概念.
第 四 讲 线性表(二).
第 六 讲 栈和队列(一).
本章的基本内容是: ⑴栈和队列的定义及操作特性; 第3章 特殊线性表—栈、队列和串 ⑵栈和队列的两种存储方法和基本运算的实现;
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
第七讲 栈和队列(二) 1/.
第3章 栈和队列 3.1 栈 3.2 队列.
Chapter 2 Entity-Relationship Model
第三章 栈和队列.
昆山爱达人信息技术有限公司 QQ: 本节内容 1.栈的链式存储结构及实现 2.栈的应用.
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
13-1 電腦可以協助解決哪些問題 13-2 電腦解題簡介 13-3 電腦解題規劃-演算法 13-4 認識資料結構
Presentation transcript:

计算机软件技术基础 数据结构与算法(3)

数据结构研究的内容

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

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

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

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

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

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

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

例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种可能性。

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

顺序栈入栈函数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);

顺序栈出栈操作——例如从栈中取出‘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 () );

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

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

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

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

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;

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++;

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;

循环队列的入队和出队操作 队列表示 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;

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