coding笔记：典型数据结构之数组模拟浅析
sixwalter Lv6
  2023-08-05 11:14:26 2023-08-05 11:14      2k Words  10 Mins  

典型数据结构之数组模拟浅析

这里默认已经对基本的数据结构有所了解，因此重点在于数组模拟练习与总结。对于算法题而讲，使用数据模拟的好处不言而喻（速度快），是STL外的一大解题利器。

变量和代码解释都写在了注释里，可以方便之后的回顾。p.s. 为了方便，有的简单的注释就直接用英语打了，可以减少输入法的繁琐切换。

链表

单链表

  • 数据准备及初始化
1
2
3
4
5
6
7
8
9
10
11
//单链表
const int N = 100010 //就实际工程而言，定死可能不太优美，注意优化方案
int e[N];// store the value of the nodes
int ne[N];// store the ptrs of next node 
int head;// store the index of head node
int idx;// store the current available index

void init(){
    head = -1;//注意：一开始链表为空，使用-1来辨识空结点
    idx = 0;
}
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//insert to the head of the list
void add_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}
//insert the node after the k(index) node
void insert_k(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}
//remove the node after the k(index) node
void remove_k(int k){
    ne[k] = ne[ne[k]];
}
  • 应用：删除倒数第二个结点 O(n)

用一个额外的pre来保存当前遍历结点的前两个结点，只要当前结点的下一结点非空就一直遍历，否则退出循环，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void remove_l2(){
    int pre = -1;
    int cnt=0;
    int cu = head;
    while(ne[cu]!=-1){
        cnt++;
        if(cnt>1){
            if(pre==-1) pre = head;
            else pre = ne[pre];
        }
        cu = ne[cu];
	}
    remove_k(pre);
}

双链表

  • 数据准备与初始化
