數(shù)組和鏈表

C++的數(shù)組和鏈表分別是什么？分別有什么種類？它們都有什么特性？針對這些特征，使用情形是什么？

數(shù)組

什么是數(shù)組？

一個數(shù)組就像是一個變量，它可以存儲一組值，但是所有值都是相同的數(shù)據(jù)類型。 

一個int數(shù)組定義：int hours [6]

該數(shù)組類型為int型，即存儲元素是整數(shù)。

該數(shù)組的名稱是hours，方括號內(nèi)為數(shù)組的大小，它表示數(shù)組可以容納的元素或值的數(shù)量，必須是一個常量整數(shù)，其值大于0.（也可以是命名常數(shù)）

初始化數(shù)組：int hours[6] = { 1, 2, 3, 4, 5, 6}.

訪問數(shù)組元素

數(shù)組的元素可以根據(jù)下標(biāo)作為單獨的變量進行訪問和使用，C++中的下標(biāo)編號從0開始，數(shù)組中最后一個元素的下標(biāo)比數(shù)組中元素的總數(shù)少1.

如果采用全局定義的方式定義一個包含數(shù)值的數(shù)組，則默認情況下，所有元素初始化為0.但是，如果定義的是局部變量，則沒有默認的初始值。 

上面hours數(shù)組的每個元素在被下標(biāo)訪問時都可以用做int變量賦值：hours[0] = 20

可變長的動態(tài)數(shù)組：vector

vector是順序容器的一種，是可變長的動態(tài)數(shù)組。所以vector具備數(shù)組的性質(zhì)：在vector容器中，根據(jù)下標(biāo)隨機訪問某個元素的時間是常數(shù)，在尾部添加一個元素的時間大多數(shù)情況也是常數(shù)。

但是，在中間插入或刪除元素，需要移動多個元素，速度較慢，平均花費時間和容器中的元素個數(shù)成正比。

Vector基本用法

#include <vector>
using namespace std;
int main(){
	int a[5] = {1, 2, 3, 4, 5}
	vector <int> v(a, a+5); //將數(shù)組a的內(nèi)容放入v
	cout << v.end() - v.begin() << endl; //兩個迭代器相減，輸出：5
	v.insert(v.begin()+2, 13); // 在begin()+2 位置插入13， v變?yōu)椋?，2,13,3，4,5
	v.eraser(v.begin()+2); // 刪除位于begin()+2 位置上的元素，v變?yōu)椋?,2,3,4，5
	vector <int> v2(4, 100); // v2有4個元素，都是100
	v2.insert(v2.begin(), v.begin() + 1, v.begin() +3); // 將v的一段插入v2開頭，v2： 2,3,100,100,100,100
	v.erase(v.begin()+1, v.begin()+3); // 刪除v上的區(qū)間，即[2,3),v:1,4,5
	// 遍歷
	int sum = 0;
	// 迭代器遍歷
	for(std::vector<int>::iterator it = v.begin(); it !=v.end(); it++){
		sum += *it;
	}
	//索引遍歷(不適用list)
	for(int i = 0; i < v.size(); i++){
		sum += v[i];
	}
}

鏈表

什么是鏈表？

鏈表是由一系列連接在一起的結(jié)點構(gòu)成，其中的每一個結(jié)點都是一個數(shù)據(jù)結(jié)構(gòu)。

鏈表的結(jié)點是動態(tài)分配、使用和刪除的。相對于數(shù)組來說，鏈表可以容易地擴大或縮小，無需知道鏈表有多少個結(jié)點；相對于矢量（vector）來說，鏈表插入或刪除結(jié)點的速度更快，因為要將值插入vector的中間，需要將插入點后的所有元素都向后移動一個位置，而鏈表插入結(jié)點，其他結(jié)點不必移動。

鏈表的結(jié)構(gòu)：鏈表中的每個結(jié)點都包含一個或多個保存數(shù)據(jù)的成員，和一個后繼指針指向鏈表的下一個結(jié)點。單節(jié)點組成如下：

在c++中表示鏈表，需要有一個表示鏈表中單個結(jié)點的數(shù)據(jù)類型。

