软件工程数据结构实验教案

实验教案实验一栈和队列

重点：

1.掌握如何使用STL中的栈

2.掌握如何自己编写栈的代码

难点：

用数组实现栈的原理，并能用c++描述

具体实验讲解如下：

本实验是要通过几段代码的编写，熟悉栈和队列的编写和应用

在实验指导书中有4个题目，其中题目1、2、3是关于栈的，题目4是关于队列的。其中题目1难度小，题目2和题目3是有联系的，经过努力可以做出，但是题目4难度大些，属于选作内容

1.题目一（STL中的栈）

读懂实验指导书中的Task1中的程序（使用栈进行序列的顺序反转），并编译运行，通过此了解如果要实现一个栈类，里面需要的基本的成员函数。这个程序在书上也有。

（1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stack numbers;中就是声明了一个栈，这个栈中存放的数据类型为double。

（2）注意要使用c++的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的：

#include

using namespace std;

2.题目二、题目三（自己编写栈）

这里可以把题目二和题目三合成一个题目，在一个程序中完成就可以了。

合并后的题目如下：自己编程程序实现一个简单的栈，并用于替换题目1中对标准模板库中的栈的使用，同时对自己实现的栈的功能进行扩充，添加实现如下几个函数

(a) clear (b) full (c) size。

使用新添加的栈函数，显示在进行数字序列反转时输入的十进制数的个数。

注意：

(1)实验题目文档中已经把大部分的代码都给出来了。栈可以用链表或者数组实现，这里是

用数组实现。

(2)实验题目中给出的仅仅是部分的代码，自己还需要在看懂的前提下，进行修改补充，才

可以达到具体的要求，不明白的地方也可以参考书上这一部分。

一些补充代码如下：

enum Error_code {success,underflow,overflow};

3.题目四（选作）

这个题目的主要目的是熟悉队列这个数据结构，而为了说明问题又用了一个模拟飞机场的程序，因此这个实验项目在程序的找错误调试编译，读源代码上对大家也是一个锻炼。

仔细阅读教科书中关于模拟飞机场这一部分，阅读源代码。实验题目中的源代码并不完整并且有些语法等等的错误，其缺少生成随机数这一个类，附录一会把这个类给大家，有兴趣的话，可以看教科书中的附录，有些介绍。另外，也可以使用随机数生成函数（当然主函数要做相应修改去使用现有的随机数生成函数），使用示例见附录二。

另外大家把代码读懂后就可以复制粘贴到编译环境中了，主要是读懂代码。但是，一定要知道，这样直接粘贴的代码并不能直接运行，需要修改其中的一些bug。

这个题目的要求是能读懂代码，明白实现，而且要把代码放到VC中编译调试，使其能正常运行。并通过此，能对程序的编译调试查找错误较为熟悉。

注意，一定要使警告也为0个。

一些补充代码如下：

(1)enum Plane_status {null, arriving, departing};

(2)enum Error_code {success,underflow,overflow};

(3)typedef Plane Queue_entry;

一个模拟时间点可以有飞机想起飞，或者有飞机想降落。但是该模拟时间点只能有一架飞机能起飞或者一架飞机能降落（假设飞机场只有一条跑道）

具有的类如下：

(1)Extended_queue：队列，实际上是作为飞机场的等待起飞和降落的排队队列，该队

列里面放的是飞机类

(2)Plane：飞机类

(3)Rumway：飞机场类，该类中有两个队列作为类成员，分别是等待起飞和降落的队

列。由于假设飞机场只有一条跑道，所以，同一时间点只能有一架飞机起飞或者降落。

(4)Random

附录一

下面是Random类，用于生成随机数，核心代码来自教科书的附录

//Random.h

#ifndef RANDOM_H_

#define RANDOM_H_

class Random

{

public:

Random(bool pseudo=true);

//declare random-number generation methods here

double random_real();

int poisson(double mean);

private:

int reseed(); //re-randomize the seed

int seed;

int multiplier,add_on;//constants for use in arithmetic operations

};

#endif

//Random.cpp

#include "Random.h"

#include

#include

#include

int Random::reseed()

//Post:The seed is replaced by a psuedorandom successor

{

seed=seed*multiplier+add_on;

return seed;

}

Random::Random(bool pseudo)

{

/*Post:The values of seed ,add-on, and multiplier are initialized. The seed is initialized randomly only if pseudo==false*/

if (pseudo)

{

seed=1;

}

else

{

seed=static_cast(time(NULL)%INT_MAX);

multiplier=2743;

add_on=5923;

}

}

double Random::random_real()

{

/*Post:A random real number between 0 and 1 is returned*/

double max=INT_MAX+1.0;

double temp=reseed();

if (temp<0)

{

temp=temp+max;

}

return temp/max;

}

int Random::poisson(double mean)

{

/*Post:A random integer, reflecting a Poisson distribution with parameter mean, is return.*/ double limit=exp(-mean);

double product=random_real();

int count=0;

while (product>limit)

{

count++;

product*=random_real();

}

return count;

}

附录二

// crt_rand.c

// This program seeds the random-number generator

// with the time, then exercises the rand function.

//

#include

#include

#include

void SimpleRandDemo( int n )

{

// Print n random numbers.

int i;

for( i = 0; i < n; i++ )

printf( " %6d\n", rand() );

}

void RangedRandDemo( int range_min, int range_max, int n )

{

// Generate random numbers in the half-closed interval

// [range_min, range_max). In other words,

// range_min <= random number < range_max

int i;

for ( i = 0; i < n; i++ )

{

int u = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min;

printf( " %6d\n", u);

}

}

int main( void )

{

// Seed the random-number generator with the current time so that

// the numbers will be different every time we run.

srand( (unsigned)time( NULL ) );

SimpleRandDemo( 10 );

printf("\n");

RangedRandDemo( -100, 100, 10 );

}

结果：

22036

18330

11651

27464

18093

3284

11785

14686

11447

11285

74

48

27

65

96

64

-5

-42

-55

66

实验教案实验二多项式加减法

重点：

用队列实现多项式加减法

难点：

1.如何用队列表示多项式

2.在用队列表示多项式时，如果涉及多项式类，则队列类和多项式类之间的关系如何，即

理清多项式类与队列类的关系

3.正确用代码实现

具体讲解如下：

本实验通过编写一个程序实现两个多项式的加法和减法运算，进一步掌握常用的数据结构：栈和队列。

