数据结构-链式栈的实现

逃离我推掉我的手 2022-08-24 11:45 18阅读 0赞

转载自：[http://blog.csdn.net/hopeyouknow/article/details/6725049][http_blog.csdn.net_hopeyouknow_article_details_6725049]

链式栈的实现：

头文件Stack.h

#ifndef Stack_H
    #define Stack_H
    
    typedef int Item;
    typedef struct node * PNode;
    /*定义栈节点类型*/
    typedef struct node
    {
    	Item data;
    	PNode down;
    }Node;
    /*定义栈类型*/
    typedef struct stack
    {
    	PNode top;
    	int size;
    }Stack;
    /*构造一个空栈*/
    Stack *InitStack();
    
    /*销毁一个栈*/
    void DestroyStack(Stack *ps);
    
    /*把栈置空*/
    void ClearStack(Stack *ps);
    
    /*判定是否为空栈*/
    int IsEmpty(Stack *ps);
    
    /*返回栈大小*/
    int GetSize(Stack *ps);
    
    /*返回栈顶元素*/
    PNode GetTop(Stack *ps,Item *pitem);
    
    /*元素入栈*/
    PNode Push(Stack *ps,Item item);
    
    /*元素出栈*/
    PNode Pop(Stack *ps,Item *pitem);
    
    /*遍历栈并访问visit函数*/
    void StackTraverse(Stack *ps,void (*visit)());
    
    #endif

实现部分Stack.c

#include"Stack.h"
    #include<malloc.h>
    #include<stdlib.h>
    /*构造一个空栈*/
    Stack *InitStack()
    {
    	Stack *ps = (Stack *)malloc(sizeof(Stack));
    	if(ps!=NULL)
    	{
    		ps->top = NULL;
    		ps->size = 0;
    	}
    	return ps;
    }
    
    /*判定是否为空栈*/
    int IsEmpty(Stack *ps)
    {
    	if(ps->top == NULL && ps->size == 0)
    		return 1;
    	else
    		return 0;
    }
    
    /*返回栈大小*/
    int GetSize(Stack *ps)
    {
    	return ps->size;
    }
    
    /*元素入栈*/
    PNode Push(Stack *ps,Item item)
    {
    	PNode pnode = (PNode)malloc(sizeof(Node));
    	if(pnode != NULL)
    	{
    		pnode->data = item;
    		pnode->down = GetTop(ps,NULL);
    		ps->size++;
    		ps->top = pnode;
    		
    	}
    	return pnode;
    }
    
    /*返回栈顶元素*/
    PNode GetTop(Stack *ps,Item *pitem)
    {
    	if(IsEmpty(ps)!=1&&pitem!=NULL)
    	{
    		*pitem = ps->top->data;
    	}
    	return ps->top;
    }
    
    
    /*元素出栈*/
    PNode Pop(Stack *ps,Item *pitem)
    {
    	PNode p = ps->top;
    	if(IsEmpty(ps)!=1&&p!=NULL)
    	{
    		if(pitem!=NULL)
    			*pitem = p->data;
    		ps->size--;
    		ps->top = ps->top->down;	
    		free(p);
    	}
    	return ps->top;
    }
    
    /*销毁一个栈*/
    void DestroyStack(Stack *ps)
    {
    	if(IsEmpty(ps)!=1)
    		ClearStack(ps);
    	free(ps);
    }
    
    /*把栈置空*/
    void ClearStack(Stack *ps)
    {
    	while(IsEmpty(ps)!=1)
    	{
    		Pop(ps,NULL);
    	}
    }
    
    /*遍历栈并访问visit函数 */
    void StackTraverse(Stack *ps,void (*visit)())
    {
    	PNode p = ps->top;
    	int i = ps->size;
    	while(i--)
    	{
    		visit(p->data);
    		p = p->down;
    	}
    }

测试部分Test.c

#include"Stack.h"
    #include<stdio.h>
    void print(Item i)
    {
    	printf("该节点元素为%d\n",i);
    }
    main()
    {
    	Stack *ps = InitStack();
    	int i,item;
    
    	printf("0-9依次入栈并输出如下：\n");
    	for(i=0;i<10;i++)
    	{
    		Push(ps,i);
    		GetTop(ps,&item);
    		printf("%d ",item);
    	}
    	
    	printf("\n从栈顶到栈顶遍历并对每个元素执行print函数：\n");
    	StackTraverse(ps,print);
    
    	printf("栈中元素依次出栈并输出如下：\n");
    	for(i=0;i<10;i++)
    	{
    		Pop(ps,&item);
    		printf("%d ",item);
    	}
    	
    	ClearStack(ps);
    	if(IsEmpty(ps))
    		printf("\n将栈置空成功\n");
    	DestroyStack(ps);
    	printf("栈已被销毁\n");
    		
    }

[http_blog.csdn.net_hopeyouknow_article_details_6725049]: http://blog.csdn.net/hopeyouknow/article/details/6725049