看数据结构写代码(8)顺序栈的实现

欢迎指出 代码 不足之处

在写顺序栈的时候 犯了两个错误,:一个是 对栈的 认识不够清楚,栈顶指针的下一个位置为栈顶元素; 另一个是粗心,在用 realloc 分配内存的时候,忽略了元素本身的大小,只写了 元素的个数。 希望引以为戒。

上代码:

// SqStack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdlib.h>
#include <cstdio>

//故意将值设置的比较小,以测试 重新分配 存储空间
#define STACK_INIT_SIZE 10
#define STACK_ADD_SIZE	2

typedef int ElementType;

enum E_State
{
	E_State_Error = 0,
	E_State_Ok,
};
//顺序栈
struct sqStack
{
	ElementType * base;
	ElementType * top;
	int stackSize;
};

E_State stackInit(sqStack * stack){
	ElementType * base = (ElementType *)malloc(sizeof(sqStack) * STACK_INIT_SIZE);
	if (base == NULL)
	{
		return E_State_Error;
	}
	stack->base = stack->top = base;
	stack->stackSize = STACK_INIT_SIZE;
	return E_State_Ok;
}

void stackDestory(sqStack * stack){
	free(stack->base);
	stack->base = stack->top = NULL;
	stack->stackSize = 0;
}

void stackClear(sqStack * stack){
	stack->top = stack->base;
}

int stackLen(sqStack stack){
	return stack.top - stack.base;
}

bool stackEmpty(sqStack stack){
	return stack.top == stack.base ? true : false;
}

E_State stackGetTop(sqStack stack,ElementType * e){
	if (stackEmpty(stack))
	{
		return E_State_Error;
	}
	/*e = *stack.top 错误,注意
	没搞清楚 栈顶 指向问题
	// 栈顶指针的下一个位置为栈顶元素
	*/
	*e = *(stack.top-1);
	return E_State_Ok;
}
//
E_State stackPush(sqStack * stack,ElementType e){
	//首先检查空间是否不足.
	int len = stackLen(*stack);
	if (len >= stack->stackSize)
	{
		//粗心啊
		//ElementType * base = (ElementType *)realloc(stack->base,stack->stackSize + STACK_ADD_SIZE);
		ElementType * base = (ElementType *)realloc(stack->base,(stack->stackSize + STACK_ADD_SIZE)*sizeof(ElementType));
		if (base == NULL)
		{
			return E_State_Error;
		}
		stack->base = base;
		stack->top = stack->base + stack->stackSize;
		stack->stackSize += STACK_ADD_SIZE;
	}
	*(stack->top) = e;
	stack->top++;
	return E_State_Ok;
}

E_State stackPop(sqStack * stack,ElementType * e){
	if (stack->top > stack->base)
	{
		stack->top--;
		*e = *stack->top;
		return E_State_Ok;
	}
	else
	{
		return E_State_Error;
	}
}

