DOC《课程设计报告》

课程设计报告 课程: 数据结构课程设计 学号:

1010431059 姓名: 胡维维 班级: 嵌入式一班 教师: 王群芳 时间: 2011年12月20日 计算机科学与技术系 设计名称: 教学计划编制问题 设计目的与要求: 目的:为大学专业制定教学计划 要求: (1)输入参数包括:学期总数,一学期的学分上限,每门课的课程号、学分和直接先修课的课程号.

(2)允许用户指定下列两种编排策略之一:一是使学生在各学期中的学习负担尽量均匀;

二是使课程尽可能地集中在前几个学期中. (3)若根据给定的条件问题无解,则报告适当的信息;

否则将教学计划输出到用户指定的文件中.计划的表格格式自行设计. 设计所用软件环境: 微型计算机一台 Mirosoft Visual C++6.0 问题的模型化描述及求解算法的简要描述: void FindInDegree(ALGraph G, int indegree[])//求图中各节点的入度(如下左图) void CreatGraph(ALGraph *G)//构件图(如下右图) void Display(ALGraph G) //输出图的邻接矩阵G void TopologicalSort_1(ALGraph G,int numterm)有向图G采用邻接表存储结构(如下左图) void TopologicalSort_2(ALGraph G, int numterm)有向图G采用邻接表存储结构(如下右图) 主函数:void main() 软件组成及使用说明: 软件组成:Mirosoft Visual C++6.0 使用说明:开始→程序→ 程序清单: #include #include #include #include #include // 函数结果状态代码 #define TRUE

1 #define FALSE

0 #define OK

1 #define ERROR

0 #define INFEASIBLE -1 typedef int Status;

#define MAX_NAME

10 // 顶点字符串的最大长度 #define MAXTERM

8 #define MAXCLASS

50 int Z=0;

int X=0;

int numterm,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;

char name[24];

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;

iMAXCLASS) {printf("提示:课程总数不能超过 %d !nn请重新输入:",MAXCLASS);

scanf("%d",&(*G).vexnum);

} printf("请输入拓扑排序所形成的课程先修关系的边数: ");

scanf("%d",&(*G).arcnum);

printf("请输入%d个课程的代表值和课程名(字符长度最大为%d):n",(*G).vexnum,MAX_NAME);

for(i=0;

ivertices[i].name);

(*G).vertices[i].firstarc=NULL;

} printf("请输入%d个课程的学分值(字符长度最大为%d):n",(*G).vexnum,MAX_NAME);

for(i=0;

iinfo=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;

inextarc;

} printf("n");

} } void FindInDegree(ALGraph G,int indegree[]) { // 求顶点的入度,算法调用 int i;

ArcNode *p;

for(i=0;

inextarc;

} } } typedef int SElemType;

// 栈类型 //栈的顺序存储表示 #define STACK_INIT_SIZE

10 #define STACKINCREMENT

2 typedef struct SqStack { SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

// 顺序栈的基本操作 Status InitStack(SqStack *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;

} void ClearStack(SqStack *S) //清空栈的操作 { S->top=S->base;

} 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_1(ALGraph G,int numterm) { // 有向图G采用邻接表存储结构.若G无回路,则输出G的顶点的一个拓扑序列并返回OK // 否则返回ERROR FILE *fp;

fp=fopen("bianpai.txt","w");

int i,k,j=0,count,indegree[MAX_VERTEX_NUM];

bool has=false;

SqStack S;

pathone a;

pathtwo b;

ArcNode *p;

FindInDegree(G,indegree);

InitStack(&S);

// 初始化栈 for(i=0;

inextarc) { // 对i号顶点的每个邻接点的入度减 k=p->adjvex;

if(!(--indegree[k])) {Push(&S,k);

//printf("%sn",*G.vertices[i].data);

} } } if(count