(C语言)栈的链式实现(数据结构九)

怼烎@ 2022-09-17 10:24 202阅读 0赞

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：

//定义数据结构中要用到的一些变量和类型
    #ifndef HEAD_H
    #define HEAD_H
    
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    #define TRUE  1
    #define FALSE 0
    #define OK    1
    #define ERROR  0
    #define INFEASIBLE -1
    #define OVERFLOW   -2    //分配内存出错
    
    typedef int  Status;     //函数返回值类型
    typedef int  ElemType;   //用户定义的数据类型
    
    #endif

2.数据结构实现

typedef struct Node{
    	ElemType data;
    	struct Node* next;
    }Node,*pNode;
    
    typedef struct Stack{
    	pNode base;
    	pNode top;
    	int   length;
    }Stack,*pStack;

3.栈的链式实现

LinkStack.h中代码如下：

#ifndef LINKSTACK_H
    #define LINKSTACK_H
    
    #include "head.h"
    
    typedef struct Node{
    	ElemType data;
    	struct Node* next;
    }Node,*pNode;
    
    typedef struct Stack{
    	pNode base;
    	pNode top;
    	int   length;
    }Stack,*pStack;
    
    
    //初始化栈
    Status InitStack(pStack &S){
    	S=(pStack)malloc(sizeof(Stack));
    	if(!S) return OVERFLOW;
    	S->length=0;
    	S->base=(pNode)malloc(sizeof(Node));
    	if(!S->base) return OVERFLOW;
    	S->top=(pNode)malloc(sizeof(Node));
    	if(!S->top) return OVERFLOW;
    	S->top->next=S->base;
    	return OK;
    }
    
    Status freeStack(pStack &S){
    	free(S);
    	S=NULL;
    	return OK;
    }
    
    //清空栈
    Status ClearStack(pStack &S){
    	if(S==NULL) return ERROR;
    	pNode p=S->top;
    	while(p->next!=S->base){
    		pNode q=p;
    		p=p->next;
    		free(q);
    		q=NULL;
    	}
    	S->top=p;
    	S->length=0;
    	return OK;
    }
    //销毁栈
    Status DestroyStack(pStack &S){
    	if(S==NULL) return ERROR;
    	ClearStack(S);
    	free(S->base);
    	S->base=NULL;
    	free(S->top);
    	S->top=NULL;
    	freeStack(S);
    	S==NULL;
    	return OK;
    }
    //栈是否为空
    Status StackEmpty(pStack S){
    	return S->length<=0;
    }
    //栈长度
    int StackLength(pStack S){
    	return S->length;
    }
    //得到栈顶数据级e
    Status GetTop(pStack S,ElemType &e){
    	e=S->top->next->data;
    	return OK;
    }
    //入栈
    Status Push(pStack &S,ElemType e){
    	if(S->length==0){
    		S->base->data=e;
    	}
    	else{
    		pNode p=S->top;
    		p->data=e;
    		pNode q=(pNode)malloc(sizeof(Node));
    		q->next=p;
    		S->top=q;
    	}
    	S->length++;
    	return OK;
    }
    //出栈
    Status Pop(pStack &S,ElemType &e){
    	if (S->length<=0) return ERROR;
    	if(S->length==1){
    		e=S->base->data;
    		S->length--;
    	}else{
    		pNode p=S->top;
    		S->top=p->next;
    		e=S->top->data;
    		free(p);
    		S->length--;
    	}
    	return OK;
    }
    
    Status print(ElemType e){
    	printf("%d\n",e);
    	return OK;
    }
    
    //用vistit遍历栈
    Status StackTraverse(pStack S,Status(*visit)(ElemType)){
    	pNode p=S->top;
    	do 
    	{
    		p=p->next;
    		(*visit)(p->data);
    	} while (p!=S->base);
    	return OK;
    }
    Status printStack(pStack S){
    	if (S==NULL ||S->length==0) return ERROR;
    	StackTraverse(S,print);
    	return OK;
    }
    
    
    #endif

4.测试

#include "LinkStack.h"
    void main(){
    	pStack S;
    	InitStack(S);
    	for (int i=0;i<10;i++)
    		Push(S,i);
    	printf("栈长度：%d",StackLength(S));
    	ElemType e;
    	GetTop(S,e);
    	printf("\n栈顶：%d",e);
    
    
    
    	printf("\n遍历栈：\n");
    	printStack(S);
    
    
    
    	while(!StackEmpty(S)){
    		ElemType e1;
    		Pop(S,e1);
    		printf("\n弹栈：%d",e1);
    	}
    
    	ClearStack(S);
    	DestroyStack(S);
    
    }

5.测试结果

栈长度：10
    栈顶：9
    遍历栈：
    9
    8
    7
    6
    5
    4
    3
    2
    1
    0
    
    弹栈：9
    弹栈：8
    弹栈：7
    弹栈：6
    弹栈：5
    弹栈：4
    弹栈：3
    弹栈：2
    弹栈：1
    弹栈：0