c语言描述：数据结构【四.栈与队列】（链栈的使用）

深藏阁楼爱情的钟 2022-11-02 15:24 159阅读 0赞

### 笔记目录 ###

*  前言
 *  结构体使用
 *  栈的初始化
 *  压栈操作
 *  遍历操作
 *  判断栈是否为空
 *  出栈操作
 *  清除数据操作

# 前言 #

这些代码均为自己在郝斌老师教学的基础下自己的理解与补充，以及一些详细的解释

# 结构体使用 #

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    typedef struct Node
    { 
       int data;
       struct Node* pNext;
    }node,*pnode;
    typedef struct Stack
    { 
       pnode pTop;
       pnode pBottom;
    }stack,*pStack;

# 栈的初始化 #

void init(pStack p)
    { 
       p->pTop=(pnode)malloc(sizeof(node));
       if (NULL == p->pTop)
    	{ 
    		printf("动态内存分配失败!\n");
    		exit(-1);
    	}
       else
       { 
           p->pBottom=p->pTop;
           p->pTop->pNext=NULL;//将栈顶和底都指向一个节点并初始化
        }
    }

# 压栈操作 #

void push(pStack p,int val)
    { 
       pnode pNew=(pnode)malloc(sizeof(node));//创建新节点
       pNew->data=val;//放入数据
       pNew->pNext=p->pTop;//必须是top，因为只有空栈的时候栈顶和栈底指向同一个节点，而若是top，能保证新节点在刚刚栈顶上放变成新栈顶
       p->pTop=pNew;
       return;//用来结束函数
    }

# 遍历操作 #

void traverse(pStack pS)
    { 
       pnode p =pS->pTop;
       while(p!=pS->pBottom)//p相当于一个滑动的指针，bottom实际上变成了是否栈底的标志
       { 
          printf("%d",p->data);
          p=p->pNext;//p借助尾结点可以到下一个节点
       }
       printf("\n");
       return;
    }

# 判断栈是否为空 #

int empty(pStack ps)
    { 
       if(ps->pTop==ps->pBottom)//同时指向一个节点则为空
        return 1;
       else
        return 0;
    }

# 出栈操作 #

int pop(pStack ps,int *temp)//把pS所指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败，返回false,否则返回tru
    { 
       if(empty(ps)==1)
       { 
           return 0;
       }
       else
       {   
           pnode r=ps->pTop;
           *temp=r->data;
           ps->pTop=r->pNext;//指向下一个
           free(r);
           r=NULL;
        }
       return 1;
    }

# 清除数据操作 #

void clear(pStack ps)
    { 
       if(empty(ps)==1)
       { 
           return;
       }
       else
       { 
          pnode p=ps->pTop;
          pnode q=NULL;
          while(p!=ps->pBottom)//判断p是否到栈底
          { 
              q=p->pNext;
              free(p);//这样操作不会内存泄漏
              p=q;
          }
       }
    
    }