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

1、华北电力大学实 验 报 告| 实验名称 数据结构实验 课程名称 数据结构 | 专业班级：网络 学生姓名： 学 号： 成 绩：指导教师：牛为华 实验日期：2011.6.17 华 北 电 力 大 学 实 验 报 告实验一：停车场管理一，实验目的1.熟悉栈和队的定义和有关操作。二，实验要求1.认真阅读和掌握实验内容。2.用栈和队解决停车场问题。3.输入和运行编出的相关操作的程序。4.保存程序运行结果 , 并结合输入数据进行分析。三，所用仪器设备1. PC机。2. Microsoft Visual Studio运行环境。四，实验方法与步骤#include"iostream"usin

2、g namespace std;/栈在这里用顺序结构实现int N; int cnum; /定义作为车牌号的变量 struct stack/定义栈 int cstack9999;/这里随便定义一个数字表示数组的长度,因为后面会根据用户输入的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(st

3、ack *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-;

4、return s->cstacks->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->ne

5、xt=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;

6、 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;

7、 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); els

8、e n=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<<"号位置

9、"<<endl; void main()/主程序 cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>&g

10、t;>>>>>>>>>>>>>>>>"<<endl<<endl; cout<<">>>> 欢迎使用停车场程序 >>>>"<<endl<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>

11、>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl<<endl; cout<<"请输入一个数作为作为停车场的最大容车量:"<

12、<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)还是离开(

13、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<&l

14、t;"输入错误!"<<endl; cout<<endl;if(flag=0) break; /对应的系统关闭程序 system("pause");六，数据与结果输入N为3实验二：约瑟夫环一，实验目的1.熟悉循环链表的定义和有关操作。二，实验要求1.认真阅读和掌握实验内容。2用循环链表解决约瑟夫问题。3.输入和运行编出的相关操作的程序。4.保存程序运行结果 , 并结合输入数据进行分析。三，所用仪器设备3. PC机。4. Microsoft Visual Studio运行环境。四，实验原理1.约瑟夫问题解决方案： 用两个指针分别指向链

15、表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。五，实验方法与步骤#include"iostream"using namespace std; struct Nodeint 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&l

16、t;=n;i+)Node* p=new Node;/新建指针p->data=n+1-i;/p的数据域赋值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;s

17、ystem(“pause”);六，数据与结果1.输入：总人数8；数到 4出列；从第 1人开始；按照理论应有出队序列：4 8 5 2 1 3 7 6. 2.实验输入输出：七，讨论总结1，循环链表（不带头结点）的建立：（1）建立一个新结点A，给其data域赋值，将其自身的next指向自己。（2）继续申请新结点B，同样赋值，把B->next=A->next，A->next=B。（3）要不断插入结点，重复（2）即可，这样就可创立一个不带头结点的循环链表。【2】约瑟夫环的顺序存储方法一，实验目的1. 熟悉顺序存储。2. 熟悉对约瑟夫的顺序存储解决算法。 二，实验要求1. 认真阅读和掌握

18、实验内容。2. 输入和运行编出的图与相关操作的程序。3. 保存程序运行结果 , 并结合输入数据进行分析。三，所用仪器设备1. PC机。2. Microsoft Visual Studio运行环境。四，实验原理#include"iostream"using namespace std;void main()int m,n,s=0,j=1;cout<<"请输入m的值："cin>>m;cout<<"请输入n的值："cin>>n;int *a=new intn;for(int i=0;i<

19、n;i+)ai=i+1;while(n!=0)if(j=m)cout<<as;j=0;if(s!=n-1)for(int i=s;i<n-1;i+)ai=ai+1;n-;j+;if(s>n-1) s=0;elsej+;s+;if(s>n-1)s=0;delete a;cout<<endl;system("pause");五，实验结果六，讨论就顺序存储来看，实现要比链式存储麻烦一些，如果元素个数较多的话，移动的次数也会迅速的增加。实验三：二叉树的遍历一，实验目的1.熟悉二叉树的定义和有关操作。2.加深理解和认识对二叉树进行遍历的递归算

20、法。二，实验要求1.认真阅读和掌握实验内容。2.对二叉树进行三种遍历。3.输入和运行给出的二叉树与相关操作的程序。4.保存程序运行结果 , 并结合输入数据进行分析。三，所用仪器设备3. PC机。4. Microsoft Visual Studio运行环境。四，实验原理1. 先序遍历：（1）访问根结点。 （2）按先序遍历原则遍历左子树。 （3）按先序遍历原则遍历右子树。2.中序遍历：（1）按中序遍历原则遍历左子树 （2）访问根结点。 （3）按中序遍历原则遍历右子树3.后序遍历：（1）按后序遍历原则遍历左子树 （2）按后序遍历原则遍历右子树 （3）访问根结点。五，实验方法与步骤#include&q

