数据结构课程设计内容.doc

《数据结构课程设计内容.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计内容.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构课程设计内容实验一 线性表的应用（从下面4道题中任选1题完成）实验一（1） 一元稀疏多项式计算器问题描述设计一个一元稀疏多项式的简单计算器。基本要求一元稀疏多项式的简单计算器的基本功能是“（1） 输入并建立多项式；（2） 输出多项式，输出形式为整数序列：，其中n是多项式的项数，和分别是第i项的系数和指数，序列按指数降序排列；（3） 多项式a和b相加，建立多项式a+b；（4） 多项式a和b相减，建立多项式a-b；（5） 多项式a和b相乘，建立多项式a*b（6） 计算多项式在x处的值；（7） 求多项式a的导数；（8） 多项式的输出形式为类数学表达式。例如，多项式的输出形式为，注意系数值为1

2、的非零次项的输出形式中略去系数1，如项的输出形式为，项的输出形式为。（9） 计算器的仿真界面。测试数据（1）（2）（3）（4）（5）（6）（7）（8）互换上述测试数据中的前后两个多项式，再测试一次。实现提示用带头结点的单链表存储多项式。实验一（2） 长整数运算问题描述设计一个程序实现两个任意长的整数求和运算。基本要求利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据（1） 0；0；应输出“0”。（2） -2345,6789；-7654,3211；应输出“-

3、1,0000,0000”。（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。（4） 1,0001,0001；-1,0001,0001；应输出“0”。（5） 1,0001,0001；-1,0001,0000；应输出“1”。实现提示（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表现为万进制数。（2） 可以利用头结点数据域的符号代表长整数的符号

4、。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。选作内容修改上述程序，使它在整型量范围是-（2n-1）（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。实验一（3） 停车场管理问题描述设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上

5、的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不

6、收费）。栈以顺序结构实现，队列以链表实现。测试数据设n=2,输入数据为：（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表示输入结束。 实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容（1） 两个栈共享空间，思考应开辟数组的空间是多少？（2） 汽车可有不同种类，则它们的占地面积不同，收费标

7、准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3） 汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。实验一(4) 迷宫求解问题描述以一个m*n的长方阵表示迷宫，和分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。程序功能有三（）创建迷宫；（）求解迷宫；（）输出迷宫的解。基本要求首先实现一个顺序储存的栈类型，然后编写一个求解迷宫问题的非递归程序。求得的通

8、路以二元组(i,j)的形式输出，(i,j)是指迷宫中的一个坐标。如对于下列数据的迷宫，输出的一条通路为：(1,1),(1,2),(2,2),(3,2),(3,1),(4,1),(5,1),(5,2),(5,3),(6,3),(6,4),(6,5),(5,5),(4,5),(4,6),(5,6),(5,7),(6,7),(7,7),(8,7),(9,7),(9,8).测试数据迷宫的测试数据如下：左上角(1,1)为入口，右下角(9,8)为出口。001000100010001000001101011100100001000001000101011110011100010111000000实现提示计算

9、机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一方向进行探索（探索的方向顺序依次为向上，向右，向下，向左），若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探测到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设入口点的坐标为(1,1)，出口点的坐标为(m,n)，当然也可以任意设定。为处理方便起见，可在迷宫的周围加一圈障碍。求解迷宫中一条通路可采用下面算法：设定当前位置的初值为入口位置；do若当前位置可通，则将当前位置入栈；/纳入路径若该位置是出口位置，则结束；/求得路径存放在栈中否则切换当前位置的上

10、方位置为新的当前位置；否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为烟着顺时针方向旋转找到的栈顶位置的下一个相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/后退一步，从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；while(栈不空)栈空说明没有路径存在实验二 二叉树的应用 （表达式类型的实现）问题描述一个表达式和一棵二叉树之间存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的处理操作。基本要求假设算术表达式Expression内可以含有变量(az)、常量(09)和二元运算符(+,-,*,/,(乘方)。实

11、现以下操作：（） ReadExpr(E)以字符序列的形式输入语法正确的前缀表达式并构造表达式。（） WriteExpr(E)用带括号的中缀表达式输出表达式。（） Asssign(V,c)实现对变量的赋值（V=c），变量的初值为。（） Value(E)对算术表达式求值。（） CompoundExpr(P,E1,E2)构造一个新的复合表达式(E1)P(E2)。测试数据（） 分别输入0;a;-91;+a*bc;+*5x2*8x;+*3x3*2x2x6并输出（） 每当读入一个表达式后，对其中的变量赋值，然后对表达式求值。实现提示（） 在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理以

12、及相应的运算。（） 在识别运算数的同时，要将其字符形式转换为整数形式。（） 用后根遍历的次序对表达式求值。（） 用中缀表示输出表达式时，适当添加括号，以正确反映运算的优先次序。实验三排序和查找的应用 （哈希表设计）问题描述针对你所在的班级中的“人名”设计一个哈希表，完成相应的建表和查表程序。基本要求假设人名为中国人姓名的汉语拼音形式，待填入哈希表的人名共60人，放在一个数据文件上。哈希函数用对应人名编码除留余数法，解决冲突的方法用线性探测。测试数据取08信管本班级的全体同学选作内容（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大

13、的名字集合作实验）。（2） 研究这60个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。附 课程设计报告的规范课程设计报告要求规范书写。应当包括如下八个部分：1. 问题描述：描述要求编程解决的问题。2. 基本要求：给出程序要达到的具体的要求。3. 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。4. 算法思想：描述解决相应问题算法的设计思想。5. 模块划分：描述所设计程序的各个模块（即函数）功能。6. 数据结构：给出所使用的基本抽象数据类型,以及新定义的抽象数据类型。7. 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。8. 测试情况：给出程序的测试情况，并分析运行结果。