刘文龙410417080121教学计划编制问题

1、石家庄经济学院本科生课程设计报告书题 目 教学计划编制问题 姓名 刘文龙 学号 410417080121 学 院 石家庄经济学院华信学院 专业计算机科学与技术 指导教师 XXX 完成日期： 2012-XX-XX教学计划编制问题1 需求分析1.1【问题描述】假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。在这样的前提下设计一个教学计划编制程序1.2【基本要求】（1）输入参数包括：学期总数，一学期的学分上限，每

2、门课的课程号、学分和直接先修课的课程号。课程的先修关系输入每条弧的弧尾与弧头空格键为间隔（2）用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。 （3）若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。1.3【测试数据】学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C1到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。先修关系如下图：194212210113657881.4【实现提示】可设学期总数不超过12，课程总数不超过100。如果输入的先修课

3、程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程号与课程号之间的对应关系。 2 概要设计2.1【图的定义与图的基本操作】ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:           R=VR           VR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作p:CreateGraph(&G,V,VR

4、);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图GDestroyGraph(&G);初始条件：图G存在操作结果：销毁图GGetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值。PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值valueFirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”NextAdjVex(G,v,w);初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。操作结果：返

5、回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。LocateVex(ALGraph G,VertexType u)初始条件: 图G存在,u和G中顶点有相同特征。 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 。CreateGra ph(&G,V,VR) 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义创作图G。 TopologicalSort(ALGraph G) 操作结果：若G没有回路，则输出G的顶点的一个拓扑排序，并返回OK，否则ERROR。 ADT Graph2.2【栈的定义】ADT Stack数据对象:

6、D=ai|aiElemSet,i=1,2,n,n>=0    数据关系:R1=ai-1，ai|ai-1,aiD,i=2,n基本操作:InitStack(SqStack *S)操作结果：构造一个空栈S 。StackEmpty(SqStack S)初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE 。Pop(SqStack *S,SElemType *e)初始条件：栈S已经存在。操作结果：若栈不空，则删除S的栈顶元素，用e返回其值并返回OK；否则返回ERROR 。Push(SqStack *S,SElemType e)初

7、始条件：栈S已经存在。操作结果：插入元素e为新的栈顶元素。 ClearStack(SqStack &S);初始条件：栈S已经存在。操作结果：清空栈。DestroyStack(&S)初始条件：栈S已经存在。操作结果：栈S被销毁。 ADT Stack2.3【本程序有三个模块,调用关系】主函数模块      图单元模块栈的操作模块 2.3.1【图的模块组成】LocateVex(ALGraph G,VertexType u)若G中存在顶点u,则返回该顶点在图中位置;否则返回-1CreateGraph（&G,V,VR）：构造生成树Displ

8、ay（ALGraph G）：输出图的邻接矩阵GFindInDegree（ALGraph G, int indegree）：求顶点的入度indegreePop（SqStack &S, int &x）：X出栈Push（SqStack &S, int x）：X入栈TopologicalSort（ALGraph G）：输出G顶点的拓扑排序结果2.3.2【栈的模块组成】InitStack（SqStack S）：构造一个空栈SClearStack（SqStack S）：清空栈SStackEmpty（SqStack S）：判断S是否为空栈Pop（SqStack &S, int

9、 &x）：X出栈Push（SqStack &S, int x）：X入栈 3 详细设计提示：根据概要设计，给出数据的存储表示（存储结构），完成相关算法的设计。3.1数据的存储表示图的邻接表的存储表示typedef struct ArcNode /定义弧结点int AdjOfV; / 该弧所指向的顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode;typedef char VertexTypeMAXOfNAME; /自定义课程名称最多三个字符的字符串typedef struct VertexType data; /顶点信息int grades;

10、 /存储学分信息ArcNode *first; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VER; / 头结点typedef struct /AdjList ver; /vertices 存储课程名(在邻接表里面)int vexnum, arcnum; / 图的当前顶点数和弧数ALGraph;3.2相关算法的设计1）建立图的邻接链表int CreateGraph(ALGraph &G)Printf请输入下列课程的先修课程 for (h=0；i<所有课程数；i+) / 构造表结点链表 while (有先修课程的时候) 定义LocateVex(G, va)叫

