数据结构课程设计报告(完整版)[1].doc

第二题：电梯模拟1、需求分析：模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；如果电梯在某层静止时间超过300t，则驶回1层侯命。而题目的最终要求输出时：按时序显示系统状态的变化过程，即发生的全部人和电梯的动作序列。2、设计21设计思想：（1）数据结构设计本题中的电梯的变化，是一个动态变化的过程，要在动态过程中实现正常跳转，首先要确定各种跳转的状态，因而这里我使用枚举类型来表示电梯的各种状态的：enum up,down,stop,homeState(home);同时初始化最初状态为电梯在本垒层。而在电梯的运行过程中对于乘客来说，显然有一个进入电梯与出电梯的队列，因而在这里我是用的链表来实现这个过程的，同时用结构体来保存该乘客的信息：typedef struct passageint now;/乘客当前所在的位置int dis;/乘客的目地地int wait;/最长的等待的时间int waitnow;/已经等待的时间struct passage *next;Passage;虽然电梯中的状态是由枚举类型来实现的，但是在整个程序的运行过程中，我还是为电梯设置了一个结构体类型，以便保存更多的信息：typedef struct liftint count_C;/计数电梯已到达的层数int count_A;/系统的总时间计数器 记得必须初始化为0int flag_inHigh;/九个楼层有无请求的标志 哪个楼层如果有请求 该标志置1int num;/等待队列中的人数 记得要进行初始化为0int people;/电梯中人数int flag_outHigh;Lift;（2）算法设计顾名思义本程序在运行的过程中用到的算法便是“电梯算法”，电梯算法借鉴了磁盘寻道C-LOOK算法，即电梯向一个方向运行，直到这个方向上没有服务为止。2.2设计表示（1）、函数调用关系图及其说明如下:(2)函数接口说明：函数中的参数均是使用的全局变量的传递，因而在函数间进行传递的过程中比较简单，下面就将主要函数及他们之间的参数的关系列出如下：int OutOrIn(Lift &L,Passage *Queue,Passage *LiftQ);/进和出电梯的总函数int Update(Lift &L,Passage *Queue,Passage *LiftQ);/刷新的函数int Run(Lift &L,Passage *Queue,Passage *LiftQ);/整个电梯各种状态转换的函数int OpenTheDoor(Lift &L);/开门主要是用于解决其中的时间问题int CloseTheDoor(Lift &L);/关门int In(Lift &L);/进入 主要是解决每个人进入电梯的时间问题int Out(Lift &L);/出去int Test(Lift &L,Passage *Queue,Passage *LiftQ);/电梯测试关门还是开门的函数int Request(Lift &L,Passage *Queue);2.3详细设计3、调试分析该程序的调试过程较为轻松，基本在算法实现的基础上没有出现什么错误，因而在调试的过程中并无什么深刻印象。4、用户手册点击运行程序，在弹出的窗口中，会提示要输入的信息：1、 提示信息为：“请输入图中的顶点数和弧数以及图的标志和弧的标志：”按要求输入即可，本题即输入9 11 v a2、 提示信息为“请完成该邻接表的输入”：由于邻接表的输入信息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心3、 在完成上面两步的输入后按enter键便能得到程序的运行结果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动 5 测试数据及测试结果测试数据如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1 5415 2 6526 9 77 7 8617 4 9718 2 10818 4 1190程序运行结果如下：6、原程序清单如下：/*关键路径问题2010年07月31日晚上08：36开始动工*/#includeusing namespace std;const int MAX_V_NUM=20;/最大存储顶点的数目const int STACK_INIT_SIZE=20;/栈的存储空间分配量/数据存储部分/*一下是图的邻接表的存储表示，由于第一次用 用的比较的生疏*/typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指下一条弧的指针int info;/该弧相关信息 即权值int name;/弧的名字ArcNode;typedef struct VNodeint data;/顶点的信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/图中当前顶点数和弧数char kind,kind1;/图中的各类标志顶点和弧ALGraph;typedef struct int *base;int *top;int stacksize;Stack;int veMAX_V_NUM;Stack T;/函数体描述部分int InitStack(Stack &S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G,Stack &T);int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM);/*下面是函数的具体实现部分*/构造一个空栈int InitStack(Stack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;/可以用于当栈的存储空间不够的情况下 进行扩充return 1;/元素进栈int Push (Stack &S, int &e)*S.top+=e;return 1;/元素出栈int Pop(Stack &S, int &e)if(S.top=S.base)return 0;e=*-S.top;return 1;/判断栈是否为空int StackEmpty(Stack &S)if(S.top=S.base)return 1;else return 0;/找出每个顶点的入度int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM)ArcNode *p;int i;for(i=0;iMAX_V_NUM;i+)indegreei=0;for(i=0;inextarc)indegreep-adjvex+;return 0;/拓扑排序同时求出各活动的最早发生时间int ToPoOrder(ALGraph &G,Stack &T)int count=0;int i,j,k;Stack S1;ArcNode *p;int indegreeMAX_V_NUM;InitStack(T);InitStack(S1);FindInDegree(G,indegree);for(i=0;iG.vnum;i+)if(indegreei=0)Push(S1,i);/建立0入度顶点栈Sfor(i=0;inextarc)k=p-adjvex;if(-indegreek=0)Push(S1,k);if(vej+(p-info)vek)vek=vej+(p-info);/for(i=0;iG.vnum;i+)/coutveiendl;if(countG.vnum)return 0;else return 1;/计算各顶点的最迟发生时间及进行输出int CriticalPath(ALGraph &G)int vlMAX_V_NUM;int dut;int i,j,k,ee,el;ArcNode *p;/char tag;if(!ToPoOrder(G,T)return 0;cout完成整项工程至少需要的时间是：veG.vnum-1endl;for(i=0;inextarc)k=p-adjvex;dut=(p-info);if(vlk-dutvlj)vlj=vlk-dut;/for(i=0;iG.vnum;i+)/coutvliendl;cout影响工程进度的关键活动是:endl;for(j=0;jnextarc)k=p-adjvex;dut=(p-info);ee=vej;el=vlk-dut;/coutj=jK=kdut=dutee=eeel=elendl;if(ee=el)/tag=(ee=el)?*:;coutG.kind1nameendl;return 1;int main()ALGraph G;int i,j,Hnum;ArcNode *p,*q;/int indegreeMAX_V_NUM;/ALGraph G;cout请输入图中的顶点数和弧数以及图的标志和弧的标志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout请完成该邻接表的输入：endl;for(i=0;iG.vnum;i+)cout请输入该顶点的信息G.verticesi.data;cout请输入与G.kindG.verticesi.data号顶点相邻的弧的数目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）q-adjvex;cinq-info;cinq-name;q-nextarc=p-nextarc;p-nextarc=q;/ToPoOrder(G,T);/CriticalPath(G);/test/*for(i=0;iG.vnum;i+)cout该顶点是G.kindG.verticesi.dataendl;cout与该顶点相邻的顶点依次是：nextarc)coutG.kindadjvex.dataendl;*/FindInDegree(G,indegree);/for(i=0;iG.vnum;i+)/coutindegreei=indegreeiendl;CriticalPath(G);/test end/return 0;/* 第五题：关键路径问题1、需求分析：当一项工程被划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证。要求：给定一个带权的有向图代表一个工程的AOE网络，研究如下问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键活动？示例图：2、设计21设计思想：（1）数据结构设计本题中的数据结构主要影响在于整个程序设计过程中数据的存储和拓扑排序、关键路径算法的实现，而在算法的实现过程中又要依赖数据的存储结构，而在图的存储结构中，比较适合实现拓扑排序算法的显然是邻接表的存储结构，所以本程序设计过程中均采用的是邻接表的存储方法。其主要数据的主要存储结构体声明如下：typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指下一条弧的指针int info;/该弧相关信息 即权值int name;/弧的名字ArcNode;typedef struct VNodeint data;/顶点的信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/图中当前顶点数和弧数char kind,kind1;/图中的各类标志顶点和弧ALGraph;同时由于拓扑排序实现过程中要用到进栈和出栈的操作，因此还有栈的声明如下：typedef struct int *base;int *top;int stacksize;Stack;（2）算法设计本程序的算法设计主要体现在拓扑排序和求事件的最早发生时间和最迟发生时间的的过程中，因此算法设计主要也是针对拓扑排序和求事件发生的最早发生和最迟发生时间的算法设计。拓扑排序的思想是将入度为零的结点进行S1中的出栈操作，同时将其对T进行进栈，这主要是方便在进行完求最早发生时间后，通过出栈的操作直接求最迟发生时间。2.2设计表示（1）、函数调用关系图及其说明如下:(2)函数接口说明：函数中的参数均是使用的全局变量的传递，因而在函数间进行传递的过程中比较简单，下面就将主要函数及他们之间的参数的关系列出如下：int InitStack(Stack &S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G,Stack &T);int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM);2.3详细设计该程序的算法主要在以下四个方面：拓扑排序、求出事件的最早发生时间、求出事件的最迟发生时间、求出关键活动，其中关键活动的算法设计较为简单，即是在求出各活动的最早发生时间和最迟发生时间的前提下根据判断两时间是否相等，来判断是否是关键活动，因而主要的算法设计便在前三个方面。拓扑排序与求事件的最早发生时间相结合，拓扑排序即将入度为零的栈S中的元素依次出栈，同时将该元素进栈到栈T中，在进栈的同时求出其最早发生时间算法如下：从ve（0）=0开始向前递推Ve（j）=然后便是求事件的最迟发生时间，该过程就是对上面的过程中得到的栈T进行依次出栈，同时求其最迟发生时间，其算法简要描述如下:从vl（n-1）=ve（n-1）起向后递推Vl（i）=具体实现见代码中int ToPoOrder(ALGraph &G,Stack &T)和int CriticalPath(ALGraph &G)函数；3、调试分析该程序的调试过程较为轻松，基本在算法实现的基础上没有出现什么错误，因而在调试的过程中并无什么深刻印象。4、用户手册点击运行程序，在弹出的窗口中，会提示要输入的信息：4、 提示信息为：“请输入图中的顶点数和弧数以及图的标志和弧的标志：”按要求输入即可，本题即输入9 11 v a5、 提示信息为“请完成该邻接表的输入”：由于邻接表的输入信息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心6、 在完成上面两步的输入后按enter键便能得到程序的运行结果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动 5 测试数据及测试结果测试数据如下：9 11 v a131 6 12 4 23 5 3214 1 4314 1 5415 2 6526 9 77 7 8617 4 9718 2 10818 4 1190程序运行结果如下：6、原程序清单如下：/*关键路径问题2010年07月31日晚上08：36开始动工*/#includeusing namespace std;const int MAX_V_NUM=20;/最大存储顶点的数目const int STACK_INIT_SIZE=20;/栈的存储空间分配量/数据存储部分/*一下是图的邻接表的存储表示，由于第一次用 用的比较的生疏*/typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指下一条弧的指针int info;/该弧相关信息 即权值int name;/弧的名字ArcNode;typedef struct VNodeint data;/顶点的信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针AdjListMAX_V_NUM;typedef struct AdjList vertices;int vnum,arcnum;/图中当前顶点数和弧数char kind,kind1;/图中的各类标志顶点和弧ALGraph;typedef struct int *base;int *top;int stacksize;Stack;int veMAX_V_NUM;Stack T;/函数体描述部分int InitStack(Stack &S);int Push(Stack &S,int &e);int Pop(Stack &S,int &e);int CriticalPath(ALGraph &G);int ToPoOrder(ALGraph &G,Stack &T);int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM);/*下面是函数的具体实现部分*/构造一个空栈int InitStack(Stack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;/可以用于当栈的存储空间不够的情况下 进行扩充return 1;/元素进栈int Push (Stack &S, int &e)*S.top+=e;return 1;/元素出栈int Pop(Stack &S, int &e)if(S.top=S.base)return 0;e=*-S.top;return 1;/判断栈是否为空int StackEmpty(Stack &S)if(S.top=S.base)return 1;else return 0;/找出每个顶点的入度int FindInDegree(ALGraph &G,int (&indegree)MAX_V_NUM)ArcNode *p;int i;for(i=0;iMAX_V_NUM;i+)indegreei=0;for(i=0;inextarc)indegreep-adjvex+;return 0;/拓扑排序同时求出各活动的最早发生时间int ToPoOrder(ALGraph &G,Stack &T)int count=0;int i,j,k;Stack S1;ArcNode *p;int indegreeMAX_V_NUM;InitStack(T);InitStack(S1);FindInDegree(G,indegree);for(i=0;iG.vnum;i+)if(indegreei=0)Push(S1,i);/建立0入度顶点栈Sfor(i=0;inextarc)k=p-adjvex;if(-indegreek=0)Push(S1,k);if(vej+(p-info)vek)vek=vej+(p-info);/for(i=0;iG.vnum;i+)/coutveiendl;if(countG.vnum)return 0;else return 1;/计算各顶点的最迟发生时间及进行输出int CriticalPath(ALGraph &G)int vlMAX_V_NUM;int dut;int i,j,k,ee,el;ArcNode *p;/char tag;if(!ToPoOrder(G,T)return 0;cout完成整项工程至少需要的时间是：veG.vnum-1endl;for(i=0;inextarc)k=p-adjvex;dut=(p-info);if(vlk-dutvlj)vlj=vlk-dut;/for(i=0;iG.vnum;i+)/coutvliendl;cout影响工程进度的关键活动是:endl;for(j=0;jnextarc)k=p-adjvex;dut=(p-info);ee=vej;el=vlk-dut;/coutj=jK=kdut=dutee=eeel=elendl;if(ee=el)/tag=(ee=el)?*:;coutG.kind1nameendl;return 1;int main()ALGraph G;int i,j,Hnum;ArcNode *p,*q;/int indegreeMAX_V_NUM;/ALGraph G;cout请输入图中的顶点数和弧数以及图的标志和弧的标志：G.vnum;cinG.arcnum;cinG.kind;cinG.kind1;cout请完成该邻接表的输入：endl;for(i=0;iG.vnum;i+)cout请输入该顶点的信息G.verticesi.data;cout请输入与G.kindG.verticesi.data号顶点相邻的弧的数目:Hnum;if(Hnum=0)G.verticesi.firstarc=0;elsecout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）nextarc=0;cinp-adjvex;cinp-info;cinp-name;for(j=0;jHnum-1;j+)cout请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）q-adjvex;cinq-info;cinq-name;q-nextarc=p-nextarc;p-nextarc=q;/ToPoOrder(G,T);/CriticalPath(G);/test/*for(i=0;iG.vnum;i+)cout该顶点是G.kindG.verticesi.dataendl;cout与该顶点相邻的顶点依次是：nextarc)coutG.kindadjvex.dataendl;*/FindInDegree(G,indegree);/for(i=0;iG.vnum;i+)/coutindegreei=indegreeiendl;CriticalPath(G);/test end/return 0;/* 第八题：研究生入学考试成绩处理1、需求分析：假设某大学计算机应用技术专业招收研究生n名，现在要根据报考者的考试成绩择优录取。考试课程有政治、英语、数学、专业综合四门。考试成绩分为两类：第一类为每门课程都达到最低录取线；第二类为有一门或多门课程未达到最低录取线。录取方法是在每门课程达到最低录取线的考生中按总分从高到低录取。试设计一个成绩处理程序实现以上功能。根据录取方法，打印输出n份录取通知书，列出录取者四门课程的成绩及总分（要求采用堆排序）。并能实现对任一考生或任一门课程成绩的查找（要求两种查找方式，根据考号或姓名进行查找，采用高效的查找算法）。录取通知书的格式如下：2、设计21设计思想：（1）数据结构设计由于本题明确要求在进行排序时必须采用推排序的算法，而堆排序最常采用的数据存储结构便是顺序表存储结构，因此在我的设计中是采用的结构体数组将各个学生的信息进行存储，同时这也方便排序算法的实现。typedef structstring name;int Politics;int English;int Mathematics;int Major;int Total;string Num;Student;（2）算法设计由于题目要求本程序的查找是针对考号和姓名两种方式进行查找的，而不是针对相应的可比较的数据进行查找，所以像二叉查找和二叉排序树这些查找方法基本都用不上，因此本程序采用的是“蛮力”查找的方法，及对整个结构体数组进行遍历，而与要查找的信息一一进行对比，只不过在进行比较的过程中用的是string类中的重载“=”，这样更加的方便快捷。而堆排序的算法，由于学生成绩的录取是一个从高分到低分排序的过程，因此推排序的算法就是一个建立“大顶堆”的过程。2.2设计表示（1）、函数调用关系图及其说明如下:(2)函数接口说明：由于个人的喜爱不同，而本人在参数传递的过程中喜欢用引用和指针进行传递，因此本程序用的是指针进行传递，因而每个参数都相当于全局变量，这样在接口方面方便而且不用重新开辟其他的空间。主要函数如下:Int HeapAdjust(Student (&S_USE)MAX_SIZE,int s,int m);/堆排序 int HeapSort(Student (&S_USE)MAX_SIZE);/调整 int PanDuan(Student (&S_ALL)MAX_SIZE,Student (&S_USE)MAX_SIZE,Student (&S_UNUSE)MAX_SIZE);/判断该研究生是否有录取资格 才能进行堆排序 int Find(Student (&S_ALL)MAX_SIZE);/查找成绩 int Display();/输出成绩单 int PutIn(Student &S);/成绩录入2.3详细设计由于查找的算法是用的“蛮力”的算法，而对成绩的录入也非常的简单，因此详细设计这一块主要说说堆排序的详细设计算法。堆排序的详细设计分析：首先题目要求是按四门课程的总分进行排序，由此我们知道我们要建立的堆是一个“大顶堆”，而建堆过程中主要解决的两个问题是：（1）如何由一个无序序列建成一个堆？（2）如何在输出堆元素之后，调整剩余的元素成为一个新的堆？在无序序列建立堆的过程中在我的程序中是用HeapAdjust()这个函数实现的，将建堆的过程看做事一个反复筛选的过程，则只需从从最后一个非终端断点n/2的下界开始向前一次进行筛选，若所比较的元素比其后继的元素要小则不需要进行交换，否则需要该元素与其父节点进行交换。即该过程中每一步都是将二叉树的子树建立成一个小顶堆的过程，这主要是方便在后面调整的过程中将堆顶元素和最后一个元素进行交换，即将其从大到小排序的过程。int HeapAdjust(Student (&S_USE)MAX_SIZE,int s,int m)Student rc;int j;rc=S_USEs;for(j=2*s;j=m;j*=2)if(jS_USEj+1.Total)j+;if(rc.Total=0;i-)S_USEi=S_USEi-1;/coutI am here!0;i-)/要不要减一 先记在这里HeapAdjust(S_USE,i,count_U);for(i=count_U;i1;i-)tmp=S_USE1;S_USE1=S_USEi;S_USEi=tmp;HeapAdjust(S_USE,1,i-1);for(i=0;icount_U;i+)S_USEi=S_USEi+1;return 0;3、调试分析印象最深刻的是在二叉树的第一个元素是下标从1开始，而顺序表的数组的下标是从0开始，这个细节总会导致内存出错，最后通过在堆排序过程中，先将数组后移，排序完后将数组在前移解决了这个问题，因此印象较为深刻，其他的调试错误，一般都是在程序测试的过程中一一改正，问题不大。4、用户手册点击运行程序，在弹出的窗口中，会提示要输入的信息：7、 首先提示输入的是学生的个数：此时输入你所需要输入的学生的个数即可。8、 提示信息为“请按照学生的姓名、政治、英语、数学和专业综合的分数以及考号依次进行输入”：按照学生的信息一一进行输入即可9、 提示信息为“请输入要录取学生的个数：”此时用户输入要录取学生的个数，窗口中便会显示出录取学生的信息10、 然后便是查找的过程，用户按提示进行输入，便可按考号和姓名两种方式对所需要的信息进行查找。5 测试数据及测试结果在测试的过程中我一共用到了如下26组数据：aaa 97 98 85 91 1001bbb 56 89 45 97 1002ccc 62 68 64 92 1003 ddd 66 68 69 92 1004eee 70 72 48 95 1005fff 50 68 78 91 1006ggg 70 76 86 95 1007hhh 75 78 79 96 1008iii 45 65 68 78 1009jjj 65 68 69 98 1010kkk 62 32 68 97 1011lll 65 75 89 100 1012mmm 65 78 89 123 1013nnn 23 56 89 45 1014ooo 47 78 89 65 1015ppp 65 89 41 45 1016qqq 68 89 78 89 1017rrr 58 89 45 97 1018sss 45 78 56 89 1019ttt 61 61 61 91 1020uuu 73 74 75 94 1021vvv 56 58 59 124 1022www 65 68 69 95 1023xxx 68 69 78 94 1024yyy 56 23 45 56 1025zzz 12 45 56 98 1026然后要求程序通过排序后录取前五位，程序运行结果如下：通过与原数据的比较，结果准确无误：一下便是查找的测试结果：通过分析知道，结果准确无误。6.、原程序清单如下：/*研究生入学考试成绩处理2010年8月1日开始动工*/#include#includeusing namespace std;const int MAX_SIZE=100;const int L_P=60;/分别表示各门的最低录取分数线const int L_E=60;const int L_MATH=60;con