C++线性表深度解析之动态数组与单链表和栈及队列的实现

一、线性表介绍

线性表是零个或多个数据元素组成的有限序列，数据元素之间有顺序，数据元素个数有限且类型必须相同。动态数组、链表、栈和队列都属于线性结构。

线性表性质

1.a[0]为线性表的第一个元素，只有一个后继。

2.a[n – 1]为线性表最后一个元素，只有一个前驱。

3.除a[0]和a[n – 1]之外的其他元素，既有前驱，又有后继。

4.线性表能够逐项访问和顺序存储。

二、动态数组

1）分析与设计

头文件DynamicArray.h

#pragma once
#include<cstring>
class dynamicArray
{
public:
	dynamicArray(int capcity);
	void insert(int pos, void* data);
	void push_back(void* data);
	void for_each(void(*MyPrint)(void*));//参数为函数指针，由用户提供
	void remove(int pos);
	void remove(void* value, bool(*MyCompare)(void*, void*));
	~dynamicArray();
private:
	void** m_pAdder;//维护真实开辟在堆区的指针
	int m_capacity;//容量
	int m_size;//当前大小
};

设计思路：

1.将二级指针、容量、大小等属性设为私有权限，避免用户直接调用。

2.提供按位置插入和尾插两种插入元素的方式。

3.利用函数重载remove实现按位置删除元素和按值删除元素。

4.提供遍历API，用数提供比较函数即可

5.返回容量、大小等API可根据自身需求考虑是否提供

2）实现

源文件DynamicArray.cpp

#include"DynamicArray.h"
dynamicArray::dynamicArray(int capacity)
{
	if (capacity <= 0)return;
	this->m_pAdder = (void**)new (void*[capacity]);
	if (this->m_pAdder == nullptr)return;
	this->m_capacity = capacity;
	this->m_size = 0;
}
void dynamicArray::insert(int pos, void* data)
{
	if (this->m_pAdder == nullptr || data == nullptr)return;
	if (pos<0 || pos>this->m_size)
	{
		pos = this->m_size;//若位置无效则进行尾插
	}
	//动态扩展
	if (this->m_size == this->m_capacity)
	{
		void** newSpace = (void**)new(void*[this->m_capacity * 2]);//每次扩展为原来的两倍
		if (newSpace == nullptr)return;
		memcpy(newSpace, this->m_pAdder, sizeof(void*) * this->m_size);
		delete[]this->m_pAdder;
		this->m_pAdder = newSpace;
		this->m_capacity *= 2;
	}
	//插入元素
	for (int i = this->m_size - 1; i >= pos; --i)//反向遍历
	{
		this->m_pAdder[i + 1] = this->m_pAdder[i];//看似越界实则并没有，m_capacity > m_size
	}
	this->m_pAdder[pos] = data;
	++this->m_size;
}
void dynamicArray::push_back(void* data)
{
	this->insert(this->m_size, data);
}
void dynamicArray::for_each(void(*MyPrint)(void*))
{
	if (this->m_pAdder == nullptr || MyPrint == nullptr)return;
	for (int i = 0; i < this->m_size ; ++i)
	{
		MyPrint(this->m_pAdder[i]);
	}
}
void dynamicArray::remove(int pos)
{
	if (pos<0 || pos>this->m_size - 1)return;
	for (int i = pos; i < this->m_size - 1; ++i)
	{
		this->m_pAdder[i] = this->m_pAdder[i + 1];
	}
	--this->m_size;
}
void dynamicArray::remove(void* value, bool(*MyCompare)(void*, void*))
{
	if (value == nullptr)return;
	for (int i = 0; i < this->m_size; ++i)
	{
		if (MyCompare(this->m_pAdder[i], value))
		{
			this->remove(i);
			--i;
		}
	}
}
dynamicArray:: ~dynamicArray()
{
	if (this->m_pAdder != nullptr)
	{
		delete[]this->m_pAdder;
		this->m_pAdder = nullptr;
	}
}

三、单链表(企业设计方式)

1）分析与设计

该设计方式与常见的一个数据域、一个指针域的设计方式并相同。

应与用户协定：使用该链表时，自定义数据类型预留4个字节的空间交予链表连接使用。

该方法本质上连接的是用户的数据，而传统版是一个个结点连接，插入时创建新结点并将用户数据拷贝进去。

头文件LinkList.h

#pragma once
#include<iostream>
using namespace std;
class LinkNode
{
	friend class LinkList;
private:
	LinkNode* next;
};
class LinkList
{
public:
	LinkList();
	void insert(int pos, void* data);
	void push_back(void* data);
	void for_each(void(*MyPrint)(void*));
	void remove(int pos);
	~LinkList();
private:
	LinkNode pHeader;
	int m_size;
};

2）实现

源文件LinkList.cpp

