数据结构实验报告_24.docx

数据结构实验报告实验一：约瑟夫问题1、实验目的1）掌握用VC6.0上机调试线性表的基本方法，2）掌握线性表的基本操作，如插入、删除、检索等在链式存储结构上的运算2、实验环境（硬/软件要求）：Windows XP + VC6.03、实验内容约瑟夫问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，先从某个人从1开始报数，报到m的人出列，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下去，直到所有人全部都出列为止试设计一个程序，求出出列顺序4、实验设计思想在实践约瑟夫问题时的关键是用两个指针把一个移动的，一个指向要删除的节点，另外要注意保留头指针第一步是建立一个循环的单向链表第二步是运用指针遍历链表同时计数到第m个时将其删除此时指针指向不变其格式如下：output(struct Joseph *head) //输出出列情况{int i,j=1;struct Joseph *p1,*p2;p1=p2=head; //p1 、p2都指向头指针for(i=1;ip1=p1->next; //从第M个人开始报数，所以p1指针依次后移，指向第m个人while(n>0){for(i=1;i{p2=p1;p1=p1->next; //开始报数报到s前p1 p2依次后移}printf("第%d个出列的人是:%d\n",j,p1->num);p2->next=p1->next;p1=p2->next; //此人出列，将p1->next赋给p2->next，将p1所指向的结点删掉n--; //人数减少1j++; // 出列人数加1}} 5、程序清单 /*运行环境VC*/#include#include#include#define LEN sizeof(struct Joseph)struct Joseph //定义joseph{int num;struct Joseph *next;};int n,s,m;print(struct Joseph *head) //打印链对中的信息{struct Joseph *p; //p指针p=head; //将p指向头指针printf("%d个人的代号如下:\n",n);do{printf("%d ",p->num);p=p->next;}while(p!=head); //依次输入每个人的代号printf("\n");}output(struct Joseph *head) //输出出列情况{int i,j=1;struct Joseph *p1,*p2;p1=p2=head; //p1 p2都指向头指针for(i=1;ip1=p1->next; //从第M个人开始报数，所以p1指针依次后移，指向第m个人while(n>0){for(i=1;i{p2=p1;p1=p1->next; //开始报数，报到s前p1、p2依次后移}printf("第%d个出列的人是:%d\n",j,p1->num);p2->next=p1->next;p1=p2->next; //此人出列，将p1->next赋给p2->next，将p1所指向的结点删掉n--; //人数减少1j++; // 出列人数加1 } }struct Joseph *create() //建立链队列{int i;struct Joseph *head;struct Joseph *p1,*p2;printf("请输入总人数(输入0退出程序):\n");scanf("%d",&n);if(n==0)exit(0);//退出for(i=1;i{p1=(struct Joseph*)malloc(LEN);p1->num=i;if(i==1)head=p1;elsep2->next=p1;p2=p1;}p2->next=head; //将整个链队构成一个环形print(head);printf("请输入从第几个人开始报数:\n");scanf("%d",&m);printf("数到第几个人出列:\n");scanf("%d",&s);return head;}main(){struct Joseph *head;while(1){head=create();output(head);system("pause");system("cls");}}6、实验心得在约瑟夫问题中，着重训练的是链表的应用，尤其是链表中结点的删除、检索等。

由于单向链表等线性表的操作基本思想是一致的，因此通过对单向链表的 练习来加深对线性表的理解 在本实验中，需要解决的问题的重点是怎样找到要删除的结点因此，我首先考虑解决这个问题，即应用循环语句来找到满足条件的结点，我选用了if循环语句然后应用指针实现查找过程在弄清出这些之后，在建立一个单向链表即形成程序在经过调试改正一些细节即可在编辑的过程中，将所学的知识充分应用于实践，虽然遇到了一些问题，比如说不知从何下手，不过通过仔细考虑找出问题的关键和参考资料并逐步编辑出程序从而注意到了一些细节问题，例如：头指针的问题、*p1,*p2之间在不同的函数中不同的关系的区分以及函数位置的前后和声明的关系等等这些只有在真的去实践时才能意识到的小问题给我带来了很大的困惑这次的实验让我重新熟悉了C++的编辑环境，为以后的实验奠定了基础 病人看病模拟程序 1、实验目的1）掌握队列的定义；2）掌握队列基本操作的实现，并能用于解决实际问题2、实验内容编写一个程序,反映病人到医院看病排队等医生的过程.在病人排除过程中,主要重复两件事:A：病人到达诊室,将病历本交给护士,排到等待队列中候诊.B：护士从等待队列中取出下一位病人的病历,该病人进入诊室就诊要求模拟病人等待就诊这一过程,程序采用菜单方式,其选项及功能说明如下:(a)排队: 输入排队病人的病历号,加入病人排队队列中(b)就诊: 病人排队队列中最前面的病人就诊,并将其从队列中删除(c)查看排队:从队首到队尾列出所有的排队病人的病历号(d)下班: 退出运行3、实验环境Microsoft Visual C++ 6.04、实验设计思想病人看病，需要进行插入和出队程序。

