第6章順序表與vector類2025/6/171順序表的特點(diǎn)

順序表的創(chuàng)建與常用函數(shù)順序表與最長遞增子數(shù)組順序表與篩選法順序表與全排列順序表與組合順序表與記錄6.1順序表的特點(diǎn)2025/6/172順序表也是線性表的一種具體體現(xiàn)，順序表節(jié)點(diǎn)形成的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)、節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)，即節(jié)點(diǎn)的物理地址是依次相鄰的。2025/6/1736.1順序表的特點(diǎn)順序表使用數(shù)組來實(shí)現(xiàn)，順序表的節(jié)點(diǎn)的物理地址是依次相鄰的，因此可以隨機(jī)訪問任何一個(gè)節(jié)點(diǎn)，不必從頭節(jié)點(diǎn)計(jì)數(shù)查找其它節(jié)點(diǎn)。1查詢節(jié)點(diǎn)

2025/6/1746.1順序表的特點(diǎn)和鏈表不同，順序表沒有單獨(dú)添加和刪除頭節(jié)點(diǎn)的操作，但是有單獨(dú)添加和刪除尾節(jié)點(diǎn)的操作。2添加節(jié)點(diǎn)

2025/6/1756.1順序表的特點(diǎn)

3刪除節(jié)點(diǎn)

6.2順序表的創(chuàng)建與常用函數(shù)2025/6/176std::vector是C++標(biāo)準(zhǔn)模板庫（StandardTemplateLibrary,STL）中的模板類，用于實(shí)現(xiàn)順序表（也稱動(dòng)態(tài)數(shù)組）數(shù)據(jù)結(jié)構(gòu)（也稱順序表是STL的容器之一）。稱std::vector類的實(shí)例（對(duì)象）為順序表（或向量），其中的節(jié)點(diǎn)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)。2025/6/1776.2順序表的創(chuàng)建與常用函數(shù)1.創(chuàng)建空順序表或具有初始容量的順序表。使用std::vectort類創(chuàng)建順序表時(shí)，必須要指定模板類中的參數(shù)類型的具體類型，類型是可以是C++允許的數(shù)據(jù)類型，比如int、float、char和類等，即指定順序表中節(jié)點(diǎn)里的數(shù)據(jù)的類型。例如，指定順序表arrList的節(jié)點(diǎn)中的數(shù)據(jù)的類型是std::string類型：std::vector<str::string>arrList;2025/6/1786.2順序表的創(chuàng)建與常用函數(shù)2.用已有順序表創(chuàng)建順序表也可以用其它相同數(shù)據(jù)類型的集合中的節(jié)點(diǎn)，例如使用arryList中的節(jié)點(diǎn)創(chuàng)建一個(gè)新順序表arrListNew：std::vector<std:string>arrListNew(arrlist);順序表arrlistNew的節(jié)點(diǎn)和arrlist的相同。順序表arrListNew修改了節(jié)點(diǎn)不會(huì)影響arrList的節(jié)點(diǎn)；順序表arrList修改了節(jié)點(diǎn)也不會(huì)影響arrListNew的節(jié)點(diǎn)。2025/6/1796.2順序表的創(chuàng)建與常用函數(shù)3.用數(shù)組或鏈表創(chuàng)建鏈表

2025/6/17106.2順序表的創(chuàng)建與常用函數(shù)4.順序表的初始化5.改變順序表的容量2025/6/17116.2順序表的創(chuàng)建與常用函數(shù)6.隨機(jī)訪問

順序表使用數(shù)組來實(shí)現(xiàn)，順序表的節(jié)點(diǎn)的物理地址是依次相鄰的，因此可以隨機(jī)訪問（randomaccess）任何一個(gè)節(jié)點(diǎn)（時(shí)間復(fù)雜度是O(1)）。std::vector提供了隨機(jī)訪問順序表節(jié)點(diǎn)的函數(shù)，例如對(duì)于順序表vectorList，vectorList.at(index)訪問vectorList的第index節(jié)點(diǎn)，順序表也可以使用下標(biāo)運(yùn)算“[]”訪問vectorList的第index節(jié)點(diǎn),例如vectorList[index]。使用at(index)函數(shù)和下標(biāo)運(yùn)算“[]”訪問index節(jié)點(diǎn)的區(qū)別是前者會(huì)檢查index是否越界，后者不檢index是否越界。2025/6/17126.2順序表的創(chuàng)建與常用函數(shù)7.運(yùn)算符重載如果順序表數(shù)據(jù)是對(duì)象，那么創(chuàng)建對(duì)象的類需要重載“==”（等于）、“>”（大于）、“<”（小于）運(yùn)算符，以便有關(guān)的函數(shù)查找順序表中的數(shù)據(jù)或比較順序表之間的大小關(guān)系（有關(guān)運(yùn)算符重載可參見附錄A）。8.和鏈表類似的函數(shù)std::vector順序表有和std::list鏈表類似的函數(shù)：began()、end（）、front()、back()、push_back()、pop_back()、insert()、erase(),clear()、empty()、swap()、size()。在后續(xù)例中會(huì)直接使用這些函數(shù)，不再列出這些函數(shù)的細(xì)節(jié)說明。2025/6/17136.2順序表的創(chuàng)建與常用函數(shù)例子1創(chuàng)建順序表ch6_1.cppch6_1.cpp的main()函數(shù)中首先創(chuàng)建并初始化順序表arrList，然后順序表arrList添加3個(gè)節(jié)點(diǎn).再用arrList中的節(jié)點(diǎn)創(chuàng)建順序表arrListNew。修改arrListNew的節(jié)點(diǎn)并不影響arrList的節(jié)點(diǎn).2025/6/17146.2順序表的創(chuàng)建與常用函數(shù)例子2比較順序表與鏈表的耗時(shí)ch6_2.cppch6_2.cpp中比較了順序表使用at(intindex)函數(shù)訪問節(jié)點(diǎn)和鏈表使用std::next()函數(shù)訪問節(jié)點(diǎn)的運(yùn)行耗時(shí)，可以看出順序表的耗時(shí)明顯小于鏈表的耗時(shí).6.3順序表與最長遞增子數(shù)組2025/6/1715順序表也稱動(dòng)態(tài)數(shù)組,比通常的（靜態(tài)）數(shù)組有更大的靈活性，例如動(dòng)態(tài)數(shù)組可以添加、刪除節(jié)點(diǎn)，因此在某些實(shí)際問題中使用動(dòng)態(tài)數(shù)組比使用通常的數(shù)組能更加方便地解決問題。2025/6/17166.3