struct ListNode
{
	double value;  // 數(shù)據(jù)
	ListNode *next; // 指向另一個相同類型結(jié)點的指針
}

非空鏈表的第一個結(jié)點成為鏈表的頭。要訪問鏈表中的結(jié)點，需要有一個指向鏈表頭的指針。從鏈表頭開始，可以按照存儲在每個結(jié)點中的后繼指針訪問鏈表中的其余結(jié)點。最后一個結(jié)點的后繼指針被設(shè)置為nullptr。

已經(jīng)聲明一個數(shù)據(jù)類型來表示結(jié)點后，可定義一個初始為空的鏈表。即定義一個用作鏈表頭的指針并將其初始化為nullptr：ListNode *head = nullptr;

創(chuàng)建一個鏈表。其中包含一個結(jié)點，存儲值為12.5

head = new ListNode; //分配新結(jié)點
head->value = 12.5; 
head->next = nullptr; // 鏈表的結(jié)尾

在單向鏈表中，頭head指向最先節(jié)點的前一個，尾end指向最后節(jié)點，新加入一個點，即加在未加入結(jié)尾時的鏈表的結(jié)尾的后一個。

  1 - 5 - 2 - 9 - 8
h                 e
這是原來的鏈表(h=head,e=end) 
新讀入3,要把3加入鏈表的最后面
那么就要加在8的后面  
  1 - 5 - 2 - 9 - 8 -   3
h                 e   e->next
                       tmp
這樣子end->next就指向3,也就是tmp
因為end是指向point類型的指針
新加入3后我們發(fā)現(xiàn)end不在結(jié)尾上,那么我們要調(diào)整
即end=tmp
  1 - 5 - 2 - 9 - 8 - 3
h                     e

創(chuàng)建一個新結(jié)點，在其中存儲13.5的值，并將其作為鏈表中的第二個結(jié)點。

ListNode *secondPtr = new ListNode;
secondPtr->value = 13.5;
secondPtr->next = nullptr;
head->next = secondPtr; //第一個結(jié)點指向第二個

鏈表的操作

1.使用構(gòu)造函數(shù)初始化結(jié)點 ——結(jié)點在創(chuàng)建時可初始化

struct ListNode
{
	double value;
	ListNode *next;
	//構(gòu)造函數(shù)
	ListNode(double value1; ListNode *next1 = nullptr){
		value = value1;
		next = next1;
	}
};

2.創(chuàng)建鏈表——讀取文件中的值并將每個新讀取的值添加到已經(jīng)累積的值鏈表的開頭

ListNode *numberList = nullptr;
double number;
while(numberFile >> number){
	// 創(chuàng)建一個結(jié)點以保存該數(shù)字
	numberList = new ListNode(number, numberList);
};

3.遍歷鏈表——從鏈表頭開始，涉及整個鏈表，并在每個結(jié)點上執(zhí)行一些處理操作

ListNode *ptr = numberList; // 一個指針ptr指向鏈表的開頭
while(ptr != nullptr){
		cout << ptr->value; // 打印結(jié)點的值；
		ptr = ptr->next; // 移動到下一個結(jié)點
};

雙向鏈表（list）

list是順序容器的一種，是一個雙向鏈表。雙向鏈表的每個元素中都有一個指針指向后一個元素，一個指針指向前一個元素。

在list容器中，在已經(jīng)定位到要增刪元素的位置的情況下，增刪元素能在常數(shù)時間內(nèi)完成。如圖2所示，在ai和ai+1之間插入一個元素，只需要修改ai和ai+1中的指針即可。

但是list容器不支持根據(jù)下標(biāo)隨機存取元素。

list的成員函數(shù)

list的構(gòu)造函數(shù)和許多成員函數(shù)的用法都與vector類似，初此之外，還有獨特接口。（以下省略與vector相同的接口）

