数据结构实验题目

《数据结构实验题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京邮电大学计算机中心实验一线性表1实验目的通过选择下面四个题目之一进行实现，掌握如下内容：Ø熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法Ø学习指针、模板类、异常处理的使用Ø掌握线性表的操作的实现方法Ø学习使用线性表解决实际问题的能力2实验内容2.1题目1根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长

2、度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。2.2题目2利用线性表实现一个通讯录管理，通信录的数据格式如下：第10页北京邮电大学计算机中心structDataType{intID;//编号charname[10];//姓名charch;//性别charphone[13];//电话charaddr[31];//地址};要求：Ø实现通讯录的建立、增加、删除、修改、查询等功能Ø能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。Ø能够保存每次更新的数据（选作）Ø能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）Ø编写测试main()函数测

3、试线性表的正确性2.3题目3利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+…+anxn提示：Polynomial的结点结构如下：structterm{floatcoef;//系数intexpn;//指数};可以使用链表实现，也可以使用顺序表实现。要求：Ø能够实现一元多项式的输入和输出Ø能够进行一元多项式相加Ø能够进行一元多项式相减Ø能够计算一元多项式在x处的值Ø能够计算一元多项式的导数（选作）Ø能够进行一元多项式相乘（选作）第10页北京邮电大学计算机中心Ø编写测试main()函数测试线性表的正确性2.4题目4利用循环链表实现约瑟夫问题的求

4、解。约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。3代码要求1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：Ø代码段与段之间要有空行和缩近Ø标识符名称应该与其代表的意义一致Ø函数名之前应该添加注释说明该函数的功能Ø关键代码应说明其功能第10页北京邮电大学计算机中心实验二栈和队列1实验目的通过选择下面五个题目之一进行实现，掌握如下内容：Ø进一步掌握指针、模板类、异常处

5、理的使用Ø掌握栈的操作的实现方法Ø掌握队列的操作的实现方法Ø学习使用栈解决实际问题的能力Ø学习使用队列解决实际问题的能力2实验内容2.1题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。2.2题目2利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非

6、递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上第10页北京邮电大学计算机中心2.3题目3利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。提示：1、可以使用递归或非递归两种方法实现2、老鼠能够记住已经走过的路，不会反复走重复的路径3、可以自己任意设置迷宫的大小和障碍4、使用“穷举求解”的方法2.4题目4设计一个算术四则运算表达式求值的简单计算器。表达

7、式求值是程序设计语言编译中最近本的问题，它要求把一个表达式翻译成能够直接求值的序列。基本要求：1、输入中缀表达式能够转化成后缀表达式，比如输入中缀表达式“(A+B)*C”，输出“AB+C*”2、操作数使用单字母变量A、B、C等表示，操作符仅为+、-、*、/、（和）；3、能够对变量A、B、C等赋值，得出正确的计算结果2.5题目5利用队列结构实现车厢重排问题。车厢重排问题如下：第10页北京邮电大学计算机中心一列货车共有n节车厢，每个车厢都有自己的编号，编号范围