2017-数据结构课程设计.doc

数据结构A课程设计题目 1、题目一 集合的并、交和差运算 【问题描述】 编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】 集合的元素限自行定义。 演示程序以用户和计算机的对话方式执行。 【测试数据】 自行建立。 【实现提示】 无。 【选做内容】 集合的元素判定和子集判定运算。 求集合的补集。 集合的混合运算表达式求解。 集合的元素类型推广到其他类型，甚至任一类型。 2、 题目二 算术表达式计算 【问题描述】 表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 【基本要求】 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用运算符优先关系，实现对算术四则混合运算表达式的求值。 【测试数据】 （1）能够判断表达式中的括号是否匹配，测试的表达式中括号不匹配，可以重新输入。 （2）能够处理多位整数以及浮点数。 （3）具体测试数据自定义。 【实现提示】 设置运算符栈和运算数栈辅助分析算符优先关系；在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算；在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作等内容。 【选做内容】 扩充运算符集，如增加乘方、单目减、赋值等运算。 3、题目三 贪吃蛇游戏开发 【问题描述】 贪吃蛇游戏是一个深受人们喜欢的游戏，编程实现该游戏。 【基本要求】 一条蛇在密闭的围墙内，在围墙内随机出现一个食物，通过键盘上的四个光标键控制蛇向上下左右四个方向移动，蛇头撞到食物，则表示食物被吃掉，这时蛇的身体长一节，同时计1分；接着又出现食物，等待被蛇吃掉，如果蛇在移动过程中，撞到墙壁或身体交叉（蛇头撞到自己的身体）游戏结束。 【测试数据】 自定义。 【实现提示】 （1）围墙区域可以用二维数组实现； （2）食物随机产生； （3）蛇的身体使用链表； （4）蛇的游动采用插入头结点，删除尾结点的方法实现。 【选做内容】 可以根据情况，自行添加完善。 4、题目四 航空订票模拟 【问题描述】 航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。设计一个航空订票模拟程序，以使上述业务可以借助计算机来完成。（难度系数：0.73） 【基本要求】 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几）、乘员定额、余票量、订票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。 系统能实现的操作和功能如下： 查询航线：根据旅客提供的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额。 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若为满员或余票额少于订票额，则须重新询问客户要求。若需要，可登记排队候补。 承办退票业务：根据客户提供的要求（日期、航班），为客户办理退票手续，然后查询该航班是否排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。 【测试数据】 自行建立。 【实现提示】 两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登陆在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。 【选做内容】 当客户订票要求不能满足时，系统可向客户提供到达同一目的的其他航线情况。读者还可充分发挥自己的想象力，增加系统的功能和其他服务项目。 5、题目五 哈希查找 【问题描述】 若要在n个城市间建设通信网路，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。（难度系数：0.78） 【基本要求】 利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。 以文本形式输出生成树中各条边以及他们的权值。 【测试数据】 自行建立。 【实现提示】 通信线路一旦建立，必然是双向的。因此，构造最小生产树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用随机数函数产生。 【选做内容】 利用堆排序选择实现权值最小的边。 6、题目六 哈夫曼编/译码器设计 【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接