当前位置：文档之家 › 数据结构教案第三章

数据结构教案第三章

  • 格式：doc
  • 大小：98.00 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

数据结构教案-详细版-第3章栈和队列教案

数据结构教案-详细版-第3章栈和队列教案

xxxx学院教案首页xxxx学院教案附页第一学时（栈的定义、常用操作与顺序存储的实现）一、情景导入（1）引出栈的概念由线性表引出栈：栈是线性表的一种，只是在操作上，与线性表有所差别。

如果没有道具，借用课本，粉笔盒或学生自主进行展示。

（2）进入主题，讲解栈的特点与线性表进行类比，栈与基础线性表的差别，在于它的操作受限、取数的方式不如线性表自由。

可以结合图3-1中的图示，引导学生回想存取碗时的具体操作，帮助学生领悟栈的特点。

图3-1 一摞碗二、知识讲解（1）栈的特点结合图3-2中栈的结构图，对栈的操作原则——后进先出，进行讲解。

图3-2 栈的结构图（2）栈的常用操作栈的常用操作如下：•创建栈（初始化栈）•判断栈是否为空•进栈•出栈•获取栈顶元素•获取栈的长度•销毁栈在对栈的原则进行讲解之后，对栈中常用操作进行总结。

（3）栈的顺序存储实现栈是线性表的一种，顺序存储的栈是一种顺序表。

在知识点（2）提到的操作中，进栈和出栈是可以展示出栈特点的特色操作，可以结合图示，对这两种操作的实现进行详细说明；此外，简单叙述栈中其余功能的实现方法。

在讲解完顺序栈中的各种操作之后，结合书中例3-1给出的代码，带领学生掌握栈的实现方法。

第二学时（栈的链式存储实现）一、知识回顾（1）对上节课留的作业进行答疑。

（2）回顾总结上节课的内容，引出本节课主题。

上个学时讲解了栈的定义、栈的特点与栈的顺序实现，本学时来探讨栈的链式存储实现。

二、知识讲解（1）链栈的数据结构定义链栈是一种链表，与顺序栈相同，链栈在操作时也受到限制，遵循“后进先出”的原则。

结合链表的数据结构定义，引导学生完成链栈的数据结构定义。

（2）链栈的实现链栈的存储方式与链表相同，操作原则与顺序栈相同。

从这两点出发进行分析，引导学生找到链栈实现的思路，然后给学生留出一定时间，由学生自主分析巩固链栈操作的实现方法，之后结合学生自主实现链栈时遇到的问题，对链栈进行讲解。

（用栈实现四则运算）三、情境引入通过计算机的算术运算功能，引出本学时的主题：计算机的基本功能大多都是基于对数据的操作，给出一个运算式，计算机能迅速计算出结果，若运算时有误，如运算式“1+3*（2+5”，右边少了一个“）”，编绎器会立刻检查出错误并报告，那么计算机是如何做到的呢？藉由以上问题，引出逆波兰表达式。

数据结构教案第三章