多个多项式连续的加减法，可以用栈为辅助结构实现，该部分作为选作内容。

存放多项式的数据结构

实现多项式的加减法，首先考虑是用什么样的数据结构保存多项式。

(1)链表：一个节点node是多项式的一项，本次实验不涉及

(2)队列：队列中的一项是多项式的一项，本实验是用队列作为保存多项式的数据结构。

教科书中详细描述了一种实现多项式运算的算法。

a)用户从键盘输入要参与运算的多项式每一项的系数和指数，输入多个多项式后

就可以对多个多项式进行运算（加法、减法等）。

b)为了使多项式的加法算法相对简单些，有一个约定，就是用户在输入多项式的

系数和指数的时候，约定用户输入的指数是降幂排列的（如果有时间可以想想

如果用户输入每个多项式的时候并不是把指数降幂排列，你该如何编写代码）。

课本中使用队列来存储每个多项式正是利用了用户输入的指数是降幂排列的

这个特点（直接对队列的首尾进行操作）。这样简化后并巧妙的利用队列，使

得多项式运算的算法相对简单。

多项式的加法和减法运算简单的说就是比较多项式的指数，然后把指数相同的项对应的系数相加减。

课本中实现的多项式算法使用的数据结构

（1）栈：第一个实验已经实现了一个简单的栈，在这个实验中可以直接使用，或者使用标准模板库中的stack。为了保存多个多项式，使用了栈（用栈是为了进行多个多项式的加减）。在进行多项式运算的时候，是让弹出栈顶的两个元素（多项式）进行运算（加、减等），再把结果压回栈中。实现多个多项式连续的加减法，这部分内容是选做。

本实验仅需要实现两个多项式的加减法就可以。

（2）队列：用一个队列保存用户输入的一个多项式。课本中已经基本实现了一个队列，

简单的添加一些成员就可以使用了，或者使用标准模板库中的queue

实验题目文档中给出了用户输入输出的几个函数，直接就可以使用了。但是需要自己编写实现一个多项式类。

注意

本次实验看上去简单，比如书上已经有绝大部分代码，而且没有的一些代码在英文的实验题目文档中也是给出了，自己要做的看上去只是要将书上的代码组织起来，并且添加一个多项式的减法函数就可以了。但是，需要注意，书上有关队列，栈的代码比较分散，而且，如果要使用书上代码的结构会涉及多个类（栈，队列，多项式类），还涉及到继承，如果对于c++并不熟悉，完全照书上的代码实现起来会有难度。

为了顺利完成实验，可以使用标准模板库中的栈和队列来进行算法实现，可以看看附录1，2，3

建议大家自己参考书上的算法，然后自己写代码，而不是仅仅简单的将书上的代码简单的照搬敲打到电脑中（前面介绍了，直接使用书上的代码并没有看上的那样简单）。自己写代码的时候可以使用标准模板库中的栈和队列，不需要自己从头再编写栈和队列的代码了。

附录1：stack

// stack_pop.cpp

#include

#include

int main( )

{

using namespace std;

stack s1, s2;

s1.push( 10 );

s1.push( 20 );

s1.push( 30 );

stack ::size_type i;

i = s1.size( );

cout << "The stack length is " << i << "." << endl;

i = s1.top( );

cout << "The element at the top of the stack is "

<< i << "." << endl;

s1.pop( );

i = s1.size( );

cout << "After a pop, the stack length is "

<< i << "." << endl;

i = s1.top( );

cout << "After a pop, the element at the top of the stack is "

<< i << "." << endl;

}

结果

The stack length is 3.

The element at the top of the stack is 30.

After a pop, the stack length is 2.

After a pop, the element at the top of the stack is 20.

// stack_empty.cpp

#include

#include

int main( )

{

using namespace std;

// Declares stacks with default deque base container

stack s1, s2;

s1.push( 1 );

if ( s1.empty( ) )

cout << "The stack s1 is empty." << endl;

else

cout << "The stack s1 is not empty." << endl;

if ( s2.empty( ) )

cout << "The stack s2 is empty." << endl;

else

cout << "The stack s2 is not empty." << endl;

}

结果

The stack s1 is not empty.

The stack s2 is empty.

附录2：queue

back：Returns a reference to the last and most recently added element at the back of the queue. Empty：Tests if the queue is empty.

Front：Returns a reference to the first element at the front of the queue.

Pop：Removes an element from the front of the queue.

Push：Adds an element to the back of the queue.

Size：Returns the number of elements in the queue.

// queue_pop.cpp

#include

#include

int main( )

{

using namespace std;

queue q1, s2;

q1.push( 10 );

q1.push( 20 );

q1.push( 30 );

queue ::size_type i;

i = q1.size( );

cout << "The queue length is " << i << "." << endl;

i = q1.front( );

cout << "The element at the front of the queue is "

<< i << "." << endl;

q1.pop( );

i = q1.size( );

cout << "After a pop the queue length is "

<< i << "." << endl;

i = q1. front ( );

cout << "After a pop, the element at the front of the queue is "

<< i << "." << endl;

}

结果：

The queue length is 3.

The element at the front of the queue is 10.

After a pop the queue length is 2.

After a pop, the element at the front of the queue is 20.

附录3：

下面的代码是简单演示多项式类继承于标准模板库中的栈。要注意的是下面的代码仅仅是演示，并没有将各个类分开为多个文件，自己编写代码的时候注意，多项式类用一个.h和一个.cpp文件实现，main函数放在另一个.cpp文件中。以后的代码示例也是如此，不再详述#include

#include

using namespace std;

class Polynomial:private queue

{

public:

myFun();

};

Polynomial::myFun()

{

push(2);

cout<

}

void main()

{

Polynomial a;

a.myFun();

}

下面的代码演示多项式类中包含一个队列，该成员队列就是用于存放多项式的数据信息的。#include

#include

using namespace std;

struct Node

{

int exp;

float coef;

};

class Polynomial

{

public:

myFun();

private:

queue m_queue;

};

Polynomial::myFun()

{

Node node;

node.exp=2;

node.coef=5;

m_queue.push(node);

Node nodeFromQueue=m_queue.front();

cout<

<

}

void main()

{

Polynomial a;

a.myFun(); }

实验教案实验三走迷宫

重点：

一些数据结构的设计，如何更好的根据算法设计数据结构。

难点：

1.根据算法，设计相应的数据结构，以便于程序的编写。比如需要理解为什么迷宫用二维

