第十一课
本课主题：栈的应用
教学目的：掌握栈的应用方法,理解栈的重要作用
教学重点：利用栈实现行编辑,利用栈实现表达式求值
教学难点：利用栈实现表达式求值
授课内容：
一、栈应用之一：数制
转换
将十进制数转换成其它进制的数有一种简单的方法：
例：十进制转换成八进制：(66)10=(102)8
66/8=8
余 2
8/8=1
余 0
1/8=0
余 1
结果为余数的逆序:102
。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：
void
conversion() { pSqStack S; SElemType e; int n; InitStack(&S); printf("Input a
number to convert to OCT:\n"); scanf("%d",&n); if(n<0) { printf("\nThe
number must be over 0."); return;} if(!n)
Push(S,0); while(n){ Push(S,n%8); n=n/8; } printf("the
result is: "); while(!StackEmpty(*S)){ Pop(S,&e);
printf("%d",e);} } |
请看：数制转换的C源
程序
二、栈应用之二：行编
辑
一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数
据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行
符，表示当前行所有字符均无效。
例：在终端上用户输入为
whli##ilr#e(s#*s)
应为
while(*s)
void LineEdit()
{ pSqStack S,T;
char str[1000]; int strlen=0;
char e; char ch; InitStack(&S); InitStack(&T); ch=getchar(); while(ch!=EOFILE)
{ while(ch!=EOFILE&&ch!='\n')
{ switch(ch){ case '#':
Pop(S,&ch); break; case '@':
ClearStack(S); break; default:
Push(S,ch); break; } ch=getchar(); } if(ch=='\n')
Push(S,ch); while(!StackEmpty(*S))
{ Pop(S,&e); Push(T,e); } while(!StackEmpty(*T))
{ Pop(T,&e); str[strlen++]=e; } if(ch!=EOFILE)
ch=getchar(); } str[strlen]='\0'; printf("\n%s",str); DestroyStack(S); DestroyStack(T); } |
请看:行编辑的C源
程序
三、栈应用之三：表达
式求值
一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，
编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3
有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。
算法基本思想：
１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；
２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。
char EvaluateExpression() { SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack(&OPTR);
Push(OPTR,'#'); InitStack(&OPND); 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; } } c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; } |
请看:表达式求值的C源程序
四、总结
栈的先进后出、后进先出的特性。
回目录上一课下一课
第十二课
本课主题：实验二 循环链表实验
教学目的：掌握单向链表的实现方法
教学重点：单向链表的存储表示及操作
教学难点：单向链表的操作实现
授课内容：
一、单向链表的存储表示
C源程序
二、单向链表的基本操作
C源程序
回目录上一课下一课
第十三课
本课主题：队列
教学目的：掌握队列的类型定义,掌握链队列的表示与实现方法
教学重点：链队列的表示与实现
教学难点：链队列的表示与实现
授课内容：
一、队列的定义:
队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离
开。
在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。
抽象数据类型队列:
ADT
Queue{
数据对象:
D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系:
R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}
基本操作：
InitQueue(&Q)
构造一个空队列Q
Destroyqueue(&Q)
队列Q存在则销毁Q
ClearQueue(&Q)
队列Q存在则将Q清为空队列
QueueEmpty(Q)
队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q)
队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e)
Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e)
队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e)
Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit())
Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT
Queue
二、链队列－队列的链式表示和实现
用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指
针。
| | | | Q.front -> | | | | | | | \|/ | | | 1 | | | 队头 | | | \|/ | | | 2 | | | | | | \|/ | | | 3 | | | | | | \|/ \|/ | | Q.rear -> | 9 | /\ | 队尾 |
| | | | | Q.front -> | | | | | | | \|/ | | | 1 | | | 队头 | | | \|/ | | | 2 | | | | | | \|/ | | | 3 | | | | | | \|/ \|/ | | Q.rear -> | 9 | /\ | 队尾 |
|
链队列表示和实现：
//存储表示
typedef
struct QNode{
QElemType
data;
struct
QNode *next;
}QNode,*QueuePtr;
typedef
struct{
QueuePtr
front;
QueuePtr
rear;
}LinkQueue;
//操作说明
Status
InitQueue(LinkQueue &Q)
//构造一个空队列Q
Status
Destroyqueue(LinkQueue &Q)
//队列Q存在则销毁Q
Status
ClearQueue(LinkQueue &Q)
//队列Q存在则将Q清为空队列
Status
QueueEmpty(LinkQueue Q)
//
队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
Status
QueueLenght(LinkQueue Q)
//
队列Q存在,返回Q的元素个数,即队列的长度
Status
GetHead(LinkQueue Q,QElemType &e)
//Q为非空队列,用e返回Q的队头
元素
Status
EnQueue(LinkQueue &Q,QElemType e)
//队列Q存在,插入元素e为Q的队
尾元素
Status
DeQueue(LinkQueue &Q,QElemType &e)
//Q为非空队列,删除Q的队头元
素,并用e返回其值
Status
QueueTraverse(LinkQueue Q,QElemType vivsit())
//Q存在且非空,从队头到队尾,依
次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
//操作的实现
Status
InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