#include"LinkList.h"
LinkList::LinkList()
{
	this->pHeader.next = nullptr;
	this->m_size = 0;
}
void LinkList::insert(int pos, void* data)
{
	if (data == nullptr)return;
	if (pos<0 || pos>this->m_size)
	{
		pos = this->m_size;//无效位置变为尾插
	}
	LinkNode* NewNode = (LinkNode*)data;
	LinkNode* pCurrent = &(this->pHeader);
	for (int i = 0; i < pos; ++i)
	{
		pCurrent = pCurrent->next;//找到前驱结点
	}
	//变更指针指向
	NewNode->next = pCurrent->next;
	pCurrent->next = NewNode;
	++this->m_size;
}
void LinkList::push_back(void* data)
{
	this->insert(this->m_size, data);
}
void LinkList::for_each(void(*MyPrint)(void*))
{
	LinkNode* node = this->pHeader.next;
	for (int i = 0; i < this->m_size; ++i)
	{
		MyPrint(node);
		node = node->next;
	}
}
void LinkList::remove(int pos)
{
	if (pos<0 || pos>this->m_size - 1)return;
	LinkNode* pCurrent = &(this->pHeader);
	for (int i = 0; i < pos; ++i)
	{
		pCurrent = pCurrent->next;//找到前驱结点
	}
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;
	--this->m_size;
}
LinkList::~LinkList()
{
	this->pHeader.next = nullptr;
	this->m_size = 0;
}

四、栈(受限线性表)

它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。

可分别使用数组和链表实现栈

1）利用数组实现栈

数组首地址做栈底。栈顶(数组尾部)频繁做出入栈和出栈操作。

对于数组尾部做插入和删除操作效率高。(无需移动其他元素)

头文件StackArray.h

#pragma once
#define MAX  1024
#include<iostream>
#include<cstring>
using namespace std;
class Stack
{
public:
	Stack();
	void top_back(void* data);//压栈
	void pop_back();//出栈
	void* top();//返回栈顶
	int size();
	bool isEmpty();
	~Stack();
private:
	void* data[MAX];//指针数组——栈数组
	int m_size;
};

源文件StackArray.cpp

#include"StackArray.h"
Stack::Stack()
{
	this->m_size = 0;
	memset(this->data, 0, sizeof(void*) * MAX);
}
void Stack::top_back(void* data)
{
	if (data == nullptr)return;
	this->data[this->m_size] = data;
	++this->m_size;
}
void Stack::pop_back()
{
	this->data[this->m_size - 1] = nullptr;
	--this->m_size;
}
void* Stack::top()
{
	if (this->m_size == 0)return nullptr;
	return this->data[this->m_size - 1];
}
int Stack::size()
{
	return this->m_size;
}
bool Stack::isEmpty()
{
	if (this->m_size == 0)return true;
	return false;
}
Stack::~Stack()
{
	this->m_size = 0;
	memset(this->data, 0, sizeof(void*) * MAX);
}

2）利用单链表实现栈

链表头做栈顶利于频繁地插入删除(无需通过遍历找到尾结点)

头文件StackLink.h

#pragma once
class StackNode
{
	friend class StackLink;
private:
	StackNode* next;
};
class StackLink
{
public:
	StackLink();
	void top_back(void* data);
	void pop_back();
	void* top();
	int size();
	bool isEmpty();
	~StackLink();
private:
	StackNode pHeader;
	int m_size;
};

源文件StackLink.cpp

#include"StackLink.h"
StackLink::StackLink()
{
	this->pHeader.next = nullptr;
	this->m_size = 0;
}
void StackLink::top_back(void* data)
{
	if (data == nullptr)return;
	StackNode* myNode = (StackNode*)data;
	myNode->next = this->pHeader.next;
	this->pHeader.next = myNode;
	++this->m_size;
}
void StackLink::pop_back()
{
	StackNode* pDel = this->pHeader.next;
	this->pHeader.next = pDel->next;
	--this->m_size;
}
void* StackLink::top()
{
	if (this->m_size == 0)return nullptr;
	return this->pHeader.next;
}
int StackLink::size()
{
	return this->m_size;
}
bool StackLink::isEmpty()
{
	if (this->m_size == 0)
	{
		return true;
	}
	return false;
}
StackLink::~StackLink()
{
	this->pHeader.next = nullptr;
	this->m_size = 0;
}

3）栈的应用——就近匹配

1.算法思想

从第一个字符开始扫描，当遇见普通字符时忽略。当遇见左括号时压入栈中，遇见右括号则弹出栈顶符号进行匹配。

匹配成功，继续识别下一字符。

匹配失败，立即停止，报错。

成功条件:所有字符扫描完且栈为空

失败条件：匹配失败或扫描完毕但栈非空

2.实现

