C++線性表深度解析之動(dòng)態(tài)數(shù)組與單鏈表和棧及隊(duì)列的實(shí)現(xiàn)
數(shù)據(jù)結(jié)構(gòu)大體可以分為兩個(gè)部分:邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。
物理結(jié)構(gòu)大體也可以分為兩個(gè)部分,即順序結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(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)訪問和順序存儲(chǔ)。
二、動(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.將二級(jí)指針、容量、大小等屬性設(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;//若位置無(wú)效則進(jìn)行尾插 } //動(dòng)態(tài)擴(kuò)展 if (this->m_size == this->m_capacity) { void** newSpace = (void**)new(void*[this->m_capacity * 2]);//每次擴(kuò)展為原來(lái)的兩倍 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;//無(wú)效位置變?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ù)組尾部)頻繁做出入棧和出棧操作。
對(duì)于數(shù)組尾部做插入和刪除操作效率高。(無(wú)需移動(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)棧
鏈表頭做棧頂利于頻繁地插入刪除(無(wú)需通過遍歷找到尾結(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)遇見左括號(hào)時(shí)壓入棧中,遇見右括號(hào)則彈出棧頂符號(hào)進(jìn)行匹配。
匹配成功,繼續(xù)識(shí)別下一字符。
匹配失敗,立即停止,報(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, "右括號(hào)沒有匹配到對(duì)應(yīng)的左括號(hào)", p); } } ++p; } while (sk.size() > 0) { printError(str, "左括號(hào)沒有匹配到右括號(hào)", (char*)sk.top()); sk.pop_back(); } return 0; }
五、隊(duì)列(受限線性表)
只允許在一端進(jìn)行插入操作,在另一端進(jìn)行刪除操作
可分別使用數(shù)組和鏈表實(shí)現(xiàn)隊(duì)列
1)隊(duì)列的順序存儲(chǔ)
數(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)六邊形掃雷游戲的示例代碼
所謂六邊形掃雷,就是沒有掃雷模式的消零算法,每一個(gè)安全的點(diǎn)都需要單獨(dú)挖出來(lái),一次顯示一個(gè)格子,感興趣的小伙伴可以跟隨小編一起了解一下2022-12-12通過stringstream實(shí)現(xiàn)常用的類型轉(zhuǎn)換實(shí)例代碼
在本篇文章里小編給大家分享了關(guān)于通過stringstream實(shí)現(xiàn)常用的類型轉(zhuǎn)換實(shí)例代碼內(nèi)容,需要的朋友們可以參考下。2020-04-04Java C++題解leetcode856括號(hào)的分?jǐn)?shù)
這篇文章主要為大家介紹了Java C++題解leetcode856括號(hào)的分?jǐn)?shù)實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-10-10C語(yǔ)言游戲必備:光標(biāo)定位與顏色設(shè)置的實(shí)現(xiàn)方法
本篇文章是對(duì)c語(yǔ)言中光標(biāo)定位與顏色設(shè)置的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05C++?STL實(shí)現(xiàn)非變易查找算法的示例代碼
C++?STL?中的非變易算法(Non-modifying?Algorithms)是指那些不會(huì)修改容器內(nèi)容的算法,是C++提供的一組模板函數(shù),下面我們就來(lái)看看這一算法的應(yīng)用吧2023-08-08C語(yǔ)言復(fù)雜鏈表的復(fù)制實(shí)例詳解
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言復(fù)雜鏈表的復(fù)制,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-02-02