教学编制问题 c语言 数据结构实现_数据结构c语言实现
教学编制问题 c语言 数据结构实现由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构c语言实现”。
数据结构 课程设计报告
主题：教学计划编制问题 学号：20091003768 班级：计科四班 姓名：熊金莲 指导老师：郭艳
内容概要
（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---->%sn”,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)){
} 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
} else printf(“
为一个拓扑序列”);printf(“n”);
int q=1,Z=0;while(q
int C = R[Z].grades;printf(“n第%d个学期应学课程:”,q);while(C
{
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
int C = R[Z].grades;printf(“n第%d个学期应学课程:”,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）25）26）27）28）29）30）31）32）33）34）35）36）37）38）#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;} 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)
/*出栈*/ 39）40）41）42）43）{
if(S.top == S.a)return 0;x = *--S.top;
return 1;}
B:::::::::ALGraph.h 44）45）46）47）48）49）50）51）52）53）54）55）56）57）58）59）60）61）62）63）64）65）66）67）68）69）70）71）72）73）74）75）76）77）78）79）80）#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;
//学期总数 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;81）82）83）84）85）86）87）88）89）90）91）92）93）94）95）96）97）98）99）100）101）102）103）
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）110）
scanf(“%s”,va);getchar();
while(va[0]!='0')
{
i = LocateVex(G, va);
//弧头
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）
G.ver[i].first = p;
scanf(“%s”,va);getchar();
}
}
return 1;}
void Display(ALGraph G)
/* 输出图G的信息*/ 122）{ 123）124）125）126）
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）154）155）156）157）158）159）160）161）162）163）164）165）
for(i = 0;i
{
p = G.ver[i].first;
while(p)
{
printf(“%s---->%sn”,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 {
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(“ 语言的设计和分析 ”);166）167）168）169）170）171）172）
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语言的语句用法，学到了很多有用的知识。
数据结构【第四次】实验报告学院：班级：学号：姓名：实验四（一）实验名称：C语言数据结构与指针（二）实验目的：巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构......
c数据结构实验报告数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____XX40703061_____;班级:_________软件二班________;姓名:________朱海霞__________;......
目 录1.需求分析.........................................错误！未定义书签。 2.概要设计.........................................错误！未定义书签。 3.详细设计...............
C语言与数据结构课程设计报告学 号 2014014083 姓 名 汪明 课程设计题目 通讯录的制作2016 年 1月目 录1 需求分析 1.1 功能与数据需求 1.1.1 题目要求的功能 1.1.2 扩展功......
用C语言实现按钮新技术（共5篇）由网友“或许@”投稿提供，以下是小编帮大家整理后的用C语言实现按钮新技术，欢迎大家分享。篇1：用C语言实现按钮新技术 用C语言实现按钮新技术一、按......
