`
香煎马鲛鱼
  • 浏览: 109404 次
  • 性别: Icon_minigender_2
社区版块
存档分类
最新评论

链栈和顺序栈的实现

    博客分类:
  • C++
阅读更多

 

顺序栈和链栈是我复习的第二部分,同样是把之前的代码整理出来,发布给大家,实现的方法并不
难,毕竟是最基本的方法嘛。关于代码的解释已经写成注释。所以不用多说了。大家好好看代码吧~
下面的代码是栈的实习,完整代码实现下载地址;

//顺序栈

//

#ifndef ASTACK_H

#defineASTACK_H

#include"Stack.h"

template <classElem> classAStack : publicStack<Elem>{

private:

         int size;//栈最大长度

         int top;//栈长度

         Elem *listArray;

public:

         AStack(intsz = DefaultListSize){

                   size = sz;

                   top = 0;

                   listArray = newElem[sz];

         }

         ~AStack(){

                   delete [] listArray;

         }

         voidclear(){

                   top=0;

         }

         boolpush(constElem& item){//存入操作

                   if(top==size) returnfalse;

                   else{

                            listArray[top++] = item;

                            returntrue;

                   }

         }

         boolpop(Elem& it){//取出操作

                   if(top==0) returnfalse;

                   else{

                            it = listArray[--top];

                            returntrue;

                   }

         }

         booltopValue(Elem& it){//获取栈顶值

                   if(top==0) returnfalse;

                   else{

                            it = listArray[top-1];

                            returntrue;

                   }

         }

         intlength() const{//栈长度

                   return top;

         }

         //利用栈将栈逆置

         //具体分为以下几步:声明一个变量,用来临时存放栈顶元素,记为A

         //声明一个顺序栈,栈长比原栈小1,记为ls

         //首先将栈顶元素放入A,将剩下的元素放入ls,再将A放入原栈,接着将ls中所有元素放入原栈;

         //重复n此,n为栈长;

         voidreverlist(){

                   Elem it;

                   Elem A;

                   AStack<Elem> ls(top-1);

                   for (int i = 0; i < top; i++){

                            this->pop(A);

                            while (this->length())

                            {

                                     this->pop(it);

                                     ls.push(it);

                            }

                            this->push(A);

                            while (ls.length())

                            {

                                     ls.pop(it);

                                     this->push(it);

                            }

                   }

         }

};

#endif

 

//Stack类,定义栈中的方法

//只有五个方法:1、清空;2、进栈;3、出栈;4、获得栈顶元素值;5、输出栈高

#ifndef STACK_H

#defineSTACK_H

 

#include<iostream>

usingnamespace std;

template <classElem> classStack{

public:

         virtualvoidclear() = 0;

         virtualboolpush(constElem&) = 0;

         virtualboolpop(Elem&) = 0;

         virtualbooltopValue(Elem&) = 0;

         virtualintlength() const =0;

         virtualvoidreverlist() = 0;

};

#endif;

 

//链式栈的节点

#ifndef  SLINK_H

#define  SLINK_H

//链栈节点

#include<iostream>

usingnamespace std;

template<classElem> classSLink{

public:

         Elem element;

         SLink *next;

         SLink(constElem& elemval,SLink* nextval = NULL){

                   element=elemval;

                   next = nextval;

         }

         SLink(SLink* nextval =NULL){

                   next = nextval;

         }

};

#endif// ! SLINK_H

 

//链式栈

#ifndef LSTACK_H

#defineLSTACK_H

#include"Stack.h"

#include"SLink.h"

template <classElem> classLStack : publicStack<Elem>{

         SLink<Elem>* top;

         int size;//表长度

public:

         LStack(){

                   size = 0;

         }

         ~LStack(){

                   clear();

         }

         //清空表

         //清空表的操作流程:将top元素一个一个delete

         voidclear(){

                   if (size == 0){

                            cout << "This stack is empty"<<endl;

                   }

                   else{

                            int num = 0;

                            while (top != NULL&&size>1)

                            {

                                     SLink<Elem>* temp = top;

                                     top = top->next;

                                     size--;

                                     delete temp;

                            }

                            delete top;

                            size--;

                            cout << size << endl;

                   }

         }

         //入栈

         boolpush(constElem& item){

                   top =newSLink<Elem>(item,top);

                   size++;

                   returntrue;

         }

         //出栈

         boolpop(Elem& it){

                   if(size==0) returnfalse;

                   else{

                   it = top->element;

                   SLink<Elem>* ltemp = top->next;

                   delete top;

                   top =ltemp;

                   size--;

                   returntrue;

                   }

 

         }

         //获取栈顶值

         booltopValue(Elem& it){

                   if(size == 0)returnfalse;

                   it = top->element;

                   returntrue;

         }

         //获取栈长

         intlength() const{

                   return size;

         }

         //逆置栈,相关操作可参考顺序表实现

         voidreverlist(){

                   Elem it;

                   Elem A;

                   AStack<Elem> ls(size - 1);

                   for (int i = 0; i < size; i++){

                            this->pop(A);

                            while (this->length())

                            {

                                     this->pop(it);

                                     ls.push(it);

                            }

                            this->push(A);

                            while (ls.length())

                            {

                                     ls.pop(it);

                                     this->push(it);

                            }

                   }

         }

 

};

 

#endif

1
0
分享到:
评论

相关推荐

    C++模版类实现顺序栈、链栈

    本项目中,模版类被用来实现两种常见的数据结构——顺序栈和链栈,这两种栈都遵循后进先出(LIFO)的原则。下面我们将详细探讨这些知识点。 首先,**顺序栈**是基于数组实现的栈。在C++中,可以定义一个名为`...

    数据结构链栈与顺序栈

    本主题将深入探讨两种栈实现方式:链栈和顺序栈,以及它们在实际编程中的应用。 链栈是一种动态数据结构,其元素(节点)通过指针链接在一起。每个节点包含一个数据元素和指向下一个节点的指针。链栈的主要操作包括...

    链栈和顺序栈.zip

    链栈和顺序栈是两种常见的数据结构,它们都是线性数据结构的一种,主要用于临时存储和管理数据。在C语言中,这两种栈的实现方式各有特点,各有优缺点。本项目提供了一个良好的交互式界面,使得用户能够通过指令来...

    Java算法实例-链栈和顺序栈操作

    在这个Java算法实例中,"SepStack1501203023"和"LinkStack1501203023"可能代表两个类,分别实现了顺序栈和链栈的抽象数据类型(ADT)。这些类可能包含了如下功能: - `push(E element)`:向栈顶添加一个元素。 - `...

    顺序栈与链栈的实现

    本文将详细介绍顺序栈和链栈的实现,包括它们的数据结构、操作和应用。 一、顺序栈 顺序栈是一种基于数组的栈实现,它使用一个数组来存储栈中的元素。顺序栈的优点是访问速度快、实现简单,但是它存在一个固定的...

    顺序栈实现括号配对

    顺序栈实现括号配对 在计算机科学中,括号配对是指在一个表达式中,各种括号之间的匹配关系。例如,在一个数学表达式中,我们可以使用小括号、中括号和大括号来表示不同的操作优先级。然而,在实际应用中,我们需要...

    数据结构课程:顺序栈和链栈的实现

    ### 数据结构课程:顺序栈和链栈的实现 #### 栈的基本概念 栈是一种特殊的线性表,其特殊之处在于所有元素的插入和删除都只能在一端进行,这一端被称为栈顶(top),与之相对的一端称为栈底(bottom)。栈通常支持以下...

    顺序栈、链栈将10进制转为2、8、16进制源码

    本话题聚焦于一种特定的应用——使用C++实现的顺序栈和链栈,将10进制数转换为2、8、16进制。这里我们将深入探讨顺序栈和链栈的概念,以及它们如何应用于不同进制之间的转换。 首先,顺序栈是一种基于数组的数据...

    顺序栈和链栈操作

    本主题主要探讨两种常见的栈实现:顺序栈和链栈。栈是一种特殊的线性数据结构,遵循“后进先出”(LIFO)的原则,即最后入栈的元素最先出栈。 首先,我们来详细了解一下顺序栈。顺序栈是用一维数组来实现的栈,其...

    C语言 栈的实现,包含顺序栈和链栈,亲测可用

    `stack_list.c`和`stack_list.h`分别对应链栈的实现和接口定义。链栈的优点在于动态扩展,可以方便地插入和删除元素,特别是在栈的大小不确定或变化较大时。在`stack_list.c`中,会定义一个链表节点结构体,包含数据...

    顺序栈验证试验

    顺序栈是基于数组实现的,其特点是元素的插入(压栈)和删除(弹栈)操作都发生在栈顶,遵循“后进先出”(LIFO,Last In First Out)的原则。这个试验的目的就是帮助我们熟悉和验证顺序栈的基本操作。 顺序栈的...

    栈和队列笔记包括栈和队列的定义、顺序栈出入栈、链栈的出入栈操作、顺序队列基本操作、链式队列基本操作等

    顺序栈是利用顺序表实现的栈,其中数组的一端代表栈底,另一端代表栈顶。 1. **顺序栈元素“入栈”** - 当栈为空时,数组中没有任何元素,此时栈顶指针 `top` 的值为 `-1`。 - 向栈中添加第一个元素时,将其存储...

    顺序栈、链栈的插入和删除实验报告.pdf

    顺序栈和链栈的插入和删除实验报告 一、顺序栈和链栈的概念 ...实验结果表明,顺序栈和链栈都可以正确实现插入和删除操作,但它们的时间复杂度不同。因此,在选择数据结构时,需要根据实际情况选择合适的数据结构。

    C语言-顺序栈实现十进制转换为二进制-八进制-十六进制

    ### C语言顺序栈实现十进制到二进制、八进制、十六进制的转换 #### 一、概述 本篇文章将详细介绍如何使用C语言中的顺序栈来实现十进制数字向二进制、八进制以及十六进制的转换。通过分析给出的代码示例,我们将...

    顺序栈链栈1

    总结,顺序栈和链栈都是实现栈数据结构的有效方式,各有优缺点。顺序栈在空间管理上简单,但可能受限于预设的大小;链栈虽然需要额外的指针存储空间,但能灵活扩展,适应性强。在实际应用中,选择哪种实现方式取决于...

    \链栈,双向顺序栈,基本操作,很简单,自己写的

    本文详细介绍了双向顺序栈和链栈两种数据结构的基本概念及其核心操作的实现。通过对这些代码的分析,我们不仅可以了解这两种数据结构的工作原理,还能学习到如何在实际编程中使用它们。希望本文能够帮助读者更好地...

    数据结构顺序栈链栈.pdf

    实验报告要求学生独立完成实验题目,包括实现顺序栈和链栈、基本操作的实现、实验结果的分析等。此外,实验报告还需要包括实验目的、实验步骤、实验结果、结论等部分。 5. 数据结构的应用: 数据结构是一门重要的...

    顺序栈 链栈 顺序队列 链式队列 循环队列的常用算法.zip

    与顺序栈相比,链栈在插入和删除操作时无需考虑内存连续性,灵活性更高。 - 入栈操作:在链表末尾添加新节点。 - 出栈操作:删除链表末尾节点。 3. **顺序队列**: - 顺序队列也是基于数组实现的,遵循先进先出...

    会定义顺序栈和链栈的结点类型

    1、 会定义顺序栈和链栈的结点类型。 2、 掌握双向栈的结构特点及其在一维数组中的实现。 3、 掌握在双向栈中进行插入和删除元素的方法。 二、 实验要求 1、 定义栈的存储结构。 2、 编写程序实现双向栈的基本操作...

Global site tag (gtag.js) - Google Analytics