数据结构与算法

C++ 版本，不包含图的数据结构

线性表

顺序表

逻辑上相邻的数据，存储在物理上相邻的存储单元，数组。

#include <iostream>
using namespace std;

#define ok 0
#define error -1

class SeqList {
private:
    int *list;
    int maxsize;
    int size;

public:
    SeqList();                         // 构造函数
    ~SeqList();                        // 析构函数
    int list_size();                   // 获取顺序表实际长度
    int list_insert(int i, int item);  // 插入一个元素，参数是插入的数值和位置
    int list_del(int i);  // 删除一个元素，参数是删除的位置
    int list_get(int i);  // 获取一个元素，参数是获取的位置
    void list_display();
};

// 构造函数，对象初始化设定
SeqList::SeqList() {
    maxsize = 1000;
    size = 0;
    list = new int[maxsize];
}

// 析构函数
SeqList::~SeqList() {
    // 回收空间
    delete[] list;
}

int SeqList::list_size() {
    return size;
}

// 插入
int SeqList::list_insert(int i, int item) {
    if (i < 1 || i > size + 1) {
        cout << "error" << endl;
        return error;
    }
    size++;
    for (int k = size - 1; k >= i - 1; k--) {
        list[k + 1] = list[k];
    }
    list[i - 1] = item;
    return ok;
}

// 删除
int SeqList::list_del(int i) {
    if (i < 1 || i > size) {
        cout << "error" << endl;
        return error;
    }
    for (int k = i - 1; k < size; k++) {
        list[k] = list[k + 1];
    }
    size--;
    return ok;
}

// 获取
int SeqList::list_get(int i) {
    if (i < 1 || i > size) {
        cout << "error" << endl;
        return error;
    }
    return list[i - 1];
}

// 打印所有数据
void SeqList::list_display() {
    cout << size << " ";
    for (int i = 0; i < size; i++) {
        cout << list[i] << " ";
    }
    cout << endl;
}

单链表

#include <iostream>
#define ok 0
#define error -1
using namespace std;

// 链表结点定义
class ListNode {
public:
    int data;
    ListNode *next;
    ListNode() {
        next = NULL;
    }
};

// 带头结点的单链表定义
class LinkList {
public:
    ListNode *head;
    int len;
    LinkList() {
        head = new ListNode();
        len = 0;
    }
    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }
    // 返回第i个结点的指针，如果不存在返回 NULL
    ListNode *LL_index(int i) {
        auto p = head;
        int j = 1;
        // 获取 i-1 结点
        while (p && j < i) {
            j++;
            p = p->next;
        }
        // 获取 i 结点
        return p;
    }
    // 获取第 i 个元素的数据
    int LL_get(int i) {
        if (i < 1 || i > len) {
            return error;
        }
        auto p = head;
        int j = 1;
        while (p && j < i) {
            j++;
            p = p->next;
        }
        if (p->next == NULL) {
            return error;
        }
        return p->next->data;
    }
    // 把数值 item 插入第 i 个位置
    int LL_insert(int i, int item) {
        auto p = head;
        if (i < 1 || i > len + 1) {
            return error;
        }
        int j = 1;
        while (p && j < i) {
            j++;
            p = p->next;
        }
        if (!p) {
            return error;
        }
        auto s = new ListNode();
        s->data = item;
        s->next = p->next;
        p->next = s;
        len++;
        return ok;
    }
    // 删除第 i 个结点
    int LL_del(int i) {
        if (i < 1 || i > len) {
            return error;
        }
        auto p = head;
        int j = 1;
        while (p && j < i) {
            j++;
            p = p->next;
        }
        if (p->next == NULL) {
            return error;
        }
        auto s = p->next;
        p->next = p->next->next;
        delete s;
        return ok;
    }
    // 输出单链表的内容
    void LL_display() {
        ListNode *p;
        p = head->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
};

双链表

class ListNode {
public:
    char data;
    ListNode *prev;
    ListNode *next;
    ListNode(): prev(this), next(this) {}
};

class DLinkList {
public:
    ListNode *head;
    int len;
    DLinkList() {
        head = new ListNode();
        len = 0;
    }
    ~DLinkList() {
        ListNode *p, *q;
        p = head;
        while (p != head) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }
    
    int add(int i, char item) {
        auto p = head->next;
        if (i < 1 || i > len + 1) {
            return error;
        }
        int j = 1;
        while (p != head && j < i) {
            j++;
            p = p->next;
        }
        if (!p) {
            return error;
        }
        auto s = new ListNode();
        s->data = item;
        
        s->prev = p->prev;
        p->prev->next = s;
        s->next = p;
        p->prev = s;
    
        len++;
        return ok;
    }
    
    void remove(ListNode *p) {
        len--;
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
    }
    
    void display() {
        if (len) {
            auto p = head->next;
            while (p != head) {
                cout << p->data;
                p = p->next;
            }
        } else {
            cout << "-";
        }
        cout << endl;
    }
};

循环链表

#include <iostream>
using namespace std;

class ListNode {
public:
    ListNode *next;
    int no;
    ListNode() {
        next = NULL;
    }
};

class LinkList {
public:
    ListNode *head;
    ListNode *last;
    int len;
    LinkList() {
        len = 0;
        head = new ListNode();
        last = head;
    }
    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != head) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
        last = NULL;
    }
    // 尾部插入
    void push(int n) {
        last->next = new ListNode();
        last->next->no = n;
        last = last->next;
        // 循环链表
        last->next = head;
        len++;
    }
};

int main() {
    int n, k, s;
    while (scanf("%d %d %d", &n, &k, &s) != EOF) {
        LinkList list;
        for (int i = 1; i <= n; i++) {
            list.push(i);
        }
        
        auto p = list.head;

        // 从 s 个人开始
        for (int i = 0; i < s - 1; i++) {
            p = p->next;
        }
        
        while (list.len) {
            if (p->next == list.head) p = p->next;
            // 数到 k 的前驱节点
            for (int i = 0; i < k - 1; i++) {
                p = p->next;
                if (p->next == list.head) p = p->next;
            }
            // 待删除的节点
            auto pk = p->next;
            list.len--;
            cout << pk->no << " ";
            p->next = pk->next;
            delete pk;
        }
        cout << endl;
    }
    
    return 0;
}

List 容器

• ** operator=**
  Assign content (public member function )

Iterators:

• begin
  Return iterator to beginning (public member function )
• end
  Return iterator to end (public member function )

Capacity:

• empty
  Test whether container is empty (public member function )
• size
  Return size (public member function )

Element access:

• front
  Access first element (public member function )
• back
  Access last element (public member function )

Modifiers:

• assign
  Assign new content to container (public member function )
• emplace_front
  Construct and insert element at beginning (public member function )
  mylist.emplace_front(10,'a');
• push_front
  Insert element at beginning (public member function )
• pop_front
  Delete first element (public member function )
• emplace_back
  Construct and insert element at the end (public member function )
• push_back
  Add element at the end (public member function )
• pop_back
  Delete last element (public member function )
• emplace
  Construct and insert element (public member function )
• insert
  Insert elements (public member function )
• erase
  Erase elements (public member function )
• clear
  Clear content (public member function )

Operations:

• splice
  Transfer elements from list to list (public member function )
  

整个链表 (1)	void splice (const_iterator position, list& x); void splice (const_iterator position, list&& x);
单个元素 (2)	void splice (const_iterator position, list& x, const_iterator i); void splice (const_iterator position, list&& x, const_iterator i);
元素范围 (3)	void splice (const_iterator position, list& x, const_iterator first, const_iterator last); void splice (const_iterator position, list&& x, const_iterator first, const_iterator last);

将元素从 x 转移到容器中，将它们插入位置。

这有效地将这些元素插入到容器中并将它们从 x 中删除，从而改变了两个容器的大小。该操作不涉及任何元素的构建或破坏。无论x是左值还是右值，或者value_type是否支持移动构造，它们都会被转移。

第一个版本 (1)将 x 的所有元素传输到容器中。 所述第二版本（2）仅传输 x 中的 i 元素（使用迭代器）放入容器中。 的第三个版本（3）的范围内传送[first, last)从 x 到容器中。

• remove
  Remove elements with specific value (public member function )
• unique
  Remove duplicate values (public member function )
• merge
  Merge sorted lists (public member function )first.merge(second);
• sort
  Sort elements in container (public member function )
  // comp 函数需手动实现
bool comp(first, second);
list.sort(comp);
• reverse
  Reverse the order of elements (public member function )

