對(duì)于向量或者數(shù)組這種數(shù)據(jù)結(jié)構(gòu)摄杂，除了常常用到的增坝咐，改，刪析恢，除元素之外墨坚，還會(huì)涉及到一些其他操作，特此做以下總結(jié)：
參考教材：《數(shù)據(jù)結(jié)構(gòu) C++語(yǔ)言版》鄧俊輝著
為了算法實(shí)現(xiàn)映挂，定義一個(gè)模板類(lèi)如下所示;
template <typename T>
class MyVector
{
private:
int my_size; //向量當(dāng)前大小
T *elem; //存放數(shù)據(jù)
public:
void uniquify(); //去重復(fù)元素
int binSearchA(T const& e,int lo,int hi) const;
int binSearchB(T const &e, int lo, int hi) const;
int binSearchC(T const &e, int lo, int hi) const;
void bubbleSort(int lo, int hi);
bool bubble(int lo, int hi);
};
1. 去重復(fù)元素
對(duì)于一個(gè)向量或者數(shù)組來(lái)說(shuō)泽篮，可能存在者若干重復(fù)元素，對(duì)于一個(gè)有序向量柑船，重復(fù)元素的去除帽撑，可以用以下C++代碼實(shí)現(xiàn)：
template <typename T>
void MyVector<T>::uniquify()
{
int i,j=0 //用i記錄不重復(fù)元素，用j遍歷當(dāng)前向量
while(++j<my_size)
{
if(elme[j]!=elem[i])
{
elem[++i] = elem[j];
}
my_size = i;
i++;
}
}
如以上代碼所示鞍时，去除一個(gè)有序向量的重復(fù)元素亏拉，其過(guò)程如下圖所示：
2. 二分查找算法及改進(jìn)
- A版算法
對(duì)于向量中某一元素的查找，除了順序查找之外逆巍，對(duì)于有序向量及塘，可以使用二分查找，常規(guī)二分查找的算法實(shí)現(xiàn)如下所示：
template <typename T>
int MyVector<T>::binSearchA(const T &e, int lo, int hi) const //在區(qū)間查找
{
while(lo<hi)
{
int mi = (lo + hi) >> 1;
if(e<elem[mi])
{
hi = mi;
}
if(e>elem[mi])
{
lo = mi;
}else
{
return mi;
}
}
return -1;
}
二分查找算法A版的實(shí)現(xiàn)可以由上代碼所示锐极，經(jīng)過(guò)多次比較笙僚，直到找到元素，返回其下標(biāo)溪烤。
- B版算法
template <typename T>
int MyVector<T>::binSearchB(const T &e, int lo, int hi) const
{
while(1<hi-lo)
{
int mi = (lo + hi) >> 1;
(e < elem[mi]) ? hi = mi : lo = mi;
}
return (e = elme[mi]?lo:-1)
}
與二分查找A版算法相比味咳，該算法只經(jīng)過(guò)一次比較庇勃，不斷通過(guò)一次比較檬嘀，更新左右區(qū)間，找到對(duì)應(yīng)元素之后责嚷，也不返回鸳兽，直到比較的區(qū)間縮小至1時(shí)，停止比較罕拂。與上一版算法相比揍异，盡管最好情況下的算法性能有所下降全陨，但是最壞情況下的算法性能有所上升。
- C版算法
A版算法與C版算法雖然能夠成功的查找到元素的位置衷掷，但是仍然存在其局限性辱姨，當(dāng)存在重復(fù)元素時(shí)，按照某種優(yōu)先級(jí)會(huì)返會(huì)較為靠后的元素戚嗅，改進(jìn)后的C版查找算法如下所示:
template <typename T>
int MyVector<T>::binSearchC(T const &e, int lo, int hi) const
{
while(lo<hi)
{
int mi = (lo + hi) >> 1;
(elem[mi]<e?):lo=mi+1:hi=mi;
}
return --lo;
}
以上算法實(shí)現(xiàn)中雨涛，結(jié)束循環(huán)的唯一條件是左右區(qū)間lo=hi,找到較為靠后的元素之后，lo-1就是較為靠后的元素的下標(biāo)懦胞。
3. 冒泡排序算法的一種新實(shí)現(xiàn)
以往在實(shí)現(xiàn)冒泡排序算法時(shí)替久，分為內(nèi)外兩次循環(huán)，外層循環(huán)遍歷整個(gè)向量躏尉，而內(nèi)層循環(huán)則用來(lái)比較和交換元素蚯根，一種新的實(shí)現(xiàn)方法是可以將內(nèi)外兩層循環(huán)分開(kāi)實(shí)現(xiàn)，具體實(shí)現(xiàn)如下代碼所示：
template <typename T>
void MyVector<T>::bubbleSort(int lo, int hi)
{
while(!bubble(lo,hi--));
}
template <typename T>
bool MyVector<T>::bubble(int lo,int hi){
bool sorted = true; //假定整體有序
while(++lo<hi)
{
if(elem[lo-1]>elem[lo])
{
sorted = false;
swap(elem[lo - 1], elem[lo]);
}
}
return sorted;
}
整體實(shí)現(xiàn)代碼胀糜，如上所示颅拦，將內(nèi)外層循環(huán)分開(kāi)實(shí)現(xiàn)，bubbleSort()相當(dāng)于實(shí)現(xiàn)了外層循環(huán)教藻，并且通過(guò)設(shè)置標(biāo)志位實(shí)現(xiàn)了交換矩距，整個(gè)代碼更加簡(jiǎn)潔。
