教学计划编制问题数据结构课程设计

信息科学工程学院《高级语言程序设计

课程设计信息科学与工程学院数据结构课程设计课程设名

教学计编问题-1-信息科学工程学院《高级语言程序设计

课程设计前

言是一门综合程序设计理论和主,涉,所包程,还是对,,大家就更深入透彻地理解数据结构的,,力,提,为大C学通过将C语言应用到实际当中且可以更好的掌握算法与数和C使关字C语言-2-信息科学工程学院《高级语言程序设计

课程设计目

录前

言244466777810测调试过程15目-3-信息科学工程学院《高级语言程序设计一课内与求1.1课题内[问]

课程设计假设任何专业都有固定[基1号占3位的字母数字串)23）若根据给定的条件1.2设要1照需求分-4-信息科学工程学院《高级语言程序设计2

课程设计a、子程序b、3用C语（d、遇到问题应及时作出5）后续工作a、及时的总结设计中遇到的问题及解决的办法。写下-5-信息科学工程学院《高级语言程序设计

课程设计二需分据教学计划中的课程及其关系和学分定义图的（AOV单（序课程排序后并决定出每学期所图大的信息Display（将图三课实模设3.1程序模设LocateVex()：reateGraph()：isplay()：FindInDegree()：InitStack()：StackEmpty()：

图的邻接表存储的基本操作构造生成树输出图的邻接矩阵求顶点的入度构造一个空栈判断是否为空栈-6-信息科学工程学院《高级语言程序设计

课程设计Pop()：Push()：ClearStack()：Judge()：

出栈入栈清空栈判断课程号对应的课程序号TopologicalSort()：输出G顶点的拓扑排序结果Output()：

