数据结构（链栈-链表）

方法一：引用

#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; typedef int ElemType; const int MaxSize=50; typedef struct LNode { ElemType data; struct LNode *next; } LinkList; void InitList(LinkList *&s) { s=(LinkList *)malloc(sizeof(LinkList)); s->next=NULL; } bool Push(LinkList *&s,int e) { LinkList *p; p=(LinkList *)malloc(sizeof(LinkList)); p->data=e; p->next=s->next; s->next=p; } bool disp(LinkList *s) { // LinkList *p; //p=(LinkList *)malloc(sizeof(LinkList)); LinkList *p; p=new LinkList; p=s->next; while(p) { cout<<p->data<<" "; p=p->next; } cout<<endl; return true; } bool Gettop(LinkList *&s,int &e) { if(s->next==NULL) return false; e=s->next->data; return true; } bool Pop(LinkList *&s,int &e) { LinkList *p; p=new LinkList; if(s->next==NULL) return false; e=s->next->data; p=s->next; s->next=p->next; free(p); return true; } bool EmptyStack(LinkList *s) { return s->next==NULL; } void Destroy(LinkList *&s) { LinkList *p; p=new LinkList; p=s->next; while(p!=NULL) { free(s); s=p; p=p->next; } free(s);//s指向尾结点,释放其空间 } int main() { LinkList *s; InitList(s); int n,a[MaxSize],e; cout<<"请输入链栈的长度n: "; cin>>n; cout<<"请依次输入"<<n<<"个数字"<<endl; for(int i=0; i<n; i++) { cin>>a[i]; Push(s,a[i]); } cout<<"栈s: "; disp(s); Gettop(s,e); cout<<endl<<"栈顶的元素是 : "<<e<<endl; cout<<"请输入你想进栈的元素 : "; cin>>e; Push(s,e); cout<<"栈s: "; disp(s); Pop(s,e); cout<<endl<<"栈顶的元素是 : "<<e<<endl; cout<<"栈顶出栈之后的s是: "; disp(s); int i=EmptyStack(s); if(i) cout<<"此链栈为空!"<<endl; else cout<<"此链栈不空!"<<endl; cout<<endl<<"此栈已经被销毁"; Destroy(s); }

方法二：指针

#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; const int MaxSize=50; typedef int ElemType; typedef struct linknode { ElemType data; struct linknode *next; }LinkStNode; void Push(LinkStNode *s,int e) { LinkStNode *p; p=(LinkStNode *)malloc(sizeof(LinkStNode)); p->data=e; p->next=s->next; s->next=p; } void disp(LinkStNode *s) { LinkStNode *p=s->next; while(p!=NULL) { cout<<p->data<<" "; p=p->next; } cout<<endl; } bool EmptyStack(LinkStNode *s) { return (s->next==NULL); } bool Gettop(LinkStNode *s,int &e) { if(s->next==NULL) return false; e=s->next->data; return true; } bool Pop(LinkStNode *s,int &e) { LinkStNode *p; if(s->next==NULL) return false; p=s->next; e=p->data; s->next=p->next; free(p); return true; } void Destroy(LinkStNode *s) { LinkStNode *p=s,*q=s->next; while(q!=NULL) { free(p); p=q; q=q->next; } free(p); } int main() { LinkStNode s; s.next=NULL; int n,a[MaxSize],e; cout<<"请输入链栈的长度n: "; cin>>n; cout<<"请依次输入"<<n<<"个数字"<<endl; for(int i=0;i<n;i++) { cin>>a[i]; Push(&s,a[i]); } cout<<"栈s: "; disp(&s); Gettop(&s,e); cout<<endl<<"栈顶的元素是 : "<<e<<endl; cout<<"请输入你想进栈的元素 : "; cin>>e; Push(&s,e); cout<<"栈s: "; disp(&s); Pop(&s,e); cout<<endl<<"栈顶的元素是 : "<<e<<endl; cout<<"栈顶出栈之后的s是: "; disp(&s); int i=EmptyStack(&s); if(i) cout<<"此链栈为空!"<<endl; else cout<<"此链栈不空!"<<endl; cout<<endl<<"此栈已经被销毁"; Destroy(&s); }