目錄

結構特性

內存布局

結構樣式

結構拓展

單鏈表

結構定義

節點關聯

插入節點

刪除節點

常見操作????????

雙鏈表

環鏈表

結構容器

結構設計

---

結構特性

• 線性結構的存儲方式

  • 順序存儲 - 數組

  • 鏈式存儲 - 鏈表

• 線性結構的鏈式存儲是通過任意的存儲單元來存儲線性表當中的數據元素。

  • 存儲單元可以是連續的也可以是不連續的。

  • 線性結構的順序存儲中每個元素只需要存儲其元素數據即可。

  • 線性結構的鏈式存儲除了存儲元素數據外，還有存儲后繼元素的內存地址。

• 結構概念

  • 節點(Node) - 鏈式存儲結構中的元素單位為節點，通常由數據域和指針域共同組成。

  • 數據域(Data) - 存儲節點值。

  • 指針域(Next) - 存儲節點指向的下一個節點的內存地址。

  • 頭節點(Head) - 鏈表頭部節點。

  • 尾節點(Tail) - 鏈表的結束位置節點，其指針域指向NULL，表示了鏈表結束。

內存布局

• 鏈式存儲

  • 

  • 

  • 

• 節點樣式

  • 

結構樣式

• 單鏈表

  • 每個節點只有一個指針域，指向下一個節點。

  • 

• 雙向鏈表

  • 每個節點存在兩個指針域，一個指向前節點，一個指向后節點。

  • 

• 循環鏈表

  • 鏈表尾部節點指向頭節點。

  • 

結構拓展

單鏈表

結構定義

typedef struct ListNode
{//數據域int value;//指針域ListNode* Next;//賦值域ListNode(int num) : value(num), Next(nullptr){}
};

節點關聯

	ListNode* Node1 = new ListNode(1);ListNode* Node2 = new ListNode(2);ListNode* Node3 = new ListNode(3);ListNode* Node4 = new ListNode(4);ListNode* Node5 = new ListNode(5);Node1->Next = Node2;Node2->Next = Node3;Node3->Next = Node4;Node4->Next = Node5;Node5->Next = NULL;

插入節點

void Insert(ListNode* Cur, ListNode* Node)
{ListNode* Temp = Cur->Next;Cur->Next = Node;Node->Next = Temp;
}

刪除節點

void Remove(ListNode* Cur)
{//當前節點.Next = 當前節點.下一個節點.下一個節點ListNode* Node6 = Cur->Next;ListNode* Node3 = Node6->Next;Cur->Next = Node3;delete Node6;
}

常見操作????????

	//遍歷節點int nIndex = 0;ListNode* pTemp = Node1;while (pTemp != NULL){printf("Index -> [%d] -> Data -> [%d] \r\n", nIndex, pTemp->value);++nIndex;pTemp = pTemp->Next;}

雙鏈表

#include <iostream>class ListNode
{
public://數據域int value;//指針域ListNode* Prev;ListNode* Next;//賦值域ListNode(int Num): value(Num), Prev(nullptr), Next(nullptr) {}
};//追加節點
void Append(ListNode* Head , int val)
{ListNode* newNode = new ListNode(val);ListNode* tempNode = Head;while (tempNode->Next != NULL){tempNode = tempNode->Next;}tempNode->Next = newNode;newNode->Prev = tempNode;newNode->Next = NULL;}//添加節點
void Insert(ListNode* Head, int val)
{ListNode* newNode = new ListNode(val);ListNode* HeadNext = Head->Next;Head->Next = newNode;newNode->Prev = Head;newNode->Next = HeadNext;HeadNext->Prev = newNode;/*Node2.Next = NodeCC;NodeCC.Prev = Node2;NodeCC.Next = Node3;Node3.Prev = NodeCC;*/}//移除節點
void Remove(ListNode* Head)
{ListNode* tempNode = Head;while (tempNode->Next != NULL){tempNode = tempNode->Next;}tempNode->Prev->Next = NULL;delete tempNode;
}//刪除節點
void Erase(ListNode* Head)
{//當前節點.上一個.下一個 = 當前節點.下一個//當前節點.下一個.上一個 = 當前節點.上一個Head->Prev->Next = Head->Next;Head->Next->Prev = Head->Prev;
}int main()
{ListNode* Node1 = new ListNode(1);ListNode* Node2 = new ListNode(2);ListNode* Node3 = new ListNode(3);ListNode* Node4 = new ListNode(4);ListNode* Node5 = new ListNode(5);Node1->Prev = NULL;Node1->Next = Node2;Node2->Prev = Node1;Node2->Next = Node3;Node3->Prev = Node2;Node3->Next = Node4;Node4->Prev = Node3;Node4->Next = Node5;Node5->Prev = Node4;Node5->Next = NULL;Append(Node1 ,0xCC);Insert(Node2 ,0xDD);Remove(Node1);Erase(Node3);return 0;
}

環鏈表

#include <iostream>class ListNode
{
public://數據域int value;//指針域ListNode* Next;//賦值域ListNode(int Num) : value(Num), Next(nullptr){}
};int main()
{ListNode* Node1 = new ListNode(1);ListNode* Node2 = new ListNode(2);ListNode* Node3 = new ListNode(3);ListNode* Node4 = new ListNode(4);ListNode* Node5 = new ListNode(5);Node1->Next = Node2;Node2->Next = Node3;Node3->Next = Node4;Node4->Next = Node5;Node5->Next = Node1;ListNode* tempNode = Node1;do{printf("%d \r\n", tempNode->value);tempNode = tempNode->Next;} while (tempNode != Node1);return 0;
}