11、做弧头并且定义弧尾 创建邻接表里面的表头与表尾，并分别让表头指向表尾 保存 2）输出图的顶点和边void Display(ALGraph G) / 输出图G的信息 for (i=0；i<课程总数；i+) 分别输出最多3个字符的字符串的“课程名” for (i=0；i<课程总数；i+) 令p 为指向该顶点的第一条弧(该表结点有邻接点或弧) while (p存在) printf(“表头->表尾”) 创建邻接表的流程图：开始 假 假 真 真 h<课程总数 h=0输入1门先修课程是否有效课程信息表头->表尾h+结束3）通过栈实现拓扑排序   

12、   int TopologicalOrder(ALGraph G,AdjList R,struct Name name) 定义栈 S; 定义弧结点 *p;对各顶点求入度 初始化栈 For(i = 0;i < 课程总数;+i) 入度为0者进栈，就是说没有先修课程的元素入栈 while(栈不空) 对i号顶点的每个邻接点的入度减1if (入度减为0) 则入栈 if(入栈的元素< 课程总数) printf("此有向图有回路无法完成拓扑排序"); return 0; Else printf( "为一个拓扑序列");whi

13、le (学期分数<=总的学分 )while (某个学期的学分 <= 学分上线) 这个学期的学分+ 另一门课程的学分 return 1;/*/通过栈实现拓扑排序的流程图 假 真 假 真 假 真开始 栈定义变量i初始化栈若变量i<总的课程数 真真 真入度为0者进栈i+若栈不空 对i号顶点的每个邻接点的入度减1, 若入度减为0,则入栈总的学分 <= 学分上线总的学分+ 另一门课程的学分结束 4)拓扑排序要点：依次将入度为0的顶点存入InDegree中，对每个顶点求入度，并存入数组InDegreei中（i=0n），初始化栈Stack,Counter=0，对以i号顶点为尾弧的每个

14、邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter+)，推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter+），堆栈是否为空？，n个顶点全输出，依次将入度为0的顶点存入InDegree中4 编码调试提示：根据详细设计完成系统的编码、测试程序，要有给定的正确数据、错误数据和边界数据，要有不同的结果并进行结果分析，对于出现的错误，要进行错误分析，并进行改正。【4.1】测试数据：数据如下：学期总数：6；学分上限：9；该专业共开设课数：12课程号：从C1到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。先修顺序：194

15、21221011365788【4.2】出现的错误以及改正1. h:数据结构课程设计wenlongjiaoxuejihua.cpp(18) : error C2146: syntax error : missing '' before identifier 'count'改正：在Push(S, i)后面加上“；”号2. h:数据结构课程设计wenlongalgraph.h(10) : error C2144: syntax error : missing '' before type 'char'改正：typedef struct

16、ArcNode/定义邻接表弧 int AdjOfV;/ 该弧所指向的顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode在ArcNode后面加上“；”3. h:数据结构课程设计wenlongalgraph.h(54) : error C2065: 'Gvexnum' : undeclared identifier改正：把printf("请输入%d个课程的学分值:",Gvexnum);改为printf("请输入%d个课程的学分值:",G.vexnum);4. h:数据结构课程设计wenlongalgrap

17、h.h(57) : error C2059: syntax error : ''改正：把scanf("%d",&G.ver.grades);getchar();改为scanf("%d",&G.veri.grades);getchar();i指的是变量，G.veri.grades指的是第几个课程的学分，当把i省略的时候，不知道输入第几个课程的学分，因此会出现错误。5. h:数据结构课程设计wenlongalgraph.h(64) : error C2059: syntax error : ''改正：while

18、 (va!='0')改为while (va0!='0'),因为如果优先修课程的时候，所以是va0!='06. h:数据结构课程设计wenlongalgraph.h(65) : error C2143: syntax error : missing '' before ''改正：printf(" n%d条弧边:n",G.arcnum);改为printf(" n%d条弧边:n",&G.arcnum)，因为%d是整数，所以加上&7. h:数据结构课程设计wenlongalg

19、raph.h(119) : error C2106: '=' : left operand must be l-value改正：把if(strcmp(str,name0.c)=0)改为if(strcmp(str,name0.c)=0)，因为是对串比较的判断而不是赋值，所以是“=”，而不是“=”。8. h:数据结构课程设计wenlongseqstack.h(41) : error C2440: '=' : cannot convert from 'int *' to 'int'改正：把x = -S.top改为x = *-S.top;

20、因为出栈元素是指针类型。【4.2】正确代码的调试，以及调试分析1需要输入输入的是学期总数6学分上限9教学计划课程数12弧的总数，也就是先修课程的总数1612门课程的名称C1-C1212门课程的学分2,3,4,3,2,3,4,4,7,5,2,3分别输入12门课程的先修课程C1的先修课程 0C2的先修课程 C1 0C3的先修课程 C1 C2 0C4的先修课程 C1 0C5的先修课程 C3 C4 0C6的先修课程 C11 0C7的先修课程 C5 C3 0C8的先修课程 C3 C6 0C9的先修课程 0C10的先修课程 C9 0C11的先修课程 C9 0C12的先修课程 C1 C9 C10 0 2输出

21、的是输出提示“创建的该图是有向图，有12个顶点C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12,”(1)16条弧分别是C1->C2C1->C4C1->C3C1->C12C2->C3C3->C5C3->C7C3->C8C4->C5C5->C7C6->C8C9->C12C9->C10C9->C12C10->C12C11->C16这16条弧的输出用到的是“Display(ALGraph G) 输出图G的信息.(2)输出每一门课程的学分用到的是拓扑排序的操作。当用到栈的基本操作时

22、时，显示每一个出栈元素的的名字，并且显示他的学分，具体的算法是printf("%s(%d学分),",G.veri.data,G.veri.grades)，操作结果如下： C9<7学分>,C10<5学分>,C11<2学分>,C6<3学分>,C1<2学分>,C2<3学分>,C3<4学分>,C8<4学分>, C4<3学分>, C5<2学分>, C7<4学分>,C12<3学分>(3)显示的C9,C10,C11,C6,C1,C2,C3, C8

23、, C4, C5, C7,C12; 是一个拓扑排序。AOV-网是固定的，但是对这个AOV-网进行拓扑排序，有很多的排序序列，下面我就介绍其中的几个排序序列。C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8C9,C10,C1C,C6,C1,C12,C4,C2,C3,C5,C7,C8C1,C9,C11,C6,C10,C2,C4,C3,C5,C12,C7,C8这些拓扑排序序列，就是通过拓扑排序的定义排序出来的，首先是没有先修课程的元素出栈，再把该元素所指向的弧都删掉，在查找没有先修课程的元素，再把该课程所指向的弧都删掉，直到所有的课程都逐一排序出来，这时候的排序就是一个拓

24、扑排序序列。(4)并将这些输出地排序序列，逐一的与课程名称对应起来，在通过与每一个学期的上限比较，例如说：通过排序序列，第一个元素是C9，该课程名字是“高等数学”学分是7；第2个是C10，该课程的学分是5，5+7>9学分上线，所以第一学期的课程只有“高等数学”；第三个为C11，学分是2，5+2=7<9，第四个元素是C6，学分为3，5+2+3>9，所以第2学期的可课程为“线性代数，普通物理”。这样逐一的输出排序后的课程，直到所有的课程都输出完毕。5 设计体会提示：这是整篇报告中最令人感兴趣的部分，主要内容包括：5.1. 本次课程设计各阶段（需求分析、概要设计、详细设计、编码调试

25、等）所遇到的问题，问题的现象描述，产生的原因，解决方案（措施），解决的结果等；实习的第一天，本来想找一个难一点的课程设计，于是我首先选择的是“伙伴管理系统”，但是我搜索了很多的资料，也啃了很多的资料，但是到最后，我还是没有一点点的思路，于是我去找老师去了，老师看了一会说：“这是第八章的内容我们没有讲”，于是又重新选择了一个，做的是“教学计划编制问题”。在需求分析中，我只出现了一点点的错误，例如，排版不够公整，有个别的错别字，但是我很快就改好了，就顺利通过了。当我完成概要设计的时候，我又仔细的看了一遍，老师验收的时候，老师是相当的仔细，她一点点的给我看，一眼就看出了一个错误，那就是我的数据类型缺

26、少数据关系与数据对象，回去之后我又认真的改了改，这一次我顺利的通过了验收。老师的态度证明天底下在伟大的事业就是老师。详细设计是我最头疼的，我验收了很多很多次，才可以通过，概要设计我周三的时候就通过了，周四，周五我准备的是详细设计，周五验收的时候，老实说我的问题不大，就让我画图，当我画好的时候，就放学了。于是我只能等到周一了，一个老师一个思想，对待同一个问题，每个人都有自己不一样的思想与看法，周一的时候，我验了三次，概要设计，我已经签字了，但是这个老师说不好，要我改，到最后只剩下流程图的不对了，到最后详细设计算过了，让明天的老师再给我看看流程图，当我验收流程图的时候，又出现了新的问题了但是到了最

27、后我还是通过了，谢天谢地，详细设计真的很难，但是收获是最大的。编码的调试大概有如下几种错误：语法上的错误，丢了“；”号或者是分号不符合C语言的要求。结构体的语法错误，也是很简单的错误； G.veri.grades指的是第几个课程的学分，当把i省略的时候，不知道输入第几个课程的学分，因此会出现错误。；当存储一个整数的时候，应该加上&，而不是省略掉因为是对串比较的判断而不是赋值，所以是“=”，而不是“=”，因为“=”指的是赋值。出栈元素是指针类型，而不是整形5.2. 测试结果分析，给出所采用的测试数据并对所得到的结果进行分析，分析算法的性能（时间与空间复杂度）。LocateVex(ALGr

28、aph G, VertexType u) 查找图中某个顶点位置，时间复杂度为f(n)=n,T(n)=O(n),空间复杂度为S(n)=O(n) CreateGraph(ALGraph &G) 时间复杂度:f(n)=<n+n+n*(n-1),T(n)=O(n2);空间复杂度:f(n)=n,S(n)=O(n)Display(ALGraph G) /输出图G的信息, 时间复杂度:f(n)<=n+n*(n-1)= n2,T(n)=O(n2)空间复杂度:f(n)=n,S(n)=O(n)FindInDegree(ALGraph G, int indegree)求顶点的入度f(n)=<

29、;n+n*(n-1)=n2,T(n)=O(n2);空间复杂度:f(n)=n,S(n)=O(n)Push(SqStack &S, int x)/*入栈*/时间复杂度:f(n)=1,T(n)=O(1);空间复杂度:S(n)=O(1)Pop(SqStack &S, int &x) 时间复杂度:f(n)=1,T(n)=O(1);空间复杂度:S(n)=O(1)TopologicalOrder(ALGraph G,AdjList R,struct Name name) /拓扑排序计算每个顶点的入度需要进行n次，入栈元素的数量计算进行n次，保存入栈元素需n次，n门课程名称与对应的字符