21、uot;iostream"using namespace std;struct nodeint data;node *Lchild;node *Rchild;void creatshu(node *nod)/建立二叉树int x,y;cin>>x;/左子树if(x=0) nod->Lchild=NULL;elsenode *p=new node;p->data=x;nod->Lchild=p;creatshu(nod->Lchild);cin>>y;/右子树if(y=0) nod->Rchild=NULL;elsenode *p=

22、new node;p->data=y;nod->Rchild=p;creatshu(nod->Rchild);void preorder(node *nod)/前序遍历if(nod!=NULL)cout<<nod->data<<" "preorder(nod->Lchild);preorder(nod->Rchild);void inorder(node *nod)/中序遍历if(nod!=NULL)inorder(nod->Lchild);cout<<nod->data<<&q

23、uot; "inorder(nod->Rchild);void postorder(node *nod)/后续遍历if(nod!=NULL)postorder(nod->Lchild);postorder(nod->Rchild);cout<<nod->data<<" "void main()node *head=new node;/头指针,树根cout<<"输入树根："<<endl;cin>>head->data;cout<<"请输

24、入结点(结点为空是输入0，结束也输入0),先建左子树，后建右子树:"<<endl;creatshu(head);cout<<endl<<endl;cout<<"先序为："<<endl;preorder(head);cout<<endl<<endl;cout<<"中序为："<<endl;inorder(head);cout<<endl<<endl;cout<<"后序为："<<

25、;endl;postorder(head);cout<<endl<<endl;system("pause");六，实验结果与数据 1.输入1,2,3,0,0,4,5,0,0,6,7,0,0,0,8,9,0,0,10,11,12,0,0,13,0,0,14,0,0, 按照原理先序遍历应输出：1,2,3,4,5,6,7,8,9,10,11,12,13,14 中序遍历应输出：3,2,5,4,7,6,1,9,8,12,11,13,10,14 后序遍历应输出：3,5,7,6,4,2,9,12,13,11,14,10,8,1七，讨论与总结本实验较好的体现了二叉树

26、遍历的递归思想。用递归算法编起来算法语句较为简单，但调用过程太多，非递归语句调用的次数上会有优势，但代码量会增加。实验四：图的遍历一，实验目的1. 熟悉图的邻接表表示。2. 熟悉对图的邻接表表示分别进行深度和广度优先遍历的算法。 二，实验要求1. 认真阅读和掌握实验内容。2. 对图的邻接表表示分别进行深度和广度优先遍历的算法。3. 输入和运行编出的图与相关操作的程序。4. 保存程序运行结果 , 并结合输入数据进行分析。三，所用仪器设备5. PC机。6. Microsoft Visual Studio运行环境。四，实验原理 1.图的深度优先遍历（DFS）：从图的某一点出发，先访问该点的顶点，后选

27、取一个与该点邻接且未被访问过的顶点A，在访问A后，再从A出发进行如上访问，重复此过程，直到某个顶点的所有邻接点都被访问过时，回退到尚有邻接点未被访问过的顶点，再从该顶点出发，重复上述过程，直到所有的被访问过的顶点的邻接点都被访问过，这时遍历结束。2.图的广度优先遍历（BFS）：访问图的某一顶点A，从A出发，先访问A的邻接点B1,B2,B3,B4，然后再顺序访问B1,B2,B3,B4的所有邻接的尚未访问过的全部顶点，再从这些被访问过的顶点出发，逐次访问与它们连接且未被访问过的顶点。以此类推，直到所有顶点都被访问完为止。五，实验方法与步骤#include"iostream"us

28、ing namespace std;struct Vertex /因为边节点没有权值，所以想用一种同构的结构来简化结构，让程序可读性更高int adjvex;/顶点域Vertex *next;int visit;/是否访问过;/初始化邻接表void creat(Vertex v,int n)int k,i,j;for(i=0;i<n;i+)vi.adjvex=i; /给顶点标上序号Vertex *s=NULL;s=v; /s作为滚动指针，不用分配实际空间for(i=0;i<n;i+)cout<<"请输入Vertex"<<i<<

