链栈,字面意思,就是用链表来实现一个栈的数据结构。
那么,只需将单链表的头节点当作栈顶,尾节点当作栈底。入栈只需要头插,出栈只需头删即可。所以只需要吧单链表稍微阉割一下就可以得到链式栈了。代码如下
//header.h
#pragma once
#include<iostream>
using namespace std;
template<class T>
struct LinkNode //节点类定义
{
T data; //数据域
LinkNode<T> *next; //链指针域
LinkNode(LinkNode<T> *ptr = NULL){this->next = ptr;} //初始化指针域的构造函数
LinkNode(const T& item, LinkNode<T> *ptr = NULL)//初始化数据成员和指针成员和指针的构造函数
{
this->data = item;
this->next = ptr;
}
};
template<class T>
class ListStack //用头结点的数据域表示链表元素数量
{
protected:
LinkNode<T> *first;
public:
ListStack(){first = new LinkNode<T>;first->data = 0;}//无参数构造
ListStack(const T& x)
{
this->first = new LinkNode<T>;
this->input(x);
}//含有参数的构造函数
ListStack(ListStack<T>& L);//拷贝构造
~ListStack(){makeEmpty();}//析构函数
void makeEmpty();//将链表置空的函数
int Length()const{return this->first->data;}//计算链表长度的函数
LinkNode<T>* getHead()const{return this->first;}//返回附加头结点地址
LinkNode<T>* getRear()const;//返回尾部指针
void input(T head);//头插
void output();//将链表打印出来
bool IsEmpty()const{return !this->first->data;}
bool Remove(int i, T& x);//删除第i个元素,将第i个元素的data赋值给x
ListStack<T>& operator=(ListStack<T>& L);//符号重载,赋值
bool del(T& x);
};
template<class T>
bool ListStack<T>::del(T& x)
{
return this->Remove(1, x);
}
template<class T>
ListStack<T>& ListStack<T>::operator=(ListStack<T>& L)
{
if(!L.IsEmpty())
{
LinkNode<T> *srcptr = L.first, *desptr = this->first;
while(srcptr->next != NULL)
{
desptr->data = srcptr->data;
desptr->next = new LinkNode<T>;
srcptr = srcptr->next;
desptr = desptr->next;
}
desptr->data = srcptr->data;
}
}
template<class T>
bool ListStack<T>::Remove(int i, T& x)
{
if(i>0 && i<=this->first->data)
{
LinkNode<T> *tmp = this->first, *p;
if(i!=1)
{
int j = 0;
while(j!=i-1)
{
tmp = tmp->next;
++j;
}
p = tmp->next;
tmp->next = p->next;
x = p->data;
delete p;
}
else
{
p = tmp->next;
x = p->data;
tmp->next = p->next;
delete p;
}
--this->first->data;
return true;
}
return false;
}
template<class T>
void ListStack<T>::input(T head)
{
LinkNode<T> *tmp = new LinkNode<T>;
if(tmp == NULL)
{
cerr<<"内存分配错误!n"<<endl;
exit(-1);
}
if(this->first->next != NULL)
{
tmp->next = this->first->next;
this->first->next = tmp;
}
else
{
this->first->next = tmp;
tmp->next = NULL;
}
tmp->data = head;
++this->first->data;
}
template<class T>
void ListStack<T>::output()
{
LinkNode<T> *p = this->first->next;
while(p!=NULL)
{
cout<<p->data<<" | ";
p = p->next;
}
cout<<"over"<<endl;
}
template<class T>
ListStack<T>::ListStack(ListStack<T>& L)
{
T value;
LinkNode<T> *srcptr = L.getHead();
LinkNode<T> *desptr = this->first = new LinkNode<T>;
this->first->data = srcptr->data;
while(srcptr->next != NULL)
{
value = srcptr->next->data;
desptr->next = new LinkNode<T>(value);
desptr = desptr->next;
srcptr = srcptr->next;
}
desptr->next = NULL;
}
template<class T>
void ListStack<T>::makeEmpty()
{
LinkNode<T> *p, *q = this->first->next;
this->first->data = 0;
while(q != NULL)
{
p = q;
q = q->next;
delete p;
}
}
template<class T>
LinkNode<T>* ListStack<T>::getRear()const
{
LinkNode<T> *p = this->first;
while(p->next!=NULL)
p = p->next;
return p;
}
#include"header.h"
int main()
{
int x = 0;
ListStack<int> LS;
for(int i=0; i<=7; ++i)
LS.input(i);
LS.output();
for(int i=0; i<=2; ++i)
{
LS.del(x);
cout<<x<<" ";
}
cout<<endl;
LS.output();
return 0;
}
运行结果
还行,这里补充一个vim将字符批量替换的命令
在vim末行模式下
a,b s#words1#words2#g
从第a行到第b行,将所有words1替换为words2
试了一下
命令是将第六行到第七行的所有i替换成io,替换后
替换后下边有提示在多少行替换了多少个(Emma,替换前的图i没有圈完,眼花眼花😀)
原文链接: https://www.cnblogs.com/area-h-p/p/11019391.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/296636
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!