图形输出函数3.2函的用系Void（）OutputCreatGraph(DisplayTopologicalSort四模的能现4.1相关数类的义a语言定义相关的数据类型。其中包括定b存的数据为结构体类型数组：typedefstructstruct。-7-信息科学工程学院《高级语言程序设计4.2主函的程eginreateGraph()

课程设计Printf(请入教学计划的课程数”Scanf(”Printf(先关系的边数)Scanf(”,&(G).arcnum)Printf(输入%课.，（*G.vexnum,MAX_NAME）i++i<(*G).vexnum“%s”(*G).vertices[i].firstarc=nulli++-8-信息科学工程学院《高级语言程序设计

课程设计Printf(“入每条.”Scanf(%s%s,...)=LocateVex(*G,va)=LocateVex(*G,vb)P=(ArcNode*)malloc(size...)p-->adjvex=jP-->info=null0-9-信息科学工程学院《高级语言程序设计

课程设计五程调5.1测试数:：：10；：12从C01C12：，3，4，3，，，4，4，7，5，2，3

5

12310611

(中析)5.2调试过输入课程的课程-10信息科学工程学院《高级语言程序设计

课程设计-11信息科学工程学院《高级语言程序设计

课程设计-12信息科学工程学院《高级语言程序设计六程设总

课程设计的CC语言并将我们当初最关每门虽然学过却没通过在网上编写了一个拓扑排-13信息科学工程学院《高级语言程序设计

课程设计能重翻书本再次学习，而这浪费了编程肯定定会-14信息科学工程学院《高级语言程序设计

课程设计七附7.1致谢致谢首先感谢我们的指导老师周铁老师在我们的课程设计过程中提出了指导性的方案和架构指引我们阅读相关的资料和书籍使我们在不熟悉的领域中仍能迅速掌握新的技术在此感谢他为我们打下良好的基础是我们这次课程设计能够顺利完成的前提。另外，刘思在此次课程设计中认真完成的需求分析，朱敏负责的代码海燕在设计完成后对程序的测试是不可多得的，在此一并表示感谢。7.2参书《数据结构（C语言版）》《数据结构题集（C语言版）》3.《C语言程序设计（第三版）》7.3源序单

严蔚敏等編著严蔚敏等編著谭浩强编著/*输出有向图的一个拓扑序列及其应用问题的算法实现程序*/#include<string.h>#include<ctype.h>#include<malloc.h>#include<limits.h>#include<stdio.h>#include<stdlib.h>#include<io.h>#include<math.h>#include<process.h>#include<iostream.h>/*函数结果状态代码宏定义/#defineTRUE1-15信息科学工程学院《高级语言程序设计

课程设计#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;typedefintBoolean;#defineMAX_NAME10#defineMAXCLASS100/*顶点字符串的最大长度*/#defineMAX_VERTEX_NUM100intZ=0;intX=0;intxlz1,q=1,xlz2;/*xlz1学期总数xlz2为学分上限*/typedefintInfoType;typedefcharVertexType[MAX_NAME];/*字符串类型*/typedefenum{DG}GraphKind;/*{有向图,有向网无向图,无向网}*//*图的邻接表存储表示*/typedefstructArcNode{intadjvex;/*structArcNode*nextarc;/*InfoType*info;/*}ArcNode;/*typedefstruct{

该弧所指向的顶点的位置*/指向下一条弧的指针*/网的权值指针*/表结点*/VertexTypedata;/*顶点信息*/ArcNode*firstarc;/*第一个表结点的地址指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/typedefstruct{AdjListvertices,verticestwo;/*vertices存储课程名*/intvexnum,arcnum;/*图的当前顶点数和弧数*/intkind;/*图的种类标志*/}ALGraph;/*图的邻接表存储的基本操作*/intLocateVex(ALGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*/inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)-16信息科学工程学院《高级语言程序设计returni;return-1;

课程设计}/*采用邻接表存储结构,构造设有相关信息的图G*/StatusCreateGraph(ALGraph*G){inti,j,k;VertexTypeva,vb;ArcNode*p;printf("请输入教学计划的课程数");scanf("%d",&(*G).vexnum);printf("\n");printf("请输入拓扑排序所形成的课程先修关系的边数");scanf("%d",&(*G).arcnum);printf("\n");printf("请输入个课课程号(字母+数字且于%d个字符):\n",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)/*构造顶点向量*/{scanf("%s",(*G).vertices[i].data);(*G).vertices[i].firstarc=NULL;}printf("\n");printf("请输个课的分值字)空格隔开:\n",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)/*构造顶点向量*/{scanf("%s",(*G).verticestwo[i].data);}printf("\n");printf("请顺序输入每条弧边)的弧尾和弧头(以空格作为间隔:\n");for(k=0;k<(*G).arcnum;++k)/*构造表结点链表*/{scanf("%s%s",va,vb);=LocateVex(*G,va);/*弧尾*/=LocateVex(*G,vb);/*弧头*/p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=NULL;/*图*/p->nextarc=(*G).vertices[i].firstarc;/*插在表头*/(*G).vertices[i].firstarc=p;}printf("\n");returnOK;-17信息科学工程学院《高级语言程序设计

课程设计}/*输出图的邻接矩阵G*/voidDisplay(ALGraphG){inti;ArcNode*p;switch(G.kind){caseDG:printf("有向图\n");}printf("%d个顶点:\n",G.vexnum);for(i=0;i<G.vexnum;++i)printf("%s",G.vertices[i].data);printf("\n");printf("\n%d条弧(边):\n",G.arcnum);for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){printf("%s→%s",G.vertices[i].data,G.vertices[p->adjvex].data);p=p->nextarc;}printf("\n");}}/*求顶点的入度*/voidFindInDegree(ALGraphG,intindegree[]){inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}-18信息科学工程学院《高级语言程序设计

课程设计/*栈的顺序存储表示*/typedefintSElemType;/*栈类型*/#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间以元素为单位*/}SqStack;/*顺序栈*//*顺序栈的基本操作函数,构造一个空栈S*/StatusInitStack(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;returnOK;}/*判栈空：若栈S为空栈，则返回TRUE，否则返回FALSE*/StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}/*出栈操作：若栈不空，则删除S的栈顶元素，e返回其值，并返回OK；否则返回ERROR*/StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}/*入栈操作：插入元素e为新的栈顶元素*/StatusPush(SqStack*S,SElemTypee){-19信息科学工程学院《高级语言程序设计

课程设计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;returnOK;}/*清空栈的操作*/voidClearStack(SqStack*S){S->top=S->base;}/*判断课程编号对应型号数*/intJudge(charstr[]){if(strcmp("C1",str)==0||strcmp("c1",str)==0)return1;if(strcmp("C2",str)==0||strcmp("c2",str)==0)return2;if(strcmp("C3",str)==0||strcmp("c3",str)==0)return3;if(strcmp("C4",str)==0||strcmp("c4",str)==0)return4;if(strcmp("C5",str)==0||strcmp("c5",str)==0)return5;if(strcmp("C6",str)==0||strcmp("c6",str)==0)return6;if(strcmp("C7",str)==0||strcmp("c7",str)==0)return7;if(strcmp("C8",str)==0||strcmp("c8",str)==0)return8;if(strcmp("C9",str)==0||strcmp("c9",str)==0)return9;if(strcmp("C10",str)==0||strcmp("c10",str)==0)-20信息科学工程学院《高级语言程序设计return10;

课程设计if(strcmp("C11",str)==0||strcmp("c11",str)==0)return11;if(strcmp("C12",str)==0||strcmp("c12",str)==0)return12;return0;}typedefintpathone[MAXCLASS];typedefintpathtwo[MAXCLASS];/*有向图G采用邻接表存储结构G回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR*/StatusTopologicalSort(ALGraphG){inti,k,j=0,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);/*对各顶点求入度*/InitStack(&S);/*初始化栈*/for(i=0;i<G.vexnum;++i)/*建零入度顶点栈S,入读为零者入栈/if(!indegree[i]){Push(&S,i);}count=0;/*对输出顶点计数*/while(!StackEmpty(S)){Pop(&S,&i);[i]=*G.vertices[i].data;[i]=*G.verticestwo[i].data;switch(Judge(G.vertices[i].data)){case1:printf("课程:%s→","程序设计基础");break;case2:printf("课程:%s→","离散数学");break;case3:printf("课程:%s→","数据结构");break;case4:printf("课程:%s→","汇编语言");break;case5:printf("课程:%s→","语言的设计和分析");break;case6:printf("课程:%s→","计算机原理");break;case7:printf("课程:%s→","编译原理");break;case8:printf("课程:%s→","操作系统");break;case9:printf("课程:%s→","高等数学");break;case10:printf("课程:%s→","线性代数");break;-21信息科学工程学院《高级语言程序设计

课程设计case11:printf("课程:%s→","普通物理");break;case12:printf("课程:%s→","数值分析");break;}printf("学分%s\n",G.verticestwo[i].data);++count;/*输出i号顶点并计数*/for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k]))/*若入度减为0,则入栈*/{Push(&S,k);}}}if(count<G.vexnum){printf("此有向图有回路。\n\n\n");returnERROR;}else{printf("为一个拓扑序列。\n\n\n");has=true;}FindInDegree(G,indegree);/*对各顶点求入度*/ClearStack(&S);printf("****************程计划如下*****************\n\n");intqq=1;intxxf;while(qq<=xlz1){intresult[20];intrtop=0;intnn=0;xxf=0;for(i=0;i<G.vexnum;++i)/*建零入度顶点栈S*/{if(0==indegree[i]){Push(&S,i);}}while(!StackEmpty(S))-22信息科学工程学院《高级语言程序设计

课程设计{intbb;Pop(&S,&i);bb=atoi(G.verticestwo[i].data);xxf=xxf+bb;if(xxf>xlz2){break;}indegree[i]--;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;indegree[k]--;}result[rtop]=i;rtop++;}printf("第%d个学期的课程为:",qq);for(nn=0;nn<rtop;nn++){switch(Judge(G.vertices[result[nn]].data)){case1:printf("%s","程序设计基础");break;case2:printf("%s","离散数学");break;case3:printf("%s","数据结构");break;case4:printf("%s","汇编语言");break;case5:printf("%s","语言的设计和分析");break;case6:printf("%s","计算机原理");break;case7:printf("%s","编译原理");break;case8:printf("%s","操作系统");break;case9:printf("%s","高等数学");break;case10:printf("%s","线性代数");break;case11:printf("%s","普通物理");break;case12:printf("%s","数值分析");break;}}printf("\n");qq++;}printf("\n");printf("教学计划编制完成!!\n\n\n");returnOK;}-23信息科学工程学院《高级语言程序设计/*图形输出函数*/voidOutput(){

课程设计printf("**************据