开发者社区> 拓海藤原> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

数据结构与算法 第二次实验报告堆栈队列

简介:     数据结构与算法 第二次实验报告             姓名:许恺 学号:2014011329 班级:计算机14-1                           中国石油大学(北京)计算机科学与技术系     前     言     《数据结构》是计算机及相关专业的一门核心基础课程,也是很多高校考研专业课之一。
+关注继续查看

 

 

 

数据结构与算法

第二次实验报告

 

 

 

 

 

 

姓名:许恺

学号:2014011329

班级:计算机14-1

 

 

 

 

 

 

 

 

 

 

 

 

 

中国石油大学(北京)计算机科学与技术系

 

 

    

    《数据结构》是计算机及相关专业的一门核心基础课程,也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现,在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习,要求学生能够掌握典型算法的设计思想及程序实现,能够根据实际问题选取合适的存储方案,设计出简洁、高效、实用的算法,为后续课程的学习及软件开发打下良好的基础。学习这门课程,习题和实验是两个关键环节。学生理解算法,上机实验是最佳的途径之一。因此,实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验,特编写实验指导书。

一、实验目的

    更好的理解算法的思想、培养编程能力。

二、实验要求

1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。

     2、在指导教师的帮助下能够完成实验内容,得出正确的实验结果。

     3、实验结束后总结实验内容、书写实验报告。

 4、遵守实验室规章制度、不缺席、按时上、下机。

     5、实验学时内必须做数据结构的有关内容,不允许上网聊天或玩游戏,如发现上述现象,取消本次上机资格,平时成绩扣 10 分。

     6、实验报告有一次不合格,扣 5 分,两次以上不合格者,平时成绩以零分记。

三、实验环境  VC++6.0 或者 VC2010

四、说明

     1、本实验的所有算法中元素类型可以根据实际需要选择。

     2、实验题目中带*者为较高要求,学生可自选;其余部分为基本内容,应尽量完成(至少完成 70%,否则实验不合格)。

     3、数据结构是很多高校的硕士研究生入学考试的专业课之一,希望有志于考研的学生能够在学习过程中注意各种算法的理解,以便为考研做一定的准备。

五、实验报告的书写要求    

  1.明确实验的目的及要求;    

  2.记录实验的输入数据和输出结果;    

  3.说明实验中出现的问题和解决过程;    

  4.写出实验的体会和实验过程中没能解决的问题;

六、参考书目《数据结构》(C++语言描述) 王红梅等 清华大学出版社DATA STRUCTURE WITH C++William Ford,William Topp 清华大学出版社(影印版)

实验二 栈、队列、串的操作

实验类型:验证性  

实验要求:必修

实验学时: 2 学时

一、实验目的:

参照给定的栈类和队列类的程序样例,验证给出的栈和队列的常见算法,并结合线性表

类实现有关串的操作。

二、实验要求:

1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。

2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。

