欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++線性表深度解析之動態(tài)數組與單鏈表和棧及隊列的實現

 更新時間：2022年05月11日 11:12:21   作者：GG_Bond18  
這篇文章主要為大家詳細介紹了C++實現動態(tài)數組、單鏈表、棧、隊列，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

數據結構大體可以分為兩個部分:邏輯結構和物理結構。

物理結構大體也可以分為兩個部分，即順序結構和鏈式存儲結構。

而線性結構就是邏輯結構中的一種。

一、線性表介紹

線性表是零個或多個數據元素組成的有限序列，數據元素之間有順序，數據元素個數有限且類型必須相同。動態(tài)數組、鏈表、棧和隊列都屬于線性結構。

線性表性質

1.a[0]為線性表的第一個元素，只有一個后繼。

2.a[n - 1]為線性表最后一個元素，只有一個前驅。

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

4.線性表能夠逐項訪問和順序存儲。

二、動態(tài)數組

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;//維護真實開辟在堆區(qū)的指針
	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;//若位置無效則進行尾插
	}
	//動態(tài)擴展
	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;
	}
}

三、單鏈表(企業(yè)設計方式)

1）分析與設計

該設計方式與常見的一個數據域、一個指針域的設計方式并相同。

應與用戶協定：使用該鏈表時，自定義數據類型預留4個字節(jié)的空間交予鏈表連接使用。

該方法本質上連接的是用戶的數據，而傳統版是一個個結點連接，插入時創(chuàng)建新結點并將用戶數據拷貝進去。

頭文件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;//無效位置變?yōu)槲膊?
	}
	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.算法思想

從第一個字符開始掃描，當遇見普通字符時忽略。當遇見左括號時壓入棧中，遇見右括號則彈出棧頂符號進行匹配。

匹配成功，繼續(xù)識別下一字符。

匹配失敗，立即停止，報錯。

成功條件:所有字符掃描完且棧為空

失敗條件：匹配失敗或掃描完畢但棧非空

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;
}

五、隊列(受限線性表)

只允許在一端進行插入操作，在另一端進行刪除操作

可分別使用數組和鏈表實現隊列

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++線性表深度解析之動態(tài)數組與單鏈表和棧及隊列的實現的文章就介紹到這了,更多相關C++動態(tài)數組內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

  • C語言實現六邊形掃雷游戲的示例代碼

    C語言實現六邊形掃雷游戲的示例代碼

    所謂六邊形掃雷，就是沒有掃雷模式的消零算法，每一個安全的點都需要單獨挖出來，一次顯示一個格子，感興趣的小伙伴可以跟隨小編一起了解一下
    2022-12-12
  • 通過stringstream實現常用的類型轉換實例代碼

    通過stringstream實現常用的類型轉換實例代碼

    在本篇文章里小編給大家分享了關于通過stringstream實現常用的類型轉換實例代碼內容，需要的朋友們可以參考下。
    2020-04-04
  • Java C++題解leetcode856括號的分數

    Java C++題解leetcode856括號的分數

    這篇文章主要為大家介紹了Java C++題解leetcode856括號的分數實現示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
    2022-10-10
  • 使用C++遞歸求解跳臺階問題

    使用C++遞歸求解跳臺階問題

    這篇文章主要介紹了使用C++求解跳臺階問題的方法,通過遞歸算法來解決,不算難,文中給出了計算思路,需要的朋友可以參考下
    2016-02-02
  • C語言游戲必備:光標定位與顏色設置的實現方法

    C語言游戲必備:光標定位與顏色設置的實現方法

    本篇文章是對c語言中光標定位與顏色設置的方法進行了詳細的分析介紹，需要的朋友參考下
    2013-05-05
  • C++?STL實現非變易查找算法的示例代碼

    C++?STL實現非變易查找算法的示例代碼

    C++?STL?中的非變易算法（Non-modifying?Algorithms）是指那些不會修改容器內容的算法,是C++提供的一組模板函數,下面我們就來看看這一算法的應用吧
    2023-08-08
  • C++基于人工智能搜索策略解決農夫過河問題示例

    C++基于人工智能搜索策略解決農夫過河問題示例

    這篇文章主要介紹了C++基于人工智能搜索策略解決農夫過河問題,簡單描述了農夫過河問題的概念、實現原理并結合具體實例形式給出了C++使用人工智能搜索策略解決農夫過河問題的相關操作技巧,需要的朋友可以參考下
    2017-12-12
  • C++中順序表操作的示例代碼

    C++中順序表操作的示例代碼

    這篇文章主要為大家詳細介紹了C++中順序表的基礎操作的相關代碼，主要有順序表的輸出、插入和刪除數據等，感興趣的小伙伴可以了解一下
    2022-10-10
  • 淺析C/C++變量在內存中的分布

    淺析C/C++變量在內存中的分布

    變量在內存地址的分布為：堆-棧-代碼區(qū)-全局靜態(tài)-常量數據。同一區(qū)域的各變量按聲明的順序在內存的中依次由低到高分配空間（只有未賦值的全局變量是個例外）
    2013-09-09
  • C語言復雜鏈表的復制實例詳解

    C語言復雜鏈表的復制實例詳解

    這篇文章主要為大家詳細介紹了C語言復雜鏈表的復制，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-02-02

最新評論