《数据结构课程设计》指导书

《数据结构》课程设计指导书沈阳理工大学.信息学院2013.11.1

一．目的与意义软件设计能力对计算机专业的学生是很重要。通过数据结构的学习，使学生对软件编程能力有一定的提高。数据结构课程设计是锻炼学生在进一步掌握模块化、结构化程序设计的方法的同时，培养学生运用已学知识分析问题、解决问题及编写实用程序的能力，通过对线性化、层次化、网络化数据结构的了解进一步掌握自然数据的结构方式及组织方式，让学生深入体会存储在计算机中的数据及程序中如何运用数据实现编程。主要目的如下：通过本课程设计使学生对面向对象的设计过程有初的认识，并对面向对象的高能语言的学习打下基础，通过不同类型的程序设计使学生进一步掌握数据的几种不同的组织和存储方式，为高级编程做准备，为专业课的深入学习和毕业设计打基础二．任务和要求分析每一组题目，按要求完成相应的题目：题目参照附录中《数据结构课程设计》题目选题。2.要求：对相应的题目进行算法设计编写源代码上机调试显示调试结果写出实验总结3．课程设计说明书设计完成后，将自己选定的题目按上述要求完成课程设计说明书。课程设计说明书内容包含：题目、要求、初步设计（可以是流程图、功能模块图）、详细设计、程序代码、测试数据、运行结果、遇到的问题及总结几部分。三．进度安排设计总学时为2周第一周：查阅资料、小组讨论、进行模块划分写出分析报告，画Ｎ－Ｓ结构化框图,编写程序清单，上机调试.第二周周四、五:验收（计算机机房）,并将课程设计报告交上来.四.考核标准与成绩评定方式成绩评定有如下几项参考：初步设计内容的考核：是否有查阅资料能力？是否有设计思想？程序编码能力调试能力的考核：程序是否清晰、易读？在技算计上是否可独立完成程序的调试，是否熟练？说明书质量的考核：设计结构是否合理？叙述是否正确？方案是否可行？答辩：设计结果的调试能力，对自己设计是否熟练？出勤率极平时表现的考核：出勤超过2次不到者成绩为不及格。五．选题参考按学号对应相应题目号，例：学号1203050101----》选择题目1。本次设计是为加强学生的软件编程能力而进行的专门训练。选题考虑到学生在数据结构中学过的各种算法、数据组织方式进行选题，考虑数据结构算法所涉及的操作系统、网络、编译方法等中的实例，进行设计。六.课程设计主要窗口展示部分

