赞
踩
数据结构(C语言实现)——堆栈
在数据结构中,存在着堆栈。
堆栈其实是两种数据结构,一种是堆,一种是栈;
1.堆:堆可以被看成是一棵树,是利用完全二叉树来存储一组数据。
2.栈:一种先进后出的数据结构。
我们通常意义上说的堆栈就是指栈。
栈有先进后出的特点,即是指在读取数据时,先存储的数据后读取。
栈有两种重要的操作,入栈push,出栈pop
栈函数功能如下:
1.初始化
2.销毁
3.入栈、出栈
4.返回栈顶元素
…
决定存储结构:线性结构(数组)
我们根据已知条件(用数组存储数据,当前存入数量多少),假设栈Stack定义如下:
#define MAX_ROOM 100
typedef int STACK;
STACK data[MAX_ROOM];
int dataCount;
假设需要输出栈中用户输入的所有数据,对应的程序段:
int i=0;
for(i = 0; i < MAX_ROOM; i++)
输出data[MAX_ROOM-i-1];
我们知道,MAX_ROOM是数组定义最大的空间,而不是用户输入数据的数量,我们可以得出:
for(i = 0; i < dataCount; i++)
输出data[dataCount - i - 1];
从上述分析可知,dataCount是栈不可或缺的控制因素。
但是上面有些问题,就是若需要同时定义多个栈,那么方式就很凌乱,而且缺乏封装性;同时,也将核心数据暴露在用户的面前,这种做法不宜采用,或者说这不符合编程规范。
所以根据以上分析,可以将各个数据封装起来,形成一个整体,即如下:
typedef struct STACK{
USER_TYPE *data;//USER_TYPE是用户自定义的一种类型
int maxRoom;//为栈申请的最大空间
int top;//指向栈顶元素
}STACK;
结构如下图所示,
**下面是数据结构栈的实现(stack.h):** #ifndef _STACK_H_ #define _STACK_H_ #include<stdio.h> #include<malloc.h> #define TRUE 1 #define FALSE 0 typedef unsigned char Boolean; typedef struct STACK{ USER_TYPE *data; int maxRoom; int top; }STACK; Boolean initStack(STACK **stack,int maxRoom);//初始化栈 Boolean push(STACK *stack,USER_TYPE value);//入栈 Boolean isStackFull(STACK stack);//判断栈溢出 Boolean isStackEmpty(STACK stack);//判断栈为空 Boolean pop(STACK *stack,USER_TYPE *value);//出栈,返回出栈的元素 void destoryStack(STACK **stack);//销毁栈 Boolean readTop(STACK stack,USER_TYPE *value);//返回栈顶指针 /*5.返回栈顶元素,出栈情况相类似,所以用value指针来返回栈顶的数据 Boolean readTop(STACK stack,USER_TYPE *value){ if(isStackEmpty(stack)){ return FALSE; } *value = stack.data[stack.top - 1]; return TRUE; } /*4.销毁栈,先释放data,在释放栈指针*/ void destoryStack(STACK **stack){ if(*stack) { if((*stack)->data){ free((*stack)->data); free(*stack); } } } /* 3.出栈操作: 出栈操作就是将栈顶的数据移除,其实只要将栈顶指针top向下移一位并将出栈的数据 返回(因为函数的运行完毕,函数内部非动态申请的空间都会被释放掉,所以用value指针 来返回出栈的数据),不管原来的数据在不在,对于栈来说是不属于有效数据的,是垃圾 数据,另外栈为空的时候不能进行出栈操作。*/ Boolean pop(STACK *stack,USER_TYPE *value){ if(isStackEmpty(*stack)) return FALSE; *value = stack->data[--stack->top]; return TRUE; } Boolean isStackEmpty(STACK stack){ return stack.top == 0; } Boolean isStackFull(STACK stack){ return stack.maxRoom == stack.top; } /*2.入栈操作: 进行入栈操作,即存储用户需要存储的数据(value),需要分情况操作。 如果栈已经满了,直接不进行入栈操作; 如果栈还有剩余空间,将一个数据加入栈顶,同时指向栈顶的top+1*/ Boolean push(STACK *stack,USER_TYPE value){ int i = 0; //如果堆栈已经满了,入栈失败 if(isStackFull(*stack) == TRUE) return FALSE; stack->data[stack->top++] = value; return TRUE; } /*1.初始化栈,这个函数的功能是给空栈申请空间 首先,需要给控制头申请一个动态空间,然后再给控制头里面的东西申请空间和初始化 给data申请空间大小为maxRoom的动态数组,控制头的maxRoom初始化为用户需要申请的空间大小maxRoom, top初始化化为0*/ Boolean initStack(STACK **stack,int maxRoom){ if(*stack){ return FALSE; } if((*stack =(STACK *)malloc(sizeof(STACK))) == NULL) return FALSE; (*stack)->maxRoom = maxRoom; (*stack)->top = 0; if(((*stack)->data = (USER_TYPE*)malloc(sizeof(USER_TYPE)*maxRoom)) == NULL){ free(*stack); return FALSE; } return TRUE; } #endif
下面是对栈的测试程序(stack.c)
#include<stdio.h> #include<malloc.h> #include"stack.h" typede int USER_TYPE; void main(void){ STACK *stack = NULL; USER_TYPE *value = NULL; int i = 0; int j = 0; value = (USER_TYPE *)calloc(sizeof(USER_TYPE), 1); initStack(&stack,10); for(i = 0; i < 5; i++){ printf("入栈:%d ", i); push(stack, i+1); readTop(*stack, value); printf("入栈元素:%d ", *value); printf("\n"); } printf("\n.......................................\n"); j = stack->top; //全部出栈 for(i = 0; i < j; i++){ printf("出栈:%d ", i); pop(stack, value); printf("出栈元素:%d\n", *value); } //查看栈顶元素 printf("读取栈顶元素:"); if(readTop(*stack, value)) printf("%d ", *value); else printf("栈内无元素\n"); free(value); destoryStack(&stack); }
运行结果如下:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。