第1节 线性表使用顺序存储

/* 主题: 使用顺序结构实现线性表
* 作者: chinazhangjie(邮箱:[email protected])
* 开发语言: C++
* 开发环境: Microsoft Visual Studio 2008
* 日期: 2010.08.26
*/　　
template <class T>
class seq_list {
public:
        typedef T                               value_type;
        typedef T*                              pointer;
        typedef unsigned int    sl_size;
public:
        // 构造函数
        seq_list(sl_size init_size = 100,sl_size incre_size = 10) 
                :INIT_SIZE(init_size),INCREMENT_SIZE(incre_size) {
                __init_list(INIT_SIZE);
        }

        // 拷贝构造函数
        explicit seq_list(seq_list<T>& sl)
                :INIT_SIZE(sl.INIT_SIZE),INCREMENT_SIZE(sl.INCREMENT_SIZE) {
                __init_list(INIT_SIZE);
                __copy_elem(sl);
        }

        // 析构函数
        ~seq_list() {
                __destroy_self();
        }

        // 重载赋值运算符
        seq_list& operator = (seq_list& sl) {
                if (this == &sl) {
                        return *this;
                }
                // 销毁自身
                __destroy_self();
                __init_list(sl.get_capacity());
                __copy_elem(sl);
                return *this;
        }
        const value_type& at(sl_size i) const {
                if (i >= length) {
                        throw std::out_of_range(string("at out_of_range"));
                }
                return elem_ptr[i];
        }
        // 重载下标运算符
        value_type& operator[] (sl_size i) const {
                if (i >= length) {
                        throw std::out_of_range(string("[] out_of_range"));
                }
                return elem_ptr[i];
        }

        // 获取长度
        sl_size get_length() const {
                return this->length;
        }

        // 获取长度
        sl_size size() const {
                return this->length;
        }

        // 获取容量
        sl_size get_capacity() const {
                return this->capacity;
        }

        // 在第 locate 个元素之前插入新的元素 elem，返回表的长度
        sl_size insert(sl_size locate, const value_type& elem) {
                if (locate >= length + 1) {  // 判断locate的合法性
                        throw std::out_of_range("insert out_of_range");
                }
                if (length >= capacity) {    // 当前存储空间已满，增加分配
                        __incre_list();
                }
                // 元素后移
                for (sl_size i = length; i > locate; -- i) {
                        elem_ptr[i] = elem_ptr[i-1];
                }
                // 安插新元素
                elem_ptr[locate] = elem;
                return ++length;
        }

        // 移除第locate个元素，返回第locate个元素的值
        value_type remove(sl_size locate) {
                if (locate >= length) {
                        throw std::out_of_range("remove out_of_range");
                }
                value_type remove_elem = elem_ptr[locate];
                for (sl_size i = locate; 
                         i < length-1; 
                         ++ i) {
                        elem_ptr[i] = elem_ptr[i+1];
                }
                -- length;
                return remove_elem;
        }

        // 判空
        bool empty() const {
                return length == 0;
        }

        // 清空顺序表
        void clear() {
                length = 0;
        }

        // 在顺序表中找到第一个与elem满足compare元素的位序
        // (函数名称根据书中所起，有什么意义，我也不清楚)
        sl_size locate_elem(const value_type& elem,
                                                bool (*compare)(value_type,value_type)) {
                // 若找到，则返回其在顺序表的位序，否则返回0
                for (sl_size i = 0; i < this->size(); ++ i) {
                        if ((*compare)(elem_ptr[i],elem))
                                return i;
                }
                return 0;
        }

        // 使用仿函数作参数
        template <class FuncObj>
        sl_size locate_elem(const value_type elem,FuncObj funcobj) {
                for (sl_size i = 0; i < this->size() ; ++ i) {
                        if (funcobj(elem_ptr[i],elem)) 
                                return i;
                }
                return 0;
        }

        // 排序(选择法)--递增
        void sort_increase() const {
                if (length == 0 || length == 1) {
                        return ;
                }
                for (sl_size i = 0; i < length - 1; ++ i) {
                        sl_size locate = i;
                        for (sl_size j = i; j < length; ++ j) {
                                if (elem_ptr[locate] > elem_ptr[j])
                                        locate = j;
                        }
                        if (locate != i) {
                                // 交换
                                value_type tmp = elem_ptr[i];
                                elem_ptr[i] = elem_ptr[locate];
                                elem_ptr[locate] = tmp;
                        }
                }
        }

