C++11 数据结构6 栈的链式存储，实现，测试

作者：笔触狂放9 | 2024-04-26 05:02:33

踩

栈顶放在链表的头部

栈顶放在链表的头部还是尾部呢？

需要栈是特殊的线性表，那么我们回忆一下线性表的链式存储的插入和删除的写法，就应该能理清线性表的头部做为栈顶合适还是线性表的尾部作为栈顶合适

插入算法核心代码


	//正式插入数据，
	int i = 0;
	LinkListNode *curSeqListNode = &(tempseqlist->head);//让curSeqListNode 指向 链表的头部
	for (int i = 0; i < pos; ++i) {
		curSeqListNode = curSeqListNode->next;
	}
	node->next = curSeqListNode->next;
	curSeqListNode->next = node;
	tempseqlist->length++;
	return ret;

删除算法核心代码


	//辅助指针变量curSeqListNode，指向的位置是链表的头部
	LinkListNode *curSeqListNode = &(tempseqlist->head);//让curSeqListNode 指向 链表的头部
	
    int i = 0;
	for (i = 0; i < pos; ++i) {
		curSeqListNode = curSeqListNode->next;
	}
	retSeqListNode = curSeqListNode->next;	//先将要删除的节点缓存出来
	curSeqListNode->next = retSeqListNode->next;// 删除的节点的next中保存着 “要删除元素的下一个元素”，让curseqlistnode->next 指向
	tempseqlist->length--;
	return retSeqListNode;

从这两个算法都能看出，如果要在pos 位置插入元素或者删除元素，那么先要遍历到pos 位置，因此我们在 线性表的头部 做为栈顶比较合理。因此不管是插入元素，或者是删除元素，都是对线性表的头部的第一个元素进行处理。

相关代码：


#ifndef __006LINKSTACK_H__
#define __006LINKSTACK_H__
 
typedef void LinkStack; //链表的返回值，需要使用void *
 
typedef struct LinkStackNode {  //链表节点
	struct LinkStackNode *next;
}LinkStackNode;
 
// 初始化，建立一个空的链表 
//返回值不为NULL，表示创建成功。
//返回值为NULL，表示创建失败。
LinkStack* LinkStack_Create();
 
//销毁该线性表
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Destory(LinkStack *list);
 
//清空seqlist
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Clear(LinkStack *list);
 
// 返回线性表List存在的元素个数
//返回值 >=0 表示：该list存在的元素个数
//<0 表示error
int LinkStack_Length(LinkStack *list);
 
 
 
//从LinkStack 中获取栈顶位置的数据，实际上是 栈的第一个链表的数据
//返回值：为存储在该位置的元素
//返回NULL 表示有问题
LinkStackNode* LinkStack_Get(LinkStack *list);
 
 
//给LinkStack中指定位置插入数据，
//参数LinkStackNode为要插入的数据
//参数 pos 为要插入的位置
//成功返回1
//失败 返回<0
 
int LinkStack_Insert(LinkStack *list, LinkStackNode *node);
 
 
//从LinkStack 中删除栈顶位置的元素，实际上删除的链表的除了头结点的第一个元素
//参数 pos
//返回值为 删除的元素
//返回NULL 表示出现了error
LinkStackNode* LinkStack_Delete(LinkStack *list);
 
//判断当前linkstack 是否为null，如果为null，则返回1
//如果不为NULL，则返回-1；
int isEmptyLinkStack(LinkStack *list);
#endif


#include "006linkstack.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
 
typedef struct LinkStack {
	LinkStackNode head;
	int length;// 该链表的大小
}TLinkStack;
 
// 初始化，建立一个空的链表 
//返回值不为NULL，表示创建成功。
//返回值为NULL，表示创建失败。
LinkStack* LinkStack_Create() {
	TLinkStack * ts = (TLinkStack *)malloc(sizeof(TLinkStack));
	if (ts == NULL) {
		printf("LinkStack_Create error list==NULL\n");
		return NULL;
	}
	memset(ts, 0, sizeof(TLinkStack));
	ts->head.next = NULL;
	ts->length = 0;
 
	return ts;
}
 