30、对应起来最多进行n*n次，所以f(n)=n+n+n+n*n，T(n)=O(n2); f(n)=n,因为保存栈，只用了n次。空间复杂度:S(n)=O(n)。5.3. 探讨更多解决问题的途径，给出改进算法的建议。 我认为该课程设计教学计划编制的算法，写的很麻烦，用到了很多的操作，我认为，我们可以适当的改进一些不必要的算法，我认为要对12门课程随机的分配，我们可以用到约瑟夫环对出栈元素分别分配的到每个学期中，这样的话，就不需要用创建图，输出图，通过栈实现拓扑排序的算法了，这样的话，我认为会简单的很多。5.4. 本次课程设计收获：存在的问题（不足之处）、感想、今后努力的方向等。 这些天的课程设计，让我

31、学到了很多受益匪浅的知识，因为通过这次的课程设计，我不仅对我的专业知识进行了加强，还锻炼了我的想象力，思维能力，还有鱼同学相互合作的精神，这次的课程设计是我与实际的相结合。 在这次的课程设计中，我遇到了很多的问题，我很笨，但是我不懒，每天晚上都在弄自己的实验报告与程序，在验收的过程中，我们老师我们精益求精，对我们相当的严格，只有这样，我们才能学到真正的本事。我深刻的意识到自己的不足，认识到我仅仅从课本上学到的知识是那么的远远不够，理论与实践的相结合才是最重要的。 实验中，我总是不经意间出现很多的错误，如调试的错误，验收的时候出现的很多的错误，本设计能够顺利的完成，也归功于各位任课老师的认真负责

