数据结构课程设计报告（完整版）

第二题：电梯模拟

1、需求分析：

模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、??第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。

乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。

模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；如果电梯在某层静止时间超过300t，则驶回1层侯命。

而题目的最终要求输出时：

按时序显示系统状态的变化过程，即发生的全部人和电梯的动作序列。 2、设计 2．1设计思想： （1）数据结构设计

本题中的电梯的变化，是一个动态变化的过程，要在动态过程中实现正常跳转，首先要确定各种跳转的状态，因而这里我使用枚举类型来表示电梯的各种状态的：

enum {up,down,stop,home}State(home); 同时初始化最初状态为电梯在本垒层。而在电梯的运行过程中对于乘客来说，显然有一个进入电梯与出电梯的队列，因而在这里我是用的链表来实现这个过程的，同时用结构体来保存该乘客的信息： typedef struct passage { int now;//乘客当前所在的位置 int dis;//乘客的目地地 int wait;//最长的等待的时间 int waitnow;//已经等待的时间 struct passage *next; }Passage;

虽然电梯中的状态是由枚举类型来实现的，但是在整个程序的运行过程中，我还是为电梯设置了一个结构体类型，以便保存更多的信息： typedef struct lift { int count_C;//计数电梯已到达的层数 int count_A;//系统的总时间计数器 记得必须初始化为0 int flag_in[High];//九个楼层有无请求的标志 哪个楼层如果有请求 该标志置1 int num;//等待队列中的人数 记得要进行初始化为0 int people;//电梯中人数

int flag_out[High]; }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 a

2、 提示信息为“请完成该邻接表的输入”：由于邻接表的输入信

息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心

3、 在完成上面两步的输入后按enter键便能得到程序的运行结

果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动

5 测试数据及测试结果

测试数据如下： 9 11 v a 1 3 1 6 1 2 4 2 3 5 3 2 1 4 1 4 3 1 4 1 5 4 1 5 2 6

5 2 6 9 7 7 7 8 6 1 7 4 9 7 1

8 2 10 8 1

8 4 11 9 0

程序运行结果如下：

6、原程序清单如下： /*

关键路径问题

2010年07月31日晚上08：36开始动工 */

#include using namespace std;

const int MAX_V_NUM=20;//最大存储顶点的数目 const int STACK_INIT_SIZE=20;//栈的存储空间分配量 ////数据存储部分 /*

一下是图的邻接表的存储表示，由于第一次用 用的比较的生疏?? */

typedef struct ArcNode {

int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指下一条弧的指针 int info;//该弧相关信息 即权值 int name;//弧的名字 }ArcNode;

typedef struct VNode

{

int data;//顶点的信息

ArcNode *firstarc;//指向第一条依附该顶点的弧的指针

}AdjList[MAX_V_NUM]; typedef struct {

AdjList vertices;

int vnum,arcnum;//图中当前顶点数和弧数 char kind,kind1;//图中的各类标志顶点和弧

}ALGraph; typedef struct {

int *base; int *top; int stacksize;

}Stack;

int ve[MAX_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; };

//元素进栈

第五题：关键路径问题

1、需求分析：

当一项工程被划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理组织人力、物力、财力，加快这些活动的进度，为按时或提前完成整个工程提供保证。

要求：

给定一个带权的有向图代表一个工程的AOE网络，研究如下问题： （1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键活动？ 示例图：

a1a2=4a3=5

61=2a4=134=a519=a75a8=77a10=2984=1a1a6=2=a94 62、设计 2．1设计思想： （1）数据结构设计

本题中的数据结构主要影响在于整个程序设计过程中数据的存储和拓扑排序、关键路径算法的实现，而在算法的实现过程中又要依赖数据的存储结构，而在图的存储结构中，比较适合实现拓扑排序算法的显然是邻接表的存储结构，所以本程序设计过程中均采用的是邻接表的存储方法。其主要数据的主要存储结构体声明如下：

typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指下一条弧的指针 int info;//该弧相关信息 即权值 int name;//弧的名字 }ArcNode;

typedef struct VNode { int data;//顶点的信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针

}AdjList[MAX_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）=Max{ve(i)?dut(?i,j?)}

然后便是求事件的最迟发生时间，该过程就是对上面的过程中得到的栈T进行依次出栈，同时求其最迟发生时间，其算法简要描述如下:

从vl（n-1）=ve（n-1）起向后递推

Vl（i）=Min{vl(j)?dut(?i,j?)}

具体实现见代码中int ToPoOrder(ALGraph &G,Stack &T)和int CriticalPath(ALGraph &G)函数；

3、调试分析

该程序的调试过程较为轻松，基本在算法实现的基础上没有出现什么错误，因而在调试的过程中并无什么深刻印象。

4、用户手册

点击运行程序，在弹出的窗口中，会提示要输入的信息： 4、 提示信息为：“请输入图中的顶点数和弧数以及图的标志和弧

的标志：”按要求输入即可，本题即输入9 11 v a

5、 提示信息为“请完成该邻接表的输入”：由于邻接表的输入信

息一般较多，而且均是采用的链表来存储，因而该部分的输入要特别的小心

6、 在完成上面两步的输入后按enter键便能得到程序的运行结

果，即输出完成整项工程至少需要多少时间和影响工程进度的关键活动

5 测试数据及测试结果

测试数据如下： 9 11 v a 1 3 1 6 1 2 4 2 3 5 3 2 1 4 1 4 3 1 4 1 5 4 1 5 2 6 5 2 6 9 7 7 7 8 6 1 7 4 9 7 1

8 2 10 8 1

8 4 11 9 0

程序运行结果如下：

6、原程序清单如下： /*

关键路径问题

2010年07月31日晚上08：36开始动工

*/

#include using namespace std;

const int MAX_V_NUM=20;//最大存储顶点的数目 const int STACK_INIT_SIZE=20;//栈的存储空间分配量 ////数据存储部分 /*

一下是图的邻接表的存储表示，由于第一次用 用的比较的生疏?? */

typedef struct ArcNode {

int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指下一条弧的指针 int info;//该弧相关信息 即权值 int name;//弧的名字 }ArcNode;

typedef struct VNode {

int data;//顶点的信息

ArcNode *firstarc;//指向第一条依附该顶点的弧的指针

}AdjList[MAX_V_NUM]; typedef struct {

AdjList vertices;

int vnum,arcnum;//图中当前顶点数和弧数 char kind,kind1;//图中的各类标志顶点和弧

}ALGraph; typedef struct {

int *base; int *top; int stacksize;

}Stack;

int ve[MAX_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;inextarc) indegree[p->adjvex]++; }

return 0; }

//拓扑排序同时求出各活动的最早发生时间

int ToPoOrder(ALGraph &G,Stack &T) {

int count=0;

int i,j,k; Stack S1; ArcNode *p;

int indegree[MAX_V_NUM]; InitStack(T); InitStack(S1);

FindInDegree(G,indegree); for(i=0;i

for(i=0;i

while(!StackEmpty(S1)) { Pop(S1,j); Push(T,j); count++; for(p=G.vertices[j].firstarc;p;p=p->nextarc) { k=p->adjvex; if(--indegree[k]==0) Push(S1,k);

if(ve[j]+(p->info)>ve[k]) ve[k]=ve[j]+(p->info); } }

// for(i=0;i

//计算各顶点的最迟发生时间及进行输出 int CriticalPath(ALGraph &G) {

int vl[MAX_V_NUM]; int dut;

int i,j,k,ee,el; ArcNode *p; // char tag;

if(!ToPoOrder(G,T)) return 0;

cout<<\完成整项工程至少需要的时间是：\ for(i=0;inextarc) { k=p->adjvex; dut=(p->info); if(vl[k]-dut

// for(i=0;i

cout<<\影响工程进度的关键活动是:\ for(j=0;jnextarc) { k=p->adjvex;

dut=(p->info); ee=ve[j]; el=vl[k]-dut;

//cout<<\endl; if(ee==el) //tag=(ee=el)?'*':''; cout<name<

int main() {

ALGraph G; int i,j,Hnum; ArcNode *p,*q;

// int indegree[MAX_V_NUM]; //ALGraph G;

cout<<\请输入图中的顶点数和弧数以及图的标志和弧的标志：\

cin>>G.vnum; cin>>G.arcnum; cin>>G.kind; cin>>G.kind1;

cout<<\请完成该邻接表的输入：\ for(i=0;i

{ cout<<\请输入该顶点的信息\ cin>>G.vertices[i].data; cout<<\请输入与\.kind<>Hnum; if(Hnum==0) { G.vertices[i].firstarc=0; } else {

cout<<\请依次次输入弧的信息（包括顶点的位置及权值和该边的名称）\ p=(ArcNode *)malloc(sizeof(ArcNode)); G.vertices[i].firstarc=p; p->nextarc=0; cin>>p->adjvex; cin>>p->info; cin>>p->name; for(j=0;j>q->adjvex; cin>>q->info; cin>>q->name; q->nextarc=p->nextarc; p->nextarc=q; } } }

//ToPoOrder(G,T); //CriticalPath(G); ////////test//////////

/* for(i=0;inextarc) { cout<adjvex].data<

// FindInDegree(G,indegree); //for(i=0;i

// cout<<\ CriticalPath(G);

////////////test end///////////

return 0; }

通过与原数据的比较，结果准确无误： 一下便是查找的测试结果：

通过分析知道，结果准确无误。

6.、原程序清单如下：

/* 研究生入学考试成绩处理 2010年8月1日开始动工 */

#include #include using namespace std; const int MAX_SIZE=100;

const int L_P=60;//分别表示各门的最低录取分数线 const int L_E=60; const int L_MATH=60; const int L_MAJOR=90;

int count_A=0;//用于记录全部录入的学生的个数

int count_U=0;//用于记录达到最低分数线的学生的个数 int count_N=0;//用与记录为达到最低分数线的学生的个数 int count_ACC=0;//用于记录录取学生的个数 typedef struct { string name; int Politics;

int English; int Mathematics; int Major; int Total; string Num; }Student;

////////////////////////////////////////////// ////////////////////////////////////////////

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);//成绩录入

//////////////////////////////////////////////// //////////////////////////////////////////////// int Find(Student (&S_ALL)[MAX_SIZE]) { int k,i; string num,name; cout<<\请输入您要查找的方式：1：按考号查找，2：按姓名查找\ cin>>k; if(k==1) { cout<<\请输入要查询考生的考号：\ cin>>num; for(i=0;i

cout<<\\ cout<<\\ cout<<\\ break; } } if(i==count_A) cout<<\查找失败！\ return 0; } else if(k==2) { cout<<\请输入要查询考生的姓名：\ cin>>name; for(i=0;i

} else return 1; }

int HeapAdjust(Student (&S_USE)[MAX_SIZE],int s,int m) { Student rc; int j; rc=S_USE[s]; for(j=2*s;j<=m;j*=2) { if(jS_USE[j+1].Total)) j++; if(rc.Total

int HeapSort(Student (&S_USE)[MAX_SIZE]) { int i; Student tmp; for(i=count_U;i>=0;i--) S_USE[i]=S_USE[i-1]; //cout<<\ for(i=count_U/2;i>0;i--)//要不要减一 先记在这里 HeapAdjust(S_USE,i,count_U); for(i=count_U;i>1;i--) { tmp=S_USE[1]; S_USE[1]=S_USE[i]; S_USE[i]=tmp; // cout<<\ HeapAdjust(S_USE,1,i-1); }

本文来源：https://www.bwwdw.com/article/l2h2.html