链栈的基本操作C语言详解

た入场券 2023-07-18 04:50 38阅读 0赞

**1. 带头结点和不带头结点的链栈实现方式不同，我这里是不带头结点的链栈。  
2. 头指针(Lhead)：不是头结点的指针，是指向头结点（首元结点）的指针，无论链栈是否为空，头指针均存在。  
3. 二级指针：指向指针变量的指针。  
4. 存储结构如图![在这里插入图片描述][20200324123901367.png]  
5. 编译环境：vc6.0。**

**代码如下：**

#include <stdio.h>
    #include <stdlib.h>
    
    //存储类型结构
    typedef struct StackNode
    { 
    	int data;								 //结点数据
    	struct StackNode* next;					//结点指针
    }StackNode, * LinkStack;
    
    //***********************销毁链栈****************************
    int DestoryLinkStack(LinkStack* Lhead)						//形参接收头指针地址（二级指针） 
    { 
    	StackNode* p, * q;										//结点指针
    	p = (*Lhead)->next;										//指向第二个结点
    	q = *Lhead;												//q指向首元结点
    	while (p)											  //第二个结点不为空
    	{ 
    		free(q);                                        //释放首元结点
    		q = p;											//q指向新首元结点
    		p = p->next;									//p->指向新的第二结点
    	}
    	free(q);										 //释放首元结点
    	*Lhead = NULL;									 //头指针指向空，头指针是指向首元结点的指针
    	return 1;
    }
    
    //**********************判断链栈是否为空*********************
    int LinkStackEmpty(StackNode* Lhead)			 //判断链栈是否非空
    { 
    	if (Lhead == NULL)
    		return 1;
    	else return 0;
    }
    
    //*************************入栈**************************
    int Push(LinkStack* Lhead, int e)									//形参Lhead接收头指针地址(二级指针)，e接收入队元素值
    { 
    	LinkStack s = (LinkStack)malloc(sizeof(StackNode));				 //动态申请内存
    	if (s == NULL)													//申请失败
    	{ 
    		printf("动态内存申请失败\n");
    		return 0;
    	}
    	s->data = e;
    	s->next = *Lhead;										 //插入新结点
    	*Lhead = s;												//头指针指向新首元结点
    	return 1;
    }
    
    //****************************出栈***************************
    int Pop(LinkStack* Lhead, int* e)                           //形参Lhead接收头指针地址(二级指针)，e接收入队元素值 
    { 
    	StackNode* p = *Lhead;									//p指向首元结点
    	if (LinkStackEmpty(p))                               //若空 
    		return 0;
    	*e = p->data;                                          //获取返回值
    	*Lhead = p->next;                                       //出栈，Lhead指针下移
    	free(p);												//释放首元结点
    	return 1;
    }
    
    //************************************遍历输出*******************************
    int StackTraverse(StackNode* Lhead)							//形参Lhead接收头指针
    { 
    	StackNode* p = Lhead;									//头指针赋值给p
    	if (p == NULL)											//栈空,头指针指向空
    		return 0;
    	while (p != NULL)											//头指针不指向NULL
    	{ 
    		printf("%-5d", p->data);							//打印数据
    		p = p->next;
    	}
    	return 1;
    }
    
    int main()
    { 
    	int i, e, n;                                  //e结点元素,n元素个数
    	LinkStack Lhead = NULL;                    //头指针,初始化为空
    	if (LinkStackEmpty(Lhead))
    		printf("链表为空\n");
    	else printf("链表不为空\n");
    
    	printf("输入插入元素个数\n");                    //插入测试
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    	{ 
    		printf("输入元素第%d个元素e的值\n", i + 1);
    		scanf("%d", &e);
    		if (Push(&Lhead, e))
    			printf("进栈成功\n");
    		else printf("进栈失败\n");
    	}
    	if (!StackTraverse(Lhead))                         //遍历输出测试
    		printf("链栈为空\n");
    
    	if (Pop(&Lhead, &e))								//出栈测试
    		printf("\n\n元素%d出栈\n", e);
    	else printf("\n出栈失败\n");
    	printf("出栈后\n");
    	if (!StackTraverse(Lhead))							 //遍历输出测试
    		printf("链栈为空\n");
    
    	if (LinkStackEmpty(Lhead))                         //判空测试
    		printf("链表为空\n");
    	else printf("链表不为空\n");
    
    	DestoryLinkStack(&Lhead);								//销毁测试
    	printf("销毁后\n");
    	if (!StackTraverse(Lhead))
    		printf("链栈为空\n");
    
    	return 0;
    }

***测试结果***：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]

[20200324123901367.png]: /images/20230528/795e08d4252d446eb43fcba2483ab4b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/2e9ccfc4632e44e7b9b4afcdb4aada10.png