文章目錄
- 目錄
- 鏈表的基本概念
- 1.數組和鏈表
- 鏈表的使用
- 1.鏈表的簡單使用
- 2.鏈表的進階使用
- 3.鏈表的高階使用
- 4.鏈表的其他操作
- 鏈表容器list
- 1.list介紹
- 2. list使用
- 3. list與vector之間的區別
- 4.list例子代碼
目錄
- 數據結構：
- 邏輯結構：數組，棧，隊列，字符串，樹，圖
- 存儲結構：順序存儲，鏈式存儲
- C++常用的數據結構有：string , stack , queue , deque , vector , list , map , iterators.
鏈表的基本概念
鏈表是一種線性表，其在內存中以鏈式結構存儲，所以叫做鏈表。具有插入和刪除方便，但是訪問則必須從鏈表的頭開始。
1.數組和鏈表
鏈表的使用
1.鏈表的簡單使用
一個個節點按順序串接起來，就構成了鏈表。顯然這一個個節點是很關鍵的，假設我們要構造一個int類型的鏈表，那么一個節點中就需要包含兩個元素：
- 一個是當前節點所保存的值，設為int value。
- 另一個就是指向下一個節點的指針，我們再假設這個節點類是node，那么這個指針就是 node *next。
這里一定不是int *next。因為這個指針指向的下一個元素是一個類的實例，而不是int類型的數據。那么node這個類最簡單的實現就如下:
class node
{
public: int value; node *next; node() { value = 0; next = NULL; }
};
這個類名字為node，包含兩個元素，一個是當前node的值，一個是指向下一個節點的指針，還有一個構造函數，分別將value初始化為0、next初始化為NULL
拿到這個類以后，假設我們生成兩個這個類的實例，node1和node2，再將node1的next指針指向node2，就構成了有兩個元素的鏈表。這樣如果我們拿到node1這個節點，就可以通過next指針訪問node2。比如下面的代碼
#include <iostream>
#include <deque>using namespace std;class node{
public:int value;//鏈表節點的數據域node* next;//用于指向下一個節點，是鏈表中的指針域node():value(0),next(NULL){};//默認構造函數node(int value):value(value),next(NULL){};//帶參數的構造函數 ~ node(){cout<<"delete the node!!!"<<endl;delete next; // 刪除節點的指針域 }
}; int main(){node mNode1(1),mNode2(2),mNode3(3),mNode4(4);mNode1.next = &mNode2;mNode2.next = &mNode3;mNode3.next = &mNode4;cout<<"the value of node3 is :"<<mNode3.value<<endl; //直接輸出節點 cout<<"the value of node3 is :"<<mNode1.next->next->value<<endl; //通過鏈表查找 return 0;
}
the value of node3 is :3
the value of node3 is :3
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
2.鏈表的進階使用
上述這樣就構成了一個最簡單的鏈表，如果還有新的節點出現，那么就如法炮制，鏈在表尾或者表頭，當然插在中間也是沒問題的。
但是這樣還有個問題就是node1和node2是我們提前聲明好的，而且知道這兩個實例的名稱，如果我們需要1000甚至跟多節點，這種方式顯然是不科學的，而且在很多時候，我們都是動態生成一個類的實例，返回的是這個實例的首地址。
下面的代碼我們用一個for循環，生成11個節點，串起來形成一個鏈表
原理就是先生成一個頭結點，然后動態生成10個節點，每生成一個節點，就將這個節點指向頭結點，然后更新頭結點為當前節點
#include <iostream>
#include <deque>using namespace std;class Node{
public:int value;//鏈表節點的數據域Node* next;//用于指向下一個節點，是鏈表中的指針域Node():value(0),next(NULL){};//默認構造函數Node(int value):value(value),next(NULL){};//帶參數的構造函數 ~ Node(){cout<<"delete the node!!!"<<endl;delete next; // 刪除節點的指針域 }
}; int main(){Node *head , *curr; //定義頭結點指針和當前插入節點的指針head = new Node();//頭插法生成鏈表 for(int i = 0 ; i < 10 ; i++ ){curr = new Node(i);if(curr==NULL){cerr<<"內存分配失敗！"<<endl; }else{curr->next = head->next; //將當前節點指針指向之前頭結點指向的地方head->next = curr; //頭結點指向當前的節點cout<<"the value is : "<<curr->value<<endl;}}return 0;
}
the value is : 0
the value is : 1
the value is : 2
the value is : 3
the value is : 4
the value is : 5
the value is : 6
the value is : 7
the value is : 8
the value is : 9
那么鏈表該如何遍歷呢，剛開頭的時候就說，遍歷鏈表需要從頭到尾，訪問每一個元素，直到鏈表尾。也就是說不斷地訪問當前節點的next，直到NULL。下面是鏈表的遍歷輸出
#include <iostream>using namespace std;class Node{
public:int value;//鏈表節點的數據域Node* next;//用于指向下一個節點，是鏈表中的指針域Node():value(0),next(NULL){};//默認構造函數Node(int value):value(value),next(NULL){};//帶參數的構造函數 ~ Node(){cout<<"delete the node!!!"<<endl;delete next; // 刪除節點的指針域 }
}; int main(){Node *head , *curr;head = new Node();//頭插法生成鏈表 for(int i = 0 ; i < 10 ; i++ ){curr = new Node(i);if(curr==NULL){cerr<<"內存分配失敗！"<<endl; }else{curr->next = head->next;head->next = curr;
// cout<<"the value is : "<<curr->value<<endl;}}//鏈表的遍歷while(head){cout<<"current data is : "<<head->value<<endl;head = head->next;} return 0;
}
current data is : 0
current data is : 9
current data is : 8
current data is : 7
current data is : 6
current data is : 5
current data is : 4
current data is : 3
current data is : 2
current data is : 1
current data is : 0
3.鏈表的高階使用
鏈表相對于數組有個非常明顯的優點就是能以時間復雜度o(1)完成一個節點的插入或者刪除操作。
插入操作的原理很簡單，假設現在有三個節點，一個是當前節點curr，一個是當前節點的下一個節點，也就是后繼節點，假設為next，還有一個待插入的節點，假設為insert。插入操作就是讓當前節點的后繼節點指向insert節點，insert節點的后繼節點指向next節點。以下是示意圖
刪除操作的原理也是類似的，就是讓當前節點的后繼節點指向它后繼節點的后繼節點。示意圖如下
那么插入和刪除操作用代碼如何實現呢，我們還用原先的鏈表，先插入一個值為20的節點，輸出鏈表的全部元素。然后再刪除鏈表中這個值為20的元素，輸出元素的全部內容。代碼如下：
#include <iostream>
#include <deque>using namespace std;class Node{
public:int value;//鏈表節點的數據域Node* next;//用于指向下一個節點，是鏈表中的指針域Node():value(0),next(NULL){};//默認構造函數Node(int value):value(value),next(NULL){};//帶參數的構造函數 ~ Node(){cout<<"delete the node!!!"<<endl;delete next; // 刪除節點的指針域 }
}; int main(){Node *head , *curr;head = new Node();//頭插法生成鏈表 for(int i = 0 ; i < 10 ; i++ ){curr = new Node(i);if(curr==NULL){cerr<<"內存分配失敗！"<<endl; }else{curr->next = head->next;head->next = curr;}}//鏈表的插入curr = head;while(curr->value != 5){ //第一步:找到要插入的節點的前驅 curr = curr->next;}cout<<"curret node is : "<<curr->value<<endl;Node* insertNode = new Node(55); //創建要插入的節點 insertNode->next = curr->next; //第二步：將插入的節點的指針域指向當前節點的后繼 curr->next = insertNode; //第三步：將當前節點的指針指向插入的新節點//鏈表遍歷curr = head;while(curr){cout<<"the value is : "<<curr->value<<endl;curr = curr->next;}//鏈表元素的刪除//第一步找到要刪除的節點的前繼curr = head;while(curr->next->value != 55){curr = curr->next;}cout<<"curret node is : "<<curr->value<<endl;Node *tempNode;tempNode = curr->next; //第二步：保存下要刪除的節點 curr->next = tempNode->next; //第三步：將要刪除節點的前繼指針指向要刪除節點的后繼 delete tempNode; //第四步：刪除當前的節點//鏈表遍歷curr = head;while(curr){cout<<"the value is : "<<curr->value<<endl;curr = curr->next;}return 0;
}
curret node is : 5
the value is : 0
the value is : 9
the value is : 8
the value is : 7
the value is : 6
the value is : 5
the value is : 55
the value is : 4
the value is : 3
the value is : 2
the value is : 1
the value is : 0
curret node is : 5
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
delete the node!!!
the value is : 0
the value is : 9
the value is : 8
the value is : 7
the value is : 6
the value is : 5
the value is : 4
the value is : 3
the value is : 2
the value is : 1
the value is : 0
至于完整的鏈表，STL中有標準的庫，也有功能非常全面的API，只要我們知道內部的實現原理，調用這些API是非常簡單的事，用起來也會得心應手。
4.鏈表的其他操作
// 在末尾加入新的結點
void AddToTail(ListNode** pHead, int value){ListNode* pNew = new ListNode();pNew->val = value;pNew->next = nullptr;if (*pHead == nullptr){*pHead = pNew;}else{ListNode* pNode = *pHead;while(pNode->next != nullptr)pNode = pNode->next;pNode->next = pNew;}return;
}// 刪除某個值為value的結點
void RemoveNode(ListNode** pHead, int value){if(pHead == nullptr || *pHead == nullptr) return;ListNode* pToDeleted = nullptr;if((*pHead)->val == value){pToDeleted = *pHead;*pHead = (*pHead)->next;}else{ListNode* pNode = *pHead;while(pNode->next != nullptr && pNode->next->val != value)pNode = pNode->next;if(pNode->next != nullptr && pNode->next->val == value){pToDeleted = pNode->next;pNode->next = pNode->next->next;}}if(pToDeleted != nullptr){delete pToDeleted;pToDeleted = nullptr;}return;
}
鏈表容器list
1.list介紹
2. list使用
3. list與vector之間的區別
4.list例子代碼
#include <iostream>
#include <list>using namespace std;int main(){list<int> c1;list<int>::iterator c1_iter;//向鏈表的末尾加入元素 c1.push_back(1);c1.push_back(2);c1.push_back(3);//使用迭代器訪問鏈表 for(c1_iter = c1.begin();c1_iter != c1.end();c1_iter++){cout<<"data is : "<<*c1_iter<<endl;}//將鏈表反轉 c1.reverse();for(c1_iter = c1.begin();c1_iter != c1.end();c1_iter++){cout<<"reverse data is : "<<*c1_iter<<endl;}return 0;
}data is : 1
data is : 2
data is : 3
reverse data is : 3
reverse data is : 2
reverse data is : 1
#include <list>
#include <iostream> int main( )
{ using namespace std; list <int> c1; list <int>::iterator c1_Iter; c1.push_back( 20 ); c1.push_back( 10 ); c1.push_back( 30 ); cout << "Before sorting: c1 ="; for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ ) cout << " " << *c1_Iter; cout << endl; c1.sort( ); cout << "After sorting c1 ="; for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ ) cout << " " << *c1_Iter; cout << endl; c1.sort( greater<int>( ) ); cout << "After sorting with 'greater than' operation, c1 ="; for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ ) cout << " " << *c1_Iter; cout << endl;
}
Before sorting: c1 = 20 10 30
After sorting c1 = 10 20 30
After sorting with ‘greater than’ operation, c1 = 30 20 10
 - 房價預測案例（進階版）)