//销毁该线性表
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Destory(LinkStack *list) {
	int ret = 1;
	if (list ==NULL) {
		ret = -1;
		printf("func LinkStack_Destory error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	free(ts);
	ts = NULL;
	list = NULL;
	return ret;
}
 
//清空seqlist
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Clear(LinkStack *list) {
	int ret = 1;
	if (list == NULL) {
		ret = -1;
		printf("func LinkStack_Clear error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	ts->head.next = NULL;
	ts->length = 0;
	return ret;
}
 
// 返回线性表List存在的元素个数
//返回值 >=0 表示：该list存在的元素个数
//<0 表示error
int LinkStack_Length(LinkStack *list) {
	int ret = 0;
	if (list == NULL) {
		ret = -1;
		printf("func LinkStack_Length error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	return ts->length;
}
 
 
 
//从LinkStack 中获取指定位置的数据
//参数pos：LinkStack中的位置
//返回值：为存储在该位置的元素
//返回NULL 表示有问题
LinkStackNode* LinkStack_Get(LinkStack *list) {
	LinkStackNode* ret = NULL;
	if (list == NULL) {
		ret = NULL;
		printf("func LinkStack_Get error bacesue list = NULL return ret = NULL\n");
		return ret;
	}
	TLinkStack * ts = list;
	if (ts->length==0) {
		ret = NULL;
		printf("func LinkStack_Get error bacesue ts->length = 0 return ret = NULL\n");
		return ret;
	}
	return ts->head.next;
}
 
 
//给LinkStack中指定位置插入数据，
//参数LinkStackNode为要插入的数据
//参数 pos 为要插入的位置
//成功返回1
//失败 返回<0
 
int LinkStack_Insert(LinkStack *list, LinkStackNode *node) {
	int ret = 1;
	if (list == NULL) {
		ret = -1;
		printf("func LinkStack_Insert error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	node->next = ts->head.next;
	ts->head.next = node;
	ts->length++;
	return ret;
}
 
 
//从LinkList 中删除指定位置的元素
//参数 pos
//返回值为 删除的元素
//返回NULL 表示出现了error
LinkStackNode* LinkStack_Delete(LinkStack *list) {
	LinkStackNode* ret = NULL;
	if (list == NULL) {
		ret = NULL;
		printf("func LinkStack_Delete error bacesue list = NULL return ret = NULL\n");
		return ret;
	}
	TLinkStack * ts = list;
	if (ts->length == 0) {
		ret = NULL;
		printf("func LinkStack_Delete error bacesue ts->length = 0 return ret = NULL\n");
		return ret;
	}
	LinkStackNode * delnode = ts->head.next;
	ts->head.next = delnode->next;
	ts->length--;
	return delnode;
 
}
 
//判断当前linkstack 是否为null，如果为null，则返回1
//如果不为NULL，则返回0；
//有error 则返回-1
int isEmptyLinkStack(LinkStack *list) {
	int ret = 0;
	if (list == NULL) {
		ret = -1;
		printf("func isEmptyLinkStack error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	int length = ts->length;
	if (length>0) {
		ret = 0;
	}
	else {
		ret = 1;
	}
	return ret;
}


#define _CRT_SECURE_NO_WARNINGS
#define _CRTDBG_MAP_ALLOC
#include "iostream"
#include <stdio.h>
#include <stdlib.h>
 
extern "C" {
#include "006linkstack.h"
}
 
typedef struct Teacher {
	LinkStackNode  linkstacknode;
	int age;
	char name[128];
	char *othername;
	char **stuname; //一个老师下面有5个学生
}Teacher;
 
int main() {
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
 
	int ret = 0;
	//初始化队列，要动态的创建SeqStack，根据user设定的大小创建
//int stacksize ，表示user 要创建栈的大小
//创建失败返回NULL
	LinkStack* linkstack = LinkStack_Create();
	if (linkstack == NULL) {
		ret = -1;
		printf("func LinkStack_Create error because linkstack = NULL return ret =-1\n");
		return ret;
	}
	ret = isEmptyLinkStack(linkstack);
	printf("isEmptyLinkStack = ret %d\n", ret);
 
	ret = LinkStack_Length(linkstack);
	printf("LinkStack_Length = ret %d\n", ret);
 
	Teacher tea1;
	tea1.age = 20;
	strcpy(tea1.name, (const char*)"tea1");
 
	tea1.othername = (char *)malloc(sizeof(char) * 128);
	memset(tea1.othername, 0, sizeof(char) * 128);
	strcpy(tea1.othername, (const char*)"tea1othername");
 
	tea1.stuname = (char **)malloc(sizeof(char *) * 5);
	memset(tea1.stuname, 0, sizeof(char *) * 5);
	for (size_t i = 0; i < 5; i++)
	{
		tea1.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
		memset(tea1.stuname[i], 0, sizeof(char) * 128);
		sprintf(tea1.stuname[i], "tea1stuname%d", i + 1);
	}
 
 
 
	Teacher tea2;
	tea2.age = 22;
 
	strcpy(tea2.name, (const char*)"tea2");
 
	tea2.othername = (char *)malloc(sizeof(char) * 128);
	memset(tea2.othername, 0, sizeof(char) * 128);
	strcpy(tea2.othername, (const char*)"tea2othername");
 
	tea2.stuname = (char **)malloc(sizeof(char *) * 5);
	memset(tea2.stuname, 0, sizeof(char *) * 5);
	for (size_t i = 0; i < 5; i++)
	{
		tea2.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
		memset(tea2.stuname[i], 0, sizeof(char) * 128);
		sprintf(tea2.stuname[i], "tea2stuname%d", i + 1);
	}
 
 
 
	Teacher tea3;
	tea3.age = 33;
	strcpy(tea3.name, (const char*)"tea3");
 
	tea3.othername = (char *)malloc(sizeof(char) * 128);
	memset(tea3.othername, 0, sizeof(char) * 128);
	strcpy(tea3.othername, (const char*)"tea3othername");
 
	tea3.stuname = (char **)malloc(sizeof(char *) * 5);
	memset(tea3.stuname, 0, sizeof(char *) * 5);
	for (size_t i = 0; i < 5; i++)
	{
		tea3.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
		memset(tea3.stuname[i], 0, sizeof(char) * 128);
		sprintf(tea3.stuname[i], "tea3stuname%d", i + 1);
	}
 
	ret = LinkStack_Insert(linkstack, (LinkStackNode * )&tea1);
	if (ret < 0) {
		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea1) func error ret =%d \n", ret);
		return ret;
	}
 
	ret = LinkStack_Insert(linkstack, (LinkStackNode *)&tea2);
	if (ret < 0) {
		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea2) func error ret =%d \n", ret);
		return ret;
	}
 
	ret = LinkStack_Insert(linkstack, (LinkStackNode *)&tea3);
	if (ret < 0) {
		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea3) func error ret =%d \n", ret);
		return ret;
	}
 
	printf("-after-\n");
	ret = isEmptyLinkStack(linkstack);
	printf("isEmptyLinkStack = ret %d\n", ret);
 
	ret = LinkStack_Length(linkstack);
	printf("LinkStack_Length = ret %d\n", ret);
 
 
 
	while (LinkStack_Length(linkstack) > 0) {
		Teacher * temptea = (Teacher *)LinkStack_Get(linkstack);
		if (temptea == NULL) {
			printf("can not get find teacher\n");
		}
		printf("temptea->age = %d,temptea->name = %s,temptea->othername=%s\n",
			temptea->age,
			temptea->name,
			temptea->othername);
		for (size_t j = 0; j < 5; j++)
		{
			printf("temptea->stuname[%d] = %s,  ",
				j, temptea->stuname[j]);
		}
		Teacher * deltea = (Teacher *)LinkStack_Delete(linkstack);
		if (deltea == NULL) {
			printf("LinkStack_Delete seqstack error\n");
		}
		if (deltea->othername != NULL) {
			free(deltea->othername);
 
		}
		if (deltea->stuname != NULL) {
			for (size_t i = 0; i < 5; i++)
			{
				if (deltea->stuname[i] != NULL) {
					free(deltea->stuname[i]);
				}
			}
			free(deltea->stuname);
			deltea->stuname = NULL;
		}
 
		printf("\n");
	}
	printf("sss\n");
 
	//销毁栈
	//成功 返回1 表示成功销毁栈 
	//失败 返回-1 表示该函数执行的时候有问题
	ret = LinkStack_Destory(linkstack);
 
 
	return 0;
 
 
 
 
 
}

相关应用：实现编译器中的符号成对检测

//几乎所有的编译器都具有检测括号是否匹配的能力，
//那么如何实现编译器中的符号成对检测？如下字符串:
//5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(
//算法思路
//
//从第一个字符开始扫描
//当遇见普通字符时忽略，
//当遇见左括号时压入栈中
//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
//匹配成功：继续读入下一个字符
//匹配失败：立即停止，并报错
//结束：
//成功 : 所有字符扫描完毕，且栈为空
// 失败：匹配失败或所有字符扫描完毕但栈非空

//总结：
//当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性


#define _CRT_SECURE_NO_WARNINGS
#define _CRTDBG_MAP_ALLOC
#include "iostream"
#include <stdio.h>
#include <stdlib.h>
 
 
//几乎所有的编译器都具有检测括号是否匹配的能力，
//那么如何实现编译器中的符号成对检测？如下字符串:
//5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(
//算法思路
//
//从第一个字符开始扫描
//当遇见普通字符时忽略，
//当遇见左括号时压入栈中
//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
//匹配成功：继续读入下一个字符
//匹配失败：立即停止，并报错
//结束：
//成功 : 所有字符扫描完毕，且栈为空
//	失败：匹配失败或所有字符扫描完毕但栈非空
 
//总结：
//当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性
 
char *err1 = (char *)"无法找到对应的右括号的 左括号";
char *err2 = (char *)"该 左括号 没有对应的有括号";
extern "C" {
#include "004seqstack.h"
}
 
int isLeft( char ch) {
	if ('(' == ch) {
		return 1;
	}
	return 0;
}
 
int isRight(char ch) {
	if (')' == ch) {
		return 1;
	}
	return 0;
}
 
void printerror(char* err,char *str, char *ptemp) {
	printf("err start");
	printf(err);
	printf("原始字符串如下\n");
	printf(str);
	printf("\n");
	printf("error位置如下\n");
 
	int num = ptemp - str;
	while (num > 0 ) {
		printf(" ");
		--num;
	}
	printf("|\n");
	printf("err end");
}
 
void testchar(char *str) {
	SeqStack * seqstack = createSeqStack(1024);
	if (seqstack ==NULL) {
		printf("func testchar error because seqstack==NULL\n");
		return;
	}
 
	if (str == NULL) {
		printf("testchar func error because str==NULL\n");
		return;
	}
	char *ptemp = str;//让辅助指针变量指向传递过来的str
	while (*(ptemp) != '\0') {
		if (isLeft(*ptemp)) { 当遇见左括号时压入栈中.判断是否是符号，如果是 左括号 符号，则要进栈，
			push_SeqStack(seqstack,ptemp);
 
		}
		if (isRight(*ptemp)) {//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
			//如果这时候栈中啥也没有，就有问题，直接break;
			if (size_SeqStack(seqstack) == 0) {
				printerror(err1,str,ptemp);
				break;
			}
			pop_SeqStack(seqstack);
		}
		ptemp++;
	}
	//当将整个字符串都弄完成后，检查栈中是否有元素，如果栈中有元素，说明有左括号没有匹配
	while (size_SeqStack(seqstack) > 0 ) {
		printerror(err2, str, (char *)top_SeqStack(seqstack));
		pop_SeqStack(seqstack);
	}
}
 
int main() {
	int ret = 0;
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
	//char* sourcestr = (char *)"5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(";
	char* sourcestr = (char *)"5 + 5 * (6) + 9 / 3 * 1 - (1 + 3(";
	testchar(sourcestr);
 
	return ret;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/489148