32、，使我能够很好的掌握和运用专业知识，并在设计中得以体现。这就要求我在今后的生活中要脚踏实地，对待事情要认真仔细，要以严谨的态度对待问题。但是最终程序的云系个成功是我的内心得到了莫大的满足。从课题选择、方案论证到具体设计和调试，无不凝聚着老师的心血和汗水，在这两年的本科学习和生活期间，也始终感受着导师的精心指导和无私的关怀，我受益匪浅。在此向所有的老师表示深深的感谢和崇高的敬意。 6 致谢提示：培养感恩之心，对在本次设计中所有对你有帮助的人（老师、同学、同组成员）表达真诚的谢意。每一天的进步，我都离不开我的导师，首先我要先感谢在这次的课程实践中，所有的老师对我的谆谆教诲，他们不但教会了我知识，还

33、教会了我本事将来在这个社会上生存的技能，谢谢所有的老师们。在这一次的课程设计中，我遇到了很多的问题，但是老师不怕麻烦，一点点的给我讲解，一点点的给我说明。我的程序调试的时候出现了很多的问题，我没有放弃，通过自己上网搜，我一点点的找答案，虽然最后我还是没有成功但是通过问老师和学生我逐一弄明白了。将来的路还很坎坷，我不知道会发生什么，不知道会遇到什么样的风风雨雨，但是我记住了老师的教导，我带着了老师们的祝福与我所学到的技能还有大学里我所得到的友谊，带着你们的祝福，我会走好我的路的，谢谢你们，我亲爱的老师们，谢谢你们我亲爱的同学们，谢谢那些给我挑战的机遇，我会变得更加坚强，不光是肉体上，还有我的心灵

