数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：
了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
二、课程设计的基本要求
1、独立思考，独立完成：每人任选一题，在课程设计中各任务要求独立完成，遇到问题大家可以相互讨论，互相调试检查，但不可以拷贝。
2、按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；
其中包括：
a）需求分析：
在该部分中叙述，每个模块的功能要求
b）概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。
c）详细设计
各个算法实现的源程序（可放在附录中），对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
d）调试分析
4、每人实现的结果必须进行检查和演示；程序源代码和程序的说明文件必须上交，作为考核内容的一部分；（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“11207210188张丽”。该文件夹下至少包括：“源代码”和“课程设计报告”，统一放在服务器的文件夹“d：/3
/11级专升本数据结构课程设计”中）。
5、课程设计报告要对重点函数及结构进行说明。报告格式参照（报告示例）。
6、报告提交
形式：课程设计报告(要求书写课程设计报告）和电子文档。
三、课程设计内容：
1.大数相乘问题
例如：输入第一个数为：***172586，输入第二个数为：***7则程序运行后输出***172586****7=正确答案。2．矩阵的运算
采用十字链表表示稀疏矩阵，并实现矩阵的加减法和乘法运算,要求：要检查有关运算的条件，并对错误的条件产生报警。3．订票系统
设计航班信息，订票信息的存储结构，设计程序完成如下功能：
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件6．宾馆订房和退房系统
假设一个宾馆有n个标准的客房，每个标准客房有m个标准间，利用链表、栈或者队列等数据结构设计出具有订房和退房等功能的管理系统。7．建立二叉树和线索二叉树
分别用以下方法建立二叉树：1）用先序遍历的输入序列2）用层次遍历的输入序列3）用先序和中序遍历的结果
最后对所建立的二叉树进行中序线索化，并对此线索树进行中序遍历(不使用栈)。8．校园导航问题
设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。9．马的遍历问题
设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。
要求：依次输出所走过的各位置的坐标。/3
11.设计一个模拟计算器来完成表达式的计算
要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解，操作数可以是多位数。12.八皇后问题
设计程序完成如下要求：在8×8的国际象样棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。
要求：依次输出各种成功的放置方法。13.图的遍历过程演示
设计程序完成如下功能：对给定的图结构和起点，产生深度优先遍历和广度优先遍历序列，并给出求解过程的动态演示。14．构造n个城市连接的最小生成树
一个地区的n个城市间的距离网，用prim算法或kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：
1)城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)15．药店的药品销售统计系统
设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。
基本要求：在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。对各药品的药名、单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序、堆排等方法。
四、上交作业及成绩评定
1、上交要求
上交设计报告和源程序。其中设计报告要以手写报告的形式上交；电子版内容包括程序源码和设计报告的电子文档。整个班级的设计均放在一个文件夹中。
2、课程设计报告注意事项：
1）运行结果请截图（alt+prtsc）；
2)系统功能模块介绍请请采用流程图形式；3）课程设计总结可以从以下几个方面书写:课程设计的收获、遇到问题及其解决过程、程序调试技巧、在课程设计过程中对《数据结构》课程的认识等内容。
3、评分标准
根据完成任务的情况、课程设计报告书的质量和课程设计过程中的工作态度等按照30%、50%、20%加权综合打分。成绩评定实行百分制。上机程序检查未通过者、无设计报告者以及严重抄袭他人设计者，成绩为不及格。
/3
2014/2015学年第一学期
《数据结构与算法课程设计》任务书
一、课程设计目的
数据结构与算法课程设计是《数据结构与算法》课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。
2二、课程设计题目
2.1棋盘覆盖
【间题描述】
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的l型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个l型骨牌不得重叠覆盖。
【基本要求】
（1）输入k以及特殊方格所在的行号dr和特殊方格的列号dc。
1（2）要求输出每一步用什么形态l型骨牌覆盖，覆盖后得到的棋盘图形。（3）如果输出的结果只是用矩阵表示则为良好，用图形表示则为优。【测试数据】【实现提示】
使用分治策略，把棋盘划分成4个小棋盘，然后用一个l型骨牌覆盖将这4个小棋盘变为都具有特殊方格的棋盘。
2.2hanoi塔问题（*）
【问题描述】
设a，b，c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2,,n，要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
规则（1）每次只能移动一个圆盘；
规则（2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上；
规则（3）在满足移动规则（1）和（2）的前提下，可将圆盘移至a，b，c中任一塔座上。
（1）设计出hannoi塔游戏，供用户玩；（2）提供正确的搬运方法。【实现说明】
正确的搬运方法使用递归方法实现。【测试数据】
2.3矩阵连乘问题
给定n个矩阵{a1,a2,...,an},其中ai和ai1是可乘的，i＝1,2,,n-1。考察这n个矩阵的连乘积a1a2,...,an，通过加括号方式，找出矩阵乘积所需的最少计算量的方法。
输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如(a1(a2(a3a4)))。【实现说明】使用动态规划方法。
2.4多边形游戏（*）
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“＋”或“*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。随后n-1步按以下方式操作：
选择一条边e及由e连接着的2个顶点v1和v2；
用一个新的顶点取代边e及用e连接着的2个顶点v1和v2，将由顶点v1和v2的整数值通过边e上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。【基本要求】
设计该游戏供用户玩；
对于给定的多边形，给出最高得分计算。【实现说明】使用动态规划方法。
2.50-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大。
使用动态规划、回溯法以及分支界限三种方法实现。【测试数据】【实现提示】
2.6排序方法
给定n个元素，要求对这n个元素进行排序。【基本要求】
使用多种排序方法，越多越好；
2.7哈夫曼编码译码器
设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件
（压缩文件，）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。
（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；
（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。【实现说明】
（1）在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、5循环单链表、双向链表、循环双链表；
（2）在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；
（3）二叉树本身也可以用静态数组模拟；（4）使用贪心算法
2.8迷宫问题（*）
设计一个迷宫并给出正确走法。如：*********************其中0表示可以走，1表示不能走，每一步只能向上下左右移动。【基本要求】
（1）给出迷宫的正确走法，包括没有解的情况；（2）要求界面友好。【测试数据】
【实现提示】使用回溯的方法。
2.9继续邮资问题
假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。
输入任意的m和n都能设计出最佳的方案，并给出连续邮资区间。【实现说明】【测试数据】
2.10图的m着色问题
给定一个地图，要求给出该地图的最少着色方案【基本要求】
（1）把地图以及最少着色的方案显示出来则为良好。（2）有友好的界面则为优【实现说明】
2.11猜数字游戏（*）
孩子想1个由4种颜色组成的序列（4种颜色不一定完全不同）。每种颜色只能是6种颜色之一。方便起见，我们用数字1到6表示6种颜色。
计算机必须根据孩子的回答找出孩子所想的颜色序列。计算机在屏幕上显示一个序列，孩子用键盘回答以下两个问题：
猜对的颜色中位置不对的有几个？猜对的颜色中位置对的有几个？【基本要求】
编程使至多6次问答后猜出序列，如果办不到，至多10次问答后猜出序列。【实现说明】【测试数据】
如孩子想的是4655计算机猜想颜色对位置错的数目颜色和位置都对的数目12341051562161651156251256531284655042.12大整数计算器
设计一个计算器实现两个任意长得整数的加、减、乘、除。【基本要求】
设计一个实现任意长的整数进行四则运算的演示程序，要求输入任意长的整数进行四则运算，都能得到精确的结果。
【实现说明】
2.13查找搜索技术
给定任意的数组，对于给定的数，查找是否在数组中，如果在，则返回给定数在数组的位置，不在则返回不在信息。
2.14tom,jerry和奶酪（*）
猫tom和鼠jerry同住在一矩阵地窖中。猫要吃鼠，鼠要吃奶酪。地窖中有2种地砖：有洞砖与无洞砖。一个洞足以让鼠钻入，但猫不能。
以菜单形式完成以下任务：
随机地生成一个地窖，并给猫、鼠和奶酪安排一个位置。如：ffffffffffffffffppppppppppppcffhfffffffffffpffpppjhppppppppffpffffffpfffffffpppppppppptppffffffffffffffff其中c表示猫，j表示鼠，h表示洞，f表示不能通行（2）鼠先行，猫后行。两者皆满足以下规定：1）必须上、下、左或右移动2）鼠必须走1步（穿过p或h）3）猫必须走1或2步（穿过p）
（3）当鼠吃到奶酪或猫抓到鼠时，游戏结束。【基本要求】【实现说明】
2.15布线问题
印刷电路板将布线区域划分成n×m个方格阵列，精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿着直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。
【基本要求】（1）解决题目的问题（2）提供友好的界面【实现说明】使用分支限界法。
2.16魔方工具包（*）
一个魔方是一个由3×3×3个小立方体组成的立方体。最初立方体的6个面分别涂上不同颜色，我们称之为“最初魔方”。魔方的每一面上的3×3个小立方体组成它的一层。
魔方所能见到的每一层（6个面）都能旋转90，180，220或360度。所有层的旋转轴都垂直于面且通过其中心。旋转的结果是另一个魔方，它的所有面的颜色都改变了。
现在我们用字符来代替颜色：u=上，d=下，f=前，b=后，l=左，r=右。任何一个序列的旋转都能表示成{u,r,f,b,l,d}中一些字符组成的字符串，其中每个字符表示它所11指定的面顺时针旋转90度。
（1）编程完成以下3个任务（菜单形式），你可以假设任何输入的字串长度都<=35。你的算法能处理非法输入的情况，如：输入输出llllllllllllllll“”(空串llllllllrrrffffrlblllbhello“error”
（2）判断输入的2个字串的旋转结果是否相同。如输入一输入二输出ruurnorrffrrffrrffrrffffrrffrryesrrffrrffrrffrrffrrffrrffno（3）求出输入字符串至少须使用几次才能将魔方转回到“最初魔方”（一定大于0）输入输出l412dd2bulb36ruf80bluff180【实现说明】
2.17图的建立与输出
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果【实现说明】
无
2.18图的建立与输出
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出13图的邻接矩阵。
给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果。【实现说明】
2.19以队列实现的仿真技术预测理发馆的经营状况（*）
理发馆一天的工作过程如下：
1)理发馆有n把理发椅，可同时为n位顾客进行理发。
2)理发师分三个等级（一级、二级、三级），对应不同的服务收费。3)当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。
4)一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。5)若理发馆每天连续营业t分钟，求
（5）统计每天不同级别理发师的创收。
1)模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5节离散事件模拟p65）；
4)某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待；
7)除了输出统计的数据外，还需要显示理发馆的状态，可以采用文本方式（横向显示每张椅编号、理发师级别。纵向表示等待该理发师理发的排队长度）。【实现说明】
2.20防抄袭管理系统（*）
对于给定的文档，如word文档，txt文档等，找出文档的相似度。【基本要求】
（1）要求找出给定的两个文档的相似度以及标出相似的地方（1:1）；（2）要求找出给定的一个文档与给定的文件夹的所有文档的相似度，以及标出相似的地方(1:n)（3）要求找出给定的文件夹下面所有文档的相似度(n:n)。【实现说明】
给定相似文档进行测试。
2.21.设计一个停车场管理系统，模拟停车场的运作
设计要求：通过此程序具备以下功能：
1、要求以栈模拟停车场，以队列模拟车场15外的便道，按照从终端读入的输入数据序列进行模拟管理；
2、要求处理的数据元素包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻；
4、要求栈以顺序结构实现，队列以链表实现。
2.22．赫夫曼编码
题目要求：给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数n（≤10000），即网络中计算机的总台数，因而每台计算机可用1到n之间的一个正整数表示。接下来的几行输入格式为ic1c2或者c或者cc1c2或者s，其中c1和c2是两台计算机的16序号，i表示在c1和c2间输入一条连线，c表示检查c1和c2间是否可以传输文件，s表示该组测试结束。
当n为0时，表示全部测试结束，不要对该数据做任何处理。
输出要求：对每一组c开头的测试，检查c1和c2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。
当读到s时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“thenetworkisconnected.”，否则输出“therearekcomponents.”,其中k是网络中连通集的个数。
两组测试数据之间请输出一空行分隔。
2.24.教学计划编制问题（图的应用）
1、输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。
2、应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
3、若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式可以自己设计。
4、可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。
=============================172.25.药品销售统计系统（排序应用）
设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。【实现提示】
在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：a125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法。
药品信息的元素类型定义：typedefstructnode{charnum[4];/*药品编号*/charname[10];/*药品名称*/floatprice;/*药品单价*/intcount;/*销售数量*/floatsale;/*本药品销售额*/}datatype;存储药品信息的顺序表的定义：typedefstruct{datatyper[maxsize];intlength;}sequenlist;
2.26梯运行仿真程序
[问题描述]办公大楼有若干层（例如，十层），每层有电梯，同时有步行楼梯；
全楼有若干部（例如，不多于10部）电梯同时供使用，电梯容量为24人，速度每上下一层需5秒，在某一层停下至少15秒。其运行状态可分：向上、向下、停止，当前乘客数，当前所在层数。它设有一个“按钮数组”，例如第五层的按钮按下，意味着有乘客在第5层到达目标层，等等。在楼的每一层，有电梯数，有按钮表示有人等待向上或向下，由若干人在等待，有若干电梯在本层停下，等等。
2.27国交通咨询模拟
[问题描述]
[基本要求]
（1）提供对城市信息进行编辑（如：添加或删除）的功能；
（2）城市之间有两种交通工具：火车或飞机，提供对全国城市交通图和列车时刻表及飞机航班表进行编辑的功能。（信息的输入方式可以是文件输入和键盘输入两种方式）
（3）提供两种最优决策：最快到达和最省钱到达。（选作：旅途中转次数最少的最优决策）
（5）咨询以用户和计算机的对话方式进行。
a）由用户输入起始站、终点站、最优决策原则和交通工具；
三、课程设计的基本要求
1．问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？
2．逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。
3．详细设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，20写出数据存储结构的类型定义，写出函数形式的算法框架。
4．程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。
5．程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。
设计最终需提交的内容包括：
a）课程设计报告（1份，a4纸打印，同时包括一份电子版）报告要求版面清晰，格式规范，否则重新编写。报告内容要求包括：
（1）问题的概述、分析及研究意义；（2）数据结构的逻辑设计和物理存储设计；（3）重要算法的设计、流程描述或伪代码描述；
（4）数据结构的时空复杂性分析以及重要算法的复杂性分析；
（5）程序最终实现结果（包括重点结果界面的抓取，能过说明问题的重要实验结果数据的打印或其可视化结果等）。
（6）参考文献（如果需要）。
（7）附录部分附上关键数据结构的定义及关键算法的源代码。
b）完整的程序系统（电子方式提交）
能够对输入产生相应的输出，同时尽量的完成可视化演示。
该部分包括源代码和可执行文件两个部分（提交的时候需清楚的注明个人姓名，班级）。
c）源程序文档（电子方式提交）
源程序代码要求结构清晰、可读性好。应对源程序中的类说明（如果采用面向对象方法设计），函数说明，接口说明，关键变量说明等进行注释；源程序要进行适当的缩进编排。
d）答辩报告（编写powerpoint答辩报告，电子方式提交）要求突出重点，思路清晰。同时就此报告准备答辩。
e）所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用winrar或winzip均21可），压缩后的文件按规定格式进行命名，命名格式为：学号+（）。8．每位同学只能选择一个题目并完成
四、评分标准
1、基本功能：
50分。
通过功能的实现情况、界面的完成情况、软件的实现情况进行评分。
2、设计报告及使用说明书：20分按照报告的要求进行评分。
3、回答问题：
4、平时考勤：
5、核分标准：
15分15分100分
（90~100为优、80~89为良、70~79为中、60~69为及格、，60以下为不及格）
五、参考书目
严蔚敏.《数据结构》（c语言版）.清华大学出版社刘玉龙．《数据结构与算法》.电子工业出版社.严蔚敏等《数据结构题集》（c语言版）.清华大学出版社
徐孝凯.数据结构实用教程（c/c++描述）.北京:清华大学出版社.陈慧南.数据结构（使用c++语言描述）.南京:东南大学出版社.殷人昆,陶永雷,谢若阳等.数据结构（用面向对象方法与c++描述）.北京:清华大学出版社.22
数据结构课程设计任务书
一、《数据结构课程设计》的目标
课程设计是《数据结构》课程的一个重要的实践环节，它可加深学生对该课程所学内容的进一步的理解与巩固，达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，培养基本的对基本数据结构的理解和运用，良好的程序设计方法、提高编码及调试程序技能的能力，为整个专业的学习以及软件设计水平的提高打下良好的基础。
二、设计内容
每位学生可以从《数据结构课程设计备选题目》中选择一个题目自行完成。要求每班中题目不能重复。
三、设计要求
1.学生必须仔细阅读《数据结构课程设计任务书》，认真主动完成课设的要求。有问题及时主动通过各种方式与指导教师联系沟通。
间学生不得缺席。
4、每位学生必须认真、独立完成设计任务，发现抄袭者或雷同者，一律按零分处理。
5、程序设计语言可选择c或c++。
6、程序要正确且具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行，对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。
上交的成果的内容必须由以下三个部分组成，缺一不可。
1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；
2．上交程序的说明文件：（中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；
3．课程设计报告：（保存在word文档中，文件名要求按照“学号_姓名_课程设计报告题目”起名，如文件名为“001_张三_二叉树动态演示”.doc）。报告要求文字工整通顺、图表规范、思路清楚、内容正确。设计报告必须按照规定格式规范，a4纸双面打印、装订。
将以上三个部分放在一个文件夹里，文件夹名要求按照"学号_姓名_课程设计报告题目”.zip命名。每个班将所有学生的文件夹收集起来刻成光盘上交。
成绩按五分制，包括课程设计过程、课程设计结果、课程设计报告三部分。其中：
课程设计过程：20%
包括设计态度（10分）、出勤（10分）
课程设计结果：40%
其中：程序正确性：30分，运行效果：10分，答辩：10分。课程设计报告：40%
其中：正确性：20分，完整性：10分，规范性：10分。
六、设计报告格式
见《数据结构课程设计报告模板》。
《数据结构与算法》课程设计教学大纲（datastructures&algorithms）
一、基本信息
课程编号：e1132107课程类别：学科基础课必修课适用层次：本科
适用专业：计算机科学与技术、网络工程、软件工程等开课学期：3学分：2学分学时：2周考核方式：考查
二、教学目的
数据结构与算法课程设计不仅是数据结构与算法课程的实践教学环节，而且是一门综合性实验项目。通过这个实验，培养学生综合运用数据结构基本知识和程序设计基本知识，解决实际问题，提高程序设计的能力和团队协作精神。
本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
1．学生通过实践掌握线性表、树、图等数据结构的存储结构及算法实现；2．培养学生利用数据结构知识解决实际问题的能力;3．使学生初步具备查阅资料、分析设计、上机实现和书写科技报告的能力。
三、基本要求
1.指导教师要在选题、设计、上机实现等诸环节上投入精力，加强指导、讨论和答疑的力度。尤其在选题上，要充分考虑学生目前所具有的知识水平、掌握的开发工具、以及综合设计能力的现状，使题目取材合理、大小适中、难易适度，使学生在完成设计工作后，能有所收获。2.参加课程设计的学生要珍惜机会、勤奋工作、勇于创新、勇于探索、勇于实践，虚心向指导教师请教，向同学学习，独立完成设计任务。
四、教学内容
1.主要内容：应用所掌握的线性表、树、图等数据结构知识解决实际问题。2.软件开发工具：c/c++、java。
3.课程设计题目：指导教师拟定（参考题目见附录1）
4.具体步骤：指导教师拟定设计题目，学生研究具体问题、进行需求分析、选择合适的数据结构、设计算法、编写并调试代码、书写文档材料、提交设计报告，最后，由指导教师验收并评定成绩。
五、考核方法
学习成绩的评定方式：考查。
课程设计成绩评定=平时出勤（20%）+设计报告（40%）+答辩（40%）通过设计答辩方式，并结合学生的动手能力，独立分析解决问题的能力和创新精神，总结报告和答辩水平以及学习态度综合考评。成绩分为优、良、中、及格和不及格五等。
六、教材与参考资料1.建议教材：
[1]数据结构(c++)版，王红梅、胡明、王涛编著，清华大学出版社，2005.7[2]自编教材
2.建议参考书目：
[1]许卓群，杨冬青，唐世渭，张铭.数据结构与算法.高等教育出版社，2004.7[2]严蔚敏,陈文博.数据结构及应用算法教程.清华大学出版社,2001.2[3]朱晋蜀.数据结构(第一版).成都:电子科技大学出版社,2000.1[4]cliffordr著.张铭，刘晓丹译.数据结构与算法分析.电子工业出版社，1998.8[5]殷人昆等.数据结构（用面向对象方法与c++描述）.清华大学出版社，1999.7[6]fordw.,toppstructureswithc++.清华大学出版社（影印版），1997.3
附录一
参考题目（可分若干组，每个学生选择其中一个题目）
3．使用哈希表技术判断两个源程序的相似性4．以队列实现的仿真技术预测理发馆的经营状况5.某公园导游图
6．用树型结构的搜索算法模拟因特网域名的查询7．管道铺设施工的最佳方案选择8．表达式分析与求值程序9．安排教学计划
10.设计huffman编码器与解码器11．在国际象棋盘上马遍历问题12．八皇后问题13．民航售票系统14．模拟旅馆管理系统中的床位分配和加收15．银行业务活动的模拟
16．文字统计系统—文字研究助手17．修道士野人问题18．考试问题
19．计算机辅助考核系统20．学籍管理系统
注：学生可以自选题目或选择指导老师拟定的题目。
附录二
开发步骤
1.分析题目的要求、目的；2.选择适当的数据结构；
3.抽象数据类型的设计；4.抽象数据类型的实现；5.编写代码、上机调试；6.总结验收、评价。
附录三报告书写格式
1．问题描述
题目内容、基本要求2．需求分析
软件的基本功能、输入/输出形式、测试数据要求3．概要设计
所需的adt及作用、主程序流程及模块调用关系4．详细设计
实现概要设计的数据类型、每个操作的伪码算法、主程序和其它模块的伪码算法、函数调用关系图5．编码与调试分析
编码与调试过程中遇到的问题及解决的办法，还存在哪些没有解决的问题？6．使用说明
简要说明程序运行操作步骤7．测试结果
8．课程设计心得体会
数据结构与算法课程设计题目
1．成绩管理
问题描述：给出n个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数
学、英语、物理），设计一个简单的成绩管理程序。
基本要求：
（1）建立成绩表，能够插入、删除、修改学生的成绩记录；（2）按任一单科成绩排序；(3)计算每名学生的平均成绩；
(4)统计任一单科成绩不及格的学生人数,输出不及格人数及不及格的学生名单(5)根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。
(6)成绩表保存在文件中,可以从文件读取数据。
测试数据：学生可以根据自己班级的考试成绩单，任意截取一部分做为测试数据2．一元多项式简单计算
问题描述：设计一个简单一元多项式计算器。基本要求：(1)输入并建立多项式；(2)输出多项式；
(3)两个多项式相加，输出结果多项式；(4)两个多项式相减，输出结果多项式。
提高要求：可以根据输入变量的值，计算出多项式的结果，且算法的效率高。测试数据：可任意选取两个一元多项式，可以是一般的多项式，也可以是稀疏多项式。3．舞伴问题
问题描述：一班有m个女生、n个男生(m不等于n),举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。
基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。
测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据提高要求：计算出任意一位男生(编号为x)和任意一位女生(编号为y),在第k曲配对跳舞的情况。
4．文学研究助手（*）
问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。基本要求：英文小说存于一个文本文件中，待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计,结果保存到文件中。
提高要求：模式匹配选取kmp算法
测试数据：以你的c/c++/java源程序模拟英文小说，相应语言的保留字集作为待统计的词汇集。
5．哈希表的设计与实现（*）
6．管道铺设施工的最佳方案（*）
问题描述:需要在某个城市的n个小区铺设管道，则在这n个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。
基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道,使总投资最小。图的信息输入一次后,保存到文件中,选择的n-1条管道输出到显示器的同时,也保存于文件中。
测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。提高要求：显示原始图及选择n-1条管道后的图。
7．安排教学计划（**）
基本要求：输入参数包括学期总数，一学期的学分上限，每门课程的课程号、学分和直接先修课的课程号；允许两种策略，一是使学生在各学期的学习负担尽量均匀，二是使课程尽量集中在前几个学期；若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定,可以从键盘读取数据也可以从文件读取数据,结果保存到文件中。
测试数据：学期总数为6，学分上限为10，该专业共开设12门。以08级某专业必修课与选修课为例，选择12门课程及相应学分，制定一个表明各门课程先后约束关系的有向图。
测试数据：设输入数据为：（‘a’，1，5），（‘a’，2，10），（‘d’，1，15），（‘a’，3，20），（‘a’，4，25），（‘a’，5，30），（‘d’，2，35），（‘d’，4，40），（‘e’，0，0）。其中，‘a’表示到达；‘d’表示离去，‘e’表示输入结束。
提高要求：设停车场有南、北两个门，每个门都可以进、出车辆。9．计算表达式的值(**)问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。
基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。
测试数据：任意选取一个符合题目要求的表达式。提高要求：（1）对于表达式中的简单错误，能够给出提示；
（2）表达式中可以包括单个字母表示的变量。
10．设计huffman编码器与解码器（***）
基本要求：根据某字符文件统计字符出现频度，构造huffman树，编制huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）测试数据：英文文件。
提高要求：用二进制表示编码，生成二进制的编码文件。11．银行业务模拟（***）
问题描述：对于两个c++语言的源程序代码，用哈希表的方法分别统计两个程序中使用c++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。
基本要求：建立c++语言关键字的哈希表，统计在每个源程序中c++关键字出现的频度,得到两个向量x1和x2，通过计算向量x1和x2的相对距离来判断两个源程序的相似性。
例如:关键字voidintforcharifelsewhiledobreakclass程序1关键字频度4304307002程序2关键字频度4205405201x1=[4,3,0,4,3,0,7,0,0,2]x2=[4,2,0,5,4,0,5,2,0,1]设s是向量x1和x2的相对距离，s=sqrt(∑(xi1-xi2)2)，当x1=x2时，s=0,反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。
测试数据:选择若干组编译和运行都无误的c++程序，程序之间有相近的和差别大的，用上述方法求s,对比两个程序的相似性。
提高要求：建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。
13．小型文本编辑器
问题描述：设计一个行编辑程序，使其具有通常行编辑器(如vi、edlin)应具备的基本功能。
基本要求：编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数，统计行数等功能，对于超过一屏的长文件，应能够分页显示，查找功能用字符串匹配算法实现。设计用户接口命令，实现对文本的编辑。具体的编辑命令，可参考数据结构算法网络教学平台上提供的edlin、vi的命令集。
测试数据：任一文本文件。
提高要求：１.可以支持“*”、“”等通配符；
２.支持复制、粘贴等功能
3.支持多文档同时编辑；
提示：可以考虑用双向链表实现，每一结点表示一行字符，注意每行字符不能超过255。14．小型英汉词典
问题描述：设计一个英汉词典，支持member(查找)、insert(插入)、delete(删除)操作。
基本要求：实现字典的常用方法有：有序线性表（memeber用二分检索实现）、avl树（二叉搜索树）、patriciatrie、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。
提示：字典可以自己建立，但必须按字母a~z建立26个文件，建议从网上下载，文件类型为txt。
备注：
1.每道题目后面的*号，表示题目的难度系数；对应的评定成绩等级为及格（无*号）、中等（*号）、良好（**号）、优秀（***号），学生完成题目的基本要求，即可得到程序设计部分的相应等级成绩，完成题目提高要求，成绩可以向上浮动，如果没有完成基本要求，成绩向下浮动，直至不及格。
2.所有题目均需用c++完成，不能用c或mfc。3.实验班的学生原则上应选择“*”号多的题目。4.每道题的选题人数不能超过3人