29、"有几条邻接的边："cin>>k;if(k!=0)for(j=0;j<k;j+)Vertex *p=new Vertex;cout<<"请输入和Vertex"<<i<<"邻接的点的序号："cin>>p->adjvex;s->next=p;s=p;p->next=NULL; /连接过程else vi.next=NULL;s=v+i+1; /每给一个顶点初始化完后，要将s指针指向下一个顶点cout<<endl;/深度优先搜索void depth

30、(Vertex v,int x)cout<<vx.adjvex<<" "vx.visit=1;Vertex *p=new Vertex;p=vx.next;while(p!=NULL)x=p->adjvex;if(vx.visit=0)depth(v,x);p=p->next;/广度优先搜索void breadth(Vertex v,int x)cout<<vx.adjvex<<" "vx.visit=1;int f=0; /队列指针int r=0;int q20;Vertex *p=new V

31、ertex;p=vx.next;dowhile(p!=NULL)x=p->adjvex;if(vx.visit=0)qr=x; /入队r+;cout<<vx.adjvex<<" "vx.visit=1;p=p->next;if(f!=r)/v出队x=qf;f+;p=vx.next;while(f!=r) | (p!=NULL); /书上的算法有问题void main()int n,x;cout<<"请输入定点个数："cin>>n;Vertex *v=new Vertexn;cout<<

32、;endl;creat(v,n);for(int i=0;i<n;i+) vi.visit=0;cout<<"请输入深度搜索的开始顶点号："cin>>x;cout<<endl;cout<<"深度优先搜索顺序为："depth(v,x);cout<<endl<<endl;for(int i=0;i<n;i+) vi.visit=0;cout<<"请输入广度搜索的开始顶点号："cin>>x;cout<<endl;cout&

33、lt;<"广度优先搜索顺序为："breadth(v,x);cout<<endl;system("pause");六，结果与数据 输入以下图的信息并进行遍历： 0213七，讨论与结论重点在于广度优先搜索与深度优先搜索的算法，以及一开始图的初始化问题。实验五：哈希表一，实验目的1. 熟悉建立哈希表的方法。二，实验要求1. 认真阅读和掌握实验内容。2. 输入和运行编出的相关操作的程序。3. 保存程序运行结果 , 并结合输入数据进行分析。三，所用仪器设备1. PC机。2. Microsoft Visual Studio运行环境。四，实验方法与步

34、骤#include"iostream"#include"string" #include"fstream"using namespace std;#define NULL 0 unsigned int key; unsigned int key2; int *p; struct node /建节点 char name8,address20; char num11; node * next; ; typedef node* pnode; typedef node* mingzi; node *phone; node *nam; node

35、 *a; /void hash1(char num11) /以电话号码为关键字建立的哈希函数int i=0;int s=0;for(i=0;i<11;i+)s=(int)numi-48)+s; key=s%7; /void hash2(char name8) /哈希函数 int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input() /输入节点 node *temp; temp = new node; temp->next=NULL; cout<&

36、lt;"输入姓名："<<endl; cin>>temp->name; cout<<"输入地址："<<endl; cin>>temp->address; cout<<"输入电话："<<endl; cin>>temp->num; return temp; int apend() /添加节点 node *newphone; node *newname; newphone=input(); newname=newphone; ne

37、wphone->next=NULL; newname->next=NULL; hash1(newphone->num); hash2(newname->name); newphone->next = phonekey->next; phonekey->next=newphone; newname->next = namkey2->next; namkey2->next=newname; return 0; void create() /新建节点 int i; phone=new pnode20; for(i=0;i<20;i+)

38、 phonei=new node; phonei->next=NULL; void create2() /新建节点 int i; nam=new mingzi20; for(i=0;i<20;i+) nami=new node; nami->next=NULL; void list() /显示列表 int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) cout<<p->name<<'_'<<p->address<<'_&

39、#39;<<p->num<<endl; p=p->next; void list2() /显示列表 int i; node *p; for(i=0;i<20;i+) p=nami->next; while(p) cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl; p=p->next; void find(char num11) /查找用户信息 hash1(num); no

40、de *q=phonekey->next; while(q!= NULL) if(strcmp(num,q->num)=0) break; q=q->next; if(q) cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"无此记录"<<endl; void find2(char name8) /查找用户信息 hash2(nam

41、e); node *q=namkey2->next; while(q!= NULL) if(strcmp(name,q->name)=0) break; q=q->next; if(q) cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"无此记录"<<endl; void save() /保存用户信息 int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) fst