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

发布于 | 分类于 数据结构| 0
文章目录 隐藏
1 视频讲解
2 CH3：栈
2.1 c1.h代码
2.2 c3-1.h代码
2.3 bo3-1.cpp代码
2.4 main3-1.cpp代码
2.5 代码包

视频讲解

录视频完了后才发现话筒坏了，已经使用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代码

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <process.h>
#include <stdio.h>
#include <malloc.h>
#include <process.h>

 

c3-1.h代码

  1. //栈的顺序表示及实现
  3. struct SqStack
  4. {
  5. SElemType* base; //栈底指针
  6. SElemType* top; //栈顶指针
  7. int stacksize; //栈容量大小
  8. };
//栈的顺序表示及实现

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

 

bo3-1.cpp代码

  1. //栈的顺序表示及实现
  3. void InitStack(struct SqStack &S)
  4. {
  5. S.base = (SElemType *)malloc(2*sizeof(SElemType));
  6. if (S.base == NULL)
  7. {
  8. printf("动态内存分配失败！\n");
  9. exit(-1);
  10. }
  11. S.top = S.base;
  12. S.stacksize = 2; // 初始分配的存储空间量，表示可以存储多少个元素。
  13. }
  15. void Push(struct SqStack &S, SElemType e)
  16. {
  17. // e代表被插入的值
  18. // 先判断栈是否还能存放下，如果满了就追加空间
  19. if (S.top - S.base >= S.stacksize)
  20. {
  21. /*
  22. void *realloc(void *ptr, size_t size)
  23. ptr -- 指针指向一个要重新分配内存的内存块，该内存块之前是通过调用 malloc、calloc 或 realloc 进行分配内存的。如果为空指针，则会分配一个新的内存块，且函数返回一个指向它的指针。
  24. size -- 内存块的新的大小，以字节为单位。如果大小为 0，且 ptr 指向一个已存在的内存块，则 ptr 所指向的内存块会被释放，并返回一个空指针。
  25. */
  26. // 10 是增量
  27. S.base = (SElemType *)realloc(S.base, (S.stacksize + 10)*sizeof(SElemType));
  28. if (S.base == NULL)
  29. {
  30. printf("Push函数中的动态内存分配失败！\n");
  31. exit(-1);
  32. }
  33. // 将原来老的栈顶指针移至新的栈顶
  34. S.top = S.base + S.stacksize;
  35. // 更改S.stacksize的计数
  36. S.stacksize = S.stacksize + 10;
  38. // e存进栈顶指针指向的结点
  39. //*(S.top) = e;
  40. // 栈顶往上移动一个结点
  41. //S.top++;
  42. }
  44. //先将top指针+1，再赋值给top原来指向的位置空间
  45. //*(S.top)++=e;
  46. *S.top = e;
  47. S.top = S.top + 1;
  50. }
  52. void StackTraverse(struct SqStack &S)
  53. {
  54. SElemType* p = S.base;
  55. while (p != S.top)
  56. {
  57. printf("%5d", *p);
  58. p = p + 1;
  59. }
  60. printf("\n");
  61. }
  63. void Pop(struct SqStack &S, SElemType &e)
  64. {
  65. //先判断栈空，如果栈为空则返回错误
  66. if (S.top == S.base)
  67. {
  68. printf("栈为空，不能删除元素\n");
  69. exit(-1);
  70. }
  71. // 栈顶指针往下移动一个结点即可
  72. S.top = S.top - 1;
  73. e = *S.top;
  74. }
  76. bool StackEmpty(struct SqStack &S)
  77. {
  78. if (S.top == S.base)
  79. {
  80. return 1; //栈为空
  81. }
  82. else
  83. {
  84. return 0; //不空
  85. }
  86. }
  88. void GetTop(struct SqStack &S, SElemType &e)
  89. {
  90. if (S.top == S.base)
  91. {
  92. printf("栈是空的\n");
  93. exit(-1);
  94. }
  96. //S.top = S.top - 1;
  97. e = *(S.top-1);
  98. }
  101. int StackLength(struct SqStack &S)
  102. {
  103. return S.top - S.base;
  104. }
  106. void ClearStack(struct SqStack &S)
  107. {
  108. S.top = S.base;
  109. }
  111. void DestroyStack(struct SqStack &S)
  112. {
  113. free(S.base);
  114. S.base = NULL;
  115. S.top = NULL;
  116. S.stacksize=0;
  117. }
//栈的顺序表示及实现

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代码

  1. //栈的顺序表示及实现
  2. #include "c1.h"
  3. typedef int SElemType; // 栈结点中存放的数据类型
  4. #include "c3-1.h"
  5. #include "bo3-1.cpp"
  7. /*
  8. 已经实现的功能
  9. 1.初始化栈
  10. 2.压一个元素入栈
  11. 3.栈内元素遍历
  12. 4.弹出栈顶元素
  13. 5.判断栈是否空
  14. 6.获取栈顶元素
  15. 7.栈长度
  16. 8.清空栈
  17. 9.销毁栈
  18. */
  20. void main()
  21. {
  22. struct SqStack S;
  23. //Init
  24. InitStack(S);
  27. //Push
  28. int j = 1;
  29. Push(S, j); //对哪个栈操作,插入什么值
  32. //批量Push
  33. int k;
  34. for (k = 2; k <= 12; k++)
  35. {
  36. Push(S, k);
  37. }
  39. //遍历
  40. printf("栈内元素有：");
  41. StackTraverse(S);
  43. //Pop(删除，弹出)
  44. int e; //弹出栈顶元素
  45. Pop(S, e);
  46. printf("被弹出的栈顶元素是：%d\n", e);
  49. printf("弹出栈顶元素后，栈内元素有：");
  50. StackTraverse(S);
  53. //判空
  54. printf("栈为空吗：");
  55. if (StackEmpty(S))
  56. {
  57. printf("栈空\n");
  58. }
  59. else
  60. {
  61. printf("栈不为空\n");
  62. }
  65. //获取栈顶元素
  66. GetTop(S, e);
  67. printf("栈顶元素是：%d\n", e);
  72. //栈长度
  73. printf("栈长度为：%d\n", StackLength(S)); //通过返回值取得长度
  76. // 清空栈
  77. ClearStack(S);
  79. // 销毁栈
  80. DestroyStack(S);
  82. }
//栈的顺序表示及实现
#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);

}

 

代码包

顺序栈

 

参考文献：

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

作者： 高志远

高志远，24岁，男生

发表评论

邮箱地址不会被公开。