链栈--数据结构学习笔记

链栈--数据结构学习笔记 链栈的创建与插入删除—学习笔记 链栈

是指采用链式存储结构实现的栈，链栈的存储结构如下：

typedef struct StackNode {
    int  data;                  //节点的数据域，这里直接用int型
    struct StackNode *next;     //指针域
} StackNode, *linkstack;

栈的主要 *** 作是在栈顶进行插入和删除， 那么以链表的头部作为栈顶是最方便的， 而且没必要像单链表那样为了 *** 作方便附加一个头结点。

链表的初始化

//初始化
StackNode *StackInit(StackNode *S) {
    S = (linkstack)malloc(sizeof(StackNode));
    S = NULL;
    printf("初始化完成！n");
    return S;
}

链表的入栈

【算法步骤】
（1）为入栈元素 e 分配空间， 用指针 p 指向。
（2）将新结点数据域置为e。
（3）将新结点插入栈顶。
（4）修改栈顶指针为 p。

StackNode *StackPush(StackNode *S, int a) {
    linkstack p;
    p = (linkstack)malloc(sizeof(StackNode));		
    p->data = a;
    p->next = S;
    S = p;
    return S;
}

链表的出栈

【算法步骤】
先判断栈是否为空 ， 若空输出“空栈”。
（1）将栈顶元素打印输出。
（2）临时保存栈顶下一元素。
（3）释放原栈顶元素的空间。
（4）修改栈顶指针， 指向新的栈顶元素。

StackNode *StackPop(StackNode *S) {
    if (S == NULL) {
        printf("空栈n");
    }
    linkstack p;
    printf("出栈元素:%dn", S->data);
    p = S->next;
    free(S);
    S = p;
    return S;
}

打印栈顶元素

【算法步骤】
先判断栈是否为空，不为空将栈顶元素打印输出。

//取栈顶元素
void GetTop(StackNode *S) {
    if (S != NULL) {
        printf("%d", S->data);
    }
}

遍历链表，打印输出

【算法步骤】
先判断栈是否为空，不为空将栈顶元素打印输出，继续打印下一元素，直到为空停止。

void StackPrint(StackNode *S) {
    if (S == NULL){
        printf("空栈");
    }
    while (S != NULL) {
        printf("%d ", S->data);
        S = S->next;
    }
    printf("n");
} 

主函数

int main() {
    StackNode *S;
    int temp;
    S = StackInit(S);
    for (int i = 0; i < N; ++i){    //入栈N个元素，控制台输入
        scanf("%d", &temp);
       S = StackPush(S, temp);
    }
         //直接压栈
    StackPrint(S);                  //打印输出
    S = StackPop(S);                //弹出栈顶元素
    S = StackPop(S);                //弹出栈顶元素                
    StackPrint(S);
}

测试结果：

初始化！
1
2
3
5
7
3
6
8
34
56
56 34 8 6 3 7 5 3 2 1
出栈元素:56
出栈元素:34
8 6 3 7 5 3 2 1

一定要注意链表的首地址，还有函数得使用指针函数，这里简要介绍一下指针函数与函数指针：
指针函数（还是一个函数，返回的是地址）与函数指针（是一个指向函数首地址的指针）
参考博客：函数指针与指针函数

1. 指针函数：int* fun(int x,int y);
   指针函数本质是一个函数，其返回值为指针。
2. 函数指针：int (*fun)(int x,int y);
   函数指针本质是一个指针，其指向一个函数。
3. 可以简单粗暴的理解为，指针函数的*是属于数据类型的，而函数指针的星号是属于函数名的。
   再简单一点，可以这样辨别两者：函数名带括号的就是函数指针，否则就是指针函数。