数据结构实验指导书(网络1401-1402).docx

陕西理工大学重点课程数据结构实验指导书使用班级：网络1401-1402数学与计算机科学学院计算机科学与技术系2016年9月return(S-top=-1 ?TRUE:FALSE);Iint Isfull(SeqStack *S)(return(S-top=Stack_size- 1?TRUE:FALSE);int Push(SeqStack *S,char x)(if(S-top=Stack_size-1)(printf(”栈满n”)；return FALSE;)elseS-top+;S-dataS-top=x; return TRUE;Iint Pushn(SeqStack *S,int x)if(S-top=Stack_size-1)(printf(栈满 n”);return FALSE;)else(S-top+;S-dataS-topJ=x;return TRUE;int Popn(ScqStack *S,int *x)( if(S-top=-l)printf(”操作数为空n“); return FALSE;else(*x=S-dataS-top;S-top-; return TRUE;Iint Pop(ScqStack *S,char *x)(if(S-top=-l) printf(”操作符为空n”); return FALSE;else(*x=S-dataS-top; S-top-;return TRUE;Ichar Gettop(SeqStack *S)Iif(S-top=-l)(printfC栈为空n”)； return FALSE;else(retum(S-dataS-topJ);int Isoperator(char ch)int i; for(i=0;iv7;i+)(if(ch=opsi)return TRUE;)return FALSE;char Compare(char ch 1 ,char ch2)char pri;int priority; for(i=0;i:Pop(&OPTR,&op);Popn(&OPND,&b);Popn(&OPND,&a); v=Execute(a,op,b); Pushn(&OPND,v); break;case:Pop(&OPTR,&op);ch=strij;i+； break:v=Gcttop(&OPND);return v;Ivoid main()int result;system(clr);result=ExpEvaluation();printf（表达式的结果为：%dnu,result）;实验四队列一、实验性质：必做二、实验学时：2学时三、实验类型：验证四、实验目的：1. 掌握队列顺序存储结构和链式结构，以便在实际背景下灵活运用。2. 掌握队列的特点，即进先出的原则。五、实验内容：1）实现队列入队、出队操作；2）利用栈和队列知识实现停车场管理。根据题目要求，停车场只有一个大门，因此可用一个栈来模拟；而当栈满后, 继续来的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来 模拟，安排队的车辆先离开便道，进入停车场。由于在停车场中间的车辆可以提 前离开停车场，而且要求在离开车辆到停车场大门之间的车辆都必须先离开停车 场，让此车离去，然后再让这些车辆依原来的次序进入停车场，因此在一个栈和 一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，很显然 这也应该用一个栈来模拟。因此本题中用到两个栈和一个队列。对于停车场和车辆规避所，有车辆进入和车辆离去两个动作，这就是栈的进 栈和出栈操作，只是还允许排在中间的车辆先离开停车场，因此在栈中需要进行 查找。而对于便道，也有入队列和出队列的操作，同样允许排在中间的车辆先离 去队列。这样基本动作只需利用栈和队列的基本操作就可实现。六、程序实现：#include stdio.h #include,stdlib.h” #define N 5 #define M 10 typedef struct int num; int arrtime; Stacktype; typedef struct定义停车场长度定义栈元素的类型定义栈Stacktype stackN;int top; Stack;typcdef struct node定义队列节点类型int num;struct node *next;Queneptr;typedef struct/ 定义队列(Queneptr * front, *rear;JQuene;void initstack(Stack *s)初始化栈s-top=-1;)int push(Stack *s,Stacktype x) 数据元素X进入指针S所指的栈(if(s-top=N-l)return(O);else(s-stack+s-top=x;return(l);)Stacktype pop(Stack *s)Stacktypc x;if(s-topstack s-top;s-top-;return x;void initquene(Quene *s) 初始化队列(s-front=(Queneptr*)malloc(sizeof(Queneptr);/产生一个新结点，作为头结点 s-rear=s-front;s-front-next=NULL;s-front-num=0;头结点的NUM保存队列元素的个数void enquene(Quene *s,int num) 数据入队列Queneptr *p;p=(Queneptr*)malloc(sizeof(Queneptr);p-num=num; p-next=NULL;s-rear-next=p;s-rear=p; s-front-num+;int delquene(Quene *s)Queneptr *p;int n;if (s-front=s-rear)如果队列空return(O);elsep=s-front-next; s-front-next=p-next; if (p-next=NULL) s-rear=s-front;n=p-num;free(p);s-front-num;return(n);()void arrive(Stack *sl,Quene *p,Stacktype x)int f;f=push(sl,x);新到达的车辆入停车栈if(f=O)enquene(p,x.num);如果停车场满，就进入队列printf(the %d car stops the %d seat of the quenen,x.num,p-front-num); )else printf(the %d car stops the %d seat of the stacknn,x.num,s 1 -top+1);void leave(Stack *sl,Stack *s2,Quene *p,Stacktype x) 处理车辆离去函数 int n,f=0;Stacktype y;Queneptr *q;while(s 1 -top- !)&(! f)(y=pop(sl);if(y.num!=x.num)n=push(s2,y);else f=l;if(y.num=x.num) 如果栈顶元素不是要离开的车辆，就将其放入车辆规避所 (printf(thc money of the %d is %d yuannM,y.num,(x.arrtime-y.arrtime)*M); while(s2-top-l)(y=pop(s2); f=push(sl,y);n=delquene(p);if(n)在停车场中找到要离开的车辆y.num=n;y.arrtime=x.arrtime;f=push(sl,y);printf(Hthe %d car stops the %d seat of the stakn,y.num,s 1 -top+1);)elsewhile(s2-top-1)车辆规避所不空，将其全放回停车场(y=pop(s2);f=push(s l,y);q=p-front;f=0;while(f=O&q-next!=NULL)if(q-next-num!=x.num) 如果便道上有车辆，将第一辆车放入停车场 q=q-next;else(q-next=q-next-next;p-front-num;数据结构上机实验的目的和要求.1实验一线性表的基本操作2实验二链表的基本操作.6实验三栈7实验四队列12实验五二叉树的操作.19实验六图的有关操作.22实验七电话号码查询系统的设计与实现.29if(q-next=NULL)p-rear=p-front;printf(lhe %d car leave the quenen,x.num);f=l；if(仁二0)在便道上没有找到要离开的车辆，输出数据错误printf(error!the stack and the quene have no the%d carn,x.num);)void main()停车场模拟char ch;int cord;Stack *sl,*s2;Quene *p;Stacktype x;int i=1;/clrscr();/ system(clr);s 1 =(Stack*)malloc(sizeof(Stack);s2=(Stack*)malloc(sizeof(Stack);p=(Quene*)malloc(sizeof(Quene);initstack(sl);initstack(s2);初始化停车规避所栈initquene(p);初始化便道队列doprintf( n主菜单n);printf(l进入停车场n);printf(2离开停车场n”)；printf(M3 退出 n”)；printf(HnM);printf(”请输入你的选择(1, 2, 3) ”); scanf(”d”,&cord);switch(cord)/*printf(what do you want to do?n);printf(input-(Add/Del/Exit):);scanf(%c,&ch);switch (ch)*/(case 1:printf(H请输入车辆到达序号:n”)； scanf(%d,&x.num);print请输入车辆到达时间:n”)； scanf(%d,&x.arrtime);arrive(sl,p,x);车辆到达break;case 2:printfC*请输入车辆离开序号:n”)； scanf(%d,&x.num); printf(”请输入离开时间:n”)； scanf(”d”,&x.arrtime);leave(s 1 ,s2,p,x);车辆离开break;case 3:/*printf(the end!);i=0;*/exit(O);break;default:printf(输入不对，请重新输入:n); break;)while(idata);Pretraverse(t-lc);Pretraverse(t-rc);)void Inorder(BiTree t)中序遍历void Postorder(BiTree t)后序遍历 Ivoid creat(BiTree *t)char ch;/printf(”请输入数据n”)；scanf(%c,&ch);if(ch=#)*l=NULL;return;else(*t=(BiTree)malloc(sizeof(struct node); (*t)-data=ch;printf( %c 二 ch);creat(&(*t)-lc);creat(&(*t)-rc);)void main()BiTree t;systeni(nclr);int cord;doprintf(n二叉树相关操作n”);printfC1建立二叉树n”)；printf(2先序遍历二叉树n”)；printfC3中序遍历二叉树n)；printf(H4后序遍历二叉树，统计叶子结点数n”)；printfC* 5程序运行结束nu);printfCn”)；printf(”请输入你的选择(1, 2, 3, 4, 5):”)； scanf(%d,&cord);switch(cord)(case 1:creat(&t);printf(”二叉树建立完成，请继续执行其他操作n”); (break;case 2:Pretraverse(t);printf(”先序遍历完成n”)；)break;case 3:Inordcr(t);printf(”中序遍历完成n”);)break;case 4: Postorder(t);printfC*后序遍历完成n”)； printf(”叶子结果数为%3d”,m);)break;case 5:printf(H二叉树程序执行完毕！ n”)； exit(O);)while(cordn,&G-e)；输入顶点数和边数scanf(%c,&a)；printf(Input Vertex string:)；for(i=0； in； i+)(scanf(%c,&a)；G-vexsfi=a；读入顶点信息，建立顶点表for(i=0； in； i+)for(j=0； jn； j+)G-edgesi|j=O；初始化邻接矩阵printf(Input edges,Creat Adjacency Matrixn)；for(k=0； kvG-e； k+) (读入e条边，建立邻接矩阵scanf(”d%d”,&i,&j)；输入边(Vi, Vj)的顶点序号G-edgesliJjJ=l；G-edgesji=l；若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句定义标志向量，为全局变量typedef enumFALSE,TRUE Boolean；Boolean visitedMaxVertexNum:DFS：深度优先遍历的递归算法void DFSM(MGraph *G,int i)访问顶点Vi置已访问标志依次搜索Vi的邻接点以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0, 1矩阵 int j； printf(%c,G-vexsi)； visitcdi=TRUE； for(j=0； jn； j+)if(G-edgesij= 1 & ! visited。)/ (Vi,/ (Vi,DFSM(Gj);Vj) eE,且Vj未访问过，故Vj为新出发点void DFS(MGraph *G)int i；for(i=0； in； visitedi=FALSE； for(i=0； ivG-n； if(!visitedi)DFSM(Qi)；i+)i+)标志向量初始化/Vi未访问过以Vi为源点开始DFS搜索)/BFS：广度优先遍历void BFS(MGraph *G,int k)(以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i,j,f=O,r=O；定义队列int cqMaxVertexNum:标志向量初始化for(i=0； in； i+)visitcdi=FALSE；队列初始化 访问源点Vkfor(i=0； in； i+)cqlij=-l；printf(%c,G-vexsk)；/Vk己访问，将其入队。注意，实际上是将其序号入队 队非空则执行visitedk=TRUE；cqr=k： while(cqf!=-l) (i=cqf|； f=f+l；Vf 出队for(j=0； jn； j+)依次 Vi 的邻接点 Vj访问Vj访问Vj访问过Vj入队if(G-edgesi|j=l & !visited。) /Vj 未访问 printf(%c,G-vexsj)； visitedj=TRUE； r=r+1； cqrl=j；)/mainvoid main()int 1；MGraph *G；为图G中请内存空间G=(MGraph *)malloc(sizeof(MGraph)；CreatMGraph(G)；建立邻接矩阵printf(MPrint Graph DFS:，DFS(G)；深度优先遍历printf(”n，printfCPrint Graph BFS:)；BFS(G,3)；以序号为3的顶点开始广度优先遍历printf(,nM)；执行顺序：Input VertexNum(n) and EdgesNum(e): 8, 9I叩ut Vertex string: 01234567Input edges,Creat Adjacency Matrix013。021 31 42526 图G的示例374756Print Graph DFS: 01374256Print Graph BFS: 317042562. 邻接链表作为存储结构程序示例#includestdio.h#inc】ude”stdlib.h”typedef VertexNode AdjListMaxVertexNum ；/Adj Li st 是邻接表类型#define MaxVertexNum 50定义最大顶点数typedef struct node int adj vex； struct node *next：JEdgeNode；边表结点 邻接点域链域typedef struct vnode ( char vertex ； EdgeNodc *firstcdge； VertexNode；顶点表结点 顶点域边表头指针typedef struct (Adj List adj list；邻接表int n,e；( ALGraph ；图中当前顶点数和边数图类型建立图的邻接表数据结构上机实验的目的和要求通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写 及调试程序的能力。要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：(1) 输入的形式和输出值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入输出结果和错误的输入及输出结果。2、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的 调用关系。3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算 法。4、调试分析：(1) 调试过程中所遇到的问题及解决方法；(2) 算法的时空分析；(3) 经验与体会。5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。6、测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输 入规模的增长所用算法的实际运行时间的变化。void CreatALGraph(ALGraph *G)(int i,j,k；char a：EdgeNode *s；定义边表结点printf(Input VertexNum(n) and EdgcsNum(e):)；scanf(”d,%d”,&G-n,&G-e)；读入顶点数和边数scanf(%cH,&a)；printf(Input Vertex string:)；for(i=0； in； i+)建立边表scanf(”c”,&a)；G-adjlisti.vertex=a；读入顶点信息G-adj 1 ist i. firstedge=NULL:边表置为空表printf(Input edges,Creat Adjacency Listn”)；for(k=0； ke； k+) ( 建立边表 scanf(”d%d”,&i,&j)；读入边(Vi, Vj)的顶点对序号s=(EdgeNode *)malloc(sizcof(EdgcNodc)；生成边表结点s-adjvex=j；邻接点序号为js-next=G-adj 1 ist i. firstedge ；G-adjlistfi.firstedge=s;将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode)； s-adjvex=i；邻接点序号为is-next=G-adj list|j. firstedge ；G-adj 1 istj.firstedge=s:将新结点*S插入顶点Vj的边表头部)定义标志向量，为全局变量typedef enumFALSE,TRUE) Boolean；Boolean visitedMaxVertexNum:DFS：深度优先遍历的递归算法void DFSM(ALGraph *G,int i)以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode *p：printf(M%c,G-adjlisli.vertex)； 访问顶点 Vi visitedi=TRUE；标记 Vi 己访问p=G-adjlisti.firstedge；取 Vi 边表的头指针while(p)(依次搜索Vi的邻接点Vj,这里j=p-adjvexif(! visitedp-adjvex) DFSM(G,p-adjvex)； p=p-next；)void DFS(ALGraph *G)int i；if(! visitedp-adjvex) DFSM(G,p-adjvex)； p=p-next；)void DFS(ALGraph *G)int i；若Vj尚未被访问则以Vj为出发点向纵深搜索找Vi的下一个邻接点for(i=0； in： i+) visitedi=FALSE； for(i=()； in； i+) if(!visitedi)DFSM(Gi);for(i=0； in： i+) visitedi=FALSE； for(i=()； in； i+) if(!visitedi)DFSM(Gi);标志向量初始化/Vi未访问过以Vi为源点开始DFS搜索/BFS：广度优先遍历void BFS(ALGraph *G,int k)(以Vk为源点对用邻接链表表示的图G进行广度优先搜索int i,f=O,r=O；EdgeNode *p；int cqMaxVertexNum: for(i=0； in； i+) visitedi=FALSE； for(i=0； in； i+)EdgeNode *p；int cqMaxVertexNum: for(i=0； in； i+) visitedi=FALSE； for(i=0； in； i+)cqi=-l；printf(M%c,G-adjlistk.vertex)；定义FIFO队列标志向量初始化初始化标志向量访问源点Vkvisitedk=TRUE；cq(r=k； Vk己访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) (队列非空则执行i=cqf; f=f+l；/Vi 出队p=G-adj 1 isti.firstedge:取 Vi 的边表头指针while(p) (依次搜索Vi的邻接点Vj (令p-adjvex=j)if(!visitedp-adjvex) (若 Vj 未访问过printf(%c,G-adjlistp-adjvex.vertex)；访问 Vj访问过的Vj入队visitedp-adj vex =TRUE ； r=r+1: cqr=p-adjvex；找Vi的下一个邻接点p=p-next；)/cndwhile)主函数void main() int i；ALGraph *G；G=(ALGraph *)malloc(sizeof(ALGraph)；CreatALGraph(G)；printf(Print Graph DFS:)；DFS(G)；printf(n)；printf(MPrint Graph BFS: )；BFS(G3)；printf(,n,);执行顺序：Input VertexNum(n) and EdgesNum(e): 8, 9Input Vertex string: 01234567图G的示例Input edges,Creat Adjacency List0 1021 31 42526374756Print Graph DFS: 02651473Prim Graph BFS: 37140265实验七 电话号码查询系统的设计与实现一、实验性质：必做二、实验学时:4学时三、实验类型：综合四、实验目的利用数据结构课程相关知识，以C/C+作为编程语言完成一个具有一定 难度的综合实验。通过本实验，巩固和加深对线性表、栈、队列、树、图、查找、 排序等理论知识的理解；掌握现实问题的分析和解决方法，进而提高利用计算机 分析解决综合实际问题的基本能力。五、实验内容编写一个电话号码查询系统，要求按照人名顺序进行记录排序，分别按照电 话号码和人名进行查询，能将满足查询要求的记录删除。具有要求：1)2)3)4)5)6)7)数据以文件的方式存放；从文件中读取数据；按照人名对对电话本中的记录进行排序； 根据电话号码查找相关信息；根据姓名查找相关信息；删除符合条件的记录；数据输出以文件存储。实验一线性表的基本操作一、实验性质：必做二、实验学时:2学时三、实验类型：验证四、实验目的1、掌握用VC+上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存 储结构和链接存储结构上的运算。五、实验内容1) 线性表建立、插入、删除操作实现：2) 己知有序表SA, SB,其元素均为递增有序，将此两表归并成一个新有序 表SC,且SC中的元素仍然递增有序。六、程序实现struct SQListint eiemMAXSIZE;intlen;；SQList creat_SQList()/*建立顺序表*/(SQList 1;int i=0;printf(H请输入顺序表”)；scanf(u%du,&l.elemi);while(Lelem i!=0)i+；scanf(n%dM,&Lelem i);l.len=i;return 1;void print_SQList(SQList 1)/顺序表输出SQList Merge_SQList(SQList LA,SQList LB)/*合并*/()SQList SQList_insert(SQList s,int i,int x)/*插入*/intj;if(is.len)printf(插入位置不存在，else(for(j=s.len ;j=i;j-)s.elem j+l=s.elem j;s.elem i=x;s.len =s.len+l;/print_SQList( s);return s;SQList SQList_delete(SQList s,int i)/*删除*/(intj;if(is.len)printf(i位置不存在，elsefor(j=i;j=s.len ;j+)s.elem j=s.elem j+l;s.len-;/prinl_SQList( s); return s;void main()(SQList LA,LB,LC; int i,y,cord;/ clrscr();doprintf(M请输入你的选择(1, 2, 3,printf(n主菜单 n）；printfCl建立线性表n”）；printf(2插入一个元素n”)；printf(3删除一个元素n”)；printf(4合并线性表n”);printf(5退出nn);printf(Hn“);scanf(”d”,&c