南航-计算机实践报告--数据结构

1、精品文档 ?计算机实践?试验报告I数据结构班号：0315206学号：031520629姓名：陈叶杭Email：2580640618qq 签名： 南京航空航天高校 2021年11月1日 名目试验一：约瑟夫斯问题求解.3试验二：停车场管理问题.10试验三：管道铺设施工的最正确方案问题.23试验四：内部排序算法的实现与比较32试验一：约瑟夫斯问题求解 对象：编号为1,2，n的n个人按顺时针方向围坐一圈，每人持有一个密码正整数。一开头任选一个正整数作为上报上线值m，从第一个人开头按顺时针方向自1开头报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人 开头重新从1报数

2、，如此下去，直至全部人全部出列为止。 根本要求：利用单向循环链表存储结构模拟此过程，依据出列的挨次印出个人的编号。测试数据：n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6正确的出列挨次应为6,1,4,7,2,3,51. 单向循环链表抽象数据类型定义：struct node int top;int num;struct node *next;typedef struct node NODE;根本操作： struct node *create_sl(int n);/创立单向循环链表2. 主程序流程及其模块调用关系 1)创立循环列表流程图：2约瑟夫斯问题求解流程图3主函数流程图

3、主程序：#include#include#include#includetypedefintElemType;typedefstructnodeElemTypedata;ElemTypenum;structnode*next;SLNODE;/单链表的定义structnode*create_sl(intn);voidJosephus(SLNODE*head,intn,intm);intmain()/主函数SLNODE*head;intn,m;time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);he