34、上。谢谢亲爱的老师们！谢谢我的同学们！7 参考文献提示：至少列出3篇（本）。1. 严蔚敏数据结构（语言版）M清华大学出版社 2008年11月2. 严蔚敏数据结构题集（语言版）M清华大学出版社 2008年11月3. 何钦铭数据结构课程设计M浙江大学出版社 2007年8月14. 孙巧萍数据结构实训教程M科学出版社 2003年8月18 附录（源程序清单） ALGraph.h#define MAXOfNAME 3 /课程名称的最多字符个数#define MAX_VER 100 /AOV-网中的最大顶点数 typedef struct ArcNode/定义邻接表弧 int AdjOfV;/ 该弧所指向的

35、顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode;/ArcNode是struct ArcNode的缩写typedef char VertexTypeMAXOfNAME; /顶点的信息typedef structVertexType data; /顶点信息int grades;/学分信息ArcNode *first; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VER; / 邻接表的最大顶点数typedef structAdjList ver; /vertices 存储课程名 AdjList只得束邻接表int vexnum, arc

36、num; / 图的当前顶点数和弧数ALGraph;int TotalOfTerms ; /学期总数int MaxScores; /学分上限 int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */ int i;/顶点的信息 for (i = 0;i < G.vexnum;+i)/小于有向网的顶点数 if (strcmp(u,G.veri.data)=0)return i;/串比较，判断输入的课程的信息与网中的节点是否相等 return -1;/时间复杂度为f(n)=12,T(n)=O(1),空间复杂度为S(n)=O(1)int Crea

37、teGraph(ALGraph &G) /采用邻接表存储结构,创建AOV网 int i, j, h;/i指的是网中的节点数，h先修课程的总数 VertexType va; /定点的名字为va（课程名称） ArcNode *p; /边节点（弧节点） printf("请输入教学计划的课程数: " );/也就是节点数 scanf("%d",&G.vexnum); getchar();/接收回车键 printf( "请输入各个课程的先修课程的总和(弧的总数): "); scanf("%d",&G.a

38、rcnum); getchar();/接收回车键 printf( "请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):", G.vexnum,MAXOfNAME); for (i = 0;i < G.vexnum;+i) /12门课程 scanf("%s",&G.veri.data);/分别把12门课程存储到data里 getchar();/每存储一个就接收一个回车键 G.veri.first = NULL;/这时所有的课程还没有弧 printf("请输入%d个课程的学分值:",G.vexnum); for

39、 (i = 0;i < G.vexnum;+i) /一共有12门课程 scanf("%d",&G.veri.grades);getchar();/分别存储到grades中，并接收字符回车键 printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n"); for (h=0;h<G.vexnum;+h)/C2 ->C1->C3,指的是C2的先修课程为后面的两个 printf("%s的先修课程:",G.verh.data);/共有12门课程 scanf("%s",va

