设为首页 加入收藏

TOP

C语言 栈(链式栈)(一)
2019-08-13 05:39:26 】 浏览:31
Tags:语言 链式


链式栈的操作一般含有:出栈、入栈、栈的初始化、判断栈是否为空、清空栈,下面先上声明部分代码


#include <stdio.h>
#include <stdlib.h>
#define Empty 0        /* 栈空 */
#define Avail 1        /* 栈可用 */


typedef struct SNode
{
    int data;
    struct SNode *next;
}StackNode;
typedef struct LStack
{
    StackNode *top;        /* 栈顶指针 */
    StackNode *bottom;    /* 栈底指针 */
    int height;            /* 链式栈高度 */
}LinkStack;


LinkStack InitStack (LinkStack pStack);    /* 栈顶指针、栈底指针、栈高度初始化*/
LinkStack Push (LinkStack pStack);        /* 入栈 */
LinkStack Pop (LinkStack pStack);        /* 出栈 */
int StackEmpty (LinkStack pStack);        /* 判断栈是否为空 */
LinkStack DeletStack (LinkStack pStack);/* 清空栈 */
void DisplyStack (LinkStack pStack);    /* 遍历栈----自顶至底*/


一、节点的声明


1 typedef struct SNode
2 {
3    int data;
4    struct SNode *next;
5 }StackNode;


链式栈节点的声明与单向链表的声明相同,都是由数据域和指针域组成,这里不再赘述


二、栈顶、栈底、栈高度的声明


1 typedef struct LStack
2 {
3    StackNode *top;        /* 栈顶指针 */
4    StackNode *bottom;    /* 栈底指针 */
5    int height;            /* 链式栈高度 */
6 }LinkStack;


三、函数声明


1 LinkStack InitStack (LinkStack pStack);    /* 栈顶指针、栈底指针、栈高度初始化*/
2 LinkStack Push (LinkStack pStack);        /* 入栈 */
3 LinkStack Pop (LinkStack pStack);        /* 出栈 */
4 int StackEmpty (LinkStack pStack);        /* 判断栈是否为空 */
5 LinkStack DeletStack (LinkStack pStack);/* 清空栈 */
6 void DisplyStack (LinkStack pStack);    /* 遍历栈----自顶至底*/


链式栈和单向链表的区别


上面已经提到的是链式栈是一种操作受限的单向链表(废话··),先来回顾一下单向链表的建立过程(不清楚单向链表的可以先之前的另一篇随笔链表(单向链表的建立、删除、插入、打印)),单向链表在添加新的节点的时候是将原链表最后一个节点的


指针域指向新建的节点,然后新建节点指针域置为NULL作为链表的最后一个节点,而链式栈在添加新的节点的时候操作就不太一样了,先来分析下栈的操作,栈只是栈顶来做插入和删除操作,那么栈顶放在链表的头部还是尾部呢?由于单向链表有头指针


而栈顶指针也是必须的,那么就把栈顶指针当作头指针来使用,比较好的办法是把栈顶放到单链表的头部。另外栈顶在头部了,那么单链表的头结点也就失去了意义,通常对于链式栈来说,是不需要头结点的,现在来说链式栈添加新节点的操作


链式栈:新一个节点->将新建节点的指针域指向原栈顶节点->将栈顶指针移动到新建节点


单向链表:新建一个节点->将原链表最后的一个节点的指针域指向新建节点->新建节点的指针域置为NULL作为新链表的最后一个节点


为了方便读者更加直观了解这个过程下面上图:



链式栈操作部分


一、入栈


/* Function: 入栈 */
LinkStack Push (LinkStack pStack)
{
    int data;
    StackNode *temp;


    if ((temp = (StackNode *)malloc(sizeof(StackNode))) == NULL)
    {
        printf("内存空间不足\n");
        return pStack;
    }
    if (StackEmpty(pStack) == Empty)    /* 如果栈为空 */
    {
        pStack.top = pStack.bottom = temp;    /* 栈顶、栈底指针都指向新建节点 */
        temp->next = NULL;                /* 节点指针域为空 */
        printf("Please input data");
        scanf("%d", &data);
        pStack.top->data = data;
        pStack.height++;


        return pStack;
    }
    else        /* 栈不为空 */
    {
        temp->next = pStack.top;/* 新建节点指向原来的栈顶 */
        pStack.t
编程开发网

首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C语言 栈(顺序栈) 下一篇链表(单向链表的建立、删除、插..