南阳理工学院软件学院数据结构上机实验指导书全部附标准答案

《南阳理工学院软件学院数据结构上机实验指导书全部附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南阳理工学院数据结构上机实验指导书（2011版）答案（仅内供）软件学院·软件工程教研室2011.3I数据结构上机实验指导书——软件学院·软件工程教研室［2011版］目录实验1线性表应用2矚慫润厲钐瘗睞枥庑赖。实验2栈和队列的应用14实验3线性表应用27实验4图论及其应用46实验5查找59实验6排序64数据结构上机实验指导书——软件学院·软件工程教研室［2011版］实验1线性表应用一、实验目的1.了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。2.能够利用线性表结构对实际问题进行分析建模，利用计

2、算机求解。3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。二、实验内容及步骤1.利用程序设计语言分别实现顺序表和链表的抽象数据类型。2.掌握程序分文件（头文件和实现文件）书写的方式。3.分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。l顺序表的非递减数列合并实验2栈和队列的应用一、实验目的1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。二、实

3、验内容及步骤1.用程序设计语言实现栈和队列的抽象数据类型。2.在第一题的基础上完成以下选择：选择一：1)设计并实现括号匹配算法。2)用队列实现在屏幕上打印杨辉三角。选择二：分别用栈和队列实现迷宫问题求解。选择三：22数据结构上机实验指导书——软件学院·软件工程教研室［2011版］分别用栈和队列实现一个列车调度系统。l括号匹配算法。#include#include#include#include"string.h"return0;}intPushStack(LinkS

4、tacktop,DataTypee)/*进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回1*/{LStackNode*p;/*定义指向第i个元素的前驱结点指针pre，指针p指向新生成的结点*/聞創沟燴鐺險爱氇谴净。if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL)残骛楼諍锩瀨濟溆塹籟。{printf("内存分配失败!");exit(-1);}p->data=e;/*指针p指向头结点*/p->next=top->next;top->next=p;retur

5、n1;}intPopStack(LinkStacktop,DataType*e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/{LStackNode*p;p=top->next;if(!p)/*判断链栈是否为空*/{printf("栈已空");q=p;p=p->next;free(q);}}intGetTop(LinkStacktop,DataType*e){LStackNode*p;p=top->next;if(!p)/*判断链栈是否为空*/{22数据结构上机实验指导书——软件学院·软件工程教研室［2

6、011版］printf("栈已空");return0;}*e=p->data;/*将出栈元素赋值给e*/return1;}voidmain(){case'[':case'{':PushStack(S,*p++);break;case')':case']':case'}':if(StackEmpty(S)){else{GetTop(S,&e);printf("缺少右括号.");}intMatch(DataTypee,DataTypech){if(e=='('&&ch==')')return1;elseif(e=='['&

7、&ch==']')return1;elseif(e=='{'&&ch=='}')return1;elsereturn0;typedefstructQNode{DataTypedata;structQNode*next;}LQNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*LQ)/*将返回1，否则返回0*/22数据结构上机实验指导书——软件学院·软件工程教研室［2011版］return1;el

8、sereturn0;}intEnterQueue(LinkQueue*LQ,DataTypee)/*将元素e插入到链式队列LQ中，插入成功返回1*/{LQNode*s;LQ->rear=s;/*将队尾指针指向p*/return1;}//intDeleteQueue(LinkQueue*LQ,DataTy