栈

后进先出

初始化

#include<stack>
using namespace std;
stack<string> s;

方法

• empty
  Test whether container is empty (public member function )
• size
  Return size (public member function )
• top
  Access next element (public member function )
• push
  Insert element (public member function )
• emplace

// stack::emplace
#include <iostream>       // std::cin, std::cout
#include <stack>          // std::stack
#include <string>         // std::string, std::getline(string)

int main ()
{
  std::stack<std::string> mystack;

  mystack.emplace ("First sentence");
  mystack.emplace ("Second sentence");

  std::cout << "mystack contains:\n";
  while (!mystack.empty())
  {
    std::cout << mystack.top() << '\n';
    mystack.pop();
  }

  return 0;
}

Output:

 mystack contains: 
 Second sentence 
 First sentence

• pop
  Remove top element (public member function )
• swap
  

Swap contents (public member function )

// stack::swap
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  foo.swap(bar);

  std::cout << "size of foo: " << foo.size() << '\n';
  std::cout << "size of bar: " << bar.size() << '\n';

  return 0;
}

Output:

 size of foo: 2 
 size of bar: 3 

复杂应用

//
//  main.cpp
//  DS堆栈--迷宫求解
//
//  Created by Jacky on 2021/3/24.
//

/*
 题目描述
 给出一个N*N的迷宫矩阵示意图，从起点[0,0]出发，寻找路径到达终点[N-1, N-1]

 要求使用堆栈对象来实现，具体算法参考课本3.2.4节51页

 输入
 第一行输入t，表示有t个迷宫

 第二行输入n，表示第一个迷宫有n行n列

 第三行起，输入迷宫每一行的每个方格的状态，0表示可通过，1表示不可通过

 输入n行

 以此类推输入下一个迷宫

 输出
 逐个输出迷宫的路径

 如果迷宫不存在路径，则输出no path并回车

 如果迷宫存在路径，将路径中每个方格的x和y坐标输出，从起点到终点，每输出四个方格就换行，最终以单词END结尾，具体格式参考示范数据

 输出的代码参考如下：

 //path是保存路径的堆栈，堆栈中每个元素都包含x坐标和y坐标，用属性xp和yp表示

 //path1是一个临时堆栈，把path的数据倒序输出到path1，使得路径按正序输出

     if (!path.empty())    //找到路径

     {    //......若干代码，实现path的数据导入path1

         i=0;  //以下是输出路径的代码

         while (!path1.empty())

         {    cpos = path1.top();

             if ( (++i)%4 == 0 )

                 cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--"<<endl;

             else

                 cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--";

             path1.pop();

         }

         cout<<"END"<<endl;

     }

     else

         cout<<"no path"<<endl; //找不到路径输出no path

 样例输入
 2
 8
 0 0 0 1 1 1 1 1
 1 0 0 0 1 0 0 1
 1 0 0 0 1 0 0 0
 1 1 0 0 0 0 0 1
 0 0 1 1 0 1 1 0
 0 0 0 0 0 0 1 1
 1 1 1 1 1 0 0 1
 0 0 0 0 1 0 0 0
 7
 0 0 0 1 1 1 1
 1 0 0 1 0 0 1
 1 0 0 1 0 0 0
 1 1 0 0 0 0 1
 0 0 1 1 0 1 0
 1 0 0 0 0 1 0
 0 0 0 0 1 1 0
 样例输出
 [0,0]--[0,1]--[0,2]--[1,2]--
 [1,3]--[2,3]--[3,3]--[3,4]--
 [4,4]--[5,4]--[5,5]--[6,5]--
 [6,6]--[7,6]--[7,7]--END
 no path
 */

// 参考 https://www.bilibili.com/video/BV1eK411L79V?from=search&seid=2431395396966728281

#include <iostream>
#include <stack>
using namespace std;

typedef struct Point {
    int x;
    int y;
} Point;

stack<Point> path;

// 当前坐标 x, y, 迷宫, 迷宫阶数
bool findPath(int x, int y, int **maze, int limit) {
    // 已有分支到达终点
    if (maze[limit-1][limit-1] == 2) {
        return true;
    }
    // 越界
    if (x < 0 || x >= limit || y < 0 || y >= limit) {
        return false;
    }

    // 判断当前位置是否可走
    if (*(*(maze + x) + y) == 0) {
        // 假设当前路径可走
        *(*(maze + x) + y) = 2;
        // 右下左上
        if (findPath(x, y + 1, maze, limit)
            || findPath(x + 1, y, maze, limit)
            || findPath(x, y - 1, maze, limit)
            || findPath(x - 1, y, maze, limit)
            ) {
            path.push(Point{x, y});
            return true;
        } else {
            *(*(maze + x) + y) = 0;
            return false;
        }
    }
    
    return false;
}

int main() {
    int t, n;
    int **p;
    cin >> t;
    while (t--) {
        cin >> n;
        p = new int*[n];
        for (int i = 0; i < n; i++) {
            p[i] = new int[n];
            for (int j = 0; j < n; j++) {
                cin >> p[i][j];
            }
        }
        findPath(0, 0, p, n);
    
        int x = 0;
        if (!path.empty()) {
            while (!path.empty()) {
                auto point = path.top();
                cout <<'['<< point.x << "," << point.y <<"]--";
                if ((++x)%4 == 0) {
                    cout << endl;
                }
                path.pop();
            }
            cout << "END";
            
        } else {
            cout << "no path";
        }
    
        cout << endl;
        for (int i = 0; i < n; i++) {
            delete p[i];
        }
        delete []p;
    }
    return 0;
}

队列

先进先出

初始化

#include<queue>
using namespace std;
queue<string> q;

方法

• empty
  Test whether container is empty (public member function )
• size
  Return size (public member function )
• front
  Access next element (public member function )
• back
  Access last element (public member function )
• push
  Insert element (public member function )
• emplace
  

Construct and insert element (public member function )

// queue::emplace
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue
#include <string>         // std::string, std::getline(string)

int main ()
{
  std::queue<std::string> myqueue;

  myqueue.emplace ("First sentence");
  myqueue.emplace ("Second sentence");

  std::cout << "myqueue contains:\n";
  while (!myqueue.empty())
  {
    std::cout << myqueue.front() << '\n';
    myqueue.pop();
  }

  return 0;
}

Output:

 myqueue contains: 
 First sentence 
 Second sentence

• pop
  Remove next element (public member function )
• swap
  Swap contents (public member function )

应用

DS队列—-银行单队列多窗口模拟

//
//  main.cpp
//  DS队列----银行单队列多窗口模拟
//
//  Created by Jacky on 2021/4/1.
//

/*
问题 D: DS队列----银行单队列多窗口模拟
时间限制: 1 Sec  内存限制: 128 MB
提交: 180  解决: 126
[提交][状态][讨论版]
题目描述
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间。

输入
输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。

输出
在一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。

样例输入
9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3
样例输出
6.2 17 62
*/
#include <iostream>
#include <iomanip>
#include <queue>
using namespace std;

typedef struct Customer {
    int t;
    int p;
    int wait;
}Customer;

typedef struct window {
    bool busy;
    int finish;
}Window;

// 排队队列
queue<Customer>q;

int main() {
    int n, t, p, k, global_time = 0, max_wait = 0, finish_time = 0;
    float avg_wait = 0;
    cin >> n;
    // 客户到达时间 T 和事务处理时间 P
    for (int i = 0; i < n; i++) {
        cin >> t >> p;
        q.push({t, p, 0});
    }
    // 银行窗口
    cin >> k;
    auto win = new window[k];
    // 每秒情况
    while (!q.empty()) {
        // 顾客已到
        if (q.front().t <= global_time) {
            // 检查窗口状态
            for (int i = 0; i < k; i++) {
                if (global_time >= win[i].finish) {
                    win[i].busy = false;
                }
            }
            
            for (int i = 0; i < k; i++) {
                if (!win[i].busy && (!q.empty()) && (global_time >= q.front().t)) {
                    win[i].busy = true;
                    q.front().wait = global_time - q.front().t;
                    avg_wait += q.front().wait;
                    win[i].finish = global_time + q.front().p;
                    
                    if (q.front().wait > max_wait) {
                        max_wait = q.front().wait;
                    }
                    if (win[i].finish > finish_time) {
                        finish_time = win[i].finish;
                    }
                    // cout << q.front().t << " " << global_time << " " << q.front().t << " " << q.front().wait << " " << q.front().finish << endl;
                    q.pop();
                }
            }
            
        }
        global_time++;
    }

    avg_wait /= n;
    
    cout << fixed << setprecision(1) << avg_wait << " " << max_wait << " " << finish_time << endl;
    delete [] win;
    return 0;
}

