2013计算机信息管理信息安全数字媒体网络工程数据结构实验教案

实验教案 实验一 栈和队列的应用 难点： 1. 掌握STL中栈的使用 2. 具体编程自己实现栈和队列 重点： 1. 掌握STL中栈的使用很重要，掌握了STL中栈的使用，就可以举一反三，掌握STL中队列的使用，能为后序的实验打下基础。 2. 理解栈的基本原理，自己编程实现栈中的几个基本函数 3. 理解队列的基本原理

详细讲述见下： 1、介绍STL中栈的使用， 如下是从帮助文档中copy的代码 #pragma warning(disable:4786) #include #include

using namespace std ; typedef stack STACK_INT; int main() { STACK_INT stack1;

cout << "stack1.empty() returned " << (stack1.empty()? "true": "false") << endl; // Function 3

cout << "stack1.push(2)" << endl; stack1.push(2);

if (!stack1.empty()) // Function 3 cout << "stack1.top() returned " << stack1.top() << endl; // Function 1

cout << "stack1.push(5)" << endl; stack1.push(5);

if (!stack1.empty()) // Function 3 cout << "stack1.top() returned " << stack1.top() << endl; // Function 1

cout << "stack1.push(11)" << endl; stack1.push(11);

if (!stack1.empty()) // Function 3 cout << "stack1.top() returned " << stack1.top() << endl; // Function 1

// Modify the top item. Set it to 6. if (!stack1.empty()) { // Function 3 cout << "stack1.top()=6;" << endl; stack1.top()=6; // Function 1 }

// Repeat until stack is empty while (!stack1.empty()) { // Function 3 const int& t=stack1.top(); // Function 2 cout << "stack1.top() returned " << t << endl; cout << "stack1.pop()" << endl; stack1.pop(); } }

运行结果： stack1.empty() returned true stack1.push(2) stack1.top() returned 2 stack1.push(5) stack1.top() returned 5 stack1.push(11) stack1.top() returned 11 stack1.top()=6; stack1.top() returned 6 stack1.pop() stack1.top() returned 5 stack1.pop() stack1.top() returned 2 stack1.pop()

2、自己编写的栈注意事项 自己编写的栈可以使用数组实现也可以使用链表实现，可以用C或者C＋＋描述，但是必须具有栈的基本功能，即必须具有栈的一些基本函数。对照STL的栈，其基本应该具有的函数是push，pop，top，empty，如果是数组实现的栈还需要判断栈是否满。

3、使用自己编写的栈实现序列反转 如果要使用自己编写的栈实现序列反转，一定要注意，自己写的函数可能原型跟STL中的不一样，因此，需要在主函数调用的时候，根据函数的具体写法具体调用，不能够直接复制原有的使用STL中栈进行序列反转的代码，否则编译可能不能通过。

4、队列的实现和使用 这里，自己实现的队列也是可以是通过数组实现一个循环队列或者用链表实现。队列实现好后，自己再写一个主函数进行测试。一般队列需要具有的基本函数，比如出队，入队，判断队列是否为空，取队首元素这些都需要具备。 实验教案 实验二 多项式的加减法 难点： 1. 多项式的表示 2. 如何读入多项式到适当的数据结构中 3. 如何显示多项式 重点： 编程实现多项式的加减法

详细讲解如下： 1、存储多项式的数据结构 本实验中并没有规定多项式该用什么样的数据结构表示。一个多项式可以使用一个链表表示，也可以用一个队列表示一个多项式等等，完全可以由大家设计合理的数据结构存放多项式。

2、用链表表示多项式 如果先择用链表表示多项式，需要考虑 （1）多项式的读取 用户输入多项式是按照降幂或者升幂的方式输入，还是不按照幂的升高或降低排列，随意输入的？如果是随意输入，则在进行多项式加减法的时候需要进行更多的处理，比如进行运算前，必须先排序等等处理方法。

（2）链表的构造 详细情况见发放的c语言实验教案中的链表一项。

3、用队列表示多项式 如果用队列表示多项式，也需要注意，一个队列对应一个多项式。队列中的一项是多项式中的一项，队列中的元素也是经过降幂或者升幂排练的。 如果使用STL中的队列也是可以的。 实验教案 实验三 迷宫 重点： 一些数据结构的设计，如何更好的根据算法设计数据结构。 难点： 1. 根据算法，设计相应的数据结构，以便于程序的编写。比如需要理解为什么迷宫用二维数组表示且该二维数组的维数大于实际的迷宫大小 2. 弄清回溯算法求解迷宫路径的非递归方法 3. 理解迷宫中行走方向，要求8个方向。理解栈在求解该迷宫非递归算法中的作用，以及需要将什么内容放入栈中。

具体讲解如下： 本实验主要是设计走迷宫算法，可以用递归和非递归两种方式完成 实验题目中详细讲述的算法是非递归算法，用栈为辅助的数据结构。这里可以使用标准模板库中的stack

1.走迷宫非递归算法的设计实现 这个算法在实验指导书中有详细的介绍，下面简单总结一下 （1）数据结构：  用二维数组MAZE[m+2][n+2]表示迷宫的结构，数组中的值为1表示是墙，为0表示可以走通。（用MAZE[m+2][n+2]而不用MAZE[m][n]的原因在于想表示和编写代码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去）  用二维数组MARK[m+2][n+2]表示迷宫是否被走过，主要是为了回溯时已经证明走不通的路线就不要再去走了。（用MARK[m+2][n+2]而不用MARK[m][n]的原因在于想表示和编写代码的时候简单些）  二维数据MOVE[8][2]是为了更方便的移动到下一步，改变坐标。这个二维数组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路  用栈保存走过的路径 （2）输出：  迷宫布局，用0表示可以走通的地方，用1表示墙  如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通  带有路径的迷宫布局 注意：虽然总的算法思想在实验指导书中有介绍，而且相当详细，但是需要仔细读懂的，因为英文版文档中的代码是伪代码，要自己写成用c++的语言实现。比如对于C++语言的数组下标是从0开始的。

2.走迷宫递归算法的设计实现(选作) 下面给出一个迷宫递归算法的实现 bool Maze::solve(int i, int j) /* Post: attempt to find a path through the maze from coordinate (i,j) */ { bool finish = false; maze[i][j] = 'X'; if (i == rowsize && j == colsize) return true; // because we're done if (!finish && maze[i+1][j] == '0') finish = solve(i+1, j); if (!finish && maze[i][j+1] == '0') finish = solve(i, j+1); if (!finish && maze[i-1][j] == '0') finish = solve(i-1, j); if (!finish && maze[i][j-1] == '0') finish = solve(i, j-1); if (!finish) //无法走通，那么修改原来设置的X符号，但是不设置为0，因为这个点现在已经走过 maze[i][j] = '+'; return finish; } 在上面的算法中，迷宫的表示还是用字符1表示墙，字符0表示可以走通，用字符X表示路径。至于＋字符，仅仅是为了表示这条路已经走过。 应该注意到在实验题目文档中的迷宫是有八个方向可以行走的，而上面的递归算法中仅仅有四个方向是可以行走的，需要改动。还有，其直接把路径放到迷宫结构数组中了，而且还多出并不需要出现的字符‘＋’。请改动上面的算法，满足实验题目文档的需要，也就是说，满足八方向行走的要求，输出的迷宫路径图中，也仅仅有三种字符（1：墙；0：可行走；X：走通的路径）。 提示：可以参照上面的非递归算法中的数据结构，专门用MARK[m+2][n+2]表示这个路是否已经走过了