链式栈(Chain stack)

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

 规定了某些操作的线性表——栈

当规定线性表的插入和删除操作都必须在线性表的一个端点进行，而不能在其他的任何位置时，这样的线性表就叫做栈(stack)。

 

 

#ifndef LINKSTACK_H
#define LINKSTACK_H

#include <stdlib.h>//malloc
#include <stdbool.h>//bool

//链表节点的数据类型默认是　int
#ifndef LINKSTACK_DATATYPE
#define LINKSTACK_DATATYPE int
#endif

typedef LINKSTACK_DATATYPE datatype;//取别名

/*
 * 链式栈节点类型
 * 即链表节点类型
*/

struct node
{
  //数据域
  datatype data;
  //单链表指针域
  struct node *next;
};

/*
 * 链式栈的管理结构体
 */
typedef struct
{
    //栈顶元素指针
    struct node *top;
    //链表节点个数
    int size;
}linkstack;

/*
 * 初始化链式栈的管理结构体
 * 参数：无
 * 返回值：
 *      成功：返回链式栈的管理结构体指针
 *      失败：返回NULL
 */
static linkstack *init_linkstack(void)
{
    linkstack *ls = malloc(sizeof(linkstack));
    if(ls != NULL)
    {
        //初始时　链式栈的节点个数为0
        ls->size = 0;
        //初始时　链式栈的栈顶指针指向空
        ls->top = NULL;
    }
    return ls;
}

/*
 * 链式栈的管理结构体
 * 参数：
 *      man_struct：链式栈的管理结构体指针
 * 返回值：
 *      链式栈为空：返回true
 *      链式栈非空：返回false
 */
static bool linkstack_empty(linkstack *man_struct)
{
    //栈中节点元素个数为0
    return man_struct->size == 0;
}


/*
 *将新节点入栈
 *参数：
 *     man_struct：链式栈的管理结构体指针
 *     new_node：新节点的指针
 * 返回值：无
 */
static void linkstack_push(linkstack *man_struct,struct node * new_node)
{
    //新节点的指针　指向　原栈顶的节点
    new_node->next = man_struct->top;
    //更新原栈顶的节点(栈顶指针指向新节点)
    man_struct->top = new_node;
    //链式栈的元素加1
    man_struct->size++;
}

/*
 * 读取栈顶节点的数据域
 * 参数：
 *     man_struct：链式栈的管理结构体指针
 *     save_node：指向栈顶指针的　指针
 * 返回值：
 *     成功：返回true
 *     失败：返回false
 */
static bool linkstack_top(linkstack *man_struct,struct node **save_node)
{
    //栈空则失败
    if(linkstack_empty(man_struct))
        return false;

    //为用户提供栈顶节点地址
    *save_node = man_struct->top;
    return true;
}

/*
 *节点出栈
 * 参数：
 *      man_struct：链式栈的管理结构体指针
 *返回值：
 *      成功：返回true
 *      失败：返回false(栈空)
 */
static bool linkstack_pop(linkstack *man_struct)
{
    //栈空就失败
    if(linkstack_empty(man_struct))
        return false;

    //栈顶节点准备出栈
    struct node *p = man_struct->top;

    //管理结构体的栈顶指针指向下面的节点
    man_struct->top = man_struct->top->next;
    //栈节点的元素减1
    man_struct->size--;

    p->next = NULL;//取消指向
    free(p);//释放节点
    return true;
}
/*
 *遍历链式栈　回调　用户实现的访问数据域的函数
 * 参数：
 *     man_struct：链式栈的管理结构体
 *     hander：用户实现的函数　的指针
 */
static bool linkstack_travel(linkstack *man_struct,void (*hander)(datatype))
{
   //链式栈为空则失败
   if(linkstack_empty(man_struct))
       return false;

   //记录链式栈节点的指针(过渡使用)
   struct node *t = man_struct->top;
   while(1)
   {
       //调用用户实现的访问数据域的函数
        hander(t->data);
        //下一个节点
        t = t->next;

        //如果遍历结束则退出while
        if(t == NULL)
            break;
   }
   return true;
}

/*
 * 链式栈回归初始化
 * 参数：
 *      **man_struct：链式栈的管理结构体指针　的指针
 * 返回值：无
 */
static void uninit_linkstack(linkstack **man_struct)
{
    //从栈顶开始释放节点
    struct node *d = (*man_struct)->top;
    while(d)//非空
    {
        //记录下一个节点
        struct node *tmp = d->next;
        //释放该当前节点
        free(d);
        //下一个节点
        d = tmp;
    }
    //回归初始化
    (*man_struct)->top = NULL;
    (*man_struct)->size = 0;
}

#endif // LINKSTACK_H

/*main.c*/
#include <stdio.h>

#define LINKSTACK_DATATYPE int
#include "linkstack.h"

/*
 * 申请内存存放新节点
 * 参数：
 *      data：节点的数据域(根据实际情况)
 * 返回值：
 *      新节点的地址(堆内存地址)
 */
static struct node *new_node(int data)
{
    struct node *n = malloc(sizeof(struct node));
    if(n != NULL)
    {
        n->data = data;//数据域
        n->next = NULL;//指针域
    }
    return n;
}

/*
 * 用户实现的访问数据域的函数　回调
 * 参数：
 *      data：数据
 * 返回值：无
 */
void show(int data)
{
    printf("%d",data);
}

/*
 *主函数
 */
int main()
{
    //初始化链式栈的管理结构体
    linkstack *man_struct = init_linkstack();
    if(man_struct == NULL)
    {
        perror(" ");
        return 0;
    }

    int num,tmp;

    while(1)
    {
        printf("输入：");

        if(scanf("%d",&num) !=1)
        {
            //清空非法输入
            while(getchar()!='
');
            continue;
        }

        if(num == -1)//来个结束
            return 0;

        while(1)
        {
            tmp = num/8;//短除法
            //余数入栈
            linkstack_push(man_struct,new_node(num%8));

            if(tmp == 0)//计算完毕则退出while循环
                break;

            num = tmp;//否者继续
        }

        printf("p is :0");
        //遍历链式栈(只读)
        linkstack_travel(man_struct,show);

        printf("
");

        //链式栈的管理结构体回归初始化
        uninit_linkstack(&man_struct);
    }

    return 0;
}

输入：0
p is :00
输入：8
p is :010
输入：7
p is :07
输入：256256
p is :0764400
输入：-1
Press <RETURN> to close this window...