首页 > 代码库 > 链式栈

链式栈



1.编写头文件

#definedatatypeint

structstatcknode

{

   intnum;                //编号

   datatypedata;          //数据

   structstatcknode *pNext;//指针域

};

 

typedefstructstatcknodeStackNode;

 

//初始化

StackNode *init(StackNode *pHead);

//进栈

StackNode *push(StackNode *pHead,intnum,datatypedata);

//出栈

StackNode *pop(StackNode * pHead,StackNode *poutdata);

//清空

StackNode *freeall(StackNode *pHead);

//打印

StackNode *printfAll(StackNode *pHead);

 

2.编写链表的实现代码

#include"stacklinknode.h"

#include"stdio.h"        //NULLstdio.h

#include"stdlib.h"       //mallocstdlib.h

 

//初始化

StackNode *init(StackNode *pHead)

{

   returnNULL;

}

 

//进栈

StackNode *push(StackNode *pHead,intnum,datatypedata)

{

   StackNode *pNewNode = (StackNode *)malloc(sizeof(StackNode));

   pNewNode->num = num;

   pNewNode->data = data;

   pNewNode->pNext = NULL;

   //如果是空的链式栈

   if (pHead == NULL)

   {

       pHead =pNewNode;

   }

   else

   {

       //备份一个头指针

       StackNode *p = pHead;

       while (p->pNext != NULL)

       {

           //一直向前

           p =p->pNext;

       }

       //插入

       p->pNext = pNewNode;

   }

   //返回头结点

   returnpHead;

}

 

//出栈

StackNode *pop(StackNode * pHead,StackNode *poutdata)

{

   if (pHead == NULL)

   {

       //已经没有元素

       returnNULL;

   }

   //表示只有一个元素的时候

   elseif (pHead->pNext == NULL)

   {

       poutdata->num = pHead->num;

       poutdata->data = pHead->data;  //取出数据

       free(pHead);//释放内存

       pHead =NULL;

       returnpHead;

   }

   else

   {

       StackNode *p = pHead;

       //表示栈顶的倒数第二个节点

       while (p->pNext->pNext != NULL)

       {

           //循环到倒数第二个节点

           p =p->pNext;

       }

       poutdata->num = p->pNext->num;

       //取出数据

       poutdata->data = p->pNext->data;

       p->pNext = NULL;

 

       returnpHead;

   }

}

 

//清空

StackNode *freeall(StackNode *pHead)

{

   if (pHead == NULL)

   {

       returnNULL;

   }

   else

   {

       StackNode *p1 = NULL, *p2 = NULL;

       //头结点

       p1 =pHead;

       while (p1->pNext != NULL)

       {

           //保存下一个节点

           p2 =p1->pNext;

           //跳过p2

           p1->pNext = p2->pNext;

           //释放节点

           free(p2);

       }

       free(pHead);

 

       returnNULL;

   }

}

 

//打印

StackNode *printfAll(StackNode *pHead)

{

   if (pHead == NULL)

   {

       returnNULL;

   }

   else

   {

       printf("%d,%d,%p,%p\n",pHead->num,pHead->data,pHead,pHead->pNext);

       //通过递归的方式进行打印

       printfAll(pHead->pNext);

   }

}

 

3.实现代码main.c

#pragma warning(disable:4996)

//#define_CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#include"stacklinknode.h"

 

voidmain1()

{

   intnum;

   scanf("%d", &num);

   //打印数据

   printf("num = %d\n",num);

   //创建一个链式栈的头节点

   StackNode *pHead = NULL;

   printf("\n\n");

   //通过这种方式实现打印打印十进制的二进制的表现形式

   while (num)

   {

       printf("%d\n",num % 2);

       pHead =push(pHead,num % 2, 0);

       num /= 2;

   }

 

   while (pHead != NULL)

   {

       StackNode *pOut = (StackNode *)malloc(sizeof(StackNode));

       pHead =pop(pHead,pOut);

       printf("%d",pOut->num);

   }

 

   system("pause");

}

 

voidmain()

{

    StackNode *pHead = NULL;//创建一个链式栈的头节点

    pHead =init(pHead);   //设置栈为NULL

    pHead =push(pHead, 1, 1);

    pHead =push(pHead, 2, 11);

    pHead =push(pHead, 3, 111);

    pHead =push(pHead, 4, 1111);

    pHead =push(pHead, 5, 11111);

 

    printfAll(pHead);

 

    /* pHead =freeall(pHead);

    printf("\n释放以后");

    printfAll(pHead);*/

 

    while (pHead != NULL)

    {

        //保存出栈的数据

        printf("出栈\n");

        StackNode *pOut = (StackNode *)malloc(sizeof(StackNode));

        pHead =pop(pHead,pOut);

        printf("出栈之后\n");

        printfAll(pHead);

        printf("\n出栈之后的数据%d,%d",pOut->num,pOut->num);

    }

 

    system("pause");

}