数据结构教案下3-7.pdfVIP

教 案 讲授章节 第三章 栈和队列 授课时数 3 教学 目的： 1 理解栈和队列仍属于线性结构，其操作是线性表操作的子集，是操作受限的线性表。 但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。 2. 掌握栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈 的顶端。 3. 掌握栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。 4. 栈的应用：表达式求值。 5. 队列的基本概念和算法，其本质是：FIFO。 6. 掌握链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有牺牲一个 单元和设标记等方法。 7. 栈和队列的综合应用 教 学 内 容 （讲授提纲） 一、栈 1．栈的基本概念： 栈、栈顶、栈尾，栈只在栈顶操作。 2．栈的抽象数据类型定义 3．顺序栈及栈的操作在顺序栈中的实现。 #defineMAXSIZE 1024 typedef struct {ElemType data[MAXSIZE]; int top; }SeqStack； 4. 双向栈的定义和使用 #define m 64 typedef struct {ElemTypedata[m]; int top[2]; //top[0],top[1]分别是两个栈的栈顶指针 }TStack; 5. 链栈及栈的操作在顺序栈中的实现。 typedef struct StackNode {ElemTypedata; struct StackNode *next; }StackNode，*LinkedStack; 6. 栈的应用 过程调用 递归 （1） 使用栈进行数制转换 十进制转为八进制 void conversion() {// 把十进制转换为八进制――非递归 SeqStack S; intN; S.top -1; scanf(“%d”,N ); while(N ) {S.data[++S.top] N%8 ; N N/8; } while(S.top ! -1) printf(“%d”,S.data[S.top--]); } void Convert(intn ) {// 把十进制 n 转换为八进制递归 if(n! 0) {Convert(n/8); pritf(“%d”,n%8); } (2) 中缀表达式的求值 算术表达式中运算符(+,-,*,/等)的优先规则 设置两个工作栈： 运算符栈 S1和操作数栈 S2。S2 存放表达式的运算结果。 算法思想： 1 首先置操作数栈 S2为空栈，置运算符栈的栈底为表达式的起始符#(优先级最低)。 2 依次读入表达式的每个字符 ch,直至表达式结束： 若 ch 是操作数,则进 S2 栈； 若 ch 是运算符，若其优先级不高于栈顶运算符的优先级时，则取出栈 S2 的栈顶和 次栈顶的两个元素以及栈 S1 的栈顶运算符，进行相应的运算，并将结果放入栈 S2 中；如 此下去，直至 ch 的优先级高于栈顶运算符的优先级，将 ch 入 S1栈。 二、队列 1．队列的基本概念和算法，其本质是：FIFO。 2．队列的删除在一端 （队头），而插入则在另一端 （队尾）。因此在两种存储结构中， 一般都需要队头和队尾两个指针。 3. 提出问题－产生矛盾－解决矛盾：顺序队列的假溢出－循环队列－队头队尾相等时 是满和空的判断。 4. 在没特别说明的情况下，循环队列都是指顺序队列。