串

字符串

常用方法

• operator=
  String assignment (public member function )

Iterators:

• begin
  Return iterator to beginning (public member function )
• end
  Return iterator to end (public member function )

Capacity:

• size
  Return length of string (public member function )
• length
  Return length of string (public member function )
• clear
  Clear string (public member function )
• empty
  Test if string is empty (public member function )

Element access:

• [operator[]]
  Get character of string (public member function )
• back
  Access last character (public member function )
• front
  Access first character (public member function )

Modifiers:

• operator+=
  Append to string (public member function )
• append
  Append to string (public member function )
• push_back
  Append character to string (public member function )
• assign
  Assign content to string (public member function )
• insert
  

Insert into string (public member function )

// inserting into a string
#include <iostream>
#include <string>

int main ()
{
  std::string str="to be question";
  std::string str2="the ";
  std::string str3="or not to be";
  std::string::iterator it;

  // used in the same order as described above:
  str.insert(6,str2);                 // to be (the )question
  str.insert(6,str3,3,4);             // to be (not )the question
  str.insert(10,"that is cool",8);    // to be not (that is )the question
  str.insert(10,"to be ");            // to be not (to be )that is the question
  str.insert(15,1,':');               // to be not to be(:) that is the question
  it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
  str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
  str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

  std::cout << str << '\n';
  return 0;
}

Output:

to be, or not to be: that is the question... 

• erase
  

Erase characters from string (public member function )

// string::erase
#include <iostream>
#include <string>

int main ()
{
  std::string str ("This is an example sentence.");
  std::cout << str << '\n';
                                           // "This is an example sentence."
  str.erase (10,8);                        //            ^^^^^^^^
  std::cout << str << '\n';
                                           // "This is an sentence."
  str.erase (str.begin()+9);               //           ^
  std::cout << str << '\n';
                                           // "This is a sentence."
  str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
  std::cout << str << '\n';
                                           // "This sentence."
  return 0;
}

Output:

This is an example sentence. 
This is an sentence. 
This is a sentence. 
This sentence.

• replace
  Replace portion of string (public member function )
  

//              源字符串中的位置       替换串的长度             替换的字符串
string& replace (size_t pos,        size_t len,        const string& str);
//              源字符串中的位置       源字符串中的位置          替换的字符串
string& replace (const_iterator i1, const_iterator i2, const string& str);
//              源字符串中的位置       替换的长度               替换的字符串
string& replace (size_t pos,        size_t len,        const string& str,
//               子串的起始位置       替换的子串长度
                 size_t subpos, size_t sublen);

• pop_back
  Delete last character (public member function )

String operations:

• find
  Find content in string (public member function )// 目标字符串 起始位置 size_t find (const string& str, size_t pos = 0) const noexcept;
• rfind
  Find last occurrence of content in string (public member function )
• substr
  Generate substring (public member function )
  

//                 起始位置     长度 [pos,pos+len), 默认为 [pos, str.length())
string substr (size_t pos = 0, size_t len = npos) const;

// string::substr
#include <iostream>
#include <string>

int main ()
{
  std::string str="We think in generalities, but we live in details.";
                                           // (quoting Alfred N. Whitehead)
  std::string str2 = str.substr (3,5);     // "think"
  std::size_t pos = str.find("live");      // position of "live" in str
  std::string str3 = str.substr (pos);     // get from "live" to the end
  std::cout << str2 << ' ' << str3 << '\n';

  return 0;
}

Output:

think live in details. 

Member constants

• npos
  Maximum value for size_t (public static member constant )

Non-member function overloads

• operator+
  Concatenate strings (function )
• getline
  Get line from stream into string (function )

KMP 算法

朴素模式匹配算法

#include <iostream>
#include <string>
using namespace std;
 
class myString {
private:
    string mainstr;
    long int size;
     
    void GetNext(string p, int next[]);
    int KMPFind(string p, int pos, int next[]);
public:
    myString();
    ~myString();
    void SetVal(string sp);
    long int KMPFindSubstr(string p, int pos);
};
 
myString::myString() {
    size = 0;
    mainstr = "";
}
 
myString::~myString() {
    size = 0;
    mainstr = "";
}
 
