链式堆栈

快来打我* 2023-03-12 09:20 22阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70][]

链式堆栈本体就是一个单链表，进行插入和删除操作的一端就是栈顶，另一端是栈底。显然把靠近头指针的一端设为栈顶，进行操作时不需要遍历链表，提高了执行效率。

头文件：

typedef int DataType;
    #include<stdio.h>
    #include<stdlib.h>
    #include <cstdlib>
    
    
    //就是单链表的定义 
    typedef struct snode
    {
    	DataType data;
    	struct snode *next;
    }LSNode;
    //初始化
    void StackInitiate(LSNode **head)
    {
    	//初始化带头结点的链式堆栈 
    	*head = (LSNode *)malloc(sizeof(LSNode));
    	(*head)->next = NULL;
     } 
    //判断是否为空
    int StackNotEmpty(LSNode *head)
    {
    	if(head->next==NULL) return 0;
    	else return 1;
     } 
    //入栈
    void StackPush(LSNode *head, DataType x)
    {
    	LSNode *p;
    	p = (LSNode *)malloc(sizeof(LSNode));
    	p->data = x;
    	p->next = head->next;
    	head->next = p; 
     } 
     //出栈
     int StackPop(LSNode *head,DataType *d)
     {
     	LSNode *p =head->next;
     	if(p==NULL)
     	{
     		printf("堆栈已空，出错！");
    		 return 0; 
    	 }
    	head->next = p->next;
    	*d = p->data;
    	free(p);
    	return 1;
      } 
    //取栈顶元素
    int StackTop(LSNode *head,DataType *d)
    {
    	LSNode *p = head->next;
    	if(p==NULL)
    	{
    		printf("堆栈已空出错！\n");
    		return 0;
    	}
    	*d = p->data;
    	return 1;
     } 
    //撤销动态申请空间
    void Destroy(LSNode *head)
    {
    	LSNode *p,*p1;
    	p= head;
    	while(p!=NULL)
    	{
    		p1=p;
    		p=p->next;
    		free(p1);
    	}
     }

测试：

#include<stdio.h>
    #include "head.h"
    int main()
    {
    	LSNode *myLSNode;
    	StackInitiate(&myLSNode);
    	int i,x;
    	for(i=0;i<8;i++)
    	{
    		StackPush(myLSNode,i+1);
    	}
    	StackTop(myLSNode,&x);
    	printf("当前栈顶数据元素为：%d/n",x);
    	printf("依次出栈的数据元素序列如下：\n");
    	while(StackNotEmpty(myLSNode))
    	{
    		StackPop(myLSNode,&x);
    		printf("%d ",x);
    	 } 
    	 Destroy(myLSNode);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70]: /images/20230312/dbfe297482aa4c5eb5d46c4e4f350479.png