约瑟夫环——栈性表的应用

《算法与数据结构》实验报告实验一约瑟夫环问题（2学时）将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。

报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

实验二链表的操作（4学时）编一程序：①建立一个数据域为1至10的带头结点的链表；②将此链表就地逆转。

链表的类型说明如下：#include <iostream.h>#include <stdlib.h>class Node{public:int data;Node *next;Node( ){next=0;}friend class LinkList;};//Nodeclass LinkList {Node *head;public:LinkList( ) { head=new Node(); }void Create(); //创建长度为n的单链表int GetElem(int i); //返回第i个元素值Node* Locate(int e); //返回第一个与e匹配的元素结点指针bool IsEmpty( ) {return (head->next==0);} //判断是否为空链表void Insert(int x, int i ); //在第i个结点之前插入元素值为x的结点int Delete ( int i ); //删除第i个结点，并返回其元素值void Clear( ); //清空链表void print( );};// LinkList实验三栈的应用－中缀表达式的求值（4学时）表达式求值是计算机实现程序设计语言中的基本问题之一，也是栈应用的一个典型例子，通过本实验，对输入的一个表达式进行求值。

说明：表达式中只包含＋、－、×、/ 运算及（和）。

栈是一种特殊的线性表，特殊之处在于插入和删除操作的位置受到限制，若插入和删除操作只允许在线性表的一端进行，则是栈，特点是后进先出。

栈的抽象数据模型：栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，允许操作的一端称为栈顶（top）不允许操作的一端称谓栈底（Bottom）,栈中插入元素操作称为入栈（push）,删除元素的操作称为出栈（pop）,没有元素的栈称为空栈、例如对数据序列｛A,B,C,D｝执行操作序列｛入栈，出栈，入栈，入栈，出栈，出栈。

出栈｝,出栈序列为｛B,D,C,A｝栈机器状态如图：由于栈的插入和删除操作只允许在栈顶进行，每次入栈元素即成为栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈的特点是后进先出（Last In First Out）,就像一落盘子，每次将只有一个盘子在最上面，从最上面取走一个盘子，不能从中间插入或者插出。

栈的基本操作有创建栈，判断是否为空，入栈，出栈，和取出栈顶元素等。

栈不支持对指定位置的插入，删除等。

顺序栈采用顺序存储结构的栈称为顺序栈｛Sequential Stack｝,声明顺序栈如下，实现栈接口，使用顺序表作为成员变量实现栈，约定null不能入栈。

其中，入栈和出栈操作实现为顺序表尾部插入和尾部删除，时间复杂度为O(1),顺序表的插入方法已经实现自动扩充数组容量，当需要扩充容量时，入栈的时间复杂度为O(n)栈和线性表是不同的数据抽象类型，栈概念不依赖于线性表而存在，我们只是使用顺序表进行设计，也可以使用数组实现。

链式栈采用连式存储结构的栈称为链式栈（Linked Stack），单链表结构的链式栈及入栈，出栈操作如图，设单链表（不带头节点）头指针top指向第一个元素节点（栈顶），入栈操作是头插入，在栈顶节点之前插入节点，出栈操作是头删除，删除栈顶节点并返回栈顶元素，再使top指向新的栈顶节点。

声明链式栈类如下，实现栈接口。

使用单链表作为成员变量实现栈。

摘要：本学期我完成的主要实验任务有:实验一对比算法的时空效率之裴波那契序列、实验二线性表及其应用之约瑟夫环、实验三栈和队列之算术表达式求值、实验四树和二叉树之层序遍历二叉树以及实验五排序之学生成绩统计程序，文档内容为对本学期的五次实验进行概要介绍、综合分析以及自我评价。

并且对本学期所写程序提供相关数据结构理论和对本课程的相关建议。

关键字：Data Structure数据结构stack栈tree 树binary tree二叉树queue 队列linear list线性表sort排序algorithm算法正文：实验开发环境及工具：1.软件环境：Microsoft Windows 7 旗舰英文版Microsoft Visual C++6.0编译器2.硬件环境：Genuine Intel(R) CPU U2700 @ 1.30GHz1.30GHz,1.86 GB 的内存320G硬盘（含隐藏分区）物理地址扩展郑重声明:本电脑无光驱，携带相当便捷重量：1.6kg(含电池)型号：Lenovo U350实验一实验名称:实验一对比算法的时空效率之裴波那契序列实验目的及要求：1.熟悉开发工具的编程环境。