4、ad=(SLNODE*)malloc(sizeof(SLNODE);printf(试验名称：试验一：约瑟夫斯问题求解n);/初始界面printf(学号：031520629n);printf(姓名：陈叶杭n);printf(/-/n);printf(程序运行开头，Currentlocaltimeanddate:%s,asctime(timeinfo);printf(请输入总人数n=n);scanf(%d,&n);printf(请输入报数上限值为正整数m=n);scanf(%d,&m);head=create_sl(n);/创立单链表Josephus(head,n,m);time(&rawtime

5、);timeinfo=localtime(&rawtime);printf(程序运行结束，Currentlocaltimeanddate:%s,asctime(timeinfo);return0;structnode*create_sl(intn)SLNODE*p,*s,*head;ElemTypex;inta;head=(SLNODE*)malloc(sizeof(SLNODE);p=head;head-next=head;for(a=1;adata=x;s-num=a;if(head-next=head)head=s;elsep-next=s;p=s;p-next=head;returnh

6、ead;voidJosephus(SLNODE*head,intn,intm)/约瑟夫斯问题求解SLNODE*p,*q;inti;p=head;printf(出列序列:);while(p-next!=p)for(i=1;inext;m=p-data;/读取新的密码值printf(%4d,p-num);q-next=p-next;/删除p节点free(p);p=q-next;printf(%4dn,p-num);运行结果： 试验调试和感想 开头先去搜寻程序开头和结束时间代码，觉察有错误，始终以为是格式错了，后来反复查验后觉察是开头没有调用时间函数。主程序调试时，开头有一个错误，也是再找缘由，后来

7、认真检查后，觉察是链表定义错误，定义成循环链表，应当是用单链表做。后来改正来后就没错了。由于是第一次做数据结构的试验，而上学期的C+也因长时间没有碰过而稍显手生，在码程序的过程中遇到了很多问题，但通过翻看教材已根本解决。约瑟夫虽然构思起来比较简洁，但实际执行时经常消灭各种意想不到的问题，如输出次数不对等等，通过将近两天的调试才最终完成，很有成就感。接下来假设有时间可以在原程序中参加其实位置编号，使得起始位置也可由用户自定。试验二：停车场管理问题 对象：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后挨次，依次由北向南排列。假设停车场内已经停

8、满n辆车，那么后来的车只能在门外的便车道上等候。一旦有车开走，那么排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必需退出车场为它开路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必需依据它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。根本要求：以栈模拟停车场，以队列模拟车场外的便道，依据终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达A表示或“离去D表示信息、汽车标识车牌号以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：假设是车辆到达，那么输出汽车在停车场内或者便道上

9、的停车位置；假设是要离去，那么输出汽车在停车场停留的时间和应缴纳的费用便道上停留的时间不收费。栈以挨次结构实现，队列以链表结构实现。测试数据：设n=2,输入数据为：A，1,5,A，2,10，D，1,5，A，3,20，A，4,25，A，5,30，D，2,35，D，4,40，E，0,0。主程序模块：出栈：推断栈是否为空：推断栈是否已满：推断队列是否为空：出队：运行结果：试验调试和感想 关于算法，题中解析说的已经很清楚了，主要是编程时用到了一些数据结构需要用单独的类定义出来，使得程序清楚完整。这一问题一个重要的思路是对于汽车出停车场时 ，由于不肯定每次都是最外面的车出去，所以需要用到另一个栈存储车辆

10、。如图，将要出停车场的车i上面的车都倒入另一个栈中，然后将i删除，再将栈Park2中的都倒回停车场park1中即可。对于数据的输出：输入A：输出在停车场或者候车场的位置，编号由北向南12；输入D：输出车辆停靠时间出栈时间减去入栈时间这里涉及到一个计算：并不是出去时间减去到达时间，因为有可能到达后在候车区等待一段时间，这段时间不能算收费时间，和收费。输入P时依据从栈顶到栈底输出车辆车牌号；输入W时，输出候车区车辆总数；输入E，退出程序这个程序设计需要栈和队列的相关操作，所以在程序设计过程中渐渐生疏了栈和队列的相关操作，由于像栈，队列这样，有推断栈空，栈满，入栈，出栈这样的操作，使自己更加生疏了栈

11、和队列的相关学问。主程序#include#include#include #define OK 1#define ERROR 0#define MAX_STACK_SIZE 2 /* 停车场大小 */typedef int StackData;typedef int QueueData;typedef int ElemType;typedef struct Node int No; int Timeinit; Node;typedef struct QueueNode /* 队列*/ struct Node data; struct QueueNode* next; QueueNode;typ

12、edef struct LinkQueue /* 链式队列 */ struct QueueNode *rear, *front; LinkQueue;typedef struct SqStackNode /* 栈 */ int top;int bottom; struct Node stack_arrayMAX_STACK_SIZE+1 ;SqStackNode ;SqStackNode* InitStack() /* 初始化栈*/ SqStackNode *S=(SqStackNode *)malloc(sizeof(SqStackNode); S-bottom=S-top=0; retur

13、n (S);int FullStack(SqStackNode *S) return S-top=MAX_STACK_SIZE;int pushStack(SqStackNode *S,Node data) /* 入栈 */ if(FullStack(S) returnERROR; S-top+ ; (S-stack_arrayS-top).No=data.No ; (S-stack_arrayS-top).Timeinit=data.Timeinit; return OK; int popStack(SqStackNode *S,Node *data) /*弹出栈顶元素*/ if(S-top

14、=0) return ERROR; (*data).No=(S-stack_arrayS-top).No; (*data).Timeinit=(S-stack_arrayS-top).Timeinit; S-top-; return OK; int FindStack(SqStackNode *S,Node data) /* 搜寻栈内元素*/ int i; if(S-top=0) return ERROR; for(i=1;itop;i+) if(S-stack_arrayi.No = data.No) return OK; return ERROR; LinkQueue* InitQueue

15、 (void) /* 初始化队列 */ LinkQueue *Q=( LinkQueue * ) malloc( sizeof ( LinkQueue ) ); Q-rear=Q-front=NULL;return Q; int QueueEmpty ( LinkQueue *Q ) return Q-front = NULL;int GetFrontQueue ( LinkQueue *Q, Node *data ) /* 取队首 */ if ( QueueEmpty (Q) ) return 0; (*data).No = (Q-front-data).Timeinit; return 1

16、;int EnQueue ( LinkQueue *Q, Node data) /* 入队*/ QueueNode *p = ( QueueNode * ) malloc( sizeof ( QueueNode ) ); (p-data).No = data.No; (p-data).Timeinit = data.Timeinit; p-next = NULL; if ( (*Q)-front = NULL ) (*Q)-front = (*Q)-rear = p; else (*Q)-rear = (*Q)-rear-next = p; return 1;int DeQueue ( Lin

17、kQueue *Q, Node *data) /* 出队*/ if ( QueueEmpty (*Q) ) return 0; QueueNode *p = (*Q)-front; (*data).No = p-data.No; (*data).Timeinit = p-data.Timeinit; (*Q)-front = (*Q)-front-next; if (*Q)-front = NULL) (*Q)-rear = NULL; free (p); return 1; Parking(LinkQueue *Q,SqStackNode *S) /* 停车*/ int i;Node dat

18、a;printf(请输入车牌号n);scanf( %d,&data.No);printf(请输入停车时间n); scanf( %d,&data.Timeinit);for(i=1;itop;i+)if(S-stack_arrayi.No = data.No) printf(该车已停好n);return ;EnQueue(Q,data); /* 进入候车队列*/while(!QueueEmpty(*Q) if(FullStack(S) printf(请稍等.n); break; else DeQueue(Q,&data); /* 候车队列车出队 */pushStack(S,data); /* 进

19、入停放栈*/printf(停车成功n);return ;leaving(SqStackNode *S,SqStackNode *B,LinkQueue *Q) /* 离开停车场*/ if(S-bottom = S-top) printf(停车场内无车:n); else Node data; int i,n;float charge;int parking_time;printf(请输入车牌号:n);scanf( %d,&i);printf(请输入离开时间:n);scanf( %d,&n);data.No=i;if(!FindStack(S,data) printf(车库内无此车n);retur

20、n ;else while(S-stack_arrayS-top.No != i) /* 此车后的车依次出栈入让路栈*/popStack(S,&data);pushStack(B,data);popStack(S,&data); /* 此车出停放栈*/parking_time=n-data.Timeinit; /*计算收费*/charge = parking_time*10;printf(车辆:%d 停车时长:从%d到%d 共%d 收费(10元/h):$%gn,data.No,data.Timeinit,n,parking_time,charge);while(B-bottom != B-to

21、p) /* 让路栈内的车依次出栈入停放栈*/popStack(B,&data);pushStack(S,data);while(!FullStack(S)&(!QueueEmpty(*Q) /* 等待队列的车进入停车场栈*/DeQueue(Q,&data); data.Timeinit=n;pushStack(S,data);situationH(LinkQueue *Q) /* 查看候车场车数*/ Node data; int i; int parking_time; struct QueueNode *p;int wait_count=0;p=(*Q)-front;if(p = NULL)

22、 printf(Waiting car :0n);else do wait_count+;p=p-next; while(p!=NULL); printf(等待的车辆有:%dn,wait_count);situationP(SqStackNode *P) /* 查看停车场车数*/ if(P-top=P-bottom) printf(停车场内的没有车n);elseprintf(停车场内的车辆有%dn,P-top); int main() int i,No,Time;char A;Node data;SqStackNode *park;SqStackNode *back; LinkQueue *w

23、ait; park=InitStack();back=InitStack();wait=InitQueue();while(1)system(clsn);printf( *试验2：停车场管理问题*n);printf( 姓名：陈叶杭n); printf( 学号：031520629n);printf(n A.停车 n);printf( B.取车 n);printf( C.查看停车场车数 n);printf( D.查看候车场车数 n); printf( E.离开 n); printf(n 请输入你要进行的操作:); scanf(%c,%d,%d,&A,&No,&Time); if(A=A) i=1;

24、 else if(A=B) i=2; else if(A=C) i=3; else if(A=D) i=4; else if(A=E) i=5; else printf(输入有误请重新输入n); getchar(); system(PAUSE); switch(i)scanf( %d,&i);switch(i)case 1:/* 停车*/system(clsn);Parking(&wait,park);getchar();system(PAUSE);break;case 2:/* 离开 */ system(clsn);leaving(park,back,&wait);getchar();sys

25、tem(PAUSE);break;case 3:/* 查看停车状况*/system(clsn);situationP(park);system(PAUSE);getchar();break;case 4:/* 查看候车状况*/ system(clsn);situationH(&wait);system(PAUSE);getchar();break;case 5:/* 退出*/return 0; default:break;return 0;试验三：管道铺设施工的最正确方案问题 对象：需要在某个城市n个居民小区之间铺设煤气管道，那么在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区

26、之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 根本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储接受邻接表的结构。测试数据：使用以下图给出的无线网数据作为程序的输入，求出最正确铺设方案。右侧是给出的参考解。 主程序流程及其模块调用关系 1) 主程序模块建表模块 函数调用关系图 运行结果：试验调试和感想 在这个管道铺设问题的程序设计中，觉察其实这个题需要解决两个问题，一个是建立无向网的问题，另一个就是最小生成树的求解。首

27、先建立无向网，无向网是边上有权值的无向图，因为自己不明白怎么建立链表才能使它无向，于是请教学长才得以解决这个问题。还有就是这个测试数据有9个顶点信息，15条边的信息，一个个输入进去有点麻烦，于是可以通过建立邻接矩阵，然后初始化矩阵，只要把边的信息输入进去，就可以建立邻接矩阵，有了这个可以知道边和顶点的信息，然后对边的值进行排序，就可以求出最小生成树。该程序的主要优点是简洁易懂，不存在理解上的障碍，也很自然地想到这种解法。主要缺点是程序的变动性比较差，类中没有私有成员，都以公有定义。主程序#include #include #include #define MAX_VEX_NUM 50#defi

28、ne MAX_ARC_NUM 100#define UN_REACH 0typedef char VertexType;typedef struct VertexType vexsMAX_VEX_NUM;float arcsMAX_VEX_NUMMAX_VEX_NUM;int vexnum, arcnum; MGraph;int getIndexOfVexs(char vex, MGraph *MG) /*依据名称得到指定顶点在顶点集合中的下标*/int i;for (i = 1; i vexnum; i+) if (MG-vexsi = vex) return i;return 0;void

29、 create_MG(MGraph *MG) /*创立邻接矩阵*/int i, j, k;float weight;int v1, v2;char c1, c2; printf(请输入小区数 : );scanf(%d, &MG-vexnum);printf(请输入管道数 :);scanf(%d, &MG-arcnum);getchar();for (i = 1; i vexnum; i+) printf(请输入第%d个小区的名称:, i);scanf(%c, &MG-vexsi);getchar();/初始化邻接矩阵for (i = 1; i vexnum; i+) for (j = 1; j

30、 vexnum; j+) if(i = j)MG-arcsij = UN_REACH;elseMG-arcsij = UN_REACH;/输入边的信息，建立邻接矩阵for (k = 1; k arcnum; k+) printf(请按格式输入第%d条管道的费用(地点 地点 费用):, k); scanf(%c %c %f,&c1,&c2,&weight);v1 = getIndexOfVexs(c1, MG);v2 = getIndexOfVexs(c2, MG); MG-arcsv1v2 = MG-arcsv2v1 = weight;getchar();void print_MG(MGrap

31、h MG) /*打印邻接矩阵和顶点信息*/int i, j; printf(n);printf(小区数: %dn,MG.vexnum);printf(管道数: %dn,MG.arcnum);printf(小区名称为:);for (i = 1; i = MG.vexnum; i+)printf(%c, MG.vexsi);printf(nn邻接矩阵为:n);for (i = 1; i = MG.vexnum; i+) for (j=1; j MG.vexnum; j+) printf(%.1f ,MG.arcsij);printf(%.1fn, MG.arcsij);typedef struct

32、int start;int end;float cost;Edge;void init_edge(MGraph MG,Edge edge)/*由邻接矩阵得到边的信息*/int i,j;int count = 0;for(i = 1; i = MG.vexnum;i+)for (j = i;j = MG.vexnum;j+)if(MG.arcsij != 0 & MG.arcsij != UN_REACH)edgecount.start = i;edgecount.end = j;edgecount.cost = MG.arcsij;count+;void sort_edge(Edge edge

33、,int arcnum)/*将边按权值从大到小排序*/int i,j;Edge temp;for(i = 0; i arcnum - 1;i+)for (j = i+1;j edgej.cost)temp = edgei;edgei = edgej;edgej = temp;int findFather(int father,int v)/*这里是找出其根节点在father数组中下标。*/ int t = v;while(fathert != -1)t = fathert;return t;void Kruskal_MG(MGraph MG,Edge edge)/*Kruskal算法求最小生成

34、树*/int fatherMAX_VEX_NUM;int i,count,vf1,vf2;float Cost=0;/ 初始化father数组for(i = 0;i MAX_VEX_NUM;i+)fatheri = -1;i = 0;count = 0; / 统计参加最小生树中的边数/ 遍历任意两个结点之间的边while(i MG.arcnum & count MG.arcnum)vf1 = findFather(father,edgei.start);vf2 = findFather(father,edgei.end);/ 假设这两个节点不属于同一个连通重量，那么参加同一个连通重量if (v

35、f1 != vf2)fathervf2 = vf1;count+;Cost+=edgei.cost;printf(%c,%c,%.1fn,MG.vexsedgei.start,MG.vexsedgei.end,edgei.cost);i+;printf(此时总投资为:n %.1f,Cost);int main(void) MGraph MG;printf( *试验三 管道铺设施工的最正确方案问题*n);printf( 姓名：陈叶杭n);printf( 学号：031520629n); time_t rawtime; struct tm * timeinfo; time (&rawtime); t

36、imeinfo = localtime (&rawtime); printf(/-/n); printf (程序运行开头，Current local time and date: %s, asctime(timeinfo);Edge edgeMAX_ARC_NUM;create_MG(&MG);print_MG(MG);init_edge(MG,edge);sort_edge(edge,MG.arcnum);printf(n最优方案为:n);Kruskal_MG(MG,edge);time (&rawtime); timeinfo = localtime (&rawtime); printf(

37、/-/n); printf (程序运行结束，Current local time and date: %s, asctime(timeinfo);printf(nn);return EXIT_SUCCESS; 试验四：内部排序算法的实现与比较对象：在教科书中，各种内部排序算法的时间简单度分析结果只给出了算法执行时间的阶，或或许执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。根本要求：(1) 对常用的内部排序算法进行比较：直接插入排序、简洁选择排序、冒泡排序、快速排序、希尔排序。(2) 利用随机函数产生n如30000个随机整数，作为输入数据作比较；比较的指标为

38、关键字参与的比较次数和关键字的移动次数关键字交换计为3次移动。(3) 对结果作出简要分析。测试数据：随机函数产生。概要设计：为了实现上述功能，应以一维数组表示集合数据类型。 int sN; int change6,compare6;/分别用来描述排序所交换的趟数和比较的趟数从第二个元素开头使用根本操作： 数组赋值： for(i=1;iN;i+) si=rand()%100; printf(%d ,si); printf(用简洁选择法排序结果为:);simplesssort(t);printf(用冒泡法排序结果为：n);bubblesort(t);printf(用直接插入法排序结果为：n);in

39、sretsort(t);printf(用快速法排序结果为：n);QuickSortprint(t，N);printf(用希尔排序结果为:);shellsort(t);主程序流程及其模块调用关系 程序相关结果如下：简洁选择法：冒泡排序法：直接插入法：快速排序法：希尔排序：主要算法的时间简单度分析 ：直接插入排序的空间简单度为O1，时间简单度为O(n)简洁选择排序的时间简单度为O(n)，空间简单度为O1，冒泡排序的间简单度为O(n)，快速排序最好时间简单度为O(nlog2n),最坏时间简单度为O(n),空间简单度Olog2(n)希尔排序：算法的简单度为n的1.2次幂试验调试和感想 这个程序很多程序

40、其实书上已经给了，所以说还是降低了难度。这个程序最重要的我觉得还是分块调试的思想。这个程序的编写不仅在直观上感受到各种排序算法的关键字比较次数，移动次数的大写，生疏了这6种排序方法，更重要的是又把握了几种程序中问题的解决方法，例如为了防止一个排序操作执行后数组值转变而对下一步操作造成的影响，可以另外定义一个数组，再如这道题最终要求对各种排序的关键字移动次数比较次数进行比较，这个时候定义两个数组也很便利的解决了很多问题，这个浩大的程序在分解了假设干块之后化简成了很多简洁的小问题，一个问题一个问题的解决，但是当几个模块一起运行时，会消灭相互影响的状况，我当时修改了很久也不能转变这种现象，后来又重新定义了一个数组才解决此问题。到此，4个数据结构题已经全部编写完毕。还有一个调试过程的问题是有时候排序，因为程序挨次进行，数组被转变，后来觉察了只要排序前进行初始化就可以解决了。主程序：#include#include#include #define N 8 /用来存排序用的数据，其中第一个元素经常作为哨兵和交换用int change6,compare6; /分别用来描述排序所交换的趟数和比较的趟数从第二个 元素开头使用int p=0;void insretsort(int t) /直接插入int i,