数据结构链栈的基本操作的实现

文章目录

        • 一、实验目的
        • 二、实验内容
        • 三、问题分析
        • 四、算法设计
          • 1、主要数据结构的设计
            • 1.1 链栈的入栈
            • 1.2 链栈的出栈
            • 1.3 取栈顶元素
          • 2、算法设计
            • 2.1 链栈初始化算法
            • 2.2 入栈操作算法
            • 2.3 出栈操作算法
            • 2.4 取栈顶元素算法
        • 五、代码实现

一、实验目的

(1)掌握栈的链式存储结构;
(2)掌握栈的操作特性;
(3)掌握基于链栈的基本操作的实现方法。

二、实验内容

(1)建立一个空栈;
(2)对已建立的栈进行插入、删除、取栈顶元素等基本操作。

三、问题分析

栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表。对栈来说,表尾端有其特殊含义,称为栈顶 (top), 表头端称为栈底 (bottom)。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的,栈又称为后进先出的线性表。
链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示,链栈的结点结构与单链表的结构相同,在此用StackNode 表示。链栈有着初始化、入栈、出栈、去栈顶元素等操作。

四、算法设计

1、主要数据结构的设计
1.1 链栈的入栈
①为入栈元素 e 分配空间,用指针 p 指向。
②将新结点数据域置为e。
③将新结点插入栈顶。
④修改栈顶指针为 p。


入栈示意图

1.2 链栈的出栈
①判断栈是否为空,若空则返回ERROR。
②将栈顶元素赋给e。
③临时保存栈顶元素的空间,以备释放。
④修改栈顶指针,指向新的栈顶元素。
⑤释放原栈顶元素的空间。


出栈示意图

1.3 取栈顶元素
当栈非空时, 此操作返回当前栈顶元素的值, 栈顶指针S保持不变。
2、算法设计
2.1 链栈初始化算法
Status InitStack(LinkStack &S){  
//构造一个空栈S,栈顶指针置空S = NULL;return OK;
}
2.2 入栈操作算法
Status Push (LinkStack &S, SElenType e){//在栈顶插人元素ep-new StackNode;                     //生成新结点p->data=e;                           //将新结点数据城置为ep->next=S;                           //将新结点插人栈顶S=p;                                 //修改栈顶指针为preturn OK;
}
2.3 出栈操作算法
Status Pop (LinkStack &S, SElemType &e){//删除s的栈顶元素,用e返回其值if(S==NULL) return ERROR;           //栈空e=S->data;                          //将栈顶元素赋给ep=S;                              //用p临时保存栈顶元素空间,以备释放S=S->next;                          //修改栈顶指针delete p;                          //释放原栈顶元素的空间return OK;
}
2.4 取栈顶元素算法
SElemtype GetTop(LinkStack S){         
//返回S的栈顶元素,不修改栈顶指针if(S!=NULL)return S->data;
}

五、代码实现

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int SElemtype;
typedef struct Node{SElemtype data;struct Node *next;
}StackNode,*LinkStack;//初始化栈
int InitStack(LinkStack &S){S = new StackNode;S->next = NULL;return OK;
}int DestroyStack(LinkStack &S){LinkStack p;while(S){p = S;S = S->next;delete p;}return OK;
}//清空栈
void ClearStack(LinkStack S){LinkStack p,q;p = S->next;while(p){q = p->next;delete p;p = q;}S->next = NULL;//头指针指针域为空,空栈
}//判断链栈是否为空
int StackEmply(LinkStack S){return(S->next==NULL);
}
//入栈操作
void PushStack(LinkStack S,SElemtype e){LinkStack p;p = new StackNode;p->data = e;p->next = S->next;S->next = p;
}//出栈操作
int PopStack(LinkStack S,SElemtype &e){LinkStack p;if(StackEmply(S))return ERROR;p = S->next;e = p->data;S->next = p->next;delete p;return OK;
}//取栈顶元素
int GetTop(LinkStack S,SElemtype e){LinkStack p;if(StackEmply(S))return ERROR;p = S->next;e = p->data;return OK;
}//输出链栈
void DispStack(LinkStack S){LinkStack p = S->next;printf("链栈为:");if(StackEmply(S)){printf("栈空!\n");return;}while(p){printf("%d ",p->data);p = p->next;}printf("\n");
}//显示菜单
void Showmenu(){printf("\n      ---链栈基本操作---     \n");printf("*******************************\n");printf("*       1、初始化链栈          *\n");printf("*       2、创建链栈            *\n");printf("*       3、入栈操作            *\n");printf("*       4、出栈操作            *\n");printf("*       5、取栈顶元素          *\n");printf("*       0、退出程序            *\n");printf("*******************************\n");printf("请选择菜单(0-5):");
}void Stack(){int choice,m,e;SElemtype item;LinkStack S;int flag = 0;while(choice){Showmenu();scanf("%d",&choice);switch(choice){case 1:if(InitStack(S)){printf("初始化链栈成功!\n");flag = 1;}elseprintf("初始化链栈失败!\n");break;case 2:if(flag){printf("请输入链栈长度:");scanf("%d",&m);for(int i = 0;i<m;i++){e = rand()%20+1;PushStack(S,e);}DispStack(S);}elseprintf("初始化链栈失败!\n");break;case 3:if(flag){printf("请输入入栈元素值:");scanf("%d",&item);PushStack(S,item);printf("元素已入栈!\n");DispStack(S);}else{printf("链栈不存在,操作失败!\n");}break;case 4:if(flag){if(PopStack(S,item))printf("出栈元素为:%d !\n",item);else printf("栈空!\n");DispStack(S);}else{printf("链栈不存在,操作失败!\n");}break;case 5:if(flag){if(GetTop(S,item))printf("栈顶元素为:%d!\n",item);else printf("栈空!\n");DispStack(S);}else{printf("链栈不存在,操作失败!\n");}break;case 0:printf("\t程序结束!\t\n");DestroyStack(S);break;default:printf("选择错误,请重新选择!!\n");break;}}
}//主函数
int main(){Stack();return 0;
}

作者文坛写于2020年5月10日

数据结构链栈的基本操作的实现

文章目录

        • 一、实验目的
        • 二、实验内容
        • 三、问题分析
        • 四、算法设计
          • 1、主要数据结构的设计
            • 1.1 链栈的入栈
            • 1.2 链栈的出栈
            • 1.3 取栈顶元素
          • 2、算法设计
            • 2.1 链栈初始化算法
            • 2.2 入栈操作算法
            • 2.3 出栈操作算法
            • 2.4 取栈顶元素算法
        • 五、代码实现

一、实验目的

(1)掌握栈的链式存储结构;
(2)掌握栈的操作特性;
(3)掌握基于链栈的基本操作的实现方法。

二、实验内容

(1)建立一个空栈;
(2)对已建立的栈进行插入、删除、取栈顶元素等基本操作。

三、问题分析

栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表。对栈来说,表尾端有其特殊含义,称为栈顶 (top), 表头端称为栈底 (bottom)。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的,栈又称为后进先出的线性表。
链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示,链栈的结点结构与单链表的结构相同,在此用StackNode 表示。链栈有着初始化、入栈、出栈、去栈顶元素等操作。

四、算法设计

1、主要数据结构的设计
1.1 链栈的入栈
①为入栈元素 e 分配空间,用指针 p 指向。
②将新结点数据域置为e。
③将新结点插入栈顶。
④修改栈顶指针为 p。


入栈示意图

1.2 链栈的出栈
①判断栈是否为空,若空则返回ERROR。
②将栈顶元素赋给e。
③临时保存栈顶元素的空间,以备释放。
④修改栈顶指针,指向新的栈顶元素。
⑤释放原栈顶元素的空间。


出栈示意图

1.3 取栈顶元素
当栈非空时, 此操作返回当前栈顶元素的值, 栈顶指针S保持不变。
2、算法设计
2.1 链栈初始化算法
Status InitStack(LinkStack &S){  
//构造一个空栈S,栈顶指针置空S = NULL;return OK;
}
2.2 入栈操作算法
Status Push (LinkStack &S, SElenType e){//在栈顶插人元素ep-new StackNode;                     //生成新结点p->data=e;                           //将新结点数据城置为ep->next=S;                           //将新结点插人栈顶S=p;                                 //修改栈顶指针为preturn OK;
}
2.3 出栈操作算法
Status Pop (LinkStack &S, SElemType &e){//删除s的栈顶元素,用e返回其值if(S==NULL) return ERROR;           //栈空e=S->data;                          //将栈顶元素赋给ep=S;                              //用p临时保存栈顶元素空间,以备释放S=S->next;                          //修改栈顶指针delete p;                          //释放原栈顶元素的空间return OK;
}
2.4 取栈顶元素算法
SElemtype GetTop(LinkStack S){         
//返回S的栈顶元素,不修改栈顶指针if(S!=NULL)return S->data;
}

五、代码实现

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int SElemtype;
typedef struct Node{SElemtype data;struct Node *next;
}StackNode,*LinkStack;//初始化栈
int InitStack(LinkStack &S){S = new StackNode;S->next = NULL;return OK;
}int DestroyStack(LinkStack &S){LinkStack p;while(S){p = S;S = S->next;delete p;}return OK;
}//清空栈
void ClearStack(LinkStack S){LinkStack p,q;p = S->next;while(p){q = p->next;delete p;p = q;}S->next = NULL;//头指针指针域为空,空栈
}//判断链栈是否为空
int StackEmply(LinkStack S){return(S->next==NULL);
}
//入栈操作
void PushStack(LinkStack S,SElemtype e){LinkStack p;p = new StackNode;p->data = e;p->next = S->next;S->next = p;
}//出栈操作
int PopStack(LinkStack S,SElemtype &e){LinkStack p;if(StackEmply(S))return ERROR;p = S->next;e = p->data;S->next = p->next;delete p;return OK;
}//取栈顶元素
int GetTop(LinkStack S,SElemtype e){LinkStack p;if(StackEmply(S))return ERROR;p = S->next;e = p->data;return OK;
}//输出链栈
void DispStack(LinkStack S){LinkStack p = S->next;printf("链栈为:");if(StackEmply(S)){printf("栈空!\n");return;}while(p){printf("%d ",p->data);p = p->next;}printf("\n");
}//显示菜单
void Showmenu(){printf("\n      ---链栈基本操作---     \n");printf("*******************************\n");printf("*       1、初始化链栈          *\n");printf("*       2、创建链栈            *\n");printf("*       3、入栈操作            *\n");printf("*       4、出栈操作            *\n");printf("*       5、取栈顶元素          *\n");printf("*       0、退出程序            *\n");printf("*******************************\n");printf("请选择菜单(0-5):");
}void Stack(){int choice,m,e;SElemtype item;LinkStack S;int flag = 0;while(choice){Showmenu();scanf("%d",&choice);switch(choice){case 1:if(InitStack(S)){printf("初始化链栈成功!\n");flag = 1;}elseprintf("初始化链栈失败!\n");break;case 2:if(flag){printf("请输入链栈长度:");scanf("%d",&m);for(int i = 0;i<m;i++){e = rand()%20+1;PushStack(S,e);}DispStack(S);}elseprintf("初始化链栈失败!\n");break;case 3:if(flag){printf("请输入入栈元素值:");scanf("%d",&item);PushStack(S,item);printf("元素已入栈!\n");DispStack(S);}else{printf("链栈不存在,操作失败!\n");}break;case 4:if(flag){if(PopStack(S,item))printf("出栈元素为:%d !\n",item);else printf("栈空!\n");DispStack(S);}else{printf("链栈不存在,操作失败!\n");}break;case 5:if(flag){if(GetTop(S,item))printf("栈顶元素为:%d!\n",item);else printf("栈空!\n");DispStack(S);}else{printf("链栈不存在,操作失败!\n");}break;case 0:printf("\t程序结束!\t\n");DestroyStack(S);break;default:printf("选择错误,请重新选择!!\n");break;}}
}//主函数
int main(){Stack();return 0;
}

作者文坛写于2020年5月10日