数组表示且该二维数组的维数大于实际的迷宫大小

2.弄清回溯算法求解迷宫路径的非递归方法

3.理解迷宫中行走方向，题目要求是8个方向。理解栈在求解该迷宫非递归算法中的作用，

以及需要将什么内容放入栈中。

具体讲解如下：

本实验主要是设计走迷宫算法，用递归和非递归两种方式完成

实验题目中详细讲述的算法是非递归算法，用栈为辅助的数据结构。这里可以使用标准模板库中的stack

1.走迷宫非递归算法的设计实现

这个算法在实验指导书中有详细的介绍，下面简单总结一下

（1）数据结构：

?用二维数组MAZE[m+2][n+2]表示迷宫的结构，数组中的值为1表示是墙，为0表

示可以走通。（用MAZE[m+2][n+2]而不用MAZE[m][n]的原因在于想表示和编写代

码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去）

?用二维数组MARK[m+2][n+2]表示迷宫是否被走过，主要是为了回溯时已经证明走

不通的路线就不要再去走了。（用MARK[m+2][n+2]而不用MARK[m][n]的原因在

于想表示和编写代码的时候简单些）

?二维数据MOVE[8][2]是为了更方便的移动到下一步，改变坐标。这个二维数组是

为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路

?用栈保存走过的路径

（2）输出：

?迷宫布局，用0表示可以走通的地方，用1表示墙

?如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通

?带有路径的迷宫布局

注意：虽然总的算法思想在实验指导书中有介绍，而且相当详细，但是需要仔细读懂的，因为英文版文档中的代码是伪代码，要自己写成用c++的语言实现。比如对于C++语言的数组下标是从0开始的。

2.走迷宫递归算法的设计实现

下面给出一个迷宫递归算法的实现

bool Maze::solve(int i, int j)

/*

Post: attempt to find a path through the maze from coordinate (i,j)

*/

{

bool finish = false;

maze[i][j] = 'X';

if (i == rowsize && j == colsize)

return true; // because we're done

if (!finish && maze[i+1][j] == '0')

finish = solve(i+1, j);

if (!finish && maze[i][j+1] == '0')

finish = solve(i, j+1);

if (!finish && maze[i-1][j] == '0')

finish = solve(i-1, j);

if (!finish && maze[i][j-1] == '0')

finish = solve(i, j-1);

if (!finish) //无法走通，那么修改原来设置的X符号，但是不设置为0，因为这个点现在已经走过

maze[i][j] = '+';

return finish;

}

在上面的算法中，迷宫的表示还是用字符1表示墙，字符0表示可以走通，用字符X 表示路径。至于＋字符，仅仅是为了表示这条路已经走过。

应该注意到在实验题目文档中的迷宫是有八个方向可以行走的，而上面的递归算法中仅仅有四个方向是可以行走的，需要改动。还有，其直接把路径放到迷宫结构数组中了，而且还多出并不需要出现的字符‘＋’。请改动上面的算法，满足实验题目文档的需要，也就是说，满足八方向行走的要求，输出的迷宫路径图中，也仅仅有三种字符（1：墙；0：可行走；X：走通的路径）。

提示：可以参照上面的非递归算法中的数据结构，专门用MARK[m+2][n+2]表示这个路是否已经走过了。

实验教案实验四树

重点：

理解按层次构造树的算法

难点：

1.理解构造二叉树具有多种方式

2.理解队列在按层次构造树中起到的作用

3.理解为什么队列中需要放置树节点的指针，而不直接是树节点

详细讲解如下：

这个实验中要求用类模板来实现树的类。需要对类模板有些了解。注意，在编写代码的时候，要将所有模板信息放在一个头文件中，并在要使用这些模板的文件中包含该头文件(如果分别用.h和.cpp实现，那就必须在使用该类的地方同时包含该.h和.cpp文件)。因为模板不是函数，模板必须与特定的模板实例化请求一起使用。若将模板成员函数放置在一个独立的实现文件中将无法运行。

本实验有三个主要任务

（1）按层次构造二叉树（要求必须按照实验指导书文档中的要求按层次构造一棵二叉树，但是实验指导书中没有描述具体的算法，这里等下会简单讲述具体的算法）（2）二叉树中按高度插入节点

（3）遍历二叉树（前根序、中根序和后根序，写出递归算法即可）

1.二叉树的构建和遍历

（1）总述

题目要求在构造树的时候，依层次（从根开始）输入树中每个结点，然后用这些结点构造树。经过分析可以看到，当一个结点被插入树中后，它还是需要保留指向它的指针的，因为，后面输入的序列中也许还有它的孩子，因此需要记录它的位置为将来把它的孩子也插入树中做准备。这样，就需要一个队列来保存这些信息（为什么用队列而不是用栈，可以想想）。每次从序列中读入一个结点数据的时候，就从队列头取出一个指向结点的指针，让这个取出的结点的左右孩子分别指向新生成的结点（为此需要再从序列中读入一个结点信息），之后删除队列的头，往队列的尾部再压入指向新生成的两个结点的指针（如果输入的结点信息为‘.’，那么就可能只压入一个结点，或者一个结点都不压入）。总的来说，队列中存放的是当前的指向树的叶子结点的指针。

上面是总体的算法思想。在实现的时候会用到的队列，这里也不要求大家再去自己实现一个有关队列的类，直接用标准模板库（STL）中的队列就可以了。需要#include STL中的queue，里面的一些成员函数如下（这里仅仅描述也许会用到的几个，具体不明白可以查找帮助文档）：

front：Returns a reference to the first element at the front of the queue.

pop：Removes an element from the front of the queue

push：Adds an element to the back of the queue

empty：Tests if the queue is empty

（2）详细算法

问题描述：按层次（从上到下，从左到右的顺序）输入树的结点，如果该结点为空，则用一个特定的值替代（比如0或者.）。例如下面的图中，输入为e b f a d . g . . c（当然为了方便输入，也可以用＃结束字符串的输入）要求构造一棵如下的二叉树

下面介绍按层次构造树的两种方法

对于如下的一棵树

输入：

为了构造上图所示的这样一棵二叉树，键盘上输入的顺序如下：

ebfad.g..c#

其中可以看到这是根据层次的一种输入，先输入第一层的结点，然后是第二层的结点，第三层….直到把所有的带信息的结点输入完。也可以看到，在输入的序列中，有.号，这是代表结点为空。注意在输入的时候，为空的结点也要这样输入进去。

