C语言程序设计 清华大学郑莉安颖莲 第十二讲数据结构基础 ①《计算机程序程序设计基础》第10章 ②《数据结构》(严蔚敏等编著)第3章
C语言程序设计 清华大学 郑莉 安颖莲 第十二讲 数据结构基础 （二） ①《计算机程序程序设计基础》第10章 ②《数据结构》（严蔚敏 等 编著）第3章
C语言程序设计 清华大学郑莉安颖莲 本讲主要内容 栈的概念和基本操作 栈的存储结构 ·栈的应用举例 ·队列的概念和基本操作 队列的存储结构 队列的疝用举例
C语言程序设计 清华大学 郑莉 安颖莲 Page 2 本讲主要内容 • 栈的概念和基本操作 • 栈的存储结构 • 栈的应用举例 • 队列的概念和基本操作 • 队列的存储结构 • 队列的应用举例
C语言程序设计 清华大学郑莉安颖莲 栈的概念和基本操作 栈的定义 栈是限定仅在表尾进行插入或删除操作的线性表。 表尾称为栈顶,表头称为栈底。不含元素的空表称 为空栈。 栈又称为后进先出(LIFO)的线性表。 栈的基本操作 生成空栈 进栈 出栈 查询栈顶结点 判断栈是否为空
C语言程序设计 清华大学 郑莉 安颖莲 Page 3 栈的概念和基本操作 • 栈的定义 - 栈是限定仅在表尾进行插入或删除操作的线性表。 - 表尾称为栈顶，表头称为栈底。不含元素的空表称 为空栈。 - 栈又称为后进先出（LIFO）的线性表。 • 栈的基本操作 - 生成空栈 - 进栈 - 出栈 - 查询栈顶结点 - 判断栈是否为空
C语言程序设计 清华大学郑莉安颖莲 栈的存储结构 栈的顺序存储结构一顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素。 栈的链式存储结构一链栈
C语言程序设计 清华大学 郑莉 安颖莲 Page 4 栈的存储结构 • 栈的顺序存储结构－顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素。 • 栈的链式存储结构－链栈
C语言程序设计 清华大学郑莉安颖莲 栈的应用举例 数制转换 输入任意一个非负十进制整数,输出与其等值 的八进制数。 void conversion o InitStack(S scanf(%d,N while(n push(S,N‰8);n=n/8;} while(! StackEmpty) Pop(s, e): printf( %d", e)
C语言程序设计 清华大学 郑莉 安颖莲 Page 5 栈的应用举例 ——数制转换 • 输入任意一个非负十进制整数，输出与其等值 的八进制数。 void conversion() { InitStack(S); scanf("%d",N); while(N) { push(S,N%8); n=n/8; } while(!StackEmpty) { Pop(S,e); printf("%d",e); } }
C语言程序设计 清华大学郑莉安颖莲 栈的应用举例行编辑程序 接收用户输入的程序或数据,存入用户的数据区 “#”表示退格符,“@”表示退行符。 void LineEdito InitStack(S) ch=getchar while(ch!=EOF) I while(ch!=EOF & ch!='\n') switch(ch case Pop (s, c) case'@': ClearStack(S) default: Push(S, ch) ch=getchar( ClearStack(S f(ch!=EoF) ch=getchar DestroyStack(S
C语言程序设计 清华大学 郑莉 安颖莲 Page 6 栈的应用举例——行编辑程序 • 接收用户输入的程序或数据，存入用户的数据区 “#”表示退格符，“@”表示退行符。 void LineEdit() { InitStack(S); ch=getchar(); while(ch!=EOF) { while(ch!=EOF && ch!='\n') { switch (ch) { case '#':Pop(S,c); case '@':ClearStack(S); default:Push(S,ch); } ch=getchar(); } ClearStack(S); if(ch!=EOF) ch=getchar(); } DestroyStack(S); }
C语言程序设计 清华大学郑莉安颖莲 栈的应用举例表达式求值 OperandType EvaluateExpression o case Pop( optr, x) InitStack(OPTR); InitStack(OPND); c=getchar Push(oPTR, #) c=getchar b reak while(c!=#'GetTop(OPTR)!=#') case I if(!In(c, OP)) Pop(optr, theta) I Push((oPND, c); c=getchar o; Pop (opnd, b) Pop (opnd, a) e⊥se switch(Precede(GetTop(optr), c) Push oPnD Operate(a, theta, b)) case < Push (oPTR, c); c=getchar break break 例1
C语言程序设计 清华大学 郑莉 安颖莲 Page 7 栈的应用举例——表达式求值 OperandType EvaluateExpression() { InitStack(OPTR); InitStack(OPND); Push(OPTR,'#'); c=getchar(); while(c!='#'||GetTop(OPTR)!='#') { if(!In(c,OP)) { Push((OPND,c); c=getchar();} else switch(Precede(GetTop(OPTR),c) { case'': Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a,theta,b)); break; } } 例 } 1
C语言程序设计 清华大学郑莉安颖莲 例1蓬数四功能计算器 题目: 编写一个简单的整数四功能计算器,要求先输入操作 数,后输入操作符,输入‘q’时结束。 分析: 数据结构:使用栈 算法要点: 输入字符,若字符不是+、-、*、/之一,进栈,再输 入,若字符是+、-、*、/之一,则把栈中两个操作数 依次弹出,进行运算,再把运算结果压进栈,再输入 字符,直到输入的字符为“q”表示结果输入。 程序:12-1.c
C语言程序设计 清华大学 郑莉 安颖莲 Page 8 例1 整数四功能计算器 · 题目： - 编写一个简单的整数四功能计算器，要求先输入操作 数，后输入操作符，输入‘q’时结束。 · 分析： - 数据结构：使用栈 - 算法要点： 输入字符，若字符不是+、-、*、/之一，进栈，再输 入，若字符是+、-、*、/之一，则把栈中两个操作数 依次弹出，进行运算，再把运算结果压进栈，再输入 字符，直到输入的字符为“q”表示结果输入。 · 程序：12-1.c
C语言程序设计 清华大学郑莉安颖莲 例1蓬数四功能计算器 运行结果: 4 白色字代 : 10 表输入的 数据,黄 ::3 色字代表 4 输出的结 米 果 12 q
C语言程序设计 清华大学 郑莉 安颖莲 Page 9 例1 整数四功能计算器 ：6 ：4 ：+ 10 ：7 ：- 3 ：4 ：* 12 ：q 运行结果： 白色字代 表输入的 数据，黄 色字代表 输出的结 果
C语言程序设计 清华大学郑莉安颖莲 栈的应用举例程序调用 由于栈有后进先出的特点,在高级语言 中,调用子程序时利用栈来传递参数和返回 地址
C语言程序设计 清华大学 郑莉 安颖莲 Page 10 栈的应用举例——子程序调用 由于栈有后进先出的特点，在高级语言 中，调用子程序时利用栈来传递参数和返回 地址