新手向C语言实现特殊的数据结构——栈

目录

    • 一、易错接口详解
      • 1.1 栈的初始化
      • 1.2 栈的销毁
      • 1.3 入栈
      • 1.4 出栈
    • 二、简单接口的实现
      • 2.1 有效数据个数
      • 2.2 返回栈顶数据
    • 三、头文件的引用,结构体和函数的定义

一、易错接口详解

1.1 栈的初始化

涉及到结构体的定义,请先跳转至第三部分查看结构体的详情。

算法实现:assert断言参数是否为NULL,即结构体指针不能为NULL

由于实现的是动态的栈,即会随着数据的增加不断增大栈的空间,所以需要给指向栈的指针初始化为NULL

最后把栈顶位置top和空间容量capacity初始化为0。

void StackInit(ST* ps)
{
     
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

1.2 栈的销毁

调用这个接口通常是在程序结束前将内存释放,还给操作系统,避免内存泄漏。

算法:assert断言结构体指针是否为空。

若指向栈的指针不为NULL则释放该指针。

最后把容量和栈顶位置均重置为0。

void StackDestroy(ST* ps)
{
     
	assert(ps);
	if (ps->a)
	{
     
		free(ps->a);
        ps->a = NULL;
	}
	ps->capacity = 0;
	ps->top = 0;
}

1.3 入栈

入栈都需要对容量进行检测,所以封装为一个函数,以便随时调用。

易错点在于realloc开辟空间可能存在失败,如果直接把新空间的地址返回,而不是用一个中间变量暂时存储,一旦开辟失败,就会造成原本已有的地址都无法查找。

static void CheckCapacity(ST* ps)
{
     
	if (ps->capacity == ps->top)
	{
     
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * newcapacity);
		if (tmp == NULL) 
		{
     
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

入栈算法:断言是否为空,检查容量,放入数据,栈顶位置自增。

void StackPush(ST* ps, STDatatype x)
{
     
	assert(ps);
	CheckCapacity(ps);
	ps->a[ps->top] = x;
	ps->top++;
}

1.4 出栈

算法:断言结构体指针是否为空,断言栈是否为空,让栈顶位置自减。

判断栈是否为空的功能可以封装为一个函数,以便后续多次调用。

bool StackEmpty(ST* ps)
{
     
	assert(ps);
	return ps->top == 0;
}
void StackPop(ST* ps)
{
     
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

二、简单接口的实现

2.1 有效数据个数

int StackSize(ST* ps)
{
     
	assert(ps);
	return ps->top;
}

2.2 返回栈顶数据

STDatatype StackTop(ST* ps)
{
     
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

三、头文件的引用,结构体和函数的定义

#include
#include
#include
#include
typedef int STDatatype;
typedef struct Stack
{
     
	STDatatype* a;
	int top;	
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDatatype StackTop(ST* ps);

你可能感兴趣的