构造二叉树：

方法一：用队列

queue A;

queue B;

假如我们把读入的数据放到一个队列中A，用于方便我们的后续处理，那么，在读入后，这个队列中的数据为ebfad.g..c，其中e为队列头存放的元素值（即该指针所指向的节点空

间数据域中的值为e），而点代表空指针NULL

把数据读入队列A中的方法如下，要用循环来读入所有数据：

Binary_node* tempNode=new Binary_node();

cin>>tempNode->data;

tempNode->left=NULL;

tempNode->right=NULL;

A.push(tempNode);

为了按层次的构造二叉树，我们还要使用一个队列B，这个队列中保存的是指向要有儿子结点的父亲结点的指针。

下面是这两个队列的变化和树的构造变化情况：

（1）第一步很特殊，首先是树根

Binary_node* pNode=A.front();

A.pop();

B.push(pNode);

A：bfad.g..c

B：e

树：

（2）后面的每一步都是从A中取出两个队首，放入B队列尾部（如果为NULL则不放）。从B中取出队首，队列A中取出的元素正好是B中取出元素的小孩子

Binary_node* pfather= B.front();

B.pop();

Binary_node* pLchild= A.front();//先出来的是左孩子

A.pop();

Binary_node* pRchild= A.front();

A.pop();

pfather->left=pLchild;

pfather->right=pRchild;

//先放入左孩子

if(pLchild!=NULL)

{

B.push(pLchild);

}

if(pRchild!=NULL)

{

B.push(pRchild);

}

A：ad.g..c

B：bf

树：

（3）

A：.g..c

B：fad

树：

（4）

A：..c

B：adg

树：

（5）

A：c

B：dg

树：

（6）

A：空（当队列A为空的时候整个算法结束，树构造成功）B：g

树：

方法二：用数组

给树的结点按层次从上到下，从左到右编号（编号从1开始，空节点也要编号），利用父亲跟小孩的编号的关系来编写代码。即节点的编号除以2，得到的商代表这该节点父亲节点的编号，得到的余数为0，则表示该节点为父亲的左孩子，若得到的余数为1，则表示该节点为父亲的右孩子。

实现方法可以为，（1）为每个节点分配空间；（2）定义一个一维数组，该数组中存放的元素为指向节点的指针，将每个分配好空间的节点的指针放入该一维数组中（3）逐一访问节点，确定节点的父子关系。当除了根节点外，每个节点的父亲都确定后，这颗二叉树就构造好了。

两种方法分析：

用队列的方法，实现有点难度，但是灵活。数组的方法，实现比较简单，但是有局限性。

2.二叉树结点的插入

简单的说就是根据二叉树的高度，进行结点的插入，把结点插入到高度最小的二叉树分叉上。这也是教科书中的一个习题。其中需要计算二叉树左右分支的高度。

（1）计算树的高度的关键代码如下，采用的是递归调用：

计算树的高度函数

{

如果寻找到的结点为空（空子树），则返回树的高度为0

否则进行下面的步骤

1.计算左子树的高度

2.计算右子树的高度

3.返回左右子树中高度最大的+1。

}

（2）插入结点的算法如下，采用的是递归调用

插入结点函数

{

如果找到的结点为空（空子树），则插入结点

否则进行下面的步骤

{

如果右子树的高度小于左子树的高度，则往右子树插入结点

如果右子树的高度大于等于左子树的高度，则往左子树插入结点}

}

注意事项：

1、辅助构造树的队列中放的要是指向树结点的指针

2、对于c＋＋不熟悉的同学，如果使用模板类，会有很大难度，建议大家如果对于c＋＋不熟悉，则不用模板类，用普通的类实现也是允许的

实验教案实验五图

重点：

图的存储结构

Dijkstra求图的最短路径算法

Prim求图的最小生成树算法

难点：

1.理解Dijkstra求图的最短路径算法

2.理解Prim求图的最小生成树算法

3.编程实现上述两种算法中，需要用到的辅助数据结构，图是如何表示的，以及最后的结

果存放在哪里

详细讲解如下：

在教科书中已经有图的类，要求编写代码实现让用户依次输入图中每个顶点并和此顶点相邻的点，存储为邻接矩阵的形式。

图的存储：用邻接矩阵，这样会方便不少。

邻接矩阵是一个二维数组，数组中的元素是边的权（一些数值），数组下标号为结点的标号。（1）例如二维数组中的一个元素M[5][6]的值为39，则表示结点5、6连接，且其上的权值为39。

（2）用邻接矩阵存储图，对图的读写就简单了。因为邻接矩阵就是一个二维数组，因此对图的读写就是对二维数组的操作。只要能弄清楚边的编号，就能把图读入了。

用一对结点表示边（也就是输入的时候输入一对结点的编号）

1.Dijkstra生成最短路径

书上给出了完整的求最短路径的源代码。总的来说的不断添加点的过程，把距离原点路径最短的点添加（通过做标记的方法）并更新没有做标记的图中点距离原点的距离，直到所有的点都做了标记。

自己编写代码的时候注意，书上仅仅是给出了最短路径的源代码，离一个完整的程序还有距离，其中要补充图的读写的函数和定义一些常量。关键是要明白书上代码的意思。比如图的节点的标号用整型变量就可以了（typedef int Vertex;）

程序输入输出示例如下：见书585页图12.10

软件工程数据结构实验教案

实验教案实验一栈和队列 重点： 1.掌握如何使用STL中的栈 2.掌握如何自己编写栈的代码 难点： 用数组实现栈的原理，并能用c++描述 具体实验讲解如下： 本实验是要通过几段代码的编写，熟悉栈和队列的编写和应用 在实验指导书中有4个题目，其中题目1、2、3是关于栈的，题目4是关于队列的。其中题目1难度小，题目2和题目3是有联系的，经过努力可以做出，但是题目4难度大些，属于选作内容 1.题目一（STL中的栈） 读懂实验指导书中的Task1中的程序（使用栈进行序列的顺序反转），并编译运行，通过此了解如果要实现一个栈类，里面需要的基本的成员函数。这个程序在书上也有。 （1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stack numbers;中就是声明了一个栈，这个栈中存放的数据类型为double。 （2）注意要使用c++的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的： #include using namespace std; 2.题目二、题目三（自己编写栈） 这里可以把题目二和题目三合成一个题目，在一个程序中完成就可以了。 合并后的题目如下：自己编程程序实现一个简单的栈，并用于替换题目1中对标准模板库中的栈的使用，同时对自己实现的栈的功能进行扩充，添加实现如下几个函数 (a) clear (b) full (c) size。 使用新添加的栈函数，显示在进行数字序列反转时输入的十进制数的个数。 注意： (1)实验题目文档中已经把大部分的代码都给出来了。栈可以用链表或者数组实现，这里是 用数组实现。 (2)实验题目中给出的仅仅是部分的代码，自己还需要在看懂的前提下，进行修改补充，才 可以达到具体的要求，不明白的地方也可以参考书上这一部分。 一些补充代码如下：