2.体会算法和程序的不同。

3.学习用不同算法实现同一程序功能，并能熟练编程实现。

4.学习分析算法。

对比不同算法实现的效率有何不同，所占空间有何不同。

对比不同算法的优点和缺点。

实验主要内容：选题题目：试编写求k阶（k>=2）裴波那契序列的第m项值的不同算法，并编程实现。

k和m均以值调用的形式在函数参数中表现。

要求：至少用两种不同的算法（如，递推、递归等等）。

当k=2时，裴波那契序列的初始两项为0、1，此后序列的每个值都是前两项之和。

当k=3时，裴波那契序列的初始三项为0、0、1，此后序列的每个值都是前三项之和，以此类推。

概要设计和存储结构：k阶（k>=2）裴波那契序列的第m项值假设为temp[m]则temp[m]=temp[m-1]+temp[m-2]+……+temp[m-k]=temp[m-1]+temp[m-2]+……+temp[m-k]+temp[m-k-1]-temp[m-k-1]=temp[m-1]+{temp[m-2]+……+temp[m-k]+temp[m-k-1]}-temp[m-k-1]}=2*temp[m-1]- temp[m-k-1]采用线性表顺序结构——数组主要算法：通过temp[m]=2*temp[m-1]- temp[m-k-1]此公式采用了循环递推以及递推的方法得出结果。

第1章绪论习题一、问答题1. 什么是数据结构?2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中,类的作用是什么?9. 参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言(如C、或PASCAL)中,指针类型是原子类型。

三、计算下列程序段中XX1 的语句频度fori1iltni forj1jltij fork1kltjk xx1 提示: i1 时:1 11×1/2 112/2 i2 时:12 12×2/2 222/2 i3 时:123 13×3/2 332/2 … in 时:123……n 1n×n/2 nn2/2 fn 123……n 12 22 32 …… n2 / 2 1nn/2 nn12n1/6 / 2 nn1n2/6 n3/6n2/2n/3区分语句频度和算法复杂度:Ofn On3 四、试编写算法求一元多项式Pnxa0a1xa2x2a3x3…anxn 的值Pnx0,并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。

注意:本题中的输入aii01…n x 和n,输出为Pnx0.通常算法的输入和输出可采用下列两种方式之一:(1)通过参数表中的参数显式传递;(2)通过全局变量隐式传递。

试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出。

提示:floatPolyValuefloat a float x int n…… 核心语句:p1 x 的零次幂s0 i 从0 到n 循环ssaip ppx 或:px x 的一次幂sa0 i 从1 到n 循环ssaip ppx 实习题设计实现抽象数据类型“有理数”。

第1章绪论习题一、问答题1. 什么是数据结构?2. 四类基本数据结构的名称与含义.3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别.7. 面向对象程序设计语言的特点.8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序.3. 在高级语言(如C、或PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1；i<=n;i++）for(j=1;j〈=i;j++)for（k=1；k<=j；k++）x=x+1;［提示］：i=1时：1 = （1+1)×1/2 = （1+12）/2i=2时：1+2 = （1+2）×2/2 = （2+22)/2i=3时：1+2+3 = （1+3)×3/2 = （3+32)/2…i=n时：1+2+3+……+n = (1+n）×n/2 = （n+n2)/2f(n）= [ (1+2+3+……+n) + （12 + 22 + 32 + …… + n2 ）] / 2=[ （1+n)n/2 + n(n+1)（2n+1)/6 ] / 2=n（n+1）(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)）= O(n3)四、试编写算法求一元多项式Pn（x)=a0+a1x+a2x2+a3x3+…a n x n的值P n（x0），并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。

注意：本题中的输入a i（i=0,1，…，n), x和n，输出为P n(x0)。

通常算法的输入和输出可采用下列两种方式之一:（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

