数据结构与算法教学编制_数据结构与算法面试题

数据结构与算法教学编制由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构与算法面试题”。

目 录

1.需求分析.........................................错误！未定义书签。2.概要设计.........................................错误！未定义书签。3.详细设计.........................................错误！未定义书签。4.测试分析.........................................错误！未定义书签。课程设计总结.......................................错误！未定义书签。参考文献...........................................错误！未定义书签。

1.需求分析

根据课程之间的依赖关系制定课程安排计划，输入课程数及课程之间的关系。需要利用代码实现排序，以及对各个学期课程安排进行排序并输出。

1.1问题描述

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

1.2设计思路

首先利用拓扑排序对课程先后顺序进行分析，邻接表位主要存储结构，栈为主要辅助结构，给出课程之间的先后关系比如AOV网，然后进行拓扑排序，但当又向图中存在环时，无法查找该图的一个拓扑排序，当图中的所有顶点全部输出，表示对该图排序成功，实现拓扑排序算法时，相应的建立邻接表存储AOV网，为了避免重复检测入度为零的顶点，建立一个栈来对入度为零的顶点进行存放。根据课程的先后关系，对个学期的课程进行排序，输出。

1.3设计环境、原理

设计环境和器材： 硬件：计算机；软件：Microsoft Visula C++。

设计原理说明：运用图的拓扑排序对课程先修排列的实现，并调用递归完成拓扑排序。

1.4实验目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用。通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

1.5实验内容

针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。

2.概要设计：

2.1流程图

void FindInDegree(ALGraph G, int indegree[])//求图中各节点的入度（如下左图）void CreatGraph(ALGraph *G)//构件图（如下右图）。

void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)//有向图G采用邻接表存储结构(如下左图)；

void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)//有向图G采用邻接表存储结构（如下右图）。

主函数： void main()

2.2抽象数据类型图的定义 ADT Graph{

数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R: R={VR} VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系} 基本操作P: void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int *);void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);}ADT Graph 栈的定义: ADT Stack{ 数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0} 数据关系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n} 基本操作: void InitStack(SqStack *S);int StackEmpty(SqStack S);void Push(SqStack *S, int);int Pop(SqStack *S, int *e);}ADT Stack 2.3主程序

int main()//主函数 {

int numterm;//学期总数

int uplcredit;//一个学期的学分上限

int selectway;

ALGraph G;

printf(“请输入学期总数:n”);

scanf(“%d”,&numterm);

printf(“请输入一个学期的学分上限:n”);

scanf(“%d”,&uplcredit);

CreatGraph(&G);

printf(“请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布n”);

scanf(“%d”,&selectway);

if(selectway==1)

TopologicalSort_1(G,numterm,uplcredit);

if(selectway==2)

TopologicalSort_2(G,numterm,uplcredit);

system(“pause”);

return 0;} 2.4本程序只有两个模块,调用关系简单

主程序模块→拓扑排序模块

3.详细设计

3.1头结点、表结点、邻接表的定义

#define MAX_VERTEX_NUM 100 //最大课程总数 typedef struct ArcNode{ int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{ char name[24];

//课程名 int claid;

//课程号

int credit;

//课程的学分 int indegree;

//该结点的入度 int state;

//该节点的状态 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VEXTEX_NUM];typedef struct{ AdjList vertices;int vexnum, arcnum;}ALGraph;邻接表的基本操作：

void CreatGraph(ALGraph *);创建邻接表

void FindInDegree(ALGraph , int *);求一个结点的入度

void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程

void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程

3.2栈的定义

#define STACk_INIT_SIZE 100 //存储空间的初时分配量 #define STACKINCREMENT 10

//存储空间的分配增量

typedef int ElemType;typedef struct { AdjList vertices;int vexnum, arcnum;}ALGraph;基本操作：

void InitStack(SqStack *S);栈的初始化

int StackEmpty(SqStack S);判断栈是否为空

void Push(SqStack *S, int);入栈操作

int Pop(SqStack *S, int *e);出栈操作

3.3主程序和其他算法：

#include #include #include // malloc()等 #include // INT_MAX等 #include // EOF(=^Z或F6),NULL #include // atoi()52 #include // eof()#include // floor(),ceil(),abs()#include