软件工程实验教案网络

课程教案 课程名称：软件工程实验 任课教师：陈利平 所属院部：计算机与信息科学学院 教学班级：计科1301-02网络1301-03 教学时间：2015－2016 学年第2 学期 湖南工学院

课程基本信息

实验一Microsoft Visio软件的使用(选做) 一、实验目的 1.熟悉Visio的工作环境及组成； 2.掌握用Visio软件绘制图表的基本操作； 3.能熟练全用Visio软件绘制各种较复杂的专业图表； 4.掌握各种图表文档创建方法. 二、实验环境 1.安装有Microsoft Visio 2010软件的计算机系统； 2.准备将使用Microsoft Visio 2010绘制图。 三、实验内容 1．熟悉Microsoft Visio 2010的建模环境； 2．根据教材和实验老师的演示，从教材或实验指导书中找到一个数据流图，用Microsoft Visio将它画出。可以使用实验指导书的图1-5所示的数据流图. 3．根据教材和实验老师的演示，从教材或实验指导书中找到一个状态图，用Microsoft Visio将它画出。可以使用实验指导书的图1-9所示的状态图。 4．根据教材和实验老师的演示，从教材或实验指导书中找到一个E-R图，用Microsoft Visio将它画出。可以使用实验指导书的图1-19所示的实体关系图。 四、实验注意事项 在实验过程中，要注意观察Microsoft Visio相关操作的实现。 五、实验成果 完成实验后，每人提供一份实验报告，简述Microsoft Visio的使用、特点、组成及安装要点，重点说明其建模环境及使用，至少包含三个已绘制的Microsoft Visio文件。 六、实验思考 1.反复练习Microsoft Visio绘制各种图。 实验后记： 实验一Microsoft Visio软件的使用(选做) 一、实验目的 1.熟悉Visio的工作环境及组成；

山东大学数据库实验答案2—8

山东大学数据库实验答案2—8 CREATE TABLE test2_01 AS SELECT SID, NAME FROM pub.STUDENT WHERE sid NOT IN ( SELECT sid FROM pub.STUDENT_COURSE ) CREATE TABLE test2_02 AS SELECT SID, NAME FROM PUB.STUDENT WHERE SID IN ( SELECT DISTINCT SID FROM PUB.STUDENT_COURSE WHERE CID IN ( SELECT CID FROM PUB.STUDENT_COURSE WHERE SID='200900130417' ) ) CREATE TABLE test2_03 AS

select SID,NAME from PUB.STUDENT where SID in ( select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where FCID='300002') ) CREATE TABLE test2_04 AS select SID,NAME from PUB.STUDENT where SID in ( select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where NAME='操作系统') intersect select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where NAME='数据结构') ) create table test2_05 as with valid_stu(sid,name) as ( select SID,NAME from PUB.STUDENT where AGE=20 and SID in (select SID from PUB.STUDENT_COURSE) ) select sid,name as name,ROUND(avg(score)) as avg_score,sum(score) as sum_score from PUB.STUDENT_COURSE natural join valid_stu where SID in (select SID from valid_stu) group by SID,NAME create table test2_06 as

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出

现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的

实验指导-数据结构B教案资料

实验指导-数据结构B

附录综合实验 1、实验目的 本课程的目标之一是使得学生学会如何从问题出发，分析数据，构造求解问题的数据结构和算法，培养学生进行较复杂程序设计的能力。本课程实践性较强，为实现课程目标，要求学生完成一定数量的上机实验。从而一方面使得学生加深对课内所学的各种数据的逻辑结构、存储表示和运算的方法等基本内容的理解，学习如何运用所学的数据结构和算法知识解决应用问题的方法；另一方面，在程序设计方法、C语言编程环境以及程序的调试和测试等方面得到必要的训练。 2、实验基本要求： 1）学习使用自顶向下的分析方法，分析问题空间中存在哪些模块，明确这些模块之间的关系。 2）使用结构化的系统设计方法，将系统中存在的各个模块合理组织成层次结构，并明确定义各个结构体。确定模块的主要数据结构和接口。 3）熟练使用C语言环境来实现或重用模块，从而实现系统的层次结构。模块的实现包括结构体的定义和函数的实现。 4）学会利用数据结构所学知识设计结构清晰的算法和程序，并会分析所设计的算法的时间和空间复杂度。 5）所有的算法和实现均使用C语言进行描述，实验结束写出实验报告。

3、实验项目与内容： 1、线性表的基本运算及多项式的算术运算 内容：实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。 要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。 2、二叉树的基本操作及哈夫曼编码译码系统的实现 内容：创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。哈夫曼编码/译码系统。 要求：能成功演示二叉树的有关运算，实现哈夫曼编码/译码的功能，运算完毕后能成功释放二叉树所有结点占用的系统内存。 3、图的基本运算及智能交通中的最佳路径选择问题 内容：在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法，实现图的深度和宽度优先遍历算法，解决智能交通中的路径选择问题。设有n 个地点，编号为0~n-1，m条路径的起点、终点和代价由用户输入提供，寻找最佳路径方案（例如花费时间最少、路径长度最短、交通费用最小等，任选其一即可）。 要求：设计主函数，测试上述运算。 4、各种内排序算法的实现及性能比较 内容：验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求：使用随机数产生器产生较大规模数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。

山东大学《数据库系统》上机实验答案 详细整理 2013最新版

