為實(shí)習(xí)準(zhǔn)備的數(shù)據(jù)結(jié)構(gòu)（1）-- 詳盡數(shù)組篇（數(shù)據(jù)結(jié)構(gòu)含上機(jī)實(shí)訓(xùn)）

文章目錄

序言

C數(shù)組

什么是數(shù)組

數(shù)組初始化

訪問(wèn)數(shù)組元素

C++中沒(méi)有數(shù)組邊界檢查

細(xì)節(jié)決定成敗

傳遞數(shù)組給函數(shù)

STL::vector

vector 簡(jiǎn)介

vector 接口

Vector的數(shù)據(jù)結(jié)構(gòu)

序言

這不是，金三銀四嘛。外邊晃蕩了這么久，突然發(fā)現(xiàn)老本兒有點(diǎn)松動(dòng)了。

斌哥（秋西哥）在他的畢業(yè)致辭上說(shuō)：“一天不練，自己知道；兩天不練，同行知道；三天不練，觀眾知道。”

今晚我打開(kāi)LeetCode，看到以前寫過(guò)的一道題，想著寫個(gè)循環(huán)，突然發(fā)現(xiàn)我只會(huì)寫for i in XXX了，這時(shí)候我知道，問(wèn)題有點(diǎn)嚴(yán)重了。

第一篇不是指針，直到倒數(shù)第二篇也不會(huì)出指針，放心吧。因?yàn)橹羔槍?shí)在太玄妙了，得壓軸。

雖然標(biāo)題上寫的是數(shù)組，但是你確定不往下看看？我何時(shí)讓你們失望過(guò)呢？

（期間會(huì)重用一些以前寫過(guò)的，不過(guò)會(huì)把以前的刪掉）

剛看到一句話挺好玩的：

曾經(jīng)一位老師跟我說(shuō)“如果你在沒(méi)有努力鉆研的情況下靈光一閃就有了一個(gè)絕妙的想法，多半是讀書少。” 共勉

本人大三大數(shù)據(jù)學(xué)生一枚，準(zhǔn)備去投一些暑期實(shí)習(xí)，有興趣可以找我一起學(xué)哦。

C數(shù)組

什么是數(shù)組

所謂數(shù)組，就是相同數(shù)據(jù)類型的元素按一定順序排列的集合，就是把有限個(gè)類型相同的變量用一個(gè)名字命名，然后用編號(hào)區(qū)分他們的變量的集合，這個(gè)名字稱為數(shù)組名，編號(hào)稱為下標(biāo)。組成數(shù)組的各個(gè)變量稱為數(shù)組的分量，也稱為數(shù)組的元素，有時(shí)也稱為下標(biāo)變量。數(shù)組是在程序設(shè)計(jì)中，為了處理方便， 把具有相同類型的若干變量按有序的形式組織起來(lái)的一種形式。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。

數(shù)組初始化

一維數(shù)組初始化： : 標(biāo)準(zhǔn)方式一： int value[100]; // value[i]的值不定，沒(méi)有初始化 : 標(biāo)準(zhǔn)方式二： int value[100] = {1,2}; // value[0]和value[1]的值分別為1和2，而沒(méi)有定義的value[i>1] : // 則初始化為0 : 指針?lè)绞剑?int* value = new int[n]; // 未初始化 : delete []value; // 一定不能忘了刪除數(shù)組空間 : : 二維數(shù)組初始化： : 標(biāo)準(zhǔn)方式一： int value[9][9]; // value[i][j]的值不定，沒(méi)有初始化 : 標(biāo)準(zhǔn)方式二： int value[9][9] = {{1,1},{2}}； //value[0][0,1]和value[1][0]的值初始化，其他初始化為0 : 指針?lè)绞揭唬?int (*value)[n] = new int[m][n]; : delete []value; // n必須為常量，調(diào)用直觀。未初始化 : 指針?lè)绞蕉?int** value = new int* [m]; : for(i) value[i] = new int[n]; : for(i) delete []value[i]; : delete []value; // 多次析構(gòu)，存儲(chǔ)麻煩，未初始化 : 指針?lè)绞饺?int * value = new int[3][4]; // 數(shù)組的存儲(chǔ)是按行存儲(chǔ)的 : delete []value; // 一定要進(jìn)行內(nèi)存釋放，否則會(huì)造成內(nèi)存泄露 : : 多維數(shù)組初始化： : 指針?lè)绞剑?int * value = new int[m][3][4]; // 只有第一維可以是變量，其他幾維必須都是常量，否則會(huì)報(bào)錯(cuò) : delete []value; // 一定要進(jìn)行內(nèi)存釋放，否則會(huì)造成內(nèi)存泄露

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

