算法与数据结构 实验报告

《算法与数据结构》实验报告

实验一 约瑟夫环问题（2学时）

将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

实验二 链表的操作（4学时）

编一程序：① 建立一个数据域为1至10的带头结点的链表；

② 将此链表就地逆转。

链表的类型说明如下：

#include

#include

class Node{

public:

int data;

第1页

Node *next;

Node( ){next=0;}

friend class LinkList;

};//Node

class LinkList {

Node *head;

public:

LinkList( ) { head=new Node(); }

void Create(); //创建长度为n的单链表

int GetElem(int i); //返回第i个元素值

Node* Locate(int e); //返回第一个与e匹配的元素结点指针

bool IsEmpty( ) {return (head->next==0);} //判断是否为空链表

void Insert(int x, int i ); //在第i个结点之前插入元素值为x的结点

int Delete ( int i ); //删除第i个结点，并返回其元素值

第2页

void Clear( ); //清空链表

void print( );

};// LinkList

实验三 栈的应用－中缀表达式的求值（4学时）

表达式求值是计算机实现程序设计语言中的基本问题之一，也是栈应用的一个典型例子，通过本实验，对输入的一个表达式进行求值。

说明：表达式中只包含＋、－、×、/ 运算及（ 和 ）。

实验四 二叉树的遍历（6学时）

树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础。

实验五 图的遍历（6学时）

建立一个图，然后用深度优先或广度优先的方式对其进行遍历。

实验六 图的应用（6学时）

如要在n个城市之间建设通信网络，只需架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是求一个无向网的最小生成树问题。

第3页

利用Prim算法求无向网的最小生成树。

实验八 实现排序和查找操作（6学时）

排序方法选择方案：

第一组：直接插入和希尔排序； 第二组：冒泡排序和快速排序；

第三组：简单选择排序和堆排序；

每位同学至少选择一组排序算法进行实现；然后再使用顺序查找和折半查找算法分别对待排序数据序列和已排序数据序列进行查找，即现实其查找算法。

实 验九 链表综合算法设计－集合运算（6学时）

有两个集合A、B，要求它的交集、并集和差集C。用两个链表L1、L2存储集合A、B，用链表L3存储集合C。

实 验十 将中缀表达式转换为后缀表达式并进行计算（6学时）

中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。

第4页