堆栈的链式存储

1.结构体定义2.初始化3.是否为空4.入栈5.出栈6.打印所有元素8.测试9.全部代码

1.结构体定义

typedef int ElementType; typedef struct SNode *Stack; struct SNode { ElementType Data; //数据域 struct SNode *Next; //指针域 };

2.初始化

只初始化头结点

Stack CreateStack() { //构造一个堆栈的头结点并返回指针 Stack S; S = (Stack)malloc (sizeof(struct SNode)); S->Next = NULL; return S; }

3.是否为空

判断：头结点指向空

int IsEmpty(Stack S) { return S->Next ==NULL; }

4.入栈

void Push(ElementType item,Stack S) { struct SNode *tmp; tmp = (struct SNode *)malloc(sizeof(struct SNode )); tmp->Data = item; tmp->Next = S->Next; S->Next = tmp; }

5.出栈

ElementType Pop(Stack S) { struct SNode *firstcell; //记录需要删除的结点 ElementType TopData; //需要返回的变量 if(!IsEmpty(S)) { firstcell = S->Next; TopData = S->Next->Data; S->Next = firstcell->Next; free(firstcell); return TopData; } else { printf("堆栈为空！"); return NULL; } }

6.打印所有元素

void print(Stack S) { if(IsEmpty(S)) { printf("堆栈为空！\n"); return ; } Stack Pri = S->Next; while(Pri->Next!=NULL) { printf("%d ",Pri->Data); Pri=Pri->Next; } printf("%d\n",Pri->Data); }

8.测试

Stack s = CreateStack(); print(s); Push(5,s); Push(23,s); Push(43,s); Push(565,s); Push(54,s); print(s); printf("删除的元素为：%d\n",Pop(s)); print(s);

9.全部代码

#include<stdlib.h> #include<stdio.h> #include<malloc.h> typedef int ElementType; typedef struct SNode *Stack; struct SNode { ElementType Data; struct SNode *Next; }; //Stack S; //初始化 Stack CreateStack() { //构造一个堆栈的头结点并返回指针 Stack S; S = (Stack)malloc (sizeof(struct SNode)); S->Next = NULL; return S; } int IsEmpty(Stack S) { return S->Next ==NULL; } //入栈 void Push(ElementType item,Stack S) { struct SNode *tmp; tmp = (struct SNode *)malloc(sizeof(struct SNode )); tmp->Data = item; tmp->Next = S->Next; S->Next = tmp; } //出栈 ElementType Pop(Stack S) { struct SNode *firstcell; //记录需要删除的结点 ElementType TopData; //需要返回的变量 if(!IsEmpty(S)) { firstcell = S->Next; TopData = S->Next->Data; S->Next = firstcell->Next; free(firstcell); return TopData; } else { printf("堆栈为空！"); return NULL; } } void print(Stack S) { if(IsEmpty(S)) { printf("堆栈为空！\n"); return ; } Stack Pri = S->Next; while(Pri->Next!=NULL) { printf("%d ",Pri->Data); Pri=Pri->Next; } printf("%d\n",Pri->Data); } int main() { Stack s = CreateStack(); print(s); Push(5,s); Push(23,s); Push(43,s); Push(565,s); Push(54,s); print(s); printf("删除的元素为：%d\n",Pop(s)); print(s); system("pause"); return 0; }