清华大学：《C语言程序设计》课程教学资源（PPT课件讲稿）第十二讲 数据结构基础（二）

C语言程序设计 清华大学郑莉安颖莲 第十二讲 数据结的基础 (二) ① 《计算机程序程序设计基础》第10章 ② 《数据结构》（严蔚敏等编著）第3章

C语言程序设计 清华大学 郑莉 安颖莲 第十二讲 数据结构基础 （二） ①《计算机程序程序设计基础》第10章 ②《数据结构》（严蔚敏 等 编著）第3章

C语言程序设计 清华大学郑莉安颖莲 本讲主要内容 。 栈的概念和基本操作 栈的存储结构 ● 栈的应用举例 ·队列的概念和基本操作 。队列的存储结构 ·队列的应用举例 Page 2

C语言程序设计 清华大学 郑莉 安颖莲 Page 2 本讲主要内容 • 栈的概念和基本操作 • 栈的存储结构 • 栈的应用举例 • 队列的概念和基本操作 • 队列的存储结构 • 队列的应用举例

C语言程序设计 清华大学郑莉安颖莲 栈的概念和基本操作 。栈的定义 一栈是限定仅在表尾进行插入或删除操作的线性表。 表尾称为栈顶，表头称为栈底。不含元素的空表称 为空栈。 -栈又称为后进先出(LIO)的线性表。 。 栈的基本操作 -生成空栈 一进栈 - 出栈 - 查询栈顶结点 判断栈是否为空 Page 3

C语言程序设计 清华大学 郑莉 安颖莲 Page 3 栈的概念和基本操作 • 栈的定义 - 栈是限定仅在表尾进行插入或删除操作的线性表。 - 表尾称为栈顶，表头称为栈底。不含元素的空表称 为空栈。 - 栈又称为后进先出（LIFO）的线性表。 • 栈的基本操作 - 生成空栈 - 进栈 - 出栈 - 查询栈顶结点 - 判断栈是否为空

C语言程序设计 清华大学郑莉安颖莲 栈的存储结构 ·栈的顺序存储结构一顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素。 栈的链式存储结构一链栈 Page 4

C语言程序设计 清华大学 郑莉 安颖莲 Page 4 栈的存储结构 • 栈的顺序存储结构－顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素。 • 栈的链式存储结构－链栈

C语言程序设计 清华大学郑莉安颖莲 栈的应用举例 数制转换 。 输入任意一个非负十进制整数，： 输出与其等值 的八进制数。 void conversion ( InitStack(S); scanf ("%d",N) while(N) {push(S,N%8);n=n/8;} while(!StackEmpty) Pop(S,e);printf("%d",e); Page 5

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 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); Page 6

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() case'=': { Pop(OPTR,x); InitStack(OPTR);InitStack (OPND); c=getchar ( Push (OPTR,'#')c=getchar(); break; while(c!=#GetTop (OPTR)!='#') case'>': if(!In(c,OP)) Pop(OPTR,theta); Push((OPND,c);c=getchar();} Pop(OPND,b); else Pop(OPND,a); switch(Precede (GetTop(OPTR),c) Push (OPND, case'<': Operate(a,theta,b)); Push (OPTR,c);c=getchar(); break; break; 例1 Page 7

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 Page 8

C语言程序设计 清华大学 郑莉 安颖莲 Page 8 例1 整数四功能计算器 · 题目： - 编写一个简单的整数四功能计算器，要求先输入操作 数，后输入操作符，输入‘q’时结束。 · 分析： - 数据结构：使用栈 - 算法要点： 输入字符，若字符不是+、-、*、/之一，进栈，再输 入，若字符是+、-、*、/之一，则把栈中两个操作数 依次弹出，进行运算，再把运算结果压进栈，再输入 字符，直到输入的字符为“q”表示结果输入。 · 程序：12-1.c

C语言程序设计 清华大学郑莉安颖莲 例1 整数四功能计算器 运行结果： 白色字代 表输入的 数据，黄 色字代表 3 4 输出的结 米 果。 12 q

C语言程序设计 清华大学 郑莉 安颖莲 Page 9 例1 整数四功能计算器 ：6 ：4 ：+ 10 ：7 ：- 3 ：4 ：* 12 ：q 运行结果： 白色字代 表输入的 数据，黄 色字代表 输出的结 果

C语言程序设计 清华大学郑莉安颖莲 栈的应用举例 子程序调用 由于栈有后进先出的特点，在高级语言 中，调用子程序时利用栈来传递参数和返回 地址。 Page 10

C语言程序设计 清华大学 郑莉 安颖莲 Page 10 栈的应用举例——子程序调用 由于栈有后进先出的特点，在高级语言 中，调用子程序时利用栈来传递参数和返回 地址