// exit()#include // cout,cin// 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE-1 typedef int Status;// Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean;// Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 10 /* 顶点字符串的最大长度 */ #define MAXCLASS 100 int Z=0;int X=0;int xqzs,q=1,xfsx;typedef int InfoType;typedef char VertexType[MAX_NAME];/* 字符串类型 */ /* 图的邻接表存储表示 */ #define MAX_VERTEX_NUM 100 typedef enum{DG}GraphKind;/* {有向图,有向网,无向图,无向网} */ typedef struct ArcNode { int adjvex;/* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc;/* 指向下一条弧的指针 */ InfoType *info;/* 网的权值指针）*/ } ArcNode;/* 表结点 */ typedef struct { VertexType data;/* 顶点信息 */ ArcNode *firstarc;/* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ } VNode,AdjList[MAX_VERTEX_NUM];/* 头结点 */ typedef struct { AdjList vertices,verticestwo;int vexnum,arcnum;/* 图的当前顶点数和弧数 */ int kind;/* 图的种类标志 */ }ALGraph;/* 图的邻接表存储的基本操作 */ int LocateVex(ALGraph G,VertexType u){ /* 初始条件: 图G存在,u和G中顶点有相同特征 */ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i;for(i=0;iadjvex=j;p->info=NULL;/* 图 */ p->nextarc=(*G).vertices[i].firstarc;/* 插在表头 */(*G).vertices[i].firstarc=p;} return OK;} void Display(ALGraph G){ /* 输出图的邻接矩阵G */ int i;ArcNode *p;switch(G.kind){ case DG: printf(“有向图n”);} printf(“%d个顶点：n”,G.vexnum);for(i=0;iadjvex].data);p=p->nextarc;} printf(“n”);}

void FindInDegree(ALGraph G,int indegree[]){ /* 求顶点的入度，算法调用 */ int i;ArcNode *p;for(i=0;iadjvex]++;p=p->nextarc;} } } typedef int SElemType;/* 栈类型 */ /*栈的顺序存储表示 */ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ typedef struct SqStack { SElemType *base;/* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top;/* 栈顶指针 */ int stacksize;/* 当前已分配的存储空间，以元素为单位 */ }SqStack;/* 顺序栈 */ /* 顺序栈的基本操作 */ Status InitStack(SqStack *S){ /* 构造一个空栈S */(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/* 存储分配失败 */(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return OK;} Status StackEmpty(SqStack S){ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top==S.base)return TRUE;else return FALSE;} Status Pop(SqStack *S,SElemType *e){ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if((*S).top==(*S).base)return ERROR;*e=*--(*S).top;return OK;} Status Push(SqStack *S,SElemType e){ /* 插入元素e为新的栈顶元素 */ if((*S).top-(*S).base>=(*S).stacksize)/* 栈满，追加存储空间 */ {(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof

(SElemType));if(!(*S).base)exit(OVERFLOW);/* 存储分配失败 */(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e;return OK;} typedef int pathone[MAXCLASS];typedef int pathtwo[MAXCLASS];Status TopologicalSort(ALGraph G){ /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */ /* 否则返回ERROR。*/ int i,k,j=0,count,indegree[MAX_VERTEX_NUM];SqStack S;pathone a;pathtwo b;ArcNode *p;FindInDegree(G,indegree);/* 对各顶点求入度indegree[0..vernum-1] */ InitStack(&S);/* 初始化栈 */ for(i=0;inextarc){ /* 对i号顶点的每个邻接点的入度减1 */ k=p->adjvex;if(!(--indegree[k]))/* 若入度减为0,则入栈 */ Push(&S,k);} } if(count

while(q

4.用户使用和说明

使用VC++，打开sjjg.cpp文件，接着编译，无错误，然后重建也没有错误，最后执行该文件。显示如下图：

要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。然后还要输入课程先修课程总数，依据教科书图7．26，可以算出有16种关系，分别输出如下图所示。接着程序会根据这些数据，自动生成建立好的邻接表，用户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现在实验的正确测试结果里（如上图）。

5.调试分析

5.1实验过程中出现的问题及解决方法

我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。

5.2测试数据

学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。

5.3测试结果（包含正确和错误的）

正确测试结果：

错误测试结果：

5.4测试数据及程序运行情况

输入的内容如下: 课程编号

课程名称

学分

先决条件 01

程序设计基础

无 02

离散数学

01 03

数据结构

01，02 04

汇编语言

01 05 语言的设计和分析

03，04 06

计算机原理 07

编译原理

05，03 08

操作系统

03，06 09

高等数学

无 10

线性代数

09 11

普通物理

09 12

数值分析

09，10，01 两种编排方法都输出结果为: 第一学期学的课程有:高等数学程序设计基础； 第二学期学的课程有:普通物理 线性代数 汇编语言； 第三学期学的课程有:数值分析 计算机原理 离散数学； 第四学期学的课程有:数据结构；

第五学期学的课程有:操作系统 语言的设计和分析； 第六学期学的课程有:编译原理。

6.总结

刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。

其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。同时也对教学编制问题有了进一步的认识。只要努力去学习，就会灵活的去应用它。

7.参考文献

［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003。［2］《数据结构题集》，严蔚敏，清华大学出版社，2005。［3］《数据结构》（C语言版），刘大有，高等教育出版社，2004。［4］《Data Structure with C++》，William Ford．William Topp，清华大学出版社，2003。