C语言程序设计课程设计指导书(晓庄)

-1-C语言程序设计课程设计任务书南京晓庄学院数学与信息技术学院2011-9-20-2-一、C语言程序设计课程设计的目的说明1）复习巩固C语言的基础知识，进一步加深对C语言编程的理解和掌握；2）利用所学知识，理论和实际结合，利用资源，采用模块化的结构，使用模仿修改自主设计相结合的方法，锻炼学生综合分析解决实际问题的编程能力；3）培养学生在项目开发中团队合作精神、创新意识及实战能力。二、课程设计要求要求实验室配备微型电子计算机80台，配置为奔腾PII以上，安装Windows2000以上操作系统，及vc6.0以上版本的开发环境。对同学们的要求包括：1.要充分认识C语言程序设计课程设计的重要性，认真做好各项准备工作，包括复习C语言基础的工作；2.要结合课题，独立思考，努力钻研，勤于实践，勇于创新，遇到困难时借助搜索引擎或者同学、老师查找解决问题的方法；3.收集资料，自学相关知识，拓宽知识面，根据课题的基本要求，自行完成设计任务。4.要按时、独立完成规定的工作任务，不弄虚作假，不抄袭他人；5.严格遵守学习和劳动纪律，不无故缺席，不迟到早退，不懈怠，不拖拉，要积极主动；6.严格要求自己，树立严肃、严密、严谨的科学态度，按时、按质、按量完成。三、课程设计的步骤C语言程序设计课程设计的步骤如下：1.选题与搜集资料：根据分组，选择课题，合理分工，进行需求分析与系统调查，搜集相关资料，了解涉及的理论基础知识。2.系统分析与预设计：根据课题要求及搜集的资料，进行系统功能划分，分析数据流程，进行模块设计。3.指导教师检查每位学生的预设计结果，确定是否可以进入下一步。4.程序设计：预设计通过的学生进入实验室，运用VC++6.0集成环境，编写程序，实现所设计的模块功能。5.调试与测试：自主调试程序，或同课题、同组成员交叉测试，并记录测试情况。6.成果验收：指导教师对每位同学设计的成果进行验收，打成果成果成绩。7.布置设计成果通过验收的同学撰写C语言程序设计课程设计报告。8.C语言程序设计课程设计答辩。9.结合每位学生的软件成果、工作态度、设计报告等，评定综合成绩。-3-四、设计课题设计课题包含两部分：第一部分为基础题目；第二部分为设计题目。每人在基础题目中选一个小题目，再在设计题目中选一个大题目完成课程设计内容：第一部分：基础题目：在以下三个基础题目中任选一个完成：题目1：实现顺序表各种基本运算的算法。这些算法包括：初始化顺序表；释放顺序表；判断顺序表是否为空表；返回顺序表的元素个数；输出顺序表；获取顺序表的第i个元素；在顺序表中查找某个给定的元素；在顺序表的第i个位置上插入元素；删除顺序表的第i个元素；题目2：实现单链表各种基本运算的算法。这些算法包括：初始化单链表；释放单链表；判断单链表是否为空表；返回单链表的元素个数；输出单链表；获取单链表的第i个元素；在单链表中查找某个给定的元素；在单链表的第i个位置上插入元素；删除单链表的第i个元素；题目3：实现双链表各种基本运算的算法。这些算法包括：初始化双链表；释放双链表；判断双链表是否为空表；返回双链表的元素个数；输出双链表；获取双链表的第i个元素；在双链表中查找某个给定的元素；在双链表的第i个位置上插入元素；删除双链表的第i个元素；以上每个题目均需要做到：1.完成代码编程，在VC6.0上编译，连接通过；2.编写一个main()主程序，测试你设计好的每个算法（每个算法对应一个调用函数，每题共9个算法）；3.如果你参考的某个范例，请务必理解这个例子；第二部分：设计题目：下面提供的设计课题，涉及面有大有小，难度有深有浅，考察的知识点、体现的设计目的也有所不同。同学可根据自身情况任选一个设计课题。每题限最多6人选。（一）成绩管理1．设计要求由于同学们已经学习了指针、链表、文件读写等基本知识，为了与后续课程，如数据结构、数据库系统等有一个知识体系上的衔接，特设置一个信息管理类的课题《成绩管理系统》，其它诸如人事管理、学籍管理、图书管理、通讯录管理等，结构类似，仅管理对象有所不同。管理内容包括：学号、姓名、班级、五门课成绩。主要功能有：添加、修改、删除、读出、写入、查找、排序、计算总分、平均分、分类汇总等。编写代码，运行程序后，显现下面的参考界面：-4-成绩管理============1．输入学生成绩2．修改学生成绩3．删除学生成绩4．计算每位学生的总分5．计算每位学生的平均分6．按学号或姓名查询学生成绩7．按班级查询学生成绩8．成绩排序9．按班级统计学科总分、平均分等请选择（1~9，0：退出）：选择一个菜单后，显示结果。（二）最短路径1．图概念图是一种复杂的非线性结构，在人工智能、工程、数学、物理、化学、生物和计算机科学等领域有着广泛的应用。图G由两个集合V和E组成，记为：G=(V，E)其中：V是顶点的有穷非空集合E是V中顶点偶对(称为边)的有穷集通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。（1）有向图和无向图有向图-5-若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧，边的始点称为弧尾，终点称为弧头。例如：vi，vj表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，vi，vj和vj，vi是两条不同的有向边。【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：V(G1)={v1，v2，v3}E(G1)={v1，v2，v2，v1，v2，v3}无向图若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。例如，(vi，vj)和(vj，vi)表示同一条边。【例】上面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：V(G2)={v1，v2，v3，v4}E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}V(G3)={v1，v2，v3，v4，v5，v6，v7}E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}注意：在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或vl，v2是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。图G的顶点数n和边数e的关系若G是无向图，则0≤e≤n(n-1)/2。恰有n(n-1)/2条边的无向图称无向完全图。若G是有向图，则0≤e≤n(n-1)。恰有n(n-1)条边的有向图称为有向完全图。注意：完全图具有最多的边数，任意一对顶点间均有边相连。例如上面(b)图的G2就是具有4个顶点的无向完全图。（2）图的边和顶点的关系无向边和顶点关系若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，或称vi和vj相邻接；并-6-称(vi,vj)依附或关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。例如：图G2中：①与顶点v1相邻接的顶点是v2，v3和v4②关联于顶点v2的边是(v1，v2)，(v2，v3)和(v2，v4)有向边和顶点关系若vi，vj是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边vi，vj关联于vi和vj或称vi，vj与顶点vi和vj相关联例如：图G1中，关联于顶点v2的弧是v1，v2，v2，v1和v2，v3。顶点的度①无向图中顶点v的度(Degree)无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。例：上图G2中顶点v1的度为3②有向图顶点v的入度(InDegree)有向图中，以顶点v为终点的边的数目称为v的入度(Indegree)，记为ID(v)。例：上图G1中顶点v2的人度为l③有向图顶点v的出度(Outdegree)有向图中，以顶点v为始点的边的数目，称为v的出度(Outdegree)，记为OD(v)例：上图G1中顶点v2的出度为2注意：①有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。例：上图G1中顶点v2的人度为l，出度为2，则度为3。②无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系：（3）子图设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图(Subgraph)。【例】：图7.2给出了有向图Gl的若干子图；图7.3给出了无向图G2的若干个子图。-7-注意：设V'={v1，v2，v3}，E'={(vl，v2)，(v2，v4)}，显然，V'属于V(G2)，E'属于E(G2)，但因为E'中序偶对(v2，v4)所关联的顶点v4不在V'中，所以(V'，E')不是图，也就不可能是G2的子图。（4）路径无向图的路径在无向图G中，若存在一个顶点序列vp,vi1，vi2,…，vim，vq，使得(vp，vi1)，(vi1，vi2)，…，(vim，vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path)。有向图的路径在有向图G中，路径也是有向的,它由E(G)中的有向边vp，vi1，vi1，vi2，…，vim，vq组成。路径长度路径长度定义为该路径上边的数目。简单路径若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。例如在图G2中顶点序列vl，v2，v3，v4是一条从顶点v1到顶点v4的长度为3的简单路径。在图G2中，顶点序列v1，v2，v4，v1，v3是一条从顶点v1到顶点v3的长度为4的路径，但不是简单路径。简单回路或简单环起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。例如图G2中，顶点序列v1，v2，v4，v1是一个长度为3的简单环例如有向图G1中，顶点序列v1，v2，v1是一长度为2的有向简单环。-8-有根图和图的根在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。（5）连通图和连通分量顶点间的连通性在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。连通图若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。图G2和G3是连通图。连通分量无向图G的极大连通子图称为G的连通分量。注意：①任何连通图的连通分量只有一个，即是其自身②非连通的无向图有多个连通分量。例如下图中的G4是非连通图，它有两个连通分量H1和H2。强连通图有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。强连通分量有向图的极大强连通子图称为G的强连通分量。注意：①强连通图只有一个强连通分量，即是其自身。②非强连通的有向图有多个强连分量。【例】下图中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。-9-（6）网络若将图的每条边都赋上一个权，则称这种带权图为网络。注意：权是表示两个顶点之间的距离、耗费等具有某种意义的数。下图就是一个网络的例子。2．图的表示方法图的存储表示方法很多，这里介绍最常用的邻接矩阵表示法。为了便于描述，假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v0，vi，…，Vn-1}。设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：【例】下图中无向图G5和有向图G6的邻接矩阵分别为Al和A2。-10-网络的邻接矩阵若G是网络，则邻接矩阵可定义为：其中：wij表示边上的权值；∞表示一个计算机允许的、大于所有边上权值的数。下面带权图的两种邻接矩阵分别为A3和A4。图的邻接矩阵存储结构#defineMaxV