正文.doc

Size: px

Start display at page:

Download "正文.doc"

闰莫
7 years ago
Views:

1 第 3 章栈实验三 3.1 实验目的及要求 1. 理解特殊的线性结构顺序栈的抽象数据类型的定义, 及其在 C 语言环境中的表示方法 2. 理解顺序栈的基本操作的算法, 及其在 C 语言环境中一些主要基本操作的实现 3. 在 C 语言环境下实现顺序栈的应用操作 : 1 利用栈实现十进制数转换成八进制数 2 利用栈实现一位数的加减乘除的表达式求解 3.2 实验内容经过对实验目的及要求的分析, 本实验仍然采用首先描述栈的基本操作集函数, 然后分别在两个应用操作中使用基本操作集函数来实现由于栈是一种特殊的线性结构, 仅在栈顶进行插入和删除操作, 即栈具有后进先出的特点, 故其操作比一般的线性表更为容易, 所以在本实验中有关栈的基本操作集的实现都比较简单, 没有做过多的说明, 而是在数制转换和表达式求解的应用操作中加入了更多的编程技巧, 使读者通过本实验不仅了解栈这种特殊结构的线性表, 而且掌握利用栈可实现很多的应用, 尤其是在实现表达式求解时用到了两个顺序栈, 并且加入了运算符的优先关系的判断等, 实现稍有难度在程序 Stack.c 中, 只包含了数制转换和一位数的表达式求解, 多位数的表达式求解思想与一位数表达式求解思想一致, 但需要添加多位数的接收处理, 请读者自行编写代码程序名为 :Stack.c 在 Stack.c 中包含的函数如图 3.1 所示

2 28 数据结构算法设计与实现指导 (C 语言版 ) 图 3.1 Stack.c 中包含的函数一览表 3.3 功能函数的分析设计及源代码本部分列出了实现顺序栈的操作的源代码, 并在适当的位置上添加了一些文字和流程图的注释, 帮助读者理解顺序存储的栈的存储结构及操作算法文件名 :Stack.c #include "alloc.h" #include "stdio.h" #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int SElemType; typedef int Status; // 定义顺序栈的结构 typedef struct SqStack SElemType *base; SElemType *top; int stacksize; SqStack; // 初始化一个空栈 Status InitStack(SqStack *S) (*S).base=(SElemType *)malloc(stack_init_size*sizeof(selemtype)); if(!(*s).base) exit(overflow);

