数据结构数据结构C语言版栈和队列的应用编程.doc

《数据结构数据结构C语言版栈和队列的应用编程.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验目的:l掌握栈的顺序存储结构的定义及顺序栈中的各种基本操作。l设计完成栈的综合应用包括1.数制转换2.判断回文3.括号匹配实验功能:本次实验栈和队列的应用，我对数制转换、判断回文和括号匹配进行了算法编程；主要采用栈的顺序存储结构和队列的单链存储，对栈的构造空栈、判空、入栈、出栈和队列的构造空队列、入队、出队基本操作分别进行了定义,建立了int型的数制转换顺序栈和char型的括号匹配顺序栈，同时用栈和队列判断字符串是否回文。由于数制转换（int）和括号匹配（char）的数据类型不同，分别对它们定义了进栈和出栈子函数，另外,我

2、还将数制转换分为了七个子函数，分别进行不同进制之间的转换,我觉得这样安排对使用者来说更简单快捷.我还将九个完整的函数块放在一个主函数main里，形成一个完整的、可以实现九个子函数功能的主函数。再通过编写选择语句switch—case，实现子函数功能的选择，循环while语句实现子函数菜单功能的重复执行，break语句跳出循环，结束子函数功能。主函数里通过对子函数的调用实现整体函数功能。流程图：预定义栈的存储空间和增量存储空间,Include头文件定义数制转换和括号匹配结构体定义栈和队列的基本算法，数制转换和括号匹配的进栈和出栈

3、子函数10-2进制整数转换10-16进制整数转换10-8进制整数转换2-10进制整数转换8-10进制整数转换16-10进制整数转换10-2进制小数转换括号匹配回文判断主函数mainWhile主菜单switch—case选择分支实验过程（完整源程序）:typedefintSElemType;//定义栈元素类型为整型#include#include#include//malloc()等#include#include//exit()#

4、include#include#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量#defineMAX20structSqStack//栈的顺序存储表示{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位};typedefstruct{char*base;//定义括号匹配的结构

5、体char*top;charsize;}Stack;typedefstructQNode//队列的链式存储结构{intdata;structQNode*next;}QNode,*QueuePtr;typedefstructLinkQueue{QueuePtrfront;//对头指针QueuePtrrear;//队尾指针}LinkQueue;//单链队列intInitStack(SqStack&S)//构造一个空栈S{if(!(S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int))))e

6、xit(0);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}voidcreatstack(Stack&W)//括号匹配顺序栈的建立{W.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));//系统自动生成一结点W.top=W.base;W.size=STACK_INIT_SIZE;printf("括号匹配空栈已成功创建!");}intStackEmpty(SqStackS){//若栈S为空栈，则返回1，否则返

7、回0if(S.base==S.top)return1;elsereturn0;}intPush(SqStack&S,inte)//入栈插入元素e为新的栈顶元素{if(S.top-S.base>=S.stacksize)//栈满，追加存储空间{S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base)exit(0);//存储分配失败S.top=S.base+STACKINCREMENT;}*(S.top)++=e;return

8、1;}voidPush(Stack&W,chare)//括号匹配进栈{if((W.top-W.base)>=W.size){W.base=(char*)realloc(W.base,(W.size+STACK_INIT_SIZE)*sizeof(char));W.top=W.