C语言 迷宫问题(堆栈及其应用)
C语言 迷宫问题(堆栈及其应用)
首先我们来看看堆栈这个数据结构，像朱老师曾经说的那样堆栈是一个单腔生物，想想一个场景，有一个笔直的路，最远端是死胡同。我们现在让车一个一个的进去，那要出来的的时候必须是后进去的先出来（push和pop操作）。对于堆栈这样的数据结构有这些操作：
1.堆栈的初始化和销毁；
2.堆栈清空；
3.判断堆栈是否为空；
4.返回栈顶元素；
5.得到堆栈内元素的个数；
6.压栈与出栈；
堆栈的应用方面非常广泛，例如：数值转换，括号匹配，行编辑程序，迷宫问题和表达式等。
无论是那种应用，都要记住堆栈的最大的功能是：记忆！！！
下面是堆栈的代码，我这个里面没有判断堆栈是否为满，如果堆栈元素等于申请个数时，堆栈会追加10个元素，这个可以修改。让对内存的申请达到合适的数量。如果要用堆栈时，把头文件预处理就行了。
将C语言梳理一下，分布在以下10个章节中：
- Linux-C成长之路（一）：Linux下C编程概要
- Linux-C成长之路（二）：基本数据类型
- Linux-C成长之路（三）：基本IO函数操作
- Linux-C成长之路（四）：运算符
- Linux-C成长之路（五）：控制流
- Linux-C成长之路（六）：函数要义
- Linux-C成长之路（七）：数组与指针
- Linux-C成长之路（八）：存储类，动态内存
- Linux-C成长之路（九）：复合数据类型
- Linux-C成长之路（十）：其他高级议题
C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码
一. STACK.H
#ifndef _STACK_H_
#define _STACK_H_
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define STACKINCREMENT 10
typedef struct STACK
{
USER_TYPE *top;
//栈顶指针
USER_TYPE *base;
//栈底指针
int maxRoom;
}STACK;
typedef unsigned char Boolean;
STACK *initStack(int maxRoom);
//初始化堆栈
void destroyStack(STACK **sta);
//销毁堆栈
Boolean isStackEmpty(STACK sta);
//判断堆栈是否为空
void clearStack(STACK *sta);
//清空堆栈信息
int stackLength(STACK sta);
//返回堆栈内元素个数
Boolean getStackTop(STACK sta, USER_TYPE *element);
//得到栈顶元素
Boolean push(STACK *sta, USER_TYPE element);
//入栈
Boolean pop(STACK *sta, USER_TYPE *element);
//出栈
Boolean pop(STACK *sta, USER_TYPE *element)
{
Boolean OK = TRUE;
if(isStackEmpty(*sta) == FALSE)
{
*element = *(sta->top - 1);
sta->top--;
}
else
{
OK = FALSE;
}
return OK;
}
Boolean push(STACK *sta, USER_TYPE element)
{
Boolean OK = TRUE;
if( (sta->top - sta->base) >= sta->maxRoom)
{
sta->base = (USER_TYPE *)realloc(sta->base,
(sta->maxRoom + STACKINCREMENT) * sizeof(USER_TYPE));
if(sta->base == NULL)
{
exit(1);
//存储分配失败
}
sta->top = sta->base + sta->maxRoom;
sta->maxRoom += STACKINCREMENT;
}
*sta->top = element;
sta->top++;
return OK;
}
Boolean getStackTop(STACK sta, USER_TYPE *element)
{
Boolean OK = TRUE;
if(isStackEmpty(sta) == FALSE)
{
*element = *(sta.top - 1);
}
else
{
OK = FALSE;
}
return OK;
}
int stackLength(STACK sta)
{
return sta.top - sta.base;
}
void clearStack(STACK *sta)
{
sta->top = sta->base;
}
Boolean isStackEmpty(STACK sta)
{
return sta.top == sta.base;
}
void destroyStack(STACK **sta)
{
if((*sta)->base)
free((*sta)->base);
(*sta)->top = NULL;
free(*sta);
}
STACK *initStack(int maxRoom)
{
STACK *stack;
stack = (STACK *)malloc(sizeof(STACK));
if(stack == NULL)
{
exit(1);
}
else
{
stack->maxRoom = maxRoom;
stack->base = (USER_TYPE *)malloc(sizeof(USER_TYPE) * maxRoom);
if(stack->base == NULL)
{
exit(0);
}
stack->top = stack->base;
}
return stack;
}
#endif
更多详情见请继续阅读下一页的精彩内容：
|
评论暂时关闭