#include<iostream>
#include<string>
#include"StackArray.h"
using namespace std;
bool isLeft(char ch)
{
	return ch == '(';
}
bool isRight(char ch)
{
	return ch == ')';
}
void printError(char* str, string errMsg, char* pos)
{
	cout << "错误信息:" << errMsg << endl;
	cout << str << endl;
	int num = pos - str;
	for (int i = 0; i < num; ++i)
	{
		cout << " ";
	}
	cout << "~" << endl;
}
int main()
{
	char* str = (char*)"5 + 5 * (6) + 9 / 3 * 1 - ( 1 + 310";
	char* p = str;
	Stack sk;
	while (*p != '\0')
	{
		if (isLeft(*p))
		{
			sk.top_back(p);
		}
		if (isRight(*p))
		{
			if (sk.size() > 0)
			{
				sk.pop_back();
			}
			else
			{
				printError(str, "右括号没有匹配到对应的左括号", p);
			}
		}
		++p;
	}
	while (sk.size() > 0)
	{
		printError(str, "左括号没有匹配到右括号", (char*)sk.top());
		sk.pop_back();
	}
	return 0;
}

C++线性表深度解析之动态数组与单链表和栈及队列的实现

五、队列(受限线性表)

只允许在一端进行插入操作，在另一端进行删除操作

可分别使用数组和链表实现队列

1）队列的顺序存储

数组的首地址做队头或队尾效率相同，本文不做详细介绍

2）利用单链表实现队列

头文件QueueLink.h

#pragma once
class QueueNode
{
	friend class QueueLink;
private:
	QueueNode* next;
};
class QueueLink
{
public:
	QueueLink();
	void push_QueueLink(void* data);
	void pop_QueueLink();
	int size();
	void* head();
	void* tail();
	bool isEmpty();
	~QueueLink();
private:
	QueueNode pHeader;
	QueueNode* pTail;//用于记录尾结点，不必通过遍历找到尾结点
	int m_size;
};

源文件QueueLink.cpp

#include"QueueLink.h"
QueueLink::QueueLink()
{
	this->m_size = 0;
	this->pHeader.next = nullptr;
	this->pTail = &this->pHeader;
}
void QueueLink::push_QueueLink(void* data)
{
	if (data == nullptr)return;
	QueueNode* myNode = (QueueNode*)data;
	this->pTail->next = myNode;
	myNode->next = nullptr;
	this->pTail = myNode;
	++this->m_size;
}
void QueueLink::pop_QueueLink()
{
	if (this->m_size == 0)return;
	if (this->m_size == 1)
	{
		this->pHeader.next = nullptr;
		this->pTail = &this->pHeader;
	}
	else
	{
		QueueNode* pDel = this->pHeader.next;
		this->pHeader.next = pDel->next;
	}
	--this->m_size;
}
int QueueLink::size()
{
	return this->m_size;
}
void* QueueLink::head()
{
	return this->pHeader.next;
}
void* QueueLink::tail()
{
	return this->pTail;
}
bool QueueLink::isEmpty()
{
	if (this->m_size == 0)return true;
	return false;
}
QueueLink::~QueueLink()
{
	this->m_size = 0;
	this->pHeader.next = nullptr;
	this->pTail = &this->pHeader;
}

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

C++线性表深度解析之动态数组与单链表和栈及队列的实现

目录

一、线性表介绍

线性表性质

二、动态数组

1）分析与设计

2）实现

三、单链表(企业设计方式)

1）分析与设计

2）实现

四、栈(受限线性表)

1）利用数组实现栈

2）利用单链表实现栈

3）栈的应用——就近匹配

1.算法思想

2.实现

五、队列(受限线性表)

1）队列的顺序存储

2）利用单链表实现队列

评论(0)

提示：请文明发言取消回复

作者信息

本站推荐

2025自媒体实战营，Deepseek、即梦 AI、Midjourney系统教程及案例实操

视频号短视频带货新玩法，用这个方法，一天佣金4407（附详细教程）

2025电商爆款课程，内销外销等方法，从0到爆单助力商家快速起量

2025小店运营全套系列课从小店基础入门到进阶精通

主播起号0-1快速成长从基础入门到进阶线上课

Ai五阶体系课入门通识理论+实操带你快速入门

热门资源

苹果cms海螺影视模板/大橙子模板/仿B站模板/v7模板/带手机移动端+详细安装使用说明

【已测】修复版H5骰子微信竞猜游戏骰宝免公众号版修复登录ID相同完美全套源码对接免签支付

网页游戏卧龙吟一键服务端加远程工具带架设教程

邪风曲单机版 2D回合制网络游戏源码一键安装即玩服务端公益服+GM工具

完整可用版本去水印小程序源码带教程源码

仙侠H5【苍穹剑诀】一键即玩端+授权后台+外网教程

C++线性表深度解析之动态数组与单链表和栈及队列的实现

目录

一、线性表介绍

线性表性质

二、动态数组

1）分析与设计

2）实现

三、单链表(企业设计方式)

1）分析与设计

2）实现

四、栈(受限线性表)

1）利用数组实现栈

2）利用单链表实现栈

3）栈的应用——就近匹配

1.算法思想

2.实现

五、队列(受限线性表)

1）队列的顺序存储

2）利用单链表实现队列

评论(0)

提示：请文明发言 取消回复

相关文章

作者信息

本站推荐

热门资源

提示：请文明发言取消回复