数据结构 链栈.doc

《数据结构 链栈.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、#include//结点类模板templatestructnode{ETdata;//结点数据域，存储该结点的数据部分node*next;//结点指针域，指示下一个节点的位置node(){next=NULL;}//无参数结点构造函数，用于未给定参数时结点的初始化node(ETdat,node*link){data=dat;next=link;}//给定参数结点构造函数，构造给定数据和指针的结点};//链栈类Pag94templateclassLinkStack{protected:i

2、ntcount;//用于计数栈元素个数,即栈长node*top;//栈起始位置指针public:LinkStack(){count=0;top=newnode;}//链栈构造函数~LinkStack(){Clear();deletetop;}//链栈析构函数//链栈相关操作boolEmpty(){returncount==0;}//栈是否为空intLength(){returncount;}//用于获取栈元素个数voidClear();//栈清空，置元素个数为0voidShow();//输出现实栈中现有的所有元素node*GetPtr

3、(intpostion);//获取指向第pos个位置节点的指针voidPush(ET&e);//向栈中末位写入元素e，元素总数加一voidTop(ET&e);//获取栈顶元素，写入e中，由e输出voidPop(ET&e);//栈顶元素出栈.元素减一voidoperator=(LinkStack&cop);//赋值符重载函数，实现链栈的复制功能voidCinHelp();//提示输入函数，用于实现键盘输入交互式操作};templatevoidLinkStack::Clear(){node*pNext=top->next

4、;//指向第一个结点while(count>0)//当栈中有元素时{top->next=pNext->next;//将第二个结点作为头结点的后继deletepNext;//删除第一个结点pNext=top->next;//指向新的第一个结点count--;//元素总数减一}}templatevoidLinkStack::Show(){intcot=count;ETtmp;node*shw=top;//指向头指针的第一个后继cout<

5、ile(cot>0)//当栈中有元素时{shw=shw->next;//每输出一位向后移动一位tmp=shw->data;cout<node*LinkStack::GetPtr(intpostion){intpos=postion;node*ElemPtr;if(pos==0)returntop;elseif(pos<1

6、

7、pos>count+1)cout<

8、置小于"<next;while(pos>1){ElemPtr=ElemPtr->next;pos--;}}//不断指向下一个结点，头指针所在位置为零returnElemPtr;}templatevoidLinkStack::Push(ET&e){node*prt=GetPtr(count);//获取指向最后一个结点的指针prt->next=newnode;//将最后一个节点的后继指向新的结点count++;//置入栈中不存在的元素，元

9、素总数加一prt->next->data=e;//将e写入后继结点的数据部分}templatevoidLinkStack::Top(ET&e){if(count==0)cout<data;//获取指向第pos个结点的数据部分}templatevoidLinkStack::Pop(ET&e){//删除在第pos个位置的结点if(count==0)cout<

10、lse{node*prt=GetPtr(co