【数据结构】 链栈的基本操作 （C语言版）
目录
一、链栈
1、链栈的定义：
链栈是一种栈的实现方式，它使用链表结构来实现。每个节点包含数据域和指针域，其中数据域用于存储数据，指针域用于指向下一个节点。链栈的栈顶指针指向栈顶元素，栈底指针指向栈底元素。
2、链栈的优缺点：
链栈的优点：
- 空间利用率高：链栈可以根据实际情况动态调整栈的大小，避免了顺序栈可能出现的内存溢出等问题。
- 时间复杂度低：链栈的入栈和出栈操作只需要改变栈顶指针的指向，时间复杂度为O(1)，不需要像顺序栈一样进行数据的移动，具有比较高的效率。
- 方便进行动态扩展：链栈可以方便地进行动态扩展，当需要增加元素时，可以动态地增加存储空间；当需要减少元素时，可以释放未使用的空间。
链栈的 缺点：
- 需要额外的指针存储空间，因此占用的存储空间较大。
- 插入和删除操作需要修改指针，操作较为复杂。
- 无法充分利用内存的连续性优势，因为链表节点的存储位置是分散的。
二、链栈的基本操作算法（C语言）
1、宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int SElemType;
typedef int Status; 2、创建结构体
//创建结构体
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;3、链栈的初始化
//初始化
Status InitStack(LinkStack &S) {
S = NULL;
return OK;
}4、链栈的进栈
//进栈
Status Push(LinkStack &S, SElemType e) {//在栈顶插入元素e
StackNode *p = new StackNode; //生成新结点
if (!p) exit(OVERFLOW);
p->data = e;
p->next = S; //将新结点插入 栈顶
S = p; //修改栈顶指针为p
return OK;
}
5、链栈的出栈
//出栈
Status Pop(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //将栈顶元素赋给e
LinkStack p = S; //用p临时保存栈顶元素空间，以备释放
S = S->next; //修改栈顶指针
delete p;
return OK;
}6、获取栈顶元素
//获取栈顶元素
Status Top(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //将栈顶元素赋给e
return OK;
}7、栈的遍历输出
//栈的遍历输出
void StackTraverse(LinkStack S) {
LinkStack p; //使用指针p辅助访问栈里元素
p = S; //p初始从栈顶开始
printf("从栈顶依次读出该栈中的元素值为:");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("n");
}8、链栈的判空
//判空
Status stackEmpty(LinkStack S) {
if (S == NULL) {如果栈顶的指针域指向空，则栈空
return true;
} else {
return false;
}
}9、求链栈的栈长
//求栈长
Status stackLength(LinkStack S) {
int len = 0;
while (S != NULL) {
len++;
S = S->next;
}
return len;
}10、链栈的清空
//清空
Status ClearStack(LinkStack &S) {
StackNode *p;
while (S != NULL) {
p = S->next;
delete S;
S = p;
}
return OK;
}11、链栈的销毁
//销毁
Status DestoryStack(LinkStack S) {
StackNode *p;
while (S) {
p = S;
S = S->next;
delete p;
}
S = NULL;
return OK;
}三、链栈的基本操作完整代码（C语言）
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int SElemType;
typedef int Status;
//创建结构体
typedef struct StackNode {
SElemType data;
struct StackNode *next;
} StackNode, *LinkStack;
//初始化
Status InitStack(LinkStack &S) {
S = NULL;
return OK;
}
//进栈
Status Push(LinkStack &S, SElemType e) {//在栈顶插入元素e
StackNode *p = new StackNode; //生成新结点
if (!p) exit(OVERFLOW);
p->data = e;
p->next = S; //将新结点插入 栈顶
S = p; //修改栈顶指针为p
return OK;
}
//出栈
Status Pop(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //将栈顶元素赋给e
LinkStack p = S; //用p临时保存栈顶元素空间，以备释放
S = S->next; //修改栈顶指针
delete p;
return OK;
}
//获取栈顶元素
Status Top(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
if (S == NULL) {
return ERROR;
}
e = S->data; //将栈顶元素赋给e
return OK;
}
//获取栈顶元素
Status GetTop(LinkStack S) {//返回S的栈顶元素，不修改栈顶指针
if (S != NULL) {
return S->data;
}
}
//栈的遍历输出
void StackTraverse(LinkStack S) {
LinkStack p; //使用指针p辅助访问栈里元素
p = S; //p初始从栈顶开始
printf("从栈顶依次读出该栈中的元素值为:");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("n");
}
//判空
Status stackEmpty(LinkStack S) {
if (S == NULL) {如果栈顶的指针域指向空，则栈空
return true;
} else {
return false;
}
}
//求栈长
Status stackLength(LinkStack S) {
int len = 0;
while (S != NULL) {
len++;
S = S->next;
}
return len;
}
//清空
Status ClearStack(LinkStack &S) {
StackNode *p;
while (S != NULL) {
p = S->next;
delete S;
S = p;
}
return OK;
}
//销毁
Status DestoryStack(LinkStack S) {
StackNode *p;
while (S) {
p = S;
S = S->next;
delete p;
}
S = NULL;
return OK;
}
//功能菜单
int choice() {
printf("==================================n");
printf(" 链栈操作功能菜单 n");
printf("1、进栈 2、出栈 3、获取栈顶元素 n");
printf("4、清空 5、销毁 6、批量进栈 n");
printf("7、判空 8、链栈的长度 n");
printf("9、打印栈内元素 10、退出程序 n");
printf("==================================n");
return 0;
}
int main() {
LinkStack linkstack;
//初始化
Status rInitStack = InitStack(linkstack);
if (rInitStack == OK) {
printf("链栈初始化成功！n");
} else {
printf("链栈初始化失败！n");
}
while (1) {
//功能菜单
choice();
int flag;
printf("请输入所需的功能编号：n");
scanf("%d", &flag);
switch (flag) {
case 1: {//进栈
Status Pushdata;
printf("请输入插入元素(请在英文状态下输入例如:1): n");
scanf("%d", &Pushdata);
Status rPush = Push(linkstack, Pushdata);
if (rPush == OK) {
printf("向链栈进栈%d成功！n", Pushdata);
} else {
printf("向链栈进栈失败！n");
}
}
break;
case 2: {//出栈
Status popData;
Status rPop = Pop(linkstack, popData);
if (rPop == OK) {
printf("向链栈出栈%d成功！n", popData);
} else {
printf("向链栈出栈失败！n");
}
}
break;
case 3: {//获取栈顶元素
Status topData;
Status rTop = Top(linkstack, topData);
if (rTop == OK) {
printf("向链栈获取栈顶元素：%dn", topData);
} else {
printf("向链栈获取栈顶元素失败！n");
}
// //获取栈顶元素
// Status rGetTop = GetTop(linkstack);
// if (rGetTop == OK) {
// printf("向链栈获取栈顶元素：%dn", topData);
// } else {
// printf("向链栈获取栈顶元素失败！n");
// }
}
break;
case 4: { //清空
Status rClearStack = ClearStack(linkstack);
if (rClearStack == OK) {
printf("链栈清空成功！n");
} else {
printf("链栈清空失败！n");
}
}
break;
case 5: {//销毁
Status rDestroyStack = DestoryStack(linkstack);
if (rDestroyStack == OK) {
printf("链栈销毁成功！n");
} else {
printf("链栈销毁失败！n");
}
}
break;
case 6: {//批量插入
int on;
printf("请输入想要插入的元素个数：n");
scanf("%d", &on);
SElemType array[on];
for (int i = 1; i <= on; i++) {
getchar();
printf("向顺序栈第%d个位置插入元素为:", (i));
scanf("%d", &array[i]);
}
for (int i = 1; i <= on; i++) {
Status rPush = Push(linkstack, array[i]);
if (rPush == OK) {
printf("向链栈进栈%d成功！n", array[i]);
} else {
printf("向链栈进栈失败！n");
}
}
}
break;
case 7: {//判空
Status rStackEmpty = stackEmpty(linkstack);
if (rStackEmpty == true) {
printf("链栈为空栈！nn");
} else
printf("链栈不为空！nn");
}
break;
case 8: {//链栈的长度
Status length = stackLength(linkstack);
printf("链栈的长度为：%d 。nn", length);
}
break;
case 9: { //打印栈内元素
StackTraverse(linkstack);
}
break;
case 10: {//退出程序
return 0;
}
break;
default: {
printf("输入错误，无此功能，请检查输入:nn");
}
}
}
return 1;
}四、运行结果
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码