三、实验内容:

     1. 堆栈类测试和应用问题。要求:

       (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为:依次把数据元素 1,2,3,4,5 入栈,然后出栈堆栈中的数据元素并在屏幕上显示。

       (2)定义数据元素的数据类型为如下形式的结构体:

typedef  struct

{  char taskname[10];//任务名

   int taskno;    //任务号

            DataType

              设计一个包含 5 个数据元素的测试数据,并设计一个主函数实现依次把 5个数据元素入栈,然后出栈堆栈中的数据元素并在屏幕上显示。

2. 队列类测试和应用问题。要求:

              设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为:依次把数据元素 1,2,3,4,5 入队,然后出队中的数据元素并在屏幕上显示。

3.设计串采用顺序存储结构,编写函数实现两个串的比较 Compare(S, T)。要求比较结果有大于、等于和小于三种情况。

    *4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。

  *5. 设计串采用静态数组存储结构,编写函数实现串的替换 Replace(S, start, T, V)即要求在主串 S 中,从位置 start 开始查找是否存在子串 T,若主串 S 中存在子串T,则用子串 V 替换子串 T,且函数返回 1;若主串 S 中不存在子串 T,则函数返回0。并要求设计主函数进行测试。一个测试例子为:S=”I am a student”,T=student”,V=teacher “。

四、实验操作计划  

实验第一部分(25 分钟) :

源代码

1.LinkStackMain.cpp文件

#include <iostream> 

using namespace std;

#include "LinkStack.h" 

void main( )

{

LinkStack<int>a;

if (a.Empty( ))

{

cout<<"栈空,执行操作"<<endl;

cout<<"10 进行压栈操作:"<<endl;

try

{

a.Push(10);

}

catch(char* wrong)

{

cout<<wrong;

}

cout<<"读取栈顶元素:"<<endl;

cout<<a.GetTop( )<<endl;

cout<<"15 栈进行压栈操作:"<<endl;

try

{

  a.Push(15);

}

catch(char* wrong)

{

  cout<<wrong;

}

cout<<"读取栈顶元素:\n";

cout<<a.GetTop( )<<endl;

cout<<"进行出栈操作:"<<endl;

a.Pop( );

cout<<"读取栈顶元素:"<<endl;

cout<<a.GetTop( )<<endl;

}

else{

  cout<<"栈不空"<<endl;

}

//a.~LinkStack( );

}

2.LinkStack.h文件

#ifndef LINKSTACK_H

#define LINKSTACK_H

template <class T>

struct Node

{

T data;

Node<T> *next;

};

template <class T>

class LinkStack

{

  public:

LinkStack( );

~LinkStack( );

void Push(T x);

T Pop( );

bool Empty( );

T GetTop( );

  private:

Node<T> *top;

Node<T> *head;

};

template <class T>

LinkStack<T>::LinkStack( )

{

head=new Node<T>;

head->next=NULL;

top = head->next;

}

template <class T>

LinkStack<T>::~LinkStack()

{

Node <T> *p=head;

Node <T> *q;

while(p)

{

q=p;

p=p->next;

delete q;

}

delete p;

}

template<class T>

void LinkStack<T>::Push(T x)

{

Node<T> *p;

p=new Node<T>;

p->data=x;

p->next=NULL;

if(top==NULL)

{

  top=p;

  head->next = p;

}

else

{

  top->next=p;

  top=p;

}

}

template <class T> T LinkStack<T>::Pop( )

{

T x;

Node<T> *p= head;

if (top==head) throw "下溢";

while(p->next!=top)

  p=p->next;

x=p->data;

top=p;

return x;

}

template <class T>

T LinkStack<T>::GetTop( )

{

if (top!=NULL)

  return top->data;

else return NULL;

}

template <class T>

bool LinkStack<T>::Empty( )

{

if(top==NULL)

  return 1;

else

  return 0;

}  

#endif;

3.SeqStackMain.cpp文件

/*#include <iostream>

using namespace std;

#include "SeqStack.h"

void main()

{

SeqStack<int> a;

if (a.Empty( ))

{

cout<<"栈空,执行入栈操作:"<<endl;

cout<<"15 10 执行入栈操作:"<<endl;

try

{

  a.Push(15);

  a.Push(10);

}

catch(char* wrong)

{

  cout<< wrong;

}

cout<<"栈顶元素为:"<<endl;

cout<<a.GetTop( )<<endl;

cout<<"执行出栈操作:"<<endl;

cout<<a.Pop( )<<endl;

cout<<"栈顶元素为:"<<endl;

cout<<a.GetTop( )<<endl;

}

else{

  cout<<"栈不空"<<endl;

}

}*/

4.SeqStack.h文件

#ifndef SEQSTACK_H

#define SEQSTACK_H

const int StackSize=10;

template <class T>

class SeqStack

{

  public:

SeqStack( ) ;

~SeqStack( );

void Push(T x);

T Pop( );

T GetTop( );

bool Empty( );

  private:

T data[StackSize];

int top;

};

template <class T>

SeqStack<T>::SeqStack( )

{

  top=-1;

}

template <class T>

SeqStack<T>::~SeqStack( )

{

 

}

template <class T>

void SeqStack<T>::Push(T x)

{

if (top== StackSize-1) throw "上溢";

  top++;

data[top]=x;

}

template <class T>

T SeqStack<T>::Pop( )

{

T x;

if (top==-1) throw "下溢";

x=data[top--];

return x;

}

template <class T>

T SeqStack<T>::GetTop( )

{

if (top!=-1)

  return data[top];

}

template <class T>

bool SeqStack<T>::Empty( )

{

  if(top==-1) return 1;

  else return 0;

}

#endif

运行程序贴图

 

 

三.报告总结:

   报告并不难,只是连老师给的代码太考验我们了,我知道可能是老师故意设的陷阱,也费了不少时间修改原来的代码。主要问题出在了析构函数的使用,其实程序结束会自动调用的,但是,我却又调了一遍,导致报错。嗯,就这些。

 

 

(真是后悔当时怎么没有多写点注释和报告总结,可是现在让我写现在的总结同样还是不会写的很详细,人类真的是很烦的物种。。。)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
educoder数据结构与算法 队列 第2关 实现一个链接存储的队列
educoder数据结构与算法 队列 第2关 实现一个链接存储的队列
0 0
educoder数据结构与算法 队列 第1关:实现一个顺序存储的队列
educoder数据结构与算法 队列 第1关:实现一个顺序存储的队列
0 0
用栈实现队列(java数据结构与算法)
用栈实现队列(java数据结构与算法)
0 0
【尚硅谷】Java数据结构与算法笔记02 - 队列
【尚硅谷】Java数据结构与算法笔记02 - 队列
0 0
数据结构与算法-数组模拟队列
数据结构与算法-数组模拟队列
0 0
数据结构与算法—队列详解
栈和队列是一对好兄弟,前面我们介绍过数据结构与算法—栈详解,那么栈的机制相对简单,后入先出,就像进入一个狭小的山洞,山洞只有一个出口,只能后进先出(在外面的先出去)。而队列就好比是一个隧道,后面的人跟着前面走,前面人先出去(先入先出)。日常的排队就是队列运转形式的一个描述!
0 0
【数据结构与算法】深入理解队列(下)
【数据结构与算法】深入理解队列(下)
0 0
【数据结构与算法】第七章:队列的表示与操作实现
前面两章重点介绍了栈的表示与实现,本章将详细解释队列的表示与实现,以及相关的基本操作。
0 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载