滴水逆向联盟

标题: VC++2012编程演练数据结构《14》链式堆栈 [打印本页]

作者: 大灰狼 时间: 2014-9-2 07:58
标题: VC++2012编程演练数据结构《14》链式堆栈
链式存储结构特点：
　　在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).
　　它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.
链式存储结构
链式存储结构特点：
　　1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
　　2、逻辑上相邻的节点物理上不必相邻。
　　3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
　　4、查找结点时链式存储要比顺序存储慢。

　　5、每个结点是由数据域和指针域组成。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
　　栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。
　　栈可以用来在函数调用的时候存储断点，做递归时要用到栈！
　　以上定义是在经典计算机科学中的解释。
　　在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址增大，弹出的操作使得栈顶的地址减小。
　　栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：
　　1．函数的返回地址和参数
　　2．临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

打开IDE

我们创建一个工程

类的声名如下

[cpp] view plaincopy

#if !defined(AFX_LINEARSTACK_H__BE959832_707C_4625_8592_D903D805B2E2__INCLUDED_)
#define AFX_LINEARSTACK_H__BE959832_707C_4625_8592_D903D805B2E2__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
//链式堆栈的类定义
const int LEN=40;
typedef struct Stack{
ElemType data;
struct Stack *next;
}StackNode;//结点数据类型
class LinStack
{private:
StackNode *top;//指向栈顶的指针
int size;// 堆栈的结点个数
public:
//构造函数
LinStack();
//初始化栈,分配存储空间并置空
void InitStack(int);
//创建有序或无序栈
void CreateStack(int,int m=LEN,int mark=0);
//返回堆栈的结点个数
int StackSize();
//清空栈
void ClearStack();
//删除栈
void DeleteStack();
//检查栈是否为空
bool StackEmpty();
//读取栈顶元素
ElemType Peek();
//向栈中插入元素
void Push(const ElemType&);
//从栈中删除元素
ElemType Pop();
//检查栈是否已满
bool StackFull(ElemType m=LEN);
//栈的输出
void StackPrint(ElemType m=LEN);
};
#endif // !defined(AFX_LINEARSTACK_H__BE959832_707C_4625_8592_D903D805B2E2__INCLUDED_)

类的实现如下

[cpp] view plaincopy

#include "stdafx.h"
#include "linearStack.h"
// 链式堆栈的实现
#include<stdlib.h>
//构造函数
LinStack::LinStack()
{top=NULL;size=0;}
//初始化栈,分配存储空间并置空
void LinStack::InitStack(int L)
{top=new StackNode[L];
size=0;
}
//创建有序或无序栈
void LinStack::CreateStack(int n,int m,int mark)
{ElemType x,a[LEN/2];
srand(n);
for(int i=0;i<m;i++) a=rand()%100;
for(int i=0;i<m-1;i++)
{int k=i;
for(int j=i+1;j<m;j++)
if(a[k]>a[j]) k=j;
if(k!=i)
{x=a[k];a[k]=a;a=x;}}
for(int i=0;i<m;i++)
if(mark==1) Push(a[m-1-i]);//升序
else
if(mark==-1) Push(a);//降序
else Push(rand()%100);//无序
}
int LinStack::StackSize()
{return size;}
//清空栈
void LinStack::ClearStack() {size=0;}
//删除栈
void LinStack::DeleteStack()
{delete top;}
//检查栈是否为空
bool LinStack::StackEmpty() {return size==0;}
//读取栈顶元素
ElemType LinStack::Peek()
{ return top->data;}
//向栈中插入元素
void LinStack::Push(const ElemType& item)
{StackNode *newNode=new StackNode;
newNode->data=item;newNode->next=top;
top=newNode;
size++;
}
//从栈中删除元素
ElemType LinStack::Pop()
{if(size==0) {
cerr<<"栈为空!"<<endl;exit(1);}
StackNode *p=top->next;
ElemType data=top->data;
delete top;
size--;
top=p;
return data;
}
//检查栈是否已满
bool LinStack::StackFull(ElemType m)
{return size==m;}
//栈的输出
void LinStack::StackPrint(ElemType m)
{for(int i=0;i<m;i++)
cout<<setw(3)<<Pop();
}

类的调用如下

[cpp] view plaincopy

#include "stdafx.h"
#include "linearStack.h"

void main()
{cout<<"运行结果:\n";
int m,n;
LinStack q,p,w;
cout<<"输入产生随机数的种子数n:";cin>>n;
cout<<"输入欲构造栈q的长度m:";cin>>m;
cout<<"创建栈q(升序):\n";
q.CreateStack(n,m,1);
cout<<"q栈的结点个数="<<q.StackSize()<<endl;
cout<<"输出q栈元素:\n";
q.StackPrint(m);cout<<endl;
cout<<"q栈:";
if(q.StackFull(m)==1)
   cout<<"已满!\n";
else cout<<"未满!\n";
cout<<"创建栈p(降序):\n";
p.CreateStack(n+10,m,-1);
cout<<"p栈:";
if(p.StackFull(m)==1)
   cout<<"已满!\n";
else cout<<"未满!\n";
cout<<"删除元素为:"<<p.Pop()<<endl;
cout<<"p栈:";
if(p.StackEmpty()==1)
   cout<<"为空!\n";
else cout<<"为非空!\n";
cout<<"输出p栈元素:\n";
p.StackPrint(m-1);cout<<endl;
cout<<"创建栈w(无序):\n";
w.CreateStack(2*n,m);
cout<<"输出w栈元素:\n";
w.StackPrint(m);cout<<endl;
p.ClearStack();
p.DeleteStack();
cin.get();cin.get();
}

效果如下

欢迎光临滴水逆向联盟 (http://dtdebug.com/) Powered by Discuz! X3.2