登录后台

页面导航

本文编写于 120 天前,最后修改于 26 天前,其中某些信息可能已经过时。

向量

抽象数据类型

可扩展向量

静态空间管理策略

静态空间管理:开辟内部数组 _elem[]并使用一段连续的空间

  • _capacity:总容量
  • _size:当前实际数量

image-20220413000041481

难以预测空间大小可能发生溢出,_elem[]空间不够,或者空间太大,存放数据却很少,造成空间的浪费

动态空间管理策略

当空间即将溢出时,会重新分配一块更大的空间,然后将数据全部放到新的空间中,将旧的空间回收

template <typepname T>
void Vector<T>::expand(){       // 向量扩容的函数
    if(_size < _capacity) return;       // 如果数据数量小于向量的容量,则直接返回,不做扩容操作
    _capacity = max(_capacity, DEFAULT_CAPACITY);       // 向量的容量不低于最小容量
    T* oldElem = _elem;
    _elem = new T[_capacity <<= 1];     // 容量左移一位即加倍
    for(int i = 0; i < _size; i++){     // 将原向量中的数据放入新的向量中
        _elem[i] = oldElem[i];
    }
    delete [] oldElem;      // 释放原空间
}

递增式扩容,时间复杂度太高

T* _oldElem = _elem;
_elem = new T[_capacity += INCREMENT];

image-20220413002550346

无序向量

循秩访问

可使用数组元素的访问方式,将下表操作符 [] 重载

tmplate <typename T>        // 0 <= r < _size
T & Vector<T>::operator[](rank r) const { return _elem[r]; }
插入

当需要向向量中某个位置插入数据时,需要将后面的数据依次后移,然后插入数据,记得要判断容器容量是否足够,防止溢出

template <typename T>
Rank Vector<T>::insert(Rank r, T const & e){
    expand();        // 如果有必要,就需要扩容
    for(int i = _size; i > r; i--){        // 从后往前一个一个将数据后移
        _elem[i] = _elem[i-1];
    }
    _elem[r] = e;        // 插入数据
    _size++;        // 总数量
    return r;        // 返回秩
}
区间删除

先将某个区间内的元素删除,然后将后面的元素一个一个向前移动

tmplate <typename T>
int Vector<T>::remove(Rank lo, Rank hi){        // 删除区间[lo, hi)内的元素
    if (lo == hi) return 0;        // 单独处理只删除一个元素的情况
    while(hi < _size){        // 逐个将[hi, _size)的数据左移
        _elem[lo++] = _elem[hi++];
    }
    _size = lo;        // 更新规模
    shrink();
    return hi - 0;        // 返回元素数量
}

以上代码可能会有一个漏洞,见下面这个程序,当要删除的区间较大时,后面的部分可能删不掉

#include <iostream>
using namespace std;

void my_print(int array[], int n){
    for(int i = 0; i < n; i++){
        cout << array[i] << " ";
    }
    cout << endl;
}

int main(){
    int lo = 2;
    int hi = 8;
    int _size = 10;
    int buf[_size] = {0,1,2,3,4,5,6,7,8,9};
    my_print(buf, _size);
    while(hi < _size){
        buf[lo++] = buf[hi++];
        _size--;
    }
    my_print(buf, _size);

    return 0;
}
单元素删除

将向量中某个元素删除

template <typename T>        // 删除向量中秩为r的元素
T Vector<T>::remove(Rank r){
    T e = _elem[r];        // 将要被删除的元素保存起来
    remove(r, r + 1);        // 将后续元素逐个向左移动
    return e;        // 返回被删除的元素
}
查找

从后往前依次遍历查找

template <typename T>
Rank Vector<T>::find(T const & e, Rank lo, Rank hi) const{
    while((lo < hi--) && (e != _elem[hi]));        // 逆向查找
    return hi;        // 若hi < lo 意味着查找失败,否则返回查找到元素的秩
}
去重/唯一化

每次遇到一个数据,就和它前面的元素比较,如果存在,则删除,若不存在,则将钙元素归入前面,然后继续查看下一个元素

template <typename T>
int Vector<T>::deduplicate(){
    int oldsize = _size;
    Rank i = 1;
    while (i < _size){
        (find(_elem[i], 0, i) < 0) ? i++ : remove(i);
    }
    return oldsize - _size;
}
遍历

利用函数指针机制,只读或局部性修改

template <template T>
void Vector<T>::traverse(void (*vist)(T&)){    // 函数指针
    for(int i = 0; i < _size; i++){
        visit(_elem[i]);
    }
}

