数据结构算法设计与实现指导(c语言版)

《数据结构算法设计与实现指导(c语言版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈——实验三3.1实验目的及要求1．理解特殊的线性结构——顺序栈的抽象数据类型的定义，及其在C语言环境中的表示方法。2．理解顺序栈的基本操作的算法，及其在C语言环境中一些主要基本操作的实现。3．在C语言环境下实现顺序栈的应用操作：①利用栈实现十进制数转换成八进制数。②利用栈实现一位数的加减乘除的表达式求解。3.2实验内容经过对实验目的及要求的分析，本实验仍然采用首先描述栈的基本操作集函数，然后分别在两个应用操作中使用基本操作集函数来实现。由于栈是一种特殊的线性结构，仅在栈顶进行插入和删除操作，即栈具有后进先出的特点，故其

2、操作比一般的线性表更为容易，所以在本实验中有关栈的基本操作集的实现都比较简单，没有做过多的说明，而是在数制转换和表达式求解的应用操作中加入了更多的编程技巧，使读者通过本实验不仅了解栈这种特殊结构的线性表，而且掌握利用栈可实现很多的应用，尤其是在实现表达式求解时用到了两个顺序栈，并且加入了运算符的优先关系的判断等，实现稍有难度。在程序Stack.c中，只包含了数制转换和一位数的表达式求解，多位数的表达式求解思想与一位数表达式求解思想一致，但需要添加多位数的接收处理，请读者自行编写代码。程序名为：Stack.c。在Stack.c中

3、包含的函数如图3.1所示。数据结构算法设计与实现指导（C语言版）28图3.1Stack.c中包含的函数一览表3.3功能函数的分析设计及源代码本部分列出了实现顺序栈的操作的源代码，并在适当的位置上添加了一些文字和流程图的注释，帮助读者理解顺序存储的栈的存储结构及操作算法。文件名：Stack.c#include"alloc.h"#include"stdio.h"#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2#defineTRUE1#defineFALSE0#defineOK1#defi

4、neERROR0#defineOVERFLOW-2typedefintSElemType;typedefintStatus;//定义顺序栈的结构typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;//初始化一个空栈StatusInitStack(SqStack*S){(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVE

5、RFLOW);第3章栈——实验三29(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}//数据元素入栈StatusPush(SqStack*S,SElemTypee){if((*S).top-(*S).base>=(*S).stacksize){(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exi

6、t(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;returnOK;}//数据元素出栈StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}//判断一个栈是否为空StatusStackEmpty(SqStackS){if(S.top==S.base)return

7、TRUE;elsereturnFALSE;}//销毁一个栈StatusDestroyStack(SqStack*S){free((*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;returnOK;}//十进制数转换成八进制本函数实现了无符号十进制数和八进制数间的转换功能。如输入的是负数，由于系统使用补码表示负数，会自动将其进行补码转换，再通过本数据结构算法设计与实现指导（C语言版）30函数对其实现八进制转换。如，当输入－1时，结果显示65535。如果需要将十进制转

8、换成十六进制应该如何修改本函数？方法有两种，第一种，在入栈时，存入十六进制数；第二种，在出栈时，输出十六进制数。请读者自己编写代码。voidconversion(){SqStacks;unsignedn;SElemTypee;InitStack(&s);printf("Ple