3 第 3 章栈实验三 29 (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; // 数据元素入栈 Status Push(SqStack *S,SElemType e) if((*s).top-(*s).base>=(*s).stacksize) (*S).base=(SElemType*)realloc((*S).base, ((*S).stacksize+STACKINCREMENT) *sizeof(selemtype)); if(!(*s).base) exit(overflow); (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *((*S).top)++=e; // 数据元素出栈 Status Pop(SqStack *S,SElemType *e) if((*s).top==(*s).base) return ERROR; *e=*--(*s).top; // 判断一个栈是否为空 Status StackEmpty(SqStack S) if(s.top==s.base) return TRUE; return FALSE; // 销毁一个栈 Status DestroyStack(SqStack *S) free((*s).base); (*S).base=NULL; (*S).top=NULL; (*S).stacksize=0; // 十进制数转换成八进制本函数实现了无符号十进制数和八进制数间的转换功能如输入的是负数, 由于系统使用补码表示负数, 会自动将其进行补码转换, 再通过本

4 30 数据结构算法设计与实现指导 (C 语言版 ) 函数对其实现八进制转换如, 当输入 -1 时, 结果显示如果需要将十进制转换成十六进制应该如何修改本函数? 方法有两种, 第一种, 在入栈时, 存入十六进制数 ; 第二种, 在出栈时, 输出十六进制数请读者自己编写代码 void conversion() SqStack s; unsigned n; SElemType e; InitStack(&s); printf("please input a decimal number:"); scanf("%u",&n); while(n) Push(&s,n%8); n=n/8; printf("the corresponding octal number is:"); while(!stackempty(s)) Pop(&s,&e); printf("%d",e); printf("\n"); DestroyStack(&s); // 取栈顶的数据元素 Status GetTop(SqStack S,SElemType *e) if(s.top>s.base) *e=*(s.top-1); return ERROR; // 按照四则运算法则定义的运算符 ( 包括 :+ - * / () #) 运算的优先关系, 即按照表 3.1 // 判断输入的运算符与运算符栈中的运算符的优先关系表 3.1 的运算符间的优先关系是按照四则运算法则定义的, 也就是本函数的运行结果如果读者希望在运算中再加入其他运算符 ( 如乘方等 ), 则必须先定义它们的关系, 丰富表 3.1 的内容, 同时在函数中添加所加入的运算符的比较内容其中 θ 1 为栈顶元素,θ 2 为输入元素定义 # 运算符为输入表达式时的结束符及存放运算符的栈的栈底元素本函数不包含任何数据结构的内容, 仅是在输入表达式的过程中, 按照表 3.1 判断运算符栈的栈顶元素与输入的运算符的关系 (< > =) 因一个表达式包含多个运算符, 故将此部分作为一个独立的函数进行编写

5 第 3 章栈实验三 31 表 3.1 运算符间的优先关系 θ 1 θ * / ( ) # + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < = SElemType Precede(SElemType t1,selemtype t2) SElemType f; switch(t2) case '+': case '-':if(t1=='(' t1=='#') f='<'; f='>'; case '*': case '/':if(t1=='*' t1=='/' t1==')') f='>'; f='<'; case '(':if(t1==')') printf("input Error\n"); exit(error); f='<'; case ')':switch(t1) case '(':f='='; case '#':printf("input ERROR\n"); exit(error); default: f='>'; case '#':switch(t1) case '#':f='=';

6 32 数据结构算法设计与实现指导 (C 语言版 ) case '(':printf("input Error\n"); exit(error); default: f='>'; return f; // 判断 c 是否为运算符 ( 运算符包括 :+ - * / () #) Status In(SElemType c) switch(c) case'+': case'-': case'*': case'/': case'(': case')': case'#':return TRUE; default:return FALSE; // 计算 a 和 b, 返回运算结果 SElemType Operate(SElemType a,selemtype theta,selemtype b) SElemType c; switch(theta) case'+':c=a+b; case'-':c=a-b; case'*':c=a*b; case'/':c=a/b; return c; // 表达式求解在栈的基本操作集中, 主要就是入栈和出栈操作, 而且栈的数据元素的特点是后进先出, 表达式求解的应用正是利用栈的这个特性结果等在对这个应用进行分析时, 设计了中间函数, 如算符优先级别判断, 计算每次运算的在这个函数中定义了两个栈, 一个栈用来存放操作数, 另一个栈用来存放运算符, 由此又设计了对输入字符的判断函数这样就使得表达式求解的函数更直观简单易理解该函数处理过程有一定难度, 其流程图如图 3.2 所示

7 第 3 章栈实验三 33 图 3.2 表达式求解的流程图 SElemType EvaluateExpression(SElemType *e) SqStack OPTR,OPND; SElemType a,b,c,x,theta; InitStack(&OPTR); Push(&OPTR,'#'); InitStack(&OPND); c=getchar();

8 34 数据结构算法设计与实现指导 (C 语言版 ) GetTop(OPTR,&x); while(c!='#' x!='#') if(in(c)) switch(precede(x,c)) case'<':push(&optr,c); c=getchar(); case'=':pop(&optr,&x); c=getchar(); case'>':pop(&optr,&theta); Pop(&OPND,&b); Pop(&OPND,&a); Push(&OPND,Operate(a,theta,b)); if(c>='0'&&c<='9') Push(&OPND,c-48); c=getchar(); printf("input Error\n"); return ERROR; GetTop(OPTR,&x); GetTop(OPND,&x); *e=x; // 主函数本实验实现两个功能, 一是十进制转换成八进制, 二是实现 10 以内个位数字的加减乘除运算 main() char chs[256],ch; SElemType e=0; clrscr(); printf("\n1:decimal-octal Conversion"); printf("\n2:numeric Expression Evaluator"); printf("\n0:exit\n"); printf("\ninput function select:"); gets(chs);

9 第 3 章栈实验三 35 while (1) if (strlen(chs)==1) ch=chs[0]; switch (ch) case '1':conversion(); case '2':printf("Input expression ended by '#'.\n"); printf("(notice: Operand should be 0-9):"); if(evaluateexpression(&e)) printf("%d\n",e); case '0': default: printf("\nbad input...\n"); printf("\nbad input...\n"); printf("\ncontinue input function select:"); fflush(stdin); gets(chs); 3.4 习题 1. 验证栈顺序存储时的基本操作集函数和利用基本操作集实现十进制和八进制转换一位数的加减乘除的表达式求解功能 2. 在主函数中编写代码实现十进制和八进制转换功能 3. 在主函数中编写代码实现一位数表达式求解功能

Microsoft PowerPoint - ch3.pptx

Microsoft PowerPoint - ch3.pptx 第 3 章栈和队列第 3 章栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列哈尔滨工业大学 ( 威海 ) 计算机科学与技术学院 (2014/2015 学年秋季版 ) 1 本章重点难点第 3 章栈和队列重点 : (1) 栈队列的定义特点性质和应用 ;(2)AT 栈 AT 队列的设计和实现以及基本操作及相关算法难点 : (1) 循环队列中对边界条件的处理 ;(2) 分析栈和队列在表达式求值