数据结构-栈⼀、栈1. 1. 为什么要学习栈？栈是什么？为什么要学习它？现在先来说说栈的辉煌作⽤吧！在计算机领域中，栈是⼀种不可忽略的概念，⽆论从它的结构上，还是存储数据⽅⾯，它对于学习数据结构的⼈们来说，都是⾮常重要的。

那么就会有⼈问，栈究竟有什么作⽤，让我们这么重视它？⾸先，栈具有⾮常强⼤的“记忆”功能，它可以保存对你有作⽤的数据，也可以被叫做保存现场；其次，当咱们调⽤⼀个带参函数时候，被调⽤的函数的形参，在编译器编译的时候，这些形参都需要⼀定的空间存放他们，这时计算机就会默认帮你保存到栈中了！1. 2. 栈的定义栈的作⽤，这是⼀个咱们⽣活中处处⽤到，但是却⼜没发现的⼀种现象，例如当你拿个篮⼦去买苹果，那么你最先挑选的苹果就是在篮⼦的最底下，最后挑选的苹果就在篮⼦的最上边，那么这就造成了这么⼀种现象：先拿进篮⼦的苹果，要最后才能取出来；相反，最后拿进篮⼦的苹果，就能最先取出来！栈是限定只能在表尾进⾏插⼊和删除的线性表。

我们把允许插⼊和删除的⼀端称作栈顶(Top)，另⼀端称作栈底(bottom)。

不含任何数据元素的栈被称作空栈，栈也被称为先进后出的线性表(具有线性关系)。

⽽栈的特殊性，就是在表中想进⾏插⼊和删除的操作，只能在栈顶进⾏。

这也就使得了：栈底是⾮常稳定的，因为先进来的元素都被放在了栈底。

栈的插⼊操作：叫做进栈，也叫作压栈，⼊栈。

栈的删除操作：叫做出栈，也叫弹栈。

1. 3. 进栈出栈变化形式现在请⼤家思考这样的⼀个问题：最先进栈的元素，是不是只能最后才能出来呢？答案是不⼀定的，这个问题就要细分情况了。

栈对线性表的插⼊和删除的位置进⾏了限制，并没有对元素的进出时间进⾏限制，这也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以先出站，只要确保⼀点：栈元素是从栈顶出栈就可以了！举例来说，现在有3个整型数元素1、2、3依次进栈，会有哪些出栈次序呢？第⼀种：1、2、3依次进，再3、2、1依次出栈。

#include<stdio.h>#include<iostream>using namespace std;template< typename T >class ArrayStack{private:int m_size; //栈容量int m_top; //栈顶，初始为-1T* m_stack; //存放栈内容的连续空间public:ArrayStack(int size);ArrayStack();~ArrayStack();void clear();bool push(const T item);bool pop( T & item);bool top( T & item );};template< typename T >ArrayStack< T >::ArrayStack(int size){this->m_size = size;this->m_top = -1;m_stack = new T[m_size];}template< typename T >ArrayStack< T >::ArrayStack(){this->m_size = 0;this->m_top = -1;m_stack = new T[m_size];}template< typename T >ArrayStack< T >::~ArrayStack(){delete[] m_stack;}template< typename T >void ArrayStack< T >::clear(){this->m_top = -1;}template< typename T >//自动解决栈溢出的入栈操作bool ArrayStack< T >::push(const T item){//扩展存储空间if(this->m_top == m_size - 1){T* newst = new T [this->m_size* 2+1];for(int i = 0 ; i <= this->m_top ; i ++ ){newst[i] = this->m_stack[i];}delete [] this->m_stack;m_stack = newst;m_size = m_size * 2+1;}++ this->m_top;m_stack[this->m_top] = item;return true;}template< typename T >bool ArrayStack< T >::pop( T & item ){if( this->m_top == -1){std::cerr<<"stack is empty, no item can bepopped!"<<std::endl;return false;}else{item = m_stack[this->m_top];this->m_top--;return true;}}template< typename T >bool ArrayStack< T >::top( T & item ){if( this->m_top == -1){std::cerr<<"stack is empty, no item can be read!"<<std::endl;return false;}else{item = m_stack[this->m_top];return true;}}template<typename T>void exchange(char inorder[],char post[],int& m)。