数据结构————链栈基本操作（C++实现）

（一）数据结构设计

1.人机交互性
在这里插入图片描述
2.面向对象之属性与方法

//链栈
class LinkedStack
{
public:
	LinkedStack(void);                    //构造函数
	~LinkedStack(void);                   //析构函数

	bool IsEmpty(void);//判断栈空
	int LengthStack(void);//栈长度
	bool Push(const int &);//入栈
	bool Pop(char &);//出栈
	bool Top(int &);//取栈顶元素
	void DispStack(void);//显示栈
	bool Match(char str[], int);//判断表达式的合法性 

private:
	node *top;//定义链栈栈顶 
};

3.具体实现

//初始化栈
LinkedStack::LinkedStack(void) {
	top = NULL;
}

//释放栈
LinkedStack::~LinkedStack(void) {
	node *p = nullptr;
	while (!IsEmpty())
	{
		p = top->next;
		delete top;
		top = p;
	}
}

//判断栈空
bool LinkedStack::IsEmpty(void) {
	return (top == nullptr) ? true : false;
}

//栈长度
int LinkedStack::LengthStack(void) {
	int len = 0;
	node *p = top;
	while (p)
	{
		p = p->next;
		len++;
	}
	return len;
}

//入栈
bool LinkedStack::Push(const elementType &e) {
	node *p = new node;
	p->data = e;
	if (IsEmpty())
	{
		p->next = nullptr;
		top = p;
	}
	else
	{
		p->next = top;
		top = p;
	}
	return true;
}

//出栈
bool LinkedStack::Pop(char &e) {
	if (IsEmpty()) {
		cout << "栈为空！" << endl;
		return false;
	}

	else {
		node *p = top->next;
		e = p->data;
		delete top;
		top = p;

		return true;
	}
}

//取栈顶元素
bool LinkedStack::Top(int &e) {
	if (IsEmpty()) {
		cout << "栈为空！" << endl;
		return false;
	}
	else {
			e = top->data;
			return true;
	}
}

//显示栈
void LinkedStack::DispStack(void) {
	node *p = top;
	while (IsEmpty())
	{
		cout << "栈空！" << endl;
		return ;
	}
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

（二）链栈实验与算法

以带头结点的单链表表示链栈，编写算法实现下列问题的求解。

<1>利用顺序栈实现将10进制数转换为16进制数。

//这里是头文件（Stack.cpp）的函数
void test_1(void)
{
    int i = 0;
	char x;
	LinkedStack S;
	elementType mod, n;
	cout << "请输入十进制数：";
	cin >> n;
	char str[MAXLEN];

	while (n)
	{
		mod = n % 16;  //取余数
		S.Push(mod);//将余数入栈
		n = n / 16;//更新被除后的数
	}

	while (!S.IsEmpty())  //出栈存入字符数组
	{
		S.Pop(x);
		if (x < 10)
		{
			str[i] = x + '0';
		}
		else  //若弹出栈的数位于10~15之间的需要转换
		{
			str[i] = x + 'A' - 10;
		}
		i++;
	}
	str[i] = '\0';

	cout << "十六进制数为：";
	for (i = 0; str[i] != '\0'; i++)
	{
		cout << str[i];
	}
}

【算法思想】进制的转换核心是两个部分：不断取余数以及逆序输出。具体操作如下：
①首先取余数,将余数入栈，再更新被除后的数，即mod = n
% 16; S.Push(mod); n = n / 16;
②逆序输出这部分正好用栈来实现，即S.Pop();

<2>对一个合法的数学表达式来说，其中的各大小括号“{”，“}”，“[”，“]”，“(”和“)”应是相互匹配的。设计算法对以字符串形式读入的表达式S，判断其中的各括号是否是匹配的。

//这里是库文件（LinkedStack.h）的函数

bool LinkedStack::Match(char str[], int n) {
	int i = 0;
	char e;
	LinkedStack st;   //建立符号栈
	while (i < n)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			st.Push(str[i]);
		else
		{
			if (str[i] == ')')
			{
				if (!st.Pop(e))  return false;
				if (e != '(')  return false;
			}
			if (str[i] == ']')
			{
				if (!st.Pop(e))  return false;
				if (e != '[')  return false;
			}
			if (str[i] == '}')
			{
				if (!st.Pop(e))  return false;
				if (e != '{')  return false;
			}
		}
		i++;
	}
	if (st.IsEmpty())    return true;
	else return false;  //遍历字符串后栈不为空说明有不匹配字符
}

【算法思想】考虑到表达式的匹配有左右括号配对次序不正确、右括号多于左括号、左括号多于右括号、左右括号匹配正确四种情况，具体操作如下：
①我们顺序读入算数表达式，让左括号表达式进栈；
②当读到右括号时，比较当前栈顶元素是否匹配，若匹配，退栈继续判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确；
③若当前为右括号而栈已经空，则右括号多于左括号；读入结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号；否则，括号配对正确。

<3>假设栈的输入序列为1、2、3、…、n，设计算法实现对给定的一个序列，判定其是否是此栈合法的输出序列。

//这里是头文件（Stack.cpp）的函数
void test_3(void)
{
	int i, N;
	int s[MAXLEN];
	seqStack S;
	cout << "请输入元素个数：" << endl;
	cin >> N;
	cout << "请输入一个输出序列：" << endl;
	for (i = 0; i < N; i++)
		cin >> s[i];
	if (S.Judge(s, N))
	{
		cout << "该序列合法！" << endl;

	}
	else
	{
		cout << "该序列非法！" << endl;
	}
}

【算法思想】我们知道，要判断栈输出序列的合法性，就要求出栈序列中在i之后所有比i小的元素必须是降序排列的。
①设置元素i从头向后遍历。
②判断需要引入两个循环和一个变量表示最小值
③依次进行比较，验证是否降序。

