数据结构——栈（链式结构）

一、栈的链式存储结构

如果一个栈存在频繁进栈和出栈操作，可以考虑链式结构。

栈的链式存储结构是指使用链表来实现栈这种数据结构。在链式存储结构中，栈的每个元素被封装成一个节点，节点之间通过指针相连，形成一个链表。栈顶元素对应链表的头部，栈底元素对应链表的尾部。这种结构可以动态地分配和管理存储空间，适合于需要频繁插入和删除操作的场景。

二、栈的基本操作（链表）

1、链栈的结构

typedef char SElemType;

/*栈元素结构体*/
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*StackLinkList;

/*链栈结构体*/
typedef struct {
    StackLinkList top;
    SElemType count;
}StackLink;

2、创建空栈

/*创建一个空栈*/
int StackInit(StackLink *S){
    if(!S->top){
        return ERROR;
    }
    S->top = (StackLinkList)malloc(sizeof(StackLinkList));
    S->top = NULL;
    S->count = 0;
    return OK;
}

3、插入栈顶元素

/*插入元素e为新的栈顶元素*/
int StackPush(StackLink *S,SElemType e){
    StackLinkList p = (StackLinkList)malloc(sizeof(StackLinkList));
    p->data = e;
    p->next = S->top;/* 把当前的栈顶元素赋值给新结点的直接后继*/
    S->top = p;/* 将新的结点s赋值给栈顶指针*/
    S->count++;
    return OK;
}

4、 删除栈顶元素

/*若栈不空，则删除S的栈顶元素*/
/*将栈顶结点赋值给 p
 使得栈顶指针下移一位,指向后一结点
 释放结点p*/
int StackPop(StackLink *S){
    if(StackEmpy(S))
    {
        return ERROR;
    }
    SElemType e = S->top->data;
    StackLinkList q;
    q = S->top;
    S->top = S->top->next;
    free(q);
    S->count--;
    return e;
}

5、清空栈元素

/*清空所有的栈元素*/
void clearStack(StackLink *S){
    if(!S->top){
        return;
    }
    StackLinkList q;
    while (S->count != 0)
    {
        q = S->top;
        S->top = S->top->next;
        free(q);
        S->count--;
    }  
}

6、打印所有栈元素

1）按出栈顺序打印

/*打印所有的栈元素*/
void printStack(StackLink *S,char *arr,int *size){
    if(!S->top){
        return;
    }
    int i = 0;
    StackLinkList ptr;
    ptr = S->top;
    while (ptr != NULL)
    {
        // printf("%c",ptr->data);
        arr[i++] = ptr->data;
        ptr = ptr->next;
    } 
    // printf("\n");
    *size = i;
}

2）按入栈顺序打印

核心思想是采用递归的栈底开始向栈顶打印元素。

/*打印所有的栈元素逆序*/
void printResverStack(StackLinkList S){
    if(S == NULL){
        return;
    }
    printResverStack(S->next);
    printf("%c",S->data);
}

三、栈案例分析

案例：输入一串字符串，并判断该字符串是否为对称串。

代码思路：将字符串输入到栈中，并存储出栈元素到数组中，并将数组中的元素倒序输入到另一个数组中，判断两个数组元素是否一致。

代码示例：

#include "LinkStack.h"

int main()
{
    StackLink Slist;
    SElemType arr[50];
    SElemType arr1[50];
    printf("本程序判断字符串是否为对称串\n");
    char ch;
    int size = 0;
    int j = 0;
    int i = 0;
    while (1)
    {
        StackInit(&Slist);
        ch = '\0'; 
        arr[50] = '\0';
        arr1[50] = '\0';
        j = 0;
        printf("请输入字符串(输入q或者Q结束):");
        while(1)
        {
            ch = getchar();
            if(ch == '\n'||ch == 'q'||ch == 'Q'){
                break;
            }
            StackPush(&Slist,ch);
        }
        if(ch == 'q'||ch == 'Q'){
            break;
        }

        printStack(&Slist,arr1,&size);
        for(int i = 0;i < size;i++)
        {
            arr[size-i-1] = arr1[i];
        }
        for(int i = 0;i < size;i++)
        {
            if(arr1[i] != arr[i])
            {
                j = 1;
                break;
            }
        }
        if(j == 0){
            printf("是对称串\n");
        }
        else{
            printf("不是对称串\n");
        }
    }
    clearStack(&Slist);
    printf("程序结束，再见！\n");
    return 0;
}

运行结果：

 

四、链栈的适用情况

对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的 优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

原文地址：https://blog.csdn.net/weixin_56362288/article/details/140580381

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！