40、);getchar(); while (va0!='0')/指的是它有先修课程的时候 i = LocateVex(G, va); /该节点叫做弧头 j = h; /先修课程叫做弧尾 p = (ArcNode*)malloc(sizeof(ArcNode);/p（弧）定义成指针 p->AdjOfV = j;/该弧所指向点的位置 p->next = G.veri.first; / 插在表头例C1->C2;则C1插在表头 G.veri.first = p; scanf("%s",va); getchar(); /时间复杂度:f(n)=<12

41、+12+12*11=156,T(n)=O(1);空间复杂度:f(n)=12,S(n)=O(1) return 1;void Display(ALGraph G) / 输出图G的信息 int i; ArcNode *p;/弧结点 printf("教学计划编制问题的有向图:n"); printf("%d个顶点（课程数）", G.vexnum);/输出总的课程数 for (i = 0;i < G.vexnum;+i)/分别输出和课程的课程名称 printf("%3s", G.veri.data);/最多3个字符的字符串 printf(

42、" n%d条弧边:n",G.arcnum);/输出一共有12条弧 for (i = 0;i < G.vexnum;i+)/分别输出每一课程的邻接点 p = G.veri.first; while (p)/当有邻接点的时候 printf("%s->%sn",G.veri.data,G.verp->AdjOfV.data);/弧头->弧尾 p = p->next;/下一个 /时间复杂度:f(n)<=12+12*11<=144,T(n)=O(1);空间复杂度:f(n)=12,S(n)=O(1) void FindInD

43、egree(ALGraph G, int indegree)/*求顶点的入度*/ int i; ArcNode *p;/定义弧的指针 for (i = 0;i < G.vexnum;i+) indegreei = 0; /先定义每一个顶点的入度为0 for (i = 0;i < G.vexnum;i+)/分别求每一个定点的入度 p = G.veri.first; while (p) indegreep->AdjOfV+; p = p->next; /时间复杂度:f(n)=<12+12*11<=144,T(n)=O(1);空间复杂度:f(n)=12,S(n)=

44、O(1)struct Name char c20;name; void CmpOfStr(VertexType str,struct Name name,int n) /*让C1C12分别与12门课程对应起来*/ if(strcmp(str,name0.c)=0)printf(" 程序设计基础"); if(strcmp(str,name1.c)=0)printf(" 离散数学"); if(strcmp(str,name2.c)=0)printf(" 数据结构"); if(strcmp(str,name3.c)=0)printf(&qu

45、ot; 汇编语言 "); if(strcmp(str,name4.c)=0)printf(" 语言的设计和分析 "); if(strcmp(str,name5.c)=0)printf(" 计算机原理"); if(strcmp(str,name6.c)=0)printf(" 编译原理"); if(strcmp(str,name7.c)=0)printf(" 操作系统 "); if(strcmp(str,name8.c)=0)printf(" 高等数学"); if(strcmp(str,n

46、ame9.c)=0)printf(" 线性代数"); if(strcmp(str,name10.c)=0)printf(" 普通物理"); if(strcmp(str,name11.c)=0)printf(" 数值分析");SeqStack.h#define StackofNUM 20 /存储空间初始分配量#define StackforMore 5 / 存储空间分配增量typedef struct SqStackint *a; /栈底 int *top; /栈顶 int size; /存储空间SqStack;/SqStack是str

47、uct SqStack的缩写，里面有变量*a,*top,size;int InitStack(SqStack &S) /*栈的初始化*/ S.a= (int *)malloc(StackofNUM * sizeof(int);/malloc函数动态分配一个整型的内存空间,用（int*）强制类型转换为整型指针，再把它赋给S.a即让指针变量S.a指向刚申请的内存空间。if (!S.a)exit(-1);/判断是否把栈里面的a强制转换为整形指针 S.top =S.a;/栈顶元素=栈底元素S.size =StackofNUM;/给栈添加存储空间初始分配量为20return 1;int Stac

48、kEmpty(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;/时间复杂度:f(n)=1,T(n)=O(1);空间复杂度:S(n)=O(1)int Pop(SqStack &S, int &x) /*出栈*/ if (S.top = S.a)return 0;x = *-S.top;/先令top指针减1，在将top所指单元值赋给x return 1;/时间复杂度:f(n)=1,T(n)=O(1);空间复杂度:S(n)=O(1) 主函数#i