訪問(wèn)數(shù)組元素

即使整個(gè)數(shù)組只有一個(gè)名稱，這些元素也可以作為單獨(dú)的變量進(jìn)行訪問(wèn)和使用。

之所以可以實(shí)現(xiàn)這一點(diǎn)，是因?yàn)槊總€(gè)元素都分配有一個(gè)稱為下標(biāo)的數(shù)字。下標(biāo)用作一個(gè)索引來(lái)精確定位一個(gè)數(shù)組中的特定元素，第一個(gè)元素分配下標(biāo) 0，第二個(gè)元素分配下標(biāo) 1，依此類推。

C++中沒(méi)有數(shù)組邊界檢查

C++ 不執(zhí)行數(shù)組邊界檢查。這意味著程序員編寫的程序，可能會(huì)意外地允許一個(gè)數(shù)組的下標(biāo)越界。

究竟發(fā)生什么取決于系統(tǒng)如何管理內(nèi)存。在許多系統(tǒng)上，它會(huì)導(dǎo)致附近其他變量的內(nèi)容被覆蓋，失去正確的值。在某些系統(tǒng)上甚至?xí)?dǎo)致死機(jī)。

下面程序演示了當(dāng)數(shù)組下標(biāo)越界時(shí)，程序編寫者的計(jì)算機(jī)上發(fā)生了什么。它證明存儲(chǔ)在一個(gè)數(shù)組中的數(shù)據(jù)會(huì)覆蓋另一個(gè)數(shù)組中的數(shù)據(jù)：

#include using namespace std; int main() { const int SIZE = 3; int A [SIZE] = {1, 1, 1}; int B[SIZE]; cout << "Here are the original numbers in 3-element array A: "; for (int count = 0; count < 3; count++) cout << A[count] << " "; cout << "\n\nNow I'm storing 7 numbers in 3-element array B."; for (int count = 0; count < 7; count++) B[count] =5; cout << "\nlf you see this message, the computer did not crash."; cout << "\n\nHere are the 7 numbers in array B : "; for (int count = 0; count < 7; count++) cout << B [count] << " "; cout << "\nHere are the numbers now in array A: "; for (int count = 0; count < 3; count ++) cout << A [count] <<" "; cout << "\n\nArray A's values were overwritten by \n" << "the values that did not fit in Array B. \n"; return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

運(yùn)行結(jié)果：

Here are the original numbers in 3-element array A: 1 1 1 Now I'm storing 7 numbers in 3-element array B. lf you see this message, the computer did not crash. Here are the 7 numbers in array B : 5 5 5 5 5 5 5 Here are the numbers now in array A: 5 5 5 Array A's values were overwritten by the values that did not fit in Array B.

1

2

3

4

5

6

7

8

9

10

解釋：

其實(shí)我也不知道為什么不把這個(gè)問(wèn)題給辦了，所以就參考我前邊那句話吧，我讀書少，不要問(wèn)我。

細(xì)節(jié)決定成敗

直接初始化字符數(shù)組char是特殊的，這種初始化需要一個(gè)null作為結(jié)尾的。如下：

char a1[] = {'h', 'e', 'l', 'l', 'o'}; // 初始化，沒(méi)有 null char a2[] = {'h', 'e', 'l', 'l', 'o', '

