数据结构——链栈的实现（C语言）

布满荆棘的人生 2022-08-25 05:23 234阅读 0赞

**大家都知道栈的顺序存储的效率低，对删除和插入不方便操作。栈的链式实现操作方便，只需改变链栈的指针域指针的方向，不需要移动数据项。链栈只能在栈顶操作，也就是说只能在栈顶入栈和出栈。**

**以下是源程序：**

**函数声明：**

#ifndef Stack_H
    #define Stack_H
    
    typedef int Item;
    typedef struct node * PNode;
    typedef struct node
    {
    	Item data;
    	PNode next;
    }Node;
    
    typedef struct stack *PStack;
    typedef struct stack
    {
    	Item size;
    	PNode top;
    }Stack;
    
    /***创建空栈，并返回栈顶***/
    PStack Creat_Stack();
    
    /***判断是否为空栈***/
    int Is_Empty(PStack);
    
    /***数据项入栈***/
    PStack Push_Stack(PStack,Item);
    
    /***计算栈的大小***/
    int Size_Stack(PStack);
    
    /***返回栈顶数据项***/
    Item Get_Item_Stack(PStack);
    
    /***数据项出栈***/
    Item Pop_Stack(PStack);
    
    /***清空链栈***/
    void Clear_Stack(PStack);
    
    /***遍历栈，并自栈顶输出数据项***/
    void Traverse_Stack(PStack);
    #endif

函数定义：

#include<stdio.h>
    #include<stdlib.h>
    #include"Stack.h"
    
    /***创建空栈，并返回栈顶***/
    PStack Creat_Stack()
    {
    	PStack P=(PStack)malloc(sizeof(Stack));
    	if(NULL!=P)
    	{
    		P->top=NULL;
    		P->size=0;
    	}
    	return P;
    }
    
    /***判断是否为空栈***/
    int Is_Empty(PStack P)
    {
    	if(0==P->size && NULL==P->top)
    		return 1;
    	else
    		return 0;
    }
    
    /***数据项入栈***/
    PStack Push_Stack(PStack P,Item val)
    {
    	PNode PNew=(PNode)malloc(sizeof(Node));
    	if(NULL==PNew)
    	{
    		printf("Malloc the PNew is failed.\n");
    		exit(1);
    	}
    	else
    	{
    		PNew->data=val;
    		PNew->next=P->top;
    		P->top=PNew;
    		P->size++;
    	}
    	return P;
    }
    
    /***计算栈的大小***/
    int Size_Stack(PStack P)
    {
    	/*int size=0;
    	PNode PCurrent=(PNode)malloc(sizeof(Node));
    	PCurrent=P->top;
    	while(NULL!=PCurrent)
    	{
    		size++;
    		PCurrent=PCurrent->next;
    	}
    	return size;*/
    	return P->size;
    }
    
    /***返回栈顶数据项***/
    Item Get_Item_Stack(PStack P)
    {
    	if(NULL!=P->top->data && Is_Empty(P)==0)
    		return P->top->data;
    }
    
    /***数据项出栈***/
    Item Pop_Stack(PStack P)
    {
    	Item data;
    	PNode temp=P->top;
    	if(NULL==temp)
    	{
    		printf("The stack is empty.\n");
    		exit(1);
    	}
    	data=temp->data;
    	P->top=temp->next;
    	P->size--;
    	free(temp);
    	return data;
    }
    
    /***清空链栈***/
    void Clear_Stack(PStack P)
    {
    	if(Is_Empty(P))
    		printf("The stack had enpty.\n");
    	PNode PCurrent=P->top;
    	int i=P->size;
    	while(i--)
    	{
    		P->top=PCurrent->next;
    		P->size--;
    		free(PCurrent);
    		PCurrent=P->top;
    	}
    }
    
    /***遍历栈，并自栈顶输出数据项***/
    void Traverse_Stack(PStack P)
    {
    	 PNode PCurrent = P->top;  
        int i = P->size; 
    	printf("The data of stack are:");
        while(i--)  
        {  
            printf("%d  ",PCurrent->data);  
            PCurrent = PCurrent->next;  
        } 
    	printf("\n");
    }

程序测试：

#include<stdio.h>
    #include<stdlib.h>
    #include"Stack.h"
    
    int main()
    {
    	int size=0;
    	int top_data,Pop_data;
    	PStack PS;
    	PS=Creat_Stack();
    	if(NULL!=PS)
    		printf("The stack is created.\n");
    
    /***判断是否为空栈***/
    	if(Is_Empty(PS))
    		printf("The stack is empty.\n");
    
    /***数据项入栈***/
    	Push_Stack(PS,2);
    	Push_Stack(PS,3);
    	Push_Stack(PS,5);
    	Traverse_Stack(PS);
    
    /***计算栈的大小***/
    	size=Size_Stack(PS);
    	printf("The length of stack is: %d\n",size);
    	
    /***返回栈顶数据项***/
    	top_data=Get_Item_Stack(PS);
    	printf("The top of data is: %d\n",top_data);
    
    /***数据项出栈***/
    	Pop_data=Pop_Stack(PS);
    	printf("The Pop of data is: %d\n",Pop_data);
    	Traverse_Stack(PS);
    
    /***清空链栈***/
    	Clear_Stack(PS);
    	Traverse_Stack(PS);
    	
    	return 0;
    }