一、课程设计教学目的及基本要求
1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4．训练用系统的观点和软件开发一般规范进行软件开发。
二、课程设计题目
1．学生信息管理
要求每条学生信息至包含学号(xh)、姓名(xm)、性别(xb)、年龄(nl)、专业(zy)等，完成如下功能：
（1）输入学生基本信息记录——enter()
（2）增加一名学生记录（可和功能1合并）——insert()
（3）删除指定（按姓名）学生的信息——delete()
（4）修改指定（按姓名）学生的信息）——modify( )
（5）查询符合条件的学生（按专业）——search()
（6）显示学生管理库中的信息——display( )
2．计算一元稀疏多项式
要求完成如下功能：
（1）输入并建立多项式——creatpolyn()
（2）输出多项式，输出形式为整数序列，序列按指数升序排列——printpolyn() （3）多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn() （4）多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn() 用带表头结点的单链表存储多项式。
测试数据：
（1）(2x+5x8-3.1x11)+(7-5x8+11x9)
（2） (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)
（3）(x+x2+x3)+0
（4）(x+x3)-(-x-x-3)
3．通讯录的制作
要求每条信息至包含姓名（name ）城市（city）电话（tel）QQ号（qq），完成
如下功能：
（1）输入信息—— enter();
（2）显示信息——display( );
（3）查找以姓名作为关键字——search( );
（4）删除信息——delete( );
（5）存盘（将数据保存在文件中，此功能选做）——save ( );
4．实现两个链表的合并，编一程序将A表和B表归并成一个新的递增有序的单链表C（值相同的元素均保留在C表中），并要求利用原表的空间存放C
测试数据：
（1） A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）
（2） A表（30，41，15，12，56，80，23，12，34）
B表（23，56，78，23，12）
5．实现字符串的基本操作
完成如下功能：
（1）插入子串——StrInsert()
（2）取子串—— SubString()
（3）串连接—— StrCat()
（4）查找子串的位置——Index()
6、运动会分数统计**
任务：参加运动会有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、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；
7、一元多项式计算**
任务：能够按照指数降序排列建立并输出多项式；
能够完成两个多项式的相加、相减，并将结果输入；
在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
8、订票系统
任务：通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
退票：可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：
当航班信息改变可以修改航班数据文件
要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
9、迷宫求解
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
要求：
在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
10、文章编辑**
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；
11、 joseph环
任务：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：
m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
要求：
输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。
输出形式：建立一个输出函数，将正确的输出序列
12、猴子选大王**
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n m,n 为整数，n 输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能 13、建立二叉树，层序、先序遍历（用递归或非递归的方法都可以）** 任务： 要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 14、赫夫曼树的建立 任务：建立建立最优二叉树函数 要求：可以建立函数输入二叉树，并输出其赫夫曼树 在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 15、纸牌游戏** 任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？ 16、图的建立及输出 任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 要求： 17、拓扑排序 任务：编写函数实现图的拓扑排序。 18、各种排序 任务：用程序实现插入法排序、起泡法改进算法排序； 利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。 输入的数据形式为任何一个正整数，大小不限。 输出的形式：数字大小逐个递增的数列? 19、最小生成树 内容： （1）了解图和网的概念。 （2）学习实现最小生成树的几种算法。 （3）利用克鲁斯卡尔算法求网的最小生成树。 20、哈希表设计 内容： （1）了解几种哈希函数的构造方法，了解处理冲突的方法。 （2）选择合适的函数完成建表和查表程序。 21、学生成绩管理 设计一个简单的学生成绩管理系统。要求用链表保存学生信息，每个学生信息包括：学生姓名、学生学号、数学成绩、英语成绩四项。可以增加新学生、修改学生成绩（学号和姓名不能修改）、删除学生信息、打印学生成绩。支持按姓名、学号查学生的信息，可以统计某班的及格率，可以按照学生的成绩排序。（最好用文件存放学生信息，开始程序时读入学生信息；修改学生信息后最后能够写入文件，以便下次读入。） 22、八皇后问题 设在初始状态下在国际象棋上没有任何棋子。然后顺序在第1行，第2行，…，第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件：即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个算法（递归或者非递归均可），求解并输出此问题的所有合法布局。 提示：用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递规求解，否则可移走这个棋子，回复安放此棋子前的状态，试探本行的j＋1列。 23、二叉树内容 实现下面题目中任意两个： 1、实现一个判断两个二叉树是否相等的接口 2、读取一个二叉树的前序和中序遍历结果，恢复这个二叉树（即实现其链式的存储）。 3、对于链式的二叉树，按层次遍历二叉树 24、公园导游图 给出一张某公园的导游图，游客通过终端询问可知： 1、从某一景点到另一景点的最短路径 2、实现添加新景点的功能（包括此点与已有景点的路径 25 家庭成员的管理问题 [问题描述] 例如有这样的一对老夫妻（A、B），他们生有n男m女，其中，某个儿子（D）娶妻（C）生有x男y女，某个女儿（E）嫁夫（F）生有i男j女，其余的子女有可能婚嫁，也有可能单身，已婚的可能生有孩子若干，其孩子相继婚嫁…… 26. 编写一个猜数字游戏，有一定的容错功能，界面友好，功能齐全。 游戏规则： a，一个四位数，各位上的数字不重复,从1到9。 b，按以下提示猜出这个四位数。 c，每次猜测输入的数据给出类似的提示*A*B。 d，其中A前的*代表你本次猜对了多少个数字。 e，其中B前的*代表你本次猜对的数字并且位置正确的个数。 27. 写出6＋1彩票开奖的情况，当前6个号码和特别号都对的时候，这个时候是特等奖。如果前面6个号码都对的时候，中的是一等奖。在前面6个数字中连续的对了5个的时候，中的是二等奖。在前面6个数字中连续的对了4个的时候，中的是三等奖。 请编写程序，实现连续多个输入，并在每次输入以后显示号码中奖的情况。28. 用C语言设计一个日历系统 功能要求： 1）输入任一年将显示出该年的所有月份日期，对应的星期 2）注意闰年情况 其显示格式要求如下： 1）份：中文英文都可以， 2）下一行显示星期，从周日到周六，中英文都可以 3）下一行开始显示日期从1号开始，并按其是周几实际情况与上面的星期数垂直对齐 当输入2004显示如下： Input the year:2004 Input the file name:a The calendar of the year 2004. Januray 1 February 2 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 1 2 3 4 5 6 7 4 5 6 7 8 9 10 8 9 10 11 12 13 14 11 12 13 14 15 16 17 15 16 17 18 19 20 21 18 19 20 21 22 23 24 22 23 24 25 26 27 28 25 26 27 28 29 30 31 29 =========================== =========================== March 3 April 4 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 1 2 3 7 8 9 10 11 12 13 4 5 6 7 8 9 10 14 15 16 17 18 19 20 11 12 13 14 15 16 17 21 22 23 24 25 26 27 18 19 20 21 22 23 24 28 29 30 31 25 26 27 28 29 30 =========================== =========================== 29. 二叉排序树与平衡二叉树的实现 (1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历，输出结果； (3)计算二叉排序树T查找成功的平均查找长度,输出结果； (4)输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序 遍历(执行操作2)；否则输出信息“无x”； (5)用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二 叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉 排序树BT； (6)计算平衡的二叉排序树BT的平均查找长度，输出结果。 30 . 线性表的链式表示和实现1（限1 人完成） 任务:( 1) 动态地建立单链表,实现插入元素、删除元素、查询、求表长度； （2）建立两个有序的单链表LA和LB，实现合并成LC，要求分LC中有和无重复值两种情况的实现； （3）求两链LA和LB两链元素的交集LD。 （4）静态链表的实现：使用数组实现单向链表的建立、插入元素、删除元素。31．线性表的链式表示和实现2（限1 人完成） 任务：（1）动态地建立循环链表； （2）实现循环链元素的插入，删除，查询； （3）使用双向链的结构实现判断一个录入的字符串是否是回文。 （4）建立一个单向链表，实现其内元素非递减排序。 32．栈的应用1 任务：（1）假设一死胡同仅能容一辆汽车进入， 使用顺序栈或链栈模拟汽车进入和退出的动态过程； （2）验证用户输入的表达式是否符合数学意义上的括号匹配（常用的括号有( ( ), [ ] { } ); 33．模拟排队（限1 人完成） 任务：（1）本题数据结构选用队列； （2）假设某汽车站有两个售票窗口，每一个窗口对每一们购票者服务时间为n秒，当新来的购票者在判断两个排列队列人数多少后再决定插入到哪个队列。 （3）动态地模拟这两个队列的运行过程。 34．跳舞搭配问题（限1 人完成） 任务：一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下: 1)输出每曲配对情况 2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况. 至少求出K的两个值. 3)尽量设计出多种算法及程序,可视情况适当加分 35．线索二叉树的应用（限1 人完成） 任务：（1）建立一任意二叉树 （2）按中序遍历的顺序线索化以上二叉树。 （3）按先序遍历的顺序线索化以上二叉树。 （4）实现在一已经中序线索化后的二叉树上插入和删除结点，并保证索引不破坏。 36．二叉树综合应用（限1 人完成） 任务：（1）用户正确输入一棵二叉树的中序和后序序列，如下： 中序：G L D H B E I A C J F K 后序: L G H D I E B J K F C A 根据以上序列来编程实现建立这棵二叉树 （2）用户正确输入一棵二叉树的先序和中序序列，如下： 先序： A B C D E F G H I 中序： B C A E D G H F I 根据以上序列来编程实现建立这棵二叉树 （3）把上面第（2）小题建立的二叉树按中序遍历线索化，并以中序遍历此二叉树。 37．树的存储与遍历（限1 人完成） 任务：以教材p135图6.13为准，实现下列要求 （1）使用双亲表示法实现此树的存储并遍历此树 （2）使用孩子表示法实现此树的存储并遍历此树 （3）使用孩子兄弟表示法实现此树的存储并遍历此树 （4）选择以上任何一种存储为结构基础，实现把此树转换成一棵二叉树 38．幂集求解（限1 人完成） 任务：求有n 个元素的集合的幂集。 提示：一个集合的幂集即是其所有子集所组成的集合；参照教材P150的算法分析。（1）建立生成幂集过程的状态的二叉树 （2）输出任意一集合的幂集 39．图的应用2（限1 人完成） 任务：有N个城市，已知每对城市之间的距离，要求完成： （1）建立描述以上N个城市之间距离关系的图，结构自选 （2）任意输入两个城市名，可查询出其间的距离 （3）现要在这N个城市中建立一个交通网，要求距离代价最低，保证各城市能连通即可，请设计出一种方案。 40 地图着色问题（限1 人完成） 任务：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。 41 学校超市选址问题（带权有向图的中心点）（限1 人完成） 任务：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。 42活期储蓄帐目管理（限1 人完成） 实现功能： 1）实现储户开户、销户、存入、支出活动频繁，系统任务： 2）实现使用多种方法查询，找到储户的帐户，以实现存款、取款记账； 3）能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。 43图书管理系统（限1 人完成） 任务：设计一个计算机管理系统完成图书管理基本业务。 （1）每种书的登记内容包括书号、书名、著作者、现存量和库存量； （2）对书号建立索引表（线性表）以提高查找效率； （3）采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； （4）借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； （5）归还：注销对借阅者的登记，改变该书的现存量。 44数制转换问题（限1 人完成） 任务：任意给定一个M进制的数x ，请实现如下要求 1)求出此数x的10进制值 2)实现对x向任意的一个非M进制的数的转换； 3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法 解决）。 此题工作量不够：故附加要求： 4）输入一个数学表达式，判断其中的括号是否配对。（括号有“（） [ ] { }”三种） 三、课程设计报告的规范 课程设计报告要求规范书写。应当包括如下六个部分： 1、设计目的与内容。 进行需求分析，确定每个模块的功能要求。即根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？） 2、算法的基本思想 进行概要设计和详细设计。说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。并用自然语言描述每个模块所涉及的算法。 3、测试数据 列出对于给定的输入所产生的输出结果。 4、源程序及系统文件使用说明 附上关键数据结构的定义及关键算法的源代码。 5、心得体会 谈谈课程设计过程的收获、遇到问题及解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。 6、参考文献 参考文献要注明作者、出版社、出版日期。 四、设计最终需提交的内容包括： 1．完整的程序系统（电子方式提交） （1）．能够对输入产生相应的输出，并在输入输出做必要的提示。 （2）．该部分包括源代码和可执行文件两个部分。 （3）．所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均可），压缩后的文件按规定格式进行命名，命名格式为：学号+姓名.rar（如z04043120张文.rar）。 (4)将提交作品发送到邮箱xialh@https://www.doczj.com/doc/fc4070589.html, 2．课程设计报告,字数不少于1000字 数据结构课程设计题目 数据结构课程设计题目(大题目).doc 一、公司销售管理系统 项目开发基本要求 1．客户信息管理：对客户的基本信息进行添加、修改和删除。 2．产品信息管理：对产品的基本信息进行添加、修改和删除。 3．供应商信息管理：对供应商的基本信息进行添加、修改和删除。 4．订单信息管理：对订单的基本信息进行添加、修改和删除。 二、高校科研管理系统 系统主要用于帮助高校或科研单位管理和维护各项科研相关资料 项目开发基本要求 1．系统用户管理模块：为系统新用户设置用户名及口令；操作员更改自己的系统口令。2．数据字典管理模块：管理项目性质包括：分为国家自然科学基金、863、部省科委及企业集团四种情况；范围包括：分为全国、国际、地方三种情况；检索源包括：分为EI、SCI、核心和一般四种情况。 3．项目参加人员管理模块包括：显示添加修改删除查询。 4．项目基本情况模块包括：显示添加修改删除查询。 5．项目获奖情况模块包括：显示添加修改删除查询。 6．期刊论文管理模块包括：显示添加修改删除查询。 7．著作管理模块包括：显示添加修改删除查询。 8．科研工作量统计模块：按照学校科研工作量计算办法，为每位科研人员进行科研工作量的计算和统计。 9．科研积分统计模块：按照学校科研积分计算办法，为每位科研人员进行科研计分的计算和统计。 三、网络五子棋对战 四、不同排序算法模拟 五、科学计算器 数据结构课程设计题目 1.运动会分数统计 任务：参加运动会有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)能统计各学校总分， 数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件， 会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。 1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出； 一、数据结构课程设计要求 1.学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。 3.课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上2小时的上机来调试C 或C++语言设计的程序，总共至少要上机调试程序20小时。属教师安排上机时间学生不得缺席。 二、数据结构课程设计题目 1. 运动会分数统计（限1 人完成） 任务：参加运动会有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) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2. 飞机订票系统（限1 人完成） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 数据结构课程设计题目 说明： （1）选用语言：C或Java语言； （2）需要注明3人（可少于3人）小组各自承担和完成的任务（据此给予成绩）； （3）如下带“*”的题目，“*”越多，难度越大一些，分值权重更高---要得到更高分数，推荐选择。 要求： (1) 用中文给出设计说明书（含重要子函数的流程图）； (2) 给出测试通过、能实现相应功能的源代码； (3) 测试报告。 0、小学数学四则混合运算试题出题、评价、题库自动生成与组卷系统（****）---已经有2组选择 任务： （1）将随机给出的四则混合运算表达式显示在计算机显示器上，要求应试者给出答案；并且使用堆栈对该表达式求值，同给出的答案进行比较，判断 正确和错误。给出鼓励信息和嘉奖信息； （2）保存多人在不同时间应试的题目与他（或她）给出的答案，评价所出题目的难易程度（通过多人回答正确与否的情况给出），形成题库； （3）按照用户给出的题目难易程度指标（例如让50人的得分满足怎样的正态分布，如90分以上10%，80分以上30%，70分以上30%，60分以上20%，60分 以下10%），从题库中抽取不同的题目，组成试卷。 要求：随机产生的题目中，参加运算的数据随机、运算符随机。题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。 1、集合的并、交和差运算---已经有1组选择 任务：编制一个能演示执行集合的并、交和差运算的程序。 要求: (1) 集合的元素限定为小写字母字符[…a?..?z?] 。 (2) 演示程序以用户和计算机的对话方式执行。 实现提示:以链表表示集合。 选作内容: (1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。 (3) 集合的混合运算表达式求值。 (4) 集合的元素类型推广到其他类型，甚至任意类型。 2、停车场管理------已经有2组选择 任务：设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 要求：以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。 3、哈夫曼码的编/译码系统（**）---已经有1组选择 题目： 学院： 专业班级： 学生姓名： 指导教师： 2016 年06 月2 9日 目录 一、课程设计目的 (3) 二、课程设计步骤 (3) 三、课程设计内容 (4) 四、课程设计报告 (6) 五、提交材料 (6) 六、考核方式与评分标准 (7) 七、参考文献 (8) 附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9) 一、课程设计目的及要求 《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。 要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。 课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。要求在教学周的第18周前完成。 二、课程设计步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤： 1.问题分析和任务定义 通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2.数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个 福建工程学院课程设计 课程：数据结构课程设计 题目： 1.综合应用 2.折半查找 3.快速排序 专业：软件工程 班级：1101 座号：3110305129 姓名：潘聪 2012 年 6 月26 日 设计题目1：综合应用 一、问题描述 有N名学生，每名学生含有如下信息：学号、姓名、某四门课的成绩，并计算其总分，用一结构数组表示之。然后实现以下功能： （1）将这些数据存放至文件stuf.dat中； （2）将文件中的数据读出至结构数组中，并显示之； （3）输出总分最高分和最低分的名字； （4）输出总分在340分，单科成绩不低于80分的名单； （5）求出各科平均分数； （6）按总分排名； （7）输出补考名单。 二、解决问题的算法思想描述 （1）子函数：首先确定需要的子函数，总共7个，对应的功能分别是题目要求的七项（2）主函数：主函数中，要设计出易于使用的人机界面，就必须要用到switch 。 （3）文件的存放读取，必须要用到文件的函数，fopen，fread，fclose等。 （4）把每个学生的信息定义在一个结构数组中，利用结构数组更加方便。 （5）各科成绩排名用冒泡排序即可。 （6）输出总分，补考名单，各科的平均分都比较简单。 三、设计 1. 数据结构的设计和说明 //定义结构体 typedef struct { int num; //学号 char name[10]; //姓名 int score1; //语文 int score2; //数学 int score3; //物理 int score4; //化学 }student; student stu[MAX]; //结构数组 2．模块结构图及各模块的功能： 题目2：运动会分数统计 1.问题描述 参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 2.功能要求 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分； 3)可以按学校编号、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。 。 题目6：哈夫曼编/译码器 1.问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 2.功能要求 I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile 中。 D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint 中。 题目9：构造可以使n个城市连接的最小生成树 1.问题描述 给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 2.功能要求 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 <<数据结构>> 课 程 设 计 班级:111004 姓名:董丽美 学号:111004122 指导教师:史延新 完成日期:2013 _07 _10 题目一:约瑟夫环问题 【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为1,2，…,n 的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。 【测试数据】m的初值为20；n=7,7个人的密码依次为：3,1,7,2，4,8,4，首先m值为6（正确的出列顺序应为：6,1,4,7,2,3,5） 一 .需求分析 1．用单循环链表存储并遍历及删除节点的方法，计算并输出约瑟夫环的问题。 2．环中总人数和节点信息由用户输入，且均为正整数。3．在窗口界面输出出列顺序的编号。 二．概要设计 1.设定链表的抽象数据类型定义： ADT List{ 数据对象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0} 数据关系：R1={ 《数据结构》课程设计题目 1. 排序算法的性能分析 问题描述 设计一个测试程序，比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 基本要求 （1）对冒泡排序、直接排序、选择排序、箱子排序、堆排序、快速排序及归并排序算法进行比较。 （2）待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3）输出比较结果。 选做内容 （1）对不同表长进行比较。 （2）验证各算法的稳定性。 （3）输出界面的优化。 2. 排序算法思想的可视化演示—1 基本要求 排序数据随机产生，针对随机案例，对冒泡排序、箱子排序、堆排序、归并算法，提供排序执行过程的动态图形演示。 3. 排序算法思想的可视化演示—2 基本要求 排序数据随机产生，针对随机案例，，对插入排序、选择排序、基数排序、快速排序算法，提供排序执行过程的动态图形演示。 4. 线性表的实现与分析 基本要求 ①设计并实现线性表。 ②线性表分别采取数组（公式化描述）、单链表、双向链表、间接寻址存储方 式 ③针对随机产生的线性表实例，实现线性表的插入、删除、搜索操作动态演示(图 形演示)。 5. 等价类实现及其应用 问题描述：某工厂有一台机器能够执行n个任务，任务i的释放时间为r i（是一个整数），最后期限为d i（也是整数）。在该机上完成每个任务都需要一个单元的时间。一种可行的调 度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。 基本要求： 使用等价类实现以上机器调度问题。 等价类分别采取两种数据结构实现。 6. 一元稀疏多项式计算器 问题描述 设计一个一元稀疏多项式简单计算器。 基本要求 一元稀疏多项式简单计算器的基本功能是： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，…,c n，e n，其中n是多项式的项数，c i，e i，分别是第i项的系数和指数，序列按指数降序排序； （3）多项式a和b相加，建立多项式a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做） 7. 长整数的代数计算 问题描述 应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。 基本要求 ①长整数长度在一百位以上。 ②实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+b mod n, a-b mod n, a?b mod n, a÷b mod n。 ③输入输出均在文件中。 ④分析算法的时空复杂性。 8. 敢死队问题。 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。 9. 简单计算器 （一）课程设计要求 1.分组要求 每个人一个小组进行分组。 2.实训目的 （1）熟悉课程所学的内容，包括线性表、链表、串，栈，队列，树，图，查找和排序； （2）学生能够按照软件工程的规范要求，能够运用软件工程的基本概念、方法与过程来进行软件的设计与开发。 3.课程设计要求 （1）每组学生在以下项目中选择一项完成即可； （2）编写程序要严格按照程序编程规范进行代码编写; （2）必须按照个体软件的过程，真实地采集数据、填写相关的表格、编写有关的文档; （3）按照老师的要求，每个人必须独立完成; （4）按照实训的时间安排进行实训，实训结束后提交有关的表格与文档。（二）课程设计题目 1.线性表 （1）实验目的：利用顺序结构和链式结构实现线性表的基本运算。 （2）实验要求：对于顺序存储结构的线性表，验证其插入、删除操作；对以链式存储结构存储的线性表，验证其插入、删除、查找操作。 2.火车列车调度问题 （1）实验目的：利用顺序结构和链式结构实现栈和队列的基本运算 （2）实验要求：栈操作的验证火车调度；对于顺序队列、链队列的基本操作进行验证； 3.稀疏矩阵 （1）实验目的：利用三元组和十字链表实现稀疏矩阵的有关算法 （2）实验要求：以三元组作为存储结构实现稀疏矩阵的转置 4.二叉树 （1）实验目的：利用二叉链表实现二叉树的建立和遍历 （2）实验要求：以二叉链表作为存储结构建立二叉树；以二叉链表作为存储结构实现先序、中序和后序遍历二叉树 5.图的遍历和最短路径问题 （1）实验目的：在图的两种存储结构基础上实现图的遍历 （2）实验要求：采用连通无向图作为遍历对象对以邻接矩阵为存储结构的图实现深度优先搜索和广度搜索遍历；采用连通无向图作为遍历对象，建立邻接表时顶点对序号从大到小输入，对以邻接表为存储结构的图实现深度优先搜索和广度优先搜索遍历； 6.排序与查找 （1）实验目的：验证各排序与查找算法 （2）实验要求：编程实现排序与查找算法，包括直接插入排序、选择和起泡排序、折半查找 7.综合课程设计1 （1）实验目的：综合应用所学知识；培养系统设计的整体思想；提高编写程序、调试程序的能力；学习系统测试的方法；学习编写技术文档； （2）实验要求：约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列； 8.综合课程设计2 （1）实验目的:综合应用所学知识；培养系统设计的整体思想；提高编写程序、调试程序的能力；学习系统测试的方法；学习编写技术文档； （2）实验要求：设计一个校园导游程序，为来访的客人提供各种信息查询 郑州工业应用技术学院 课程设计说明书 题目：手机信息数据检索 姓名：王港 院（系）：信息工程学院 专业班级：16级计算机科学与技术6班 学号：1601110241 指导教师：王礼云 成绩： 时间：2018 年 1 月 2 日至2018 年 1 月12 郑州工业应用技术学院 课程设计任务书 题目手机信息数据检索 专业、班级16级计算机科学与技术6班学号1601110241姓名王港 主要内容： 开发一个手机信息数据检索，使管理员可以很好的管理回收的手机，避免平时废旧手机没有作用，不知道如何去处理旧的手机等问题。减轻废旧手机资源的浪费。本废旧手机回收系统利用单链表实现了基本信息的添加。管理员能够对各种信息进行修改，例如手机信息添加，手机信息删除，密码修改，退出系统。 基本要求： 1、巩固并加深学生对数据结构基本算法的理解； 2、认识面向过程和面向对象两种设计方法的区别； 3、进一步掌握和应用VC++6.0 集成开发环境； 4、提高运用对于数据结构的理解，增强了我解决实际问题的能力； 5、初步掌握开发小型实用软件的基本方法。 主要参考资料： [1]谭浩强. C语言基础课程[M].北京:清华大学出版社,2009. [2]刘振安. C程序设计课程设计[M].北京:机械工业出版社,2016. [3]滕国文. 数据结构课程设计[M].北京:清华大学出版社, 2010. [4]吴伟民. 数据结构[M].北京:清华大学出版社, 2017. 完成期限：2018.1.2-2018.1.12 指导教师签名： 课程负责人签名： 2018 年1 月12 日 摘要 21世纪以来，经济高速发展，人们生活发生了日新月异的变化，特别是手机普及到每个人生活的各个领域。但对于手机的回收越来越不适应现在社会的发展。计算机技术的飞速发展，也为我们带来了巨大的便利。为了适应现代人们回收旧手机方便的愿望。手机信息管理系统软件能够为我们现如今手机回收带来巨大的便利。 我国现如今已经成为手机产品的生产消费大国，伴随着通信技术的迅猛发展，手机更新换代的速度不断提高。特别是追求时尚潮流的大学生群体手机的更换频率增加更快。随着智能手机产品不断推陈出新，手机更新换代的周期也在缩短。据业内人士估计，我国存量闲置手机至少以亿计，但旧手机的回收率却不到2%，旧手机的处置成为一大问题。 中国目前废旧手机的回收现状和回收模式，造成我国手机回收效率低下，更是对垃圾回收产业带来了巨大的冲击，同时目前，我国年废旧手机产生量约上亿部，大部分闲置家中，未能有效回收利用。既浪费了资源，又威胁居民身心健康，造成环境污染。在分析我国废旧手机回收利用现状的基础上，提出了完善废旧手机回收的法律制度、增强消费者环保意识、构建绿色环保废旧手机回收利用新模式等建议。本手机信息数据检索为回收手机的人管理废旧的手机使用，使用单链表实现，对于信息的增加删除效率比较高，可以很方便的进行各种信息管理，对于数据的管理可以让我们更好的面对管理手机的繁杂工作。 关键字：信息检索；冒泡算法；单链表 《数据结构》课程设计课题表 课题1：设计出链表结构的相关函数库，以便在程序设计中调用。要求： （1）包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题2：设计出顺序表结构的相关函数库，以便在程序设计中调用。要求： （1）包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题3：设计程序以实现任意两个高次多项式的加法和乘法运算。 要求： （1）所设计的数据结构应尽可能节省存储空间。 （2）程序的运行时间应尽可能少。 课题4：设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。 要求：要检查有关运算的条件，并对错误的条件产生报警。 课题5：设计出二叉链表结构的相关函数库，以便在程序设计中调用。要求： （1）包括二叉树的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题6：设计出树结构的相关函数库，以便在程序设计中调用。要求： （1）包括树结构的存储结构及各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题7：选择合适的存储结构表示广义表，并能实现下列运算要求： （1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。 （2）取广义表L的表头和表尾的函数head(L)和tail(L)。 关于数据结构课程设计心得体会范文 心得体会是指一种读书、实践后所写的感受性文字。是指将学习的东西运用到实践中去，通过实践反思学习内容并记录下来的文字，近似于经验总结。下面是小编搜集的关于数据结构课程设计心得体会范文，希望对你有所帮助。 关于数据结构课程设计心得体会(1) 这学期开始两周时间是我们自己选题上机的时间，这学期开始两周时间是我们自己选题上机的时间，虽然上机时间只有短短两个星期但从中确实学到了不少知识。上机时间只有短短两个星期但从中确实学到了不少知识。 数据结构可以说是计算机里一门基础课程，据结构可以说是计算机里一门基础课程，但我觉得我们一低计算机里一门基础课程定要把基础学扎实，定要把基础学扎实，然而这次短短的上机帮我又重新巩固了 c 语言知识，让我的水平又一部的提高。数据结构这是一门语言知识让我的水平又一部的提高。数据结构这是一门知识，纯属于设计的科目，它需用把理论变为上机调试。 纯属于设计的科目，它需用把理论变为上机调试。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。来说具有一定的难度。它是其它编程语言的一门基本学科。我选的上机题目是交叉合并两个链表，对这个题目，我选的上机题目是交叉合并两个链表，对这个题目，我觉得很基础。刚开始调试代码的时候有时就是一个很小的错觉得很基础。 刚开始调试代码的时候有时就是一个很小的错调试代码的时候误，导致整个程序不能运行，然而开始的我还没从暑假的状导致整个程序不能运行，态转到学习上，每当程序错误时我都非常焦躁，态转到学习上，每当程序错误时我都非常焦躁，甚至想到了放弃，但我最终找到了状态，一步一步慢慢来，放弃，但我最终找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件! 同时，通过此次课程设计使我了解到，必然具备的条件! 同时，通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得件语言必不可缺少，要想成为一个有能力的人，硬件 《数据结构课程设计》报告 题目：课程设计题目2教学计划编制 班级：700 学号：09070026 姓名：尹煜 完成日期：2011年11月7日 一．需求分析 本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。 （一）输入形式：文件 文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。 格式：第一行给出课程数量。大于等于0的整形，无上限。 之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。 课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。 先给出边的数量。大于等于0的整形。 默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。 例： （二）输出形式：1.以图形方式显示有向无环图 2.以文本文件形式存储课程安排 （三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系） 以图形方式输出课程的有向无环图。 拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果） 二．概要设计 数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个 是为了实现核心算法拓扑排序。 2.ArrayList数据结构课程设计参考题目
数据结构实验总结报告
数据结构课程设计
数据结构课程设计题目2010
数据结构课程设计题目选择
数据结构课程设计
数据结构课程设计
数据结构课程设计独立题目
数据结构课程设计题目及要求
数据结构课程设计报告模板
数据结构课程设计
数据结构课程设计题目
数据结构课程设计内容
数据结构课程设计
数据结构课程设计题目表
关于数据结构课程设计心得体会范文
数据结构课程设计报告
相关主题
文本预览