数据结构课程设计论文
封面
指导教师评定成绩：
指导教师签名： 年 月 日
说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。
2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。
说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。 2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。
说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。 2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。
摘要
随着软件技术的日益普及, 程序的代码量也不断增大, 这就需要合理的数据结构来完善程序的编写。本论文主要利用数据结构的知识解决飞机场的模拟、八皇后问题和二叉树的建立于遍历。
针对飞机场的模拟问题，主要利用栈的知识。其算法思想：对飞机场的跑道可以被用作起飞或降落。在每个单位时间内, 只有一架飞机可以着陆, 或者只有一架飞机可以起飞, 但不允许同时着陆和起飞。飞机的到达和起飞是随机的。在单位时间里, 飞机的降落比起飞优先。
针对八皇后问题，我们采用回溯法实现，其算法思想：从根结点出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深 方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。 换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地 在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
针对二叉树的建立和遍历问题，我们以二叉链表作为其存储方式，以前序来建立二叉树并分别使用二叉树前序、中序和后序遍历的递归算法来遍历二叉树。其算法思想：以前序遍历二叉树为例，若二叉树非空，则依次执行如下操作：访问根结点、遍历左子树、遍历右子树。对其左右子树，使用同样的方法实现。
关键字： 栈 回溯法 深度优先 递归 二叉链表
（一）飞机场模拟 （1）问题描述：
考虑一个很繁忙的小型飞机场，只有一条飞机跑道。创建模拟程序以对飞机的起降进行调度。将所有用于飞机场模拟的函数和方法组合唱一个完整的程序，有飞机场模拟程序做若干次试运行实验，调整准备着陆和起飞的飞机数的期望值，并找出在飞机不会被拒绝服务的条件下这些数字的尽可能大的近似值。 （2）基本要求：
在每个单位时间内，只有一架飞机可以着陆，或者只有一架飞机可以起飞，不允许同时着陆起飞。飞机的到达和起飞是随机的。在任何给定时刻，飞机跑道可能空闲，或可能有一架飞机正着陆或起飞，并且可能有若干架飞机等待着陆或起飞。 （3）算法思想：
跑道可以被用作起飞或降落。
在每个单位时间内, 只有一架飞机可以着陆, 或者只有一架飞机可以起飞, 但不允许同时着陆和起飞。
飞机的到达和起飞是随机的。
在单位时间里, 飞机的降落比起飞优先。
正在等待的飞机都在 landing 和 takeoff的队列中, 他们都具有固定的大小。 （4）模块划分：
Plane 类：其对象表示单个飞机，包括一个初始化方法和表示起飞和着陆的方法；并维护特定的Plane 对象的数据，包括航班号、到达机场系统的时间、到达或者离开的Plane 状态。
Random 类：Random 类封装到达或离开跑道的飞机的随机特征，将模拟期间的时间分成单元，使得在任一给定的时间单元内仅有一架飞机能利用飞机跑道着陆或起飞。
飞机跑道Runway 维护两个飞机队列，称其为landing 和takeoff ，用于保存正在等待的飞机。仅当没有飞机等待着陆时才允许起飞。
（5）数据结构：
Plane ：创建飞机抽象类型（包含plane （），fly （），land （），refuse （），started （），）
Runway ：创建跑道抽象类型（包含runway （），RunwayInitialize （），can_land(),:can_depar(),actvility(),） Queue ：创建队列抽象类型(包含Queue （），)
Random:创建随机数抽象类型（包含Random （），random_real()，reseed()，possion()，） （6）源程序： Plane 类： #include "plane.h"
#include "queue.h" #include "random.h" #include "runway.h" #include #include using namespace std;
Plane ::Plane(int flt,int time,Plane_status status) { }
Plane::Plane() { }
void Plane::refuse()const { }
void Plane::land(int time) const
cout
cout
cout
cout
}
void Plane::fly(int time)const { }
int Plane::started()const { }
void Plane::run_idle(int time) { }
Random 类： #include #include "random.h" #include #include
Random::Random(bool peseudo) {
if (peseudo) seed=1; else
seed = time(NULL)%INT_MAX; cout
cout
cout
multiplier = 2743;
}
int Random::reseed() { }
double Random::random_real() { }
int Random::possion(double mean) { }
Runway 类： #include "runway.h" #include "queue.h" #include "plane.h" #include "random.h" #include
double limit = exp(-mean); double product = random_real(); int count = 0; while (product > limit) { }
return count;
count++;
product *=random_real(); double max = INT_MAX + 1.0; double temp = reseed(); if (temp
seed = seed*multiplier + add_on; return seed;
#include
using namespace std;
Runway::Runway(int limit)
{
}
void RunwayInitialize(int &end_time,int &queue_limit,double &arrival_rate,double &departure_rate)
{
bool acceptable; do { cout > arrival_rate; cout > departure_rate; if (arrival_rate > end_time; cout > queue_limit;
}
Error_code Runway::can_land(Plane ¤t)
/*
Post: If possible, the Plane current is added to the
landing Queue; otherwise, an Error_code of overflow is
returned. The Runway statistics are updated.
Uses: class Extended_queue.
*/
{
}
Error_code Runway::can_depart(Plane ¤t)
/* return result; if (result != success) else num_land_accepted++; num_land_refused++; Error_code result; if (landing.size() 1.0) cerr
Post: If possible, the Plane current is added to the
takeoff Queue; otherwise, an Error_code of overflow is
returned. The Runway statistics are updated.
Uses: class Extended_queue.
*/
{
}
Runway_activity Runway::activity(int time, Plane &moving)
/*
Post: If the landing Queue has entries, its front
Plane is copied to the parameter moving
and a result land is returned. Otherwise,
if the takeoff Queue has entries, its front
Plane is copied to the parameter moving
and a result takeoff is returned. Otherwise,
idle is returned. Runway statistics are updated.
Uses: class Extended_queue.
*/
{ return result; Error_code result; if (takeoffing.size()
}
if (!landing.empty()) { } landing.retrive(moving); land_wait += time - moving.started(); num_landings++; in_progress = land; landing.serve(); else if (!takeoffing.empty()) { } takeoffing.retrive(moving); takeoff_wait += time - moving.started(); num_takeoffs++; in_progress = takeoff; takeoffing.serve(); else { } return in_progress; idle_time++; in_progress = idle;
void Runway::shut_down(int time) const
/*
Post: Runway usage statistics are summarized and printed.
*/
{
cout
}
（7）测试数据：
This program simulates an airport with only one runway.
One plane can land or depart in each unit of time.
Up to what number of planes can be waiting to land or take off at any time ：5
How many units of time will the simulation run ：1000
Expected number of arrivals per unit time ：48
Expected number of departures per unit time ：48
（8）测试情况：
给出程序的测试情况，并分析运行结果。（测试结果如下图3.1所示）：
图3.1
（二）八皇后问题
（1）问题描述：
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后
（2）基本要求：
在
8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。
为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
（3）算法思想：
通过回溯法实现：从根结点出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深 方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。 换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地 在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
（4）模块划分：
主程序：驱动概要的递归方法。打印出关于程序功能的信息，在程序中允许用户指定所用的皇后数。
Queens 类：打印一个配置，在棋盘上某特定位置向配置中增加一个皇后，移去这个皇后，测试某特定格子是否未被配置设防。
回溯函数：基于上述决定，编写在棋盘上摆放皇后的递归函数。注意通过引用传递函数参数是为了节省用于复制Queens 对象的时间。
（5）数据结构：
Queen:创建皇后抽象数据类型
（包含Queens(int size);
bool is_solved()const ; void print()const ; bool unguarded(int col) const ; void insert (int col); void remove(int col); int board_size;
）
（6）源程序：
queensclass.h:
#ifndef QUEENS_H
#define QUEENS_H
const int max_board = 30;
class Queens
{
public :
Queens(int size); bool is_solved()const ;
bool unguarded(int col) const ; void insert (int col); void remove(int col); int board_size;
protected :
private :
};
#endif
主函数：
#include "queensclass.h"
#include
#include
using namespace std;
void solve_from(Queens &configuration); void start();
int main()
{
}
void start()
{
int board_size; cout>board_size; if (board_sizemax_board) start(); cout>xx; int count; bool queen_square[max_board][max_board];
}
else { } Queens configuration(board_size); solve_from(configuration); start();
void solve_from(Queens &configuration) {
}
queenscpp.cpp:
#include "queensclass.h"
#include
#include
using namespace std;
Queens::Queens(int size)
{
board_size = size; count = 0; if (configuration.is_solved()) else for (int col = 0;col
}
for (int col = 0;col
bool Queens::is_solved()const {
}
void Queens::print()const
{
}
bool Queens::unguarded(int col)const {
int i; bool ok = true ; for (i = 0;ok&&i=0&&col-i>=0;i++) ok=!queen_square[count-i][col-i];//元素上左
}
for (i = 1;ok&&count-i>=0&&col+i
void Queens::insert(int col)
{
}
void Queens::remove(int col)
{
}
（7）测试数据：用户指定所用的皇后数（如图1.1所示） queen_square[count--][col]=false ; queen_square[count][col]=false ; queen_square[count++][col] = true ;
图1.1
（8）测试情况：
给出程序的测试情况，并分析运行结果八皇后问题共有92种解答：
（部分解答情况如图1.2所示）。
图1.2
（三）二叉树的建立与遍历
（1）问题描述：
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
（2）基本要求：
从键盘接受输入（前序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行遍历（前序、中序、后序），将遍历结果打印输出。
（3）算法思想：
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身(N)
（2）遍历该结点的左子树(L)
（3）遍历该结点的右子树(R)
以上三种操作有六种执行次序： NLR、LNR 、LRN 、NRL 、RNL 、RLN 。 前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作：遍历左子树、访问根结点、遍历右子树。前序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：访问根结点、遍历左子树、遍历右子树。后序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树、遍历右子树、访问根结点。
（4）模块划分：
1. 建立二叉树 tree *CreatBitree()
2. 基本运算
void push(stack **top,tree *tree) //树结点入栈
void pop(stack **top,tree **T) //出栈，栈内元素赋值
void getTop(stack*s,tree **t) //获取栈顶元素
3. 递归遍历函数
void PreOrder(tree *b1) //前序遍历函数
void MidOrder(tree *b2) //中序遍历函数
void LastOrder(tree *b3) //后序遍历函数
（5）数据结构：
Binary_node：创建节点抽象数据类型
（
Binary_node（）
Entry data;
Binary_node *left;
Binary_node *right;
// constructors:
Binary_node();
Binary_node(const Entry &x);
）
Binary_tree：创建二叉树抽象数据类型
(
Binary_tree();
bool empty() const ;
void preorder(void (*visit)(Entry &));
void inorder(void (*visit)(Entry &));
void postorder(void (*visit)(Entry &));
int size() const ;
void clear();
int height() const ;
void insert(const Entry &);
Binary_tree (const Binary_tree &original);
Binary_tree & operator =(const Binary_tree &original);
~Binary_tree();
)
（6）源程序：
cpp1.cpp
typedef char Entry;
template
struct Binary_node {
// data members:
Entry data;
Binary_node *left;
Binary_node *right;
// constructors:
Binary_node();
Binary_node(const Entry &x);
};
template
class Binary_tree {
public :
Binary_tree();
bool empty() const ;
void preorder(void (*visit)(Entry &));
void inorder(void (*visit)(Entry &));
void postorder(void (*visit)(Entry &));
int size() const ;
void clear();
int height() const ;
void insert(const Entry &);
Binary_tree (const Binary_tree &original);
Binary_tree & operator =(const Binary_tree &original);
~Binary_tree();
protected :
// Add auxiliary function prototypes here.
Binary_node *root;
int recursive_height(Binary_node *sub_root) const ;
void recursive_insert(Binary_node * &sub_root,const Entry &x);
void recursive_postorder(Binary_node *sub_root, void (*visit)(Entry &));
void recursive_preorder(Binary_node *sub_root,void (*visit)(Entry &));
void recursive_inorder(Binary_node *sub_root,void (*visit)(Entry &));
void recursive_clear(Binary_node * &sub_root);
Binary_node * recursive_copy(Binary_node *sub_root);
};
cpp2.cpp
#include"cpp1.cpp"
#include
using namespace std;
template
int Binary_tree :: height() const
{
return recursive_height(root);
}
template
int Binary_tree::recursive_height(Binary_node *sub_root) const
{
if (sub_root==0)
return 0;
int L=recursive_height(sub_root->left);
int R=recursive_height(sub_root->right);
if (L>R)
return 1+L;
else
return 1+R;
template
Binary_node::Binary_node(const Entry &x)
{
}
template
void Binary_tree::insert(const Entry &x)
{
recursive_insert(root, x);
}
template
void Binary_tree ::recursive_insert(Binary_node * &sub_root,const Entry &x) {
if (sub_root==0)
sub_root=new Binary_node(x);
else
if (recursive_height(sub_root->right)left))
recursive_insert(sub_root->right, x);
else
recursive_insert(sub_root->left, x);
}
template
Binary_tree::Binary_tree()
{
root=0;
}
data=x; left=0; right=0;
template
bool Binary_tree::empty() const
{
return root==0;
}
template
void Binary_tree::inorder(void (*visit)(Entry &))
{
recursive_inorder(root, visit);
}
template
void Binary_tree::recursive_inorder(Binary_node *sub_root,
void (*visit)(Entry &))
{
if (sub_root != 0) {
recursive_inorder(sub_root->left, visit);
(*visit)(sub_root->data);
recursive_inorder(sub_root->right, visit);
}
}
template
void Binary_tree::preorder(void (*visit)(Entry &))
{
recursive_preorder(root, visit);
}
template
void Binary_tree::recursive_preorder(Binary_node *sub_root,
void (*visit)(Entry &))
if (sub_root != 0) {
(*visit)(sub_root->data);
recursive_preorder(sub_root->left, visit);
recursive_preorder(sub_root->right, visit);
}
}
template
void Binary_tree::postorder(void (*visit)(Entry &))
{
recursive_postorder(root, visit);
}
template
void Binary_tree::recursive_postorder(Binary_node *sub_root,
void (*visit)(Entry &))
{
if (sub_root != 0) {
recursive_postorder(sub_root->left, visit);
recursive_postorder(sub_root->right, visit);
(*visit)(sub_root->data);
}
}
template
void Binary_tree::recursive_clear(Binary_node * &sub_root)
{
Binary_node *temp = sub_root;
if (sub_root ==0) return ;
recursive_clear(sub_root->left);
recursive_clear(sub_root->right);
sub_root =0;
delete temp;
}
template
void Binary_tree::clear( )
{
recursive_clear(root);
}
template
Binary_tree :: ~Binary_tree( )
{
clear();
}
template
Binary_tree :: Binary_tree (const Binary_tree &original)
{
root = recursive_copy(original.root);
}
template
Binary_node *Binary_tree :: recursive_copy(
Binary_node *sub_root)
{
if (sub_root == 0) return 0;
Binary_node *temp = new Binary_node(sub_root->data);
temp->left = recursive_copy(sub_root->left);
temp->right = recursive_copy(sub_root->right);
return temp;
}
template
Binary_tree &Binary_tree :: operator = (const
Binary_tree &original)
{
Binary_tree new_copy(original);
clear( );
root = new_copy.root;
new_copy.root = 0;
return *this ;
}
cpp3.cpp
typedef char type;
#include"cpp2.cpp"
#include
using namespace std;
void visitvisit(type &x);
int main()
{
cout mytree; int n; cin>>n; cout
>j; mytree.insert(j); mytree.preorder(visitvisit); cout
}
mytree.postorder(visitvisit); cout
void visitvisit(type &x){
}
（7）测试数据：
ABC ффDE фG ффF ффф（其中ф表示空格字符）
则输出结果为：
先序：ABCDEGF
中序：CBEGDFA
后序：CGBFDBA
（8）测试情况： cout
输出结果为：
前序：ABCDEFG
中序：CBEFDGA
后序：CFBGDBA
总结
1、 在飞机场模拟、八皇后问题的解决过程中，原本想为了使程序的执行过程更加易于理解，而
对程序进行可视化，可后来为了因为种种原因而去掉了，设计过程中尽管去掉了可视化，但在实现中所遇到的困难也不少，但在大家的齐心合力之下，所有问题都得以解决。
2、 在二叉树的遍历问题的设计过程中，本分函数用到了指针的指针，如： push(stack **top,tree
*tree) ，pop(stack **top,tree **T)， getTop(stack*s,tree **t)，在设计和理解的过程中遇到了不少麻烦，这个问题给我们一个启示：指针能够避免则避免，若确实不能避免，也因减少它指向的层数。这可以减少程序设计和代码理解上的难度。
3、 在本次课程设计的过程中，我们经历了好几场专业课考试，尽管大家时间紧迫，备考压力很
大，但在课程设计这个问题上，大家依旧各司其职，保质保量的完成自己应该完成的内容，以避免拖慢课程设计的进程。
4、 在这次课程设计的过程中，我们认识到自己对C++编程语言的掌握的不足，和运用的不熟练，
这是导致我们编程时遇到有些，如链接问题，指针指向等问题时抓狂的原因。通过此次课程设计，我们学到了部分编程技巧和很多程序与算法设计方面的知识，丰富了我们对程序设计的认识，使我们对C++语言的使用更加熟练，同时，在整个课程设计过程中，锻炼了组员间的合作意识和挑战精神，增强了团队的凝聚力，加强了同学间的相互了解，增强了彼此间的友谊。
参考文献
[1]Robert L.Kruse ，Alexander J.Ryba . 钱丽萍. C++数据结构与程序设计. 北京：清华大学出版社. 2004
[2]Robert L.Kruse，Alexander J.Ryba. 《Data structures and Program Design In C++(影印版) 》. 北京：高等教育出版社. 2001
[3]严蔚敏，吴伟民. 《数据结构（C 语言版）》. 北京：清华大学出版社. 2007
[4]Sartaj Sahni. 汪诗林 , 孙晓东. 《数据结构、算法与应用:C++语言描述》. 机械工业出版社. 2004
[5]Clifford A. Shaffer. 张铭. 《数据结构与算法分析C++语言描述》. 电子工业出版社. 2010