链栈和顺序栈的实现_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 链栈和顺序栈的实现

链栈和顺序栈的实现

 2015/3/18 0:18:00  香煎马鲛鱼  程序员俱乐部  我要评论(0)
  • 摘要:顺序栈和链栈是我复习的第二部分,同样是把之前的代码整理出来,发布给大家,实现的方法并不难,毕竟是最基本的方法嘛。关于代码的解释已经写成注释。所以不用多说了。大家好好看代码吧~下面的代码是栈的实习,完整代码实现下载地址;//顺序栈//#ifndefASTACK_H#defineASTACK_H#include"Stack.h"template<classElem>classAStack:publicStack<Elem>{private:intsize
  • 标签:实现

class="MsoNormal">?

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

//顺序栈

//

#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

  • Palindromejudgment.rar (3.3 KB)
  • 下载次数: 0
上一篇: 挖角支付宝组建小米钱包团队,雷军加快布局金融 下一篇: 没有下一篇了!
发表评论
用户名: 匿名