数据结构课程设计二叉树的建立与遍历

课程设计指导教师评定成绩表项目分值优秀(100x90)良好(90x80)中等(80x70)及格(70x60)不及格(x60)评分参考标准参考标准参考标准参考标准参考标准学习态度15学习态度认真，科学作风严谨，严格保证设计时间并按任务书中规定的进度开展各项工作学习态度比较认真，科学作风良好，能按期圆满完成任务书规定的任务学习态度尚好，遵守组织纪律，基本保证设计时间，按期完成各项工作学习态度尚可，能遵守组织纪律，能按期完成任务学习马虎，纪律涣散，工作作风不严谨,不能保证设计时间和进度技术水平与实际能力25设计合理、理论分析与计算正确，实验数据准确，有很强的实际动手能力、经济分析能力和计算机应用能力，文献查阅能力强、引用合理、调查调研非常合理、可信设计合理、理论分析与计算正确，实验数据比较准确，有较强的实际动手能力、经济分析能力和计算机应用能力，文献引用、调查调研比较合理、可信设计合理，理论分析与计算基本正确，实验数据比较准确，有一定的实际动手能力，主要文献引用、调查调研比较可信设计基本合理，理论分析与计算无大错，实验数据无大错设计不合理，理论分析与计算有原则错误，实验数据不可靠，实际动手能力差，文献引用、调查调研有较大的问题创新10有重大改进或独特见解，有一定实用价值有较大改进或新颖的见解，实用性尚可有一定改进或新的见解有一定见解观念陈旧论文(计算书、图纸)撰写质量50结构严谨，逻辑性强，层次清晰，语言准确，文字流畅，完全符合规范化要求，书写工整或用计算机打印成文；图纸非常工整、清晰结构合理，符合逻辑，文章层次分明，语言准确，文字流畅，符合规范化要求，书写工整或用计算机打印成文；图纸工整、清晰结构合理，层次较为分明，文理通顺，基本达到规范化要求，书写比较工整；图纸比较工整、清晰结构基本合理，逻辑基本清楚，文字尚通顺，勉强达到规范化要求；图纸比较工整内容空泛，结构混乱，文字表达不清，错别字较多，达不到规范化要求；图纸不工整或不清晰指导教师评定成绩：指导教师签名： 年 月 日重庆大学本科学生课程设计任务书课程设计题目二叉树的建立与遍历学院软件学院专业软件工程年级2009级已知参数和设计要求：问题描述建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。学生应完成的工作：基本要求 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。测试数据ABCDEGF（其中表示空格字符）则输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA选作内容采用非递归算法实现二叉树遍历。目前资料收集情况（含指定参考资料）：1. Robert L. Kruse编. Data Structures and Program Design in C+.高等教育出版社，2001.2.数据结构严蔚敏编，清华大学出版社，2000.3.数据结构教程李春葆编，清华大学出版社，2002.课程设计的工作计划： 14周：小组成员初步讨论选题，制定课程设计实施计划15周：实现选题编码，初步完成主要编程工作 16周：对已完成题目的编码进行调试，撰写课程设计报告任务下达日期 2011年 4 月 23 日完成日期 2011 年 6 月 17 日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本科学生课程设计任务书课程设计题目飞机场的模拟学院软件学院专业软件工程年级2009级已知参数和设计要求：问题描述 考虑一个很繁忙的小型飞机场，这个飞机场只有一条飞机跑道。在每个单位时间内，只有一架飞机可以着陆，或者这有一架飞机可以起飞，但不允许同时着陆起飞。学生应完成的工作：基本要求 将所有用于飞机场模拟的函数和方法组合成一个完整的程序。用飞机场模拟程序作若干次试运行试验，调整准备着陆和起飞的飞机数的期望值，并找出在飞机不会被拒绝服务的条件下这些数字的尽可能大的近似值。测试数据 找出在飞机不会被拒绝服务的条件下这些数字的尽可能大的近似值。选作内容 修改模拟程序，使飞机场有三条飞机跑道，其中一条用于着陆，另一条用于起飞。目前资料收集情况（含指定参考资料）：1. Robert L. Kruse编. Data Structures and Program Design in C+.高等教育出版社，2001.2.数据结构严蔚敏编，清华大学出版社，2000.3.数据结构教程李春葆编，清华大学出版社，2002.课程设计的工作计划： 14周：小组成员初步讨论选题，制定课程设计实施计划15周：实现选题编码，初步完成主要编程工作 16周：对已完成题目的编码进行调试，撰写课程设计报告任务下达日期 2011 年 4 月 23 日完成日期 2011 年 6 月 17 日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本科学生课程设计任务书课程设计题目八皇后问题学院软件学院专业软件工程年级2009级已知参数和设计要求：问题描述八皇后问题是一个以国际象棋为背景的问题：如何能够在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后学生应完成的工作：基本要求 在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。 测试数据 在计算机上运行八皇后程序，编写尚缺的Queens方法；通过引入一个计数器，在solve_from每次启动的时候递增此计数器，准确地找出要探查的棋盘位置数 选作内容 用415范围内的皇后数运行程序，尝试找出一个数学函数，它作为皇后数的函数、目前资料收集情况（含指定参考资料）：1. Robert L. Kruse编. Data Structures and Program Design in C+.高等教育出版社，2001.2.数据结构严蔚敏编，清华大学出版社，2000.3.数据结构教程李春葆编，清华大学出版社，2002.课程设计的工作计划： 14周：小组成员初步讨论选题，制定课程设计实施计划15周：实现选题编码，初步完成主要编程工作 16周：对已完成题目的编码进行调试，撰写课程设计报告任务下达日期 2011 年 4 月 23 日完成日期 2011 年 6 月 17 日指导教师 （签名）学 生 （签名）说明：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)flt_num = flt;clock_start = time;state = status;coutplane numberfltready to;if(status = arriving)coutland.endl;elsecouttake off.endl;Plane:Plane()flt_num = -1;clock_start = -1;state = null;void Plane:refuse()constcoutplane numberflt_num;if(state = arriving)coutdirected to another airportendl;elsecouttold to try to take off again laterendl;void Plane:land(int time) constint wait = time - clock_start;cout time :Plane number flt_numlanded afterwaittime unit(wait =1)?:s)in the takeoff queueendl;void Plane:fly(int time)constint wait =time - clock_start;cout time :Plane number flt_numtook off afterwaittime unit(wait =1)?:s)in the takeoff queueendl;int Plane:started()constreturn clock_start;void Plane:run_idle(int time)couttime:Runway is idleendl;Random类：#include #include random.h#include #include Random:Random(bool peseudo)if(peseudo) seed=1;elseseed = time(NULL)%INT_MAX;multiplier = 2743;add_on = 5923;int Random:reseed()seed = seed*multiplier + add_on;return seed;double Random:random_real()double max = INT_MAX + 1.0;double temp = reseed();if (temp limit)count+;product *=random_real();return count;Runway类：#include runway.h#include queue.h#include plane.h#include random.h#include #include using namespace std;Runway:Runway(int limit)queue_limit = limit;num_land_requests = num_takeoff_requests = 0;num_landings = num_takeoffs = 0;num_land_refused = num_takeoff_refused = 0;num_land_accepted = num_takeoff_accepted = 0;land_wait = takeoff_wait = idle_time = 0;void RunwayInitialize(int &end_time,int &queue_limit,double &arrival_rate,double &departure_rate)cout This program simulates an airport with only one runway. endl One plane can land or depart in each unit of time. endl;cout Up to what number of planes can be waiting to land or take off at any time? queue_limit;cout How many units of time will the simulation run? end_time;bool acceptable;do cout Expected number of arrivals per unit time? arrival_rate;cout Expected number of departures per unit time? departure_rate;if (arrival_rate 0.0 | departure_rate 0.0)cerr These rates must be nonnegative. 1.0)cerr Safety Warning: This airport will become saturated. endl; while (!acceptable);Error_code Runway:can_land(Plane ¤t)/*Post: If possible, the Plane current is added to thelanding Queue; otherwise, an Error_code of overflow isreturned. The Runway statistics are updated.Uses: class Extended_queue.*/Error_code result;if (landing.size() queue_limit)result = landing.append(current);elseresult = fail;num_land_requests+;if (result != success)num_land_refused+;elsenum_land_accepted+;return result;Error_code Runway:can_depart(Plane ¤t)/*Post: If possible, the Plane current is added to thetakeoff Queue; otherwise, an Error_code of overflow isreturned. The Runway statistics are updated.Uses: class Extended_queue.*/Error_code result;if (takeoffing.size() queue_limit)result = takeoffing.append(current);elseresult = fail;num_takeoff_requests+;if (result != success)num_takeoff_refused+;elsenum_takeoff_accepted+;return result;Runway_activity Runway:activity(int time, Plane &moving)/*Post: If the landing Queue has entries, its frontPlane is copied to the parameter movingand a result land is returned. Otherwise,if the takeoff Queue has entries, its frontPlane is copied to the parameter movingand a result takeoff is returned. Otherwise,idle is returned. Runway statistics are updated.Uses: class Extended_queue.*/Runway_activity in_progress;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 idle_time+;in_progress = idle;return in_progress;void Runway:shut_down(int time) const/*Post: Runway usage statistics are summarized and printed.*/cout Simulation has concluded after time time units. endl Total number of planes processed (num_land_requests + num_takeoff_requests) endl Total number of planes asking to land num_land_requests endl Total number of planes asking to take off num_takeoff_requests endl Total number of planes accepted for landing num_land_accepted endl Total number of planes accepted for takeoff num_takeoff_accepted endl Total number of planes refused for landing num_land_refused endl Total number of planes refused for takeoff num_takeoff_refused endl Total number of planes that landed num_landings endl Total number of planes that took off num_takeoffs endl Total number of planes left in landing queue landing.size() endl Total number of planes left in takeoff queue takeoffing.size() endl;cout Percentage of time runway idle 100.0 * ( float ) idle_time) / ( float ) time) % endl;cout Average wait in landing queue ( float ) land_wait) / ( float ) num_landings) time units;cout endl Average wait in takeoff queue ( float ) takeoff_wait) / ( float ) num_takeoffs) time units endl;cout Average observed rate of planes wanting to land ( float ) num_land_requests) / ( float ) time) per time unit endl;cout Average observed rate of planes wanting to take off ( float ) num_takeoff_requests) / ( float ) time) per time unit endl; （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 ：5How many units of time will the simulation run ：1000Expected number of arrivals per unit time ：48Expected number of departures per unit time ：48（8）测试情况：给出程序的测试情况，并分析运行结果。（测试结果如下图3.1所示）：图3.1（二）八皇后问题（1）问题描述：八皇后问题是一个以国际象棋为背景的问题：如何能够在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后（2）基本要求：在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。（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_Hconst int max_board = 30;class Queenspublic: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;protected:private:int count;bool queen_squaremax_boardmax_board;#endif主函数：#include queensclass.h#include #include using namespace std;void solve_from(Queens &configuration);void start();int main()start();cout00000000000000000xx;void start()int board_size;coutwhat is the size of the board?board_size;if(board_sizemax_board)coutthe number must be between 0 andmax_boardendl;elseQueens configuration(board_size);solve_from(configuration);start();void solve_from(Queens &configuration)if(configuration.is_solved()configuration.print();elsefor(int col = 0;colconfiguration.board_size;col+)if(configuration.unguarded(col)configuration.insert(col);solve_from(configuration);configuration.remove(col); queenscpp.cpp:#include queensclass.h#include #include using namespace std;Queens:Queens(int size)board_size = size;count = 0;for(int row = 0;rowboard_size;row+)for(int col = 0;colboard_size;col+)queen_squarerowcol=false; bool Queens:is_solved()constif(board_size = count)return true;elsereturn false;void Queens:print()constfor(int i=0;iboard_size;i+)for(int j=0;jboard_size;j+)cout (int)queen_squareij ;cout endl;cout endl; bool Queens:unguarded(int col)constint i;bool ok = true;for(i = 0;ok&i=0&col-i=0;i+)ok=!queen_squarecount-icol-i;/元素上左for(i = 1;ok&count-i=0&col+iboard_size;i+)ok=!queen_squarecount-icol+i;/元素上右return ok;void Queens:insert(int col)queen_squarecount+col = true;void Queens:remove(int col)queen_squarecount-col=false;queen_squarecountcol=false; （7）测试数据：用户指定所用的皇后数（如图1.1所示）图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.cpptypedef 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#includecpp1.cpp#includeusing 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(LR) return 1+L; else return 1+R;template Binary_node:Binary_node(const Entry &x)data=x;left=0;right=0;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;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,