?(n)。

课题一的具体实验内容

1、构造元素类型为整型的线性表，将以下元素插入分别插入线性表：

<34 56 20 9 15 5> 2、查找表中是否存在元素20，实现元素20与元素9的交换；

3、按照课题要求编写函数，实现线性表元素<34 56 9 20 15 5>的倒置，即倒置后的表应为< 5 15 20 9 56 34 >。

*实验课题二：约瑟夫（Josephus）问题的求解（循环链表的使用，使用C和C++语言均可）。

假设有编号为1，2，??，n的n个人围坐成一圈，约定从编号为k（n>=k>=1）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。

1、给定一个8个人的圈（n=8），约定从第3个人开始报数（k＝3），数到第4个人时的那个人出列（m＝4），使用循环链表，产生一个出队编号的序列。 2、参考的出队序列为：< 6 2 7 4 3 5 1 8 >。

实验步骤：

1、 在“F:\DataStru\”目录下面创建自己以自己学号作为名字的文件夹。自己所有的实验程

序均放在该文件夹下面。

2、 创建项目，文件保存到第1步说的目录。

3、 每台计算机的教材参考代码在“E：DataStru\”，先解压至“F:\DataStru\”。

4、 通过“工具/选项/vc++目录/包含文件”把相应的F:\DataStru\”的代码包含进去，以便编

程的时候，包含相关头文件，或参考测试程序。

5、 弄懂教材参考代码中给出的线性表类（c++）或线性表结构体以及与之相关的函数（c）;

构造一个表，进行实验要求的课题。

实验二 栈

【实验目的】

1、 掌握栈的LIFO（后进先出）特点和栈的存储结构； 2、熟悉栈的各种操作；

3、掌握栈的应用方法，理解栈的重要应用；

4、根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。

【实验原理】

栈是一种特殊的线性表，这种线性表只能在固定的一端（称为栈顶（top））进行插入和

删除操作。由于只允许在栈顶进行插入和删除操作，所以栈的操作是按照“后进先出”（Last In First Out，缩写为LIFO）原则进行的。本实验要求用栈作为基本的数据结构解决各实验课题。

【实验要求】（实验课题一必做，其他选做）

实验课题一： 将一个十进制数转换成另外一个P进制数字符串（可以是二进制到十六进制）。转换函数的原型为：

void Convert (int n, char str[], unsigned P); n：输入，待转换的数

str：输出，转换好的P进制字符串

P：输入，要转换的进制，取值可从2到16。如果在这范围之外，可认为输入错，不做转换。 将一个整数转换成P进制的数，我们可以采用如下的方法：

例：十进制转换成八进制（P等于8）：(66)10=(102)8 66/8=8 余 2 8/8 =1 余 0 1/8 =0 余 1

当商为0时转换结束，转换结果为上述过程余数序列的逆序：102。

先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的LIFO性质，故可用栈来实现数制转换。

*实验课题二：用2个栈实现一个队列，并对使用这种方法实现的队列执行入队、出队操作的时间进行分析。

用C实现的同学，应该实现教科书第76页Figure 3.56（参考代码的queue.h）中定义的队列类型的那些操作函数；

用C++实现作为ADT的队列，应以以下抽象类VQueue作为与用户的界面接口： template <typename Object> class VQueue { public: };

出队函数dequeue()有2个原型，如Queue<int>Q; int x; x = Q.front(); Q.dequeue (); 等价于Q.dequeue(x); 前面的用法符合STL的习惯，后面一个有时会觉得方便，所以2个都放在接口里。

*实验课题三： 将一个普通代数表达式（infix expression）转换为后缀表达式（postfix expression）。转换规则描述参见：描述C语言描述的课本pp.68-71，C++语言描述的课本pp.99-102。

栈的ADT接口：

用C++描述的教科书中没给栈的ADT，可以用以下Stack类模版： template <typename Object> class Stack { public:

bool empty( ) const { return theList.empty( ); } const Object & top( ) const { return theList.front( ); } void push( const Object & x ) { theList.push_front( x ); } void pop( Object & x )

{ x = theList.front( ); theList.pop_front( ); } void pop( )

{ theList.pop_front( ); } private:

List<Object> theList; };

virtual void enqueue (const Object&) = 0; virtual void dequeue (Object&) = 0; virtual void dequeue () = 0;

virtual const Object& front () const = 0; virtual bool empty () const = 0;

在本实验中，也只用＋、＊、（、）作为算符，优先级自低至高为＋、*、（）。

实验三 队列

【实验目的】

1、 掌握队列的FIFO的特点（先进先出）特点和队列的存储结构； 2、熟悉队列的各种操作；

3、掌握队列的应用方法，理解队列的重要应用； 4、根据实验要求设计并完成程序。

【实验原理】

队列是限定只能在表的一端进行插入，而在表的另一端进行删除的线性表。是一种“先

进先出”（First In First Out，缩写为 FIFO）的线性表。队列可以有多种实现形式，本实验要求将队列作为一个抽象数据类型（ADT）来解决各实验课题。

【实验要求】（实验课题一必做，课题二选做）

实验课题一：回文（palindrome）是指一个字符串从前面读和从后面读都一样，仅使用若干栈和队列、栈和队列的ADT函数以及若干个int类型和char类型的变量，设计一个算法来判断一个字符串是否为回文。假设字符串从标准输入设备一次读入一个字符，算法的输出结果为true或者false。

可以用一些字符串测试输出结果，如： "abcdeabcde"， "madamimadam" 等

实验课题二：打印扬辉三角形。

打印二项式 ( a + b )i 的展开系数，也就是扬辉三角，国外叫做Pascal's triangle。如右下图为扬辉三角的前8行数据。

按照如右图所示的方式，完成对应杨辉三角的打印输出。

1 1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

杨辉三角