char a1[] = {'h', 'e', 'l', 'l', 'o'}; // 初始化，沒(méi)有 null char a2[] = {'h', 'e', 'l', 'l', 'o', '\0'}; // 初始化，明確有 null char a3[] = "hello"; // null 終止符自動(dòng)添加 const char a4[6] = "hello"; // 報(bào)錯(cuò)，沒(méi)有 null 的位置

'}; // 初始化，明確有 null char a3[] = "hello"; // null 終止符自動(dòng)添加 const char a4[6] = "hello"; // 報(bào)錯(cuò)，沒(méi)有 null 的位置

1

2

3

4

數(shù)組的大小是固定的，不能額外增加元素，當(dāng)想定義不固定大小的字符時(shí)，使用vector

vector vec; // 創(chuàng)建向量用于存儲(chǔ)整型數(shù)據(jù) int m; // 顯示vec初始大小 cout << "vector size = " << vec.size() << endl; // 向向量vec追加5個(gè)整數(shù)值 for(int m = 0; m < 5; m++) vec.push_back(m); // 顯示追加后vec的大小 cout << "追加后的vector size = " << vec.size() << endl;

1

2

3

4

5

6

7

8

9

數(shù)組初始化時(shí)可以用聚合方法，但是賦值時(shí)候不可以用聚合方法。舉例如下：

int array[] = {5,10,20,40}; // 合法 int array[]; int main() { array[] = {5,10,20,40}; // 不合法 return 0; }

1

2

3

4

5

6

7

8

傳遞數(shù)組給函數(shù)

C++ 中，可以通過(guò)指定不帶索引的數(shù)組名來(lái)傳遞一個(gè)指向數(shù)組的指針。

C++ 傳數(shù)組給一個(gè)函數(shù)，數(shù)組類型自動(dòng)轉(zhuǎn)換為指針類型，因而傳的實(shí)際是地址。

如果想要在函數(shù)中傳遞一個(gè)一維數(shù)組作為參數(shù)，可以用下面三種方式來(lái)聲明函數(shù)形式參數(shù)，這三種聲明方式的結(jié)果是一樣的，因?yàn)槊糠N方式都會(huì)告訴編譯器將要接收一個(gè)整型指針。同樣地，也可以傳遞一個(gè)多維數(shù)組作為形式參數(shù)。

//形參是一個(gè)指針： void myFunction(int *param) { ··· } //形參是一個(gè)已定義大小的數(shù)組： void myFunction(int param[10]) { ··· } //形參是一個(gè)已定義大小的數(shù)組： void myFunction(int param[]) { ··· }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

STL::vector

vector 簡(jiǎn)介

vector可用于代替C中的數(shù)組，或者M(jìn)FC中的CArray，從許多說(shuō)明文檔或者網(wǎng)上評(píng)論，一般一致認(rèn)為應(yīng)該多用vector，因?yàn)樗男矢撸揖邆浜芎玫漠惓０踩浴６襳ector是STL推薦使用的默認(rèn)容器，除非你知道你有特殊需要，使用vector不能滿足你的需求，例如需要容器在head和tail高效的插入和刪除，或者在任何位置高效的刪除和插入操作，那么你可能使用deque或者list更加合適。

vector是連續(xù)內(nèi)存容器，換句話說(shuō)，標(biāo)準(zhǔn)要求所有標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)的時(shí)候，vector中的元素的內(nèi)存必須是連續(xù)的。所以對(duì)于插入和刪除的時(shí)間復(fù)雜度是很高的，因?yàn)閯h除或者插入的時(shí)候，需要元素的移動(dòng)，即元素復(fù)制拷貝。

vector的內(nèi)部實(shí)現(xiàn)一般需要用到placement new ，所以效率很高，因?yàn)楹芏嗟臅r(shí)候，只要我們是使用得到，就可以省去很多的內(nèi)存分配開(kāi)銷。而且vector的使用，元素可以沒(méi)有默認(rèn)的構(gòu)造函數(shù)，但是需要拷貝構(gòu)造函數(shù)的存在，這是使用CArray所無(wú)法實(shí)現(xiàn)的。