void myString::GetNext(string p, int next[]) {
    int i = 0, j = -1;
    next[i] = j;
    auto length = p.length();
    while (i < length) {
        if (j == -1 || p[i] == p[j]) {
            ++i; ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}
 
int myString::KMPFind(string p, int pos, int next[]) {
    int i = 0, j = 0;
    int length = (int)p.length();
 
    while (i < size && j < length) {
        if (j == -1 || mainstr[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == length) {
        return i - j + 1;
    }
    return 0;
}

void myString::SetVal(string sp) {
    mainstr = "";
    mainstr.assign(sp);
    size = mainstr.length();
}
 
long int myString::KMPFindSubstr(string p, int pos) {
    auto L = p.length();
    auto *next = new int[L];
    GetNext(p, next);
    for (auto i = 0; i < L; i++) {
        cout << next[i] << ' ';
    }
    cout << endl;
    int v = -1;
    v = KMPFind(p, pos, next);
     
    delete []next;
     
    return v;
}

 
int main() {
    int t;
    string main, pattern;
    cin >> t;
     
    while (t--) {
        cin >> main >> pattern;
        myString s;
        s.SetVal(main);
        cout << s.KMPFindSubstr(pattern, 0) << endl;
    }
     
    return 0;
}

数组

• 这里的数组不局限于 C 语言的数组，为更广义的概念
• 数组元素为特定数据结构，那么元素也可以是数组
• 二维数组，三位数组…

树和二叉树

根：没有前驱 叶子：没有后继 森林：多棵不相交的树的集合

有序树：结点各子树从左到右有序 无序数：结点各子树可互换位置

父节点：直接前驱 子节点：直接后继 兄弟节点：统一前驱下的节点

堂兄弟：父节点位于同一层 祖先：根节点到该结点分支所有节点 子孙：该节点下层子树任意节点

结点：树的数据元素 结点的度：结点的子节点数量

结点的层次：根节点到该节点层数 终端结点：度为0的节点，叶子 分支节点：度不为零的节点

数的度：所有结点的度的最大值 树的深度：最大的层数

二叉树

性质

• 所有节点的度不大于2的树形结构
• 子树有左右之分，次序不能任意颠倒
• 在二叉树的第i层上至多有  个结点
• 深度为 k 的二叉树至多有  个结点
• 对于任意一棵二叉树，若2度的结点数有  个，则叶子数 
• 满二叉树：一棵深度为k且有  个结点的二叉树。每层都充满结点。
• 完全二叉树：深度为k，有n个结点的二叉树，其每个节点都与深度为k的满二叉树中编号从1-n对应。只有最后一层叶子不满，且叶子全都集中在左边。
• 具有n个结点的完全二叉树的深度为[]+1
• 对完全二叉树，若从上至下、从左至右
  • 从0开始编号，编号为 i 的结点，其左孩子编号为 2i+1，右孩子编号为 2i+2
  • 从1开始编号，编号为 i 的结点，其左孩子编号为 2i，右孩子编号为 2i+1
  • 父节点编号为[i/2]

模板

//
//  main.cpp
//  DS二叉树--二叉树构建与遍历(含代码框架)
//
//  Created by Jacky on 2021/4/20.
//

#include <iostream>
#include <string>
using namespace std;
class BiTreeNode {
public:
    char data;
    //结点数据
    BiTreeNode *LeftChild;
    //左子树指针
    BiTreeNode *RightChild;
    //右子树指针
    BiTreeNode() : LeftChild(NULL), RightChild(NULL) {}
    ~BiTreeNode() {}
};
class BiTree {
private:
    BiTreeNode *Root;
    //根结点指针
    int pos;
    string strTree;
    BiTreeNode *CreateBiTree();
    void PreOrder(BiTreeNode *t);
    void InOrder(BiTreeNode *t);
    void PostOrder(BiTreeNode *t);

public:
    BiTree(){};
    //构造函数
    ~BiTree(){};
    //析构函数
    void CreateTree(string TreeArray);  //利用先序遍历结果创建二叉树
    void PreOrder();
    //前序遍历
    void InOrder();
    //中序遍历
    void PostOrder();
    //后序遍历
};  //构造二叉树，利用先序遍历结果建树
void BiTree::CreateTree(string TreeArray)  //公有函数，对外接口
{
    pos = 0;
    strTree.assign(TreeArray);
    Root = CreateBiTree();
}

BiTreeNode *BiTree::CreateBiTree()  //递归建树，私有函数，类内实现
{
    BiTreeNode *T;
    char ch;
    ch = strTree[pos++];
    if (ch == '0')
        T = NULL;
    else {
        T = new BiTreeNode();
        T->data = ch;                    //生成根结点
        T->LeftChild = CreateBiTree();   //构造左子树
        T->RightChild = CreateBiTree();  //构造右子树
    }
    return T;
}

//定义先序遍历函数
void BiTree::PreOrder()  //公有函数，对外接口
{
    PreOrder(Root);
}
void BiTree::PreOrder(BiTreeNode *t) {  //私有函数，类内实现
    //若结点t不空，执行以下操作
    if (t != NULL) {
        //1、输出当前结点t的数据，表示t已访问
        cout << t->data;
        //2、先序遍历t的左孩子
        PreOrder(t->LeftChild);
        //3、先序遍历t的右孩子
        PreOrder(t->RightChild);
    }
}
//定义中序遍历函数
void BiTree::InOrder()  //公有函数，对外接口
{
    InOrder(Root);
}
void BiTree::InOrder(BiTreeNode *t) {  //私有函数，类内实现
    //若结点t不空，执行以下操作
    if (t != NULL) {
        //1、中序遍历t的左孩子
        InOrder(t->LeftChild);
        //2、输出当前结点t的数据，表示t已访问
        cout << t->data;
        //3、中序遍历t的右孩子
        InOrder(t->RightChild);
    }
}
//后序遍历函数
void BiTree::PostOrder()  //公有函数，对外接口
{
    PostOrder(Root);
}
void BiTree::PostOrder(BiTreeNode *t) {  //私有函数，类内实现
    //若结点t不空，执行以下操作
    if (t != NULL) {
        //1、后序遍历t的左孩子
        PostOrder(t->LeftChild);
        //2、后序遍历t的右孩子
        PostOrder(t->RightChild);
        //3、输出当箭结点t的数据，表示t已访问
        cout << t->data;
    }
}

int main() {
    int t;
    string s;
    cin >> t;
    while (t--) {
        cin >> s;
        BiTree bt;
        bt.CreateTree(s);
        bt.PreOrder();
        cout << endl;
        bt.InOrder();
        cout << endl;
        bt.PostOrder();
        cout << endl;
    }
    return 0;
}

层次遍历

void LevelOrder(BiTreeNode * t) {
        queue<BiTreeNode *>tq;
        BiTreeNode *p = t;
        // 设 p 是指向当前节点的指针变量，如果 p 不空，p 入队，然后执行以下循环
        if (p) {
            tq.push(p);
            // 当队列不空
            while (!tq.empty()) {
                // 把队首元素出队到p，注意这里代码不止1行
                p = tq.front();
                tq.pop();
                // 输出 p 的数据，表示p已遍历
                if (p) {
                    cout << p->data;
                    // 把 p 的左右节点以此入队
                    tq.push(p->LeftChild);
                    tq.push(p->RightChild);
                }
            }
        }
    }

后序遍历非递归

void PostOrder() {
        stack<BiTreeNode *>s1;
        stack<BiTreeNode *>s2;
        auto T = Root;
        if(!T) return;
        auto p = T;
        do {
            if (p) {
                // 若 p 不空，p进栈s1，tag赋值0进栈s2
                s1.push(p);
                auto tag = new BiTreeNode(0);
                s2.push(tag);
                // p = p->Lchild, 跳转1
                p = p->LeftChild;
                continue;
            }
            if (s1.empty()) {
                break;
            }
            if (!p) {
                auto tag = s2.top();
                if (tag->tag == 0) {
                    tag->tag = 1;
                    p = s1.top()->RightChild;
                } else {
                    p = s1.top();
                    s1.pop();
                    s2.pop();
                    cout << p->data;
                    p = NULL;
                }
            }
        } while (!s1.empty());
    }

赫夫曼树构建

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
 
const int MaxW = 9999999;  // 假设结点权值不超过9999999
// 定义huffman树结点类
class HuffNode
{
public:
    int weight;     // 权值
    int parent;     // 父结点下标
    int leftchild;  // 左孩子下标
    int rightchild; // 右孩子下标
};
// 定义赫夫曼树类
class HuffMan
{
private:
    void MakeTree();    // 建树，私有函数，被公有函数调用
    void SelectMin(int pos, int *s1, int*s2);  // 从 1 到 pos 的位置找出权值最小的两个结点，把结点下标存在 s1 和 s2 中
public:
    int len;    // 结点数量
    int lnum;   // 叶子数量
    HuffNode *huffTree; // 赫夫曼树，用数组表示
    string *huffCode;   // 每个字符对应的赫夫曼编码
    void MakeTree(int n, int wt[]); // 公有函数，被主函数main调用
    void Coding();  // 公有函数，被主函数main调用
    void Destroy();
};
// 构建huffman树
void HuffMan::MakeTree(int n, int wt[])
{
    // 参数是叶子结点数量和叶子权值
    // 公有函数，对外接口
    int i;
    lnum = n;
    len = 2 * n - 1;
    huffTree = new HuffNode[2 * n];
    huffCode = new string[lnum + 1];    // 位置从 1 开始计算
    // huffCode实质是个二维字符数组，第 i 行表示第 i 个字符对应的编码
    // 赫夫曼树huffTree初始化
    for(i = 1; i <= n; i ++)
        huffTree[i].weight = wt[i - 1]; // 第0号不用，从1开始编号
    for(i = 1; i <= len; i ++)
    {
        if(i > n) huffTree[i].weight = 0;  // 前n个结点是叶子，已经设置
        huffTree[i].parent = 0;
        huffTree[i].leftchild = 0;
        huffTree[i].rightchild = 0;
    }
    MakeTree();  // 调用私有函数建树
}
void HuffMan::SelectMin(int pos, int *s1, int *s2)
{
    // 找出最小的两个权值的下标
    // 函数采用地址传递的方法，找出两个下标保存在 s1 和 s2 中
    int w1, w2, i;
    w1 = w2 = MaxW;  // 初始化w1和w2为最大值，在比较中会被实际的权值替换
    *s1 = *s2 = 0;
    for(i = 1; i <= pos; i ++)
    {
        // 比较过程如下：
        // 如果第 i 个结点的权值小于 w1，且第 i 个结点是未选择的结点，提示：如果第 i 结点未选择，它父亲为 0
        if (huffTree[i].weight < w1 && huffTree[i].parent == 0) {
            // 把第 w1 和 s1 保存到 w2 和 s2，即原来的第一最小值变成第二最小值
            w2 = w1;
            *s2 = *s1;
            // 把第 i 结点的权值和下标保存到 w1 和 s1，作为第一最小值
            w1 = huffTree[i].weight;
            *s1 = i;
        } else {
            // 否则，如果第 i 结点的权值小于 w2，且第 i 结点是未选择的结点
            if (huffTree[i].weight < w2 && huffTree[i].parent == 0) {
                // 把第 i 结点的权值和下标保存到 w2 和 s2，作为第二最小值
                w2 = huffTree[i].weight;
                *s2 = i;
            }
        }
    }
}
void HuffMan::MakeTree()
{
    // 私有函数，被公有函数调用
    int i, s1, s2;
    for(i = lnum + 1; i <= len; i ++)
    {
        SelectMin(i - 1, &s1, &s2);  // 找出两个最小权值的下标放入 s1 和 s2 中
        // 将找出的两棵权值最小的子树合并为一棵子树，过程包括
        // 结点 s1 和结点 s2 的父亲设为 i
        huffTree[s1].parent = huffTree[s2].parent = i;
        // 结点 i 的左右孩子分别设为 s1 和 s2
        huffTree[i].leftchild = s1;
        huffTree[i].rightchild = s2;
        // 结点 i 的权值等于 s1 和 s2 的权值和
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
    }
}
// 销毁赫夫曼树
void HuffMan::Destroy()
{
    len  = 0;
    lnum = 0;
    delete []huffTree;
    delete []huffCode;
}
// 赫夫曼编码
void HuffMan::Coding()
{
    char *cd;
    int i, c, f, start;
    // 求 n 个结点的赫夫曼编码
    cd = new char[lnum];    // 分配求编码的工作空间
    cd[lnum - 1] = '\0';    // 编码结束符
    for(i = 1; i <= lnum; ++ i)
    {
        // 逐个字符求赫夫曼编码
        start = lnum - 1;   // 编码结束符位置
        // 参考课本P147算法6.12 HuffmanCoding代码
        for (c = i, f = huffTree[i].parent; f!=0; c = f, f = huffTree[f].parent) {
            if (huffTree[f].leftchild == c) cd[--start] = '0';
            else cd[--start] = '1';
        }
        huffCode[i].assign(&cd[start]); // 把cd中从start到末尾的编码复制到huffCode中
    }
    delete []cd;    // 释放工作空间
}
// 主函数
int main()
{
    int t, n, i, j;
    int wt[800];
    HuffMan myHuff;
    cin >> t;
    for(i = 0; i < t; i++)
    {
        cin >> n;
        for(j = 0; j < n; j++)
        {
            cin >> wt[j];
        }
        myHuff.MakeTree(n, wt);
        myHuff.Coding();
        for(j = 1; j <= n; j ++)
        {
            cout << myHuff.huffTree[j].weight << '-';   // 输出各权值
            cout << myHuff.huffCode[j] << endl; // 输出各编码
        }
        myHuff.Destroy();
    }
    return 0;
}

赫夫曼解码

#include <cstring>
#include <iostream>
#include <string>
#define ok 1
#define error -1
using namespace std;

const int MaxW = 9999999;  // 假设结点权值不超过9999999
// 定义huffman树结点类
class HuffNode {
public:
    int weight;      // 权值
    int parent;      // 父结点下标
    int leftchild;   // 左孩子下标
    int rightchild;  // 右孩子下标
};
// 定义赫夫曼树类
class HuffMan {
private:
    void MakeTree();  // 建树，私有函数，被公有函数调用
    void SelectMin(
        int pos, int *s1,
        int *
            s2);  // 从 1 到 pos 的位置找出权值最小的两个结点，把结点下标存在 s1 和 s2 中
public:
    int len;                         // 结点数量
    int lnum;                        // 叶子数量
    HuffNode *huffTree;              // 赫夫曼树，用数组表示
    char value[800];
    void MakeTree(int n, int wt[], char cd[]);  // 公有函数，被主函数main调用
    void Coding();                   // 公有函数，被主函数main调用
    void Destroy();
    int Decode(const string codestr, char txtstr[]);
};
// 构建huffman树
void HuffMan::MakeTree(int n, int wt[], char cd[]) {
    // 参数是叶子结点数量和叶子权值
    // 公有函数，对外接口
    int i;
    lnum = n;
    len = 2 * n - 1;
    huffTree = new HuffNode[2 * n];
    for (int i = 0; i < n; i++) {
        value[i] = cd[i];
    }
    // huffCode实质是个二维字符数组，第 i 行表示第 i 个字符对应的编码
    // 赫夫曼树huffTree初始化
    for (i = 1; i <= n; i++)
        huffTree[i].weight = wt[i - 1];  // 第0号不用，从1开始编号
    for (i = 1; i <= len; i++) {
        if (i > n) huffTree[i].weight = 0;  // 前n个结点是叶子，已经设置
        huffTree[i].parent = 0;
        huffTree[i].leftchild = 0;
        huffTree[i].rightchild = 0;
    }
    MakeTree();  // 调用私有函数建树
}
void HuffMan::SelectMin(int pos, int *s1, int *s2) {
    // 找出最小的两个权值的下标
    // 函数采用地址传递的方法，找出两个下标保存在 s1 和 s2 中
    int w1, w2, i;
    w1 = w2 = MaxW;  // 初始化w1和w2为最大值，在比较中会被实际的权值替换
    *s1 = *s2 = 0;
    for (i = 1; i <= pos; i++) {
        // 比较过程如下：
        // 如果第 i 个结点的权值小于 w1，且第 i 个结点是未选择的结点，提示：如果第 i 结点未选择，它父亲为 0
        if (huffTree[i].weight < w1 && huffTree[i].parent == 0) {
            // 把第 w1 和 s1 保存到 w2 和 s2，即原来的第一最小值变成第二最小值
            w2 = w1;
            *s2 = *s1;
            // 把第 i 结点的权值和下标保存到 w1 和 s1，作为第一最小值
            w1 = huffTree[i].weight;
            *s1 = i;
        } else {
            // 否则，如果第 i 结点的权值小于 w2，且第 i 结点是未选择的结点
            if (huffTree[i].weight < w2 && huffTree[i].parent == 0) {
                // 把第 i 结点的权值和下标保存到 w2 和 s2，作为第二最小值
                w2 = huffTree[i].weight;
                *s2 = i;
            }
        }
    }
}
void HuffMan::MakeTree() {
    // 私有函数，被公有函数调用
    int i, s1, s2;
    for (i = lnum + 1; i <= len; i++) {
        SelectMin(i - 1, &s1, &s2);  // 找出两个最小权值的下标放入 s1 和 s2 中
        // 将找出的两棵权值最小的子树合并为一棵子树，过程包括
        // 结点 s1 和结点 s2 的父亲设为 i
        huffTree[s1].parent = huffTree[s2].parent = i;
        // 结点 i 的左右孩子分别设为 s1 和 s2
        huffTree[i].leftchild = s1;
        huffTree[i].rightchild = s2;
        // 结点 i 的权值等于 s1 和 s2 的权值和
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
    }
}
// 销毁赫夫曼树
void HuffMan::Destroy() {
    len = 0;
    lnum = 0;
    delete[] huffTree;
}

int HuffMan::Decode(const string codestr, char *txtstr) {
    //编码串是codestr，解码结果放在txtstr中
    //编码0表示往左孩子移动，编码1表示往右孩子移动
    int i, k, c;
    char ch = '\0';
    c = len;  //c表示结点数组的下标
    //根结点是结点数组的最后一个结点，所以c一开始指向根结点

    k = 0;  //txtstr的指针
    for (i = 0; i < codestr.length(); i++) {
        //解码流程如下:
        //取编码串的第i个字符放入变量 ch
        ch = codestr[i];
        // 如果ch是字符0，表示往左孩子移动，则c跳转到左孩子
        if (ch == '0') {
            c = huffTree[c].leftchild;
        } else if (ch == '1') {
            // 如果ch是字符1，表示往右孩子移动，则c跳转到右孩子
            c  = huffTree[c].rightchild;
        } else {
            // 如果ch非0非1，表示编码传有错误，返回error表示解码失败
            return error;
        }
        if (huffTree[c].leftchild == 0 && huffTree[c].rightchild == 0) {
            // 如果c指向的节点是否是叶子
            // 解码串txtstr的第k位置保存节点c内的字符
            txtstr[k] = value[c-1];
            k++;
            //c跳回根节点
            c = len;
        } else {
            // 否则
            ch = '\0'; // 设置ch值是用于检查不完成编码的报错
        }
    }
    if (ch == '\0')
        return error;
    else
        txtstr[k] = '\0';  //解码成功，加入字符串结束符
    return ok;
}

// 主函数
int main() {
    int t, n, i, j, k;
    int wt[800];
    char cd[800];
    string huffcode;
    HuffMan myHuff;
    // 1
    cin >> t;
    for (i = 0; i < t; i++) {
        // 2
        cin >> n;
        for (j = 0; j < n; j++) {
            cin >> wt[j];
        }
        // 3
        for (j = 0; j < n; j++) {
            cin >> cd[j];
        }
        // 4
        cin >> k;
        myHuff.MakeTree(n, wt, cd);
        
        // 5
        for (j = 0; j < k; j++) {
            cin >> huffcode;
            
            char *txt = new char[n+1];
            auto err = myHuff.Decode(huffcode, txt);
            if (err == error) {
                cout << "error" << endl;
            } else {
                cout << txt << endl;
            }
            delete [] txt;
        }
    
        myHuff.Destroy();
    }
    return 0;
}

查找

静态查找

顺序查找

时间复杂度O(n)

空间复杂度O(1)

void findKey(int v, int d[], int length) {
    // 哨兵
    d[0] = v;
    int i;
    for (i = length; d[i] != v; i--);
    if (i) {
        cout << i << endl;
    } else {
        cout << "error" << endl;
    }
}

折半查找

时间复杂度O()

不适用于链式结构

int findKey(int v, int d[], int length) {
    int low = 1, high = length, mid;
    while (low <= high) {
        mid = (low+high)/2;
        if (d[mid] == v) return mid;
        else if (v < d[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

索引分块查找

/* 
	arr 顺序表
	masks 分块索引中的最大值
	index = n / k
*/
void search(int n) {
  int count = 0, flag = 0;
  for (int i = 0; i < sizeof(mark); i++) {
    count++;
    if (n <= mark[i]) {
      int start = i * index;
      int end = (i + 1) * index;
      for (int j = start; i < end; j++) {
        count++;
        if (n == arr[j]) {
          cout << j + 1 << '-' << count << endl;
          flag = 1;
        }
      }
      if (flag == 0) {
        cout << "error" << endl;
      }
    }
  }
}

动态查找

• 表结构在查找过程中动态生成
• 对于插入给定值 key
  • 若表中存在，则返回
  • 否则插入关键字等于 key 的记录

二叉排序树

#include <iostream>
using namespace std;

class TreeNode {
public:
    int data;
    TreeNode *left = NULL;
    TreeNode *right = NULL;
    TreeNode *parent = NULL;
};

class BiTree {
    TreeNode *Root = NULL;
    void InOrder(TreeNode *p) {
        if (p) {
            InOrder(p->left);
            cout << p->data << " ";
            InOrder(p->right);
        }
    }
    
    TreeNode *Insert_BST(TreeNode *T, int data) {
        if (T==NULL) {
            T = new TreeNode();
            T->data = data;
            T->left = T->right = NULL;
        } else {
            if (T->data == data) {
                return NULL; // 已有节点
            } else if (data < T->data) {
                T->left = Insert_BST(T->left, data);
            } else {
                T->right = Insert_BST(T->right, data);
            }
            
        }
        return T;
    }
  
  	void Find(bool *flag, TreeNode *t, int data, int *count) {
        if (!*flag && t) {
            (*count)++;
            if (t->data == data) {
                *flag = true;
                return; // 已有节点
            } else if (data < t->data) {
                Find(flag, t->left, data, count);
            } else {
                Find(flag, t->right, data, count);
            }
        }
   }
  
  void FindParent(TreeNode *t, TreeNode *parent) {
        if (t) {
            t->parent = parent;
            FindParent(t->left, t);
            FindParent(t->right, t);
        }
    }

    void Del(TreeNode *t, int data) {
        if (t) {
            if (data == t->data) {
                return Delete(t);
            } else if (data < t->data) {
                Del(t->left, data);
            } else Del(t->right, data);
        }
    }
    void Delete(TreeNode *p) {
        TreeNode *s;
        if (!p->left && !p->right) {
            if (p->parent->left == p) p->parent->left = NULL;
            else p->parent->right = NULL;
            delete p;
        } else if (!p->right) {
            s = p->left; *p = *s; delete s;
        } else if (!p->left) {
            s = p->right; *p = *s; delete s;
        } else {
            s = p->left;
            while (s->right) {
                s = s->right;
            }
            
            p->data = s->data;
            if (s->parent != p) {
                s->parent->right = s->left;
            } else {
                p->left = s->left;
            }
            delete s;
        }
    }
public:
    BiTree() {
        create_BST();
    }
    
    void create_BST() {
        int d, n;
        //Root = new TreeNode();
        cin >> n;
        while (n--) {
            cin >> d;
            Root = Insert_BST(Root, d);
        }
    }
    
    void Insert_BST(int data) {
        Insert_BST(Root, data);
    }
  
  	void Find(int data) {
        bool flag = false;
        int count = 0;
        Find(&flag, Root, data, &count);
        if (flag) {
            cout << count << endl;
        } else {
            cout << "-1" << endl;
        }
    }
    
    void Del(int data) {
        Del(Root, data);
    }
    
    void InOrder() {
        InOrder(Root);
        cout << endl;
    }
    
    void FindParent() {
        FindParent(Root, NULL);
    }
};

平衡二叉树

#include <iostream>
using namespace std;

#define LH 1 // 左高
#define EH 0 // 等高
#define RH -1 // 右高

class BiNode
{
    public:
        int key; // 关键值
        int bf; // 平衡因子
        BiNode *lChild, *rChild;
        BiNode() {};
        BiNode(int kValue, int bValue)
       {

           key = kValue;
           bf = bValue;
           lChild = NULL;
           rChild = NULL;
       }

       ~BiNode()
      {
           key = 0;
           bf = 0;
           lChild = NULL;
           rChild = NULL;
       }
};

// 二叉排序树
class BST
{
     private:
         BiNode *root; // 根结点指针
         void rRotate(BiNode *&p);
         void lRotate(BiNode *&p);
         void leftBalance(BiNode *&t);
         void rightBalance(BiNode *&t);
         int insertAVL(BiNode *&t, int key, bool &taller); // 插入元素并做平衡处理
         void inOrder(BiNode *p);
     public:
         BST();
         void insertAVL(int key); // 二叉排序树插入元素
         ~BST();
         void inOrder(); // 中序遍历
};

// 以p为根的二叉排序树作右旋处理
void BST::rRotate(BiNode *&p)
{
    // 参考课本236页算法9.9
    auto lc = p->lChild;
    p->lChild = lc->rChild;
    lc->rChild = p;
    p = lc;
}

// 以p为根的二叉排序树作左旋处理
void BST::lRotate(BiNode *&p)
{
    // 参考课本236页算法9.10
    auto rc = p->rChild;
    p->rChild = rc->lChild;
    rc->lChild = p;
    p = rc;
}

// t为根的二叉排序树作左平衡旋转处理
void BST::leftBalance(BiNode*& t)
{
    BiNode* l, * lr;
    l = t->lChild;
    switch (l->bf)
    {
    case LH:
        t->bf = l->bf = EH;
        rRotate(t);
        break;
    case RH:
        lr = l->rChild;
        switch (lr->bf)
        {
        case LH:
            t->bf = RH;
            l->bf = EH;
            break;
        case EH:
            t->bf = l->bf = EH;
            break;
        case RH:
            t->bf = EH;
            l->bf = LH;
            break;
        }
        lr->bf = EH;
        lRotate(t->lChild);
        rRotate(t);
    }
}

// t为根的二叉排序树作右平衡旋转处理
void BST::rightBalance(BiNode *&t)
{
     // 参考课本238页算法9.12
    auto rc = t->rChild;
    switch (rc->bf) {
        case RH:
            t->bf = rc->bf = EH;
            lRotate(t);
            break;
        
        case LH:
            auto rl = rc->lChild;
            switch (rl->bf) {
                case RH:
                    t->bf = LH;
                    rc->bf = EH;
                    break;
                
                case EH:
                    t->bf = rc->bf = EH;
                    break;
                
                case LH:
                    t->bf = EH;
                    rc->bf = RH;
                    break;
            }
            rl->bf = EH;
            rRotate(t->rChild);
            lRotate(t);
    }
}


int BST::insertAVL(BiNode*& t, int key, bool& taller)
{
    if (!t)
    {
        t = new BiNode;
        t->key = key;
        t->lChild = t->rChild = NULL;
        t->bf = EH;
        taller = true;
    }
    else
    {
        if (key == t->key)
        {
            taller = false;
            return false;
        }
        if (key < t->key)
        {
            if (!insertAVL(t->lChild, key, taller))
                return false;
            if (taller)
            {
                switch (t->bf)
                {
                case LH:
                    leftBalance(t);
                    taller = false;
                    break;
                case EH:
                    t->bf = LH;
                    taller = true;
                    break;
                case RH:
                    t->bf = EH;
                    taller = false;
                    break;
                }
            }
        }
        else {
            if (!insertAVL(t->rChild, key, taller))
                return false;
            if (taller)
            {
                switch (t->bf)
                {
                case LH:
                    t->bf = EH;
                    taller = false;
                    break;
                case EH:
                    t->bf = RH;
                    taller = true;
                    break;
                case RH:
                    rightBalance(t);
                    taller = false;
                    break;
                }
            }
        }
    }
    return true;
}

void BST::inOrder(BiNode *p)
{
    if(p)
    {
        inOrder(p->lChild);
        cout << p->key << ':' << p->bf << ' ';
        inOrder(p->rChild);
    }

    return;
}

// 二叉排序树初始化
BST::BST()
{
    root = NULL;
}

BST::~BST()
{
    root = NULL;
}

// 插入元素并作平衡处理
void BST::insertAVL(int key)
{
    bool taller = false;
    insertAVL(root, key, taller);
}


// 中序遍历
void BST::inOrder()
{
    inOrder(root);
}

int main(void)
{
    int t;
    cin >> t;
    while(t--)
    {
        // 构建二叉平衡树，并在插入元素时做平衡处理
        int n, elem;
        cin >> n;
        BST tree;
        while(n--)
        {
           cin >> elem;
           tree.insertAVL(elem);
        }
        tree.inOrder();
        cout << endl;
    }

    return 0;
}

哈希表

#include <iostream>
#include <list>
#include <map>
#define N 11
using namespace std;

class HashTable {
    map<int, list<int>> table;
public:
    void store(int n) {
        table[n%N].push_front(n);
    }
    void search(int n) {
        int count = 0;
        bool flag = false;
        for (auto it = table[n%N].begin(); it != table[n%N].end(); ++it) {
            ++count;            
            if (*it == n) {
                flag = true;
                break;
            }
        }
        if (flag) {
            cout << n%N << ' ' << count << endl;
        } else {
            table[n%N].push_front(n);
            cout << "error" << endl;
        }
    }
};

int main() {
    int n, t;
    while(cin >> n) {
        HashTable table;
        while (n--) {
            cin >> t;
            table.store(t);
        }
        
        cin >> n;
        while (n--) {
            cin >> t;
            table.search(t);
        }
        
    }
    return 0;
}

线性探测再散列

#include <iostream>
#define N 11
using namespace std;

class HashTable {
    int size;
    int *data;
    void store(int n, int hash) {
        hash %= size;
        if (data[hash] == -1) {
            data[hash] = n;
            return;
        }

        if (data[hash + 1] == -1) {
            data[hash + 1] = n;
            return;
        }
        store(n, hash + 1);
    }
    int hash(int n) {
        return n % N;
    }

public:
    HashTable(int n) {
        size = n;
        data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = -1;
        }
    }
    void store(int n) {
        store(n, hash(n));
    }
    void print() {
        for (int i = 0; i < size; i++) {
            if (data[i] != -1) {
                cout << data[i] << ' ';
            } else {
                cout << "NULL ";
            }
        }
        cout << endl;
    }
    void search(int n) {
        int h = hash(n);
        int count = 0;
        while (true) {
            count++;
            h %= size;
            if (data[h] == n) {
                cout << "1 " << count << ' ' << h + 1 << endl;
                break;
            }

            if (data[h] == -1) {
                cout << "0 " << count << endl;
                break;
            }
            h++;
        }
    }
    ~HashTable() {
        delete[] data;
    }
};

int main() {
    int t, n, tmp, size;
    cin >> t;
    while (t--) {
        cin >> size >> n;
        HashTable table(size);
        while (n--) {
            cin >> tmp;
            table.store(tmp);
        }
        table.print();
        cin >> n;
        while (n--) {
            cin >> tmp;
            table.search(tmp);
        }
    }
    return 0;
}

二次线性探测再散列

//
//  main.cpp
//  DS哈希查找—二次探测再散列
//
//  Created by Jacky on 2021/5/31.
//

#include <iostream>
#define N 11
using namespace std;
int sqr(int x) {
    return x * x;
}
class HashTable {
    int size;
    int *data;

    int hash(int n) {
        return n % N;
    }

public:
    HashTable(int n) {
        size = n;
        data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = -1;
        }
    }
    void store(int key) {
        if (data[key % 11] == -1) {
            data[key % 11] = key;
        } else {
            int flag = 1;  //1为 +，0为-
            int cnt = 1;
            while (1) {
                int hsNum;
                if (flag == 1) {
                    hsNum = (((key % 11) + sqr(cnt) % size) + size) % size;
                    flag = 0;
                } else {
                    hsNum = (((key % 11) - sqr(cnt) % size) + size) % size;
                    if (hsNum < 0) hsNum *= -1;
                    flag = 1;
                    cnt++;
                }
                if (data[hsNum] == -1) {
                    data[hsNum] = key;
                    break;
                }
            }
        }
    }
    void print() {
        for (int i = 0; i < size - 1; i++) {
            if (data[i] == -1) {
                cout << "NULL ";
            } else {
                cout << data[i] << " ";
            }
        }
        if (data[size - 1] == -1) {
            cout << "NULL" << endl;
        } else {
            cout << data[size - 1] << endl;
        }
    }
    void search(int key) {
        if (data[key % 11] == key) {
            cout << "1 1 " << key % 11 + 1 << endl;
        } else {
            int flag = 1;  //1为 +，0为-
            int cnt = 1;
            int cs = 1;
            while (1) {
                cs++;
                if (cnt == size) {
                    cout << "0 " << size << endl;
                    break;
                }
                int hsNum;
                if (flag == 1) {
                    hsNum = (((key % 11) + sqr(cnt) % size) + size) % size;
                    flag = 0;
                } else {
                    hsNum = (((key % 11) - sqr(cnt) % size) + size) % size;
                    flag = 1;
                    cnt++;
                }
                if (data[hsNum] == key) {
                    cout << "1 " << cs << " " << hsNum + 1 << endl;
                    break;
                }
                if (data[hsNum] == -1) {
                    cout << "0 " << cs << endl;
                    break;
                }
            }
        }
    }
};

int main() {
    int t, n, tmp, size;
    cin >> t;
    while (t--) {
        cin >> size >> n;
        HashTable table(size);
        while (n--) {
            cin >> tmp;
            table.store(tmp);
        }
        table.print();
        cin >> n;
        while (n--) {
            cin >> tmp;
            table.search(tmp);
        }
    }
    return 0;
}

Tire 树

//
//  main.cpp
//  DS哈希查找--Trie树
//
//  Created by Jacky on 2021/5/31.
//

#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
using namespace std;

class Node {
public:
    char data = '0';
    int count = 0;
    Node *next[26];
    Node() {
        for (int i = 0; i < 26; i++) {
            next[i] = NULL;
        }
    }
};

class Trie {
    void LevelOrder(Node *t) {
        queue<Node *> tq;
        for (int i = 0; i < 26; i++) {
            if (t[i].data != '0') {
                tq.push(&t[i]);
            }
        }
        while (!tq.empty()) {
            Node *t = tq.front();
            tq.pop();
            cout << t->data;
            for (int i = 0; i < 26; i++) {
                if (t->next[i] != NULL) {
                    tq.push(t->next[i]);
                }
            }
        }

        cout << endl;
    }

public:
    Node *root;
    Trie() {
        root = new Node[26];
    }
    void LevelOrder() {
        LevelOrder(root);
    }
};

int main() {
    Trie trie;
    int t;
    string s;
    stringstream ss;
    getline(cin, s);
    ss << s;

    string tmp;
    while (ss >> tmp) {
        auto p = trie.root;
        p[tmp[0] - 'a'].data = tmp[0];
        p[tmp[0] - 'a'].count++;
        p = &p[tmp[0]- 'a'];
        for (int i = 1; i < tmp.length(); i++) {
            if (p->next[tmp[i] - 'a'] != NULL) {
                p->next[tmp[i] - 'a']->count++;
                p = p->next[tmp[i] - 'a'];
                continue;
            }
            Node *tempNode = new Node;
            tempNode->data = tmp[i];
            tempNode->count++;
            p->next[tmp[i] - 'a'] = tempNode;
            p = p->next[tmp[i] - 'a'];
        }
    }
    trie.LevelOrder();
    cin >> t;
    while (t--) {
        cin >> tmp;
        auto p = trie.root;
        bool flag = true;
        if (p[tmp[0] - 'a'].data == '0') {
            flag = false;
        }
        p = &p[tmp[0]-'a'];
        for (int i = 1; i < tmp.length() && flag; i++) {
            if (p->next[tmp[i] - 'a']) {
                p = p->next[tmp[i] - 'a'];
            } else {
                flag = false;
            }
        }
        if (flag && p) {
            cout << p->count << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}

排序

冒泡排序

时间复杂度 O()

for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (data[j] > data[j+1]) {
                    swap(data[j], data[j+1]);
                }
            }
 }

插入排序

直接插入排序

基于顺序查找

时间复杂度 O()

空间复杂度 O(1)

是一种稳定的排序方法

// 从数组下标1开始存数据，length 为数据长度非数组长度
void InsertSort(int data[], int length) {
    int i, j;
    for (i = 2; i <= length; ++i) {
        if (data[i] < data[i-1]) {
            data[0] = data[i];
            data[i] = data[i - 1];
            for (j = i - 2; data[0] < data[j]; --j) {
                data[j+1] = data[j];
            }
            data[j+1] = data[0];
        }
        
        
        // print
        for (int k = 1; k <= length; k++) {
            cout << data[k] << ' ';
        }
        cout << endl;
    }
}

折半插入排序

基于折半查找

时间复杂度 O()

空间复杂度 O(1)

是一种稳定的排序方法

// 从数组下标1开始存数据，length 为数据长度为数据长度非数组长度
void BInsertSort(int *arr, int len) {
    for (int i = 2; i <= len; i++) {
        arr[0] = arr[i];
        int low = 1, high = i - 1;
        while (low <= high) {
            int m = (low + high) / 2;
            if (arr[0] > arr[m]) high = m - 1;
            else low = m + 1;
        }
        for (int j = i - 1; j >= high + 1; j--) {
            arr[j+1] = arr[j];
        }
        arr[high+1] = arr[0];
    }
}

希尔排序

基于逐趟缩小增量

时间复杂度 O( ~ O()

是一种不稳定的排序算法

#include <iostream>
using namespace std;

void ShellInsert(
    int data[], int length,
    int dk) {
    //作一趟希尔插入排序
    // 1. 前后记录位置的增量是dk，而不是1;
    // 2. r[0]只是暂存单元，当j<=0时，插入位置已找到。
    int i, j;
    for (i = dk + 1; i <= length; ++i)
        if (data[i] > data[i - dk]) {  // 需要做交换
            data[0] = data[i];         // 暂存在L.r[0]
            for (j = i - dk; j > 0 && (data[0] > data[j]); j -= dk)
                data[j + dk] = data[j];  // 记录后移，查找插入位置
            data[j+dk] = data[0]; // 插入
        }
}  // ShellInsert

void printData(int data[], int len) {
    for (int i = 1; i <= len; i++) {
        cout << data[i] << ' ';
    }
    cout << endl;
}

void ShellSort(
    int data[], int length, string dlta) {
    // 算法10.5 // 按增量序列dlta[0..t-1]对顺序表L作希尔排序。
    for (int k = 0; k < dlta.length(); ++k) {
        ShellInsert(data, length, dlta[k]-'0');
        printData(data, length);
    }
    cout << endl;
    
}

int main() {
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n;
        int *data = new int[n+1];
        for (int i = 1; i <= n; i++) {
            cin >> data[i];
        }

        string dlta = "";
        m = n / 2;
        while (m!=1) {
            dlta += (m+'0');
            m /= 2;
        }
        dlta += '1';
        ShellSort(data, n, dlta);
        delete []data;
    }
    
    return 0;
}

快速排序

时间复杂度 O()

空间复杂度 O()

不稳定排序，用于分割的数字可任选

int Partition(int *arr, int low, int high) {
    arr[0] = arr[low];
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) --high;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) ++low;
        arr[high] = arr[low];
    }
    arr[low] = arr[0];
    return low;
}

// usage: QuickSort(arr, 1, n);
void QuickSort(int *arr, int low, int high) {
    if (low <= high) {
        int pivot = Partition(arr, low, high);
        cout << arr[pivot] << ' ' << pivot << endl;
        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}

简单选择排序

时间复杂度 O()

空间复杂度 O(1)

稳定

void SelectSort(int *arr, int len) {
    for (int i = 0; i < len; i++) {
        int t = i;
        for (int j = i+1; j < len; j++) {
            if (arr[t] > arr[j]) {
                t = j;
            }
        }
        swap(arr[i], arr[t]);
    }
}

堆排序

时间复杂度 O()

空间复杂度 O(1)

不稳定，适用于 n较大的情况

void HeapAdjust(int *arr, int i, int n) {
    int s;
    while (2*i+1 < n) {
        s = 2*i+1;
        if (s+1<n&&arr[s] > arr[s+1]) s++;
        if (arr[i] > arr[s]) {
            swap(arr[i], arr[s]);
            i = s;
        } else {
            break;
        }
    }
}

// usage: HeapSort(arr, n);
void HeapSort(int *arr, int n) {
    int i;
    for (i = n/2; i >= 0; i--) {
        HeapAdjust(arr, i, n);
    }
    // PrintArray(arr, n);
    for (i = 1; i < n; i++) {
        swap(arr[0], arr[n-i]);
        HeapAdjust(arr, 0, n - i);
        // PrintArray(arr, n);
    }
}

2-路归并排序

时间复杂度 O(nlgn)

空间复杂度 O(n)

非递归

void MergeSort() {
        int t = 2;
        while (t < n) t *= 2;
        for (int i = 2; i < t + 1; i *= 2) {
            for (int j = 0; j < n; j += i) {
                int left = j, right = j + i / 2;
                if (right > n) break;
                int middle = right - 1;
                int temp_loc = left;
                while (left <= middle && right < j + i &&
                       right <
                           n)  //根据left,right,middle合并，合并结果存在临时数
                {
                    if (nums[left] > nums[right])  //谁大就把谁放进去
                        temp[temp_loc++] = nums[left++];
                    else
                        temp[temp_loc++] = nums[right++];
                }
                while (left <= middle)  //把剩余的也存进去
                    temp[temp_loc++] = nums[left++];
                while (right < j + i && right < n)  //把剩余的也存进去
                    temp[temp_loc++] = nums[right++];
                for (int m = j; m < j + i && m < n;
                     m++)  //将临时存的合并结果存回原数组
                {
                    nums[m] = temp[m];
                }
            }

            Print();
        }
    }

递归

#define MAXN 10001
#include <iostream>
#include <list>
using namespace std;

struct List {
    int data;
    int no;
    bool end;
} a[MAXN], B[MAXN];

list<list<List>> result[MAXN];

void Merge(List A[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) {
        B[k] = A[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (B[i].data <= B[j].data) {
            A[k] = B[i];
            i++;
        } else {
            A[k] = B[j];
            j++;
        }
    }
    while (i <= mid) {
        A[k] = B[i];
        A[k] = B[i];
        k++;
        i++;
    }
    while (j <= high) {
        A[k] = B[j];
        A[k] = B[j];
        k++;
        j++;
    }
}

void MergeSort(List A[], int low, int high, int level,
               int &resultLevel) {
    if (low < high) {
        int mid = (low + high) / 2;
        level++;
        resultLevel = level;
        MergeSort(A, low, mid, level, resultLevel);
        MergeSort(A, mid + 1, high, level, resultLevel);
        list<List> tmp;
        for (int i = low; i <= high; i++) {
            if (i == mid) {
                A[i].end = true;
            }
            tmp.push_back(A[i]);
            A[i].end = false;
        }
        result[level].push_back(tmp);
        Merge(A, low, mid, high);
    }
}

基数排序

时间复杂度 O(d(n+r))

空间复杂度 O(n+r)

稳定排序

#define N 1200
#include <iostream>
#include <list>
using namespace std;

int a[N];
list <int> l[10];

void RadixSortlth(int a[], int n, int ith) {
    for (int i = 0; i < 10; i++) {
        l[i].clear();
    }
    for (int i = 0; i < n; i++) {
        int tmp = a[i];
        for (int j = 0; j < ith; j++) {
            tmp /= 10;
        }
        l[tmp%10].push_back(a[i]);
    }
}

void MoveBack(int a[], list<int>l[]) {
    int j = 0;
    for (int i = 0; i < 10; i++) {
        cout << i << ':';
        if (l[i].empty()) {
            cout << "NULL";
        } else {
            while (!l[i].empty()) {
                a[j++] = l[i].front();
                cout << "->" << l[i].front();
                l[i].pop_front();
            }
            cout << "->^";
        }
        cout << endl;
    }
}

// Usage: RadixSort(a, n);
void RadixSort(int a[], int n) {
    int maxa = a[0];
    for (int i = 0; i < n; i++) {
        maxa = maxa > a[i] ? maxa : a[i];
    }
    int maxDigit = 0;
    for (; maxa; maxa /= 10, maxDigit++);
    for (int i = 0; i < maxDigit; i++) {
        RadixSortlth(a, n, i);
        MoveBack(a, l);
        for (int i = 0; i < n; i++) {
            cout << a[i] << ' ';
        }
        cout << endl;
    }
}

stringstream 字符串流

实用工具，非常爽。

#include <sstream>
using namespace std;

void test() {
    string v1;
    int v2;
    streamstring ss;
    ss << 1;
    ss >> v1; // int(1) 被转入 string(1)
    ss.clear(); // 清空
    ss << "2";
    ss >> v2; // string(2) 被转入 int(2)
}

int main() {
  test();
  stringstream ss;
  string s;
  getline(cin, s);
  ss << s;
  cout << ss.str() << endl;
  return 0;
}

EOF