void push_front(const T &val); //在頭部添加元素
void pop_front(); //刪除頭部元素
void sort(); //排序
void remove(const T &val); // 刪除值為val的所有元素
void remove_if(bool (*pred)(const T &val)); // 刪除滿足條件的所有元素
void unique(); // 刪除連續(xù)的重復(fù)元素（只保留第一個）
void merge(list < T> &x); // 在自身有序的前提下，與另一個有序鏈表x合并，并保持有序。
void splice(iterator i, list < T> &x, iterator i); //在位置i前插入鏈表x中的一個結(jié)點（剪切操作）
void splice(iterator i, list < T> &x, iterator first, iterator last); // 在位置i前插入鏈表x中的區(qū)間[first, last)，并在鏈表x中刪除該區(qū)間。鏈表自身和鏈表x可以是同一個鏈表，只要i不在[first，last)中即可

哈希表

什么是哈希表？

散列圖（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值（Key value）而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

給定表M，存在函數(shù)f(key),對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵詞的記錄在表中的地址，則稱表M為哈希（Hash）表，函數(shù)f(key)為哈希(Hash)函數(shù)。

數(shù)據(jù)的哈希地址 = f(關(guān)鍵字key的值)

通俗解釋：哈希表是一種數(shù)據(jù)結(jié)構(gòu)，可以直接根據(jù)給定的key值計算出目標(biāo)位置。在工程中，哈希表結(jié)構(gòu)通常采用數(shù)組實現(xiàn)。

普通列表僅能通過下標(biāo)來獲取目標(biāo)位置的值，而哈希表可以根據(jù)給定的key計算得到目標(biāo)位置的值。

列表查找中，二分查找算法，復(fù)雜度為O(log2n),只能用于有序列表；普通無序列表只能采用遍歷查找，復(fù)雜度為O(n);而用哈希函數(shù)實現(xiàn)的哈希表，對任意元素查找速度始終是常數(shù)級別，即O(1).

哈希碰撞

一個哈希值會對應(yīng)多種值。即不同的key值，哈希函數(shù)結(jié)果一樣，都指向同一個value地址，出現(xiàn)重復(fù)。

對于哈希表而言，沖突只能盡可能地少，無法完全避免。通常用順序表存一堆鏈表來解決這個問題：

哈希表應(yīng)用場景

哈希表的優(yōu)點是可以通過關(guān)鍵值計算直接獲取目標(biāo)位置，對于海量數(shù)據(jù)的精確查找有顯著速度提升，理論上即使有無限的數(shù)據(jù)量，一個良好的哈希表依舊可以保持O(1)的查找速度。

在工程上，經(jīng)常用于通過名稱制定配置信息、通過關(guān)鍵詞傳遞參數(shù)、建立對象與對象的映射關(guān)系等?？偠灾?，所有使用鍵值對的地方，都用到了哈希表思想。

構(gòu)建哈希表

在構(gòu)建哈希表時，最重要的是哈希函數(shù)的設(shè)計。常用的哈希函數(shù)的構(gòu)造方法有6種：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法和隨機數(shù)法。

1.直接定址法：哈希函數(shù)為一次函數(shù)，即一下兩種形式：

?H(key) = key / ?H(key) = ?a * key + b

2.數(shù)字分析法：如果關(guān)鍵字由多位字符或數(shù)字組成，可以考慮抽取其中的2位或者多位作為該關(guān)鍵字對應(yīng)的哈希地址，在取法上盡量選擇變化較多的位，避免沖突發(fā)生。

3.平方取中：對關(guān)鍵字做平方操作，取中間的幾位作為哈希地址。適合關(guān)鍵字位數(shù)較短

4.折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。此方法適合關(guān)鍵字位數(shù)較多的情況。

5.除留余數(shù)法：若一直整個哈希表的最大長度m，可以取一個不大于m的數(shù)p，然后對該關(guān)鍵字key做取余運算：H(key) = key % p。此方法中，p的取值非常重要，由經(jīng)驗得p可以為不大于m的質(zhì)數(shù)或不包含小于20的質(zhì)因數(shù)的合數(shù)。

6.隨機數(shù)法：去關(guān)鍵字的一個隨機函數(shù)值作為它的哈希地址，即H(key) = random(key).適合關(guān)鍵字長度不等的情況。 

set和map都可以由哈希表和二叉搜索樹實現(xiàn)。