vector 接口

#include //這是頭

1

創(chuàng)建

vector test; //初始化一個(gè)Vector實(shí)例，用于存放int型數(shù)據(jù)，實(shí)例名字叫test vector test2 = test; //以test1為標(biāo)準(zhǔn)創(chuàng)建test2

1

2

3

再看一個(gè)vectortest3(10);

創(chuàng)建一個(gè)vector容器，大小為10，內(nèi)容默認(rèn)置空

不是很建議這種做法啊，往里面插成段的值的時(shí)候只能插入第一個(gè)，后面就無(wú)法插入了。

再說(shuō)了，你不用自己分配空間，STL都給你安排的好好的。

當(dāng)然，初始化方式千千萬(wàn)，放多了反而讓人眼花繚亂，會(huì)基本的最實(shí)用的夠了。

插入元素

test.insert(test.begin()+i,a); //在第i個(gè)元素前插入a test.insert(test.begin()+i,te2.begin(),te2.end()); //插入一段相同數(shù)據(jù)類型數(shù)據(jù)，第一個(gè)參數(shù)放插入位置（指針/迭代器形式），第二三個(gè)參數(shù)放待插入元素起始位置 test.push_back(a); //往尾部插入

1

2

3

4

5

6

刪除元素

test.erase(test.begin()); test.erase(test.begin(),test.begin()+5);//刪除區(qū)間(第一個(gè)元素到第五個(gè)元素) test.clear(); //清空 test.pop_back(); //刪除尾部元素

1

2

3

4

5

6

刪除呢，還有個(gè)比較靈活的方式：

test.erase(it); //這個(gè)it是迭代器

1

關(guān)于刪除有一個(gè)必須·要注意的點(diǎn)：在foreach的時(shí)候進(jìn)行刪除操作，需要注意：

for(iter = v1.begin(); iter != v1.end(); ++iter) { if(404 == *iter) v1.erase(iter); } 運(yùn)行后報(bào)錯(cuò)

1

2

3

4

5

6

erase()被調(diào)用后iter就失效了，即成為了一個(gè)野指針，下次循環(huán)訪問(wèn)到一個(gè)野指針肯定會(huì)拋異常。

解決辦法是：

重新為iter進(jìn)行賦值

for(iter = v1.begin(); iter != v1.end(); ++iter) { if(404 == *iter) { iter = v1.erase(iter); //返回刪除元素后面一個(gè)元素 iter–; //刪除元素前面的一個(gè)元素 } }

1

2

3

4

5

6

7

8

遍歷元素

當(dāng)然，你可以使用數(shù)組下標(biāo)形式訪問(wèn)元素，因?yàn)関ector重載了 [] 操作，不過(guò)不建議。雖然是很方便，但是有諸多限制，要是隨便就任你操作數(shù)據(jù)，那人家封裝起來(lái)干什么？

我們應(yīng)該養(yǎng)成使用下面這種迭代器訪問(wèn)的方式。

vector::iterator it; //初始化一個(gè)vector類型的迭代器 for(it = test.begin();it!=test.end();it++) //從頭遍歷到尾 { cout<<*it<

1

2

3

4

5

關(guān)于迭代器還需要知道的是：vector的迭代器支持前后向，及重載了 +，—，++，-- 操作。

還有一個(gè)叫at()的函數(shù)，這個(gè)好用。

test.at(2); //用這個(gè)比直接用下標(biāo)要好的地方在于它會(huì)檢測(cè)越界

1

（明面上是這么說(shuō)啊，其實(shí)我自己寫代碼也喜歡用下標(biāo)定位）

頭尾指針

這四個(gè)函數(shù)的區(qū)別要清楚：begin()、end()、front()、back()。我喜歡稱它們?yōu)轭^尾指針。

我也不知道為什么有人要就這些區(qū)別長(zhǎng)篇大論。

begin()：指向容器的第一個(gè)元素的地址。 front()：指向容器的第一個(gè)元素的值。 end()：和begin()配套 back()：和front()配套

1

2

3

4

