数据结构 - Lesson 2.1

<!-- toc -->本节课的内容较多，又牵扯到实际代码，因此分为基本内容和实践代码两部分

基本内容

实践代码

顺序表

简单的C++（zao）实（lun）现（zi）

一个省略部分实现的C++实现的框架如下所示：

// 第一次写纯C++程序，如有不当，欢迎指出
#ifndef seqlist_hpp
#define seqlist_hpp
#include <iostream>
#include <stdlib.h>
template <class T>
class SeqList {
public:
    int max_length;
    T *data;
    int real_lengh;
    SeqList(int);
    ~SeqList();
    bool AddElement(T);
    void PrintList() const;
    bool FindInSortedList(T, int &) const;
    bool FindElement(T, int &) const;
    void SortList();
    bool InsertElement(int);
    bool DelElement(int);
    bool PartList(int);
    bool ValidIndex(int) const;
    bool SwapElement(int, int);
};
template <class T>
bool SeqList<T>::SwapElement(int x, int y) {  // swap two elements by given index
    if (!(ValidIndex(x) && ValidIndex(y))) {
        return false;
    }
    T tmp;
    tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
    return true;
}
template <class T>
bool SeqList<T>::ValidIndex(int index) const {  // check if a given index is valid
    if (index < 0  index >= real_lengh) {
        return false;
    }
    return true;
}
// allocate memory for seq list
template <class T>
SeqList<T>::SeqList(int length) : max_length(length) {
    data = (T *) malloc(sizeof(T) * length);
    real_lengh = 0;
}
// destroy the list object
template <class T>
SeqList<T>::~SeqList() {
    free(data);
}
template <class T>
bool SeqList<T>::AddElement(T element) {  // add an element at the tail
    if (real_lengh >= max_length) {
        return false;
    }
    data[real_lengh] = element;
    real_lengh++;
    return true;
}
template <class T>
void SeqList<T>::PrintList() const {
    for (int i = 0; i < real_lengh; ++i) {
        std::cout << data[i] << ' ';
    }
    std::cout << std::endl;
}
#endif /* seqlist_hpp */

这里我们使用模版来实现顺序表可以存储不同类型的数据对象。使用构造函数和析构函数来实现顺序表的存储和初始化和销毁。

排序

由于技艺不精，这里暂且实现一个简单的冒泡排序，为下面有序表的二分查找做准备:

template <class T>
void SeqList<T>::SortList() {
    int tmp = 0;
    for (int i = 0; i < real_lengh; ++i) {
        for (int j = i; j < real_lengh; ++j) {
            if (data[i] > data[j]) {
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }
}

时间复杂度O(n^2)，空间复杂度为O(1).

有序表二分查找

既然已经搭起了框架，就要开始实现一些方法了，首先尝试实现有序表的二分查找算法。代码如下：

template <class T>
bool SeqList<T>::FindInSortedList(T element, int &index) const {
    int part_begin = 0;  // 搜索区域头
    int part_end = real_lengh;
    int part_middle = part_end / 2;
    while (part_begin != part_middle) {
        if (data[part_middle] > element) {
            part_end = part_middle;
            part_middle = (part_middle + part_begin) / 2;  // 注意向下取整
        } else if (data[part_middle] < element) {
            part_begin = part_middle;
            part_middle = (part_end + part_begin) / 2;
        } else {
            index = part_middle;
            return true;
        }
    }
    index = -1;
    return false;
}

这里注意两点：

• 初始时将搜索区域尾设置为表的实际长度+1的目的是中和整型除以2带来的向下取整的影响，保证变量part_middle能刚好取到所有有效值

• 循环终止的条件一个是找到需要的数据，一个是查找完毕也没有找到需要的值，后者的条件是part_begin == part_middle，同样是向下取整的影响。

本算法的时间复杂度O(logn)，空间复杂度为O(1).

根据基准元素分割（快排基础）

这个算法所实现的是预定一个基准元素，将表中与该元素大小关系相同的元素放在该元素的同一侧，是快速排序的第一步。算法实现如下：

template <class T>
bool SeqList<T>::PartList(int pivot) {  // 基准元素的索引
    if (!ValidIndex(pivot)) {
        return false;
    }
    T tmp = 0;
    tmp = data[pivot];  // 将基准元素与表首的元素互换，保证所有元素被遍历
    data[pivot] = data[0];  // 暂存基准元素
    int part_head = 0;
    int part_tail = real_lengh - 1;
    while (part_tail != part_head) {
        while (data[part_tail] > tmp && part_tail != part_head) {
            part_tail--;
        }
        SwapElement(part_tail, part_head);
        while (data[part_head] <= tmp && part_tail != part_head) {
            part_head++;
        }
        SwapElement(part_tail, part_head);
    }
    data[part_tail] = tmp;
    return true;
}

这里的part_tail和part_head相当于两把相向而行的梳子，同时两者每次均前进1，因此两者必然会相遇。相遇的位置即放置基准元素的位置。

测试

最后测试一下上面的几个算法，结果如图：