在C++STL中，哈希表對應(yīng)的容器是unordered_map，訪查插刪時間復(fù)雜度為O(1)，但內(nèi)部是無序的，額外空間復(fù)雜度高出許多。map對應(yīng)的數(shù)據(jù)結(jié)構(gòu)是紅黑樹，訪查插刪時間復(fù)雜度為O(logn),內(nèi)部是有序的。對于需要高效率查詢的情況，使用unordered_map容器，對內(nèi)存大小比較敏感或者數(shù)據(jù)要求有序的情況，可以用map容器。

哈希表基本使用

unordered_map的用法和map大同小異：

#include <iostream>
#include <unordered_map>
#include <string>
int main(int argc, char **argv){
	std::unordered_map<int, std::string> map;
	map.insert(std::make_pair(1, "Scale");
	map.insert(std::make_pair(2, "java");
	map.insert(std::make_pair(3, "python");
	map.insert(std::make_pair(6, "Erlang");
	map.insert(std::make_pair(13,"Haskell");
	
	std::unordered_map<int, std::string>::iterator it;
	if((it = map.find(6)) != map.end()){
		std::cout << it->second << std::endl;
	}
	return 0;
}

Leetcode對應(yīng)題目

前綴和

前綴和技巧：對應(yīng)題目：303、304、560（ 用到哈希表 ）

前綴和主要適用場景是：原始數(shù)組不會被修改的情況下，頻繁查詢某個區(qū)間的累加和。

差分數(shù)組

差分數(shù)組：對應(yīng)題目：370、1109、1094

差分數(shù)組主要適用場景：頻繁對原始數(shù)組某個區(qū)間的元素進行增減

滑動窗口

滑動窗口：對應(yīng)題目：76、567、438、3 

和子數(shù)組/子字符串相關(guān)的題目，很可能要考察滑動窗口，往這方面思考就行了

滑動窗口算法思路:

我們在字符串S中使用左右雙指針，初始化left = right = 0， 把索引左閉右開區(qū)間[left, right)稱為一個窗口；先不斷地增加right指針，擴大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）;（尋找可行解）此時，停止增加right，轉(zhuǎn)而不斷增加left指針縮小窗口[left， right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同時，每增加left，更新一次。（優(yōu)化可行解，尋找最優(yōu)解）重復(fù)2、3步，直到right到達字符串s的盡頭。

左右指針輪流前進，窗口大小增增減減，窗口不斷右滑。

關(guān)鍵問題：

• 1.當(dāng)right擴大窗口，即加入字符時，需要更新哪些數(shù)據(jù)?
• 2.什么條件下，窗口應(yīng)該暫停擴大，開始移動left縮小窗口？
• 3.當(dāng)移動left縮小窗口，移出字符時，應(yīng)該更新哪些數(shù)據(jù)？
• 4.我們要的結(jié)果應(yīng)該在擴大窗口還是縮小窗口時更新？

二分查找

二分查找對應(yīng)題目：704、34、875、1011

分析二分查找的一個技巧是:不要出現(xiàn)else，而是把所有情況用else if寫清楚，這樣可以清楚地展示所有細節(jié)。 另外需要聲明一下，計算mid時需要防止溢出，left + (right - left) / 2 和 (left + right) / 2 結(jié)果相同，但是有效防止了 left和right太大直接相加導(dǎo)致溢出。

什么問題可以運用二分搜索算法技巧？

首先，你要從題目中抽象出一個自變量x，一個關(guān)于x的函數(shù)f(x)，以及一個目標(biāo)值target。

同時，f(x)必須是在x上的單調(diào)函數(shù)；題目是讓你計算滿足約束條件f(x) == target時的x的值。

具體來說，想要用二分搜索算法解決問題，分為以下幾步：

• 1.確定x， f(x)， target分別是什么，并寫出函數(shù)f的代碼；
• 2.找到x的取值范圍作為二分搜索的搜索區(qū)間，初始化left和right變量
• 3.根據(jù)題目要求，確定應(yīng)該使用搜索左側(cè)還是右側(cè)的二分搜索算法，寫出解法代碼 

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論