《数据结构与算法》课程设计题⽬及要求
北⽅民族⼤学课程设
计
课程名称: 数据结构与算法
院(部)名称：信息与计算科学学院
组长姓名学号
同组⼈员姓名
指导教师姓名：纪峰
设计时间:2010.6.7----2009.6.27
⼀、《数据结构与算法》课程设计参考题⽬
（⼀）参考题⽬⼀（每位同学选作⼀个，同组⼈员不得重复）
1、编写函数实现顺序表的建⽴、查、插⼊、删除运算。
2、编写函数分别实现单链表的建⽴、查、插⼊、删除、逆置算法。
3、编写函数实现双向链表的建⽴、插⼊、删除算法。
4、编写函数实现顺序栈的进栈、退栈、取栈顶的算法。
5、编写函数实现链栈的进栈、退栈、取栈顶的算法。
二叉树中序遍历非递归算法6、编写函数实现双向顺序栈的判空、进栈、出栈算法。
7、编写函数实现循环队列的判队空、取队头元素、⼊队、出队算法。
8、编写函数实现链环队列的判队空、取队头节点、⼊队、出队算法。
9、编写函数实现串的，求串长、连接、求字串、插⼊、删除等运算。
10、分别实现顺序串和链串的模式匹配运算。
11、实现⼆叉树的建⽴，前序递归遍历和⾮递归遍历算法。
12、实现⼆叉树的建⽴，中序递归遍历和⾮递归遍历算法。
13、实现⼆叉树的建⽴，后序递归遍历和⾮递归遍历算法。
14、实现⼆叉树的中序线索化，查*p结点中序下的前驱和后继结点。
15、分别以临接表和邻接矩阵作为存储就够实现图的深度优先搜索和⼴度优先搜索算法。
16、利⽤线性探测处理冲突的⽅法实现散列表的查和插⼊算法。
(⼆)参考题⽬⼆（每三⼈⼀组，任选三个题⽬完成）
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.飞机订票系统
任务：通过此系统可以实现如下功能：
录⼊：
可以录⼊航班情况（数据可以存储在⼀个数据⽂件中，数据结构、具体数据⾃定）查询：
可以查询某个航线的情况（如，输⼊航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输⼊起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在⼀个数据⽂件中，结构⾃⼰设定）
可以订票，如果该航班已经⽆票，可以提供相关可选择航班；
退票：可退票，退票后修改相关数据⽂件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：
当航班信息改变可以修改航班数据⽂件
要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
3.⽂章编辑
功能：输⼊⼀页⽂字，程序可以统计出⽂字、数字、空格的个数。
静态存储⼀页⽂章，每⾏最多不超过80个字符，共N⾏；要求（1）分别统计出其中英⽂字母数和空格数及整篇⽂章总字数；（2）统计某⼀字符串在⽂章中出现的次数，并输出该次数；（3）删除某⼀⼦串，并将后⾯的字符前移。
存储结构使⽤线性表，分别⽤⼏个⼦函数实现相应的功能；
输⼊数据的形式和范围：可以输⼊⼤写、⼩写的英⽂字母、任何数字及标点符号。
输出形式：（1）分⾏输出⽤户输⼊的各⾏字符；（2）分4⾏输出"全部字母数"、"数字个数"、"空格个数
"、"⽂章总字数"（3）输出删除某⼀字符串后的⽂章；
4.宿舍管理查询软件
1)任务：为宿舍管理⼈员编写⼀个宿舍管理查询软件, 程序设计要求：
A.采⽤交互⼯作⽅式
B.建⽴数据⽂件，数据⽂件按关键字（姓名、学号、房号）进⾏排序(冒泡、选择、插⼊排序等任选⼀种)
2)查询菜单: (⽤⼆分查实现以下操作)
A.按姓名查询
B.按学号查询
C.按房号查询
3)打印任⼀查询结果（可以连续操作）
5.校园导航问题（限1 ⼈完成）
设计要求：设计你的学校的平⾯图，⾄少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，出从任意场所到达另⼀场所的最佳路径。
6.教学计划编制问题
设计要求：针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满⾜各学期课程数⽬⼤致相同。
7.散列法的实验研究
散列法中，散列函数构造⽅法多种多样，同时对于同⼀散列函数解决冲突的⽅法也可以不同。两者是影响查询算法性能的关键因素。对于⼏种典型的散列函数构造⽅法，做实验观察，不同的解决冲突⽅法对查询性能的影响。
8.图书借阅管理系统
主要分为两⼤功能：
1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)；
2)会员管理(增加会员、查询会员、删除会员、借书信息)；
9.学⽣成绩管
实现功能：输⼊、输出、插⼊、删除、查、追加、读⼊、显⽰、保存、拷贝、排序、退出。
10.活期储蓄帐⽬管理
活期储蓄处理中，储户开户、销户、存⼊、⽀出活动频繁，系统设计要求：
1)能⽐较迅速地到储户的帐户，以实现存款、取款记账；
2)能⽐较简单，迅速地实现插⼊和删除，以实现开户和销户的需要。
11.⼆叉排序树的实现
⽤顺序和⼆叉链表作存储结构
1)以回车('\n')为输⼊结束标志，输⼊数列L，⽣成⼀棵⼆叉排序树T；
2)对⼆叉排序树T作中序遍历，输出结果；
3)输⼊元素x，查⼆叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执⾏操作2)；否则输出信息“⽆x”；
12.最⼩⽣成树问题
设计要求：在n个城市之间建设⽹络，只需保证连通即可，求最经济的架设⽅法。存储结构采⽤多种。求解算法多种。
13.通讯录的制作
设计⽬的：⽤〈〈数据结构〉〉中的双向链表作数据结构，结合C语⾔基本知识。编写⼀个通讯录管理系统。以把所学数据结构知识应⽤到实际软件开发中去。
设计内容：本系统应完成⼀下⼏⽅⾯的功能：
1)输⼊信息——enter();
2)显⽰信息———display( );
3)查以姓名作为关键字———search( );
4)删除信息———delete( );
5)存盘———save ( );
6)装⼊———load( ) ;
设计要求：
1)每条信息⾄包含：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）⼏项
2)作为⼀个完整的系统，应具有友好的界⾯和较强的容错能⼒
3)上机能正常运⾏，并写出课程设计报告
14.哈夫曼编码/译码器
【问题描述】
设计⼀个利⽤哈夫曼算法的编码和译码系统，重复地显⽰并处理以下项⽬，直到选择退出为⽌。
【基本要求】
1)将权值数据存放在数据⽂件(⽂件名为，位于执⾏程序的当前⽬录中)
2)分别采⽤动态和静态存储结构
3)初始化：键盘输⼊字符集⼤⼩n、n个字符和n个权值，建⽴哈夫曼树；
4)编码：利⽤建好的哈夫曼树⽣成哈夫曼编码；
5)输出编码；
6)设字符集及频度如下表：
字符空格 A B C D E F G H I J K L M
频度186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符N O P Q R S T U V W X Y Z
频度57 63 15 1 48 51 80 23 8 18 1 16 1
【进⼀步完成内容】
1)译码功能；
2)显⽰哈夫曼树；
3)界⾯设计的优化。
15.图书管理系统
【问题描述】
设计⼀个计算机管理系统完成图书管理基本业务。
【基本要求】
1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；
2)对书号建⽴索引表（线性表）以提⾼查效率；
3)系统主要功能如下：
*采编⼊库：新购⼀种书，确定书号后，登记到图书帐⽬表中，如果表中已有，则只将库存量增加；
*借阅：如果⼀种书的现存量⼤于0，则借出⼀本，登记借阅者的书证号和归还期限，改变现存量；
*归还：注销对借阅者的登记，改变该书的现存量。
【进⼀步完成内容】
1)系统功能的进⼀步完善；
2)索引表采⽤树表。
3)设计内容
4)程序流程图
5)源程序
6)软件测试报告（包括所⽤到的数据及结果）
16.散列表的设计与实现
【问题描述】
设计散列表实现电话号码查系统。
【基本要求】
1)设每个记录有下列数据项：电话号码、⽤户名、地址；
2)从键盘输⼊各记录，分别以电话号码和⽤户名为关键字建⽴散列表；
3)采⽤⼀定的⽅法解决冲突；
4)查并显⽰给定电话号码的记录；
5)查并显⽰给定⽤户名的记录。
【进⼀步完成内容】
1)系统功能的完善；
2)设计不同的散列函数，⽐较冲突率；
3)在散列函数确定的前提下，尝试各种不同类型处理冲突的⽅法，考察平均查长度的变化。
17.顺序结构、动态链表结构下的⼀元多项式的加法、减法、乘法的实现。
设有⼀元多项式A m(x)和B n(x).
A m(x)=A0+A1x1+A2x2+A3x3+… +A m x m
B n(x)=B0+B1x1+B2x2+B3x3+… +B n x n
请实现求M(x)= A m(x)+B n(x)、M(x)= A m(x)-B n(x)和M(x)= A m(x)×B n(x)。
要求：
1)⾸先判定多项式是否稀疏
2)分别采⽤顺序和动态存储结构实现；
3)结果M(x)中⽆重复阶项和⽆零系数项；
4)要求输出结果的升幂和降幂两种排列情况
18.简易⽂本编辑器
要求：
1)具有图形菜单界⾯；
2)查，替换（等长，不等长），插⼊（插串，⽂本块的插⼊）、块移动（⾏块，列块
移动），删除

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。