精华内容
下载资源
问答
  • 链栈
    2020-02-02 21:47:07

    注意:链栈中,指针的方向为由栈顶指向栈尾! 

    即插入元素时为头插法

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #define TRUE 1
    #define FALSE 0
    
    using namespace std;
    /**
    *在链栈中指针的方向是从栈顶指向栈底!!!
    *在栈中只 能对栈顶进行插入、删除操作
    */
    
    /**链栈的结点*/
    typedef struct StackNode{
        int data;
        struct StackNode * next;
    }StackNode;
    
    /**链栈结构*/
    typedef struct Stack{
        StackNode * top;//指向栈顶的指针
        int length;
    }Stack;
    
    void InitStack(Stack &S)
    {
        S.top = NULL;
        S.length = 0;
    }
    int Push(Stack &s,int element)
    {
        //不存在栈满情况
        StackNode * node;
        node = (StackNode*)malloc(sizeof(StackNode));
        node->data =  element;
        node->next = s.top;
        s.top = node;
        s.length++;
        return TRUE;
    
    }
    int Pop(Stack &s,int &element)
    {
        if(s.top == NULL)
            return FALSE;
        StackNode *temp = s.top;
        element = s.top->data;
        s.top = s.top->next;
        s.length--;
        free(temp);
        return TRUE;
    }
    void ClearStack(Stack &s)
    {
        while(s.top)
        {
            StackNode * temp;
            temp = s.top;
            s.top = s.top->next;
            s.length--;
            free(temp);
        }
    }
    int main()
    {
        Stack S;
        InitStack(S);
        cout << "请输入要入栈的元素个数:";
        int n;
        cin >> n;
        while(n--)
        {
            cout<<"请输入元素:" ;
            int x;
            cin >> x;
            Push(S,x);
        }
        cout << "栈内元素个数为:" << S.length << endl;
        cout << "请输入要出栈的元素个数:";
        cin >> n;
        while(n--)
        {
            int m;
            if(Pop(S,m))
                 cout << "出栈元素:" << m << endl;
             else
                cout << "栈空,出栈失败" << endl;
        }
        ClearStack(S);
        //cout << "清空栈后长度:" << S.length;
    
        return 0;
    }
    

     

    更多相关内容
  • 链栈的基本操作,包括入栈、显示栈元素、清空栈元素、判断栈空、进制的转换、出栈
  • 链栈的基本操作的实现,这个程序中演示了链栈的初始化、链栈的创建、删除、查找以及输出等功能。使用c语言所写。
  • 栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表。对栈来说,表尾端有其...通常链栈用单链表来表示,链栈的结点结构与单链表的结构相同,在此用StackNode 表示。链栈有着初始化、入栈、出栈、去栈顶元素等操作。
  • 本文实例为大家分享了C++利用链栈实现表达式求值的具体代码,供大家参考,具体内容如下 #include typedef int Status; typedef char Cstack; #define OK 1 #define ERROR 0 typedef struct StackNode { Cstack ...
  • 注:分为四个内容:顺序栈、链栈、循环队列、链队列。代码由C++程序设计语言编写,包含栈和队列的基本操作(栈:出、入、取、判空等|队列:出、入、取、打印队列、判空等),并展示了三个具体的使用例子,包括用栈求...
  • 链栈的基本运算

    2018-09-03 15:29:10
    本程序共设计了链栈需要的的4个基本操作运算,分别是顺序栈的入栈,出栈,访问,以及置空操作。附带实验报告。
  • 数据结构实验-括号匹配的检验-链栈实现
  • 数据结构-链栈(C语言实现)
  • 自己定义的栈的接口,完全是按照栈的常用方法以及命名方式实现: 注意以下类,接口都是在一个命名空间下 栈的接口:包括了常用的方法 namespace 栈 { interface IStackDS { int Count { get;...
  •  对于链栈,一般不会出现栈满的情况。  链栈头文件定义例如以下: #ifndef CSTOCK_H_ #define CSTOCK_H_ typedef int elemType; struct Item { elemType data; Item * p_next; }; class CStock { ...
  • c语言实现链栈ADT,初始化,销毁,清空,判空,获取栈顶元素,栈长度,入栈,出栈
  • 实验一 线性表 1. 实验要求 1.1 掌握数据结构中线性表的基本概念 1.2 熟练掌握线性表的基本操作创建插入删除查找输出求长度 及合并并运算在顺序存储结构上的实验 1.3 熟练掌握链表的各种操作和应用 2....
  • 数据结构课程中顺序栈和链栈的操作实现,实现语言为C语言
  • 数据结构(C语言版)——链栈(代码版),里面包含c文件和exe文件。基本操作为1:初始化链栈2:销毁链栈3:清空链栈4:链栈是否为空5:返回栈顶元素6:元素压入到链栈中7:删除栈顶元素,并返回8:当前栈元素个数
  • 顺序栈和链栈操作

    2016-12-16 16:09:49
    栈的操作,顺序栈和链栈的操作.数据结构基础.
  • 栈文档之链栈

    2022-04-22 23:37:02
    采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高效率,且不存在栈满上溢的清空。通常采用单链表实现,并且规定所有操作都是在单链表的表头进行上的(因为头结点的 `next` 指针指向栈的栈顶结点...

    链栈

    定义

    概念

    采用链式存储的栈称为链栈。链栈的优点是便于多个栈共享存储空间和提高效率,且不存在栈满上溢的清空。通常采用单链表实现,并且规定所有操作都是在单链表的表头进行上的(因为头结点的 next 指针指向栈的栈顶结点)。

    在这里插入图片描述

    结构体

    链栈的结构体定义如下:

    /**
     * 链栈结构体定义
     */
    typedef struct LNode {
        /**
         * 数据域
         */
        int data;
        /**
         * 指针域,指向后继结点
         */
        struct LNode *next;
    } LNode;// 链栈结点定义
    

    特点

    • 采用链式存储,便于结点的插入和删除,但是对于栈这种只能在一端操作的数据结构来说,顺序栈和链栈插入和删除的时间复杂度区别不大。
    • 链栈的操作和顺序栈的操作类似,出栈和入栈的操作都在栈顶进行。
    • 对于带头结点和不带头结点的链栈,具体实现有所不同,下面的实现代码都是以带头结点为例。

    基本操作

    注,完整代码请参考:

    概述

    链栈的常见操作如下:

    • void init(LNode **stack):初始化链栈。其中 stack 表示链栈。
    • int isEmpty(LNode *stack):判断链栈是否为空。其中 stack 表示链栈。如果链栈为空则返回 1,否则返回 0。
    • void push(LNode **stack, int ele):将元素入栈。其中 stack 表示链栈;ele 表示新元素值。
    • int pop(LNode **stack, int *ele):将元素出栈。其中 stack 表示链栈;ele 用来保存出栈元素。如果链栈为空则返回 0,否则出栈成功则返回 1。
    • int getTop(LNode *stack, int *ele):获取栈顶元素,但不出栈元素。其中 stack 表示链栈;ele 用来保存栈顶元素。如果链栈为空则返回 0,否则返回 1。
    • int size(LNode *stack):获取链栈中的元素个数。其中 stack 表示链栈。
    • void print(LNode *stack):打印链栈中所有元素。其中 stack 表示链栈。
    • void clear(LNode **stack):清空链栈中所有元素。其中 stack 表示链栈。
    • void destroy(LNode **stack):销毁链栈。其中 stack 表示链栈。

    init

    初始化链栈。

    在这里插入图片描述

    实现步骤如下:

    • 创建链栈头结点,为其分配空间,将头结点指针域指向 null,表示是空链栈。

    实现代码:

    /**
     * 初始化链栈
     * @param stack 未初始化的链栈
     */
    void init(LNode **stack) {
        // 即创建链栈的头结点,为其分配空间
        *stack = (LNode *) malloc(sizeof(LNode));
        // 将头结点的 next 指针指向 null,表示这是一个空栈
        (*stack)->next = NULL;
    }
    

    isEmpty

    判断链栈是否为空。如果链栈为空则返回 1,否则返回 0。

    在这里插入图片描述

    实现步骤:

    • 判断链栈的栈顶结点是否存在,即 stack->next==null

    实现代码如下:

    /**
     * 判断链栈是否为空
     * @param stack 链栈
     * @return 如果链栈为空则返回 1,否则返回 0 表示非空链栈
     */
    int isEmpty(LNode *stack) {
        // 即判断链栈的栈顶结点(即头结点的后继结点)是否存在
        if (stack->next == NULL) {
            return 1;
        } else {
            return 0;
        }
    }
    

    push

    将元素入栈。以 stack=[11, 22, 33]; ele=44 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 创建新结点,为新结点分配空间,指定数据域为 ele,指定指针域初始指向 null,表示这是一个新结点。
    • 将新结点入栈。即将新结点的 next 指针指向原栈顶结点(栈顶结点即为 stack->next),然后将链栈头结点的 next 指向新结点。

    注:结点入链栈,采用的就是单链表的头插法。

    实现代码如下:

    /**
     * 将元素入栈
     * @param stack 链栈
     * @param ele 新元素值
     */
    void push(LNode **stack, int ele) {
        // 1.创建新节点,为其初始化数据域和指针域
        // 1.1 为新结点分配空间
        LNode *newNode = (LNode *) malloc(sizeof(LNode));
        // 1.2 为新结点指定数据域
        newNode->data = ele;
        // 1.3 将新结点的指针域初始指向 null,表示没有与任何结点进行连接
        newNode->next = NULL;
    
        // 2.将新节点入栈,成为栈顶结点
        // 2.1 将新结点的 next 指针指向原栈顶结点,完成新结点与原栈顶结点的链接
        newNode->next = (*stack)->next;
        // 2.2将链栈头结点的 next 指针指向新结点,即新结点成为了链栈的新栈顶结点
        (*stack)->next = newNode;
    }
    

    pop

    将元素出栈,如果是空栈则不能出栈,并且将出栈元素保存到 ele 中。以 stack=[44, 33, 22, 11] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果链栈为空,则不能出栈,返回 0 表示出栈失败。
    • ele 保存栈顶元素。
    • 然后删除栈顶结点。即用链栈的头结点的 next 指针指向原栈顶结点的后继结点。
    • 释放原栈顶结点的空间。

    实现代码如下:

    /**
     * 将元素出栈
     * @param stack 链栈
     * @param ele 用来保存栈顶结点的数据值
     * @return 如果栈空则不能出栈返回 0 表示出栈失败,否则返回 1 表示出栈成功
     */
    int pop(LNode **stack, int *ele) {
        // 0.变量,记录栈顶结点
        LNode *topNode = (*stack)->next;
        // 1.判断链栈是否为空,分情况处理
        // 1.1 如果栈空,则返回 0 表示不能出栈
        if (topNode == NULL) {
            return 0;
        }
        // 1.2 如果栈不为空,则出栈栈顶元素
        else {
            // 1.2.1 用 ele 保存栈顶元素的值
            *ele = topNode->data;
            // 1.2.2 删除栈顶结点,即将链栈的头结点的 next 指针指向原栈顶结点的后继结点
            (*stack)->next = topNode->next;
            // 1.2.3 释放栈顶结点空间
            free(topNode);
            // 1.2.4 返回 1 表示出栈成功
            return 1;
        }
    }
    

    getTop

    获取链栈的栈顶元素。以 stack=[44, 33, 22, 11] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果栈空则返回 0 表示获取失败。
    • 直接返回栈顶结点的数据域。即头结点的后继结点的数据域。

    实现代码如下:

    /**
     * 获取栈顶元素,但并不出栈
     * @param stack 链栈
     * @param ele 用来保存栈顶元素数据值
     * @return 如果栈空则不能获取栈顶元素则返回 0 表示出栈失败,否则返回 1 表示获取栈顶元素成功
     */
    int getTop(LNode *stack, int *ele) {
        // 1.判断链栈是否为空
        // 1.1 如果栈空,则返回 0 表示失败
        if (stack->next == NULL) {
            return 0;
        }
        // 1.2 如果栈非空,则用 ele 保存栈顶元素的值
        else {
            // 1.2.1 用 ele 保存栈顶元素的值,其中 stack->next 指向栈顶结点
            *ele = stack->next->data;
            // 1.2.2 返回 1 表示获取成功
            return 1;
        }
    }
    

    size

    获取链栈中的结点个数。以 stack=[44, 33, 22, 11] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 声明变量 len 用作计数器,记录链栈结点个数。
    • 从栈顶扫描结点到栈底,统计结点个数。即遍历单链表罢了。

    实现代码如下:

    /**
     * 获得链栈中结点个数
     * @param stack 链栈
     * @return 结点个数
     */
    int size(LNode *stack) {
        // 0.变量,记录链栈的栈顶结点
        LNode *topNode = stack->next;
        // 0.变量,计数器,记录链栈中结点个数
        int len = 0;
        // 1.从栈顶扫描到栈底,统计链栈中结点个数
        while (topNode != NULL) {
            len++;
            topNode = topNode->next;
        }
        // 2.返回结点个数
        return len;
    }
    

    print

    打印链栈中所有结点。

    在这里插入图片描述

    实现步骤:

    • 从栈顶到栈底,扫描栈中所有结点,打印其数据域。即遍历单链表。

    实现代码如下:

    /**
     * 从栈顶到栈底,打印链栈所有结点
     * @param stack 链栈
     */
    void print(LNode *stack) {
        printf("[");
        LNode *topNode = stack->next;
        while (topNode != NULL) {
            printf("%d", topNode->data);
            if (topNode->next != NULL) {
                printf(", ");
            }
            topNode = topNode->next;
        }
        printf("]\n");
    }
    

    clear

    清空链栈,即将链栈的头结点的 next 指针指向 null

    在这里插入图片描述

    实现步骤:

    • 从栈顶到栈底扫描栈中所有结点,释放每一个结点的存储空间。
    • 最后将头结点的 next 指针指向 null,表示是空栈。

    实现代码如下:

    /**
     * 清空链栈
     * @param stack 链栈
     */
    void clear(LNode **stack) {
        // 变量,记录链栈的栈顶结点
        LNode *topNode = (*stack)->next;
        // 从栈顶到栈底扫描栈中所有结点
        while (topNode != NULL) {
            // 记录当前结点的后继结点
            LNode *temp = topNode->next;
            // 释放当前结点的存储空间
            free(topNode);
            // 继续栈的下一个结点
            topNode = temp;
        }
        // 最后将链栈头结点的 next 指针指向 null,表示这是一个空栈
        (*stack)->next = NULL;
    }
    

    destroy

    销毁链栈。

    实现代码如下:

    /**
     * 销毁链栈
     * @param stack 链栈
     */
    void destroy(LNode **stack) {
        // 释放头结点空间
        free(*stack);
    }
    

    练习题

    关于链栈的练习题如下:

    展开全文
  • vs2017编写的链栈(链式存储的栈),包括:创建、销毁、清空、判空、获取元素数、获取栈顶、入栈、出栈、遍历等
  • 基于链栈的四则运算,可将运算表达式自动转化为可用于直接计算的式子,代码规范,有大量注释,对新手友好

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,506
精华内容 6,202
关键字:

链栈