怎樣將順序表和鏈表合并成一個(gè)有序表？這個(gè)問(wèn)題最麻煩之處在于內(nèi)存的分配。你用C還是C ?C 的話(huà)，單鏈表用list結(jié)構(gòu)，順序表用vector結(jié)構(gòu)，假設(shè)二者分別為list<int> a和vec

怎樣將順序表和鏈表合并成一個(gè)有序表？

這個(gè)問(wèn)題最麻煩之處在于內(nèi)存的分配。你用C還是C ?

C 的話(huà)，單鏈表用list結(jié)構(gòu)，順序表用vector結(jié)構(gòu)，假設(shè)二者分別為list<int> a和vector<int> b。后面就容易了，

while (!a.empty())

{

b.push_back(a.front())

a.pop_front()

}

順序表的內(nèi)存分配問(wèn)題STL會(huì)自行解決的。

如果是C就有點(diǎn)辛苦了，比較直觀的做法是先把鏈表從頭到尾走一遍，算出它的長(zhǎng)度，然后分配一個(gè)空間，其長(zhǎng)度等于單鏈表和順序表長(zhǎng)度之和，再把兩個(gè)表的內(nèi)容拷進(jìn)去。稍微優(yōu)化一點(diǎn)的做法是先猜測(cè)一個(gè)適當(dāng)?shù)逆湵淼拈L(zhǎng)度，然后以此來(lái)分配內(nèi)存；如果后來(lái)發(fā)現(xiàn)鏈表過(guò)長(zhǎng)，那么把猜測(cè)的長(zhǎng)度加倍，重新分配內(nèi)存。