文档章节

栈-链式(c/c++实现)

 白客C
发布于 10/21 00:26
字数 1012
阅读 118
收藏 0

上次说“栈是在线性表演变而来的,线性表很自由,想往哪里插数据就往哪里插数据,想删哪数据就删哪数据...。但给线性表一些限制呢,就没那么自由了,把线性表的三边封起来就变成了栈,栈只能“先进后出”,在现实使用还是很多的,像进制数转换,我们写编程时的括号匹配...“但顺序存申请的空间过大与过小都是会影响程序算法效率,链式空间大小是没固定的,前提是底层空间足够情况下,还是三个步骤完成。

栈(链式)实现的三个步骤:

  • 定义所需的功能(LinkStack.h)
  • 实现功能(LinkStack.cpp)
  • 调用功能(Stack.cpp)

 按上面的三个步骤我把代码写成三个文件的形式,同时代码都有详细的注释。

LinkStack.h文件

/*
 *名字:白客C
 *LinkStack.h
 *时间:2019年10月7日
 *环境:Visual Studio 2019
 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1   //不可行
#define OVERFLOW -2    //溢出

typedef int Status;
typedef int ElemType;
typedef struct  SNode 
{
	ElemType   data;         // 数据域 
	struct  SNode  *next;   // 指针域 
}SNode,*LinkStack;     //Snode是结点类型,LinkStack是结点指针类型 


//构造一个空栈
Status InitStack(LinkStack& S);

//摧毁栈
Status DestroyStack(LinkStack& S);

//清空栈
Status ClearStack(LinkStack& S);

//判断是否空栈
Status StackEmpty(LinkStack S);

//判断栈的长度
Status StackLength(LinkStack S);
//取栈顶元素
Status GetTop(LinkStack S, ElemType& e);

//入栈
Status Push(LinkStack& S, ElemType e);

//出栈 
Status Pop(LinkStack& S, ElemType& e);

//访问函数
Status Visit(ElemType e);

//遍历从栈底到栈头
Status StackTraverse(LinkStack S/*, Status Visit(ElemType e)*/);



LinkStack.cpp文件

/*
 *名字:白客C
 *LinkStack.cpp
 *时间:2019年10月7日
 *环境:Visual Studio 2019
 */
#include "LinkStack.h"
#include <iostream>
#include <stdlib.h>

using namespace std;

Status InitStack(LinkStack& S)
{
	S = new SNode;
	if (!S)
	{
		//存储分配失败
		exit(OVERFLOW);
	}
	S->next = NULL;
	return OK;
}

Status DestroyStack(LinkStack& S)
{
	ClearStack(S);
	delete S;
	return OK;
}

Status ClearStack(LinkStack& S)
{
	if (!S)
	{
		return ERROR;
	}
	LinkStack p = NULL;
	while (S->next)
	{
		p = S->next;
		S->next = p->next;
		delete p;
	}
	S->next = NULL;
	return OK;
}

Status StackEmpty(LinkStack S)
{
	return !(S->next);
}

Status StackLength(LinkStack S)
{
	if (!S)
	{
		return OK;
	}
	int i = 0;
	LinkStack p;
	p = S->next;
	while (p)
	{
		p = p->next;
		i++;
	}
	return i;
}

Status GetTop(LinkStack S, ElemType& e)
{
	if (!S)
	{
		return ERROR;
	}
	e = S->data;
	return OK;
}

Status Push(LinkStack& S, ElemType e)
{
	LinkStack p;
	p = new SNode;
	p->data = e;    
	p->next = S; 
	S = p; //p成为新的栈顶 return OK
	return OK;
}

Status Pop(LinkStack& S, ElemType& e)
{
	LinkStack p;
	if (!S)
	{
		exit(UNDERFLOW);
	}
	e = S->data;
	p = S;
	S = S->next; 
	delete p;
	return e;
}

Status StackTraverse(LinkStack S)
{
	if (!S || S->next == NULL) {
		return ERROR;
	}
	
	while (S)
	{
		cout << S->data<<" ";
		S = S->next;
		if (S->next == NULL)
		{
			break;
		}
	}
	return OK;
}

Stack.cpp文件

/*
 *名字:白客C
 *Stack.cpp
 *时间:2019年10月7日
 *环境:Visual Studio 2019
 */

#include <iostream>
#include <stdlib.h>
#include "LinkStack.h"
using namespace std;