利用函数对象机制,全局性修改

template <typelate T> template <typename VST>
void Vector<T>::traverse(VST& vist){
    for(int i = 0; i < _size; i++){
        visit(_elem[i]);
    }
}

例子

// 将向量中的每一个元素都加1
template <typename T>
struct Increase{
    virtual void operator()(T & e){
        e++;
    }
}

template <typename T>
void increase(Vector<T> & v){
    V.traverse(Increase<T>());
}

有序向量

有序性

有序序列要求任意一对相邻元素顺序

无序序列中总有一对相邻元素逆序

template <typelate T>
int Vector<T>::desordered() const{
    int n = 0;
    for(int i = 1; i < _size; i++){
        n += (_elem[i-1] > _elem[i]);
    }
    return n;
}
唯一化
// 逐个删除相同元素(低效)
template <typename T>
int Vector<T>::uniquify(){
    int ordSize = _size;
    int i = 0;
    while(i < _size - 1){
        (_elem[i] == _elem[i+1]) ? remove(i + 1) : i++;        // 若相同则删除,不同则比较下两个
    }
    return oldSize - _size;        // 删除的元素数量
}
// 批量删除相同元素(高效)
template <typename T>
int Vector<T>::uniquify(){
    Rank i = 0, j = 0;
    while(++j < _size){        // 逐一扫描,直至末尾元素
        if(_elem[i] != _elem[j]){
            _elem[++i] = _elem[j];        // 如果相邻两个元素不相等,则右移,比较下两个
        }        // 不然的话J++
    }
    _size = ++i;
    shrink();        // 直接截除尾部多余元素
    return j - 1;        // 返回被删除的元素数量
}
二分查找

取中间值比较,若相等可以直接返回,若小于中间值则去左边查找,否则去右边查找

// 1
template <typename T>
static Rank binSearch(T* A, T const& e, Rank lo, Rank hi){
    while(lo < hi){
        mid = (lo + hi) >> 1;        // 取中间那个
        if(e < A[mid]){        // 如果要查找的数小于mid则去左边查找
            hi = mid;
        }
        else if(A[mid] < e){        // 如果要查找的数大于mid则去右边查找
            lo = mid + 1;
        }
        else{
            return mid;        // 如果要查找的数刚好等于mid则直接返回
        }
    }
    return -1;        // 没有找到,返回-1
}
// 2
template <typename T>
static Rank binSearch(T* A, T const & e, Rank e, Rank lo, Rank hi){
    while(1 < hi - lo){        // 当查找宽度缩短到1时,停止查找
        Rank mid = (lo + hi) >> 1;        // 取中点
        (e < A[mid]) ? (hi = mid) : (lo = mid);
    }        // 结束时,hi = lo + 1,查找区间只含一个元素A[lo]
    return(e == A[lo]) ? lo : -1;        // 查找成功返回查找到的秩否则返回-1
}
// 3
template <typename T>
static Rank binSearch(T* A, T const& e, Rank lo, Rank hi){
    while(lo < hi){
        Rank mid = (lo + hi) >> 1;
        (e < A[mid]) ? hi = mid : lo = mid + 1;
    }        // 结束时,A[lo = hi]为大于e的最小元素
    return --lo;        // lo - 1即不大于e的元素的最大秩
}
Fib查找
template <typename T>
static Rank fibSearch(T* A, T const & e, Rank lo, Rank hi){
    Fib fib(hi - lo);        // 创建Fib数列
    while(lo < hi){
        while(hi - lo < fib.get()){        // 最多迭代几次
            fib.prev();
        }
        Rank mid = lo + fib.get() - 1;        // 向前查找,确定轴点
        if(e < A[mid]){
            hi = mid;
        }
        else if(A[mid] < e){
            lo = mid + 1;
        }
        else{
        return mid;
            }
    }
    return -1;
}
差值查找

冒泡排序

// 1
template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi){
    while(!bubble(lo, hi--));        // 逐趟扫描交换
}

template<typename T>
vool Vector<T>::bubble(Rank* lo, Rank hi){
    bool sorted = true;        // 整体有序的标志
    while(++lo < hi){
        if(_elem[lo - 1] > _elem[lo]){        // 若前面的大于后面的则交换,然后设置sorted为false
            sorted = false;
            swap(_elem[lo - 1], _elem[lo]);
        }
    }
    return sorted;        // 返回是否有序的标志
}
// 2
template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi){
    while(lo < (hi = bubble(lo, hi)));        // 逐趟扫描交换
}

