问题描述：
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。
基本要求：
（1） 输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。
（2） 若根据输入条件问题无解，则报告适当的信息；
否则将教学计划输出到用户指定的文件中。
一、需求分析：
本程序需要基于图的基本操作来实现
二、概要设计 ：
抽象数据类型 ：
为实现上述功能需建立一个结点类，线性表类，图类。
算法的基本思想 ：
1、图的构建：
建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。
2、Topsort算法：
先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。
程序的流程
程序由三个模块组成：
输入模块：
读入图的信息（顶点和边，用线性表进行存储）。
处理模块：topsort算法。
输出模块：将结果输出。
三、详细设计
算法的具体步骤：
cla Node{//结点类 public: string node; int position; //位置 Node* next; bool visit; //是否被访问
Node(){visit=false;next=NULL;position=0;node=" ";} }; cla 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++; } }; cla 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
cout
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
{
cout
cin>>ch1>>ch2;
for(int j=0;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
d[i]=0; //数组初始化
for(i=0;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
if(d[i]==0){
d[i]=top; //找到第一个入度为0的点
top=i;
}
while(top!=-1){ j=top; top=d[top];
coutnode
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
cout>n>>m; Graph G(n,m); G.pushVertex(); G.pushEdge(); G.topsort (); system("pause"); return 0; }
四、调试分析
略。
五、测试结果
本实验的测试结果截图如下：
注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入。
六、用户使用说明（可选）
1、本程序的运行环境为windows 操作系统，执行文件为Untitled1.exe 2、运行程序时
提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。
七、实验心得（可选）
1、本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图 的遍历问题中的代码（不过要将结点类中的char改为string型）， 自己另外写了topsort函数，就完成了整个程序。
2、topsort函数中一开始采用的方法是找到一个入度为0的点，完成 相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的 点后面连接的点，这样减少了算法复杂度。
附录（实验代码）：
#include #include using namespace std; cla Node{//结点类 public: string node; int position; //位置 Node* next; bool visit; //是否被访问
Node(){visit=false;next=NULL;position=0;node=" ";} }; cla 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++; } }; cla 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
cout
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
{
cout
cin>>ch1>>ch2;
for(int j=0;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
d[i]=0; //数组初始化
for(i=0;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
if(d[i]==0){
d[i]=top; //找到第一个入度为0的点
top=i;
}
while(top!=-1){ j=top; top=d[top];
coutnode
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
cout>n>>m; Graph G(n,m); G.pushVertex(); G.pushEdge(); G.topsort (); system("pause"); return 0; }
数据结构实验报告
实验十:教学计划的编制问题
姓名：戴铁泉 学号：20101410305 班级：物联网1001班 完成日期：2012.05.21
一、问题描述：
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。
基本要求
（1） 输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。
（2） 若根据输入条件问题无解，则报告适当的信息；
否则将教学计划输出到用户指定的文件中。
二．需求分析：
1、本程序需要基于图的基本操作来实现
三．概要设计
抽象数据类型：
为实现上述功能需建立一个结点类，线性表类，图类。
算法的基本思想：
1、
图的构建：
建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。
2、Topsort算法：
先计算每个点的入度，保存在数组中。找到第一个入度为0 的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。
程序的流程：
（1） 输入模块：
读入图的信息（顶点和边，用线性表进行存储）。
（2） 处理模块：topsort算法。
（3） 输出模块：将结果输出。
四．详细设计：
算法的具体步骤：
cla Node{//结点类 public:
string node;
int position; //位置
Node* next;
bool visit; //是否被访问
Node(){visit=false;next=NULL;position=0;node=" ";} }; cla 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++; }; cla Graph{
//图类 private: int numVertex; int numEdge; Line* line; public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点
} void pushEdge(){ //读入边
string ch1,ch2; int pos1,pos2; for(int i=0;i
} cout>ch; line[i].head->node=ch; line[i].head->position=i;
}
} cout>ch1>>ch2; for(int j=0;j
} line[pos1].insert(pos2,ch2); if(line[j].head->node==ch1) pos1=j;
//找到该字母对应的位置
if(line[j].head->node==ch2){
} pos2=line[j].head->position; break;
void topsort(){
//拓扑排序
int i; int *d=new int[numVertex];
for(i=0;i
//数组初始化
for(i=0;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
} while(top!=-1){ if(d[i]==0){ d[i]=top;
//找到第一个入度为0的点
top=i;
j=top;
top=d[top];
coutnode
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
if(m
//输出点的个数小于输入点的个数，不能完全遍历
cout
delete []d; } }; int main(){
int n,m; cout>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 #include using namespace std; cla Node{//结点类 public:
string node;
int position; //位置
Node* next;
bool visit; //是否被访问
Node(){visit=false;next=NULL;position=0;node=" ";} }; cla 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++; cla Graph{
//图类 private:
int numVertex; int numEdge; Line* line; public:
Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点
} void pushEdge(){ //读入边 string ch; for(int i=0;i
} cout>ch; line[i].head->node=ch; line[i].head->position=i;
} string ch1,ch2; int pos1,pos2; for(int i=0;i
} cout>ch1>>ch2; for(int j=0;j
} line[pos1].insert(pos2,ch2); if(line[j].head->node==ch1) pos1=j;
//找到该字母对应的位置
if(line[j].head->node==ch2){
} pos2=line[j].head->position; break;
void topsort(){
//拓扑排序
int i; int *d=new int[numVertex];
for(i=0;i
//数组初始化
for(i=0;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
} while(top!=-1){ if(d[i]==0){ d[i]=top;
//找到第一个入度为0的点
top=i;
j=top;
top=d[top];
coutnode
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
//输出点的个数小于输入点的个数，不能完全遍历
cout
delete []d; } }; int main(){
int n,m; cout>n>>m; Graph G(n,m); G.pushVertex();
G.pushEdge(); G.topsort (); system("pause");
return 0; }
数据结构课程设计报告
题目：教学计划编制
一.需求分析
（1）实验内容和实验目的：
1.大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。
2.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.
3.本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程.（2）测试数据：
学期总数：6；
学分上限：10；
该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图7．26。
（3）测试结果（包含正确和错误的）：
正确测试结果：
错误测试结果：
二.概要设计
1.抽象数据类型图的定义如下: 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.主程序
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; } 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); 拓扑排序来编排课程 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．主程序和其他算法
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; } void CreatGraph(ALGraph *G)//构件图 {
int i, m, n;
ArcNode *p;
printf(\"请输入需要编排课程总数:\\n\");
scanf(\"%d\",&G->vexnum);
for( i=1;ivexnum;i++)
{
printf(\"请输入课程名\\n\");
scanf(\"%s\",&G->vertices[i].name);
printf(\"请输入课程号\\n\");
scanf(\"%d\",&G->vertices[i].claid);
printf(\"请输入该课程的学分\\n\");
scanf(\"%d\",&G->vertices[i].credit);
G->vertices[i].indegree=0;
G->vertices [i].state=NOTSTUDY;
G->vertices[i].firstarc=NULL;
}
printf(\"请输入课程先修关系总数：\");
scanf(\"%d\",&G->arcnum);
printf(\"请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):\\n\");
for (i = 1; i arcnum; i++)
{
printf(\"\\n请输入存在先修关系的两个课程的序号:\");
scanf(\"%d,%d\",&n,&m);
while (n G->vexnum || m G->vexnum)
{
printf(\"输入的顶点序号不正确 请重新输入:\");
scanf(\"%d,%d\",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{
printf(\"memory allocation failed,goodbey\");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf(\"\\n建立的邻接表为:\\n\");
//输出建立好的邻接表
for(i=1;ivexnum;i++)
{
printf(\"%d:->\",G->vertices[i].claid);
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\");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE; } int StackEmpty(SqStack *S) {
if(S->top==S->base)
return OK;
else
return ERROR; } void Push(SqStack *S,int e) {
if(S->top - S->base >= S->stacksize)
{
S->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(int));
if(!S->base)
{
printf(\"ERROR\");
exit(1);
}
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e; } int Pop(SqStack *S, int *e) {
if(S->top == S->base) exit(1);
*e = * --S->top;
return 0; } void FindInDegree(ALGraph G, int indegree)//求图中各节点的入度 {
int i;
for (i = 1; i
indegree[i] = 0;
for (i = 1; 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\");
ArcNode *p;
SqStack S;
int indegree[M];//存放各节点的入度
int i,j, k, m,n;
int count; //课程编排数目计数器
int sumcredit;//每个学期的课程学分累加器
FindInDegree(G, indegree);
for (i = 1; i
G.vertices[i].indegree=indegree[i];
InitStack(&S);
count=0;
k=0;
while(count!=G.vexnum && k
{
sumcredit=0;
for(i=1;i
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY))
{
Push(&S,i);
G.vertices[i].state = STUDY;//避免入度为零节点重复入栈
}
if(!StackEmpty(&S)&&(sumcredit
{
k= k+1;
printf(\"\\n\");
printf(\"第%d个学期学得课程有:\\n\",k);
sumcredit = 0;
for(i=1;i
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY))
Push(&S,i);
while((!StackEmpty(&S))&&(sumcredit
{
Pop(&S,&j);
sumcredit = sumcredit + G.vertices[j].credit;
if(sumcredit
{
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
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\");
ArcNode *p;
SqStack S;
int indegree[M];
int i,j, k, m,n;
int maxnum;
int sumnum;
int count; //课程编排数目计数器
int sumcredit;//每个学期的课程学分累加器
FindInDegree(G, indegree);
for (i = 1; 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
{
for(i=1;i
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY))
{
Push(&S,i);
G.vertices[i].state = STUDY;
}
if(!StackEmpty(&S)&&(sumcredit
{
k= k+1;
printf(\"\\n\");
printf(\"第%d个学期学得课程有:\",k);
sumcredit = 0;
sumnum = 0;
for(i=1;i
if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY))
Push(&S,i);
while((!StackEmpty(&S))&&(sumcredit
//栈非空&&学分总数小于学分上限&&学期课程数目小于学期最大数目
{
Pop(&S,&j);//出栈
sumcredit = sumcredit + G.vertices[j].credit;
sumnum = sumnum+1;
if((sumcredit
{
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
printf(\"课程编排出错\\n\"); else {
printf(\"课程编排成功\\n\"); } fclose(fp); 流程图如下所示：
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()
四．调试分析：
（1）实验过程中出现的问题及解决方法
我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。
（2）实验体会:
经过此次课程设计，我们认识到了理论与实践结合的重要性，仅仅只是从课本上学到算法原理是远远不够的。在实践中，我们总会出现许多错误。这就要求我们以一个脚踏实地的态度来处理问题。我们深刻地认识到自己写程序的不足，使我们学到了好多有用的知识，让我们明白了C语言的语句用法。
五．用户使用和说明：
使用VC++，打开教学计划编制问题.cpp文件，接着编译，无错误，然后重建也没有错误，最后执行该文件。显示如下图：
要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。然后还要输入课程先修课程总数，依据教科书图7．26，可以算出有16种关系，分别输出如下图所示。接着程序会根据这些数据，自动生成建立好的邻接表，用户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现在实验的正确测试结果里（如上图）。
六.测试数据及程序运行情况: 输入的内容如下: 课程编号
课程名称
学分
先决条件
01
程序设计基础
2
无 02
离散数学
3
01 03
数据结构
4
01，02 04
汇编语言
3
01 05
语言的设计和分析
2
03，04 06
计算机原理
3
11 07
编译原理
4
05，03 08
操作系统
4
03，06 09
高等数学
7
无 10
线性代数
5
09 11
普通物理
2
09 12
数值分析
3
09，10，01
两种编排方法都输出结果为: 第一学期学的课程有:高等数学 程序设计基础 第二学期学的课程有:普通物理 线性代数 汇编语言 第三学期学的课程有:数值分析 计算机原理 离散数学 第四学期学的课程有:数据结构
第五学期学的课程有:操作系统 语言的设计和分析 第六学期学的课程有:编译原理 七.参考文献: 《数据结构》、《C程序设计》、互联网
数据结构实验指导
说明：课内上机要求完成实验一到实验四的内容，并完成实验报告，实验报告在十七周星期三之前交，其他实验请大家课外抽时间完成。给出的示例程序供大家参考，大家实验的时候要自己动手编写程序，切不可完全照抄，每个实验具体的实验题目大家可以做示例的题目，也可以自己定一题目，只需用到该实验的知识点即可，编程语言大家可以选用自己熟悉的语言。
一．实验要求：
书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。。
二．主要仪器设备：（所开实验的主要仪器设备）
硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PⅢ及以上的微机。
三、实验项目内容简介
为了达到实验目的，本课程安排了四个实习单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容。
1、线性表基本操作
（1) 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现 （2)以线性表的各种操作（建立、插入、删除等）的实现为重点
（3) 通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。
2、栈、队列以及递归算法的设计
（1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们 （2) 训练的要点是“栈”的观点及其典型用法；
问题求解的状态表示及其递归算法；
由递归程序到非递归程序的转化方法
3、树、图及其应用
（1) 树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。
（2) 要求学生熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。
（3) 训练的要点是：递归算法的设计方法；
表达式的求值技术；
哈夫曼方法及其编译码技术；
完整的应用系统的用户界面设计和操作定义方法；
矩阵乘法的特殊操作顺序；
路径遍历（树、图的遍历）技术。
4、查找和排序
本次实习旨在集中对几个专门的问题做较为深入的探讨和理解
重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。
四、主要参考书
1、《数据结构题集》（C语言版）实习题部分，清华大学出版社,1999.11
2、《数据结构习题与解析》（C语言篇），李春葆 编著，清华大学出版社，2000.1
3、宁正元《数据结构习题解析与上机实验指导》
水利水电出版社（2003年）
实验一
线性表的操作
一、实验目的
1．熟悉C语言的上机环境，掌握C语言的基本结构。
2．会定义线性表的顺序存储结构。（链式存储结构） 3．熟悉对顺序表（单链表）的一些基本操作。
二、实验要求
1．认真阅读和掌握本实验内容所给的全部程序。
2．保存和打印出程序运行结果，并结合程序进行分析。
注意事项
在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。
三、实验内容
1、示例（以顺序表为示例，同学们也可以编程实现单链表的创建、查找、插入、删除等功能）
以输入整形数据为主，输入后按“？”结束输入。
程序所能表达到的功能为：实现顺序表的创建、查找、插入、删除等功能。
程序运行后，输入数据并执行。
#include "stdio.h" #include "conio.h" #define MaxSize 50 typedef char elemtype; typedef struct node { elemtype data[MaxSize]; int len; }lnode,*List; void init(List L){ L->len=0;} int length(List L) { return L->len;} elemtype getnode(List L,int pos) { if(posL->len) printf("error"); else return L->data[pos-1]; } int locate(List L,elemtype x) { int i=0; while(ilen && L->data[i]!=x) i++; if(i==L->len) return -1; else return(i+1); } void insert(List L,int pos,elemtype x) { int j; if(posL->len+1) printf("insert error\\\\n"); else { L->len++; for(j=L->len;j>=pos;j--) L->data[j]=L->data[j-1]; L->data[pos-1]=x; }; } void delnode(List L,int pos) { int j; if(posL->len)printf("del error\\\\n"); else { for(j=pos;jlen;j++) L->data[j-1]=L->data[j]; L->len--;} } void print(List L) { int i; for(i=1;ilen;i++) printf("%c->",L->data[i-1]); printf("%c",L->data[L->len-1]); } main() { int i=1,n; lnode L; char ch,x; init(&L); printf("\\\\n\\\\n\\\\n*******************************顺序表演示程序***********\\\\n"); printf("请输入你想建立的顺序表的元素，以？结束:"); ch=getchar(); while(ch!="?") {insert(&L,i,ch); i++; ch=getchar(); }; printf("你建立的顺序表为:"); print(&L); printf("\\\\n顺序表的长度为:%d",L.len); printf("\\\\n输入你想查找的元素："); fflush(stdin); scanf("%c",&x); printf("你查找的元素为%c序位为%d",x,locate(&L,x)); printf("\\\\n输入你想查找的元素序位:"); scanf("%d",&n); printf("\\\\n你查找的元素为：%c",getnode(&L,n)); printf("\\\\n输入你想插入的元素以及序位:"); fflush(stdin); scanf("%c,%d",&x,&n); insert(&L,n,x); printf("\\\\n插入后顺序表为："); print(&L); fflush(stdin); printf("\\\\n请输入你想删除的元素序位："); scanf("%d",&n); delnode(&L,n); printf("\\\\n删除后的顺序表为："); print(&L); getch(); }
四、测试结果
运行程序，屏幕显示：“请输入你想建立的顺序表的元素，以？结束:” 输入：54381 你建立的顺序表为:5—>4—>3—>8—>1 顺序表的长度为:5 输入你想查找的元素：4 你查找的元素为4序位为2 输入你想查找的元素序位:4 你查找的元素为：8
输入你想插入的元素以及序位:"：6，3 插入后顺序表为：5—>4—>6—>3—>8—>1 请输入你想删除的元素序位：5 删除后的顺序表为：5—>4—>6—>3—>1
实验二 二叉树的操作 一．实验目的
理解并熟悉掌握创建二叉树和实现二叉树的三种遍历 二．实验内容
创建二叉树和实现二叉树的三种遍历
根据提示输入字符型数据创建二叉树，输入值为所有字符型数据 输出为遍历后的每个结点的值的顺序
创建二叉树并能实现二叉树的先序、中序、后序遍历 如果输入数据为：a b c 输出结果为：a b c
b a c
b c a
程序流程：main()clrscr()createtree()preorder()inorder()postorder 源程序
#include "stdlib.h" struct tnode {char data; struct tnode*lchild; struct tnode*rchild; }; struct tnode tree;
void createtree(struct tnode*t) {struct tnode*p=t;
char check; if(p->lchild==NULL||p->rchild==NULL) /*判断左右子树是否为空*/
{printf("please enter the data:");
scanf("%c",&(p->data));
getchar();
}
/*输入根结点数据*/
/*创建函数*/
/*定义二叉树指针*/
/*引入头文件*/ /*定义二叉树存储结构*/
/*把二叉树指针给p*/ if(p->lchild==NULL)
{printf("%c leftchild is null.Add? y/n\\\\n",p->data); /*左子树空，询问是否创建*/
scanf("%c",&check);
getchar();
if(check=="y")
{struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode)); /*开辟空间*/
q->lchild=NULL;
q->rchild=NULL;
p->lchild=q;
createtree(q);
}
} if(p->rchild==NULL)
{printf("%c rightchild is NULL.Add? y/n\\\\n",p->data); /*右子树空，询问是否创建*/
scanf("%c",&check);
getchar();
if(check=="y")
{struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode)); /*开辟空间*/
q->lchild=NULL;
q->rchild=NULL;
p->rchild=q;
createtree(q);
}
} }
void preorder(struct tnode*t) {if(t)
{printf("%c ",t->data);
/*输出根结点数据*/
/*先序遍历函数*/
/*连到二叉树上*/
preorder(t->lchild);
preorder(t->rchild);
} }
void inorder(struct tnode*t) {if(t)
{inorder(t->lchild);
printf("%c ",t->data);
inorder(t->rchild);
} } void postorder(struct tnode*t) /*后序遍历函数*/ {if(t)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c ",t->data);
} }
void main() { clrscr();
/*清屏函数*/
/*左子树*/ /*右子树*/ /*创建二叉树*/
/*中序遍历函数*/ tree.lchild=NULL; tree.rchild=NULL; createtree(&tree);
preorder(&tree);
printf("\\\\n"); inorder(&tree);
/*先序遍历*/
/*中序遍历*/ printf("\\\\n"); postorder(&tree); }
三．使用说明
程序运行：
先输入根结点数据，例如：a 输入y或n判断是否创建左子树。输入y然后输入左子树数据 输入y或n判断是否创建右子树。输入y然后输入右子树数据 按回车可查看遍历结果并退出程序。
四．测试结果
运行程序，屏幕提示：
please enter the data:a
/*首先输入根结点，为a*/ a leftchild is null.add?y/n
/*询问是否输入a结点的左结点*/ y
/*输入*/ please enter the data:b
/*输入结点a的左结点，为b*/ b leftchild is null.add?y/n
/*询问是否输入b结点的左结点*/ n
/*不输入*/ b rightchild is null.add?y/n
/*询问是否输入b结点的右结点*/ n
/*不输入*/ a rightchild is null.add?y/n
/*询问是否输入a结点的右结点*/ y
/*输入*/ please enter the data:c
/*输入结点a的右结点，为c*/ c leftchild is null.add?y/n
/*询问是否输入c结点的左结点*/ n
/*不输入*/ c rightchild is null.add?y/n
/*询问是否输入c结点的右结点*/ n
/*不输入*/ 程序退出，显示结果应为：
a b c
/*先序*/
/*后序遍历*/
b a c
/*中序*/
b c a
/*后序*/
实验三
图的遍历操作
一．实验目的：
该实验主要完成对图的创建，并实现图的深度优先遍历和广度优先遍历 二．实验内容：
所输入的数据要为整形数据
输出的形式为：每按一次回车，遍历一个结点
能创建最大结点树为30的任意图，实现对无向图的两种遍历 程序流程：
main()clrscr()visited()DFS()visited()BFS() 源程序：
#include #define maxvex 30 struct edgenode {int adjvex; char info; struct edgenode*next; }; struct vexnode {char data; struct edgenode*link; }; typedef struct vexnode adjlist[maxvex]; /*自定义adjlist为结构体数组类型*/ adjlist tu1;
void creategraph(adjlist g,int n) {int e,i,s,d;
/*图创建函数*/
/*定义存储边、点的变量*/ /*定义边的结构体指针*/ /*显示提示输入点，边*/
/*定义结构体数组变量tu1*/
/*定义点的结构体*/
/*引用两个头文件*/ /*定义MAXVEX=30*/
/*定义边的结构体*/ struct edgenode*p,*q;
printf("the point(n) and edge(e):"); scanf("%d,%d",&n,&e); for(i=1;i
{getchar();
/*接收点、边存入n,e中*/
/*提示输入结点信息*/ /*存储信息*/ /*最后指针为空*/
printf("\\\\tthe %d information:",i);
scanf("%c",&g[i].data);
g[i].link=NULL;
}
for(i=1;i
{printf("\\\\nthe%d edges=>\\\\n\\\\t :",i);
scanf("%d,%d",&s,&d);
/*提示输入边信息*/ /*接收边的信息*/
p=(struct edgenode*)malloc(sizeof(struct edgenode));
q=(struct edgenode*)malloc(sizeof(struct edgenode)); /*开辟两个存储边的空间*/
p->adjvex=d;
p->info=g[d].data;
q->adjvex=s;
q->info=g[s].data;
p->next=g[s].link;
g[s].link=p;
q->next=g[d].link;
g[d].link=q;
} }
int visited[maxvex];
/*定义访问数组*/
/*q和s的link指针连接起来*/ /*完成一个边的创建*/
/*p和s的link指针连接起来*/
/*把另一个点存储下来*/
/*把其中一个点存储下来*/ void dfs(adjlist adj,int v) {int i; struct edgenode*p; visited[v]=1;
/*深度优先遍历函数*/
/*定义边指针*/
/*把开始遍历的点在访问数组中标识*/
/*输出正访问的点*/ printf("now is at point %d",v);
p=adj[v].link; printf("the data is %c \\\\n",adj[v].data); getch(); while(p)
{if(visited[p->adjvex]==0)
dfs(adj,p->adjvex);
p=p->next;
} }
int quene[maxvex]; void bfs(adjlist adj,int vi) {int m=maxvex;
/*输出点的信息*/
/*没有访问的再调用DFS函数*/
/*访问过的判断下一个*/
/*广度优先遍历函数*/ /*定义一个队列*/ int front=0,rear=1,v; struct edgenode*p; visited[vi]=1;
/*定义边指针*/
/*开始访问的点标识一下*/
/*输出正访问的点*/ printf("now visit the point:%d\\\\n",vi);
getch();quene[rear]=vi; while(front!=rear)
{front=(front+1)%m;
v=quene[front];
p=adj[v].link;
while(p)
{if(visited[p->adjvex]==0)
{visited[p->adjvex]=1;
/*把访问过的点放入数组中*/
/*判断p->adjvex点是否访问过*/ /*访问没有访问过的结点*/ printf("now visit the point:%d\\\\n",p->adjvex); /*输出正访问的结点*/ getch();
rear=(rear+1)%m;
quene[rear]=p->adjvex;
}
p=p->next;
/*指向下一个*/
/*放入数组中*/
}
} }
void main() {int i;clrscr(); creategraph(tu1,0); for(i=1;i
visited[i]=0;
dfs(tu1,1);
getch();
/*访问数组初始化*/
/*调用DFS*/
/*创建图*/
/*等待输入*/
for(i=1;i
visited[i]=0; bfs(tu1,1);
} 三．使用说明：
根据屏幕上的英文提示先输入结点的个数和边数。然后输入各结点存储的信息，再输入定义的边，形成图。最后分别按照DFS深度优先遍历和BFS广度优先遍历实现对图的遍历。
四．测试结果：
运行程序，屏幕提示：
the point(n) and edge(e):4,3 /*输入顶点和边的数目*/ the 1 information:a
/*各个顶点的信息*/ the 2 information:b the 3 information:c the 4 information:d the 1 edges=>
/*各个边的连接情况*/ :1,2 the 2 edges=> :1,3 the 3 edges=>
/*调用BFS*/ :3,4
now is at point 1 the data is a /*深度优先遍历结果*/
now is at point 3 the data is c now is at point 4 the data is d now is at point 2 the data is b now visit the point:1
/*广度优先遍历结果*/ now visit the point:3 now visit the point:2 now visit the point:4
a b c d 实验四
栈的基本操作
一、实验目的：
1．熟练掌握栈的结构，以及这种数据结构的特点；
2． 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；
二、实验内容：
计算表达式的值 【问题描述】
计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式，比中缀表达式计算起来更方便简单些，中缀表达式要计算就存在着括号的匹配问题，所以在计算表达式值时一般都是先转换成后缀表达式，再用后缀法计算表达式的值。如：表达式(a+b*c)/d-e用后缀法表示应为abc*+d/e-。只考虑四则算术运算，且假设输入的操作数均为1位十进制数（0—9），并且输入的后缀形式表达式不含语法错误。
【数据描述】 #define add 43 /*运算符加号„+‟的ASCII码*/ #define subs 45 /*运算符减号„-‟的ASCII码*/ #define mult 42 #define div 47 /*运算符乘号„*‟的ASCII码*/ /*运算符除号„/‟的ASCII码*/ #define MAXSIZE 100 typedef struct{ { int stkdata[MAXSIZE];//用数组来表示栈空间，定义长度为MAXSIZE的栈
int top;
}STKzone; typedef STKzone *STK; typedef enum{true=1,false=0} bool; typedef enum{ok,error} status;
【C源程序】 #include #define add 43
/*运算符加号„+‟的ASCII码*/ //栈顶指针 #define subs 45
/*运算符减号„-‟的ASCII码*/ #define mult 42
/*运算符乘号„*‟的ASCII码*/ #define div 47
/*运算符除号„/‟的ASCII码*/ #define MAXSIZE 100 typedef struct { int stkdata[MAXSIZE];/*用数组来表示栈空间，定义长度为MAXSIZE的堆栈*/
int top; /*栈顶*/ }STKzone; typedef STKzone *STK; typedef enum{true=1,false=0} bool; typedef enum{ok,error} status; STKzone expSTKzone; STK expSTK; STK initSTK(STKzone *stack_zone){
/*执行栈初始化，建栈指针*/
STK p;
p=stack_zone;
p->top=0; } status push(int *term,STK pstk){ /*将一结构型数据送入栈中*/ if(pstk->top==MAXSIZE)
return error; /*栈满，进栈失败*/ pstk->stkdata[pstk->top] =*term; (pstk->top)++;/*栈顶指针移动*/ return ok; }/*push*/ bool emptySTK(STK pstk){ /*判断栈是否为空栈*/ return(pstk->top==0); } status pop(int *pdata, STK pstk){
/*从栈中取出一结构型数据*/ if(emptySTK(pstk))
return error; (pstk->top)--;/*退栈*/ *pdata =pstk->stkdata[pstk->top]; return ok; } void synerror() { printf("\\\\n表达式语法错！"); exit(); } int eval(char tag,int a1,int a2) { switch(tag)
{ case add:return(a1+a2); case subs:return(a1-a2); case mult:return(a1*a2); case div:return(a1/a2); } } main() { char c;
int opd1,opd2,temp,c1;
expSTK=initSTK(&expSTKzone);
printf("\\\\n后置表达式: ");
while((c=getchar())!="\\\\n")
{ if(c== " ") continue; if((c>47)&&(c
{ putchar(c);
/*判断是否是0—9的字符*/ c1=c-48;
/*把输入的字符型数字转换成数字*/
if(push(&c1,expSTK)==error)/*运算分量进栈*/
{ printf("\\\\n表达式太长\\\\n");
exit();} } else if((c==add)||(c==subs)||(c==mult)||(c==div))
{ putchar(c); if(pop(&opd1,expSTK)==error) /*将运算量1出栈*/ synerror();
if(pop(&opd2,expSTK)==error) /*将运算量2出栈*/ synerror();
}
else synerror();/*出现非法字符*/ }/*while*/ if(pop(&opd1,expSTK)==error) synerror(); if(!(emptySTK(expSTK))) synerror(); printf(“=%-3d\\\\n”,opd1); }/*main_end*/ 【测试数据】 输入: 23+↙
输出: =5
(即求2+3的结果) 输入: 145*+3/3-↙
输出: 4 (即求(1+4*5)/3-3的结果) 【说明】
本算法中对后置法表示的表达式求值按如下规则进行：自左向右扫描，每遇到一个`n+1元组（opd1,opd2,…,opdn,opr）(其中opd为操作数，opr为n元运算符)，就计算一次opr（opd1,opd2,…,opdn）的值，其结果取代原来表达式中n+1元组的位置，再从表达式开头重复上述过程，直到表达式中不含运算符为止。
temp=eval(c,opd2,opd1);/*计算得到结果*/ push(&temp,expSTK);/*将运算结果进栈*/ 【实验题】
1.假设一个算术表达式中包含零对到多对圆括弧，括弧对之间允许嵌套但不允许交叉，编写一个算法并上机实现：判断输入的表达式是否正确配对。 Status correct(string expre)；
//括弧配对正确，返回ok，否则返回error 2.3. 用栈实现一般表达式（即中缀表达式）到后缀表达式的转换。
数制转换。
实验五 数据查找
一．实验目的：
理解各种查找的思想，实现对数据的查找。例如用：直接查找法和折半查找法。
二．实验内容：
任意输入10个整形数据，然后再输入一个数据进行查找。
该程序能对输入的数据进行查找，然后把数据所在的位置输出。
例如：输入10个数据：12 3 4 5 6 7 8 9 1 2
输入查找数据：5 输出为：the 5 is at 4 position 源程序：
#include #include void seqsearch(int*,int); void binsearch(int*,int); void bubblesort(int*,int);
void menu() { printf(" 1.seqsearch()\\\\n"); printf(" 2.binsearch()\\\\n"); printf(" 3.exit()\\\\n"); printf("please select the method:"); }
void main() {int i,j=1; int ch; int a[10];
/*声明插入查找函数*/ /*声明折半查找函数*/
/*声明起泡排序函数*/
/*引入头文件*/ clrscr(); printf("please input 10 data:"); for(i=0;i
scanf("%d",&(a[i]));
menu(); while(j)
/*接收输入*/
/*提示输入10个数据*/
/*显示菜单*/ /*循环一次*/ {scanf("%d",&ch);
switch(ch)
{case 1:seqsearch(a,10);break;
case 2:binsearch(a,10);break;
case 3:j=0;break;
default:break;
}
printf("\\\\n");
menu();
} }
void seqsearch(int*r,int n)
{int i=0,data; printf("please input find data:");
scanf("%d",&data);
while(r[i]!=data)
i++; if(i>n)
printf("the data is not found");
else printf("the %d position is %d",data,i+1); getch(); }
/*选择执行程序*/
/*直接查找函数*/
/*提示输入查找数据*/ /*接收数据*/
/*循环查找*/
/*输出数据没有找到*/
/*如果找到，输出位置*/
void binsearch(int *r,int n)
{int j,data,low=0,high=n,mid,find=0; bubblesort(r,n);
for(j=0;j
printf("%d ",r[j]);
printf("please input find data:");
scanf("%d",&data); while(low
{mid=(low+high)/2;
if(data
high=mid-1;
else if(data>r[mid])
low=mid+1; else find=1;
} if(!find)
printf("the data is not found!\\\\n");
else printf("the data position is %d",mid+1); getch(); }
void bubblesort(int *r,int n)
{int i,j,k,temp; k=n-1; for(j=0;j
{for(i=0;i
{if(r[i]>r[i+1])
{temp=r[i];
r[i]=r[i+1];
r[i+1]=temp;
/*折半查找函数*/
/*起泡法排序*/
/*排序后输出*/
/*提示输入查找数据*/
/*循环查找*/
/*置mid指针*/
/*判断数据大小，移动指针*/
/*显示数据没有找到*/
/*输出数据位置*/
/*起泡排序函数*/
/*比较大小*/
/*交换数据的位置*/
}
}
k=k-1;
} }
三．使用说明：
按提示输入10个任意的整形数据；
输入要查找的数据；
可以看到所要查找的数据的位置。
四．测试结果：
运行程序，屏幕提示
please input 10 data:12 3 4 5 6 seqsearch()
binsearch()
exit please select the method:1
please input find data:5
the 5 is at 4 position
please select the method:2 please input find data:5 the 5 is at 4 position
7 8 9
2 /*输入10个数据*/ /*顺序查找*/ /*折半查找*/
/*选择顺序查找*/
/*输入要查找的数据*/
/*输出正确结果，并返回提示*/
实验六 哈希表设计
一．实验目的：
熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。
二．实验内容：
程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的哈希表和完成查找过程及平均查找长度的计算。
【问题描述】
研究哈希（HAXI）表查找技术的两个重要问题是：构造HAXI函数和处理冲突。现在要求针对某个数据集合中的关键字设计一个哈希表（选择合适的哈希函数和处理冲突的方法），完成HAXI表的建立、查找，并计算HAXI表查找成功的平均查找长度。HAXI函数的构造方法有多种，其中除留余数法是一种最简单和最常用的方法。
考虑具体问题的关键字集合，如{19，14，23，1，68，20，84，27，55，11，10，79}这样一组数据和给定的哈希表长m 或哈希表的装填因子a，选用除留余数法和线性探测再散列技术解决冲突所形成的哈希表以及该哈希表在查找成功时的平均查找长度ASL。
【数据描述】
HAXI表是根据设定的HAXI函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上，并以关键字在地址区间的“象”作为记录在表中的存储位置。因此我们可以采用动态分配的顺序存储结构表示HAXI表。
typedef struct {
KeyType key ; }ElemType;
//元素类型的定义
ElemType *HAXI;//动态分配的哈希表的首地址
【算法描述】
1、选择合适的哈希函数H（ key）=key % p（P为小于或等于HAXI 表长的最大质数）；
2、计算各个关键字的直接哈希函数值；
3、根据处理冲突的方法建立哈希表，并输出；
4、在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。
三、源程序 #include #include #define NULL 0 typedef int KeyType; typedef struct {
KeyType key ; }ElemType; int haxi(KeyType key,int m){ /*根据哈希表长m, 构造除留余数法的哈希函数haxi*/
int i,p,flag;
for (p=m ; p>=2 ; p--)
/*p为不超过m的最大素数*/
{ for (i=2,flag=1;i
if (p %i==0) flag=0;
if (flag==1) break;
} return key%p;
/*哈希函数*/ }
void inputdata(ElemType **ST,int n ){ /*从键盘输入n个数据，存入数据表ST（采用动态分配的数组空间）*/
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\\\\nPlease input %d data:",n);
for (i=0;i
scanf("%d",&((*ST)[i].key)); }
void createhaxi(ElemType **HAXI,ElemType *ST,int n,int m){
/*根据数据表ST，构造哈希表HAXI*，n,m分别为数据集合ST和哈希表的长度*/ int i,j;
(*HAXI)=(ElemType*)malloc(m*sizeof(ElemType));
for (i=0;i
for (i=0;i
j=haxi(ST[i].key,m);
/*获得直接哈希地址*/
while ((*HAXI)[j].key!=NULL) j=(j+1)%m;/*用线性探测再散列技术确定存放位置*/
(*HAXI)[j].key=ST[i].key;
/*将元素存入哈希表的相应位置*/
} }
int search(ElemType *HAXI,KeyType key,int m,int *time){
/*在表长为m的哈希表中查找关键字等于key的元素，并用 time记录比较次数，
若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/ int i;
*time=1;
i=haxi(key,m);
while (HAXI[i].key!=0 && HAXI[i].key!=key) {i++; ++*time;}
if (HAXI[i].key==0) return -1;
else return i; } main(){
ElemType *ST,*HAXI;
KeyType key;
int i,n,m,stime,time;
char ch;
printf("\\\\nPlease input n && m(n
/*输入关键字集合元素个数和HAXI表长*/
scanf("%d%d",&n,&m);
inputdata(&ST,n);
/*调用函数，输入n个数据*/
createhaxi(&HAXI,ST,n,m);
/*建立哈希表*/ /*输出已建立的哈希表*/
printf("\\\\nThe haxi Table is\\\\n");
for (i=0;i
printf("\\\\n");
for (i=0;i
/*哈希表的查找，可进行多次查找*/ do {
printf("\\\\nInput the key you want to search:");
scanf("%d",&key);
i=search(HAXI,key,m,&time);
if (i!=-1) {printf("\\\\nSucce,the position is %d ",i);/*查找成功*/
printf("\\\\nThe time of compare is %d",time);
}
else{ printf("\\\\nUnsucce");
/*查找失败*/
printf("\\\\nThe time of compare is %d",time);
}
printf("\\\\nContinue(y/n):\\\\n");
/*是否继续查找yes or no*/
ch=getch();
} while (ch=="y" || ch=="Y") ;
/*计算表在等概率情况下的平均查找长度，并输出*/
for (stime=0,i=0;i
search(HAXI,ST[i].key,m,&time);
stime+=time;
};
printf("\\\\nThe Average Search Length is%5.2f",(float)stime/n);
ch=getch(); }
四、测试数据
按运行提示输入数据(关键字集合)ST，建立HAXI表，然后进行多次查找。
Please input n && m(n
0 1
7 14
68 27 55 19 20 84 Input the key you want to search:27 Succe,the position is 4 The time of compare is 4; Continue(y/n):y
Input the key you want to search:68 Succe,the position is 3 The time of compare is 1; Continue(y/n):n
The Average Search Length is 2.5
10 79 23
11 12
10 实验七 排序 一．实验目的：
理解各种排序的思想，实现对数据的排序。例如用：起泡排序和插入排序。
二．实验内容：
按提示输入10个整形数据。
每个数据中间一空格输出
程序达到的功能要求对输入的10个数据进行排序 例如：输入2 4 3 5 6 8 9 11 15 0
输出 0 2 3 4 5 6 8 9 11 15 源文件：
#include #include void bubblesort(int[],int); void insertsort(int[],int);
void menu() {printf("
1.bubblesort()\\\\n"); printf("
2.insertsort()\\\\n"); printf("please select the method:"); }
void main() {int i,j=1; int ch; int a[10]; clrscr(); printf("please input 10 data:"); for(i=0;i
scanf("%d",&a[i]);
/*显示提示输入10个数据*/ menu();
while(j--) {ch=getchar();
ch=getchar();
switch(ch)
{case"1":bubblesort(a,10);break;
case"2":insertsort(a,10);break;
} } for(i=0;i
printf("%d ",a[i]);
} void insertsort(int r[],int n)
{int i,j,temp1,temp2;
for(i=1;i
{temp1=r[i];j=i-1;
while(temp1=0)
{temp2=r[j+1];
r[j+1]=r[j];
r[j]=temp2;j--;
}
r[j+1]=temp1;
} }
void bubblesort(int r[],int n)
{int i,j,change,temp; for(i=n-1,change=1;i>=0&&change;--i)
{change=0;
for(j=0;j
/*显示菜单*/
/*选择排序方法*/
/*输出排序结果*/
/*插入排序函数定义*/ /*定义控制循环及中间变量*/
/*数据交换位置*/
/*起泡排序法函数定义*/
{if(r[j]>r[j+1])
/*数据交换位置*/
{temp=r[j+1]; r[j+1]=r[j]; r[j]=temp; change=1; }
}
} }
三．使用说明：
按提示输入10个整形数据 在菜单中选择排序的方法 查看排序结果
四．测试结果：
运行程序，屏幕提示
please input 10 data: 2 4 3 5 bubblesort() insertsort()
please select the method:1
0 2 3 4 5 6 8 9
please select the method:2
0 2 3 4 5 6 8 9
6 8 9 11 15 11 15 11 15 0
攀枝花学院课程设计论文 教学计划编制问题
摘 要
教学计划（课程计划）是课程设置的整体规划，它规定不同课程类型相互结构的方式，也规定了不同课程在管理学习方式的要求及其所占比例，同时，对学校的教学、生产劳动、课外活动等作出全面安排，具体规定了学校应设置的学科、课程开设的顺序及课时分配，并对学期、学年、假期进行划分。
根据一定的教育目的和培养目标制定的教学和教育工作的指导文件。它决定着教学内容总的方向和总的结构，并对有关学校的教学、教育活动，生产劳动和课外活动校外活动等各方面作出全面安排，具体规定一定学校的学科设置、各门学科的教学顺序、教学时数以及各种活动等。教学计划、教学大纲和教科书互相联系，共同反映教学内容。
近代以来，特别是在实行学科课程的条件下，教学计划主要是学科的计划，或只是学科表。随着社会经济和科学技术的新发展，教育结构不断发生变革，现代教育和教学理论主张对教学计划的结构实行改革。除了教学以外，生产劳动、科技活动、发展体力和增进健康的活动、艺术活动和社会活动等也应列入教学计划。下面就利用对此进行程序设计，已达到预期的目的。
关键字：数据结构，教学计划编制，抽象数据类型，程序设计
- 1攀枝花学院课程设计论文 教学计划编制问题
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()
- 4攀枝花学院课程设计论文 教学计划编制问题
数据关系: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本程序只有两个模块,调用关系简单
主程序模块→拓扑排序模块
攀枝花学院课程设计论文 教学计划编制问题
4.详细设计
4.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); 拓扑排序来编排课程
4.2栈的定义
#define STACk_INIT_SIZE 100 //存储空间的初时分配量 #define STACKINCREMENT 10 //存储空间的分配增量
- 789101112131415攀枝花学院课程设计论文 教学计划编制问题
6.调试分析
6.1实验过程中出现的问题及解决方法
我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。
6.2测试数据
学期总数：6；
学分上限：10；
该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。
6.3测试结果（包含正确和错误的）
正确测试结果：
攀枝花学院课程设计论文 教学计划编制问题
错误测试结果：
攀枝花学院课程设计论文 教学计划编制问题
6.4测试数据及程序运行情况
输入的内容如下: 课程编号 课程名称 学分 先决条件 01 程序设计基础 2 无 02 离散数学 3 01 03 数据结构 4 01，02 04 汇编语言 3 01 05 语言的设计和分析 2 03，04 06 计算机原理 3 11 07 编译原理 4 05，03 08 操作系统 4 03，06 09 高等数学 7 无 10 线性代数 5 09 11 普通物理 2 09 12 数值分析 3 09，10，01 两种编排方法都输出结果为: 第一学期学的课程有:高等数学 程序设计基础；
第二学期学的课程有:普通物理 线性代数 汇编语言；
第三学期学的课程有:数值分析 计算机原理 离散数学；
第四学期学的课程有:数据结构；
攀枝花学院课程设计论文 教学计划编制问题
第五学期学的课程有:操作系统 语言的设计和分析；
第六学期学的课程有:编译原理。
7.实验分工
8.总结
刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。
其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。同时也对教学编制问题有了进一步的认识。只要努力去学习，就会灵活的去应用它。
9.参考文献
［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003。
攀枝花学院课程设计论文 教学计划编制问题
［2］《数据结构题集》，严蔚敏，清华大学出版社，2005。
［3］《数据结构》（C语言版），刘大有，高等教育出版社，2004。
［4］《Data Structure with C++》，William Ford．William Topp，清华大学出版社，2003。
数据结构 课程设计报告
主题：教学计划编制问题 班级：计科四班 姓名：熊金莲 指导老师：郭艳
内容概要
（1） 题目要求
（2） 教学计划编制问题的要点
（3） 函数模块及各函数可实现的功能简介 （4） 具体的源代码 （5） 使用说明 （6） 实验心得 一：题目要求如下：
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
要求
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；
二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；
否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
二：教学计划编制问题的要点：
根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。
1） 采用第二种策略：使课程尽可能地集中在前几个学期中；
2） 根据教学计划中的课程及其关系和学分定义图的顶点和 边的结构体
3） 创建图CreateGraph：结合先修关系的AOV网，显示代号所对应课程及课程的先修课程
4）拓扑排序TopologicalOrder (G)：将课程排序后并决定出每学期所学课程，输出图G的信息Display(G)：将图的顶点和弧边输出 三：程序模块及可实现的功能简介：
1）、图的邻接表的存储表示，即结构体的定义
typedef struct ArcNode { int AdjOfV;
// 该弧所指向的顶点的位置 struct ArcNode *next;
//指向下一条弧的指针
}ArcNode; typedef char VertexType[MAXOfNAME]; typedef struct
//链接表 {
VertexType data;
//顶点信息 int grades;
//存储学分信息
ArcNode *first;
//指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VER];
// 头结点 typedef struct { AdjList ver;
//vertices 存储课程名
int vexnum, arcnum;
// 图的当前顶点数和弧数
}ALGraph; 2）、利用前插法，建立图的邻接链表
printf(\"请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\\n\");
for (h=0;h
// 构造表结点链表,利用前插法
{
printf(\"%s的先修课程:\",G.ver[h].data);
scanf(\"%s\",va);getchar();
while (va[0]!="0")
{
i = LocateVex(G, va);
//弧头
j = h;
//弧尾
p = (ArcNode*)malloc(sizeof(ArcNode));
p->AdjOfV = j;
p->next = G.ver[i].first; // 插在表头
G.ver[i].first = p;
scanf(\"%s\",va);
getchar();
}
}? 3）、输出图的顶点和边
printf(\"%d个顶点\", G.vexnum);
for (i = 0;i
printf(\" \\n%d条弧边:\\n\",G.arcnum);
for (i = 0;i
{
p = G.ver[i].first;
while (p)
{
printf(\"%s---->%s\\n\",G.ver[i].data,G.ver[p->AdjOfV].data);
p = p->next;
}
}? 4）、通过栈实现拓扑排序
??????int TopologicalOrder(ALGraph G,AdjList R,struct Name name) {
int i, k, j = 0, count, indegree[MAX_VER]; SqStack S; ArcNode *p; FindInDegree(G, indegree);
// 对各顶点求入度 InitStack(S);
// 初始化栈 for (i = 0;i
//建零入度顶点栈S
if (!indegree[i]) Push(S, i); // 入度为0者进栈 count = 0;
// 对输出顶点计数 while (!StackEmpty(S)) {
} if (count
} else printf( \"
为一个拓扑序列\"); printf(\"\\n\"); int q=1,Z=0; while (q
int C = R[Z].grades ; printf(\"\\n第%d个学期应学课程:\",q); while (C
// 输出i号顶点并计数
for (p =G.ver[i].first; p; p=p->next)// 对i号顶点的每个邻接点的入度减1 {
} k = p->AdjOfV; if (!(--indegree[k])) // 若入度减为0,则入栈
Push(S, k);
}
if (Z
{
CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/
} return 1;/**/ ++Z; } printf(\"\\n\"); if (q == TotalOfTerms)printf( \"\\nOK Over!\"); q++; } 依次将入度为0的顶点存入InDegree中，对每个顶点求入度，并存入数组InDegree[i]中（i=0…n），初始化栈Stack,Counter=0，对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter++)，推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter++），堆栈是否为空？，n个顶点全输出，依次将入度为0的顶点存入InDegree中
5)根据学分上限决定出每学期应学课程，其中R[ ]中存储的是经过拓扑排序后的课程先后顺序。????????
???
int q=1,Z=0; while (q
while (C
{
C = C + R[Z+1].grades; if (Z
++Z; }
} } printf(\"\\n\"); if (q == TotalOfTerms)printf( \"\\nOK Over!\"); q++; 四：具体的源代码
本程序分为三部分 A:::::::::SeqStack.h 1） 2） 3） 4） 5） 6） 7） 8） 9） 10） 11） 12） 13） 14） 15） 16） 17） 18） 19） 20） 21） 22） 23） 24） #define StackofNUM 20
//存储空间初始分配量 #define StackforMore 5
// 存储空间分配增量
typedef struct SqStack { int *a;
int *top;
int size;
//分配的存储空间 }SqStack;
int InitStack(SqStack &S)
/*栈的初始化*/ {
S.a= (int *)malloc(StackofNUM * sizeof(int)); if (!S.a)exit(-1); S.top =S.a; S.size =StackofNUM; return 1; }
int StackEmpty(SqStack S)
/*判断栈是否为空*/ {
if (S.top == S.a)return 1; else return 0; } 25） 26） 27） 28） 29） 30） 31） 32） 33） 34） 35） 36） 37） 38） 39） 40） 41） 42） 43） 44） 45） 46） 47） 48） 49） 50） 51） 52） 53） 54） 55） 56） 57） 58） 59） 60） 61） 62） 63） 64） 65） 66） 67） int Push(SqStack &S, int x)/*入栈*/
{ if (S.top - S.a >= S.size) {
S.a = (int *) realloc ( S.a, (S.size + StackforMore) * sizeof(int));
if ( !S.a ) exit(-1);
S.top =S.a +S.size;
S.size +=StackforMore; } *S.top++ = x; return 1; }
int Pop(SqStack &S, int &x)
/*出栈*/ {
if (S.top == S.a)return 0; x = *--S.top;
return 1; } #define MAXOfNAME 3
//最多字符个数 #define MAX_VER 100 //最大顶点数
typedef struct ArcNode { int AdjOfV;
// 该弧所指向的顶点的位置
struct ArcNode *next;
//指向下一条弧的指针 }ArcNode;
typedef char VertexType[MAXOfNAME];
typedef struct
//链接表
{ VertexType data;
//顶点信息
int grades;
//存储学分信息
ArcNode *first;
//指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VER];
// 头结点
typedef struct { AdjList ver;
//vertices 存储课程名
int vexnum, arcnum;
// 图的当前顶点数和弧数 }ALGraph;
int TotalOfTerms ;
//学期总数 B:::::::::ALGraph.h 68） 69） 70） 71） 72） 73） 74） 75） 76） 77） 78） 79） 80） 81） 82） 83） 84） 85） 86） 87） 88） 89） 90） 91） 92） 93） 94） 95） 96） 97） 98） 99） 100） 101） 102） 103） int MaxScores;
//学分上限
int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */
{
int i;
for (i = 0;i
if (strcmp(u,G.ver[i].data)==0)return i;
return -1; }
int CreateGraph(ALGraph &G)
/*采用邻接表存储结构*/ {
int i, j, h;
VertexType va;
ArcNode *p;
printf(\"请输入教学计划的课程数: \" );
scanf(\"%d\",&G.vexnum);
getchar();
printf( \"请输入各个课程的先修课程的总和(弧总数): \");
scanf(\"%d\",&G.arcnum);
getchar();
printf( \"请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):\", G.vexnum,MAXOfNAME);
for (i = 0;i
{
scanf(\"%s\",&G.ver[i].data);
getchar();
G.ver[i].first = NULL;
}
printf(\"请输入%d个课程的学分值:\",G.vexnum);
for (i = 0;i
{
scanf(\"%d\",&G.ver[i].grades);getchar();
}
printf(\"请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\\n\");
for (h=0;h
// 构造表结点链表,利用前插法
104）
{
105）
printf(\"%s的先修课程:\",G.ver[h].data); 106） 107） 108） 109）
scanf(\"%s\",va);getchar();
while (va[0]!="0")
{
i = LocateVex(G, va);
//弧头 110）
j = h;
//弧尾 111）
p = (ArcNode*)malloc(sizeof(ArcNode)); 112）
p->AdjOfV = j; 113）
p->next = G.ver[i].first; // 插在表头 114） 115） 116） 117） 118） 119） 120） 121） 122） 123） 124） 125） 126）
G.ver[i].first = p;
scanf(\"%s\",va); getchar();
}
}
return 1; }
void Display(ALGraph G)
/* 输出图G的信息*/ {
int i;
ArcNode *p;
printf(\"有向图\\n\");
printf(\"%d个顶点\", G.vexnum); 127）
for (i = 0;i
printf(\" \\n%d条弧边:\\n\",G.arcnum); 129） 130） 131） 132） 133） 134） 135） 136） 137） 138） 139） 140） 141） 142） 143） 144） 145） 146） 147） 148） 149） 150） 151） 152） 153）
for (i = 0;i
{
p = G.ver[i].first;
while (p)
{
printf(\"%s---->%s\\n\",G.ver[i].data,G.ver[p->AdjOfV].data);
p = p->next;
}
} }
void FindInDegree(ALGraph G, int indegree)
/*求顶点的入度*/ {
int i;
ArcNode *p;
for (i = 0;i
for (i = 0;i
{
p = G.ver[i].first;
while (p)
{
indegree[p->AdjOfV]++;
p = p->next;
}
} } struct Name 154） 155） 156） 157） 158） 159） 160） 161） 162） 163） 164） 165） 166） 167） 168） 169） 170） 171） 172） {
char c[20]; }name;
void CmpOfStr(VertexType str,struct Name name,int n)
/*让C1~C12分别与12门课程对应起来*/ {
if(strcmp(str,name[0].c)==0)printf(\" 程序设计基础\");
if(strcmp(str,name[1].c)==0)printf(\" 离散数学\");
if(strcmp(str,name[2].c)==0)printf(\" 数据结构\");
if(strcmp(str,name[3].c)==0)printf(\" 汇编语言 \");
if(strcmp(str,name[4].c)==0)printf(\" 语言的设计和分析 \");
if(strcmp(str,name[5].c)==0)printf(\" 计算机原理\");
if(strcmp(str,name[6].c)==0)printf(\" 编译原理\");
if(strcmp(str,name[7].c)==0)printf(\" 操作系统 \");
if(strcmp(str,name[8].c)==0)printf(\" 高等数学\");
if(strcmp(str,name[9].c)==0)printf(\" 线性代数\");
if(strcmp(str,name[10].c)==0)printf(\" 普通物理\");
if(strcmp(str,name[11].c)==0)printf(\" 数值分析\"); C::::::::::::::::::教学计划编制问题.Cpp
#include #include #include #include #include \"SeqStack.h\" #include \"ALGraph.h\" #define N 12 int TopologicalOrder(ALGraph G,AdjList R,struct Name name) { int i, k, j = 0, count, indegree[MAX_VER];
SqStack S; ArcNode *p; FindInDegree(G, indegree);
// 对各顶点求入度
InitStack(S);
// 初始化栈
for (i = 0;i
//建零入度顶点栈S
if (!indegree[i]) Push(S, i); // 入度为0者进栈
count = 0;
// 对输出顶点计数
while (!StackEmpty(S))
{
Pop(S, i);
printf(\"%s(%d学分),\",G.ver[i].data,G.ver[i].grades);
R[j++] = G.ver[i]; //将当前的拓扑序列保存起来
++count;
// 输出i号顶点并计数
for (p =G.ver[i].first; p; p=p->next)// 对i号顶点的每个邻接点的入度减1
{
k = p->AdjOfV;
if (!(--indegree[k])) // 若入度减为0,则入栈
Push(S, k);
}
}
if (count
{
printf(\"此有向图有回路无法完成拓扑排序\");
return 0;
}
else printf( \"
为一个拓扑序列\");
printf(\"\\n\");
int q=1,Z=0;
while (q
{
int C = R[Z].grades ;
printf(\"\\n第%d个学期应学课程:\",q);
while (C
{
C = C + R[Z+1].grades;
if (Z
{
CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/
++Z;
}
}
printf(\"\\n\");
if (q == TotalOfTerms)printf( \"\\nOK Over!\");
q++;
}
return 1;/**/ } void main() {
ALGraph G;
AdjList R;
struct Name name[N]={{\"C1\"},{\"C2\"},{\"C3\"},{\"C4\"},{\"C5\"},{\"C6\"},{\"C7\"},{\"C8\"},{\"C9\"},{\"C10\"},{\"C11\"},{\"C12\"}};
printf(\"
***************教学计划编制问题**************\\n\" );
printf( \"请以课件9-2上课程先序图为例输入学期总数:\");
scanf(\"%d\",&TotalOfTerms);
getchar();
printf(\"请输入学期的学分上限（8或9）:\");
scanf(\"%d\",&MaxScores);
getchar();
CreateGraph(G);
Display(G);
TopologicalOrder(G,R,name); } 五：说明：
本程序按照课件9-2所显示的那12门课程编排，示列6个学期，每学期不超过学分数示例输入9。程序示例运行如下：
六：实验心得：
经过此次课程设计，我深刻地认识到自己写程序的不足，认识到了仅仅只是从课本上学到算法原理是远远不够的，理论与实践结合才是最重要的。实验中，我总是不经意间出现各种错误，这就要求 今后的我要以脚踏实地的态度来思考处理问题。总之本次课程设计，让我进一步熟悉了C语言的语句用法，学到了很多有用的知识。
数据结构教学计划编制（共5篇）
实数教学设计（共6篇）
实验教学工作计划（共16篇）
数学教学计划（共6篇）
实用数学教学计划（共7篇）
相关热词搜索： 数据结构 教学计划 编制 实验