int main()
{
	LinkStack S = NULL;
	int i;
	cout << "0.退出" << endl;
	cout << "1.创建一个空栈" << endl;
	cout << "2.摧毁栈" << endl;
	cout << "3.清空栈" << endl;
	cout << "4.判断栈是否为空" << endl;
	cout << "5.查看栈的长度" << endl;
	cout << "6.取栈顶元素" << endl;
	cout << "7.入栈" << endl;
	cout << "8.出栈 " << endl;
	cout << "9.遍历" << endl;
	do
	{
		cout << endl << "请选择一个操作:";
		cin >> i;
		switch (i)
		{
		case 1:
			int Init_i;
			Init_i = InitStack(S);
			if (Init_i)
			{
				cout << "创建一个空栈成功" << endl;
			}
			else
			{
				cout << "创建一个空栈失败" << endl;
			}
			break;

		case 2:
			DestroyStack(S);
			cout << "摧毁栈成功" << endl;
			break;

		case 3:
			if (ClearStack(S))
			{
				cout << "栈以清空" << endl;
			}
			else
			{
				cout << "栈已经是空的,不需要再次清空" << endl;
			}

			break;

		case 4:
			if (StackEmpty(S))
			{
				cout << "是空栈" << endl;
			}
			else
			{
				cout << "不是空栈" << endl;
			}
			break;

		case 5:
			cout << "栈长度为" << StackLength(S) << endl;
			break;

		case 6:
			ElemType Get_e;
			GetTop(S, Get_e);
			cout << "顶元素为:" << Get_e;
			break;

		case 7:
			ElemType Push_e;
			cout << "请输入入栈元素:";
			cin >> Push_e;
			Push(S, Push_e);
			cout << Push_e << "已经入栈" << endl;

			break;

		case 8:
			ElemType Pop_e;
			if (S->next == NULL)
			{
				cout << "栈里为空" << endl;
			}
			else
			{
				cout << Pop(S, Pop_e) << "已经出栈" << endl;
			}
			break;

		case 9:
			cout << "栈元素:";
			StackTraverse(S);
			cout << endl;
			break;

		default:
			break;
		}
	} while (i != 0);
}

 

© 著作权归作者所有

粉丝 0
博文 16
码字总数 15579
作品 0
深圳
程序员
私信 提问
C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/04/01
0
0
C语言/C++编程学习:栈的代码实现之数组方案

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你学知识
2018/06/14
19
0
C语言编程基础学习——队列详细讲解!

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/20
0
0
10个Objective-C基础面试题,iOS面试必备

苹果的iOS系统越来越火了,苹果这个金矿平台也吸引了大量的iOS开发者参与其中,这也促使越来越多的公司向iOS应用开发方向靠拢,因此市场上 对iOS开发的人才需求自然也非常巨大。如果你准备去...

ruby_chen
2013/07/15
56.4K
18
C# vs C++之二:GC vs RAII

C# vs C++之二:GC vs RAII 资源管理 C中资源管理极为繁琐易错,大多复杂C系统都面临内存泄露、悬挂指针等问题 一方面由底层语言特点决定;另一方面也由于C语言特性相对较少,严重依赖程序员...

ddatsh
2011/06/28
1K
6

没有更多内容

加载失败,请刷新页面

加载更多

Kafka实战(五) - 核心API及适用场景全面解析

1 四个核心API ● Producer API 允许一个应用程序发布一串流式的数据到一个或者多个Kafka topic。 ● Consumer API 允许一个应用程序订阅一个或多个topic ,并且对发布给他们的流式数据进行处...

JavaEdge
今天
11
0
实现线程的第三种方式——Callable & Future

Callable Runnable 封装一个异步运行的任务, 可以把它想象成为一个没有参数和返回值的异步方 法。Callable 与 Runnable 类似, 但是有返回值。Callable 接口是一个参数化的类型, 只有一 个...

ytuan996
今天
12
0
OSChina 周六乱弹 —— 不要摁F了!

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 : 朴树写的词曲都给人一种莫名的失落感,不过这首歌他自己却没有唱,换成赵传这种高音阶嘶喊的确很好,低沉但却有力,老男人的呐喊...

小小编辑
今天
22
0
Android Binder机制 - interface_cast和asBinder讲解

研究Android底层代码时,尤其是Binder跨进程通信时,经常会发现interface_cast和asBinder,很容易被这两个函数绕晕,下面来讲解一下: interface_cast 下面根据下述ICameraClient例子进行分析...

天王盖地虎626
昨天
13
0
计算机实现原理专题--存储器的实现(二)

计算机实现原理专题--存储器的实现(一)中描述了一种可以记住输入端变化的装置。现需要对其功能进行扩充,我们将上面的开关定义为置位,下面的开关定义为复位,然后需要增加一个保持位,当保...

FAT_mt
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部