1
2
3
4
5
6
7
8
9
int e[N];
int l[N]; //store the pre idex of current node
int r[N]; //store the next idex of current node
int idx; // store the current available node
void init(){
    r[0]=1; // 默认0号点为左边界，1号点为右边界
    l[1]=0;
    idx = 2;
}
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// insert a node at the head of the list
void insert_left(int x){
    insert_k_right(0,x);
}
//insert a node at the end of the list
void insert_right(int x){
    insert_k_left(1,x);
}
//insert a node to the k(index) node 's left
void insert_k_left(int k, int x){
    insert_k_right(l[k],x);
}
//insert a node to the k(index) node 's right
void insert_k_right(int k, int x){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]]=idx;
    r[k] = idx++;
}
// delete the k(index) node 
void delete_k(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

栈

先进后出

  • 数据准备与初始化
1
2
int stk[N];
int tt=0;
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//push to the top of stack
void push(int x){
    stk[++tt]=x;
}
//pop the top of the stack
void pop(){
    if(tt>0) tt--;
}
//check if the stack is empty
bool isEmpty(){
    if(tt) return false;
    else return true;
}
//query the top of the stack
int top(){
    return stk[tt];
}

一种可能的优化：面向对象的封装+任意类型的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
const int N = 100010;

template<class T>
class Stack {
    T stk[N];
    int tt;
public:
    Stack(){
        init();
    }

    //init
    void init() { tt = 0; }

    // pop
    T pop() { return stk[tt--]; }

    // push
    void push(T x) { stk[++tt] = x; }

    // isempty
    bool isEmpty() {
        if (tt > 0) return false;
        else return true;
    }
    void printStack(){
        printf("--------------\n");
        for(int i =1;i<=tt;i++) printf("%c ",stk[i]);
        printf("--------------\n");
    }

    // top
    T queryTop() { return stk[tt]; }
};

队列

先进先出

  • 数据准备与初始化
1
2
3
4
5
6
7
int q[N];
int hh,tt;//指向队头和队尾元素

void init(){
    hh=0;
    tt=-1;
}
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//向队尾插入一个数
void push(int x){
    q[++tt] = x;
}
//从队头弹出一个数
int pop(){
    if(!isEmpty()) return q[hh++];
    else printf("error");
}
//判断队列是否为空
bool isEmpty(){
    if(hh>tt) return true;
    else return false;
}
//查询队头元素
int top(){
    if(!isEmpty()) return q[hh];
    else printf("error");
}

Trie

  • 概念：用于高效存储和查找字符串集合的数据结构

  • 数据准备与初始化

1
2
3
4
5
6
7
int son[N][26]; //假设只有大写字母A-Z,存储当前结点的所有子结点
int cnt[N]; //记录以i为结尾的字符串的个数
int idx; //存储当前可用的索引
//下标为0的点既是根结点又是空结点
void init(){
    idx = 1;
}
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char str[N];
// add a string to the trie
void insert(char str[]){
    if(!str[0]) return;
    int cu = 0;
    for(int i=0;str[i];i++){
        int k = str[i]-'A';
        if(!son[cu][k]) son[cu][k] = idx++;
        cu = son[cu][k];
    }
    cnt[cu]++;
}
// query the number of occurances of the string in the trie
int find_occur(char str []){
    if(!str[0]) return 0;
    int cu = 0;
    for(int i=0;str[i];i++){
        int k = str[i]-'A';
        if(!son[cu][k]) return 0;
        cu = son[cu][k];
    }
    return cnt[cu];
}

并查集

  • 概念：可以快速处理并维护

    • 将两个集合合并
    • 询问两个元素是否在一个集合中

  • 如果使用暴力解法，合并两个集合需要O(n)的时间，而并查集可以在O(1)的时间内近似完成这两个操作。

  • 数据准备与初始化

1
2
3
4
5
6
7
int fa[N]; // store the parent index of each node
// only the root node has the property of fa[root]=root'
void init(){
    int num;
    cin>>num;
    for(int i=1;i<=num;i++) fa[i]=i;
}
  • 数据操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// find the set(root) index which num x is in
int find_root(int x){
    //if current node is not root
    if(fa[x]!=x) fa[x]=find_root(fa[x]); // path compression
    return x;
}
// combine two sets which num a/b is in
void combine(int a, int b){
    int r_a = find_root(a);
    int r_b = find_root(b);
    if(r_a != r_b) fa[a]= b;
}
// query whether two num are in the same set
bool inSameSet(int a, int b){
    return find_root(a)==find_root(b);
}

堆

  • 在STL中也称为优先队列priority queue

  • 数据准备与初始化

1
2
3
4
5
6
int heap[N];//heap is a 完全二叉树
int size;
int cnt; // cnt the num of insert
int cti[N],itc[N]; // preserve a count to index mapping and a index to count mapping
// cause 2*i is the left node index and 2*i+1 is the right node index
// so we have to start at the index 1
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// swap
void myswap(int x, int y){
    swap(heap[x],heap[y]);
    swap(cti[itc[x]],cti[itc[y]]);
    swap(itc[x],itc[y]);
}
// build a heap
void buildHeap(){
    for(int i = size/2;i;i--){
        down(i);
    }
}
// up
void up(int x){
    if(x/2 && heap[x/2]>heap[x]){
        myswap(x/2,x);
        up(x/2);
    }
}
// down
void down(int x){
    int min_i = x;
    if(2*x<=size && heap[min_i]>heap[2*x]) min_i = 2*x;
    if(2*x+1<=size && heap[min_i]>heap[2*x+1]) min_i = 2*x + 1;
    if(min_i!=x) {
        myswap(min_i,x);
        down(min_i);
    }
}
// insert a num
void insert(int num){
    heap[++size] = num;
    itc[size] = ++cnt;
    cti[cnt] = size;
    up(size);
}
// output the min num of the heap
int min_val(){
    return heap[1];
}
// delete the min num of the heap
void delete_min(){
    myswap(1,size--);
    down(1);
}
// delete the kth insert num
void delete_k(int k){
    // put the num at position size of the heap(end) to the position cti[k]
    // if we don't know the itc(index to count mapping)
    // we can't update the new cti[itc[size]] which is actually cti[k]
    // so we need a two way mapping
    int tmp = cti[k]; // store this value because the function below it may change its value
    myswap(tmp, size--);
    up(tmp),down(tmp);
}
// modify the kth insert num to x
void modify_k(int k, int x){
    heap[cti[k]] = x;
    up(cti[k]),down(cti[k]);
}

哈希表

开放寻址法

以开放寻址为主例，因为开的空间小，且写起来简单；拉链法仅贴出代码

  • 数据准备与初始化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int h[N];
    //列表长度取>操作集合2倍大小的最小质数，不容易起冲突
    int null = 0x3f3f3f3f;// 该数大于10^9，一般看作最大整型，这里取不可能出现的数作为空值

    // 使用下面的函数即可得到N的大小为200003
    void find_min_prime(int x){
        for(int i=x;;i++){
            bool flag = true;
            for(int j=2;j*j<i;j++){
                if(i%j==0) {
                    flag=false;
                    break;
                }
            }
            if(flag) {
                printf("%d",i);
                break;
            }
        }
    }
    void init(){
        memset(h,0x3f,sizeof h);//将所有entry置为null
    }

  • 数据操纵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// find the index where the num should be(exists if h[index] not null) 
int find(int x){
    int k = (x%N+N)%N; // not to make it negative, compute the hash Which is often the mod operation. 
    while(h[k]!=null && h[k]!=x){
        k++;
        if(k==N) k=0;
    }
    return k;
}
// query whether the num is in the hash table
bool hasNum(int x){
    if(h[find(x)]!=null) return true;
    else return false;
}
// insert a num into hash table
void insert(int x){
    if(!hasNum(x)) h[find(x)]= x;   
}

拉链法

  • 数据准备与初始化
1
2
3
int h[N] // N = 100003 
int e[N],ne[N],idx;
memset(h,-1,sizeof h);//-1代表为空
  • 数据操纵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//拉链法
// insert a num into hash table, can be duplicate in this situation
int insert(int x){
    int k = (x%N+N)%N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k]= idx++;
}
// query whether the num is in the hash table
bool hasNum(int x){
    int k = (x%N+N)%N;
    int cu = h[k];
    while(cu!=-1) {
        if(e[cu]==x) return true;
        cu = ne[cu];
    }
    return false;
}
  • Post title：coding笔记：典型数据结构之数组模拟浅析
  • Post author：sixwalter
  • Create time：2023-08-05 11:14:26
  • Post link：https://coelien.github.io/2023/08/05/coding-solution/常用数据结构/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments