目录
一、链栈
1、链栈的定义:
2、链栈的优缺点:
二、链栈的基本操作算法(C语言)
1、宏定义
2、创建结构体
3、链栈的初始化
4、链栈的进栈
5、链栈的出栈
6、获取栈顶元素
7、栈的遍历输出
8、链栈的判空
9、求链栈的栈长
10、链栈的清空
11、链栈的销毁
三、链栈的基本操作完整代码(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#include #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("向链栈获取栈顶元素:%d\n", topData); } else { printf("向链栈获取栈顶元素失败!\n"); } // //获取栈顶元素 // Status rGetTop = GetTop(linkstack); // if (rGetTop == OK) { // printf("向链栈获取栈顶元素:%d\n", 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("链栈为空栈!\n\n"); } else printf("链栈不为空!\n\n"); } break; case 8: {//链栈的长度 Status length = stackLength(linkstack); printf("链栈的长度为:%d 。\n\n", length); } break; case 9: { //打印栈内元素 StackTraverse(linkstack); } break; case 10: {//退出程序 return 0; } break; default: { printf("输入错误,无此功能,请检查输入:\n\n"); } } } return 1; }
四、运行结果