1.主窗口2.分层菜单附录题目：根据字符使用权值不同，设计哈夫曼编码，具体功能如下：①输入N个权值。②先构造哈夫曼树，然后再求各结点的编码。将编码写入文件③显示指定字符的哈夫曼编码④求指定两个结点的公共编码（先找到共同的祖先）。键盘输入一个含有括号的四则运算表达式，实现功能如下：①输出后缀表达式—即逆波兰；②将表达式的逆波兰式写入文件③对文件中的逆波兰表达式读出并求值。迷宫求解：在迷宫中求一条路径的算法，基本思想：若当前、位置可通过，则压入栈中，否则探索下一位置，若走不通，则回溯，迷宫大小：M*N。迷宫设置自定义。已知二叉树的中序序列和后序序列，求出这棵二叉树，并判别给定的二叉树是否是完全二叉树。输入数据对数据按菜单选择对数据进行插入排序。要求①菜单列出所有插入排序②对数据按菜单选择的进行排序③统计比较和交换的次数，将结果写入文件。2人完成输入数据对数据按菜单选择对数据进行选择排序。要求①菜单列出所有选择排序②对数据按菜单选择的进行排序③统计比较和交换的次数，将结果写入文件。输入数据对数据按菜单选择对数据进行交换排序。要求①菜单列出所有交换排序②对数据按菜单选择的进行排序③统计比较和交换的次数，将结果写入文件。对一个存储为邻接表的图求：①其邻接矩阵表示，将其储存到文件中。②求其所有连通分量并显示。③统计结点的度。内存分配算法：利用静态链表，模拟实现内存分配（分区、分页）请设计一个有效的算法，可以进行两个n位大整数的四则运算。航空公司每天起落的航班有很多，设计程序实现对航班信息的管理。具体功能包含：录入功能、查询功能、修改功能等。计算机外部输出设备（如显示器）和的CPU处理数据的速度不同。按先来先服务的方式进行管理，设计缓冲队列，实现外设与CPU的匹配。已知高校排课AOV网，给出一个排课序列（利用栈）二叉树用二叉链存储，链接时用叶子结点的rchild域存放指针。请设计一个算法完成①对一棵二叉树加线索（中序）；②把二叉树的叶子结点按从左到右的顺序连成一个单链表。③统计二叉树中0到2度结点了。处理器中有一就绪队列，若干个进程依到达的时刻依次进入就绪队列，每个进程有进程名和处理器处理此进程的所需空间，仿静态链表形式分配内存所需空间，编程序实现cpu调度算法。学籍管理：对学生、课程、成绩分别建立三个数据文件（学生、课程、成绩属性自定）。完成下列各题：①对数据录入②查询（如：某个学生的选课情况、成绩不及格的学生情况）③插入、删除、修改④排序（如：对课程名按不及格学生人数进行）等功能。工资管理：自己建立数据文件（提示可建立：职工、工资级别、职工工资）完成：①数据录入②查询（如：职工的平均工资查询、某一级别人员的平均工资查询）③插入、删除、修改④排序（将职工姓名按工资额度进行）等功能。房产信息管理按上述建立数据文件的方式对房产信息进行如下管理：①数据录入②查询③插入、删除、修改④排序等功能。供货信息管理按上述建立数据文件的方式对供货信息进行如下管理：①数据录入②查询③插入、删除、修改④排序等功能。图书管理建立图书数据文件进行如下管理：①数据录入②查询③插入、删除、修改④排序等功能。图书借阅管理建立借阅数据文件进行如下管理：①数据录入②查询③插入、删除、修改④排序等功能。通讯录：建立通讯录数据文件。完成下列功能：①对数据录入②查询（如：某个电话号、某个名字等）③插入、删除、修改④排序等。人事档案管理：建立数据文件（职工、部门、职称）完成：①数据录入②查询③插入、删除、修改④排序等功能。俄罗斯方块将堆排序的过程通过图示显示出来。要求：①输入一组数据②在顺序结构上完成,先建堆然后重建堆,最后实现全部排序。③图示上述过程。例如在菜单上：给出2则显示第二趟堆排序过程。④将排序结果写入文件。实现连通无向图的深度与广度遍历。基数排序的演示过程。最小生成树(普里母算法实现)的求解演示过程关键路径、拓扑排序的求解演示过程万年历：通过给定的年，求该年的日历，闰年判断：{Y%4&&!Y%100}||Y%400＝＝0要求：①输入年份②选择列数③打印日历并写入文件。说明：列数表示打印格式12行一列、6行二列、四行三列。。。。。给定两个串X和Y，①求子串在主串中的所有位置并记录②找出X和Y的一个最长公共子串。③置换①所定位的所有子串。将地图存储20个城市，求任意两个城市间的最短路径。分子式是用来表达分子组成结构的表达式，一般表达形式为A1c1A2c2A3c3...其中Ai(i=1,2,.......)表示原子或原子团，ci(i=1,2,....)表示原子或原子团Ai重复的次数。当ci=1时，ci必须省略不写，且原子团的括号也不要。例如N的原子量为14，H的原子量为1，C的原子量为12，O的原子量为16，因此(NH4）2CO3的分子量为（14+1*4）*2+12+16*3=96。试编写程序求出给定的各个分子式所对应的分子量。设明文P=P0P1P2…Pn和密钥K=K0K1K2…Km(n>=m)中的字符Pi(1<=i<=n)或Kj(1<=j<=m)的ASCII为00~7FH，用密钥K对明文P进行加密得到密文C=C0C1C2…Cn,用密钥K对密文C解密得到明文P。加密：Ci=Pi+Kj(j=imod(m+1))(当Ci<=7FH)Ci=Pi+Kj-80H(j=imod(m+1))(当Ci>7FH)解密：：Pi=Ci-Kj(j=imod(m+1))(当Ci>=Kj)Pi=Ci-Kj+80H(j=imod(m+1))(当Ci<Kj)要求：①将明文加密后别存入文件中②将密文文件解密后存入另一文件中③将明文中的某字符u替换为v，同时将密文中的字符做相应修改。矩阵A中的元素若满足：A[i,j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称元素A[i,j]为该矩阵的一个马鞍点。求出用一维数组压缩存储表示的稀疏矩阵m×n矩阵的所有马鞍点。银行业务模拟问题描述：客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。五子棋在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W[i][j]=0表示在位置(i,j)上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。模拟实现五子棋过程。运动会分数统计程序的设计（2人）运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)．能统计各学校总分，3)．可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以