順序表與最長遞增子數(shù)組例子3求最長遞增子數(shù)組ch6_3.cppsub_arr.cppsub_arr.cpp中的maxLengthSubarray(std::vector<int>arr)函數(shù)返回順序表arr的最長遞增子順序表。6.4順序表與篩選法2025/6/1717篩法的算法從2開始：2是素?cái)?shù)，把素?cái)?shù)2保存，然后把2后面所有能被2整除的數(shù)都劃去。數(shù)字2后面第1個(gè)沒劃去的數(shù)是素?cái)?shù)3，把素?cái)?shù)3保存，然后再把3后面所有能被3整除的數(shù)都劃去。3后面第1個(gè)沒劃去的數(shù)是素?cái)?shù)5，把素?cái)?shù)5保存，然后再把5后面所有能被5整除的數(shù)都劃去?！凑蘸Y法，每次留下的數(shù)字中的第1個(gè)數(shù)字一定是素?cái)?shù)，如此繼續(xù)進(jìn)行，就會(huì)把不超過N的全部合數(shù)都篩掉，保存的就是不超過N的全部素?cái)?shù)。2025/6/17186.4順序表與篩選法例子4用篩選法求素?cái)?shù)prime_filter.cppch6_4.cpp

6.5順序表與全排列2025/6/1719

2025/6/17206.5順序表與全排列例子5遞歸與全排列full_fermutatio.cppch6_5.cpp

1.遞歸法求全排列2025/6/17216.5順序表與全排列例子6九宮格填數(shù)字ch6_6.cpp2數(shù)字填空

full_fermutatio.cpp2025/6/17226.5順序表與全排列3迭代法求全排列對(duì)于字符1，2，3，5，6，7，8組成的全排列，按字典序，最小的是12345678，最大的是87654321。從最小的全排列（或最大的全排列）開始，按著字典序依次尋找下一個(gè)全排列，一直到找到最大的（最小的）全排列為止，就可以給出全部的全排列。這里，我們通過找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。①尋找正序相鄰對(duì)在全排列的相鄰對(duì)中找到最后一對(duì)“正序相鄰對(duì)”（小的在前、大的在后）。2025/6/17236.5順序表與全排列●迭代法求全排列這里，我們通過找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。②尋找最小字符

對(duì)于：58，找到的字符是6。字符6以后的字符（假如有的話）都比字符5小2025/6/17246.5順序表與全排列這里，我們通過找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。③最小字符與pairLast的首字符互換

2025/6/17256.5順序表與全排列34587621的下一個(gè)全排列：34612578。④反轉(zhuǎn)子序列

例子7迭代法求全排列dictionary.cppch6_7.cpp6.6順序表與組合2025/6/1726

2025/6/17276.6順序表與組合1迭代求組合和排列不同，[1,2,3]和[1,3,2]是不同的排列，是相同的組合。因此，表示組合時(shí)可以讓組合里的數(shù)字都是升序的。

該組合中的每個(gè)數(shù)，按順序存放到一個(gè)順序表list中。

得到下一個(gè)組合[1,4,5]2025/6/17286.6順序表與組合1迭代求組合例子8用迭代法求組合combination.cppch6_8.cpp

2025/6/17296.6順序表與組合2遞歸求組合例子9用遞歸求組合recurrence_com.cppch6_9.cpp參考遞歸求楊輝三角形（見第3章例子9），可以寫出遞歸求組合的算法（作者反復(fù)畫遞歸圖，找出了遞歸的規(guī)律.

2025/6/17306.6順序表與組合3組合與砝碼稱重例子10用天平秤重量weight.cppch6_10.cpp有n多個(gè)重量不同的砝碼各一枚，比如，4個(gè)重量不同的砝碼：1克，3克，5克和8克。能稱出多少種重量。有些組合可能稱出相同的重量，比如用一個(gè)5克的砝碼可以稱出5克重量，用1個(gè)2克砝碼和1個(gè)3克砝碼，同樣也可以稱出5克重量。遍歷全部的組合，發(fā)現(xiàn)能稱出相同的重量的組合（即方案）時(shí)，保留一個(gè)即可。

如果允許砝碼放在天秤的兩端（允許放在被稱重的物體一端），那么就把另一端（被稱重的物體一端）的砝碼拿回到放置砝碼的一端、并變成“負(fù)碼”（重量是負(fù)數(shù)），就將問題轉(zhuǎn)化為砝碼只放天秤一端的情況。6.7順序表與記錄2025/6/1731有時(shí)候，需要將一維數(shù)組，比如一個(gè)記錄