結構容器

• std:list

• 構造函數

  • 默認構造函數

  • 有參構造函數

  • 拷貝構造函數

  • 列表構造函數

  • 默認析構函數

• 大小函數

  • 節點數量

  • 是否為空

  • 清空數據

• 功能函數

  • 插入元素

  • 頭部插入

  • 尾部插入

  • 指定插入

  • 刪除元素

  • 修改元素

  • 訪問元素

結構設計

#include <iostream>class Node
{
public://數據域int value;//指針域Node* Prev;Node* Next;//賦值域Node(int Num, Node* p = nullptr, Node* n = nullptr) : value(Num), Prev(p), Next(n) {}
};class List
{
public://頭部節點Node* Head;//尾部節點Node* Tail;//節點數量size_t size;public://默認構造List();//有參構造List(int Count, int value);//拷貝構造List(const List& ref);//列表構造List(std::initializer_list<int> initList);//默認析構~List();public://是否為空bool IsEmpty();//節點數量size_t GetSize();//清空容器void Clear();public://尾部插入void Push_Back(int value);//頭部插入void Push_Front(int value);//指定插入void Insert(int InsertValue, int value);//尾部移除void Pop_Back();//頭部移除void Pop_Front();//按值匹配void Remove(int value);//查找節點bool Find(int value);public://賦值運算符List& operator=(const List & other);//下標運算符int& operator[](int Index);};std::ostream& operator<<(std::ostream& output, const List& obj);List::List()
{this->Head = nullptr;this->Tail = nullptr;this->size = 0;
}List::List(int Count, int value) : Head(nullptr), Tail(nullptr), size(0)
{while (Count--){Push_Back(value);}
}List::List(const List& ref) : Head(nullptr), Tail(nullptr), size(0)
{Node* node = ref.Head;while (node){Push_Back(node->value);node = node->Next;}
}List::List(std::initializer_list<int> initList) : Head(nullptr), Tail(nullptr), size(0)
{for (auto value : initList){Push_Back(value);}
}List::~List()
{Clear();
}bool List::IsEmpty()
{return this->size == 0 ? true : false;
}size_t List::GetSize()
{return this->size;
}void List::Clear()
{if (IsEmpty()) return;Node* node = this->Head;while (node){Node* Temp = node->Next;delete node;node = Temp;}Head = Tail = nullptr;size = 0;
}void List::Push_Back(int value)
{//創建對象時關聯前后節點對象Node* node = new Node(value, Tail, nullptr);//當前容器是否存在尾節點if (Tail != nullptr){Tail->Next = node;}//修正尾部節點Tail = node;//判斷頭部節點if (Head == nullptr){Head = node;}++this->size;
}void List::Push_Front(int value)
{Node* node = new Node(value, nullptr, Head);if (Head != nullptr){Head->Prev = node;}Head = node;if (Tail == nullptr){Tail = node;}++this->size;
}void List::Insert(int InsertValue, int value)
{Node* node = Head;while (node != nullptr && node->value != InsertValue){node = node->Next;}if (node != nullptr){Node* InsertNode = new Node(value, node, node->Next);if (node->Next != nullptr){node->Next->Prev = InsertNode;}else{Tail = InsertNode;}node->Next = InsertNode;++this->size;}}void List::Pop_Back()
{if (Tail == nullptr){return;}//保存尾節點Node* temp = Tail;//修正尾節點Tail = Tail->Prev;if (Tail == nullptr){Head = nullptr;}else{Tail->Next = nullptr;}delete temp;--this->size;
}void List::Pop_Front()
{if (Head == nullptr){return;}Node* temp = Head;Head = Head->Next;if (Head == nullptr){Tail = nullptr;}else{Head->Prev = nullptr;}delete temp;--this->size;
}void List::Remove(int value)
{Node* node = Head;while (node != nullptr && node->value != value){node = node->Next;}if (node != nullptr){if (node == Head) Pop_Front();else if (node == Tail) Pop_Back();else{node->Prev->Next = node->Next;node->Next->Prev = node->Prev;delete node;--this->size;}}}bool List::Find(int value)
{Node* node = Head;while (node != nullptr){if (node->value == value) return true;node = node->Next;}return false;
}List& List::operator=(const List& other)
{if (this != &other){//刪除默認數據Clear();Node* node = other.Head;while (node){Push_Back(node->value);node = node->Next;}}return *this;
}int& List::operator[](int Index)
{Node* node = Head;int Count = 0;while (node != nullptr && Count < Index){node = node->Next;++Count;}if (node != nullptr){return node->value;}
}std::ostream& operator<<(std::ostream& output, const List& obj)
{Node* node = obj.Head;while (node != nullptr){output << node->value;if (node->Next != nullptr){output << " | ";}node = node->Next;}return output;
}int main()
{//默認構造函數List myList1;//有參構造函數List myList3(3, 0xCC);//列表構造函數List myList4 = { 1,2,3,4,5 };//拷貝構造函數List myList5 = myList4;//賦值運算符List myList6;myList6 = myList5;std::cout << myList6 << std::endl;return 0;
}