顺序栈实验的算法分析

顺序栈的基本操作实验报告

学院：应用科技学院 专业：电子信息工程 姓名：林三德 学号：120352010067 年级：2010级 时间：2011-11-7 一：实验目的

1）熟悉栈的定义和栈的基本操作。

2）掌握顺序结构存储栈和链接存储栈的基本运算。

3）加深对栈结构的理解，逐步培养解决实际问题的能力。

二：实验要求

1）调用进栈函数建立一个栈。 2）读取栈顶元素。 3）从栈中删除元素。 4）输出栈中德所有元素。

注意：每完成一个步骤就必须及时输出栈中的元素。

三：概要设计

1)编写栈的基本操作函数。

①进栈函数 Status Push(SqStack *S, SElemType e) ②出栈函数 Status Pop(SqStack *S,SElemType *e) ③输出栈元素 OutputStack(SqStack *S) 2)本程序包出栈函数含6个函数。

? 主函数 main() ? ? ? ?

进栈函数PushStack() 出栈函数PopStack()

取栈顶元素Ge

#include using namespace std;

# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10

typedef struct { int * base; int * top;

int stacksize;//当前栈可使用的最大容量 } SqStack;

void InitStack(SqStack &S)//构造一个空栈 { S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) {cout<<\存储分配失败!!!\ else { S.top=S.base; S.stacksize=STACK_INIT_SIZE; cout<<\构造成功!!!\ } }

void Push(SqStack &S,int e)//插入元素e为栈顶元素 { if(S.top-S.base>=S.stacksize) { S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) cout<<\存储分配失败!!!\ else { S.stacksize+=STACKINCREMENT; S.top=S.base+S.stacksize; } } *S.top++=e; }

void DisplayStack(SqStack &S) //从栈底到栈顶逐次显示栈中的元素 { int *p; p=S.base;

实验一 算法的实验分析方法

一、实验目的及要求

（一）实验目的

1、 熟悉算法的实验分析方法； 2、 熟悉实验的数据分析。

（二）实验要求 1．合理添加计数器

2．理解执行次数和问题规模之间的关系

二、实验设备及软件环境

（一）实验设备 PC机

（二）软件环境

1．Microsioft Windows XP 操作系统； 2．JAVA SDK

三、实验内容与步骤

1、 设计选择排序算法

2、 在算法中添加计数器，累计比较次数 3、 完成算法分析

4、 用JAVA实现算法，分别运行5-10个记录的排序，分析执行次数和规模之间的关系 5、 判断运行结果是否与分析结果一致

答、1、2、

3、假设第一个数是最小的数，然后让它与其余的数依次比较，比较完之后，如果有比他小的数就进行交换，没有则不用交换。再假设第二个数是最小的，再跟余下的数字依次比较，如果有比他小的数就进行交换，没有则不用交换…….重复，直到假设最后一个数是最小 4、 原数组5,4,3,2,1，1,2,3,4,52,5,6,1,91,1,2,3,2,4,3,2,5,1,6,6,5,4,3,2,11,1,1,1,1,1由小到大排列好的数组1,2,3,4,51,2,3,4,51

算法分析设计与提高

实验指导

2016年4月

实验一 算法基础

一、实验要求

1. 掌握算法的计算复杂性概念。 2. 掌握算法渐近复杂性的数学表述。 3. 掌握描述算法的方法。

4. 实现具体的编程与上机实验，验证算法的时间复杂性函数。

二、实验内容

统计数字问题 1. 问题描述

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。 2. 编程任务

给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。

三、程序算法

四、程序代码

五、程序调试中的问题

六、实验结果

1

实验二 分治法

一.实验要求

1. 了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大

的问题时，

2. 如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，

其中1

4. 3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

二.实验

算法分析设计与提高

实验指导

2016年4月

实验一 算法基础

一、实验要求

1. 掌握算法的计算复杂性概念。 2. 掌握算法渐近复杂性的数学表述。 3. 掌握描述算法的方法。

4. 实现具体的编程与上机实验，验证算法的时间复杂性函数。

二、实验内容

统计数字问题 1. 问题描述

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。 2. 编程任务

给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。

三、程序算法

四、程序代码

五、程序调试中的问题

六、实验结果

1

实验二 分治法

一.实验要求

1. 了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大

的问题时，

2. 如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，

其中1

4. 3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。

二.实验

实验三 栈的基本运算

学号：0700710319 姓名：梁浩然 实验日期：2009年5月6日

一、 实验目的：

（1）掌握栈的各种存储结构及基本运算的实现。

（2）掌握堆栈后进先出的运算原则在解决实际问题中的应用。 （3）复习c语言中相关语句及函数的用法。

（4）进一步熟悉c语言的相关知识，能够把某些c语言知识应用得自如一点。 （5）一定要自己先完成实验的课后习题，认真的思考，能够达到独立思考。

二、 实验要求：

（1） 熟练掌握栈的存储结构及其基本操作。

（2）理解所给出的算法，掌握栈在实际中的应用。

（3）将上机程序调试通过，并能独立完成一至两个拓展题目。

（4）一定要读书老师所给出来的程序。

三、 实验内容：

认真阅读数据结构的课本，熟悉所学的知识，认真复习c语言的相关的知识，然后对括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对算法的理解。

四、 实验步骤：

首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句

或带括号的数学表达式，

实验三 栈和队列的基本操作

一、实验目的

1、掌握栈的顺序存储结构。 2、掌握栈特点，即先进后出原则。 3、掌握栈基本操作实现方法。

4、熟练掌握顺序队、链队的存储原理；

5、熟练掌握顺序队、链队的Java语言实现方法； 6、掌握队列空、队满的判断条件；

7、了解循环队列与普通队列实现上的不同及其解决方法。

二、实现内容

[问题描述] 1、栈

首先，创建栈，并置top指针为-1，栈处于空的状态。

第二，入栈。先判断栈是否是满栈。满栈的话，不做入栈操作，未满的话，做入栈操作。 第三，出栈。先判断栈是否为空，如果是空栈的话，不能做出栈操作，非空的话做出栈操作。 2、队列

首先，创建空队，置队首指针，队尾指针为0和-1

第二，入队操作。判断队列是否已满，队满的话，不能入队，未满的话，做入队操作。 第三，出队操作。判断队是否为空，如果空队的话，不能出队，未空的话，做处队操作。

[基本要求]用顺序存储结构实现存储

[实现提示]顺序存储结构是随机存储结构，直接数组来存储相关数据，用下标来表示栈顶，数据存储从下标0开始存储数据。

[程序实现]

参考书本相关程序实例

三、实验要求

1、通过建立一个简单的菜单来实现进栈、出栈、显示当前栈内元素和退除操作

《算法设计与分析》实验报告

学号： 姓名：

实验一 分治法求解**问题

一、实验目的

1.掌握分治法的设计思想并能熟练应用；

2.理解分治与递归的关系。

二、实验题目

在有序序列中(r1,r2,…,rn)中,存在序号i（1≤i≤n）,使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).