void stackTraverse(sqStack stack){
	printf("----------------遍历开始----------------------\n");
	if (stack.top > stack.base)
	{
		ElementType * top = --stack.top;
		while (top != stack.base)
		{
			printf("-------%d-----------\n",*top--);
		}
		//最后还要遍历栈底
		printf("-------%d-----------\n",*top);
	}
	printf("----------------遍历结束----------------------\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	sqStack stack;
	stackInit(&stack);
	//插入 1 ~ 15
	for (int i = 1; i < 16; i++)
	{
		stackPush(&stack,i);
	}
	ElementType top;
	//删除15
	stackPop(&stack,&top);
	//删除14
	stackPop(&stack,&top);
	stackTraverse(stack);
	stackGetTop(stack,&top);
	printf("栈长为:%d,栈顶元素为 :%d,栈是否为空 %d",stackLen(stack),top,stackEmpty(stack));
	stackDestory(&stack);
	return 0;
}

时间: 02-28

看数据结构写代码(8)顺序栈的实现的相关文章

看数据结构写代码(9)链栈的实现

在写链栈的时候 和 顺序栈一样 犯了两个错误: 一个是 在 入栈 和 进栈顶时候 忘记 操作 linkstack.len 了,另一个是 在写 stackClear 的时候 犯了一个 低级的内存错误. 这两个问题 都是 粗心造成的. 希望 引以为戒 在做下一个例子:数值转换时,又发现了一个问题:在 stackPop 没有返回 pop元素的值.唉  欢迎指出代码不足 下面上代码: // LinkStack.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h"

看数据结构写代码(32) 赫夫曼树编码以及译码

杂谈:最近有点慵懒,不好不好.好几天都没写代码,原本准备上星期完结 树 这一章节的.现在 又耽误了.哎.要抓紧时间啊. 下面直接上代码: 可以到我的网盘下载源代码,或者 直接拷贝下面的源代码 运行 网盘地址:点击打开链接 // HuffmanTree.cpp : 定义控制台应用程序的入口点. //哈弗曼编码,译码 #include "stdafx.h" #include <stdlib.h> #include <cstring> enum E_State { E

看数据结构写代码(16)顺序队列的实现(循环队列)

循环队列的基本结构如下: front 属性 表示 队头,rear 属性表示 队尾. 在队空时 :q.rear 和 q.front 都为0 ,其余时刻q.rear 指向 队尾的后继节点,q.front指向 队头. 当在队尾插入元素时,q.rear + 1 ,在删除 队头元素时 ,q.front + 1,这样的操作 会造成 "假溢出"问题. 图(d) 就是一种 假溢出 问题,q.rear 指向 空间的边界,再插入 会造成 溢出,但是 实际上 空间 并未满. 为了解决假溢出,将 队列 看成

看数据结构写代码(13)栈的应用(四) 迷宫求解

这是一个 用 穷举法 解 迷宫问题 的一个示例,但在 效率 和 解的 最短路径上 就稍显不足了. 这 两个问题,留在 以后 空闲 时刻 解答. 欢迎指出代码不足 下面上代码: // Maze.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <stdlib.h> struct Postion { int x; int y; }; typedef int Direction; struct ElementType { P

看数据结构写代码(10)栈的应用(一) 数值转换

首先 修正上一节 stackPop 代码的错误 E_State stackPop(linkStack * stack,elelmentType * data){ if (stack->top != stack->bottom) { //首先指向第一个元素. lStackNode * next = stack->bottom; <strong><span style="font-size:18px;color:#ff6666;">*data =

看数据结构写代码(15)链式队列的实现

队列 和 栈 是 一种 受限制的 线性表.所以 他们的 实现方式 都 相差 无几.之前有过  链栈 和 链式线性表 的 实现经验,自然 写 链队 ,也毫无问题. 下面详细讲解每一段代码 的技术要点 下面是队列节点的数据结构 struct QueueNode { ElementType data; QueueNode * next; }; //生成一个节点 QueueNode * queueNodeMake(ElementType data){ QueueNode * pNode = (Queue

看数据结构写代码(44) 判断无向图是否有环路

在 看 严蔚敏的 数据结构 一书 7.5小节时,书上 说" 判断有向图是否存在环要不无向图复杂.对于无向图来说,深度优先遍历过程中遇到回边(即指向已访问过的顶点的边),则必定存在环路". 看的不明白,所以 网上 百度了一下. 有了思路:故写下算法 和思路,以便以后 温故. 思路: 1.一个n个顶点,e条边的 无向图,若 e>= n,必有环路. 2.若 e < n ,需要 深度 遍历,并把 父节点传入 参数中,如果 遇到 一个 节点 被访问过 并且 不是 父节点,那么 就有环

看数据结构写代码(43) 关节点

首先 说明一下 概念问题: 关节点 :如果删除无向 图中的一个顶点,以及与顶点相关的边,把 图的 一个连通 分量 变成 两个 以上的 连通 分量.这样的顶点叫做关节点. 没有 关节点的 无向图,叫做 重连通图.重连通图中 任意 两个顶点 至少 存在 两条以上的 通路. 如果 删除 连通图上的 k个 节点,才能 破坏 他的连通性,那么 这个连通图的 连通度 为k. 下面的算法 是 求 连通图的 关节点,并没有 考虑 求图的 关节点,不过 要 改成 图的 关节点 也不难,只要 加 一个 for i

看数据结构写代码(57) AVL树的删除

上一节 已经说了 AVL树的插入 操作,可是 只有 插入,没有删除,怎么能叫 动态 查找表呢. 呵呵,博主 赶紧 去 研究了一番.下面 是成果: AVL树的删除 大致 分为 两大块: 1. 查找节点 并 删除 2. 保持 删除 后 平衡因子的 影响 1. 首先 找到 这个 节点,如果 节点 不存在,直接 退出 函数 if (*tree == NULL){//没找到 return false; } 2.如果 存在,分为 四种情况:(根 二叉 排序树的 删除 类似) 1.节点 为 叶子 节点,直接