《程序设计课程设计》指导书2016

程序设计课程设计指导书软件学院计算机工程系2016年6月15日前言《程序设计课程设计》是计算机科学与技术专业的重要实践性课程。目的在于培养学生分析问题和解决问题的能力，为学生提供了一个既动手又动脑，独立实践的机会。将课本上的数据结构、离散数学和C语言的理论知识和实际应用问题进行有机结合，提高学生程序设计、程序调试及项目开发能力。为后续课程：操作系统、软件工程，编译原理等课程的学习奠定必要的实践基础。本课程设计是利用数据结构、离散数学、C语言理论和实验课中学到的编程知识和编程技巧，通过布置具有一定难度、一定编程量的课程设计题目，利用C语言作为开发工具，使学生通过课程设计掌握高级编程语言的知识和编程技术，掌握程序设计的思想和方法，初步具备利用计算机求解实际问题的能力。通过《程序设计课程设计》课程的学习，能够帮助学生加深理解数据结构、离散数学、C语言基本概念，达到培养学生良好程序设计的习惯和运用C语言编写程序解决实际问题的能力。使学生学会把书本知识用于解决实际问题，起到深化理解和灵活掌握教学内容的目的。同时使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。通过该课程设计，学生应该掌握C或C++语言程序设计的方法、数据结构和离散数学理论知识，熟悉C或C++程序的开发环境及C或C++程序的调试过程，巩固和加深对理论课中知识的理解，提高学生对所学知识的综合运用能力；学生应该具有如下基本技能：①培养学生查阅参考资料、手册的自学能力，通过独立思考深入钻研问题，学会自己分析、解决问题。②通过对所选题目方案分析比较，确立方案，编制程序与调试程序。③能熟练调试程序，在教师的指导下，完成课题任务。④根据个人的设计调试过程，按课程设计报告的要求撰写设计报告。选用教材及主要参考书：1教材呼克佑.C语言程序设计电子工业出版社,2013严蔚敏.数据结构(C语言版)清华大学出版社，2012目录前言.........................................................................................................................................1一．课程设计报告要求...........................................................................................................1二．课程设计报告示例——迷宫问题(参考)........................................................................2三．设计题目（6选4）.........................................................................................................81．消除类游戏.........................................................................................................................82．数字统计.............................................................................................................................93．画图...............................................................................................................................104．构造可以使n个城市连接的最小生成树.......................................................................125．送货...............................................................................................................................136．学生管理系统...................................................................................................................15-1-一．课程设计报告要求课程设计报告封面应给出专业、班级、姓名、学号、指导教师和完成日期，报告开头给出题目，内容包括以下几项：1．【问题描述】简要描述问题，然后说明程序设计的任务，程序要做什么。明确规定以下内容：（1）输入的形式和输入值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2．【问题分析】分析问题，简述解决的思想或方法，最好给出解决问题的流程主程序的流程；若涉及到多个函数模块，还要给出模块之间的调用关系。实现设计中定义的所有数据类型，对每个操作写出伪码算法，对主程序和其他函数模块也写出伪码算法（伪码算法的详细程度为按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）。3．【功能实现】（用C或C++描述）//说明：用C或C++写出所有程序代码。4．【实例测试及运行结果】列出测试结果，包括输入和输出。测试数据应该完整、严格。测试分析内容包括：（1）测试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析；（2）算法的时空分析和改进设想；（3）经验和体会。5．【心得体会】谈谈在设计和调试过程中的收获。-2-二．课程设计报告示例——迷宫问题(参考)专业：_________班级：_________姓名：_________学号：_________完成日期：_________【问题描述】编制一个求解迷宫通路的程序。以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标,d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）……【问题分析】（1）以二维数组MAZE[M+2][N+2]表示迷宫，其中：MAZE[0][J]和MAZE[M+1][J]（0≤J≤N+1）及MAZE[I][0]和MAZE[I][N+1]（0≤I≤M+1）为添加的一圈障碍。数组中以元素值为0表示通路，1表示障碍。限定迷宫的大小M，N≤10。（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数M和列数N；从第2行至第M+1行（每行N个数）为迷宫值，同一行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾经经过但不能到达出口的位置，其余用空格符表示。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。【功能实现】（用C或C++语言描述）设计如下：1．坐标位置类型typedefstruct{intr,c;//迷宫中行、列的范围}PosType;2．迷宫类型typedefstruct{intm,n;chararr[RANGE][RANGE];//各位置取值‘’,‘#’,‘@’或‘*’}MazeType;voidInitMaze(MazeType&maze,inta[][],introw,intcol);//按照用户输入的row行和col列的二维数组（元素值为0或1）//设置迷宫的初值，包括加上边缘一圈的值boolMazePath(MazeType&maze,PosTypestart,PosTypeend);//求解迷宫maze中，从入口start到出口end的一条路径-3-//若存在，则返回TRUE；否则返回FALSEvoidPrintMaze(MazeTypemaze);//将迷宫以字符型方阵的形式输出到标准输出文件上3．栈类型typedefstruct{intstep;//当前位置在路径上的“序号”PosTypeseat;//当前的坐标位置directiveTypedi;//往下一坐标位置的方向}ElemType;//栈的元素类型typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,*LinkType;//结点类型，指针类型typedefstruct{LinkTypetop;intsize;}Stack;//栈类型栈的基本操作设置如下：voidInitStack(Stack&S)//初始化，设S为空栈（S.top=NULL）voidDestroyStack(stack&S)//销毁栈S，并释放所占空间voidClearStack(Stack&S)//将S清为空栈intstackLength(StackS)//返回栈S的长度S.sizeStatusStackEmpty(StackS)//若S为空栈（S.top==NULL）,则返回TRUE;否则返回FALSEStatusGetTop(Stacks,ElemTypee)//若栈S不空,则以e带回栈顶元素并返回TRUE,否则返回FALSE;StatusPush(Stack&S,ElemTypee)//若分配空间成功,则在S的栈顶插入新的栈顶元素e,并返回TRUE,//否则栈不变,并返回FALSEStatusPop(Stack&S,ElemType&e)//若栈不空,则删除S的栈顶元素并以e带回其值，且返回TRUE//否则返回FALSEvoidStackTraverse(Stacks,Status(*visit)(ElemTypee))//从栈底到栈顶依次对S中的每个结点调用函数visit其中部分操作的算法：StatusPush(Stack&S,ElemTypee){//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；//否则栈不变，并返回FALSEif(MakeNode(p,e)){p-next=s.top;s.top=p;-4-s.size++;returnTRUE;}elsereturnFALSE;}StatusPop(Stack&S,ElemType&e){//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，//否则返回FALSE，且e无意义if(StackEmpty(S))returnFALSE;else{p=S.top;S.top=S.top-next;e=p-date;S.size--;returnTRUE;}}4.求迷宫路径的伪码算法：StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){//若迷宫中存在从入口start到出口end的通道,则求得一条存入在栈中//（从栈底到栈顶为从入口到出口的路径），并返回TRUE；否则返回FALSEInitStack(S);curpos=start;//设定“当前位置”为“入口位置”curstep=1;found=FALSE;//探索第