三、实验程序

//以(0,2,3,3,5,7,8,10,12,13)为例

#include<iostream>

using namespace std;

void PrintData(int data[],int length)

{

}

int Bisearch(int data[],int begin ,int last)

{

if ( mid < data[mid] ) int mid=(begin + last) /2; if (mid+1 == data[mid]) { } return mid; cout<<"有序序列是："; for (int i=0;i

实验三 栈和队列

一、实验目的

1.了解栈和队列的特性。 2.掌握栈的顺序表示和实现。 3.掌握栈的链式表示和实现。 4.掌握队列的顺序表示和实现。 5.掌握队列的链式表示和实现。

6.掌握栈和队列在实际问题中的应用。

二、实验内容

实验2.1栈的顺序表示和实现

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：

(1)初始化顺序栈。 (2)插入元素。 (3)删除栈顶元素。 (4)取栈顶元素。 (5)遍历顺序栈。 (6)置空顺序栈。

实验2. 2栈的链式表示和实现

编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：

(1)初始化链栈。 (2)链栈置空。 (3)入栈。 (4)出栈。

(5)取栈顶元素。 (6)遍历链栈。

实验2. 3队列的顺序表示和实现

编写一个程序实现顺序队列的各种基本运算（采用循环队列），并在此基础上设计一个主程序，完成如下功能： (1)初始化队列。 (2)建立顺

攀枝花学院数据结构第三次实验

实验二 栈和队列的应用

1、实验目的

（1）熟练掌握栈和队列的结构，以及这两种数据结构的特点；

（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；

（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；

2、实验内容

利用栈的基本操作实现将任意一个十进制整数转化为R进制整数.

3、实验步骤

（1）理解栈的基本工作原理；

（2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法；

（4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。

4、实验帮助

算法为：

1) 定义栈的顺序存取结构

2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈

只要X不为0重复做下列动作

将X % R入栈 X=X/R

只要栈不为空重复做下列动作

栈顶出栈 输出栈顶元素

程序代码：

# include # include

typedef struct zan {

int data[100]; int top; }seqstack;

//置空栈

seqstac