迪丽热巴不慎走光:数据结构教程5
来源:百度文库 编辑:九乡新闻网 时间:2024/04/29 02:21:55
第十一课
本课主题: 栈的应用
教学目的: 掌握栈的应用方法,理解栈的重要作用
教学重点: 利用栈实现行编辑,利用栈实现表达式求值
教学难点: 利用栈实现表达式求值
授课内容:
一、栈应用之一:数制转换
将十进制数转换成其它进制的数有一种简单的方法:
例:十进制转换成八进制:(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是操作数。 界定符有括号和表达式结束符等。
算法基本思想:
1首先置操作数栈为空栈,表达式起始符#为运算符栈的栈底元素;
2依次讲稿表达式中每个字符,若是操作数则进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={
基本操作:
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);
Q.front->next=NULL;
return OK;}
Status Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;}
Status EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
Status DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;}
三、总结
链队列的存储表示
链队列的操作及实现