北邮数据结构实验题目

实验一 线性表

1 实验目的

通过选择下面四个题目之一进行实现，掌握如下内容：

? 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 ? 学习指针、模板类、异常处理的使用 ? 掌握线性表的操作的实现方法 ? 学习使用线性表解决实际问题的能力

2 实验内容

2.1题目1

根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：

1、 带头结点的单链表 2、 不带头结点的单链表 3、 循环链表 4、 双链表 5、 静态链表

线性表的基本功能：

1、构造：使用头插法、尾插法两种方法

2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁

7、其他：可自行定义

编写测试main()函数测试线性表的正确性。

2.2题目2

利用线性表实现一个通讯录管理，通信录的数据格式如下：

struct DataType {

int ID; char ch;

//编号 //姓名 //性别 //电话 //地址

char name[10];

};

char phone[13]; char addr[31];

要求：

? 实现通讯录的建立、增加、删除、修改、查询等功能

? 能够实现简单的菜单交互，即可以根据用户输入的命令，选择不

同的操作。

? 能够保存每次更新的数据（选作）

? 能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作） ? 编写测试main()函数测试线性表的正确性

2.3题目3

利用线性表实现一个一元多项式Polynomial

f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn

提示：

Polynomial的结点结构如下： struct term {

float coef; //系数 int expn; //指数 };

可以使用链表实现，也可以使用顺序表实现。

要求：

? 能够实现一元多项式的输入和输出 ? 能够进行一元多项式相加 ? 能够进行一元多项式相减 ? 能够计算一元多项式在x处的值 ? 能够计算一元多项式的导数（选作） ? 能够进行一元多项式相乘（选作）

? 编写测试main()函数测试线性表的正确性

2.4题目4

利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。

2.5题目5

动态内存管理是操作系统的基本功能之一，用于响应用户程序对内存的申请和释放请求。初始化时，系统只有一块连续的空闲内存；然后，当不断有用户申请内存时，系统会根据某种策略选择一块合适的连续内存供用户程序使用；当用户程序释放内存时，系统将其回收，供以后重新分配，释放时需要计算该内存块的左右是否也为空闲块，若是，则需要合并变成更大的空闲块。

试设计用于模拟动态内存管理的内存池类。 基本要求：

? 实现内存池MemoryPool(int size)的初始化 ? 实现Allocate(int size)接口 ? 实现Free(void *p)接口 ? 实现内存池的析构

? 在分配内存空间时，可选择不同的内存分配策略：最佳拟合策略、

最差拟合策略或最先拟合策略。实现其中至少两种分配策略。

编写测试main()函数对类中各个接口和各种分配策略进行测试，并实时显示内存池中的占用块和空闲块的变化情况。

3代码要求

1、必须要有异常处理，比如删除空链表时需要抛出异常；

2、保持良好的编程的风格：

? 代码段与段之间要有空行和缩近 ? 标识符名称应该与其代表的意义一致 ? 函数名之前应该添加注释说明该函数的功能 ? 关键代码应说明其功能

实验二 扩展线性表

1 实验目的

通过选择下面五个题目之一进行实现，掌握如下内容： ? 进一步掌握指针、模板类、异常处理的使用 ? 掌握栈的操作的实现方法 ? 掌握队列的操作的实现方法 ? 学习使用栈解决实际问题的能力 ? 学习使用队列解决实际问题的能力

2 实验内容

2.1题目1

利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。

提示：

1、可以使用递归或非递归两种方法实现

2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上

2.2题目2

利用栈结构实现迷宫求解问题。迷宫求解问题如下：

心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。

提示：

1、可以使用递归或非递归两种方法实现

2、老鼠能够记住已经走过的路，不会反复走重复的路径 3、可以自己任意设置迷宫的大小和障碍 4、使用“穷举求解”的方法