数据库实验（一） 熟悉环境、建立/删除表、插入数据 Drop table 表名 update dbtest set test=1 select * from dbscore 1．教师信息(教师编号、姓名、性别、年龄、院系名称) test1_teacher：tid char 6 not null、name varchar 10 not null、sex char 2、age int、dname varchar 10。 根据教师名称建立一个索引。 1、create table test1_teacher( tid char(6) primary key, name varchar(10) not null, sex char(2), age int, dname varchar(10) ) 2．学生信息（学生编号、姓名、性别、年龄、出生日期、院系名称、班级）test1_student：sid char 12 not null、name varchar 10 not null、sex char 2、age int、birthday date（oracle的date类型是包含时间信息的，时间信息全部为零）、dname varchar 10、class varchar(10)。 根据姓名建立一个索引。 2、create table test1_student(

sid char(12) primary key, name varchar(10) not null, sex char(2), age int, birthday date, dname varchar(10), class varchar(10) ) 3．课程信息（课程编号、课程名称、先行课编号、学分） test1_course：cid char 6 not null、name varchar 10 not null、fcid char 6、credit numeric 2，1（其中2代表总长度，1代表小数点后面长度）。 根据课程名建立一个索引。 3、create table test1_course( cid char(6) primary key, name varchar(10) not null, fcid char(6), credit numeric(2,1) ) 4．学生选课信息（学号、课程号、成绩、教师编号） test1_student_course：sid char 12 not null、cid char 6 not null、 score numeric 5，1（其中5代表总长度，1代表小数点后面长度）、tid char 6。 4、 create table test1_student_course( sid char(12) , cid char(6) , score numeric(5,1), tid char(6), primary key(sid,cid),

山东大学操作系统实验报告4进程同步实验

山东大学操作系统实验报告4进程同步实验

计算机科学与技术学院实验报告 实验题目：实验四、进程同步实验学号： 日期：20120409 班级：计基地12 姓名： 实验目的： 加深对并发协作进程同步与互斥概念的理解，观察和体验并发进程同步与互斥 操作的效果，分析与研究经典进程同步与互斥问题的实际解决方案。了解 Linux 系统中 IPC 进程同步工具的用法，练习并发协作进程的同步与互斥操作的编程与调试技术。 实验内容： 抽烟者问题。假设一个系统中有三个抽烟者进程，每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料：烟草、纸和胶水。一个抽烟者有烟草，一个有纸，另一个有胶水。系统中还有两个供应者进程，它们无限地供应所有三种材料，但每次仅轮流提供三种材料中的两种。得到缺失的两种材料的抽烟者在卷起并抽掉一颗烟后会发信号通知供应者，让它继续提供另外的两种材料。这一过程重复进行。请用以上介绍的 IPC 同步机制编程，实现该问题要求的功能。 硬件环境： 处理器：Intel? Core?i3-2350M CPU @ 2.30GHz ×4 图形：Intel? Sandybridge Mobile x86/MMX/SSE2 内存：4G 操作系统：32位 磁盘：20.1 GB 软件环境： ubuntu13.04 实验步骤： （1）新建定义了producer和consumer共用的IPC函数原型和变量的ipc.h文件。

（2）新建ipc.c文件，编写producer和consumer 共用的IPC的具体相应函数。 （3）新建Producer文件，首先定义producer 的一些行为，利用系统调用，建立共享内存区域，设定其长度并获取共享内存的首地址。然后设定生产者互斥与同步的信号灯，并为他们设置相应的初值。当有生产者进程在运行而其他生产者请求时，相应的信号灯就会阻止他，当共享内存区域已满时，信号等也会提示生产者不能再往共享内存中放入内容。 （4）新建Consumer文件，定义consumer的一些行为，利用系统调用来创建共享内存区域，并设定他的长度并获取共享内存的首地址。然后设定消费者互斥与同步的信号灯，并为他们设置相应的初值。当有消费进程在运行而其他消费者请求时，相应的信号灯就会阻止它，当共享内存区域已空时，信号等也会提示生产者不能再从共享内存中取出相应的内容。 运行的消费者应该与相应的生产者对应起来，只有这样运行结果才会正确。

《数据结构》实验指导

《数据结构》实验指导 (计算机信息大类适用) 实验报告至少包含以下内容： 实验名称 实验目的与要求: 实验内容与步骤（需要你进行细化）: 实验结果（若顺利完成，可简单说明；若实验过程中遇到问题，也请在此说明） 收获与体会（根据个人的实际情况进行说明，不得空缺） 实验1 大整数加法（8课时） 目的与要求： 1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。 2、单链表的简单应用训练。 3、熟悉标准模版库STL中的链表相关的知识。 内容与步骤: 1、编程实现单链表的基本操作。 2、利用单链表存储大整数（大整数的位数不限）。 3、利用单链表实现两个大整数的相加运算。 4、进行测试，完成HLOJ(https://www.doczj.com/doc/0c3879454.html,) 9515 02-线性表大整数A+B。 5、用STL之list完成上面的任务。 6、尝试完成HLOJ 9516 02-线性表大菲波数。 实验2 栈序列匹配（8课时） 目的与要求 1、栈的顺序存储结构及其基本运算、实现方法和技术的训练。 2、栈的简单应用训练。 3、熟悉标准模版库STL中的栈相关的知识。 内容与步骤: 1、编程实现顺序栈及其基本操作。 2、对于给出的入栈序列和出栈序列，判断2个序列是否相容。即：能否利用栈 将入栈序列转换为出栈序列。 3、进行测试，完成HLOJ 9525 03-栈与队列栈序列匹配。 4、用STL之stack完成上面的任务。 5、尝试完成HLOJ 9522 03-栈与队列胡同。

实验3 二叉排序树（8课时） 目的与要求 1、二叉树的链式存储结构及其基本运算、实现方法和技术的训练。 2、二叉树的遍历方法的训练。 3、二叉树的简单应用。 内容与步骤: 1、编程实现采用链式存储结构的二叉排序树。 2、实现插入节点的操作。 3、实现查找节点的操作（若查找失败，则将新节点插入二叉排序树）。 4、利用遍历算法对该二叉排序树中结点的关键字按递增和递减顺序输出，完成 HLOJ 9576 07-查找二叉排序树。 5、尝试利用二叉排序树完成HLOJ 9580 07-查找Let the Balloon Rise。 实验4 最小生成树（8课时） 目的与要求 1、图的邻接矩阵存储结构及其相关运算的训练。 2、掌握最小生成树的概念。 3、利用Prim算法求解最小生成树。 实验背景： 给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。要求显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 内容与步骤: 1、建立采用邻接矩阵的图。 2、编程实现Prim算法，求解最小生成树的代价。 3、尝试利用Prim算法完成：HLOJ 9561 06-图最小生成树。

山大网络教育《数据结构》(-C-卷)

山大网络教育《数据结构》(-C-卷)

《数据结构》模拟卷 一、单项选择题 1．数据结构是（）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（ B ）。 A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（ D ）。 A．插入B．删除 C．排序D．定位 4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5

C．1，2，5，3，4，6 D．5，6，4，2，3，1 5．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ D ）。 A．15 B．16 C．17 D．18 6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ A ）。 A．1207 B．1209 C．1211 D．1213 7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ）。 A．队列B．栈 C．线性表D．有序表 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ B ）。A．不一定相同B．都相同 C．都不相同D．互为逆序 9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ C ）。

2017数据结构实验指导书

《数据结构》实验指导书 贵州大学 电子信息学院 通信工程

目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109)

实验一顺序表的操作 实验学时：2学时 实验类型：验证 实验要求：必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作（建立、插入、删除等）的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型，输入一组整型数据，建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数，调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程，上机调试、得出正确的运行程序。 2、编译运行程序，观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。

【附录----源程序】 #include #include using namespace std; typedef int ElemType; struct List { ElemType *list; int Size; int MaxSize; }; //初始化线性表 bool InitList(List &L) { L.MaxSize=20; L.list=new ElemType[L.MaxSize]; for(int i=0;i<20&&L.list==NULL;i++) { L.list=new ElemType[L.MaxSize]; } if(L.list==NULL) { cout<<"无法分配内存空间，退出程序"<L.Size+1||pos<1) { cout<<"位置无效"<

软件工程测试实验

淮海工学院计算机科学系实验报告书 课程名：《软件工程》 题目：软件测试实验 班级：软件121 学号：2012122722 姓名：朱德坤

软件测试验报告要求 1目的与要求: 1）系统学习和理解结构化软件工程实现阶段的基本概念、原理、技术和方法； 2）掌握软件测试的基本技术和方法，特别是白盒测试与黑盒测试技术和方法； 3）通过实验，要逐步提高白盒测试与黑盒测试技术的实际应用能力； 4）熟悉C++编程环境下编写、调试单元代码的基本操作技术和方法； 5）按照实验题目要求独立完成本次试验任务，严禁拷贝、抄袭他人设计成果； 6）认真书写实验报告（要求给出完整的测试信息，如测试程序、测试用例，测试结果分析等），并于5月5日以前提交。 2 实验内容或题目 1.选择结构化详细设计试验中自己设计的某一具有代表性控制结构模块（含有分支和循环结 构），并用C语言实现（提前准备好，每种测试用例分别写在作业本上，上机时带上检查），而后分别完成下述2、3、4各题测试用例设计和测试结果分析； 2.采用白盒测试技术中逻辑覆盖方法（至少包含语句覆盖、判定覆盖、条件覆盖、条件组合 覆盖）设计测试用例，完成测试（测试屏幕截图）和测试结果分析； 3.采用白盒控制结构测试技术的基本路径测试和边界测试方法设计相应测试用例，并完成测 试和测试结果分析； 4.采用黑盒测试技术中的等价类划分方法设计相应测试用例（可重选适合黑盒测试技术的模 块），并完成程序测试和测试结果分析； 3 实验步骤与源程序 程序流程图:

流图：

程序: //拥有超级用户superuser，密码zdk #include #include #include #include #include using namespace std; int PD; //全局判断执行码 void SetPos(int i,int j) //界面光标位置函数{ COORD pos= {i-1,j-1}; HANDLE Out=GetStdHandle(STD_OUTPUT_HANDLE);

山东大学操作系统实验二

软件学院操作系统实验报告 实验题目： 实验二、线程和进程/线程管道通信实验 学号：201100300124 日期：2013年04月19日 班级：5班姓名：韩俊晓 Email：hanjunxiao188@https://www.doczj.com/doc/0c3879454.html, 实验目的： 通过Linux 系统中线程和管道通信机制的实验,加深对于线程控制和管道通信概念的理解,观察和体验并发进/线程间的通信和协作的效果,练习利用无名管道进行进/线程间通信的编程和调试技术。 实验要求： 设有二元函数f(x,y) = f(x) + f(y) 其中：f(x) = f(x-1) * x(x >1) f(x)=1(x=1) f(y) = f(y-1) + f(y-2)(y> 2) f(y)=1(y=1,2) 请编程建立3个并发协作进程（或线程），它们分别完成f(x,y)、f(x)、f(y) 其中由父进程（或主线程）完成：f(x,y) = f(x) + f(y) 由子进程1（或线程1）完成：f(x) = f(x-1) * x(x >1) f(x)=1(x=1)

由子进程2（或线程2）完成：f(y) = f(y-1) + f(y-2)(y> 2) f(y)=1(y=1,2) 硬件环境： 实验室计算机 软件环境： Ubuntu08.4－Linux操作系统 BASH_VERSION='3.2.33(1)-release gcc version 4.1.2 gedit 2.18.2 OpenOffice 2.3 实验步骤： 1.实验说明： 1）与线程创建、执行有关的系统调用说明 线程是在共享内存中并发执行的多道执行路径,它们共享一个进程的资源,如进程程序段、文件描述符和信号等,但有各自的执行路径和堆栈。线程的创建无需像进程那样重新申请系统资源,线程在上下文切换时也无需像进程那样更换内存映像。多线程的并发执行即避免了多进程并发的上下文切换的开销又可以提高并发处理的效率。 Linux 利用了特有的内核函数__clone 实现了一个叫phread 的线程库,__clone是fork 函数的替代函数,通过更多的控制父子进程共享哪些资源而实现了线程。Pthread 是一个标准化模型,用它可把一个程序分成一组能够并发执行的多个任务。phread 线程库是POSIX 线程标

数据结构实验指导书及答案(徐州工程学院)

《数据结构实验》实验指导书及答案

信电工程学院计算机科学和技术教研室编 2011.12 数据结构实验所有代码整理 作者郑涛 声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ps:重点知识最好让孙天凯给出），希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的 不好的地方请大家谅解并欢迎予以指正。 实验一熟悉编程环境 实验预备知识： 1．熟悉本课程的语言编译环境（TC或VC），能够用C语言编写完整的程序，并能够发现和改正错误。 2．能够灵活的编写C程序，并能够熟练输入C程序。 一、实验目的 1．熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。 2．能够熟练的将C程序存储到指定位置。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。 ⒉软件：Windows操作系统+Turbo C； 三、实验要求 1．将实验中每个功能用一个函数实现。 2．每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280和100的和是：380。）。 3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。 四、实验内容 1．在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。

2．编写一个输入某个学生10门课程成绩的函数（10门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。 3．编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有多个最高成绩，则每个最高成绩均输出。 4．编写一个求10门成绩平均成绩的函数。 5．编写函数求出比平均成绩高的所有课程及成绩。 #include #include struct subject { int subject_id; char subject_name[20]; double subject_grades; }; struct subject sub[10]; void input() { int i; printf("please input:\n"); for(i=0;i<10;i++) { scanf("%d %s %lf",&sub[i].subject_id,&sub[i].subject_name,&sub[i].subject_g rades); } printf("you just input:\n"); for(i=0;i<3;i++) { printf("%d %s %lf\n",sub[i].subject_id,sub[i].subject_name,sub[i].subject_g rades); } } void subject_max() { int i,flag; double max=sub[0].subject_grades; for(i=0;i<10;i++) { if(sub[i].subject_grades>max)

(完整版)数据结构详细教案——图

数据结构教案第七章图

第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)

