华北电力大学实验报告||实验名称数据结构实验课程名称数据结构||专业班级：学生姓名：学号：成绩：指导教师：实验日期：2015/7/3实验报告说明：本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。
编译环境：visual studio 2010使用语言：C++所有程序经调试均能正常运行实验目录实验一约瑟夫环（基于链表和数组）实验二简易停车场管理实验三二叉树的建立和三种遍历实验四图的建立和两种遍历实验五哈希表的设计实验一：约瑟夫环一、实验目的1.熟悉循环链表的定义和有关操作。
二、实验要求1.认真阅读和掌握实验内容。
2．用循环链表解决约瑟夫问题。
3.输入和运行编出的相关操作的程序。
4.保存程序运行结果 , 并结合输入数据进行分析。
三、所用仪器设备1.PC机。
2.Microsoft Visual C++运行环境。
四、实验原理1.约瑟夫问题解决方案：用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。
五、代码1、基于链表#include<iostream.h>using namespace std;struct Node{int data;Node* next;};void main(){int m,n,j=1;cout<<"请输入m的值：";cin>>m;cout<<"请输入n的值：";cin>>n;Node* head=NULL;Node* s=new Node;for(int i=1;i<=n;i++){Node* p=new Node;p->data=n+1-i;p->next=head;head=p;if(i==1) s=head;}Node* p=new Node;p=head;s->next=head;while(p!=s){while(j!=m){p=p->next;s=s->next;j++;}cout<<p->data;s->next=p->next;delete p;p=s->next;j=1;}cout<<p->data<<endl;delete p;}2、基于数组#include<iostream.h>void main(){int m,n,s=0,j=1;cout<<"请输入m的值：";cin>>m;cout<<"请输入n的值：";cin>>n;int *a=new int[n];for(int i=0;i<n;i++)a[i]=i+1;while(n!=0){if(j==m){cout<<a[s];j=0;if(s!=n-1){for(i=s;i<n-1;i++)a[i]=a[i+1];}n--;j++;if(s>n-1) s=0;}else{j++;s++;if(s>n-1)s=0;}}delete []a;cout<<endl;}六、实验结果1.输入：总人数8；数到 4出列；从第 1人开始；按照理论应有出队序列：4 8 5 2 1 3 7 6.2.实验输入输出：实验二：停车场管理一、实验目的1.熟悉栈和队的定义和有关操作。
二、实验要求1.认真阅读和掌握实验内容。
2．用栈和队解决停车场问题。
3.输入和运行编出的相关操作的程序。
4.保存程序运行结果 , 并结合输入数据进行分析。
三、所用仪器设备1.PC机。
2.Microsoft Visual C++运行环境。
四、代码#include<iostream.>using namespace std;//栈在这里用顺序结构实现int N;int cnum; //定义作为车牌号的变量struct stack//定义栈{int cstack[9999];//这里随便定义一个数字表示数组的长度,因为后面会根据用户输入的N值作为停车场能够停车的数量.int top;int size;};struct node//定义队列节点的类型{int nnum;node *next;} ;struct queue//定义队列{node *front,*rear;};void initstack(stack *s)//初始化栈{s->top=-1;}int instack(stack *s,int x)//元素进栈返回值类型为int 这个作为flag使用{ //int 元素进栈n;if(s->top==N-1){cout<<"停车场已满!车将会停在便道上。
"<<endl;return 0;}else{s->cstack[++(s->top)]=x;return 1;}}int outstack(stack *s)//元素出栈{if(s->top<0){cout<<"目前停车场内一辆车也没有"<<endl;return 0;}else{s->top--;return s->cstack[s->top+1]; //帮刚才出栈的那台车的号码返回}}void initqueue(queue *q)//初始化队列这里也想写成(*front,*rear){q->front=new node;q->rear=q->front;q->front->nnum=0;q->front->next=NULL;} //队列初始化要涉及到front和rear指针void inqueue(queue *q,int num1)//元素进队列{node *p=new node;p->nnum=num1;p->next=NULL;q->rear->next=p;q->rear=p;q->front->nnum++;//头结点的数据域放上便道上所停车的辆数}int outqueue(queue *q)//元素出队列{ node* p;int n;if(q->front==q->rear)return 0;else{p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;n=p->nnum;delete p;q->front->nnum--;return n;}}void carrival(stack *s,queue *q,int x)//处理车辆到达的情况{int flag;flag=instack(s,x); //退出及返回值都正常if(flag==0) //停车场满{inqueue(q,x); // 在主程序部分的确是这个位置****************************cout<<"车牌号为"<<x<<"的车停在便道上第"<<q->front->nnum<<"号位置."<<endl;}else{cout<<"车牌号为"<<x<<"的车停在停车场第"<<s->top+1<<"号位置."<<endl; //细节：数组是从0记位的}}void carleave(stack* s1,stack* s2,queue *q,int x)//处理车辆离开{int y;int a,n=0;while((s1->top>-1)&&(n==0)){y=outstack(s1);if(y!=x){a=instack(s2,y);}elsen=1;}if(y==x){cout<<"车牌号为"<<x<<"的车离开停车场"<<endl;while(s2->top>-1){y=outstack(s2);n=instack(s1,y);}a=outqueue(q);if(a!=0){ y=a;n=instack(s1,y);cout<<"车牌号为"<<y<<"的车开进停车场并停在"<<s1->top+1<<"号位置"<<endl;}}}void main()//主程序{cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>"<<endl<<endl;cout<<">>>> 欢迎使用停车场程序 >>>>"<<endl<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>"<<endl<<endl;cout<<"请输入一个数作为作为停车场的最大容车量:"<<endl;cin>>N;//这里N将作为栈能存放元素的数量while(N<=0){cout<<"输入错误，请再输入:"<<endl;cin>>N;}char ch1;stack *s1,*s2;queue *q;int x;int flag;s1=new stack;s2=new stack;q=new queue;initstack(s1);initstack(s2);initqueue(q);flag=1;for(;;){cout<<"车辆是到达(A)还是离开(D)?请输入车辆的牌号："<<endl;cin>>ch1>>x;switch(ch1){case'A':case'a':carrival(s1,q,x);break;case'D':case'd':carleave(s1,s2,q,x);break;case'E':case'e':flag=0;cout<<"停车场系统即将关闭"<<endl;break;default:cout<<"输入错误!!"<<endl;}cout<<endl;if(flag==0)break; //对应的系统关闭程序}}五、实验结果输入N为3实验三：二叉树的遍历一、实验目的1.熟悉二叉树的定义和有关操作。