        // 排序(选择法)--递减
        void sort_decrease() const {
                if (length == 0 && length == 1) {
                        return ;
                }
                for (sl_size i = 0; i < length - 1; ++ i) {
                        sl_size locate = i;
                        for (sl_size j = i; j < length; ++ j) {
                                if (elem_ptr[locate] < elem_ptr[j])
                                        locate = j;
                        }
                        if (locate != i) {
                                // 交换
                                value_type tmp = elem_ptr[i];
                                elem_ptr[i] = elem_ptr[locate];
                                elem_ptr[locate] = tmp;
                        }
                }
        }

        // 排序(选择法)--使用仿函数
        template <class FuncObj>
        void sort(FuncObj funcobj) {
                if (length == 0 && length == 1) {
                        return ;
                }
                for (sl_size i = 0; i < length - 1; ++ i) {
                        sl_size locate = i;
                        for (sl_size j = i; j < length; ++ j) {
                                if (funcObj(elem_ptr[locate],elem_ptr[j]))
                                        locate = j;
                        }
                        if (locate != i) {
                                // 交换
                                value_type tmp = elem_ptr[i];
                                elem_ptr[i] = elem_ptr[locate];
                                elem_ptr[locate] = tmp;
                        }
                }
        }

        // 
        friend ostream& operator << (ostream& out,seq_list<T>& rhs) {
                for (sl_size i = 0; i < rhs.get_length(); ++ i) {
                        out << rhs[i] << ' ';
                }
                out << endl;
                return out;
        }

        // 顺序表表的合并——按照递增顺序，不修改ths
        void merge(seq_list<T>& rhs) {
                if (rhs.size() == 0) {
                        this->sort_increase();
                        return ;
                }
                seq_list<T> other;
                other = rhs;
                // 先按照递增排序
                this->sort_increase();
                other.sort_increase();
                if (length == 0) {
                        *this = other;
                        return ;
                }
                sl_size total = this->size() + other.size();
                seq_list<T> new_list(total);
                sl_size len1 = 0;
                sl_size len2 = 0;
                sl_size i = 0;
                while (len1 < this->size() && len2 < this->size()) {
                        if (this->at(len1) <= other.at(len2)) {
                                new_list.insert(i,this->at(len1));
                                ++ len1;
                                ++ i;
                        }
                        else {
                                new_list.insert(i,other.at(len2));
                                ++ len2;
                                ++ i;
                        }
                }
                while (len1 < this->size()) {
                        new_list.insert(i,this->at(len1));
                        ++ i;
                        ++ len1;
                }
                while (len2 < other.size()) {
                        new_list.insert(i,other.at(len2));
                        ++ i;
                        ++ len2;
                }
                *this = new_list;
        }

private:
        void __incre_list() {
                pointer new_ptr = new value_type[capacity + INCREMENT_SIZE];
                capacity += INCREMENT_SIZE;     // 增加存储容量
                if (new_ptr == NULL) {
                        throw std::bad_alloc("__incre_list bad_alloc");
                }
                // 复制
                for (sl_size i = 0; i < length; ++ i) {
                        new_ptr[i] = elem_ptr[i];
                }
                delete[] elem_ptr;
                elem_ptr = new_ptr;
        }

        void __init_list(sl_size cap) {
                elem_ptr = new value_type[cap];
                if (elem_ptr == NULL) {
                        throw std::bad_alloc("__init_list bad_alloc");
                }
                length = 0;
                capacity = cap;
        }

        void __copy_elem(seq_list<T>& sl) {
                for (sl_size i = 0; i < sl.get_length(); ++ i) {
                        elem_ptr[i] = sl[i];
                }
                length = sl.get_length();
        }

        void __destroy_self() {
                delete[] elem_ptr;
                elem_ptr = NULL;
                length = 0;
                capacity = 0;
        }

private:
        pointer elem_ptr;       // 存储空间基址
        sl_size length;         // 当前长度
        sl_size capacity;       // 总容量（长度）
        
        const sl_size INIT_SIZE;                // 初始分配量
        const sl_size INCREMENT_SIZE;   // 分配增量
};