template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi){
    Rank last = lo;        // 最右侧的逆序对的初始化为[lo - 1, lo]
    while(++lo < hi){        // 自左向右逐个检查各对元素
        if(_elem[lo - 1] > _elem[lo]){        // 若逆序则交换
            last = lo;
            swap(_elem[lo - 1], _elem[lo]);
        }
    }
    return last;        // 返回最右侧的逆序对位置
}

归并排序

template <typename T>
void Vector<T>::merge(Rank lo, Rank mid. Rank hi){
    T* A = _elem + lo;        // 合并后的向量A[0, hi - lo) = _elem[lo, hi)
    int lb = mid - lo;        // 前字向量B[0, lb) = _elem[lo, mid)
    T* B = new T[lb];
    for(Rank i = 0; i < lb; B[i] = A[i++]);        // 复制前字向量B
    int lc = hi - mid;        // 后子向量C[0, lc) = _elem[mid, hi)
    T* C = _elem + mid;
    for(Rank i = 0; j = 0; k = 0; (j < lb) || (k < lc);){    // B[j]和C[k]中小的转至A的末尾
        if((j < lb) && (lc <= k }} (B[j] <= C[k]))){
            A[i++] = B[j++];        // C[k]已无或不小
        }
        if((k < lc) && (lb <= j || (C[k] < B[j]))){        // B[j]已无或更大
            A[i++] = C[j++];
        }
    }
    delect [] B;        // 释放临时空闲B
}

位图

每个位置的0/1代表了该位置的数据是否存在

class Bitmap{
private:
    int N;
    char* M;
public:
    Bitmap(int n = 8){
        M = new char[N = (n + 7) / 8];
        memset(M, 0, N);
    }
    ~Bitmap(){
        delete [] M;
        M = NULL;
    }
    void set(int k);
    void clear(int k);
    bool test(int k);
};

list

循秩访问

O(n) 效率有点低

template <typelate T>
T List<T>::operator[](Rank r) const{        // 0 <= r < size
    Posi(T) p = first();        // 从首节点出发
    while (0 < r--) { p = p->succ; }        // 顺序数到第r个节点
    return p->data;        // 返回目标节点
}

无序列表

插入和构造
template <typename T>
Posi(T) List<T>::insertBefore(Posi(T) p, T const& e){
    _size++;
    return p->insertBefore(e);        // 把e当做p的前驱插入
}
template <typename T>
Posi(T) ListNode<T>::insertAspred(T const& e){
    Posi(T) x = new ListNode(e, pred, this);        // 创建一个新的节点,将前驱设置为fred,后继设置为this
    pred->succ = x;        // 
    pred = x;
    return x;
}
template <typename T>
void List<T>::copyNodes(Posi(T) p, int n){
    init();
    while (n--){
        insertAslast(p->data);
        p = p->succ;
    }
}
删除与析构
template <typename T>
T List<T>::remove(Posi(T) p){
    T e = p->data;        // 备份要删除的节点
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    _size--;
    return e;
}
template <typename T> List<T>::~List(){
    clear();        // 清空列表
    delete header;        // 删除头结点
    delete trailer;        // 删除尾结点
}

template typename <T> int List<T>::clear() {
    int oldSize = _size;
    while(0 < _size) { remove(header->succ); }        // 反复删除首节点
    return oldSize;
}
查找
template <typename T>
Posi(T) List<T>::find(T const & e, int n, Posi(T) p) const {
    while (0 < n--){        // 从后往前遍历
        if(e == (p = p->pred)->data ) return p;        // 如果找到相等的则返回节点p
    }
    return NULL;        // 未找到返回空
}
去重
template <typename T>
int List<T>:;deduplicate() {
    if(_size < 2) return0;            // 如果只有一个元素则直接返回0
    int lodSize = _size;        // 保存大小
    Posi(T) p = first();        // 把第一个元素赋值给p
    Rank r = 1;
    while (trailer != (p = p->suucc)){        // 向后遍历直到哨兵节点
        Posi(T) q = find(p->data, r, p);    // 在前面的区域寻找是否有何p相同的节点
        q ? remove(q) : r++;        // 找到则把前面相同的节点删除,否则继续向后查找
    }
    return oldSize - _size;        // 返回被删除元素的总数
}

有序列表