数据结构实验指导书(C版)

数据结构实验指导书（C语言版） 2017年9月

目录 1、顺序表的实现 (1) 2、链栈的实现 (3) 3、前序遍历二叉树 (5) 4、图的深度优先遍历算法 (7) 5、散列查找 (9)

1、顺序表的实现 1. 实验目的 ⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现； ⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。 2. 实验内容 ⑴建立含有若干个元素的顺序表； ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示 定义顺序表的数据类型——顺序表结构体SeqList，在SeqList基础上实现题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。简单起见，本实验假定线性表的数据元素为int型，要求学生： （1）将实验程序调试通过后，用模板类改写； （2）加入求线性表的长度等基本操作； （3）重新给定测试数据，验证抛出异常机制。 4. 实验程序 在编程环境下新建一个工程“顺序表验证实验”，并新建相应文件，文件包括顺序表结构体SeqList的定义，范例程序如下： #define MaxSize 100 /*假设顺序表最多存放100个元素*/ typedef int DataType; /*定义线性表的数据类型，假设为int型*/ typedef struct { DataType data[MaxSize]; /*存放数据元素的数组*/ int length; /*线性表的长度*/ } SeqList; 文件包括建立顺序表、遍历顺序表、按值查找、插入操作、删除操作成员函数的定义，范例程序如下： int CreatList(SeqList *L, DataType a[ ], int n) { if (n > MaxSize) {printf("顺序表的空间不够，无法建立顺序表\n"); return 0;} for (int i = 0; i < n; i++) L->data[i] = a[i]; L->length = n; return 1; }

