C语言程序设计 清华大学 郑莉 安颖莲第十二讲 数据结构基础
（二）
①,计算机程序程序设计基础,第 10章
②,数据结构,（严蔚敏 等 编著）第 3章
C语言程序设计 清华大学 郑莉 安颖莲
Page 2
本讲主要内容
栈的概念和基本操作
栈的存储结构
栈的应用举例
队列的概念和基本操作
队列的存储结构
队列的应用举例
C语言程序设计 清华大学 郑莉 安颖莲
Page 3
栈的概念和基本操作
栈的定义
- 栈是限定仅在表尾进行插入或删除操作的线性表。
- 表尾称为 栈顶,表头称为 栈底 。不含元素的空表称为空栈。
- 栈又称为 后进先出（ LIFO） 的线性表。
栈的基本操作
- 生成空栈
- 进栈
- 出栈
- 查询栈顶结点
- 判断栈是否为空
C语言程序设计 清华大学 郑莉 安颖莲
Page 4
栈的存储结构
栈的顺序存储结构－顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
栈的链式存储结构－链栈
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语言程序设计 清华大学 郑莉 安颖莲
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语言程序设计 清华大学 郑莉 安颖莲
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'<':
Push(OPTR,c); c=getchar();
break;
case'=':
Pop(OPTR,x);
c=getchar();
break;
case'>':
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,
Operate(a,theta,b));
break;
}
}
}例 1
C语言程序设计 清华大学 郑莉 安颖莲
Page 8
例 1 整数四功能计算器
· 题目：
- 编写一个简单的整数四功能计算器，要求先输入操作数，后输入操作符，输入‘ q’ 时结束。
· 分析：
- 数据结构：使用栈
- 算法要点：
输入字符，若字符不是 +,-,*,/之一，进栈，再输入，若字符是 +,-,*,/之一，则把栈中两个操作数依次弹出，进行运算，再把运算结果压进栈，再输入字符，直到输入的字符为,q” 表示结果输入。
· 程序,12-1.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 9
例 1 整数四功能计算器
,6
,4
,+
10
,7
,-
3
,4
,*
12
,q
运行结果：
白色字代表输入的数据，黄色字代表输出的结果。
C语言程序设计 清华大学 郑莉 安颖莲
Page 10
栈的应用举例 —— 子程序调用由于栈有后进先出的特点，在高级语言中，调用子程序时利用栈来传递参数和返回地址。
C语言程序设计 清华大学 郑莉 安颖莲
Page 11
队列的概念和基本操作
队列的定义
- 队列是只允许在表的一端进行插入，另一端进行删除操作的线性表。
- 允许插入的一端叫做 队尾,允许删除的一端称为 队头 。
- 队是一种 先进先出（ FIFO） 的线性表。
栈的基本操作
- 生成空队列
- 进队
- 出队
- 判断队满和队空
C语言程序设计 清华大学 郑莉 安颖莲
Page 12
队列的存储结构
队列的链式表示和实现－链队列
- 具有头指针和尾指针的单链表。
队列的顺序表示和实现
- 队满和队空的情况
- 假溢出
- 循环队列
C语言程序设计 清华大学 郑莉 安颖莲
Page 13
队列的应用举例题目：用队列处理备忘录功能如下：
程序启动后显示下列菜单：
1------------input memo
2------------save memo to file
3------------load memo from file
4------------list memo
5------------delete memo item
0------------exit
C语言程序设计 清华大学 郑莉 安颖莲
Page 14
队列的应用举例
· 选,1” 时，提示用户从键盘逐条输入备忘录内容，
当输入回车时，结束输入,然后重新显示上述菜单。
· 选,2” 时，将备忘录存入磁盘文件,memo” 中,然后重新显示上述菜单 。
· 选,3” 时，从文件,memo” 中读取备忘录队列,然后重新显示上述菜单 。
· 选,4” 时，输出备忘录队列内容，然后重新显示上述菜单。
· 选,5” 时，删除已完成的事件（队头）。
C语言程序设计 清华大学 郑莉 安颖莲
Page 15
队列的应用举例分析
- 数据结构：
使用队列，定义指针数组，存放备忘录队列。
- 算法要点：
定义几个函数分别实现输入、存文件、从文件中读、输入、删除队头和显示菜单的功能。
主函数用两层循环，外层循环用 for( ; ;)，无终止的执行循环体，内层循环用 switch语句，当 switch括号中表达式的值通过调用显示菜单的函数得到，每一个 case
对应一个函数，通过调用执行相应的功能。
程序,12-2.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 16
队列的应用举例
1------------input memo
2------------save memo to file
3------------load memo from file
4------------list memo
5------------delete memo item
0------------exit
please input your select:
1
运行结果,
黄色为屏幕显示，白色为用户输入的数据。
C语言程序设计 清华大学 郑莉 安颖莲
Page 17
Input the 1st item:aaa
Input the 2st item:bbb
Input the 3st item:ccc
Input the 4st item:ddd
Input the 5st item:(回车）
重新显示主菜单
please input your select:
4
No.1:aaa
No.2:bbb
No.3:ccc
No.4:ddd
重新显示主菜单
please input your select:
0
C语言程序设计 清华大学 郑莉 安颖莲
Page 18
作 业
复习：
①,计算机程序程序设计基础,第 10章
②,数据结构,（严蔚敏 等 编著）第 3章
上机：
- 用 C 语言编写：进栈、出栈、进队、出队函数，
要考虑栈满、栈空情况。分别用链表和数组实现。
- 修改例 12-1.c,实现在一行上用中缀法输入算式，
以,＝,结束算式。
- 按下列要求修改例 12-2.c：
① 改用循环队列。② 考虑内存回收。
（二）
①,计算机程序程序设计基础,第 10章
②,数据结构,（严蔚敏 等 编著）第 3章
C语言程序设计 清华大学 郑莉 安颖莲
Page 2
本讲主要内容
栈的概念和基本操作
栈的存储结构
栈的应用举例
队列的概念和基本操作
队列的存储结构
队列的应用举例
C语言程序设计 清华大学 郑莉 安颖莲
Page 3
栈的概念和基本操作
栈的定义
- 栈是限定仅在表尾进行插入或删除操作的线性表。
- 表尾称为 栈顶,表头称为 栈底 。不含元素的空表称为空栈。
- 栈又称为 后进先出（ LIFO） 的线性表。
栈的基本操作
- 生成空栈
- 进栈
- 出栈
- 查询栈顶结点
- 判断栈是否为空
C语言程序设计 清华大学 郑莉 安颖莲
Page 4
栈的存储结构
栈的顺序存储结构－顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
栈的链式存储结构－链栈
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语言程序设计 清华大学 郑莉 安颖莲
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语言程序设计 清华大学 郑莉 安颖莲
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'<':
Push(OPTR,c); c=getchar();
break;
case'=':
Pop(OPTR,x);
c=getchar();
break;
case'>':
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,
Operate(a,theta,b));
break;
}
}
}例 1
C语言程序设计 清华大学 郑莉 安颖莲
Page 8
例 1 整数四功能计算器
· 题目：
- 编写一个简单的整数四功能计算器，要求先输入操作数，后输入操作符，输入‘ q’ 时结束。
· 分析：
- 数据结构：使用栈
- 算法要点：
输入字符，若字符不是 +,-,*,/之一，进栈，再输入，若字符是 +,-,*,/之一，则把栈中两个操作数依次弹出，进行运算，再把运算结果压进栈，再输入字符，直到输入的字符为,q” 表示结果输入。
· 程序,12-1.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 9
例 1 整数四功能计算器
,6
,4
,+
10
,7
,-
3
,4
,*
12
,q
运行结果：
白色字代表输入的数据，黄色字代表输出的结果。
C语言程序设计 清华大学 郑莉 安颖莲
Page 10
栈的应用举例 —— 子程序调用由于栈有后进先出的特点，在高级语言中，调用子程序时利用栈来传递参数和返回地址。
C语言程序设计 清华大学 郑莉 安颖莲
Page 11
队列的概念和基本操作
队列的定义
- 队列是只允许在表的一端进行插入，另一端进行删除操作的线性表。
- 允许插入的一端叫做 队尾,允许删除的一端称为 队头 。
- 队是一种 先进先出（ FIFO） 的线性表。
栈的基本操作
- 生成空队列
- 进队
- 出队
- 判断队满和队空
C语言程序设计 清华大学 郑莉 安颖莲
Page 12
队列的存储结构
队列的链式表示和实现－链队列
- 具有头指针和尾指针的单链表。
队列的顺序表示和实现
- 队满和队空的情况
- 假溢出
- 循环队列
C语言程序设计 清华大学 郑莉 安颖莲
Page 13
队列的应用举例题目：用队列处理备忘录功能如下：
程序启动后显示下列菜单：
1------------input memo
2------------save memo to file
3------------load memo from file
4------------list memo
5------------delete memo item
0------------exit
C语言程序设计 清华大学 郑莉 安颖莲
Page 14
队列的应用举例
· 选,1” 时，提示用户从键盘逐条输入备忘录内容，
当输入回车时，结束输入,然后重新显示上述菜单。
· 选,2” 时，将备忘录存入磁盘文件,memo” 中,然后重新显示上述菜单 。
· 选,3” 时，从文件,memo” 中读取备忘录队列,然后重新显示上述菜单 。
· 选,4” 时，输出备忘录队列内容，然后重新显示上述菜单。
· 选,5” 时，删除已完成的事件（队头）。
C语言程序设计 清华大学 郑莉 安颖莲
Page 15
队列的应用举例分析
- 数据结构：
使用队列，定义指针数组，存放备忘录队列。
- 算法要点：
定义几个函数分别实现输入、存文件、从文件中读、输入、删除队头和显示菜单的功能。
主函数用两层循环，外层循环用 for( ; ;)，无终止的执行循环体，内层循环用 switch语句，当 switch括号中表达式的值通过调用显示菜单的函数得到，每一个 case
对应一个函数，通过调用执行相应的功能。
程序,12-2.c
C语言程序设计 清华大学 郑莉 安颖莲
Page 16
队列的应用举例
1------------input memo
2------------save memo to file
3------------load memo from file
4------------list memo
5------------delete memo item
0------------exit
please input your select:
1
运行结果,
黄色为屏幕显示，白色为用户输入的数据。
C语言程序设计 清华大学 郑莉 安颖莲
Page 17
Input the 1st item:aaa
Input the 2st item:bbb
Input the 3st item:ccc
Input the 4st item:ddd
Input the 5st item:(回车）
重新显示主菜单
please input your select:
4
No.1:aaa
No.2:bbb
No.3:ccc
No.4:ddd
重新显示主菜单
please input your select:
0
C语言程序设计 清华大学 郑莉 安颖莲
Page 18
作 业
复习：
①,计算机程序程序设计基础,第 10章
②,数据结构,（严蔚敏 等 编著）第 3章
上机：
- 用 C 语言编写：进栈、出栈、进队、出队函数，
要考虑栈满、栈空情况。分别用链表和数组实现。
- 修改例 12-1.c,实现在一行上用中缀法输入算式，
以,＝,结束算式。
- 按下列要求修改例 12-2.c：
① 改用循环队列。② 考虑内存回收。
