C++栈学习——顺序栈和链栈的差别
2023-09-11 14:14:42 时间
- C++中栈有顺序栈和链栈之分。在顺序栈中,定义了栈的栈底指针(存储空间首地址base)、栈顶指针top以及顺序存储空间的大小stacksize(个人感觉这个数据成员是能够不用定义的)
//顺序栈数据结构C++类声明(基类)
template <typename ElemType>
class SqStack
{
public:
void clear(); //把顺序栈置空
int getLength(); //求顺序栈中元素个数
int getstackSize(); //返回当前已分配的存储空间的大小
Status getTop(ElemType & e); //读栈顶的元素
bool isEmpty(); //推断顺序栈是否为空
SqStack<ElemType> operator =(SqStack<ElemType> rightS); //重载赋值运算符的定义
Status pop(ElemType & e); //弹出栈顶元素到e
void push(ElemType & e ); //在栈顶压入元素e
//*****************************以下为系统自己主动调用构造函数及析构函数声明******************************//
SqStack(); //顺序栈构造函数
virtual ~SqStack();//顺序栈析构函数
SqStack (const SqStack<ElemType>& otherS);//顺序栈拷贝初始换构造函数
protected:
ElemType *base;
ElemType *top;
int stackSize;//顺序存储空间的大小
};
- 而对于链栈来说,它仅仅定义栈顶指针。
template<typename ElemType>
class Linkstack
{
private:
class LinkNode
{
public:
ElemType data;
LinkNode *next;
};
typedef LinkNode * NodePointer;
public:
void clear();
int getlength();
void display();
void randLinkStack();
Linkstack <ElemType> operator = (Linkstack <ElemType> rightS);
protected:
NodePointer top;
};
事实上这二者的差别是由顺序表和链表的存储结构决定的,在空间上,顺序表是静态分配的,而链表则是动态分配的;就存储密度来说:顺序表等于1,而链式表小于1。可是链式表能够将非常多零碎的空间利用起来;顺序表查找方便。链式表插入和删除时非常方便。
顺序表的这样的静态存储的方式,决定了必须至少得有首地址和末地址来决定一个空间。否则,不知道查找到哪了。链式表每一个节点存储了下一个节点的指针信息,故,对于链栈来说,仅仅须要一个top指针就可以查找到整个栈。
另外,顺序栈和链栈的top指针有差别,顺序栈的top指针指向栈定的空元素处,top-1才指向栈定元素,而链栈的top指针相当于链表的head指针一样,指向实实在在的元素。
另外附自己写的顺序栈和链栈的随机产生函数:
//顺序栈:
template<typename ElemType>
void MyStack<ElemType>::RandStack()
{
int *p;
ElemType n;
ElemType Elem[11];
srand(time(NULL));
n=rand()%10+1;
cout<<"产生的随机栈的深度为:"<<n<<endl;
cout<<"产生的随机栈元素为:"<<endl;
for (int i = 0; i < n; i++)
{
Elem[i]=rand()%100+1;
cout<<Elem[i]<<" ";
}
cout<<endl;
base=new ElemType[n];
assert(base!=0);
top=base;
stackSize=n;
for (int j = 0; j < n; j++)
*(base+j)=Elem[j];
top=base+n;
cout<<"随机产生的栈为:"<<endl;
for (int i = 0; i < stackSize; i++)
cout<<" "<<*(base+i);
cout<<endl;
cout<<" ♂";
for (int i = 1; i <stackSize ; i++)
{
setw(4);
cout<<" ";
}
cout<<" ♂"<<endl;
cout<<" base";
for (int i = 1; i <stackSize ; i++)
{
setw(4);
cout<<" ";
}
cout<<" top"<<endl;
}
template<typename ElemType>
void MyStack<ElemType>::display()
{
int n=top-base;
cout<<"当前栈为:"<<endl;
for (int i = 0; i < n; i++)
cout<<" "<<*(base+i);
cout<<endl;
cout<<" ♂";
for (int i = 1; i <n ; i++)
{
setw(4);
cout<<" ";
}
cout<<" ♂"<<endl;
cout<<" base";
for (int i = 1; i <n ; i++)
{
setw(4);
cout<<" ";
}
cout<<" top"<<endl;
}
//链栈
template<typename ElemType>
void Linkstack<ElemType>::display()
{
NodePointer r;
int num=0;
r=top;
while (r)
{
cout<<r->data<<" ";
r=r->next;
num++;
}
cout<<endl;
for(int i=0;i<num-1;i++)
cout<<setw(4)<<" ";
cout<<"↑" ;
cout<<endl;
for(int i=0;i<num-1;i++)
cout<<setw(4)<<" ";
cout<<"top"<<endl;
}
template <typename ElemType>
void Linkstack<ElemType>::randLinkStack()
{
ElemType elem[11];
srand(unsigned(time(NULL)));
int n;
n=rand()%10+1;
cout<<"the number of the stack is:"<<n<<endl;
cout<<"the elements here are:";
for (int i = 0; i < n; i++)
{
elem[i]=rand()%100+1;
cout<<elem[i]<<" ";
}
cout<<endl;
NodePointer p,s;
p=NULL;
for (int i = 0; i < n; i++)
{
s=new(LinkNode);
assert(s!=NULL);
s->data=elem[i];
s->next=p;
p=s;
}
top=p;
cout<<"the stack produced is:"<<endl;
NodePointer r;
int num=0;
r=top;
while (r)
{
cout<<r->data<<" ";
r=r->next;
num++;
}
cout<<endl;
for(int i=0;i<num-1;i++)
cout<<setw(4)<<" ";
cout<<"↑" ;
cout<<endl;
for(int i=0;i<num-1;i++)
cout<<setw(4)<<" ";
cout<<"top"<<endl;
}
相关文章
- C++ 面向对象编程
- 【华为云实战开发】10.经典的C++项目怎么在云端开发?
- 经典中的品味:第二章 C++基本的对象,类型和值(上)
- C++学习笔记——常量定义
- 如何学好C++语言(转)
- C++ template 学习归纳总结4
- C++ 几行代码就能重载操作符模拟 cout<<123<<endl;
- C语言/C++常见习题问答集锦(四十五) 之数字之谜
- Open3D (C++) 基于投影点密度的建筑物立面提取
- C++:C++编程语言学习之数组/字符串/指针/引用/日期&I/O输入输出操作(I/O 库头文件/标准输出流cout/标准输入流cin/标准错误流/准日志流)的简介、案例应用之详细攻略
- 历届真题 小朋友崇拜圈【第九届】【省赛】【C组】——【C++】【C】【Java】【Python】四种语言解法
- [h5棋牌项目]-15-C#与C++通信
- 【华为OD机试 2023】 人数最多的站点/小火车最多人时所在园区站点(C++ Java JavaScript Python)
- c++子类重写父类方法
- cocos2dx3.2 画图方法小修改之 C++ final学习
- 坚持c++,真正掌握c++(2)
- AI模型设计必备:PyTorch与TensorFlow模型C++与python实现学习资料
- C/C++音频算法: noise suppression算法及技术资料汇总
- C++创建对象new与不new区别(二十五)
- VC++获取电脑的各个磁盘盘符及容量信息(附源码)
- json c++处理学习
- C++ spdlog日志管理
- C/C++学习笔记三
- C/C++学习笔记 C++中用于动态内存的new和delete运算符
- 【跟学C++】C++的函数(Study6)
- 学习C++:C++进阶(一)标准模板库STL
- C++学习第四节:C和C++的区别第二节课