数据结构 顺序栈 链栈 循环队列 链队列 hrbedu.doc

《数据结构 顺序栈 链栈 循环队列 链队列 hrbedu.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章实验报告实验名称：数据结构第三章实验实验类型：验证性学号姓名：红领巾1.问题描述（1）顺序栈l顺序栈的C语言描述l基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满（2）链栈l链栈的C语言描述l基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶（3）循环队列l循环队列的C语言描述l基本运算的算法——置空队、判队空、进队、出队、读队头元素、输出循环队列（4）链队列l链队列的C语言描述l基本运算的算法——置空队、判队空、进队、出队、读队头元素2.数据结构设计（1）顺序栈要实现顺序栈操作，我们需要一个栈顶指针一个

2、栈底指针，以及说明当前已经分配的存储空间（即当前可使用的最大容量），因此结构中需要定义这三个部分typedefstruct{char*base;char*top;intstacksize;}Sq;（2）链栈对于链栈，每一个人节点需要有data域和next域，分别储存数据以及指向下一个节点，下一个节点也应该是拥有这两个域，所以用到嵌套定义来定义节点的数据结构typedefstructnode{chardata;structnode*next;}node;（3）循环队列对于循环队列，需要有头尾指针指向队列头元素和尾元素的下一个位置，所以

3、我们定义front，rear指针，为了说明动态分配的存储空间，我们定义了base，这就是循环队列的存储结构typedefstruct{int*base;intfront;intrear;}SqQueue;（4）链队列根据要求可知，我们运用单链队列即可实现所需要的功能，对于单链队列，我们需要两个指针作为队头队尾指针从而实现队列的操作，所以定义front，rear。对于每一个节点都有data和next域来存储数据和指向下一个节点，所以进行这种节点定义。typedefstructQNode{intdata;QNode*next;}QNod

4、e,*QPtr;typedefstructQlink{QPtrfront;QPtrrear;}Qlink;3.算法设计（1）顺序栈系统规定的功能设计的算法有：置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满1）初始化和建立顺序栈S1:定义数据结构类型typedefstruct{char*base;char*top;intstacksize;}Sq//定义结构体，其中包含栈顶、栈尾指针和存储空间S2：初始化这个顺序栈intInitSq(Sq&S){S.base=(char*)malloc(STACK_INIT_SIZE*sizeof

5、(Sq));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//申请存储空间，并且将栈顶栈尾元素指在一个位置，构造空栈S3：从键盘输入一串字符，根据这些字符构造顺序栈Sqcreate(Sq&S){InitSq(S);printf("请输入你的栈");charstr[100];gets(str);//得到字符intn=strlen(str);for(inti=0;i

6、数将每个字符入栈returnS;}2）置空栈编写子函数Clear，使其可以实现置空栈功能intClear(Sq&S){while(S.top!=S.base){chare;Pop(S,e);}returnOK;}在主函数里调用Clear子函数，就能达到置空栈的功能3）判栈空S1：编写判断栈空的子函数Empty，使其实现判栈空功能intEmpty(SqS){if(S.top==S.base)returnOK;elsereturnERROR;}S2：在主函数调用时根据子函数返回值判断输出内容if(Empty(S))printf("Emp

7、ty");elseprintf("NotEmpty");4）进栈S1：从客户端得到所要入栈的元素printf("进栈元素是:");scanf("%c",&x);S2：编写子函数Push，使其可以实现将元素入栈功能intPush(Sq&S,chare){if(S.top-S.base>=S.stacksize){S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));if(!S.base)exit(OVERFLOW);S.top=S.base+

8、S.stacksize;//调整指针S.stacksize+=STACKINCREMENT;//增大空间}*S.top++=e;returnOK;}3）出栈S1：编写子函数GetTop，使其可以得到栈顶元素，从而确定要删去的元素是什么