数据结构实验报告
题目：
教学计划的编制问题
姓名：杨维
学号：20090810229
班级：物联网工程0901班
指导老师：李晓鸿
完成日期：20##年11月26日
一、问题描述：
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。
基本要求
（1） 输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。
（2） 若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。
二．需求分析：
1、本程序需要基于图的基本操作来实现
三．概要设计
抽象数据类型：
为实现上述功能需建立一个结点类，线性表类，图类。
算法的基本思想：
1、 图的构建：
建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。
2、 Topsort算法：
先计算每个点的入度，保存在数组中。找到第一个入度为0
的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。
程序的流程：
（1）输入模块： 读入图的信息（顶点和边，用线性表进行存储）。
（2）处理模块：topsort算法。
（3）输出模块：将结果输出。
四．详细设计：
算法的具体步骤：
class Node{//结点类
public:
string node;
int position; //位置
Node* next;
bool visit; //是否被访问
Node(){visit=false;next=NULL;position=0;node=' ';}
};
class Line{ //线性表类
public:
int num;
Node* head;
Node* rear;
Node* fence;
Line(){num=0;head=fence=rear=new Node();}
void insert(int v,string ch){ //插入元素
Node* current=new Node();
current->node=ch;
current->position=v;
fence->next=current;
fence=current;
num++;
}
};
class Graph{ //图类
private:
int numVertex;
int numEdge;
Line* line;
public:
Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];}
void pushVertex(){ //读入点
string ch;
for(int i=0;i<numVertex;i++){
cout<<"请输入顶点"<<i+1<<":";
cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
}
}
void pushEdge(){ //读入边
string ch1,ch2;
int pos1,pos2;
for(int i=0;i<numEdge;i++)
{
cout<<"请输入边"<<i+1<<":";
cin>>ch1>>ch2;
for(int j=0;j<numVertex;j++){
if(line[j].head->node==ch1)
pos1=j; //找到该字母对应的位置
if(line[j].head->node==ch2){
pos2=line[j].head->position;
break;
}
}
line[pos1].insert(pos2,ch2);
}
}
void topsort(){ //拓扑排序
int i;
int *d=new int[numVertex];
for(i=0;i<numVertex;i++)
d[i]=0; //数组初始化
for(i=0;i<numVertex;i++){
Node* p=line[i].head;
while(p->next!=NULL){
d[p->next->position]++; //计算每个点的入度
p=p->next;
}
}
int top=-1,m=0,j,k;
for(i=0;i<numVertex;i++){
if(d[i]==0){
d[i]=top; //找到第一个入度为0的点
top=i;
}
while(top!=-1){
j=top;
top=d[top];
cout<<line[j].head->node<<" ";
m++;
Node* p=line[j].head;
while(p->next!=NULL){
k=p->next->position;
d[k]--; //当起点被删除，时后面的点的入度-1
if(d[k]==0){
d[k]=top;
top=k;
}
p=p->next;
}
}
}
cout<<endl;
if(m<numVertex) //输出点的个数小于输入点的个数，不能完全遍历
cout<<"网络存在回路"<<endl;
delete []d;
}
};
int main(){
int n,m;
cout<<"请输入节点的个数和边的个数"<<endl;
cin>>n>>m;
Graph G(n,m);
G.pushVertex();
G.pushEdge();
G.topsort ();
system("pause");
return 0;
}
五．调试分析：
将建立的线性表输出来检验图的信息是否完全被读入，构建是否正确。
六．测试结果：
七．实验心得：
1、 本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图
的遍历问题中的代码（不过要将结点类中的char改为string型），
自己另外写了topsort函数，就完成了整个程序。
2、 topsort函数中一开始采用的方法是找到一个入度为0的点，完成
相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的
点后面连接的点，这样减少了算法复杂度。
八、附件
教学计划的编制问题.cpp
#include<iostream>
#include<string.h>
using namespace std;
class Node{//结点类
public:
string node;
int position; //位置
Node* next;
bool visit; //是否被访问
Node(){visit=false;next=NULL;position=0;node=' ';}
};
class Line{ //线性表类
public:
int num;
Node* head;
Node* rear;
Node* fence;
Line(){num=0;head=fence=rear=new Node();}
void insert(int v,string ch){ //插入元素
Node* current=new Node();
current->node=ch;
current->position=v;
fence->next=current;
fence=current;
num++;
}
};
class Graph{ //图类
private:
int numVertex;
int numEdge;
Line* line;
public:
Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];}
void pushVertex(){ //读入点
string ch;
for(int i=0;i<numVertex;i++){
cout<<"请输入顶点"<<i+1<<":";
cin>>ch;
line[i].head->node=ch;
line[i].head->position=i;
}
}
void pushEdge(){ //读入边
string ch1,ch2;
int pos1,pos2;
for(int i=0;i<numEdge;i++)
{
cout<<"请输入边"<<i+1<<":";
cin>>ch1>>ch2;
for(int j=0;j<numVertex;j++){
if(line[j].head->node==ch1)
pos1=j; //找到该字母对应的位置
if(line[j].head->node==ch2){
pos2=line[j].head->position;
break;
}
}
line[pos1].insert(pos2,ch2);
}
}
void topsort(){ //拓扑排序
int i;
int *d=new int[numVertex];
for(i=0;i<numVertex;i++)
d[i]=0; //数组初始化
for(i=0;i<numVertex;i++){
Node* p=line[i].head;
while(p->next!=NULL){
d[p->next->position]++; //计算每个点的入度
p=p->next;
}
}
int top=-1,m=0,j,k;
for(i=0;i<numVertex;i++){
if(d[i]==0){
d[i]=top; //找到第一个入度为0的点
top=i;
}
while(top!=-1){
j=top;
top=d[top];
cout<<line[j].head->node<<" ";
m++;
Node* p=line[j].head;
while(p->next!=NULL){
k=p->next->position;
d[k]--; //当起点被删除，时后面的点的入度-1
if(d[k]==0){
d[k]=top;
top=k;
}
p=p->next;
}
}
}
cout<<endl;
if(m<numVertex) //输出点的个数小于输入点的个数，不能完全遍历
cout<<"网络存在回路"<<endl;
delete []d;
}
};
int main(){
int n,m;
cout<<"请输入节点的个数和边的个数"<<endl;
cin>>n>>m;
Graph G(n,m);
G.pushVertex();
G.pushEdge();
G.topsort ();
system("pause");
return 0;
}
第二篇：数据结构与算法实验报告4图及教学计划的编制
数据结构与程序设计专题实验报告
实验报告
一、实验任务
实验题目：图的基本操作及教学计划的编制
二、实验内容
实验四：图的基本操作及教学计划编制问题
（一）实验目的：掌握图的基本操作
（二）基本要求：实现必要的图的基本操作，编写教学计划编制程序，输出正确结果。
（三）内容提要： 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
（4）测试数据：学期总数6；学分上限10；共开设12门课，课程号从C1-C12,学分顺序为 2,3,4,3,2,3,4,4,7,5,2,3。先修关系见教材（严蔚敏-数据结构-C语言版）图7.26.但程序不能仅局限于该测试数据。
三、要点分析
题目中涉及的主要知识点有：
(1)栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存放入度为零的顶点，即当前无先修关系可以编排的课程。
(2)图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点入度减一来实现。
(3)拓扑排序。
（a）在有向图中选一个没有前驱的顶点且输出之。
（b）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止，后一种情况则说明有向图中存在环。
四、程序的算法描述
1、所用存储结构及宏定义：
#define MAX_VERTEX_NUM 100 //最大课程总数
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间的分配增量
typedef struct ArcNode
{
int adjvex;//该弧所指向顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode
{
char name[24];//课程名
int classid; //课程号
int credit;//课程的学分
int indegree;//该结点的入度
int state;//该节点的状态，1代表已学，0代表未学
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;//顶点向量
int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
typedef int ElemType;
typedef struct //栈
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
2、程序中各函数的简要说明：
（1）void CreatGraph(ALGraph &G)构建图。先输入各顶点（课程）的信息，包括课程名、课程号、课程学分。再输入弧信息（先修关系），将弧中顶点赋为弧尾，相应入度加1.最后输出构建好的邻接表。
（2）void FindInDegree(ALGraph G, int indegree[])求图中各节点的入度。从每个节点的第一条依附于该节点的弧出发，将该节点对应的入度加1，接着指向下一条弧执行同样的操作，直至指针为空。
（3）void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)按课程尽可能集中到前几个学期进行编排。当每个学期的学分总数不超过学分上限时，在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该顶点（课程）和所有以它为尾的弧。当某学期的学分已满时，进入下一学期的编排。重复上述几步，直至全部顶点（课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有向图中存在环。
（4）void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)按课程尽量均匀分布编排。当每个学期的学分总数不超过学分上限且课程数不超过课程数上限时，在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该顶点（课程）和所有以它为尾的弧。当某学期的学分已满或课程数已满时，进入下一学期的编排。重复上述几步，直至全部顶点（课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有向图中存在环。
（5）int main()主函数。在主函数中输出交互界面，要求用户输入各项信息。调用CreateGraph函数创建图，之后根据用户选择调用TopologicalSort_1或者TopologicalSort_2函数进行拓扑排序并输出编排结果，写入文件中。
3、源代码
完整程序及相应说明如下：
#include "stdio.h"
#include "malloc.h"
#define MAX_VERTEX_NUM 100 //最大课程总数
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间的分配增量
typedef struct ArcNode
{
int adjvex;//该弧所指向顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode
{
char name[24];//课程名
int classid; //课程号
int credit;//课程的学分
int indegree;//该结点的入度
int state;//该节点的状态，1代表已学，0代表未学
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef int ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void CreatGraph(ALGraph &G)//构建图
{
int i, m, n;
ArcNode *p;
printf("请输入需要编排课程总数:");
scanf("%d",&G.vexnum);
for( i=1;i<=G.vexnum;i++)
{
printf("\n请输入课程名:");
scanf("%s",&G.vertices[i].name);
printf("\n请输入课程号:");
scanf("%d",&G.vertices[i].classid);
printf("\n请输入该课程的学分:");
scanf("%d",&G.vertices[i].credit);
G.vertices[i].indegree=0;
G.vertices [i].state=0;//NOTSTUDY
G.vertices[i].firstarc=NULL;
}
printf("请输入课程先修关系总数：");
scanf("%d",&G.arcnum);
printf("请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):\n");
for (i = 1; i <= G.arcnum; i++)
{
printf("\n请输入存在先修关系的两个课程的序号:");
scanf("%d,%d",&n,&m);
while (n<0||n>G.vexnum||m<0||m>G.vexnum)
{
printf("输入的顶点序号不正确请重新输入:");
scanf("%d,%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{
printf("memory allocation failed,goodbey");
return;
}
p->adjvex = m;
p->nextarc=G.vertices[n].firstarc;
G.vertices[n].firstarc = p;
}
printf("\n建立的邻接表为:\n");//输出建立好的邻接表
for(i=1;i<=G.vexnum;i++)
{
printf("%d:->",G.vertices[i].classid);
for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
printf("%d->",p->adjvex);
printf("NULL");
printf("\n");
}
}
void InitStack(SqStack &S)
{
S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if (!S.base)
{
printf("ERROR");
return;
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
int StackEmpty(SqStack &S)
{
if(S.top==S.base)
return 1;
else
return 0;
}
void Push(SqStack &S,int e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int*)realloc(S.base,(S.stacksize+10)*sizeof(int));
if(!S.base)
{
printf("ERROR");
return;
}
S.top=S.base+S.stacksize;
S.stacksize+=10;
}
*S.top++=e;
}
int Pop(SqStack &S, int *e)
{
if(S.top==S.base)
return 1;
*e=*--S.top;
return 0;
}
void FindInDegree(ALGraph G, int indegree[])//求图中各节点的入度
{
int i;
for (i = 1; i <= G.vexnum; i++)
indegree[i] = 0;
for (i = 1; i <= G.vexnum; i++)
{
while (G.vertices[i].firstarc)
{
indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)
{
FILE *fp;
fp=fopen("bianpai.txt","w");
struct ArcNode *p;
SqStack S;
int indegree[MAX_VERTEX_NUM];//存放各节点的入度
int i,j,k;
int count; //课程编括排数目计数器
int sumcredit;//每个学期的课程学分累加器
FindInDegree(G,indegree);
for (i = 1; i <= G.vexnum; i++)
G.vertices[i].indegree=indegree[i];
InitStack(S);
count=0;
k=0;
while(count!=G.vexnum && k<=numterm)
{
sumcredit=0;
for(i=1;i<=G.vexnum;i++)
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==0))//入度为零的节点入栈，即无先修的课程入栈
{
Push(S,i);
G.vertices[i].state =1;//避免入度为零节点重复入栈
}
if((!StackEmpty(S))&&(sumcredit<=uplcredit))
{
k= k+1;
printf("\n");
printf("第d个学期学得课程有:\n",k);
sumcredit = 0;
for(i=1;i<=G.vexnum;i++)
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==0))//入度为零的节点入栈，即无先修的课程入栈
Push(S,i);
while((!StackEmpty(S))&&(sumcredit<uplcredit))//栈非空&&学分总数小于学分上限
{
Pop(S,&j);
sumcredit = sumcredit + G.vertices[j].credit;
if(sumcredit <= uplcredit)
{
printf(" %s ",G.vertices[j].name);
fprintf(fp," %s ",G.vertices[j].name);
count++;
for(p=G.vertices[j].firstarc;p;p=p->nextarc)//对j号顶点每个邻接点的入度减一
G.vertices[p->adjvex].indegree--;
}
else Push(S,j);//将未输出的节点重新压入栈
}
}
fprintf(fp,"\n");
}
printf("\n");
if(count<G.vexnum)
printf("\n课程编排出错\n");
else
{
printf("\n课程编排成功\n");
}
fclose(fp);
}
void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)
{
FILE *fp;
fp=fopen("bianpai.txt","w");
struct ArcNode *p;
SqStack S;
int indegree[MAX_VERTEX_NUM];//存放各节点的入度
int i,j,k,m,n;
int maxnum;
int sumnum;
int count; //课程编排数目计数器
int sumcredit;//每个学期的课程学分累加器
FindInDegree(G,indegree);
for (i = 1; i <= G.vexnum; i++)
G.vertices[i].indegree=indegree[i];
InitStack(S);
count=0;
k=0;
maxnum=G.vexnum/numterm+1;
sumnum=0;
while(count!=G.vexnum && k<=numterm)
{
sumcredit=0;
for(i=1;i<=G.vexnum;i++)
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==0))//入度为零的节点入栈，即无先修的课程入栈
{
Push(S,i);
G.vertices[i].state =1;//避免入度为零节点重复入栈
}
if((!StackEmpty(S))&&(sumcredit<=uplcredit))
{
k= k+1;
printf("\n");
printf("第d个学期学得课程有:\n",k);
sumcredit = 0;
sumnum=0;
for(i=1;i<=G.vexnum;i++)//入度为零的节点入栈，即无先修的课程入栈
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==0))
Push(S,i);
while((!StackEmpty(S))&&(sumcredit<uplcredit)&&(sumnum<maxnum))//栈非空&&学分总数小于学分上限&&不超过每学期课程上限
{
Pop(S,&j);
sumcredit = sumcredit + G.vertices[j].credit;
sumnum=sumnum+1;
if((sumcredit<=uplcredit)&&(sumnum<=maxnum))
{
printf(" %s ",G.vertices[j].name);
fprintf(fp," %s ",G.vertices[j].name);
count++;
for(p=G.vertices[j].firstarc;p;p=p->nextarc)//对j号顶点每个邻接点的入度减一
G.vertices[p->adjvex].indegree--;
}
else Push(S,j);//将未输出的节点重新压入栈
}
}
fprintf(fp,"\n");
}
printf("\n");
if(count<G.vexnum)
printf("\n课程编排出错\n");
else
{
printf("\n课程编排成功\n");
}
fclose(fp);
}
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);
return 0;
}
五、程序运行结果
六、实验总结
通过本次实验一方面对学过的有关栈的知识进行了复习和应用，进一步熟悉和掌握了栈的有关操作。另一方面，熟悉和掌握了图的有关操作，尤其是邻接表作为存储结构的图的创建。加深了对拓扑排序的理解。对拓扑排序的应用还有待熟悉和提高。
七、致谢词
非常感谢刘老师在本次实验中对我的指导与帮助，尤其是在拓扑排序处的耐心指导，帮助我得到正确的运行结果。
八、参考文献
1.陈维兴，林小茶.C++面对对象的程序设计教程（第三版）.北京：清华大学出版社,2009
2.谭浩强.C程序设计（第四版）.北京：清华大学出版社，2010
3.严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，1997.4