对于向量或者数组这种数据结构，除了常常用到的增，改，删，除元素之外，还会涉及到一些其他操作，特此做以下总结：
参考教材：《数据结构 C++语言版》邓俊辉著
为了算法实现，定义一个模板类如下所示;
template <typename T>
class MyVector
{
private:
int my_size; //向量当前大小
T *elem; //存放数据
public:
void uniquify(); //去重复元素
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. 去重复元素
对于一个向量或者数组来说，可能存在者若干重复元素，对于一个有序向量，重复元素的去除，可以用以下C++代码实现：
template <typename T>
void MyVector<T>::uniquify()
{
int i,j=0 //用i记录不重复元素，用j遍历当前向量
while(++j<my_size)
{
if(elme[j]!=elem[i])
{
elem[++i] = elem[j];
}
my_size = i;
i++;
}
}
如以上代码所示，去除一个有序向量的重复元素，其过程如下图所示：
2. 二分查找算法及改进
- A版算法
对于向量中某一元素的查找，除了顺序查找之外，对于有序向量，可以使用二分查找，常规二分查找的算法实现如下所示：
template <typename T>
int MyVector<T>::binSearchA(const T &e, int lo, int hi) const //在区间查找
{
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版的实现可以由上代码所示，经过多次比较，直到找到元素，返回其下标。
- 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版算法相比，该算法只经过一次比较，不断通过一次比较，更新左右区间，找到对应元素之后，也不返回，直到比较的区间缩小至1时，停止比较。与上一版算法相比，尽管最好情况下的算法性能有所下降，但是最坏情况下的算法性能有所上升。
- C版算法
A版算法与C版算法虽然能够成功的查找到元素的位置，但是仍然存在其局限性，当存在重复元素时，按照某种优先级会返会较为靠后的元素，改进后的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;
}
以上算法实现中，结束循环的唯一条件是左右区间lo=hi,找到较为靠后的元素之后，lo-1就是较为靠后的元素的下标。
3. 冒泡排序算法的一种新实现
以往在实现冒泡排序算法时，分为内外两次循环，外层循环遍历整个向量，而内层循环则用来比较和交换元素，一种新的实现方法是可以将内外两层循环分开实现，具体实现如下代码所示：
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;
}
整体实现代码，如上所示，将内外层循环分开实现，bubbleSort()相当于实现了外层循环，并且通过设置标志位实现了交换，整个代码更加简洁。
网友评论