链表实现栈的动态顺序存储实现—C语言

头文件

ElemType.h

/***
*ElemType.h - ElemType的定义
*
****/

#ifndef ELEMTYPE_H
#define ELEMTYPE_H

typedef int ElemType;

int  compare(ElemType x, ElemType y);
void visit(ElemType e);

#endif /* ELEMTYPE_H */

 DynaSeqStack.h

/***
*DynaSeqStack.h - 动态顺序栈的定义
*
****/

#if !defined(DYNASEQSTACK_H)
#define DYNASEQSTACK_H

#include "ElemType.h"

/*------------------------------------------------------------
// 栈结构的定义
------------------------------------------------------------*/
typedef struct Stack
{
	ElemType *base;				// 栈基址
	ElemType *top;				// 栈顶
	int stacksize;				// 栈存储空间的尺寸
} SqStack;

/*------------------------------------------------------------
// 栈的基本操作
------------------------------------------------------------*/

bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int  StackLength(SqStack S);
bool GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);

#endif /* DYNASEQSTACK_H */

 主函数文件

Lab.cpp

#include <stdio.h>
#include <stdlib.h>
#include "DynaSeqStack.h"

const int STACK_INIT_SIZE = 100; 	// 初始分配的长度
const int STACKINCREMENT  = 10;		// 分配内存的增量


int main()
{
	SqStack S;

    InitStack(&S);
	Push(&S,12);
	system("pause");
	return 0;
}

实现函数文件

ElemType.cpp

/***
*ElemType.cpp - ElemType的实现
*
****/

#include <stdio.h>
#include "ElemType.h"

int compare(ElemType x, ElemType y)
{
	return(x-y);
}

void visit(ElemType e)
{
	printf("%dn", e);
}

DynaSeqStack.cpp

/***
*DynaSeqStack.cpp - 动态顺序栈,即栈的动态顺序存储实现
*
*
*题目:实验3-1 栈的动态顺序存储实现
*
*
*
*
****/

#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaSeqStack.h"

const int STACK_INIT_SIZE = 100;	// 初始分配的长度
const int STACKINCREMENT  = 10;		// 分配内存的增量

/*------------------------------------------------------------
操作目的:	初始化栈
初始条件:	无
操作结果:	构造一个空的栈
函数参数:
		SqStack *S	待初始化的栈
返回值:
		bool		操作是否成功
------------------------------------------------------------*/
bool InitStack(SqStack *S)
{
     S->base = S->top = (ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
	 if (!S->base)
	 {
		 return false;
	 }
	S->stacksize = STACK_INIT_SIZE;
	return true;
}

/*------------------------------------------------------------
操作目的:	销毁栈
初始条件:	栈S已存在
操作结果:	销毁栈S
函数参数:
		SqStack *S	待销毁的栈
返回值:
		无
------------------------------------------------------------*/
void DestroyStack(SqStack *S)
{
	free(S->base);
	S->top = S->base = NULL;
}

/*------------------------------------------------------------
操作目的:	判断栈是否为空
初始条件:	栈S已存在
操作结果:	若S为空栈,则返回true,否则返回false
函数参数:
		SqStack S	待判断的栈
返回值:
		bool		是否为空
------------------------------------------------------------*/
bool StackEmpty(SqStack S)
{
	if (S.base == S.top)
	{
        return true;
	}
	return false;
}

/*------------------------------------------------------------
操作目的:	得到栈的长度
初始条件:	栈S已存在
操作结果:	返回S中数据元素的个数
函数参数:
		SqStack S	栈S
返回值:
		int			数据元素的个数
------------------------------------------------------------*/
int StackLength(SqStack S)
{

	return (S.top - S.base);
;
}

/*------------------------------------------------------------
操作目的:	得到栈顶元素
初始条件:	栈S已存在
操作结果:	用e返回栈顶元素
函数参数:
		SqStack S	栈S
		ElemType *e	栈顶元素的值
返回值:
		bool		操作是否成功
------------------------------------------------------------*/
bool GetTop(SqStack S, ElemType *e)
{
	if (!S.base)
	{
		*e = *(S.top-1);
		return true;
	}
	return false;
}

/*------------------------------------------------------------
操作目的:	遍历栈
初始条件:	栈S已存在
操作结果:	依次对S的每个元素调用函数fp
函数参数:
		SqStack S		栈S
		void (*fp)()	访问每个数据元素的函数指针
返回值:
		无
------------------------------------------------------------*/
void StackTraverse(SqStack S, void (*fp)(ElemType))
{
	for (;S.base<S.top;S.base++)
	{
		fp(*S.base);

	}
}

/*------------------------------------------------------------
操作目的:	压栈——插入元素e为新的栈顶元素
初始条件:	栈S已存在
操作结果:	插入数据元素e作为新的栈顶
函数参数:
		SqStack *S	栈S
		ElemType e	待插入的数据元素
返回值:
		bool		操作是否成功
------------------------------------------------------------*/
bool Push(SqStack *S, ElemType e)
{
	if ((S->top - S->base)==S->stacksize)
	{
		//1.分配大一点的空间
		ElemType *newbase = (ElemType*)malloc(sizeof(ElemType)*(S->stacksize+STACKINCREMENT));
		if (!newbase)
		{
			return false;
		}
		//2.复制元素到新的空间
		memcpy(newbase,S->base,sizeof(ElemType)*S->stacksize);
		//3.销毁原储存空间
		free(S->base);

		//4.栈顶指针、栈顶指针
		S->base = newbase;
		S->top = S->base+S->stacksize;
		S->stacksize = S->stacksize+STACKINCREMENT;

	}
	*(S->top) = e;
	S->top++;
	return true;
}

/*------------------------------------------------------------
操作目的:	弹栈——删除栈顶元素
初始条件:	栈S已存在且非空
操作结果:	删除S的栈顶元素,并用e返回其值
函数参数:
		SqStack *S	栈S
		ElemType *e	被删除的数据元素值
返回值:
		bool		操作是否成功
------------------------------------------------------------*/
bool Pop(SqStack *S, ElemType *e)
{
	*e = *(--S->top);
	return true;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

13620
来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

22390
来自专栏mySoul

线性表

源文件 https://gitlab.com/melovemingming/code/blob/practice/practice/C/2018/10/01/u...

9610
来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

36870
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

28750
来自专栏数据处理

leetcode222求完全二叉树节点个数

39240
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

11240
来自专栏Vamei实验室

纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。 在之前的文章中,我们基于完全二叉树(complete bi...

34490
来自专栏xingoo, 一个梦想做发明家的程序员

程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了,以至于很多开发者习惯性的用到数组,就来一个ArrayList,根本不做过多的思考。其实列表里面还是有很多玩法的,有时候玩不...

21760
来自专栏大闲人柴毛毛

剑指offer代码分析——面试题13在O(1)内删除链表结点

本题详细解析都已在代码中注释了: /** * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p * @author chibozhou *...

38950

扫码关注云+社区

领取腾讯云代金券