【数据结构】链栈的基本操作（C语言版）

发布时间：2024年01月23日

一、链栈

1、链栈的定义：

2、链栈的优缺点：

一、链栈

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("向链栈获取栈顶元素：%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;
}

?四、运行结果

文章来源:https://blog.csdn.net/weixin_56814370/article/details/135786789
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

【数据结构】 链栈的基本操作 （C语言版）

一、链栈

1、链栈的定义：

2、链栈的优缺点：

二、链栈的基本操作算法（C语言）????

1、宏定义

??2、创建结构体

3、链栈的初始化?

?4、链栈的进栈

5、链栈的出栈

6、获取栈顶元素

7、栈的遍历输出

8、链栈的判空

?9、求链栈的栈长

10、链栈的清空

11、链栈的销毁

三、链栈的基本操作完整代码（C语言）

?四、运行结果

【数据结构】链栈的基本操作（C语言版）