唯一化
template <typename T>
int List<T>:;uniquify() {
    if ( _size < 2 ) return 0;        // 元素只有一个就直接返回 0
    int oldSize = _size;        // 记录原规模
    ListNodePosi(T) p = first();    // p是各区段的起点
    ListNodePosi(T) q;        // 设q是后继
    while( trailer != ( q = p->succ ) ){        // 一直往后遍历
        if ( p->data != q->data ) { p = q; }        // 若相邻的数据不相等则后移
        else { remove(q); }        // 若相等则删除后面的元素
    }
    return oldSize - _size;        // 返回删除的元素个数
}
查找
template <typename T>        // 在有序列表内节点p的前驱中找到不大于e的最后一个
Posi(T) List<T>::search(T const & e, int n, Posi(T) p) const {
    while ( 0 <= n-- ){        // 从后向前遍历
        if ( ( (p = p->pred) -> data ) <= e ) break;        // 如果找到小于等于e的数据就直接退出循环
    }
    return p;
}

选择排序

template <typename T>        // 对列表中起始于位置p的连续n个元素做选择排序
void List<T>::selectionSort(Posi(T) p, int n) {
    Posi(T) head = p->pred;        // p的前驱赋给head
    Posi(T) tail = p;        // p赋给tail
    for (int i = 0; i < n; i++){        // 遍历
        tail = tail->succ;
        while (1 < n) {
            insertBefore( tail, remove ( selectMax(head->succ, n) ) );        // 选择最大的插入到前面
            tail = tail->pred;
            n--;
        }
    }
}
template <typename T>        // 从位置p开始的n个元素中挑出最大的那个
Posi(T) List::selectMax(Posi(T) p, int n){
    Posi(T) max = p;        // 先将最大的定为p
    for(Posi(T) cur = p; 1 < n; n--){        // 后续的节点一个一个和max比较
        if( !lt((cur = cur->succ)->data, max->data) ) { max = cur }        // 如果比max大则更新max
    }
    return max;
}

插入排序

template <typename T>        // 对列表中起始于位置p的n个元素做插入排序
void List<T>::insertSort(Posi(T), int n){
    for (int r = 0; r < n; r++) {        // 向后遍历节点
        insertAfter(search(p->data, r, p), p->data);    // 找到合适位置插入
        p = p->succ;
        remove(p->pred);
    }
}

栈和队列

栈ADT及实现

template <typename T>
class Stack : public Vector<T> {        // 是向量的派生类
public:
    void push(T const & e) { insert(size(), e); }        // 入栈
    T pop() { return remove(size() - 1); }        // 出栈
    T & top() { return (*this)[size() - 1]; }        // 取顶
};

逆序输出

进制转换,因为进制转换最终是要逆序输出所以可以使用栈

void convert(Stack<char> &s, __int n, int base) {
    static char digit[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C'. 'D', 'E', 'F'};
    while(n > 0){
        S.push(digit[n % base]);
        n /= base;
    }
}

main(){
    Stack<char> S;
    convert(S, n, base);
    while(!S.empty()) { printf("%c", S.pop()); }
}

递归嵌套

括号匹配

bool paren(const char exp[], int lo, int hi){
    Stack<char> S;
    for(int i = lo; i < hi; i++){
        if( '(' == exp[i] ) { S.push(exp[i]); }
        else if( !S.empty() ) { S.pop(); }
        else { return false; }
    }
    return S.empty();
}

栈混洗

按照一定的规则对栈中的数据进行排列

延迟缓冲

中缀表示求值

float evaluate(char* S, char* & RPN) {
    Stack<float> opnd;        // 运算数
    Stack<char> optr;        // 运算符
    optr.push('\0');        // 尾哨兵'\0'先入栈
    while (!optr.empty()) {        // 如果栈内部为空
        if( isdigit(*S)) { readNumber(S, opnd); }        // 如果是操作数,读入操作数
        else { switch(orderBetween(optr.top(), *S)); }    // 如果是运算符,则看它与栈顶的操作符的优先级进行相应操作
    }
    return opnd.pop();        // 弹出最后的计算结果
}

逆波兰表达式

float valuate(char* S, char* RPN) {
   while( !optr.empty() ) {        // 逐个处理个字符,直至运算符栈空
       if(isdigit(*S)){        // 若是操作数
           readNumber(S, opnd);        // 介入RPN
           append(RPN, opnd top());
       }else{        // 若当前字符位运算符
           switch(orderBetween(optr.top(), *S))
               case '>' {
                   char op = optr(pop();        // 介入RPN
                   append(RPN op);
           }
       }
   }
}

队列

template <typename T> class Queue:public List<T> {
public:
    void enqueue(T const & e) { insertAsLast(e); }        // 入队
    T dequeue() { return remove(first()); }        // 出队
    T & front() { return first()->data; }        // 队首
}

二叉树