《数据结构》实验1实验报告

南京工程学院实验报告 操作的函数程序清单，分别用顺序表和链表结构完成，并在首页上表明团队名称、成员及个人的工作（函数），未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用（main函数程序清单） 程序1的主要代码(附简要注释) #include "stdio.h" #include "malloc.h" #define SUCCESS 1 #define FAILURE 0 #define null 0 #define maxsize 100 typedef int datatype; typedef struct /*定义线性表（顺序结构）数据类型*/ { datatype data[maxsize]; int last; }sequenlist; int n; /*定义功能选择菜单函数*/ void print() { printf("----线性表（顺序结构）的基本操作----\n"); printf("----------开始----------\n"); } /*打印线性表（顺序结构）*/

软件工程实验教学大纲

《软件工程》实验教学大纲 课程代码：0668036 课程名称：软件工程/Software Engineering 开课院（系）实验室：计算机科学系；软件实验室、信息安全实验室 适用专业：计算机科学与技术、信息与计算科学、信息安全 实验指导书名称：《软件工程实验指导书》 一、学时、学分 总学时：64 总学分：4 讲课学时：48 实验学时：16 实验成绩占总成绩20 % 二、课程简介 软件工程是计算机科学与技术等专业开设的一门必修课，是软件开发类的综合性和实践性很强的核心课程。本课程从系统工程的角度介绍软件工程方法，使学生掌握软件工程的基本理论、方法和技术，以及软件开发的完整过程和步骤，掌握软件生命周期中各阶段的知识，并能够使用UML进行软件分析和设计。培养学生初步具有中小型软件项目的需求分析、设计、编码、测试、维护和管理的工程化能力，以及软件开发和项目管理能力，为今后更深入地学习和从事软件开发工作打下良好的基础。 三、实验的地位、作用和目的及学生能力标准 本实验课程是《软件工程》课程教学的重要组成部分。通过本实验课程的教学，使学生加深对面向对象分析与设计的理解，从而掌握如何把统一建模语言UML应用到基本的面向对象分析和设计乃至整个软件开发过程中。 软件工程课程实验的目的是让学生掌握求解软件的基本思想、途径和方法，为从事计算机软件开发、维护和应用奠定良好的基础。学生通过软件工程课程实验，掌握软件分析、设计、实现和测试的基本技术，以及面向对象分析和设计的基本方法。通过该课程实践，实际运用软件工程的技术和方法，掌握软件项目管理和团队开发的工作方法。 经过软件工程课程的实验环节，使学生进一步掌握面向对象的系统设计与开发的方法和技术，树立团队合作精神，培养自主学习能力和创造性的工程设计能力，提高综合分析和解决问题的能力，以及软件项目的管理能力。此外，在实验环节中，还应深入了解面向对象分析和设计的基本概念，UML 在面向对象分析和设计中的作用，UML 的基础知识和应用技术，学会如何使用UML 对系统建模，掌握软件建模工具Rational Rose 的使用。 四、实验方式与基本要求 本实验课程要求学生在教师的指导与帮助下，学习了解UML的基本概念，实践UML对系统进行分析和设计的开发过程。以“网上图书销售系统”为案例，使学生经历软件项目的可行性研究、需求分析，软件设计、实现、测试到维护等各阶段的软件生命过程。 基本要求是：在实验初期，学生要在教师指导下自学Rational Rose软件的安装、使用和操作方法，并能运用Rational Rose完成课程全部实验内容；在每个实验开始之前，要求学生预先针对课堂相关知识进行深入思考、分析、讨论，按实验题目要求给出初步的软件需求分析模型和设计模型；在实验过程中按照实验步骤积极动手进行实验操作，按各个实验的具体要求完成和提交实验成果。 “网上图书销售系统”功能需求： （1）查询图书信息：顾客登录该系统后，可根据书名对所需的图书信息进行查询。