源代码

LinkedStack.h

#pragma once
#ifndef LinkedStack_h_
#define LinkedStack_h_

#include<iostream>

using namespace std;
typedef int elementType;
//类定义结点node
class node
{
public:
	elementType data;
	node *next;
};

//链栈
class LinkedStack
{
public:
	LinkedStack(void);                    //构造函数
	~LinkedStack(void);                   //析构函数

	bool IsEmpty(void);//判断栈空
	int LengthStack(void);//栈长度
	bool Push(const int &);//入栈
	bool Pop(char &);//出栈
	bool Top(int &);//取栈顶元素
	void DispStack(void);//显示栈
	bool Match(char str[], int);//判断表达式的合法性 

private:
	node *top;//定义链栈栈顶 
};

//初始化栈
LinkedStack::LinkedStack(void) {
	top = NULL;
}

//释放栈
LinkedStack::~LinkedStack(void) {
	node *p = nullptr;
	while (!IsEmpty())
	{
		p = top->next;
		delete top;
		top = p;
	}
}

//判断栈空
bool LinkedStack::IsEmpty(void) {
	return (top == nullptr) ? true : false;
}

//栈长度
int LinkedStack::LengthStack(void) {
	int len = 0;
	node *p = top;
	while (p)
	{
		p = p->next;
		len++;
	}
	return len;
}

//入栈
bool LinkedStack::Push(const elementType &e) {
	node *p = new node;
	p->data = e;
	if (IsEmpty())
	{
		p->next = nullptr;
		top = p;
	}
	else
	{
		p->next = top;
		top = p;
	}
	return true;
}

//出栈
bool LinkedStack::Pop(char &e) {
	if (IsEmpty()) {
		cout << "栈为空！" << endl;
		return false;
	}

	else {
		node *p = top->next;
		e = p->data;
		delete top;
		top = p;

		return true;
	}
}

//取栈顶元素
bool LinkedStack::Top(int &e) {
	if (IsEmpty()) {
		cout << "栈为空！" << endl;
		return false;
	}
	else {
			e = top->data;
			return true;
	}
}

//显示栈
void LinkedStack::DispStack(void) {
	node *p = top;
	while (IsEmpty())
	{
		cout << "栈空！" << endl;
		return ;
	}
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

//判断一个数学表达式是否合法
bool LinkedStack::Match(char str[], int n) {
	int i = 0;
	char e;
	LinkedStack st;   //建立符号栈
	while (i < n)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			st.Push(str[i]);
		else
		{
			if (str[i] == ')')
			{
				if (!st.Pop(e))  return false;
				if (e != '(')  return false;
			}
			if (str[i] == ']')
			{
				if (!st.Pop(e))  return false;
				if (e != '[')  return false;
			}
			if (str[i] == '}')
			{
				if (!st.Pop(e))  return false;
				if (e != '{')  return false;
			}
		}
		i++;
	}
	if (st.IsEmpty())    return true;
	else return false;  //遍历字符串后栈不为空说明有不匹配字符
}


#endif // !LinkedStack_h_

Stack.cpp

#include"LinkedStack.h"
#include<stdlib.h>
#include<cstring>


void test_1(void)
{
	int i = 0;
	char x;
	LinkedStack S;
	elementType mod, n;
	cout << "请输入十进制数：";
	cin >> n;
	char str[MAXLEN];

	while (n)
	{
		mod = n % 16;  //取余数
		S.Push(mod);//将余数入栈
		n = n / 16;//更新被除后的数
	}

	while (!S.IsEmpty())  //出栈存入字符数组
	{
		S.Pop(x);
		if (x < 10)
		{
			str[i] = x + '0';
		}
		else  //若弹出栈的数位于10~15之间的需要转换
		{
			str[i] = x + 'A' - 10;
		}
		i++;
	}
	str[i] = '\0';

	cout << "十六进制数为：";
	for (i = 0; str[i] != '\0'; i++)
	{
		cout << str[i];
	}
}

void test_2(void)
{
	LinkedStack S;
	cout << "请输入表达式：" << endl;
	char str[MAXLEN];
	cin >> str;
	int n = strlen(str);
	if (S.Match(str, n))
		cout << "表达式" << str << "中的括号是匹配的" << endl;
	else
		cout << "表达式" << str << "中的括号是不匹配的" << endl;
}

void test_3(void)
{
	int i, N;
	int s[MAXLEN];
	seqStack S;
	cout << "请输入元素个数：" << endl;
	cin >> N;
	cout << "请输入一个输出序列：" << endl;
	for (i = 0; i < N; i++)
		cin >> s[i];
	if (S.Judge(s, N))
	{
		cout << "该序列合法！" << endl;

	}
	else
	{
		cout << "该序列非法！" << endl;
	}
}



int main(int argc, char **argv)
{
	char str;
	cout << "开始实验测试" << endl;
	cout << "0.退出" << endl;
	cout << "1.10进制数转换为16进制数：" << endl;
	cout << "2.判断表达式是否匹配" << endl;
	cout << "3.判断栈输出序列的合法性" << endl;

	cout << endl << "请输入0-3：";

	cin >> str;
	while (toupper(str) != '0')
	{
		switch (toupper(str))
		{
		case '1':test_1();break;
		case '2':test_2();break;
		case '3':test_3();break;

		default:
			cout << "请输入正确选项！" << endl;
			break;
		}
		cout << endl << "输入选项继续操作：" << endl;
		cin >> str;
	}
	cout << "操作结束！" << endl;

	system("pause");
	return 0;
}

原文链接：https://blog.csdn.net/weixin_51358062/article/details/116566591