这与队列的操作顺序完全相同，具有先进先出的顺序，只在对头进进行输出在对尾进行插入操作，故此问题可以用队列这种特殊的数据结构实现在具体的实现过程中需要进行数据的插入即病人入队操作在程序中实现数据的输出处理即病人就诊过程其中还需设置一个实现对队列中数据的遍历操作函数以及一个退出函数即查看和下班在设计时，首先应对相应的数据结构以及相应的对头指针进行定义，其具体格式为：typedef struct qnode{ int data;struct qnode *next;} qnode; //链队结点类型typedef struct{qnode *front,*rear;} qutype; //链队类型再次，通过四个函数实现具体的操作，其定义格式如下：paidu(qutype *q );jiuzhen(qutype *q);chakan(qutype *q);xiaban(qutype *q);5、程序源代码及解释#include#include#include#define null 0 typedef struct node { int data;struct node *next; //连队节点定义}Qnode, *Queuepre;typedef struct{ Qnode *front,*rear}LQueue; //将对头指针和队尾指针定义为一个结构体void paidui(LQueue *Q) //实现数据节点的插入函数{Qnode *p;int num,m;coutcin>>m;for(int i=0;i{coutcin>>num;p=(Queuepre)malloc(sizeof(Qnode));//malloc()函数生成一个新节点p->data=num;p->next=null;//Q->rear->next=p;Q->rear=p;//将节点插入到队列中}}void jiuzhen(LQueue &Q)//出队函数的实现{Queuepre q;int m;q=Q.front->next;//取出对头节点的值m=q->data;if(q==Q->rear)//判断队列中是否已经只有一个节点剩余{coutelse //若还有多个节点直接输出数据元素{cout}Q->front->next=q->next;free(q);}void chakan(LQueue *Q){Queuepre p;coutp=Q->front->next;coutdatado{p=p->next;coutdata}while(p->next!=null);//判断队列中的节点个数并实现指针的后移以逐个输出其值} void xiaban(LQueue *Q) {while(Q->front){Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;// 摧毁整个队列即下班操作的实现}}void main(){int sel,flag=1; //定义一个选择字符和一个标志符LQueue *qu;Queuepre p;qu=(LQueue *)malloc(sizeof(LQueue));p=(Queuepre)malloc(sizeof(Qnode)); /*创建空队*/qu->front=qu->rear=p;p->next=null;free(p);while(flag==1) //实现入队，出队，查看的多次操作{coutprintf("Please select:");cin>>sel;switch(sel){case 1: paidui(qu); break;case 2:jiuzhen(qu); break;case 3: chakan(qu);break;case 4: xiaban(qu);flag=0; break; //执行此语句是改变标志符，一跳出本循环}}}6、实验心得本实验中应用的主要是队列的知识，重点是结点的插入。

在主函数中创建一个菜单，使得进行操作的选择运用switch语句，此为复习上学期所学内容在实践本实验的过程中，我没有遇到太大的问题，这得益于第一个实验本实验与第一个实验的基本思想是一致的，不同的是表达方式在进行队列的遍历，即查看排队时，我开始并不是很明白它的意图，但经过参考资料，终于发现原来是要清点人数，判断队列是否为空通过本实验的学习，使我进一步认识到了栈与队列的区别，栈是“先进后出”，队列是“先进先出”，根据病人。