华北电力大学数据结构实验报告

华北电力大学实验报告||实验名称算法与数据结构综合实验课程名称 专业班级： 学生姓名：学号： 成绩：指导教师： 实验日期：（实验报告如打印，纸张用A4,左装订；页边距：上下2.5cm,左2.9cm,右2.1cm；字体：宋体小四号，1.25倍行距。）（实验一停车场管理）（实验二约瑟夫环）（实验三二叉树的存储及遍历）（实验四图的存储及遍历）（实验五哈希表的设计）一、 实验目的及要求二、 所用仪器、设备三、 实验原理四、 实验方法与步骤五、 实验结果与数据处理六、 讨论与结论（对实验现象、实验故障及处理方法、实验中存在的问题等进行分析和讨论，对实验的进一步想法或改进意见）七、 所附实验输出的结果或数据实验一停车场管理一、 实验内容设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。二、 实验目的掌握栈和队列的定义和实现，学习利用栈和队列解决实际问题。三、 所用仪器、设备计算机，VC++2010。四、 实验方法与步骤停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下：当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。1、 用栈模拟停车场，用队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。2、 每次输入完进行输出操作：若是车辆到达，输出汽车在停车场内或便道上的停车位置；若是车辆离去，输出离开的车牌号。3、 其中栈以顺序结构实现，队列以链表结构实现。详细步骤：1、定义栈：typedefstruct（chardata[stacksize];inttop;}stack；初始化栈：voidStackinit(stack*x)voidStackinit(stack*x)(inti；x->top=0；for(i=0；i〈=stacksize；i++)x->data[x->top]=NULL;}2、 定义队列：typedefstructNode(chardata；structNode*next；}Node；typedefstruct(structNode*head；structNode*rear；}squeue；初始化队列：intQueueinit(squeue*Q)intQueueinit(squeue*Q)(Q->head=(Node*)malloc(sizeof(Node))；if(Q->head!二NULL)(Q->head->next=NULL；Q->rear=Q->head；returnOK；}elsereturnERROR；}3、 处理车辆到达的情况intArrival(stack*s,squeue*Q)intArrival(stack*s,squeue*Q)(charp；Node*t；cout<<"请输入车牌号："<<endl；cin>>p；if(s->top<stacksize)(s->top++；cout<<p<<"号车辆停在车场第"<<s->top<<"位置"<<endl；s->data[s->top]=p；returnOK；}else(cout<<p<<"号车须停在便道等待！"<<endl；t=(Node*)malloc(sizeof(Node))；t->data=p;t->next=NULL;Q->rear->next=t;Q->rear=t;returnOK;}}处理车辆离开voidLeave(stack*s,stack*t,squeue*Q)voidLeave(stack*s,stack*t,squeue*Q)(introom;charp,q;Node*n;n二newNode;if(s->top>0)(while(1)(cout<<"请输入车在车站中的位置1 "<<s->top<<endl;cin>>room;if(room>=1&&room〈=s->top)break;}while(s->top>room)(t->top++;t->data[t->top]=s->data[s->top];s->data[s->top]=NULL;s->top--;}p=s->data[s->top];s->data[s->top]=NULL;s->top一;while(t->top>=1)(s->top++;s->data[s->top]=t->data[t->top];t->data[t->top]=NULL;t->top——;}cout<<"离开车辆的车牌号为："<<p<<endl；if((Q->head!二Q->rear)&&s->top<stacksize)(n=Q->head->next;q=n->data;s->top++;cout<<"便道的"<<q<<"车进入车场第"<<s->top<<"位置"<<endl;Q->head->next=n->next;if(n二二Q->rear)Q->rear=Q->head;s->data[s->top]=q;delete(n);}elsecout<<"便道里没有车！"<<endl;}elsecout<<"车站里没有车！"<<endl;}4、主程序voidmain()voidmain()(stacks,t;squeueQ;intch;Stackinit(&s);Stackinit(&t);Queueinit(&Q);while(1)(cout<<"1.车辆到达2.车辆离开 3.退出系统"<<endl;while(1)(cin>>ch;if(ch>=1&&ch<=3)break;elsecout<<"请选择：1 2 3.”<<endl;}switch(ch)(case1:Arrival(&s,&Q);break；case2：Leave(&s,&t,&Q)；break；case3：exit(0)；default：break；}}system("pause")；}五、实验结果1、进入车站：IM]C:\Us-ers\qykj\docurnents\visualstudio2010\Prcjects\suhang\Debug\l23-.exe-「车辆到达A车辆离开3.退出系统1鬲输入车牌号二a匚1.1E辆停在车场第1恒置

:辆到达2.车辆离开3.退出系统请输入车牌号'b号车辆停在车场第w也置「车辆到达2一车辆展开1恒输入车牌号二Z号车辆停在车场第3■置「车辆到达A车辆展开1请输入车牌号二3.退出系统3.退出系统2、车站已满进入便道:'青输人车牌号::号车辆停在车场第3也置「车辆到达2■车辆^开［青输入车牌号：:号车须停在便道箸但「车辆到达2■车摘舄开:青输入车牌号：d号车须停在便道等但「车辆到达2■车摘裔开3■退出系统3■退出系统3■退出系统3、车辆离开:卷袂开3•退出系统章输入车在车站中的位置1——31卜车辆到达2-车翩离开3.退出系统备输入车在车站中的位置1——3「车辆到达A车辆离开3.退出系统六、总结与体会1、 虽然实验中遇到了一些问题，但最后在老师的帮助下问题很快就解决了，主要是由于刚开始接触算法不是很熟悉。2、 通过《停车场管理》的实验学习使我基本上理解并学会了用栈的先进后出和队列的先进先出的原理去解决实际问题的思想和方法。但是在编程方面还是很欠缺，还要加强学习。实验二约瑟夫环一、 实验内容约瑟夫（Joeph）问题的一种描述是：编号为1,2，…,的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。二、 实验目的掌握顺序表和链表的定义和实现，学习利用顺序表和链表解决问题。三、 所用仪器、设备计算机，VC++2010。四、 实验方法与步骤分析约瑟夫问题：n个人围成圈，提供密码m，从第一个人开始，数到第m个人，删除，从下一个人开始进行第二轮操作，直到所有人都出列。n个人围圈，形成线性关系；处理为逐个删除，故用链式结构合适；又人员围成圆圈，所以此链式结构采用循环方式较好；排号按照一个方向进行，故数据结构采用带头结点的单向循环链表。假设人员以首次的编号命名，对每个人员采用编号加以描述。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。详细步骤：1、 定义约瑟夫环：typedefstructNode(intdata;structNode*next;}*circularList;2、 建立约瑟夫环：voidCreatList(circularList*head,constintn)voidCreatList(circularList*head,constintn)(inti;Node*p,*q;q二newNode;for(i=1;i〈=n;i++)(p=newNode;p->data=i;p->next=NULL;if(*head二二NULL)(*head二q二p;q->next=*head;}else(p->next=q->next;q->next=p;q=p;}}}3、 进行约瑟夫游戏：voidJoseph(circularList*head,intt)voidJoseph(circularList*head,intt)(Node*p,*q,*b;b=newNode;intr=1;p=q=*head;while(r)(for(inti=1;i<=t;i++)(p=q;q=q->next;}if(p二二q)r=0；b=q；p->next=q->next；q=q->next；cout<<"第"<<b->data<<"个人出列"<<endl；delete(b)；}head二NULL；}4、主程序voidmain()voidmain()(circularListhead二NULL；intn,m；cout<<"请输入总人数n=”；cin>>n；while(n<=0)(cout<<"输入错误！请重新输入！"<<endl；cout<<"请输入总人数n=”；cin>>n；}cout<<"请输入m=”；cin>>m；while(m<=0)(cout<<"输入错误！请重新输入！"<<endl；cout<<"请输入m=”；cin>>m；}CreatList(&head,n)；cout<<"出列顺序如下："<<endl；Joseph(&head,mT)；cout<<"约瑟夫环游戏完成！"<<endl；system("pause")；}五、实验结果1、输入总人数n

C:\U5ers\qykj\documents\uisuaIstudio2010\Project5\suhang\Deb^i2、输入密码m,进行约瑟夫环游戏C:\LIsersVqyki\doeuments\vi汩日Istudio2010\Prcisct5\suh洽nq\Debuq\l23.eye数A>-b-RSzTf总冬股个2-/个数A>-b-RSzTf总冬股个2-/个0-/个1-/个53,44Jm,”-iLrn-iLrnTi/&-13--H2L5-117-L4L8-7出出出瑟按六、总结与体会1、 刚开始对头结点的运用不是很熟悉，通过本次实验加深了我对头结点、链表和顺序表的认识。2、 这次实验相对来说比较简单，但中间也出现了一些错误，在老师的帮助下问题很快就解决了。3、 认识到自己的编程技术还是比较次的，以后一定多多练习。实验三二叉树的存储及遍历一、 实验内容1、按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树。2、然后按先序、中序、后序顺序分别遍历这棵二叉树。二、 实验目的1、树是一种重要的非线性数据结构，要求掌握二叉树的两种基本的存储结构，及各种操作的算法实现（建立、遍历）以及应用。2、 本实验训练的要点是：递归算法的设计方法以及二叉树的应用。三、 所用仪器、设备计算机，VC++2010。四、 实验方法与步骤1、编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建立。2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，采用递归实现，遍历算法有先序、中序和后序遍历算法详细步骤：1、 定义树：typedefstructbtnode(chardata;structbtnode*Lchild,*Rchild;}*Tree;2、 建立二差树：voidCreateTree(Tree*t)voidCreateTree(Tree*t)(charx;cout<<"请输入字母："<<endl;cin>>x;if(x二二'#')*t=NULL;else(*t=(btnode*)malloc(sizeof(btnode));(*t)->data=x;CreateTree(&((*t)->Lchild));CreateTree(&((*t)->Rchild));}}3、先序遍历：voidPrecorder(Treet)voidPrecorder(Treet)(if(t)(cout<<t->data；Precorder(t->Lchild)；Precorder(t->Rchild)；}}4、 中序遍历：voidInorder(Treet)voidInorder(Treet)(if(t)(Inorder(t->Lchild);cout<<t->data;Inorder(t->Rchild);}}5、 后序遍历：voidPostorder(Treet)voidPostorder(Treet)(if(t)(Postorder(t->Lchild);Postorder(t->Rchild);cout<<t->data;}}6、 主程序：voidmain()voidmain()(Treet;CreateTree(&t);cout<<"先序遍历："<<endl;Precorder(t);cout<<endl;cout<<"中序遍历："<<endl;Inorder(t);cout<<endl;cout<<"后序遍历："<<endl;Postorder(t);cout<<endl;system("pause");}五、实验结果

1、建立二叉树■CUs-ers\qylcj\documents\visuaIstudio2OlO^Prcjects\suhang\Debug\l23.ex情输入字母;&输入字母:｝输入字母:&输入字母:&输入字母!&输入字母:｝输入字母:｝输入字母:§输入字母:章输入字母:F尹输入字母:§输入字母:寿输入■字母:2、对二叉树进行遍历历历历=品遍EF遍FE遍即任序CD序DA序BF按#先祯中CB后CD请六、总结与体会1、 树状结构中的重点自然是二叉树。对于二叉树的很多操作都是基于对二叉树的遍历，掌握了如何遍历，很多问题也就迎刃而解了，比如对二叉树结点的查找访问、统计二叉树中叶子结点的数目、求二叉树的深度等。2、 学习算法的目的是利用算法解决实际问题。会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。比如数值转换，括号匹配的检验，检验平衡二叉树等。实验四图的存储及遍历一、 实验内容1、 按次序输入图中结点的值，建立一个以邻接表存储的图。2、 然后分别进行深度优先遍历和广度优先遍历。二、 实验目的熟悉图的两种常用的存储结构，邻接矩阵和邻接表。建立无向图，用邻接表存储结构存储。在邻接表存储结构上实现深度优先遍历和广度优先遍历。三、 所用仪器、设备计算机，VC++2010。四、 实验方法与步骤1、编程实现构造图的算法，适合任意合法输入的无向图的建立。2、编程实现图在邻接表存储结构存储方式下，实现图的深度优先遍历和广度优先遍历。详细步骤：1、 定义图的结构：typedefstructEdgeNode(intadjvex;structEdgeNode*next;};typedefstructVnode(intvertex;EdgeNode*link;}Adjlist[MAX];2、 建立图：voidbuild_adjlist(Adjlist*ga)voidbuild_adjlist(Adjlist*ga)(intn,e,i,j;EdgeNode*p,*q;cout<<"请输入顶点数：”；cin>>n;while(n<2)(cout<<"请重新输入！"<<endl；cin>>n；}for(intm=1；m〈=n；m++)(ga[m]->link=NULL;ga[m]->vertex二m;}cout<<"请输入边数：";cin>>e;for(intk=0;k<e;k++)(cout<<"读入顶点对：";cin>>i;cin>>j;p=newEdgeNode;p->adjvex二j;p->next=ga[i]->link;ga[i]->link=p;q二newEdgeNode;q->adjvex二i;q->next=ga[j]->link;ga[j]->link=q;}}3、深度优先遍历：voiddfs(Adjlist*g,intv0,intvisited[])voiddfs(Adjlist*g,intv0,intvisited[])(cout<<v0;visited[v0]=1;EdgeNode*p;p=newEdgeNode;p=g[v0]->link;while(p!=NULL)(if(visited[p->adjvex]==0)(dfs(g,p->adjvex,visited);}elsep=p->next;}}4、 广度优先遍历：voidbfs(Adjlist*g,intv0,intvisited[])voidbfs(Adjlist*g,intv0,intvisited[])(intv;visited[v0]=1;cout<<v0;EdgeNode*p;p=newEdgeNode;p=g[v0]->link;squeue*q;q二newsqueue;q->f=q->r=0;do(while(p!二NULL)(v=p->adjvex;if(visited[v]==0)(cout<<v;q->data[q->r]=v;q->r=q->r+1;visited[v]=1;}p=p->next;}if(q->f!=q->r)(v=q->data[q->f];q->f=q->f+1;p=g[v]->link;}}while((p!二NULL)&&(q->f!=q->r));}5、 主程序：voidmain()voidmain()(Adjlistga;build_adjlist(&ga);intvisited[MAX];

for(inti=1；i〈=MAX；i++)visited[i]=0；cout<<"深度优先遍历："<<endl;dfs(&ga,1,visited);cout<<endl;for(inti=1;i<=MAX;i++)visited[i]=0;cout<<"广度优先遍历："<<endl;bfs(&ga,1,visited);cout<<endl;system("pause");}五、实验结果1、输入顶点数和边数C;\Uaers\qycument5\vi5U□Istudio2010\Proiect5\su入入顶:;点魏对顶边点入入顶:;点魏对顶边点2、输入顶点对J-C:\Users\qyki\dorumentsXuisualstudie2010\Project5\suhang\Debtig，\123防费入项点数德榆输入恒珈10牍入顶点对：13牍入顶点对：12牍入顶点对；37牍人顶点对;3£精入顶点对；25传入顶点对：24传入顶点对：?牍入顶点对：6牍入顶点对：5牍入顶点对：43、图的深度优先遍历和广度优先遍历J-C;\Userocument5\yi5ualstudio2O1Q\Project5\siihang\Debug\123.exe惨入顶点对！24情入顶点对：？fi悚入顶点对：6S棣入顶点对；5苗入顶点对：4京度优先遍历，12478563广度任先遍历：12345678请按任意键继续.六、总结与体会1、 本次试验设计内容比较多，虽然实验过程中多次出现问题，但通过老师的帮助和多次调试最终得到解决。2、 通过本次试验，对图的建立有了更深的了解，对书上的代码进行了实现，熟悉并掌握了dfs和bfs算法，对图结构的运用有了进一步的认识。实验五哈希表的设计一、 实验内容设计哈希表实现电话号码查询系统。要求实现以下功能：（1） 哈希表中每个记录有下列数据项：电话号码、用户名、地址；（2） 从键盘输入各记录，以电话号码为关键字建立哈希表（至少要有12个以上的记录，哈希表的长度为8）；（3） 采用链地址法解决冲突；（4） 显示建立好的哈希表，并在哈希表上查找、删除和插入给定关键字值得记录。二、 实验目的熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。建立哈希表，采用除留余数法进行哈希表的散列，即以电话号码作为主关键字，将电话号码的11位相加，按照模7取余。3.解决冲突用链地址法。三、 所用仪器、设备计算机，VC++2010。四、 实验方法与步骤1、 要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码为关键字进行查找，所以本问题要用到一个哈希函数，进行哈希查找。2、 在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要用电话号码为关键字建立哈希表，所以该链表结点它是由四个域组成，name[8]、num、 ads[20]、next其中num[是为以电话号码为关键字域，存放关键字key；address[20]为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。详细步骤：1、 定义哈希表的结构：structEdgenode(charname[8];doublenum;charads[20];structEdgenode*next;};typedefstructnode(intdata;Edgenode*link;}hashlist[MAX];2、 建立哈希空表：voidbuildlist(hashlist*h)voidbuildlist(hashlist*h)(for(inti=0;i<MAX;i++)(h[i]->data=i;h[i]->link=NULL;}}3、获取关键字key:intkeygain(doublenum)intkeygain(doublenum)(inta,sum=0;a二num/1000000;while(a>1)(sum+=a%10;a=a/10;}a二num-floor(num/1000000)*1000000；while(a>1)(sum+=a%10；a二a/10；}returnsum%7;}4、输入信息函数：voidinput(hashlist*h)voidinput(hashlist*h)(Edgenode*p;p=newEdgenode;charname[8],address[8];doublenumber;intkey;cout<<"请输入姓名”<<endl;cin>>name;cout<<"输入手机号"<<endl;cin>>number;cout<<"输入地址"<<endl;cin>>address;key二keygain(number);p=h[key]->link;if(p!二NULL)(while(p->num!二number&&p->next!二NULL)p=p->next;if(p->num=二number)cout<<"你输入的信息已经存在"<<endl;else(Edgenode*q=newEdgenode;strcpy(q->name,name);strcpy(q->ads,address);q->num=number;q->next=NULL;p->next=q;}}else(Edgenode*q=newEdgenode;strcpy(q->name,name);strcpy(q->ads,address)；q->num=number；q->next=NULL；h[key]->link=q；}}5、查找函数：voidfindhash(hashlist*h)voidfindhash(hashlist*h)(Edgenode*p,*q;intx;intkey;doublenum2;cout<<"请输入要查找的电话："<<endl;cin>>num2;key二keygain(num2);p=newEdgenode;p=h[key]->link;if(p二二NULL)(cout<<"您输入的信息不存在！"<<endl;}else(while(p->num!二num2&&p->next!二NULL)p=p->next;if(p->num=二num2)(cout<<"姓名："<<p->name<<" "<<"电话："<<setprecision(11)<<p->num<<" "<<"地址："<<p->ads<<endl;cout<<"您是否要删除这个信息？1：是；2：否"<<endl;cin>>x;if(x==1)(if(h[key]->link=二p)h[key]->link=p->next;else(q二newEdgenode;q=h[key]->link;while(q->next=二p)q=q->next;q->next=p->next;delete(p);}cout<<"删除成功"<<endl；}}}}6、 输出函数：voidoutput(hashlist*h)voidoutput(hashlist*h)(Edgenode*p;p=newEdgenode;for(inti=0;i<7;i++)(p=h[i]->link;while(p!二NULL)(cout<<"姓名："<<p->name<<" "<<"电话："<<setprecision(11)<<p->num<<" "<<"地