容器容量

test.size(); //容器已存入數(shù)據(jù)量 test.capacity(); //容器還能存多少數(shù)據(jù)量

1

2

其實(shí)不用擔(dān)心容器不夠大，容量要滿的時(shí)候它會(huì)自己擴(kuò)容。

排序

#include /*test.*/sort(test.begin(),test.end()); //從頭到尾，默認(rèn)從小到大排序 這里要非常注意，前面那個(gè)test. 被我注釋掉了，因?yàn)閟ort是屬于算法范疇，不是容器的類方法。 //一般排序都是要自定義排序的： bool Comp(const int &a,const int &b) { return a>b; } sort(test.begin(),test.end(),Comp); //這樣就降序排序。

1

2

3

4

5

6

7

8

9

10

其他

swap(test,test2); //交換test和test2中的數(shù)據(jù) test.resize(20); //重置大小 reverse(test); //元素翻轉(zhuǎn)

1

2

3

4

5

如果要問(wèn)為什么沒(méi)有 “修改數(shù)據(jù)的部分”，參見(jiàn)第四點(diǎn)“遍歷數(shù)據(jù)”。

10、unique()函數(shù)

這個(gè)函數(shù)用來(lái)清理容器中的重復(fù)項(xiàng)，但前提是容器經(jīng)過(guò)排序了。

而且，它不提供刪除操作，只是把重復(fù)項(xiàng)移到容器后面的部分，所以直接size()的話大小是不會(huì)變的。

如果要清理重復(fù)項(xiàng)，這樣：nums.erase(unique(nums.begin(),nums.end()),nums.end());

最后再提一下兩個(gè)頭文件：

#include //vector類相關(guān) #include //容器算法

1

2

vector的元素不僅僅可以是int,double,string,還可以是結(jié)構(gòu)體，但是要注意：結(jié)構(gòu)體要定義為全局的，否則會(huì)出錯(cuò)。

特別注意：

使用vector需要注意以下幾點(diǎn)：

1、如果你要表示的向量長(zhǎng)度較長(zhǎng)（需要為向量?jī)?nèi)部保存很多數(shù)），容易導(dǎo)致內(nèi)存泄漏，而且效率會(huì)很低；

2、Vector作為函數(shù)的參數(shù)或者返回值時(shí)，需要注意它的寫法：

double Distance(vector&a, vector&b) 其中的“&”絕對(duì)不能少！！

Vector的數(shù)據(jù)結(jié)構(gòu)

所謂動(dòng)態(tài)增添大小，并不是在原有空間之后再開(kāi)辟空間，顯然那也不太現(xiàn)實(shí)。

而是以原大小的兩倍大小尋找一塊新空間，將內(nèi)容真實(shí)的拷貝過(guò)去，然后釋放原空間。

不過(guò)就算刪除元素過(guò)半也不會(huì)將內(nèi)存放出來(lái)。

但是，需要牢記的一點(diǎn)是：對(duì)于Vector的一切操作，一旦引起空間的重新分配，那么指向原有空間的迭代器將會(huì)全部失效。

關(guān)于這點(diǎn)，我也做了一個(gè)測(cè)試代碼：

可測(cè)可不測(cè)，結(jié)果我都注釋好了

#include #include using namespace std; int main() { vector vec1; //vector::iterator it1 = vec1.begin(); //放這里試試 vec1.push_back(1); cout<<"left size :"<::iterator it1 = vec1.begin(); //放這里試試 vec1.push_back(3); cout<<"left size :"<::iterator it1 = vec1.begin(); //這個(gè)循環(huán)用于在6之后插入4 while (it1 != vec1.end()) { if (3 == *it1) { vec1.insert(it1+1, 4); cout<<"insert:"<<*it1<::iterator it2 = vec1.begin() ; while (it2 != vec1.end()) { if (3 == *it2) { //it2 =vec1.erase(it2); vec1.erase(it2); //這里有沒(méi)有都一樣，都指向刪除之后的那個(gè)位置 cout<<"delete:"<<*it2<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。