C++線性表深度解析之動(dòng)態(tài)數(shù)組與單鏈表和棧及隊(duì)列的實(shí)現(xiàn)
更新時(shí)間：2022年05月11日 11:12:21 作者：GG_Bond18
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)動(dòng)態(tài)數(shù)組、單鏈表、棧、隊(duì)列，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
數(shù)據(jù)結(jié)構(gòu)大體可以分為兩個(gè)部分:邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。
物理結(jié)構(gòu)大體也可以分為兩個(gè)部分，即順序結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
而線性結(jié)構(gòu)就是邏輯結(jié)構(gòu)中的一種。
一、線性表介紹
線性表是零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列，數(shù)據(jù)元素之間有順序，數(shù)據(jù)元素個(gè)數(shù)有限且類型必須相同。動(dòng)態(tài)數(shù)組、鏈表、棧和隊(duì)列都屬于線性結(jié)構(gòu)。
線性表性質(zhì)
1.a[0]為線性表的第一個(gè)元素，只有一個(gè)后繼。
2.a[n - 1]為線性表最后一個(gè)元素，只有一個(gè)前驅(qū)。
3.除a[0]和a[n - 1]之外的其他元素，既有前驅(qū)，又有后繼。
4.線性表能夠逐項(xiàng)訪問和順序存儲。
二、動(dòng)態(tài)數(shù)組
1）分析與設(shè)計(jì)
頭文件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*));//參數(shù)為函數(shù)指針，由用戶提供
void remove(int pos);
void remove(void* value, bool(*MyCompare)(void*, void*));
~dynamicArray();
private:
void** m_pAdder;//維護(hù)真實(shí)開辟在堆區(qū)的指針
int m_capacity;//容量
int m_size;//當(dāng)前大小
};設(shè)計(jì)思路：
1.將二級指針、容量、大小等屬性設(shè)為私有權(quán)限，避免用戶直接調(diào)用。
2.提供按位置插入和尾插兩種插入元素的方式。
3.利用函數(shù)重載remove實(shí)現(xiàn)按位置刪除元素和按值刪除元素。
4.提供遍歷API，用數(shù)提供比較函數(shù)即可
5.返回容量、大小等API可根據(jù)自身需求考慮是否提供
2）實(shí)現(xiàn)
源文件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;//若位置無效則進(jìn)行尾插
}
//動(dòng)態(tài)擴(kuò)展
if (this->m_size == this->m_capacity)
{
void** newSpace = (void**)new(void*[this->m_capacity * 2]);//每次擴(kuò)展為原來的兩倍
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];//看似越界實(shí)則并沒有，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è)設(shè)計(jì)方式)
1）分析與設(shè)計(jì)
該設(shè)計(jì)方式與常見的一個(gè)數(shù)據(jù)域、一個(gè)指針域的設(shè)計(jì)方式并相同。
應(yīng)與用戶協(xié)定：使用該鏈表時(shí)，自定義數(shù)據(jù)類型預(yù)留4個(gè)字節(jié)的空間交予鏈表連接使用。
該方法本質(zhì)上連接的是用戶的數(shù)據(jù)，而傳統(tǒng)版是一個(gè)個(gè)結(jié)點(diǎn)連接，插入時(shí)創(chuàng)建新結(jié)點(diǎn)并將用戶數(shù)據(jù)拷貝進(jìn)去。
頭文件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）實(shí)現(xiàn)
源文件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;//找到前驅(qū)結(jié)點(diǎn)
}
//變更指針指向
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;//找到前驅(qū)結(jié)點(diǎn)
}
LinkNode* pDel = pCurrent->next;
pCurrent->next = pDel->next;
--this->m_size;
}
LinkList::~LinkList()
{
this->pHeader.next = nullptr;
this->m_size = 0;
}四、棧(受限線性表)
它的特殊之處在于限制了這個(gè)線性表的插入和刪除的位置，它始終只在棧頂進(jìn)行。
可分別使用數(shù)組和鏈表實(shí)現(xiàn)棧
1）利用數(shù)組實(shí)現(xiàn)棧
數(shù)組首地址做棧底。棧頂(數(shù)組尾部)頻繁做出入棧和出棧操作。
對于數(shù)組尾部做插入和刪除操作效率高。(無需移動(dòng)其他元素)
頭文件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];//指針數(shù)組——棧數(shù)組
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）利用單鏈表實(shí)現(xiàn)棧
鏈表頭做棧頂利于頻繁地插入刪除(無需通過遍歷找到尾結(jié)點(diǎn))
頭文件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）棧的應(yīng)用——就近匹配
1.算法思想
從第一個(gè)字符開始掃描，當(dāng)遇見普通字符時(shí)忽略。當(dāng)遇見左括號時(shí)壓入棧中，遇見右括號則彈出棧頂符號進(jìn)行匹配。
匹配成功，繼續(xù)識別下一字符。
匹配失敗，立即停止，報(bào)錯(cuò)。
成功條件:所有字符掃描完且棧為空
失敗條件：匹配失敗或掃描完畢但棧非空
2.實(shí)現(xiàn)
#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 << "錯(cuò)誤信息:" << 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, "右括號沒有匹配到對應(yīng)的左括號", p);
}
}
++p;
}
while (sk.size() > 0)
{
printError(str, "左括號沒有匹配到右括號", (char*)sk.top());
sk.pop_back();
}
return 0;
}
五、隊(duì)列(受限線性表)
只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作
可分別使用數(shù)組和鏈表實(shí)現(xiàn)隊(duì)列
1）隊(duì)列的順序存儲
數(shù)組的首地址做隊(duì)頭或隊(duì)尾效率相同，本文不做詳細(xì)介紹
2）利用單鏈表實(shí)現(xiàn)隊(duì)列
頭文件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;//用于記錄尾結(jié)點(diǎn)，不必通過遍歷找到尾結(jié)點(diǎn)
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;
}到此這篇關(guān)于C++線性表深度解析之動(dòng)態(tài)數(shù)組與單鏈表和棧及隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++動(dòng)態(tài)數(shù)組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
所謂六邊形掃雷，就是沒有掃雷模式的消零算法，每一個(gè)安全的點(diǎn)都需要單獨(dú)挖出來，一次顯示一個(gè)格子，感興趣的小伙伴可以跟隨小編一起了解一下2022-12-12
通過stringstream實(shí)現(xiàn)常用的類型轉(zhuǎn)換實(shí)例代碼
在本篇文章里小編給大家分享了關(guān)于通過stringstream實(shí)現(xiàn)常用的類型轉(zhuǎn)換實(shí)例代碼內(nèi)容，需要的朋友們可以參考下。2020-04-04
Java C++題解leetcode856括號的分?jǐn)?shù)
這篇文章主要為大家介紹了Java C++題解leetcode856括號的分?jǐn)?shù)實(shí)現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-10-10
這篇文章主要介紹了使用C++求解跳臺階問題的方法,通過遞歸算法來解決,不算難,文中給出了計(jì)算思路,需要的朋友可以參考下2016-02-02
C語言游戲必備:光標(biāo)定位與顏色設(shè)置的實(shí)現(xiàn)方法
本篇文章是對c語言中光標(biāo)定位與顏色設(shè)置的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++?STL實(shí)現(xiàn)非變易查找算法的示例代碼
C++?STL?中的非變易算法（Non-modifying?Algorithms）是指那些不會修改容器內(nèi)容的算法,是C++提供的一組模板函數(shù),下面我們就來看看這一算法的應(yīng)用吧2023-08-08
這篇文章主要介紹了C++基于人工智能搜索策略解決農(nóng)夫過河問題,簡單描述了農(nóng)夫過河問題的概念、實(shí)現(xiàn)原理并結(jié)合具體實(shí)例形式給出了C++使用人工智能搜索策略解決農(nóng)夫過河問題的相關(guān)操作技巧,需要的朋友可以參考下2017-12-12
這篇文章主要為大家詳細(xì)介紹了C++中順序表的基礎(chǔ)操作的相關(guān)代碼，主要有順序表的輸出、插入和刪除數(shù)據(jù)等，感興趣的小伙伴可以了解一下2022-10-10
變量在內(nèi)存地址的分布為：堆-棧-代碼區(qū)-全局靜態(tài)-常量數(shù)據(jù)。同一區(qū)域的各變量按聲明的順序在內(nèi)存的中依次由低到高分配空間（只有未賦值的全局變量是個(gè)例外）2013-09-09
這篇文章主要為大家詳細(xì)介紹了C語言復(fù)雜鏈表的復(fù)制，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02