数据结构课设任务书.doc

_课 程 设 计 报 告课程名称 数据结构 课题名称1.通讯录管理 2.迷宫求解 专 业 计算机科学与技术 班 级 1381 学 号 201313030120 姓 名 杨承志 指导教师 刘铁武 刘杰君 2015年 7月 5日湖南工程学院课 程 设 计 任 务 书一设计目标强化学生编码、调试错误的能力；了解和掌握数据结构相关技术、并合理利用其解决实际应用问题；了解软件开发的流程和项目管理控制；掌握企业级IDE的使用 ；了解当前IT行业及职业人应具备的素质；完全模拟真实软件开发流程和管理；增强团队意识和团队合作精神。二设计内容：问题1：拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需设定课时，而各学期的总课时不能超过上限。测试数据：学期课时上限数：350 ；各课程所需学时：48；课程先、后修关系如图：194212101136578问题2：huffman编码对于确定的字符集的电文字符串编码，实现最高的通信效率。编程实现对于给定的输入串及各字符的已知频度，输出其编码方式（各字符的二进制编码）及对应的输出流。测试数据： 字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116问题3：成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。问题4：成绩排序对某次考试成绩排序，输入为多门课程成绩，可以任一课程成绩为关键字进行检索。建议采用快速排序等算法效率高的算法。问题5：迷宫求解一个M*N的长方阵迷宫，0和1分别表示迷宫中的通路和墙壁。对任意设定的迷宫，东、南、西、北四个方向是可能的行走方向。求出一条从入口到出口的路径。（或没有通路）。测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。001000100010001000001101011100100001000001000101011110011100010111000000问题6：一元多项式计算。对于任意输入的多项式A=anxn+an-1xn-1+a1x+a0和B=bmxm+bm-1xm-1+b1x+b0，用链表存储后实现A+B；A-B。测试数据：a.；b.；c.；d.；e. ；问题7: 通讯录管理设计一个通讯录管理，包括通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询以及信息修改等。要求有运行界面,从菜单中进入选项。三设计要求：1选题：每位学生需完成两个课题，其中一个必选，另一个自选，必选题次为，学号/7+1。2课程设计报告内容说明1)需求分析 程序的功能；输入输出的要求。2)概要设计 程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计 采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。5)使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式 见附带说明。7)附录 参考书目； 源程序清单（带注释）3成绩评定：指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。四进度安排第 17周星期一星期二星期三星期四星期五上午9：0012：00下午13：3016：30E512E411E414E414第 18周星期一星期二星期三星期四星期五上午9：0012：00下午13：3016：30E412E413附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。目录一，通讯录管理系统1. 需求分析2. 概要设计3. 详细设计4. 调试分析二，迷宫求解1. 问题描述2. 需求分析3. 概要设计4. 流程图5. 详细设计6. 调试分析三，课程设计总结四，附录通讯录管理系统1，需求分析设计一个实用的小型通讯录，用双向链表做数据结构，编写一个通讯录管理系统实现通讯录信息的输入、添加、显示、以姓名做关键字进行查找、删除信息等功能。每条信息至少包含：姓名、街道、城市、邮编、国家等信息。2，概要设计 载入文件load（）：将磁盘中可能存在的文件载入到内存中。信息输入enter（）：系统将提示输入新纪录所需信息，信息包含：姓名、街道、城市、邮编、国家。信息删除del（）：首先提示用户输入要删除的纪录姓名，然后调用删除函数，删除该纪录的相关资料，支持重名选择删除和循环删除。查找search（）：提示用户输入要查找的姓名，然后系统调用查找函数查找，接着系统使用相关命令输出查到的全部信息。显示全部display（）：将内存中的纪录内容全部输出，包括未保存到磁盘的记录项。保存save（）：将操作结果实时保存到磁盘文件txl.txt中，完成后返回到主菜单界面。退出系统exit（0）：直接退出系统，不保存修改。流程图:3，详细设计1. 各个操作的算法实现：（1）链表初始化void initlist()/链表初始化函数l=(linklist)malloc(sizeof(pnode);/动态申请内存l-next=l;l-prior=l;（2）载入可能存在的通讯录文件void load()/装载已有文件信息 /无文件，新建立文件;/已有文件，导入文件;（3）增加新结点void listinsert()/增加新结点 /插入新结点，读入内存信息;（4）添加新纪录（可循环）void enter()/添加新纪录 /信息输入; /是否继续添加？; （5） 按姓名查找（同时显示全部符合要求的结果，包括没有保存到磁盘的）void search() /输入姓名;/输出查询结果;/检索可能的重名纪录;（6） 显示所有记录（包括没有保存到磁盘的）void display()/显示所有纪录 /显示内存中的所有记录; （7） 删除指定记录（可循环）void del() /删除纪录 /输入要删除的姓名;/查找符合条件的记录，对于每条记录询问是否删除；/满足条件的输出结束，询问是否删除其他记录，循环;（8） 保存到磁盘文件（实时写入文件）void save()/ /写入文件操作;3，调试分析程序主界面新增联系人现实所有联系人查找联系人经过反复测试，最终提供了一个较为友好的界面和操作模式，而且容错能力较好，稳定性很强。下面做一些简单的说明：（1）2级菜单只是作为一种尝试，并非必须！（2） 在界面排版上，我学习了互联网上部分程序的界面编排，其中以格式控制方式显示提 高了界面显示的稳定性，较为理想。（3） 在文件读取和保存方面，该程序做到了实时保存保存和读取，操作非常简便。（4） 在查找方面，我将其设计为一次多记录的显示方式，也更合乎操作习惯，界面较为友 好，对于无符合条件的结果，只是结果集为空，界面保持不变。同时，它是实时读取 的，可以将刚刚输入而未保存的记录也读取到！另外，一次查询结束后返回的是查询 菜单，可以直接进行下一次的查询，也较为合理。（5） 删除功能我做了较多的工作，整体界面和设计都较为合理。对于输入的姓名，查找出结果后提示是否删除。若有重名，则会二次显示，提示是否删除，一直到所有记录查询结束（可以在重名中选中需要的进行删除，并不需要删除每一个纪录）。结束之后可以直接再次删除其他纪录，因为它提供循环删除操作功能。迷宫求解问题描述：a.问题描述：以一个m * n的长方阵表示迷宫，0和1分别表示迷宫的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。b.基本要求 ：（1）实现一个以链表做存储的栈类型，然后编写一个求解迷宫的非递归程序。求的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出一条通路：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）。（2）编写递归形式的算法，求得迷宫中所有可能的道路；（3）以方阵形式输出迷宫及其到道路（选做）c.测试数据：迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。001000100010001000001101011100100001000001000101011110011100010111000000d.实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着米一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求的一条通路。假如所有的可能的通路都探索到而未能到出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n，n）。为处理器方便起见，可在迷宫的四周加上一圈障碍 。对于迷宫中任一位置，均可约定有东、西、南、北四个方向可通。需求分析：本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中要应用“栈”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向（上、下、左、右）上相邻的方块。假设以栈记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。概要设计1.构建一个二维数组mazeM+2N+2用于存储迷宫矩阵自动或手动生成迷宫，即为二维数组mazeM+2N+2赋值构建一个队列用于存储迷宫路径建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况实现搜索算法屏幕上显示操作菜单 2.本程序包含10个函数： (1)主函数 main()(2)手动生成迷宫函数 shoudong_maze()(3)自动生成迷宫函数 zidong_maze()(4)将迷宫打印成图形 print_maze()(5)打印迷宫路径 (若存在路径) result_maze()(6)入队 enqueue()(7)出队 dequeue()(8)判断队列是否为空 is_empty()(9)访问节点 visit()(10)搜索迷宫路径 mgpath()流程图：详细设计实现概要设计中定义的所有数据类型及操作的伪代码算法1. 节点类型和指针类型迷宫矩阵类型：int mazeM+2N+2;为方便操作使其为全局变量迷宫中节点类型及队列类型：struct pointint row,col,predecessor que5122. 迷宫的操作(1)手动生成迷宫void shoudong_maze(int m,int n)定义i,j为循环变量for(i=m)for(j=n)输入mazeij的值(2)自动生成迷宫void zidong_maze(int m,int n)定义i,j为循环变量for(i=m)for(j=n) mazeij=rand()%2 /由于rand()产生的随机数是从0到RAND_MAX,RAND_MAX是定义在stdlib.h中的,其值至少为32767),要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X;(3)打印迷宫图形void print_maze(int m,int n)用i,j循环变量，将mazeij输出 、(4)打印迷宫路径void result_maze(int m,int n)用i,j循环变量，将mazeij输出 、(5)搜索迷宫路径 迷宫中队列入队操作void enqueue(struct point p)将p放入队尾，tail+迷宫中队列出队操作struct point dequeue(struct point p)head+,返回quehead-1判断队列是否为空int is_empty()返回head=tail的值，当队列为空时，返回0访问迷宫矩阵中节点void visit(int row,int col,int maze4141)建立新的队列节点visit_point,将其值分别赋为row,col,head-1,mazerowcol=2,表示该节点以被访问过;调用enqueue(visit_point),将该节点入队路径求解void mgpath(int maze4141,int m,int n)先定义入口节点为struct point p=0,0,-1,从maze00开始访问。如果入口处即为障碍，则此迷宫无解，返回0 ，程序结束。否则访问入口节点，将入口节点标记为访问过mazep.rowp.col=2,调用函数enqueue(p)将该节点入队。判断队列是否为空，当队列不为空时，则运行以下操作： 调用dequeue()函数，将队头元素返回给p，如果p.row=m-1且p.col=n-1,即到达出口节点，即找到了路径，结束如果p.col+1n且mazep.rowp.col+1=0,说明未到迷宫右边界，且其右方有通路,则visit(p.row,p.col+1,maze),将右边节点入队标记已访问如果p.row+10且mazep.rowp.col-1=0,说明未到迷宫左边界，且其左方有通路,则visit(p.row,p.col-1,maze),将左方节点入队标记已访问如果p.row-10且mazep.row-1p.col=0,说明未到迷宫上边界，且其上方有通路,则visit(p.row,p.col+1,maze),将上方节点入队标记已访问访问到出口(找到路径)即p.row=m-1且p.col=n-1,则逆序将路径标记为3即mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3; 最后将路径图形打印出来。3.菜单选择 while(cycle!=(-1) 手动生成迷宫 请按：1 自动生成迷宫 请按：2 退出 请按：3 scanf(%d,&i); switch(i) case 1：请输入行列数(如果超出预设范围则提示重新输入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 2 ：请输入行列数(如果超出预设范围则提示重新输入) zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 3：cycle=(-1); break;调试分析程序主界面手动输入迷宫在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以通过算法比较，改用此算法调试过程出现了最多60个错误。后经多次调试检查，发现有些格式问题没有注意比如函数括号的放置等。课程设计总结通过这段时间的数据结构课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实践的各个环节中，通过自主学习和认真听老师讲课分析，我收获了不少。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在这段时间里，我对for、while等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。例如：头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。时间过得真快，大学生活不知不觉就走过了一学期，这一学期的大学学习和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心，我们相信自己未来两年半的学习更使我们有能力胜任将来的工作。附录通讯录源程序#include #include #include #include struct record char name20; char street20; char city20; char eip20; /邮编char state20; people500;/500个记录，可修改struct pnoderecord data;struct pnode *next, *prior;/双循环链表;typedef pnode * linklist;linklist l;int len=0;/链表长度FILE *fp; /文件指针void mainmenu();/主菜单void searchmenu();/查询菜单void enter();/添加新纪录void search();/按条件搜索记录void display();/显示全部记录void load();/载入文件内容void save();/写入文件void del();/删除记录void listinsert();/插入结点函数void initlist();/初始化链表函数void main() /主函数 initlist();load();listinsert(); while (1)mainmenu(); /进入主菜单，有非法输入仍停留在主菜单 void initlist()/链表初始化函数l=(linklist)malloc(sizeof(pnode);/动态申请内存l-next=l;l-prior=l; void load()/装载已有文件信息 if(fp=fopen(txl.txt,rb)=NULL) printf(ntt通讯录文件不存在); if (fp=fopen(txl.txt,wb)=NULL) printf(ntt建立失败); exit(0); else printf(ntt通讯录文件已建立); printf(ntt按任意键进入主菜单); getch(); return; exit(0); /导入文件功能部分fseek(fp,0,2); if (ftell(fp)0) rewind(fp); for(len=0;!feof(fp)&fread(&peoplelen,sizeof(struct record),1,fp);len+); printf(ntt文件导入成功); printf(ntt按任意键返回主菜单); getch(); return; printf(ntt文件导入成功); printf(ntt通讯录文件中无任何纪录); printf(ntt按任意键返回主菜单); getch(); return; void listinsert()/增加新结点 linklist s,p=l;for(int i=0;idata.name,peoplei.name); strcpy(s-data.city,peoplei.city); strcpy(s-data.street,peoplei.street); strcpy(s-data.eip,peoplei.eip); strcpy(s-data.state,peoplei.state); s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s;p=p-next;void mainmenu()/主菜单 char ch; system(cls); printf(ntt 欢迎进入通讯录系统); printf(ntt 1-新添纪录 ); printf(ntt 2-查找联系人 ); printf(ntt 3-删除联系人 ); printf(ntt 4-保存 ); printf(ntt 5-退出 ); printf(ntt); printf(ntt请选择：); printf(%c ,ch=getch(); switch (ch) case 1:enter();break; case 2:searchmenu();break; case 3:del();break; case 4:save();break;case 5:exit(0); default:mainmenu(); void enter()/添加新纪录 printf(ntt* 请输入学生信息 *n); printf(ntt姓名:); scanf(%s,&peoplelen.name); printf(ntt街道:); scanf(%s,&peoplelen.street); printf(ntt城市:); scanf(%s,&peoplelen.city); printf(ntt邮编:); scanf(%s,&peoplelen.eip); printf(ntt国家:); scanf(%s,&peoplelen.state); len+; printf(ntt是否继续添加?(Y/N):); if (getch()=y) enter(); return; void searchmenu()/查询菜单 char ch; system(cls); printf(ntt 查询菜单 ); printf(ntt 1-显示所有记录 ); printf(ntt 2-按姓名查询 ); printf(ntt 3-返回主菜单 ); printf(ntt); printf(ntt请选择：); printf(%c,ch=getch(); switch (ch) case 1:display();break; case 2:search();break; case 3:mainmenu();break; void search() printf(ntt* 按姓名查找 *); char name20; printf(ntt请输入姓名:); scanf(%s,name); printf( 查询到的信息:n); printf( %-18s%-18s%-18s%-15s%sn,姓名,街道,城市,邮编,国家);/格式控制输出printf( -n);for (int i=0;ilen;i+) if(strcmp(name,peoplei.name)=0)printf( %-18s%-18s%-18s%-15s%sn,peoplei.name,peoplei.street,peoplei.city,peoplei.eip,peoplei.state);if (i+1len) continue;/重名纪录再检索 printf( -n);printf(ntt按任意键返回查询菜单); getch(); searchmenu(); void display()/显示所有纪录 int i; system(cls); if(len!=0) printf(ntt* 以下为通讯录所有信息*nn); printf( %-18s%-18s%-18s%-15s%sn,姓名,街道,城市,邮编,国家);printf( -n);for (i=0;ilen;i+) printf( %-18s%-18s%-18s%-15s%sn,peoplei.name,peoplei.street,peoplei.city,peoplei.eip,peoplei.state);if (i+1len) continue; printf( -n); else printf(ntt通讯录中无任何纪录); printf(ntt按任意键返回查询菜单：); getch(); searchmenu(); void del() /删除纪录 int a=0,i,j,findmark; /findmark为查找结果标志 / int findmark=0,delmark=0; char name20; printf(ntt请输入要删除学生姓名：); scanf(%s,name); for (i=a;ilen;i+) if (findmark=strcmp(peoplei.name,name)=NULL) /找到一条符合条件的记录 /findmark+; printf(ntt以下是您要删除的学生纪录：n); printf( %-18s%-18s%-18s%-15s%sn,姓名,街道,城市,邮编,国家);printf( -n);printf( %-