点击刷新
链栈和顺序栈的区别在于，链栈不受空间限制，根据链表生成，如图，首先观察它的特点：
灰色表示真实数据，而top指向的结点，称之为头结点，它的数据项没存入数据，仅仅是做为一个头结点存在。在链栈的初始化中，首先创建了一个头结点，但是里面没有存放数据，如果可能，存放链栈的长度也是可以的。
如果初始化不创建头结点，仅仅是将top=NULL，就省了一个头结点。而，多了一个头结点，计算的时候可能绕那么一点。反正，我不太习惯用这个头结点。
接下来，是入栈操作，归根到底还是单链表的细节操作，需要周转几步。这种手法在单链表的总结中会详细记录
链栈没有特别要说的地方，如果单链表熟练，这个应该不会有大问题，而问题在于，这种代码很容易前学后忘！
/*-----此链表带有头结点-------*/ /*-----可以改成不带头结点，更简练一些*/ #include <iostream> using namespace std; #define OK 1 #define ERROR 0 typedef struct node { int data; struct node *next; }*ListStack,stack; void InitStack(ListStack &L)/*初始化*/ { L=(ListStack)malloc(sizeof(stack)); if(!L) exit(-1); L->next=NULL; } int PushStack(ListStack &top,int e)/*入栈！此创建带头结点*/ { ListStack p; if((p=(ListStack)malloc(sizeof(stack)))==NULL) exit(-1); p->data=e; p->next=top->next; top->next=p; return OK; } int PopStack(ListStack &top,int &e) /*出栈*/ { ListStack p;/*辅助指针p*/ p=top->next; if(!p) { cout<<"栈已空！"<<endl; return ERROR; } e=p->data; top->next=p->next; free(p); return OK; } void Traverse(ListStack &top)/*遍历，打印*/ { ListStack p=top->next; while(p) { cout<<p->data<<" "; p=p->next; }; } void DestoryStack(ListStack &top)/*销毁*/ { if(top->next) { DestoryStack(top->next);/*采用递归方式销毁*/ free(top->next); top->next=NULL; } } int main(void) { int e; ListStack top; InitStack(top);/*初始化*/ PushStack(top,23);/*入栈*/ PushStack(top,20);/*入栈*/ PushStack(top,15);/*入栈*/ Traverse(top);/*遍历打印*/ PopStack(top,e);/*出栈*/ DestoryStack(top);/*销毁栈*/ return 0; }
补充：上面所说的头结点可以专门用一个结构体包括，其中包含一个top指针和计数count，方法如下：
先定义结点结构：
typedef struct node { int data; struct node *next; }*LinkStackPtr,Node;
接着再定义头结点：
typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack;
这样，头结点就比较独立，而且里面还包含一个计数功能
/*————————————————————————————*/
© 著作权归作者所有
举报
发表评论
0/200
