资源描述：
《南阳理工学院软件学院数据结构上机实验指导书全部答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、南阳理工学院数据结构上机实验指导书（2011版）答案（仅内供）软件学院•软件工程教研室2011.3实验1线性表应用2实验2栈和队列的应用14实验3线性表应用27实验4图论及其应用46实验5查找59实验6排序64实验1线性表应用、实验目的1.了解和掌握线性表顺序存储和链式存储在计算机屮的表示，基本操做在计算机中的实现。2.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。二、实验内容及步骤1.利用程序设计语言分别实现顺序表和链表的抽象数据类型。2.掌握程序分文件（头文件和实现文件）书写的方
2、式。3.分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。•顺序表的非递减数列合并实验2栈和队列的应用、实验目的1.掌握栈和队列这两种抽彖数据类型的特点，并能在相应的应用问题中止确选用它们。2.熟练常握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基木操作实现算法。二、实验内容及步骤1.用程序设计语言实现栈和队列的抽象数据类型。2.在第一题的基础上完成以下选择：选择一：1）设计并实现括号匹配算法。2）用队列实现在屏幕上打卬杨辉三角。选择二分别用栈和队列实现迷宫问题求解。数据结构上机实验指导书一软件学院•软件工程教研室［2011版］选择
3、三:分别用栈和队列实现一个列车调度系统。•括号匹配算法。#include#include#includeinclude”string.h”return0;}intPushStack(LinkStacktop,DataTypee)广进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回17{LStackNode*p;广定义指向第i个元素的前驱结点指针pre,指针p指向新生成的结点*/if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL){printf(”内存分配
4、失败!”);exit(-1);}p->data=e;广指针p指向头结点*7p->next=top-ext;top->next=p;return1;}intPopStack(LinkStacktop,DataType*e)广删除单链表中的第i个位置的结点。删除成功返回1,失败返回0*/{LStackNode*p;p=top->next;if(!p)广判断链栈是否为空*/{printff栈已空”)；q=p;p=p->next;free(q);}}intGetTop(LinkStacktop,DataType*e){LStackNode*p;p=top->next;if(!p)广判
5、断链栈是否为空*/printfC栈已空J;return0;}*e=p->data;广将出栈元素赋值给e*/return1;}voidmain(){casecase*{':PushStack(S,*p++);break;case*)':caseT：caseif(StackEmpty(S)){else{GetTop(S,&e);printf(n缺少右括号.”);}intMatch(DataTypee,DataTypech){if(e==,(,&&ch==,)1)return1;elseif(e=='['&&ch==T)return1;elseif(e=={&&ch==*}')
6、return1;elsereturn0;typedefstructQNode{DataTypedata;structQNode*next;}LQNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*LQ)广将返回1,否则返回0*/return1;elsereturn0;}intEnterQueue(LinkQueue*LQ,DataTypee)广将元素e插入到链式队列LQ中，插入成功返回1*/{LQNode*s;LQ->rear=s;广将队尾指针指向p
7、*/return1;}//intDeleteQueue(LinkQueue*LQ,DataType*e)〃广删除链式队列中的队头元素，并将该元素赋值给e,删除成功返回1,否则返回0*///{//LQNode空*7return0;else{s=LQ.front->next;广将指针p指向队列的第一个元素即队头元素*e=s->data;广将队头元素赋值给e,取出队头元素return1;}}广出队操作。*/intDeleteQueue(LinkQueue*Q,DataType*x){/*将队列Q的队头元素出队
