软件工程数据结构实验指导书.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 <stack>
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<double> numbers; // declares and initializes a stack of numbers
cout << " Type in an integer n followed by n decimal numbers."
<< endl
<< " The numbers will be printed in reverse order."
<< endl;
cin >> n;
for (int i = 0; i < n; iCC) {
cin >> item;
numbers.push(item);
}
cout << endl << endl;
while (!numbers.empty( )) {
cout << numbers.top( ) << " ";
numbers.pop( );
}
cout << endl;
}

Task 2:
Assemble the appropriate declarations from the text into the files stack.h and stack.cpp. Make any necessary changes as re-compiling the above application Reversing a List by replacing the use of STL class stack with the use of user defined class Stack.

// Section 2.2:

const int maxstack = 10; // small value for testing

class Stack {
public:
Stack();
bool empty() const;
Error_code pop();
Error_code top(Stack_entry &item) const;
Error_code push(const Stack_entry &item);

private:
int count;
Stack_entry entry[maxstack];
};

Error_code Stack::push(const Stack_entry &item)
/*
Pre: None.
Post: If the Stack is not full, item is added to the top
of the Stack. If the Stack is full,
an Error_code of overflow is returned and the Stack is left unchanged.
*/

{
Error_code outcome = success;
if (count >= maxstack)
outcome = overflow;
else
entry[count++] = 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 = entry[count - 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 entry[maxstack];
};

Implement the following methods: (a) clear (b) full (c) size
Use 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 testing

class 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 entry[maxqueue];
};

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 full
return an Error_code of overflow and leave the Queue unchanged.
*/

{
if (count >= maxqueue) return overflow;
count++;
rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1);
entry[rear] = item;
return success;
}

Error_code Queue::serve()
/*
Post: The front of the Queue is removed. If the Queue
is 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 = entry[front];
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 &current);
Error_code can_depart(const Plane &current);
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? " << flush;
cin >> queue_limit;

cout << "How many units of time will the simulation run?" << flush;
cin >> end_time;

bool acceptable;
do {
cout << "Expected number of arrivals per unit time?" << flush;
cin >> arrival_rate;
cout << "Expected number of departures per unit time?" << flush;
cin >> departure_rate;
if (arrival_rate < 0.0 || departure_rate < 0.0)
cerr << "These rates must be nonnegative." << endl;
else
acceptable = true;

if (acceptable && arrival_rate + departure_rate > 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 &current)
/*
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 &current)
/*
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 =