还剩31页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
陕西理工大学重点课程《数据结构》实验指导书使用班级网络1401-1402数学与计算机科学学院计算机科学与技术系2016年9月returnS-top==-1TRUE:FALSE;IintIsfullSeqStack*SreturnS-top==Stack_size-1TRUE:FALSE;}intPushSeqStack*ScharxifS-top==Stack_size-1printf”栈满\n”;returnFALSE;else{S-top++;S-data[S-top]=x;returnTRUE;I}intPushnSeqStack*Sintx{ifS-top==Stack_size-1printf栈满\n”;returnFALSE;elseS-top++;S-data[S-topJ=x;returnTRUE;intPopnScqStack*Sint*xifS-top==-l{printf”操作数为空\n“;returnFALSE;}else*x=S-data[S-top];S-top-;returnTRUE;}IintPopScqStack*Schar*xifS-top==-l{printf”操作符为空\n”;returnFALSE;}else*x=S-data[S-top];S-top-;returnTRUE;}IcharGettopSeqStack*SIifS-top==-lprintfC栈为空\n”;returnFALSE;}elseretumS-data[S-topJ;intIsoperatorcharch{inti;fori=0;iv7;i++ifch==ops[i]returnTRUE;returnFALSE;charComparecharch1charch2charpri;intpriority;fori=0;i7;i++{ifchl==opsfi]m=i;ifch2==ops[i]n=i;}returncmp[m][nj;}intExecuteintacharopintb{intresult;switchopcase+:result=a+b;break;case-:result=a-b;break;case*:result=a*b;break;case7:result=a/b;break;}returnresult;intExpEvaluationintabvtemp;charopch;char*str;inti=0;SeqStackOPTR;SeqStackOPND;InitStackOPTR;InitStackOPND;PushnOPTR;#;printf”输入表达式,以#结束\n”;str=char*malloc5*sizeofchar;getsstr;ch=str[i];i++;whilech!=#||GettopOPTR!=#{if!Isoperatorchtemp=ch-O*;ch=str[ij;i++;whilc!Isoperatorch{temp=temp*10+ch-O;ch=str[i];i++;}PushnOPNDtemp;elseswitchCompareGettopOPTRch{casev PushOPTRch;ch=str[i];i++;break;case’:PopOPTRop;PopnOPNDb;PopnOPNDa;v=Executeaopb;PushnOPNDv;break;case:PopOPTRop;ch=str[ij;i++;break:}}}v=GcttopOPND;returnv;Ivoidmainintresult;systemclr;result=ExpEvaluation;printf(表达式的结果为%d\nuresult);}实验四队列
一、实验性质必做
二、实验学时2学时
三、实验类型验证
四、实验目的掌握队列顺序存储结构和链式结构,以便在实际背景下灵活运用掌握队列的特点,即进先出的原则
五、实验内容1)实现队列入队、出队操作;2)利用栈和队列知识实现停车场管理根据题目要求,停车场只有一个大门,因此可用一个栈来模拟;而当栈满后继续来的车辆只能停在便道上,根据便道停车的特点,可知这可以用一个队列来模拟,安排队的车辆先离开便道,进入停车场由于在停车场中间的车辆可以提前离开停车场,而且要求在离开车辆到停车场大门之间的车辆都必须先离开停车场,让此车离去,然后再让这些车辆依原来的次序进入停车场,因此在一个栈和一个队列的基础上,还需要有一个地方保存为了让路离开停车场的车辆,很显然这也应该用一个栈来模拟因此本题中用到两个栈和一个队列对于停车场和车辆规避所,有车辆进入和车辆离去两个动作,这就是栈的进栈和出栈操作,只是还允许排在中间的车辆先离开停车场,因此在栈中需要进行查找而对于便道,也有入队列和出队列的操作,同样允许排在中间的车辆先离去队列这样基本动作只需利用栈和队列的基本操作就可实现Stacktypestack[N];inttop;}Stack;typcdefstructnode〃定义队列节点类型{intnum;structnode*next;}Queneptr;typedefstruct//定义队列Queneptr*front*rear;JQuene;voidinitstackStack*s〃初始化栈{s-top=-1;intpushStack*sStacktypex〃数据元素X进入指针S所指的栈ifs-top=N-lreturnO;elses-stack[++s-top]=x;returnl;}StacktypepopStack*s{Stacktypcx;ifs-top0x.num=;x.aiTtime=O;returnx;〃如果栈不空,返回栈顶元素}else{x=s-stack[s-top];s-top-;returnx;}}voidinitqueneQuene*s〃初始化队列s-front=Queneptr*mallocsizeofQueneptr;//产生一个新结点,作为头结点s-rear=s-front;s-front-next=NULL;s-front-num=0;〃头结点的NUM保存队列元素的个数}voidenqueneQuene*sintnum〃数据入队列{Queneptr*p;p=Queneptr*mallocsizeofQueneptr;p-num=num;p-next=NULL;s-rear-next=p;s-rear=p;s-front-num++;}intdelqueneQuene*sQueneptr*p;intn;ifs-front==s-rearreturnO;elsep=s-front-next;s-front-next=p-next;ifp-next==NULLs-rear=s-front;n=p-num;freep;s-front-num—;returnn;voidarriveStack*slQuene*pStacktypex{intf;f=pushslx;〃新到达的车辆入停车栈iff==O{enquenepx.num;〃如果停车场满,就进入队列printfthe%dcarstopsthe%dseatofthequene\nx.nump-front-num;elseprintfthe%dcarstopsthe%dseatofthestack\nnx.nums1-top+1;}voidleaveStack*slStack*s2Quene*pStacktypex〃处理车辆离去函数{intnf=0;Stacktypey;Queneptr*q;whiles1-top-!!fy=popsl;ify.num!=x.numn=pushs2y;elsef=l;}ify.num==x.num〃如果栈顶元素不是要离开的车辆,就将其放入车辆规避所printfthcmoneyofthe%dis%dyuan\nMy.numx.arrtime-y.arrtime*M;whiles2-top-ly=pops2;f=pushsly;}n=delquenep;ifn〃在停车场中找到要离开的车辆{y.num=n;y.arrtime=x.arrtime;f=pushsly;printfHthe%dcarstopsthe%dseatofthestak\ny.nums1-top+1;}else{whiles2-top-1〃车辆规避所不空,将其全放回停车场y=pops2;f=pushsly;}q=p-front;f=0;whilef==Oq-next!=NULLifq-next-num!=x.num〃如果便道上有车辆,将第一辆车放入停车场q=q-next;elseq-next=q-next-next;p-front-num—;《数据结构》上机实验的目的和要求.・・・.1实验一线性表的基本操作2实验二链表的基本操作.6实验三栈7实验四队列12实验五二叉树的操作..19实验六图的有关操作.22实验七电话号码查询系统的设计与实现.29ifq-next==NULLp-rear=p-front;printflhe%dcarleavethequene\nx.num;f=l;}if仁二0〃在便道上没有找到要离开的车辆,输出数据错误printferror!thestackandthequenehavenothe%dcar\nx.num;voidmain〃停车场模拟{charch;intcord;Stack*sl*s2;Quene*p;Stacktypex;inti=1;//clrscr;//systemclr;s1=Stack*mallocsizeofStack;s2=Stack*mallocsizeofStack;p=Quene*mallocsizeofQuene;initstacksl;initstacks2;〃初始化停车规避所栈initquenep;〃初始化便道队列do{printf\n主菜单\n;printfl进入停车场\n;printf2离开停车场\n”;printfM3退出\n”;printfH\nM;printf”请输入你的选择123”;scanf”%d”cord;switchcord/*printfwhatdoyouwanttodo\n;printfinput---Add/Del/Exit:;scanf%cch;switchch*/case1:printfH请输入车辆到达序号:\n”;scanf%dx.num;print请输入车辆到达时间:\n”;scanf%dx.arrtime;arriveslpx;〃车辆到达break;case2:printfC*请输入车辆离开序号:\n”;scanf%dx.num;printf”请输入离开时间:\n”;scanf”%d”x.arrtime;leaves1s2px;〃车辆离开break;case3:/*printftheend!;i=0;*/exitO;break;default:{printf输入不对,请重新输入:\n;break;}}whilei=3;//ch=getchar;}实验五二叉树的操作
一、实验性质必做
二、实验学时:4学时
三、实验类型验证
四、实验目的掌握二叉树的定义、性质及存储方式,各种遍历算法
五、实验内容采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序遍历的操作,求所有叶子结点总数的操作
六、程序实现typcdefstructnodechardata;structnode*lc;structnode*rc;}*BiTree;inim=0;voidPrctraverseBiTreet先序遍历ift!二NULL{printf%ct-data;Pretraverset-lc;Pretraverset-rc;}voidInorderBiTreet中序遍历voidPostorderBiTreet后序遍历{IvoidcreatBiTree*t{charch;//printf”请输入数据\n”;scanf%cch;ifch=#{*l=NULL;return;}else*t=BiTreemallocsizeofstructnode;*t-data=ch;printf%c二ch;creat*t-lc;creat*t-rc;}voidmain{BiTreet;systeninclr;intcord;doprintfH4后序遍历二叉树,统计叶子结点数\n”;printfC*5程序运行结束\nu;printfC\n”;printf”请输入你的选择12345:”;scanf%dcord;switchcordcase1:{creatt;printf”二叉树建立完成,请继续执行其他操作\n”;break;case2:{Pretraverset;printf”先序遍历完成\n”;break;case3:{Inordcrt;printf”中序遍历完成\n”;break;case4:{Postordert;printfC*后序遍历完成\n”;printf”叶子结果数为%3d”m;break;case5:printfH二叉树程序执行完毕!\n”;exitO;whilecord=5;实验六图的有关操作
一、实验性质必做
二、实验学时:4学时
三、实验类型验证
四、实验目的掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用
五、实验内容采用邻接矩阵和邻接表作为图的存储结构,完成无向图的DFS及BFS操作
六、程序实现邻接矩阵作为存储结构的程序示例#includestdio.hn#includeustdlib.h”#defineMaxVertexNum10〃定义最大顶点数typedefstructcharvexs[MaxVertexNum];〃顶点表intedges[MaxVertexNum][MaxVertexNum];〃邻接矩阵,可看作边表intne;〃图中的顶点数n和边数eJMGraph;〃用邻接矩阵表示的图的类型〃建立邻接矩阵voidCreatMGraphMGraph*G{intijk;chara;printfnInputVertexNumnandEdgesNume:;scanf”%d%d”G-nG-e;〃输入顶点数和边数scanf%ca;printfInputVertexstring:;fori=0;iG-n;i++scanf%ca;G-vexsfi]=a;〃读入顶点信息,建立顶点表fori=0;iG-n;i++forj=0;jG-n;j++G-edges[i]|j]=O;〃初始化邻接矩阵printfInputedgesCreatAdjacencyMatrix\n;fork=0;kvG-e;k++〃读入e条边,建立邻接矩阵scanf”%d%d”ij;〃输入边ViVj的顶点序号G-edgesliJ[jJ=l;G-edges[j][i]=l;〃若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句}}〃定义标志向量,为全局变量typedefenum{FALSETRUE}Boolean;Booleanvisited[MaxVertexNum]:〃DFS深度优先遍历的递归算法voidDFSMMGraph*Ginti{〃以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是01矩阵intj;printf%cG-vexs[i];visitcd[i]=TRUE;forj=0;jG-n;j++ifG-edges[i][j]==1!visited]VjeE且Vj未访问过,故Vj为新出发点}voidDFSMGraph*G//BFS广度优先遍历voidBFSMGraph*Gintk〃以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索intijf=Or=O;intcq[MaxVertexNum]:fori=0;iG-n;i++visitcd[i]=FALSE;fori=0;iG-n;i++cqlij=-l;printf%cG-vexs[k];visited[k]=TRUE;cq[r]=k whilecq[f]!=-li=cq[f|;f=f+l;〃Vf出队forj=0;jG-n;j++〃依次Vi的邻接点VjifG-edges[i]|j]==l!visited]{//Vj未访问printf%cG-vexs[j];visited[j]=TRUE;r=r+1;cq[rl=j;//mainvoidmainint1;MGraph*G;G=MGraph*mallocsizeofMGraph;CreatMGraphG;〃建立邻接矩阵printfMPrintGraphDFS:,DFSG;〃深度优先遍历printf”\n,printfCPrintGraphBFS:;BFSG3;〃以序号为3的顶点开始广度优先遍历printf\nM;执行顺序InputVertexNumnandEdgesNume:89I叩utVertexstring:01234567InputedgesCreatAdjacencyMatrix01302\131425图G的示例374756PrintGraphDFS:01374256PrintGraphBFS:31704256邻接链表作为存储结构程序示例#includestdio.h#inc】ude”stdlib.h”typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型〃建立图的邻接表《数据结构》上机实验的目的和要求通过上机实验加深对课程内容的理解,增加感性认识,提高软件设计、编写及调试程序的能力要求所编的程序能正确运行,并提交实验报告实验报告的基本要求为
1、需求分析陈述程序设计的任务,强调程序要做什么,明确规定输入的形式和输出值的范围;输出的形式;程序所能达到的功能;测试数据包括正确的输入输出结果和错误的输入及输出结果
2、概要设计说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系
3、详细设计提交带注释的源程序或者用伪代码写出每个操作所涉及的算法
4、调试分析调试过程中所遇到的问题及解决方法;算法的时空分析;经验与体会
5、用户使用说明说明如何使用你的程序,详细列出每一步操作步骤
6、测试结果列出对于给定的输入所产生的输出结果若有可能,测试随输入规模的增长所用算法的实际运行时间的变化voidCreatALGraphALGraph*Gintijk;chara EdgeNode*s;〃定义边表结点printfInputVertexNumnandEdgcsNume:;scanf”%d%d”G-nG-e;〃读入顶点数和边数scanf%cHa;printfInputVertexstring:;fori=0;iG-n;i++〃建立边表{scanf”%c”a;G-adjlist[i].vertex=a;〃读入顶点信息G-adj1ist[i].firstedge=NULL:〃边表置为空表}printfInputedgesCreatAdjacencyList\n”;fork=0;kG-e;k++〃建立边表scanf”%d%d”ij;〃读入边ViVj的顶点对序号s=EdgeNode*mallocsizcofEdgcNodc;〃生成边表结点s-adjvex=j;〃邻接点序号为js-next=G-adj1ist[i].firstedge;G-adjlistfi].firstedge=s;〃将新结点*S插入顶点Vi的边表头部s=EdgeNode*mallocsizeofEdgeNode;s-adjvex=i;〃邻接点序号为is-next=G-adjlist|j].firstedge;G-adj1ist[j].firstedge=s:〃将新结点*S插入顶点Vj的边表头部}〃定义标志向量,为全局变量typedefenum{FALSETRUEBoolean;Booleanvisited[MaxVertexNum]:〃DFS深度优先遍历的递归算法voidDFSMALGraph*Ginti{〃以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p printfM%cG-adjlisl[i].vertex;〃访问顶点Vivisited[i]=TRUE;〃标记Vi己访问p=G-adjlist[i].firstedge;〃取Vi边表的头指针whilep〃依次搜索Vi的邻接点Vj这里j=p-adjvexvisited[k]=TRUE;cqr]=k;〃Vk己访问,将其入队注意,实际上是将其序号入队whilecq[f]!=-1队列非空则执行i=cq[f];f=f+l;//Vi出队p=G-adj1ist[i].firstedge:〃取Vi的边表头指针whilep〃依次搜索Vi的邻接点Vj令p-adjvex=jif!visited[p-adjvex]〃若Vj未访问过printf%cG-adjlist[p-adjvex].vertex;〃访问Vjvisited[p-adjvex]=TRUE;r=r+1:cq[r]=p-adjvex;}p=p-next;}//cndwhile〃主函数voidmain{inti;ALGraph*G;G=ALGraph*mallocsizeofALGraph;CreatALGraphG;printfPrintGraphDFS:;DFSG;printf\n;printfMPrintGraphBFS:;BFSG3;printf\n;}执行顺序InputVertexNumnandEdgesNume:89InputVertexstring:01234567InputedgesCreatAdjacencyList010213142526374756PrintGraphDFS:02651473PrimGraphBFS:37140265实验七电话号码查询系统的设计与实现
一、实验性质必做
二、实验学时:4学时
三、实验类型综合
四、实验目的利用《数据结构》课程相关知识,以C/C++作为编程语言完成一个具有一定难度的综合实验通过本实验,巩固和加深对线性表、栈、队列、树、图、查找、排序等理论知识的理解;掌握现实问题的分析和解决方法,进而提高利用计算机分析解决综合实际问题的基本能力
五、实验内容编写一个电话号码查询系统,要求按照人名顺序进行记录排序,分别按照电话号码和人名进行查询,能将满足查询要求的记录删除具有要求实验一线性表的基本操作
一、实验性质必做
二、实验学时:2学时
三、实验类型验证
四、实验目的
1、掌握用VC++上机调试线性表的基本方法;
2、掌握线性表的基本操作,插入、删除、查找,以及线性表合并等运算在顺序存储结构和链接存储结构上的运算
五、实验内容线性表建立、插入、删除操作实现己知有序表SASB其元素均为递增有序,将此两表归并成一个新有序表SC且SC中的元素仍然递增有序
六、程序实现structSQList{inteiem[MAXSIZE];intlen;};SQListcreat_SQList/*建立顺序表*/SQList1;inti=0;printfH请输入顺序表”;scanfu%dul.elem[i];whileLelem[i]!=0{i++;scanfn%dMLelem[i];}l.len=—i;return1;voidprint_SQListSQList1//顺序表输出}SQListMerge_SQListSQListLASQListLB/*合并*/SQListSQList_insertSQListsintiintx/*插入*/{intj;ifi||is.lenprintf插入位置不存在,elseforj=s.len;j=i;j-s.elem[j+l]=s.elem[j];s.elem[i]=x;s.len=s.len+l;}//print_SQLists;returns;}SQListSQList_deleteSQListsinti/*删除*/intj;ifiO||is.lenprintfi位置不存在,elseforj=i;j=s.len;j++s.elem[j]=s.elem[j+l];s.len-;//prinl_SQLists;returns;}voidmainSQListLALBLC;intiycord;//clrscr;doprintfM请输入你的选择123scanf”%d”cord;switchcord{case1:{LA=creat_SQList;LB=creat_SQList;printfClistLA:H;print_SQListLA;printfClistLB:”;print_SQListLB;}break;case2:{printf”请输入插入位置及元素,scanf”%d%d”iy;LA=SQList_insertLAiy;printfulistLA”;print_SQListLA;break;case3:{printfn请输入删除位置”;scanf”%d”i;LA=SQList_deleteLAi;printfnlistLA”;print_SQListLA;break;case4:{printf”线性表合并”;LC=Merge_SQListLALB;printfMlistLCn;print_SQListLC;break;case5:exitO;}whilecord=5;实验结果以下面的界面显示:、d:\IyDocuaentsWisualStudio2005\Projects\SQList\debu|\SQLi8t.exe实验二单链表的基本操作
一、实验性质必做
二、实验学时2学时
三、实验类型验证
四、实验目的了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析
五、实验内容单链表的基本操作实现,建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之;根据要求插入相应的字符串单链表实现相关操作代码自己完成,链表中结点定义如下〃定义结点实验性质必做实验类型验证实验目的熟练掌握栈的结构,以及这种数据结构的特点;能够在两种存储结构上实现栈的基本运算,特别注意栈满和栈空的判断条件及描述方法;
五、实验内容计算表达式的值计算用运算符后缀法表示的表达式的值后缀表达式也称逆波兰表达式,比中缀表达式计算起来更方便简单些,中缀表达式要计算就存在着括号的匹配问题所以在计算表达式值时一般都是先转换成后缀表达式,再用后缀法计算表达式的值如表达式a+b*c/d.e用后缀法表示应为abc*+d/e.只考虑四则算术运算,且假设输入的操作数均为1位十进制数0-9并且输入的后缀形式表达式不含语法错误
六、程序实现typedefstructchardata[Stack_size];inttop;}SeqStack;charops
[7]=charcmp
[7]
[7]={{VW‘}J*;}voidlnitStackScqStack*SS-top=-l;}intEmptyStackSeqStack*Sprintf\n二叉树相关操作\n”;printfC1建立二叉树\n”;printf2先序遍历二叉树\n”;printfC3中序遍历二叉树\n;#defineMaxVertexNum50〃定义最大顶点数typedefstructnode{intadjvex;structnode*next JEdgeNode;〃边表结点〃邻接点域〃链域typedefstructvnodecharvertex;EdgeNodc*firstcdge;}VertexNode;〃顶点表结点〃顶点域〃边表头指针typedefstructAdjListadjlist;〃邻接表intne;ALGraph;〃图中当前顶点数和边数〃图类型1234567数据以文件的方式存放;从文件中读取数据;按照人名对对电话本中的记录进行排序;根据电话号码查找相关信息;根据姓名查找相关信息;删除符合条件的记录;数据输出以文件存储printf\n主菜单\n);printfCl建立线性表\n”);printf2插入一个元素\n”;printf3删除一个元素\n”;printf4合并线性表\n”;printf5退出\nn;printfH\n“;。