软件工程数据结构实验指导书.doc

软件工程数据结构实验指导书（完整版）(文档可以直接使用，也可根据实际需要修改使用,可编辑 欢迎下载）给大家的实验文档中分为一下几部分1.实验准备：其中是c的一些内容，希望大家能借此好好复习c。因为大家现在使用的教材是c版本的，所以，对于c的一些基本语法，程序的编写都需要有些了解2.c语言实验教案中是一些c语言的基础知识，包括VC环境的使用和程序的调试，希望对c语言已经忘记的同学好好看看复习一下。（程序的编写调试是长年累月的过程，需要不断的积累，写得多了，程序调试的多了，自然就熟练了）3.对应的flash课件：其中是一些实验的flash课件演示，给大家做一下参考4.实验指导书和实验教案大家在做每个实验前都需要看看。阅读的时候，可以使用【视图】|【文档结构图】，可以比较自由跳到相应位置5. 总体实验难度比较大，时间紧，单靠实验课上的几个学时，作为初学者是无法完成的，需要大家在课前课后尽自己最大的努力。实验一 栈和队列（2学时）实验二 多项式加减法（2学时）实验三 迷宫（4学时）实验四 二叉树（4学时）实验五 图（2学时）实验六 归并排序（2学时）Programming Project one ：Application of Stack & Queue一、实验目的通过几段代码的编写，熟悉栈和队列二、实验内容1、Reversing a list （必做，分3个小题目task1,task2,task3）2、Small airport simulation（选作）具体如下：Task 1:Compile and run the following sample application of stack from the text. You may need to make changes to the code if necessary. Write down your input and output./ Section 2.1:Reversing a List#include int main( )/* Pre: The user supplies an integer n and n decimal numbers.Post: The numbers are printed in reverse order.Uses: The STL class stack and its methods */int n;double item;stack numbers; / declares and initializes a stack of numberscout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in reverse order. n;for (int i = 0; i item;numbers.push(item);cout endl endl;while (!numbers.empty( ) cout numbers.top( ) ;numbers.pop( );cout = maxstack) outcome = overflow; else entrycount+ = item; return outcome;Error_code Stack:pop()/*Pre: None.Post: If the Stack is not empty, the top of the Stack is removed. If the Stack is empty, an Error_code of underflow is returned.*/ Error_code outcome = success; if (count = 0) outcome = underflow; else -count; return outcome;Error_code Stack:top(Stack_entry &item) const/*Pre: None.Post: If the Stack is not empty, the top of the Stack is returned in item. If the Stack is empty an Error_code of underflow is returned.*/ Error_code outcome = success; if (count = 0) outcome = underflow; else item = entrycount - 1; return outcome;bool Stack:empty() const/*Pre: None.Post: If the Stack is empty, true is returned. Otherwise false is returned.*/ bool outcome = true; if (count 0) outcome = false; return outcome;Stack:Stack()/*Pre: None.Post: The stack is initialized to be empty.*/ count = 0;Task 3:Assume the following definition file for an extended stack data structure.class Extended_stack public: Extended_stack(); Error_code pop(); Error_code push(Stack_entry item); Error_code top(Stack_entry &item) const; bool empty() const; void clear(); / Reset the stack to be empty. bool full() const ; / If the stack is full, return true; else return false. int size() const; / Return the number of entries in the stack.private: int count; Stack_entry entrymaxstack;Implement the following methods: (a) clear(b) full(c) sizeUse method size of the class Extended_stack in your application Reversing a List to display the number of decimal numbers you imputed.Task 4:Combine all the functions and methods for the airport simulation into a complete program. Experiment with several sample rums of the airport simulation, adjusting the values for the expected numbers of planes ready to land and take off. Find approximate values for these expected numbers that are as large as possible subject to the condition that it is very unlikely that a plane must be refused service. What happens to these values if the maximum size of the queues is increased or decreased?/* Program extracts from Chapter 3 of Data Structures and Program Design in C+ by Robert L. Kruse and Alexander J. Ryba Copyright (C) 1999 by Prentice-Hall, Inc. All rights reserved. Extracts from this file may be used in the construction of other programs, but this code will not compile or execute as given here. */ Section 3.3:const int maxqueue = 10; / small value for testingclass Queue public: Queue(); bool empty() const; Error_code serve(); Error_code append(const Queue_entry &item); Error_code retrieve(Queue_entry &item) const;protected: int count; int front, rear; Queue_entry entrymaxqueue;Queue:Queue()/*Post: The Queue is initialized to be empty.*/ count = 0; rear = maxqueue - 1; front = 0;bool Queue:empty() const/*Post: Return true if the Queue is empty, otherwise return false.*/ return count = 0;Error_code Queue:append(const Queue_entry &item)/*Post: item is added to the rear of the Queue. If the Queue is fullreturn an Error_code of overflow and leave the Queue unchanged.*/ if (count = maxqueue) return overflow; count+; rear = (rear + 1) = maxqueue) ? 0 : (rear + 1); entryrear = item; return success;Error_code Queue:serve()/*Post: The front of the Queue is removed. If the Queueis empty return an Error_code of underflow.*/ if (count = 0) return underflow; count-; front = (front + 1) = maxqueue) ? 0 : (front + 1); return success;Error_code Queue:retrieve(Queue_entry &item) const/*Post: The front of the Queue retrieved to the output parameter item. If the Queue is empty return an Error_code of underflow.*/ if (count = 0) return underflow; item = entryfront; return success;int Extended_queue:size() const/*Post: Return the number of entries in the Extended_queue.*/ return count;/ Section 3.5:int main() / Airport simulation program/*Pre: The user must supply the number of time intervals the simulation is to run, the expected number of planes arriving, the expected number of planes departing per time interval, and the maximum allowed size for runway queues.Post: The program performs a random simulation of the airport, showing the status of the runway at each time interval, and prints out a summary of airport operation at the conclusion.Uses: Classes Runway, Plane, Random and functions run_idle, initialize.*/ int end_time; / time to run simulation int queue_limit; / size of Runway queues int flight_number = 0; double arrival_rate, departure_rate; initialize(end_time, queue_limit, arrival_rate, departure_rate); Random variable; Runway small_airport(queue_limit); for (int current_time = 0; current_time end_time; current_time+) / loop over time intervals int number_arrivals = variable.poisson(arrival_rate); / current arrival requests for (int i = 0; i number_arrivals; i+) Plane current_plane(flight_number+, current_time, arriving); if (small_airport.can_land(current_plane) != success) current_plane.refuse(); int number_departures= variable.poisson(departure_rate); / current departure requests for (int j = 0; j number_departures; j+) Plane current_plane(flight_number+, current_time, departing); if (small_airport.can_depart(current_plane) != success) current_plane.refuse(); Plane moving_plane; switch (small_airport.activity(current_time, moving_plane) / Let at most one Plane onto the Runway at current_time. case land: moving_plane.land(current_time); break; case takeoff: moving_plane.fly(current_time); break; case idle: run_idle(current_time); small_airport.shut_down(end_time);enum Runway_activity idle, land, takeoff;class Runway public: Runway(int limit); Error_code can_land(const Plane ¤t); Error_code can_depart(const Plane ¤t); Runway_activity activity(int time, Plane &moving); void shut_down(int time) const;private: Extended_queue landing; Extended_queue takeoff; int queue_limit; int num_land_requests; / number of planes asking to land int num_takeoff_requests; / number of planes asking to take off int num_landings; / number of planes that have landed int num_takeoffs; / number of planes that have taken off int num_land_accepted; / number of planes queued to land int num_takeoff_accepted; / number of planes queued to take off int num_land_refused; / number of landing planes refused int num_takeoff_refused; / number of departing planes refused int land_wait; / total time of planes waiting to land int takeoff_wait; / total time of planes waiting to take off int idle_time; / total time runway is idle;enum Plane_status null, arriving, departing;class Plane public: Plane(); Plane(int flt, int time, Plane_status status); void refuse() const; void land(int time) const; void fly(int time) const; int started() const;private: int flt_num; int clock_start; Plane_status state;void initialize(int &end_time, int &queue_limit, double &arrival_rate, double &departure_rate)/*Pre: The user specifies the number of time units in the simulation, the maximal queue sizes permitted, and the expected arrival and departure rates for the airport.Post: The program prints instructions and initializes the parameters end_time, queue_limit, arrival_rate, and departure_rate to the specified values.Uses: utility function user_says_yes*/ 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);Runway:Runway(int limit)/*Post: The Runway data members are initialized to record no prior Runway use and to record the limit on queue sizes.*/ 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;Error_code Runway:can_land(const 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 result; if (landing.size() queue_limit) result = landing.append(current); else result = fail; num_land_requests+; if (result != success) num_land_refused+; else num_land_accepted+; return result;Error_code Runway:can_depart(const Plane ¤t)/*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.*/ Error_code result; if (takeoff.size() queue_limit) result = takeoff.append(current); else result = fail; num_takeoff_requests+; if (result != success) num_takeoff_refused+; else num_takeoff_accepted+; return result;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.*/ Runway_activity in_progress; if (!landing.empty() landing.retrieve(moving); land_wait += time - moving.started(); num_landings+; in_progress = land; landing.serve(); else if (!takeoff.empty() takeoff.retrieve(moving); takeoff_wait += time - moving.started(); num_takeoffs+; in_progress = takeoff; takeoff.serve(); else idle_time+; in_progress = idle; return in_progress;Plane:Plane(int flt, int time, Plane_status status)/*Post: The Plane data members flt_num, clock_start, and state are set to the values of the parameters flt, time and status, respectively.*/ flt_num = flt; clock_start = time; state = status; cout Plane number flt ready to ; if (status = arriving) cout land. endl; else cout take off. endl;Plane:Plane()/*Post: The Plane data members flt_num, clock_start, state are set to illegal default values.*/ flt_num =