数据结构算法实现:顺序栈——栈的顺序表示和实现

视频讲解

录视频完了后才发现话筒坏了,已经使用PR处理过尽量让音频变得可识别,如果公放听不清建议戴上耳机。给大家的不便还请谅解。——下次录视频前一定先试录一次(ಥ_ಥ)

 

CH3:栈

因为栈只在栈顶有插入和删除操作,所以没必要使用链式栈,使用顺序栈更合适。

其实c语言中的数组,经过限制后(先进后出,中间结点不允许操作)就可以成为栈。

栈只是一种思想。

  • c3-1.h:顺序栈的存储结构

  • bo3-1.cpp:顺序栈的基本操作(9个)

    已经实现的功能:

    1. 初始化栈

    2. 压一个元素入栈

    3. 栈内元素遍历

    4. 弹出栈顶元素

    5. 判断栈是否空

    6. 获取栈顶元素
    7. 栈长度

    8. 清空栈

    9. 销毁栈

  • main3-1.cpp:bo3-1.cpp 的主程序

 

c1.h代码

#include <stdio.h>
#include <malloc.h>
#include <process.h>

 

c3-1.h代码

//栈的顺序表示及实现

struct SqStack
{
	SElemType* base;	//栈底指针
	SElemType* top;		//栈顶指针
	int stacksize;		//栈容量大小
};

 

bo3-1.cpp代码

//栈的顺序表示及实现

void InitStack(struct SqStack &S)
{
	S.base = (SElemType *)malloc(2*sizeof(SElemType));
	if (S.base == NULL)
	{
		printf("动态内存分配失败!\n");
		exit(-1);
	}
	S.top = S.base;
	S.stacksize = 2;		// 初始分配的存储空间量,表示可以存储多少个元素。
}

void Push(struct SqStack &S, SElemType e)
{
	// e代表被插入的值
	// 先判断栈是否还能存放下,如果满了就追加空间
	if (S.top - S.base >= S.stacksize)
	{
		/* 
		void *realloc(void *ptr, size_t size)
		ptr -- 指针指向一个要重新分配内存的内存块,该内存块之前是通过调用 malloc、calloc 或 realloc 进行分配内存的。如果为空指针,则会分配一个新的内存块,且函数返回一个指向它的指针。
		size -- 内存块的新的大小,以字节为单位。如果大小为 0,且 ptr 指向一个已存在的内存块,则 ptr 所指向的内存块会被释放,并返回一个空指针。
		*/
		// 10 是增量
		S.base = (SElemType *)realloc(S.base, (S.stacksize + 10)*sizeof(SElemType));
		if (S.base == NULL)
		{
			printf("Push函数中的动态内存分配失败!\n");
			exit(-1);
		}
		// 将原来老的栈顶指针移至新的栈顶
		S.top = S.base + S.stacksize;
		// 更改S.stacksize的计数
		S.stacksize = S.stacksize + 10;

		// e存进栈顶指针指向的结点
		//*(S.top) = e;
		// 栈顶往上移动一个结点
		//S.top++;
	}

	//先将top指针+1,再赋值给top原来指向的位置空间
	//*(S.top)++=e;
	*S.top = e;
	S.top = S.top + 1;

	
}

void StackTraverse(struct SqStack &S)
{
	SElemType* p = S.base;
	while (p != S.top)
	{
		printf("%5d", *p);
		p = p + 1;
	}
	printf("\n");
}

void Pop(struct SqStack &S, SElemType &e)
{
	//先判断栈空,如果栈为空则返回错误
	if (S.top == S.base)
	{
		printf("栈为空,不能删除元素\n");
		exit(-1);
	}
	// 栈顶指针往下移动一个结点即可
	S.top = S.top - 1;
	e = *S.top;
}

bool StackEmpty(struct SqStack &S)
{
	if (S.top == S.base)
	{
		return 1;	//栈为空
	}
	else
	{
		return 0;	//不空
	}
}

void GetTop(struct SqStack &S, SElemType &e)
{
	if (S.top == S.base)
	{
		printf("栈是空的\n");
		exit(-1);
	}

	//S.top = S.top - 1;
	e = *(S.top-1);
}


int StackLength(struct SqStack &S)
{
	return S.top - S.base;
}

void ClearStack(struct SqStack &S)
{
	S.top = S.base;
}

void DestroyStack(struct SqStack &S)
{
	free(S.base);
	S.base = NULL;
	S.top = NULL;
	S.stacksize=0;
}

 

main3-1.cpp代码

//栈的顺序表示及实现
#include "c1.h"
typedef int SElemType;		// 栈结点中存放的数据类型
#include "c3-1.h"
#include "bo3-1.cpp"

/*
	已经实现的功能
	1.初始化栈
	2.压一个元素入栈
	3.栈内元素遍历
	4.弹出栈顶元素
	5.判断栈是否空
	6.获取栈顶元素
	7.栈长度
	8.清空栈
	9.销毁栈
*/

void main()
{
	struct SqStack	S;
	//Init
	InitStack(S);


	//Push
	int j = 1;
	Push(S, j);		//对哪个栈操作,插入什么值

					
	//批量Push
	int k;
	for (k = 2; k <= 12; k++)
	{
		Push(S, k);
	}

	//遍历
	printf("栈内元素有:");
	StackTraverse(S);

	//Pop(删除,弹出)
	int e;		//弹出栈顶元素
	Pop(S, e);
	printf("被弹出的栈顶元素是:%d\n", e);


	printf("弹出栈顶元素后,栈内元素有:");
	StackTraverse(S);
	

	//判空
	printf("栈为空吗:");
	if (StackEmpty(S))
	{
		printf("栈空\n");
	}
	else
	{
		printf("栈不为空\n");
	}


	//获取栈顶元素
	GetTop(S, e);
	printf("栈顶元素是:%d\n", e);




	//栈长度
	printf("栈长度为:%d\n", StackLength(S));		//通过返回值取得长度


	// 清空栈
	ClearStack(S);

	// 销毁栈
	DestroyStack(S);

}

 

代码包

顺序栈

 

参考文献:

《数据结构算法实现及解析》 高一凡

作者: 高志远

高志远,23岁,男生,毕业于上海杉达学院电子商务系。

发表评论

邮箱地址不会被公开。