数据结构教案第三章
case ‘>’: //新输入的算符c优先级低，即栈顶算符优先权高，
//出栈并将运算结果入栈OPND
op=Pop(OPTR);
b=Pop(OPND); a= Pop(OPND);
Push(OPND, Operate(a, op, b));
break; }
} return GetTop(OPND);
}
{ InitStack(s); //建空栈
scanf(“%d”,&x); //输入一个非负十进制整数
while(x!=0) { // x不等于零循环
push(s, x% 8); // x/8第一个余数进栈
x=x/8; //整除运算
}
while(! StackEmpty(s) ) //输出存放在栈中的八制数位
{case‘*‘:
case‘/‘: c_temp1=4; break;
case‘+‘:
case‘-‘: c_temp1=2; break;
. . . . . . }
switch(c2)
{case‘*‘:
case‘/‘: c_temp2=3; break;
case‘+‘:
case‘-‘: c_temp2=1; break;
N：十进制数，div：整除运算，mod：求余运算；
(1348)10 = 283+582+08+4 = (2504)8
N 1348 168 21 2
N div 8 168 21 2 0
N mod 8 4 0 5 2
安徽新华电脑专修学院课堂教学教案
（电脑应用课使用）
教
学
过
程
设
计
(续表)

数据结构第三章

数据结构第三章

SeqStack *S;
栈顶指针top， 用来指示栈顶位
置
第三章 栈和队 列
通常0下标端设为栈底，这样空栈时栈顶指针S->top = -1；入 栈时，栈顶指针加1，即S->top++；出栈时，栈顶指针减1，即S->top--。
5
S->top
4
E
E
3
D
D
S->top
2
C
C
1 S->top 0
S->top A
return 0;
s->top= -1;
return 1; }
首先建立栈空间， 然后初始化栈顶指
⑵ 判栈空
针。
int Empty_SeqStack(SeqStack *s) { if (s->top== -1) return 1;
else return 0; }
top
5
4 3 2 1 0 top=-1
第三章 栈和队 列
两个栈共享空间时初始化、进栈和出栈操作的算法：
1 初始化操作
int initDupStack(dupsqstack *s) { if ((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)
return 0; s->lefttop= -1; s->righttop=MAXSIZE; return 1; }
第三章 栈和队 列
⑶ 入栈
1 int Push_SeqStack(SeqStack *S, datatype x)
/*插入数据元素x */
2{
3 if(S->top==MAXSIZE-1)

数据结构第三章 栈和队列part2)

数据结构第三章 栈和队列part2)
制转移到调用函数。
多个函数嵌套调用的规则是：
后调用先返回 ！
此时的内存管理实行“栈式管理”
例如：
void main( ){ void a( ){
…
…
a( );
b( );
…
…
}//main
}// a
void b( ){
… 函数b的数据区 函数a的数据区 Main的数据区
}// b
递归函数执行的过程可视为同一 函数进行嵌套调用.
例七、实现递归
当在一个函数的运行期间调用另一个函 数时，在运行该被调用函数之前， 需先完成三项任务：
• 将所有的实在参数、返回地址等信息传 递给被调用函数保存；
• 为被调用函数的局部变量分配存储区； • 将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该 完成下列三项任务：
• 保存被调函数的计算结果； • 释放被调函数的数据区； • 依照被调函数保存的返回地址将控
从原表达式求得后缀式的规律为：
1) 设立操作数栈； 2) 设表达式的结束符为“#”，
预设运算符栈的栈底为“#”；
3) 若当前字符是操作数， 则直接发送给后缀式。
从原表达式求得后缀式的规律为：
4) 若当前运算符的优先数高于栈顶运算 符，则进栈；
5) 否则，退出栈顶运算符发送给后缀式；
6) “(” 对它之前后的运算符起隔离作 用，“)”可视为自相应左括弧开始的 表达式的结束符。
// 从终端接收下一个字符
}
将从栈底到栈顶的字符传送至调用过程的数据区；
ClearStack(S);
// 重置S为空栈
if (ch != EOF) ch = getchar();
}

数据结构(第3章).

数据结构(第3章).

2017年1ห้องสมุดไป่ตู้月21日
数据结构讲义
10
⑸取栈顶元素 datatype Top_SeqStack(SeqStack *s) { if (Empty_SeqStack(s)) return 0; /*栈空 */ else return(s->data[s->top]); }
2017年10月21日
数据结构讲义
⒌教学时间：6 学时
2017年10月21日
数据结构讲义
1
3.1 栈
栈的定义及基本运算 栈的存储实现和运算实现
2017年10月21日
数据结构讲义
2
3.1.1 栈的定义及基本运算
栈是限制在表的一端进行插入和删除的线性表。允许 插入、删除的这一端称为栈顶，另一个固定端称为栈底。 当表中没有元素时称为空栈。 右图所示栈中有三个元素， 进栈的顺序是a1、a2、a3，当 需要出栈时其顺序为a3、a2、 a1，所以栈又称为后进先出的 线性表（Last In First Out）， 简称 LIFO表。
第三章 栈和队列
⒈教学内容：3.1
3.2 3.3 3.4 栈 栈应用举例 队列 队列应用举例
⒉教学目的：⑴理解栈的定义、特征及在其上所定义的基本运算；
⑵掌握在两种存储结构上对栈所施加的基本运算的实现； ⑶理解队列的定义、特征及在其上所定义的基本运算； ⑷掌握在两种存储结构上对队列所施加的基本运算的实现。
2017年10月21日 数据结构讲义 5
通常 0下标端设为栈底，这样空栈时栈顶指针 top=-1; 入栈时，栈顶指针加１，即s->top++; 出栈时，栈顶指 针减１，即s->top--。栈操作的示意图如图所示。

数据结构授课教案-第3章

数据结构授课教案-第3章
{
top= NULL;
}
⑵判栈空
intEmpty_LinkStack（LinkStacktop）
{
if（top==NULL）return 1;
else return 0;
}
⑶入栈
void Push（LinkStack&top,ElemTypex）
{ s=malloc(sizeof(StackNode));
后缀表示法在表示表达式时，每一个运算符都紧跟在它所操作的运算量之后的方法叫后缀表示法。
如A＋B的后缀表示法为：AB＋
中缀表达式求值
3.3栈与递归
1．递归的概念
递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。
2．递归设计
1）将问题用递归的方式描述（定义）
2）根据问题的递归描述（定义）编写递归算法
2.对每章习题中的重点及难点问题进行讨论，并解答学生有关的疑问。
{ if (Empty_SeqStack( s ) ) return 0; /*下溢*/
else {s.top--; x=s.data[s.top];return 1; }
}
⑸取栈顶元素
elemtypeGetTop(SeqStacks)
{
if (Empty_SeqStack( s ) ) return 0; /*栈空*/
}SeqStack；
定义2：
ElemTypes[MAXSIZE];
inttop;
⑴置空栈：首先建立栈空间，然后初始化栈顶指针。
voidinitStack(SqStack&s)
{
s.top= 0;
}
⑵判空栈
boolStackEmpty(SeqStacks)

《数据结构》教案 第三章 串及其应用

《数据结构》教案 第三章 串及其应用

ch3 串及其应用本实习单元的目的是熟悉串类型的实现方法和文本模式匹配方法,熟悉一般文字处理软件的设计方法,较复杂问题的分解求精方法。

本实习单元的难度较大,在教学安排上可以灵活掌握完成此单元实习的时间。

编程技术训练要点:并行的模式匹配技术(3.1);字符填充技术(3.2,3.4);逻辑/物理概念隔离技术(GetAWord,3.2);活区操作技术(3.3);不定长对象的成块存储分配技术(3.3);命令识别与分析技术(3.3,3.4);串的动态组织技术(3.4);合理有效的错误处理方法(3.4);程序语法结构基本分析技术(3.5).1. 文学研究助手【问题描述】文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。

试写一个实现这一目标的文字统计系统,称为"文学研究助手"。

【基本要求】英文小说存于一个文本文件中。

待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。

程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。

【测试数据】以你的C源程序模拟英文小说,C语言的保留字集作为待统计的词汇集。

【实现提示】约定小说中的词汇一律不跨行。

这样,每读入一行,就统计每个词在这行中的出现次数。

出现位置所在行的行号可以用链表存储。

若某行中出现了不止一次,不必存多个相同的行号。

如果读者希望达到选做部分(1)和(2)所提出的要求,则首先应把KMP算法改写成如下的等价形式,再将它推广到多个模式的情形。

i=1;j=1;while(i!=s.curlen+1&&j!=t.curlerl十1){while(j!=0&&s.ch[i]!=t.ch[j])j=next[j]; //j==O或s.ch[i]==t.ch[j]j++;i++;//每次进入循环体,i只增加一次}【选作内容】(1)模式匹配要基于KMP算法。

(2)整个统计过程中只对小说文字扫描一遍以提高效率。

第3章数据结构基本类型3.1线性表-高中教学同步《信息技术-数据与数据结构》(教案)

第3章数据结构基本类型3.1线性表-高中教学同步《信息技术-数据与数据结构》(教案)
学生预习：
布置预习任务，要求学生提前阅读线性表的基础知识和概念。
发放预习材料，如PPT、视频教程或预习习题。
课堂讨论引导：
准备引导性问题，鼓励学生积极参与课堂讨论。
设计小组活动，促进学生之间的合作与交流。
课后反馈：
设计课后习题和作业，以检验学生的学习效果。
准备课后答疑和辅导，为学生提供必要的帮助和支持。
确保教学环境中网络连接稳定，以便在需要时展示在线资源或示例。
教学媒体
教学媒体
PPT演示文稿：
线性表的基本概念、定义、特点和示例的幻灯片。
顺序存储和链式存储的对比图示。
线性表基本操作（如初始化、查找、插入、删除）的动画或图解。
代码编辑器/IDE：
演示顺序表和链表的实现代码（如Python）。
允许学生直接看到、理解和操作代码。
情感、态度与价值观：
激发学生的学习兴趣和创造力，培养学生的探索精神和创新精神。
引导学生认识到数据结构在解决实际问题中的重要性，形成合理的计算机思维观念。
学习重难点
教学重点
线性表的基本概念：理解线性表是什么，它如何表示具有相同பைடு நூலகம்型数据元素的有限序列，并理解其特点，包括唯一的首尾元素以及除首尾外每个元素有且仅有一个前驱和后继。
准备用于课堂讨论的实例和问题，如通信录的设计和实现。
准备教学用计算机和相关编程环境（如Python环境），以便现场演示代码和执行结果。
教学流程设计：
设计教学流程，从线性表的基础概念引入，逐步深入到线性表的存储方式和操作。
设计课堂互动环节，如提问、小组讨论等，鼓励学生积极参与和表达。
安排编程实践环节，让学生亲自编写线性表相关操作的代码，加深理解。
线性表的应用场景：通过通信录的实例，了解线性表在实际问题中的应用，并理解如何根据需求选择合适的数据结构和存储方式。

数据结构第3章

数据结构第3章

弹出/，但*高于+，继续进栈 输出8 遇到结束符#，依次弹出*，+
26
3.2.1 表达式的转换与计算
2．后缀表达式的计算 后缀表达式求值的运算要用到一个数栈stack和 一个存放后缀表达式的字符型数组exp。其实现 过程就是从头至尾扫描数组中的后缀表达式： （1）当遇到运算对象时，就把它插入到数栈 stack中； （2）当遇到运算符时，就执行两次出栈的操作， 对出栈的数进行该运算符指定的运算，并把计 算的结果压入到数栈stack。把它插入到数栈 stack中； （3）重复（1）、（2），直至扫描到表达式的 终止符“#”，在数栈的栈顶得到表达式的值。
9
3.1.2 栈的定义及基本操作
栈的基本操作如下。
(1) Init_Stack(s)：初始化操作。构造一个空栈。 (2)Stack_Empty(s)：判栈空操作。若栈s为空栈，函数返回 值为1；否则，返回值为0。 (3)Push_Stack(s, x)：入栈操作。在栈s的顶部插入一个新 元素x。 (4)Gettop_Stack(s)：读栈顶元素操作。若栈非空，函数返 回栈顶元素；若栈空，函数返回值为0。 (5)Pop_Stack(s)：出栈操作。删除栈s的顶部元素，并返回 栈顶元素；若栈空，函数返回值为0。 (6)Clear_Stack(s)：栈置空操作。将栈s置为空栈。 (7)StackLength(s)：求栈的长度操作。返回栈s中的元素个 数。
7
栈操作的示意图如下图所示。
top=9
J I H G
top=5
F E
F E
top=3
F E
D
C B
top=0 top=-1 (a)
D
C B A
(d)
D

大学《数据结构》第三章：栈和队列-第一节-栈

大学《数据结构》第三章：栈和队列-第一节-栈

第一节栈
一、栈的定义及其运算
1、栈的定义
栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。

不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out)的线性表，简称为LIFO表。

真题选解
（例题·填空题）1、如图所示，设输入元素的顺序是（A，B，C，D），通过栈的变换，在输出端可得到各种排列。

若输出序列的第一个元素为D，则输出序列为。

隐藏答案
【答案】DCBA
【解析】根据堆栈"先进后出"的原则，若输出序列的第一个元素为D，则ABCD入栈，输出序列为DCBA
2、栈的基本运算
(1)置空栈InitStack(&S)：构造一个空栈S。

数据结构第三章-栈和队列(严蔚敏)

数据结构第三章-栈和队列(严蔚敏)

}
s
top
top
…... 栈底 ^
x
24
出栈算法
LinkStack Pop_LinkStack (LinkStack DataType *x) { StackNode *p; if （top= =NULL）return NULL; else {*x = top->data; p = top; top = top->next; top top free (p); a return top;} p } x a top,
11
顺序栈
栈的顺序存储结构简称为顺序栈，是利用一组地址 连续的存储单元依次存放自栈底到栈顶的数据元素，同 时附设指针top指向实际栈顶后的空位置。
12
顺序表和顺序栈的操作区别
以线性表 S= (a1 , a2 , …. , an-1 , an )为例 顺序栈S an+1 高地址 顺序表S 高地址 表尾 an an …… …… S[i] ai ai …… …… a2 低地址 a1 a2 低地址 表头 a1 栈顶top 栈顶top
Stacksize 指示栈的当前可使用的最大容量。栈的初始化操作为： 按设定的初始分配量进行第一次存储分配； base可称为栈底指针，在顺序栈中它始终指向栈底的位置，若 base的值为NULL，则表明栈结构不存在。 top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标 记； 每当插入新的栈顶元素时（入栈），堆栈指针top先压后加 （S[top++]=an+1）； ； 删除栈顶元素时（出栈），堆栈指针top先减后弹
B
A
19
顺序栈入栈 int push(SqStack &s, SElemType e){ if (s.top-s.base>=s.stacksize){//栈满的判断 s.base=(SElemTYpe*) realloc(s.base,s.stacksize+ STACKINCREMENT)*sizeof(SElemType)); if (!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; top } *s.top++=e; //入栈（ *s.top=e; *s.top++)； return OK; } base

数据结构实用教程(C语言版) 第3章 栈和队列

数据结构实用教程(C语言版) 第3章 栈和队列
返回到本节目录
3.1.1 栈的概念
假设有一个栈S=（a1，a2，…，an），栈 中元素按a1，a2，…，an的次序进栈后， 进栈的第一个元素a1为栈底元素，出栈的第 一个元素an为栈顶元素，也就是出栈的操作 是按后进先出的原则进行的，其结构如图31所示。
图3-1栈结构示意图
返回到本节目录
3.1.2栈的基本操作
3.1.3顺序栈
由于栈是操作受限制的线性表，因此与线性表类似，栈也 有两种存储结构，即顺序存储结构和链式存储结构。 1. 顺序栈的定义 栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺 序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素 位置的变量来实现。顺序栈中栈顶指针与栈中数据元素的关1.3顺序栈
3. 顺序栈的基本操作实现
（3）进栈操作 进栈操作的过程如图3-3所示。先判断栈S如图3-3（a） 是否为满，若不满再将记录栈顶的下标变量top加1如 图3-3（b），最后将进栈元素放进栈顶位置上如图33（c）所示，算法描述见算法3.3。
图3-3 进栈操作过程图
返回到本节目录
栈除了在栈顶进行进栈与出栈外，还有初始化、判空 等操作，常用的基本操作有： （1）初始化栈InitStack(S)。其作用是构造一个空 栈 S。 （2）判断栈空EmptyStack(S)。其作用是判断是 否是空栈，若栈S为空，则返回1；否则返回0。 （3）进栈Push(S,x)。其作用是当栈不为满时，将 数据元素x插入栈S中，使其为栈S的栈顶元素。 （4）出栈Pop(S,x)。其作用是当栈S不为空时，将 栈顶元素赋给x，并从栈S中删除当前栈顶元素。 （5）取栈顶元素GetTop(S,x)。其作用是当栈S不 为空时，将栈顶元素赋给x并返回，操作结果只是 读取栈顶元素，栈S不发生变化。 返回到本节目录

西安石油大学数据结构教案第03章

西安石油大学数据结构教案第03章

3、顺序堆栈
顺序堆栈：顺序存储结构的堆栈。
顺序栈的存储结构： 利用一组地址连续的存储单元依次存放自栈底到栈顶的 数据元素.
栈底 0 1 2 3
栈顶 4 5
stack a0 a1 a2 a3 a4 =
top
MaxStackSize-1
typedef struct { DataType stack[MaxStackSize]; int top; } SeqStack;
}
else if(exp[i] == ']' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '['] StackPop(&myStack, &c);
else if(exp[i] == ']' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '[')
}
head->next = p->next; *d = p->data;
free(p);
return 1; }
（5）取栈顶数据元素StackTop(head, d)
int StackTop(LSNode *head, DataType *d) {
LSNode *p = head->next;
if(p == NULL) {
2、表达式计算问题
表达式计算是编译系统中的基本问题，其实现方法是堆 栈的一个典型应用。在编译系统中，要把便于人理解的表达 式翻译成能正确求值的机器指令序列，通常需要先把表达式 变换成机器便于理解的形式，这就要变换表达式的表示序列。

第3章数据结构基本类型3.5二叉树-高中教学同步《信息技术-数据与数据结构》(教案)

第3章数据结构基本类型3.5二叉树-高中教学同步《信息技术-数据与数据结构》(教案)
二叉树定义的深入理解：
学生在初次接触二叉树时，可能会对其定义和特性感到抽象和难以理解。
需要通过具体实例和图示帮助学生建立直观理解。
二叉树遍历算法的实现：
遍历算法是二叉树操作的核心和基础，但对于一些学生来说可能较为复杂和困难。
需要逐步引导学生从简单到复杂，从理论到实践，逐步掌握遍历算法的实现。
二叉树的应用场景：
举例法：
通过具体的例子（如图3.5.3、图3.5.4、图3.5.5等）来解释和说明二叉树的相关概念和操作，使学生能够将理论知识与实际应用相联系。
归纳法：
在介绍完二叉树的基本概念和操作后，教师通过归纳的方式，总结二叉树的特点、遍历方法及其重要性，帮助学生形成系统的知识体系。
演示法：
在介绍二叉树的遍历方法时，教师可以通过黑板绘图或使用多媒体演示软件（如PowerPoint）进行演示，展示遍历的过程和结果。
在二叉树的定义部分，我们明确了二叉树是一种特殊的树形结构，其中每个节点最多有两个子节点，并且子树有左右之分。基于这个定义，我们了解了二叉树的基本形态，包括空树、只有一个节点的树、根节点有左子树或右子树的树，以及根节点同时具有左右子树的树。
随后，我们讨论了二叉树的深度（或高度）以及满二叉树和完全二叉树的概念。满二叉树是二叉树的一种特殊形态，其中每个节点都有两个子节点（除了叶子节点外）。而完全二叉树则是从满二叉树中按照一定规则删除节点后得到的二叉树。
学生能够通过实际编程实践，掌握二叉树操作的基本算法，提高编程能力。
学生能够通过小组讨论和合作，共同解决问题，培养团队协作能力。
三、情感态度与价值观目标
激发学生对数据结构学习的兴趣，认识到数据结构在计算机科学中的重要性。
培养学生善于思考、勇于探索的学习态度，以及解决问题的自信心。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
复习思考题
作业
上机任务
案例分析：
例1数制转换
例2表达式求值
参考文献
《数据结构》（C语言版）扬振生中国科学技术大学出版社
课后记
（或归纳小结）
本章主要介绍的栈的特性，来说明两个例子
课程名称
数据结构
教学对象
新华软工
教材
数据结构（C语言）
授课内容
第三章栈和队列
课时
3
教学目的
与要求
本章主要介绍栈和队列的定义，它们的特点，算法实现
任务五：队列的存储
一、队列的顺序存储：（用时40分钟）
#define MAX 50 /*数据结构定义*/
int queue[MAX]; int front=-1; rear=-1;
int insert_queue(int x) /*入队列*/
{if(rear==MAX-1)return(0);
rear++;
front = 0; rear=0;
Return (1)}
2、入队操作功能：将元素x插入队尾
教
学
过
程
设
计
(续表)
int insert_queue(int x) /*入队列*/
{ if((rear+1)%MAX==front)return(0);
queue[rear]=x;
rear=(rear+1)%MAX; return(1);
{ InitStack(s); //建空栈
scanf(“%d”,&x); //输入一个非负十进制整数
while(x!=0) { // x不等于零循环
push(s, x% 8); // x/8第一个余数进栈
x=x/8; //整除运算
}
while(! StackEmpty(s) ) //输出存放在栈中的八制数位
第一个出栈的元素为栈顶元素，
最后一个出栈的元素为栈底元素
安徽新华电脑专修学院课堂教学教案
（电脑应用课使用）
教
学
过
程
设
计
(续表)
二栈的基本操作（用时20分钟）
1）构造一个空栈S；
2）进栈操作Push
3）出栈操作Pop
4)取栈顶元素top
任务二、栈存储
1、栈的顺序存储结构（用时40分钟）
#define MAX 50
}
3、出队操作功能：删除队头元素；
int del_queue() /*出队列*/
{ int x;
if(rear==front) return(0);
x=queue[front];
front=(front+1)%MAX;
return(x);
}
三、链队列——队列的链式存储结构和实现（用时40分钟）
struct node //链队列结点的类型定义
二循环队列的基本操作算法（用时20分钟）
有两种方法：
1）另设一个标志位以区分队空、队满。
2）少用一个存储单元，队满条件:front=rear+1;
1、初始化操作
功能：建一个空队列Q；算法：
Int queue[MAX];
Int front, rear;
int InitQueue_Sq() {
//构造一个空队列Q
int express ( )
{//运算数栈，OP为运算符集合。
InitStack(OPTR); Push (OPTR, ‘# ‘);
InitStack(OPND); w=getchar( );
While(w!=‘ #’ || GetTop(OPTR)!=‘#’)
{if(! In(w,OP)){Push(OPND,w);w=getchar();} //不是运算符则进栈
{case‘*‘:
case‘/‘: c_temp1=4; break;
case‘+‘:
case‘-‘: c_temp1=2; break;
. . . . . . }
switch(c2)
{case‘*‘:
case‘/‘: c_temp2=3; break;
case‘+‘:
case‘-‘: c_temp2=1; break;
重点、难点
重点：栈和队列的定义和特性、它们的基本操作、存储结构
难点：队列的顺序存储结构
课型
电脑＋理论
教学方法
投影、讨论、板书
教学过程
设计
（包括讲授知识、演示内容及案例、提问及学生演示内容）
任务四、队列的概念
一、什么是队列（用时30分钟）
队列是限定仅能在表头进行删除，表尾进行插入的线性表
队列的特点：先进先出
任务一、栈
前言：（用时15分钟）
从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表的子集，它们是操作受限的线性表，即可称限定性的数据结构
一、什么是栈（用时35分钟）
栈是限定仅能在表尾一端进行插入、删除操作的线性表
栈的特点：后进先出
第一个进栈的元素在栈底，
最后一个进栈的元素在栈顶，
case ‘>’: //新输入的算符c优先级低，即栈顶算符优先权高，
//出栈并将运算结果入栈OPND
op=Pop(OPTR);
b=Pop(OPND); a= Pop(OPND);
Push(OPND, Operate(a, op, b));
break; }
} return GetTop(OPND);
}
rear->link=p;rear=p;
}
2、队列出列运算
int count( )
{ int i=0; NODE *p;
if (front==rear)return(0);
for(p=front->link;p!=NULL;p=p->link)i++;
return(1);
}
复习思考题
作业
上机任务
案例分析：
{int data;
struct node *link;
};typedef struct node NODE
NODE *front, *rear;
1、队列入列运算
Void addqlink(int x)
{NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->data=x;p->link=NULL;
重点：栈和队列的定义和特性、它们的基本操作、存储结构
难点：队列的顺序存储结构
课型
电脑＋理论
教学方法
投影、讨论、板书
教学过程
设计
（包括讲授知识、演示内容及案例、提问及学生演示内容）
任务三、栈的应用举例
例1数制转换（用时50分钟）
对于输入的任意一个非负十进制数，显示输出与其等值的八进制数
数制转换方法
N = (Ndiv8)108+N mod 8
队列中的元素具有先进先出的特点；
队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，
入队操作要修改队尾指针，出队操作要修改队头指针；
top--; return(stack[top]);
}
2、栈的链式存储和实现（用时40分钟）
(1)进栈算法
NODE *top;
Void push(int x)
{ NODE *p=(NODE *)malloc(sizeof(NODE);
p->data=x;
p->link=top;
top=p;
}
教
学
过
程
queue[rear]=x;return(1);
}
int del_queue() /*出队列*/
{ if(rear==front) return(0);
front++;return(queue[front]);
}
当rear==front相等时，队列有可能是空的也有可能满的，所以就不能有任何二义性，到底是满的，还是空的，所以必须想办法处理，出现一种循环列
else// In(w, OP)判断c是否是运算符的函数
switch (Precede(GetTop(OPTR), w) {
case ‘<‘: //新输入的算符w优先级高，w进栈
Push(OPTR, w ); w =getchar( ); break;
case ‘=‘: //去括号并接收下一字符
x=Pop(OPTR); w=getchar( ); break;
若ci>cj则说明ci是已扫描的运符中优先级最高者，可进行运算；
若ci = cj则ci为（，cj为），说明括号内的式子已计算完，需要消去括号；
教
学
过
程
设
计
(续表)
算符比较算法
Char Precede( char c1, char c2)
{int c_temp1, c_temp2;
switch(c1)
. . . . . . }
if (c_temp1<c_temp2) return(‘<‘);
if (c_temp1=c_temp2) return(‘=‘);
if (c_temp1>c_temp2) return(‘>‘);
}
在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符一个是OPND栈，用以保存操作数或运算结果。
4）算符优先关系表
表达式中任何相邻运算符c1、c2的优先关系有：
c1<c2：c1的优先级低于c2
c1=c2：c1的优先级等于c2