数据结构

时间复杂度、空间复杂度

算法时间复杂度以算法中基本操作重复执行的次数（简称 频度）作为算法的时间度量，只需要打字计算出相应的数量级即可

如：

O(1) < O(log2 (n)) < O(n) < O(nlog2 (n)) < O(n^2) < O(n^3) < O(2^n) < O(n!) <O(n^n)

大o表达式 T(n) = O(表达式) n —> 表示问题规模

  1. 加法规则：多项相加，保留最高阶项，并将系数化为1
    1. T(n) = n^3+n^2 +nlog2(n) + n log2(n) = n^3
  2. 乘法规则：多项相乘都保留，并将系数化为1
    1. T(n)=n*n^2 = n^3
    2. T(n) = 2n^3*3n^4 = n^7
  3. 加法乘法混合规则：小括号再乘法规则而，最后加法规则
    1. T(n)=n^2*n^3+n^3 = n^5 + n^3 = n^5
    2. T(n)=(2n+3)(2n^4+4) = 2(n)\2(n^4)=n^5

  1. T(n) = o(1)

  2. 1 2 4 8 16 32….n

    ​ 2^x = n

    ​ x = log2(n) —-> T(n) =o( log2(n))

  3. T(n)= 1+1+n+1+n+n = O(n)

  4. T(n)=o(n)*o(log2(n)) = o(nlog2(n))

  5. T(n)=o(n)*o(n)=o(n^2)

  6. T(n)=o(n)*o(n)*o(n)=o(n^3)

空间复杂度 o(1) , o(n), o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int i = 1;
//,,,,
while (i <= n) {
    i ++ ;
}
// 空间 复杂度 与 内存空间有关 
// ↑ 空间复杂度为 o(1) 与 n 的 增加 不会改变 内存的 占用

int [][] x = new int[n][n];
for (int i = 0; i < n; i ++){
    for (int j = 0; j < n; j++ ){
        x[i][j] = j;
    }
}
// 这里的 空间 复杂度为 o(n*n)

渐进符号

渐进上界

渐进下界

渐进紧致界

递归时间复杂度 空间复杂度

递归的时间复杂度 = 递归的次数*每次递归的时间复杂度

递归的空间复杂度 = 递归的次数*每次递归的空间复杂度

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
int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n-1)
}
// 递归的时间度 = 递归的次数*每次递归的时间复杂度 	
// T(n) = n * O(1) = o(n)

int f(int n) {
    int i = 1;
    if (n == 1) {
        return 1;
    }
    while (i <= n) {
        // 时间复杂度会变化
        // n , n = n-1 , n = n -2
        // a1+an/2 == (n + 1)n/2 = n^2/2 + 1/2 = n^2
        // T(n) = n^2
    }
    return n * f(n-1)
}
// 递归的时间度 = 递归的次数*每次递归的时间复杂度 	
// 递归的时间复杂度会改变
// T(n) = O(n^2)*O(n) = O(n^3)

主方法：求解递归式的快速方法

T(n) = aT(n/b) + f(n),a>=1 b>1 f(n) 是渐进的正函数

  1. 诺有常数 e > 0 由 f(n) = O(n^logb(a-e)) 则 T(n) = Q(n^logb(a))
    1. T(n) = 9T(n/3) + n
      1. a = 9, b= 3 f(n) = n ,logb(a) = 2 ,f(n) = O(n^logb(a-e)) 其中 e = 1，则T(n) = Q(n^logb(a) = Q(n^2))
  2. 若f(n) = Q(n^logb(a)((lg^k)n)) 则 T(n) = Q(n^logb(a)\lgb(a))
    1. T(n) = T(2n/3)+1
      1. a=1 , b = 3/2 f(n) = 1, logb(a) = 0 ,f(n ) =Q(n^logb(a)(lg^k)n),其中 k =0 则 T(n) = Q(nn^logb(a(lg^(k+1))n=Q(lgn)

线性结构

​ 线性结构是一种基本的数据结构，主要用于对客观时间中具有单一前驱和后继的数据关系，进行描述、线性结构的特点是数据元素之间呈现一种线性关系，级元素之间一个接一个排列

线性表

​ 线性表是一种最常用的线性结构，常用于顺序存储和链式存储，主要的基本操作是插入、删除和查找

  1. 线性表的定义

    1
    2
    3
    4
    5
    6
    1、一个线性并表示m(N>=0)个元素的有限序列，通常表示为（a1,a2,a3,a4)
    非空线性表的特点
    1、存在唯一的一个一个称作“第一个”的元素
    2、存在唯一的一个称作“最后一个”的元素
    3、除第一i给元素外，序列中的每一个元素都有一个直接前驱
    4、除最后一个元素之外，序列中的每一个元素都一个直接后驱

  2. 线性表的存储结构

    1. 顺序存储
      1. 插入元素的需要移动元素的期望值 为 E = n/2
      2. 删除元素的需要移动给元素的期望值 为 E = n-1/2

​ 插入：时间复杂度 最好o(1) 最坏o(n) 平均o(n)

​ 删除：时间复杂度 最好o(1) 最坏o(n) 平均o(n)

​ 查找：时间复杂度 最好o(1) 最坏o(1) 平均o(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
：// 代码方式 java
public class SeQuenceList {
    final int N = 10;// 容量
    
    int [] a;
    int n; // 表长
    void init() {
        a = new init[N];
        for (int i = 0; i < N / 2; i ++ )
            System.out.print([i] + " ");
        System.out.print("\n");
    }
    
    public static void main(String [] args) {
        SequenceList list = new SequenceList();
        list.init();
    }
    void insert(int x,int k) {
        // 判断是否为 合法 下不表
       	if (k < 1 || k > n + 1) return 
        for (int i = n; ; i--) {
            a[i] =  a[i - 1];
        }
        a[k - 1] = x;
        n++;
    }
    void delete(int k) {
        if （ k < 1|| k > n) return
        for (int i = k; i < n; i++) {
            a[i-1] = a[i];
        }
        n--;
    }
    void getElement(int k) {
        if (k < 1 || k > n) reutrn -1;
        return a[k-1];
    }
}

链表

 2. 链式存储(头节点和不带头节点)
      1. 概念 通过指针进行连接起来的节点，来存储数据元素，基本的节点：数据域+指针域
      2. 链表(无表头)插入的时间复杂度：最好o(1) 最坏 o(n) 平均o(n)
      3. 链表(有表头)插入的时间复杂度：最好o(1) 最坏 o(n) 平均o(n)
      4. 链表(无表头)删除的时间复杂度：最好o(1) 最坏o(n) 平均o(n)

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
public class Node {
    int data;
    Node next;
    public Node() {}
    public Node (int data) {
        this.data=data;
    }
}
// 不带头节点的 初始化方式
public class LinkList{
    Node list;
    int length;
    void initList() {
        list = null;
        list.next = null;
    }
    // 遍历链表
    void printList(Node list) {
        Node iter = list;
        while(iter!=null) {
            System.out.print(iter.data + " - ");
            iter = iter.next;
        }
    }
    // 插入
    boolean insert(int k,Node list,int data) {
        if (k < 1 || k > length + 1 ) return false;
        Node new_node  = new Node(data);  
      	if (k < 1) return false;

        Node p = list;
        if ( k == 1) {
            new_node.next = p.next;
            p.next = new_node;
            return True;
        }
        //  无头指针 [1,2,4,5,6,7]
        //			 0 1 2 3 4 5 
        while (p != null) {
            p = p.next;
        }
        if (p == null) return false;
        new_node.next = p.next;
        p.next = new_node;
        length ++;
    }
    // 删除
    boolean delete(Node list, int k) {
        if (k>length||k<=0) return false;
        
        if (k==1) {
            list=list.next;
            return true;
        }
        
        int i = 1;
        Node p = list;
        while (i < k - 1){ 
        	i++;
            p = p.next;
        }
        length --;
        reutnr true
    }
    // 查找
    Node getElement(int k,list){
        if (k>length||k<=0) return false;
        
        int i = 1;
        Node p = list
        whil(i < k) {
            i ++;
            p = p.next;
        }
        return p;
    }
}

// 带头节点的 单链表
public class HeadLinkLists(){
    Node list;
    
    void initList() {
        head = new Node();
        list.next = head;
        list.data = 0;
    }
    
      // 遍历链表
    void printList(Node list) {
        Node iter = list.next;
        while(iter!=null) {
            System.out.print(iter.data + " - ");
            iter = iter.next;
        }
    }
    // 插入
    Boolean insert (Node list,int k, int data) {
        // 要插入的 数据
        Node new_node = new Node();
        new_node.data = data;
        new_node.next = null;
        // 获取 头节点
        Node p = list;
        int i = 0;
        //  头节点 [1,2,3,5,6] --> 5 个元素  
        // 		   0 1 2 3 4   
        if (k > list.data + 2 || k < 1) return False;
        if (p == null) return False;
        while (p == null || i >= k) {
            if ( i == K-1 ){
            	new_node.next = p.next;
            	p.next = new_node;
                p.data ++;
            }
            i++;
        }
    }
    // 删除
    boolean delete(None list,int k) {
        if (k>list.data || k<=0) return false;
        
        int i  = 0;
        Node p = list;
        if(p==null) return false;
        while (i < k-1 && p != null) {
            i++;
            p = p.next;
        }
        Node s = p.next ;
        p.next = s.next;
    }
    // 查询
    Node getElement(int k,Node list) {
        if (k>list.data||k<=0) return -1;
        
        int i = 1;
        // 有头[1,23,4,5]
        //	    0 1 2 3
        Node p = head.next;
        while (i < k) {
            i ++;
            p = p.next;
        }
        return p;
        
    }
}		
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
include <stdio.h>
#include <stdlib.h>
 
 /*  单链表插入和删除  */
typedef struct Node {
    int data;
    struct Node* next;
} Node;


/* 定义头节点 */
Node* initList() {
    Node* list = (Node*)malloc(sizeof(Node));
    list->data = 0;
    list->next = NULL;
    return list;
}

/*  头插法 添加数据 */
void headInsert(Node* list, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = list->next;
    list->next = node;
    list->data++;
}
/* 尾插法 */
void tailInsert(Node* list, int data) {
    // 保存 头结点
    Node* head = list;
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    // 将链表遍历到 最后一个 结点
    list = list->next;
    while (list->next){
        list = list->next;
    }
    // 将链表最后一个结点的next 添加为 node
    list->next = node;
    head->data++;
} 

/*  删除元素 */
void delete(Node* list, int data ) {
    // 前结点
    Node* pre = list;
    // 当前结点
    Node* current = list->next;
    while (current!=NULL) {
        if (current->data == data) {
            pre->next = current->next;
            // 释放控件 
            free(current);
            list->data--;
            break;
        }else{
            // 指针下移
            pre = current;
            current = current->next;
        }
    } 
}

/*  打印链表 */
void  printList(Node* list) {
    list = list->next; 
    while(list) {
        printf("%d ", list->data);
        list = list->next;
    }
    printf("\n");
}
int main() {
    Node* list = initList();
    headInsert(list,1);
    headInsert(list,2);
    headInsert(list,3);
    tailInsert(list, 1);
    tailInsert(list, 2);
    tailInsert(list, 3);
    printList(list);
    delete(list, 1);
    delete(list, 2);
    printList(list);
    printf("%d\n",list->data);
    printf("test");
    return 0;
}

循环单链表

链表的最后一个元素的next 指向 头节点

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
61
62
63
64
65
66
67
68
// 带头节点的 单链表
public class HeadLinkLists(){
    Node list;
    
    void initList() {
        head = new Node();
        list.next = head;
        list.data = 0;
        head.next = list;
    }
    
      // 遍历链表
    void printList(Node list) {
        Node iter = list.next;
        while(iter!=list) {
            System.out.print(iter.data + " - ");
            iter = iter.next;
        }
    }
    // 插入
    Boolean insert (Node list,int k, int data) {
        // 要插入的 数据
        Node new_node = new Node();
        new_node.data = data;
        // 获取 头节点
        Node p = list;
        int i = 0;
        //  头节点 [1,2,3,5,6] --> 5 个元素  
        // 		   0 1 2 3 4   
        if (k > list.data + 2 || k < 1) return False;
        while ( i >= k) {
            if ( i == K-1 ){
            	new_node.next = p.next;
            	p.next = new_node;
                p.data ++;
            }
            i++;
        }
    }
    // 删除
    boolean delete(None list,int k) {
        if (k>list.data || k<=0) return false;
        
        int i  = 0;
        Node p = list;
        while (i < k-1 && p != null) {
            i++;
            p = p.next;
        }
        Node s = p.next ;
        p.next = s.next;
    }
    // 查询
    Node getElement(int k,Node list) {
        if (k>list.data||k<=0) return -1;
        
        int i = 1;
        // 有头[1,23,4,5]
        //	    0 1 2 3
        Node p = head.next;
        while (i < k) {
            i ++;
            p = p.next;
        }
        return p;
        
    }
}

双链表

双链表是存在一个指向前节点pre 和 下节点next

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
typedef struct Node{ int data;
    struct Node* pre;
    struct Node* next;
}Node;

// 初始化双向链表
Node* initialList() {
    Node* L = (Node*)malloc(sizeof(Node));
    L->data = 0;
    L->pre = NULL;
    L->next = NULL;
    return L;
}

// 头插法
void headInsert(Node* L, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    Node* head = L;
    node->data = data;
    if(L->data == 0){
        node->next = L->next;
        node->pre = L;
        L->next = node;
    } else {
        // 链表为空
        node->pre = L;
        node->next = L->next;
        node->next->pre = node;
        L->next = node;
    }
    L->data++;

}
// 尾插法
void tailInsert(Node* L, int data) {
    Node* head = L;
    Node* node =  (Node*)malloc(sizeof(Node));

    while(head->next!=NULL){
        head = head->next;
    }
    node->data = data;
    node->pre = head;
    node->next = head->next;
    head->next = node;    
    L->data++;
}

// 删除操作
int delete(Node* L, int data){
    Node* head = L;
    Node* current = L->next;
    while(current){
        // 判断当前的值 是否 要查找的值
        if(current->data == data){
            printf("%d",data);
            // 前一个结点 指向 后一个结点
            current->pre->next = current->next;
            // 后一个结点  指向 前一个结点
            current->next->pre = current->pre;
            free(current);
            return TRUE;
        }
        current = current->next;
        return FALSE;
    }
}
void printLinkList(Node*L) {
    Node* node = L->next;
    while(node!=NULL) {
        printf("%d -> ->",node->data);
        node = node->next;
    }
    printf("NULL\n");
}
int main(int argc, char const *argv[])
{
    /* code */
    Node* L = initialList();
    headInsert(L,1);
    headInsert(L,2);
    headInsert(L,3);
    tailInsert(L,3);
    // 3 2 1 3
    // 3 2 3
    delete(L,2);
    printLinkList(L);
    tailInsert(L,4);
    tailInsert(L,5);
    printLinkList(L);
    delete(L, 3);
    int a = delete(L, 3);
    printf("%d",a);
    printLinkList(L);
    printf("next"); 
    return 0;
}

循环双链表

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

// 双循环结构
// 定义双链表
typedef struct Node{
    int data;
    struct Node* pre;
    struct Node* next;
}Node;

// 初始化链表
Node* initialLink(){
    Node* L = (Node*)malloc(sizeof(Node));
    L->data = 0;
    L->next = L;
    L->pre = L;
}

// 头插法
void headInsert(Node* L, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data=data;
    if(data == 0){
        node->next=L;
        node->pre=L;
        L->next=node;
        L->pre=node;
    }else {
        node->next = L->next;
        node->pre = L;
        L->next->pre = node;
        L->next = node;
    }
    L->data++;
}
void printLinkList(Node* L){
    Node* head =L->next;
    while(head != L){
        printf("%d -> ",head->data);
        head=head->next;
    }
    printf("NULL\n");
}
void tailInsert(Node* L,int data){
    Node* node = (Node*)malloc(sizeof(Node));
    Node* n = L->next;
    node->data = data;
    while(n->next!=L){
        n=n->next;
    }
    node->next = L;
    node->pre = n;
    n->next = node;
    L->pre = node;
    L->data++;
}
// 删除操作
int delete(Node* L, int data) {
    Node* node = L->next;
    while(node != L){
        if(node->data == data){
            node->pre->next = node->next;
            node->next->pre = node->pre;
            free(node);
            L->data--;
            return TRUE;
        }
        node = node->next;
    }
    return FALSE;
}

int main(int argc, char const *argv[])
{
    Node* L=initialLink();
    headInsert(L, 1);
    headInsert(L, 2);
    headInsert(L, 3);
    printf("next\n");
    tailInsert(L, 3);
    tailInsert(L, 2);
    tailInsert(L, 1);
    printLinkList(L);
    delete(L,1);
    delete(L,3);
    printLinkList(L);
    return 0;
}

栈

栈的定义：栈式只能通过访问它的一端来实现数据存储和检索的一种线性表数据结构。栈的修改是按照先进后出，先进后出(Last In First Out, LIFO)线性表，

插入和删除的一端称为栈顶，另一端称为栈底，不含元素的栈称为空栈

栈的基本运算（可以使用递归）

  • 初始化栈 initStack(s) 创建以空栈
  • 判栈空 isEmpty(S) 单栈S 为 空 是 返回 真，则 返回假
  • 入栈 push(s)：将元素x加入栈顶，并更新栈顶指针
  • 出栈pop：将栈顶元素从栈中删除，并更新栈顶指针，若需要得到栈顶元素的值，可见pop定为一个返回栈顶元素的函数
  • 读栈顶元素top（s）：返回栈顶元素的值，但是不修改栈顶指针

栈的顺序存储

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
public class initStack{
    final max = 5
    int [] a = new int[max];
    int top = 0;
}

public class test {
    public boolean isEmpty(Stack s){
        if (s.top==0) return true;
        else return true
    }

    public boolean push(Stack s,int c) {
        if (s.top>=s.max) return false;
        s.a[top] = c;
     	return true
    }
    
    public boolean pop(Stack s){
        if (isEmpty(s)) return false;
        System.out.print("pop "+s.a[top]);
        s.a[top-1] = null;
        top --;
        return false;
    }
    
    public int Top(Stack s ) {
        if(isEmpty(s)) return false;
        System.out.print("top"+ s.a[top-1]);
        return a.[top-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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
/* 栈的实现 —————— 先进后出 */
typedef struct Node{
    int data;
    struct Node* next;
}Node;

/* 初始化栈 */
Node* initStack() {
    Node* S = (Node*)malloc(sizeof(Node));
    S->data = 0;
    S->next = NULL;
    return S;
}

// 判断栈 是否为空
int isEmpty(Node* S) {
    if(S->data == 0|| S->next == NULL) {
        return 1;
    }else {
        return 0;
    }
}
// 获取栈顶元素
int getTop(Node* S) {
    if(isEmpty(S)){
        return -1;
    }else {
        return S->next->data;
    }
}
// 出栈
int pop(Node* S){
    if(isEmpty(S)){
        return -1;
    }else {
        Node* node = S->next;
        int data = node->data;
        S->next = node->next;
        free(node);
        return data;
    }
}

// 如栈
void push(Node* S, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data=data;
    node->next=S->next;
    S->next = node;
    S->data++;
}
void printStack(Node* S) {
    Node* node = S->next;
    while(node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main(int argc, char const *argv[])
{
    Node* S = initStack();
    push(S,1);
    push(S,2);
    push(S,3);
    printStack(S);
    int i = pop(S);
    printf("current elem=%d\n",i);
    return 0;
}

队列

队列是先进先出线性报表，它只允许在表的一端插入元素，而在表的另一端删除元素，在队列中，插入元素的一端称为队尾(rear)、允许删除元素的一端称为对头(Front)

顺序存储

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
public class Queue {
    final int N = 6;
    int[] q = null;
    int front,rear;
}

public class TestQueue {
    
    Queue initQueue(Queue q) {
        q.q= new int [q.N];
        front = reer = 0;
    }
    
    boolean isEmpty(Queue q) {
    	if (q.front == 0 && q.rear == 0) return True;
        return false;
    }
    
    boolean enQueue(Queue q, ini data) {
        if (q.rear >= q.N) return false;
        q.data[q.rear] = data;
        q.rear ++ ;
    }
    
    boolean popQueue(Queue q) {
        if (q.front >= q.N|| isEmpty(q))return false;
        q.front ++ ;
        return True;
    }
    
    data getQueueTop(Queue q) {
        if (isEmpty(q)) return -1;
        return q.data[q.front-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
public class Queue {
    final int N = 6;
    int[] q = null;
    int front,rear;
}

public class TestQueue {
    
    Queue initQueue(Queue q) {
        q.q= new int [q.N];
        front = reer = 0;
    }
    
    boolean isEmpty(Queue q) {
    	if ((q.front == 0 && q.rear == 0)|| q.front==q.rear) return True;
        return false;
    }
    
    boolean enQueue(Queue q, ini data) {
        if (q.rear+1 == q.front) return false;
        q.data[q.rear] = data;
        q.rear = (q.rear+1)%q.N;
    }
    
    boolean popQueue(Queue q) {
        if (|| isEmpty(q))return false;
        q.front=(q.front+1)%q.N;
        return True;
    }
    
    data getQueueTop(Queue q) {
        if (isEmpty(q)) return -1;
        return q.data[q.front-1];
    }
}

队列的链式存储

存在头节点（head) 和 尾节点（rear）

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
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
}Node;

Node* initQueue() {
    Node* Q = (Node*)malloc(sizeof(Node));
    Q->data = 0;
    Q->next = NULL;
    return Q;
}
// 入队
void enQueue(Node* Q,int data) {
    Node* q = Q;
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    for(int i=0; i < Q->data; i++){
        q = q->next;
    }
    node->next = q->next;
    q->next = node;
    Q->data++;
}

// 判断队列是否为空
int isEmpty(Node* Q) {
    if(Q->data == 0|| Q->next == NULL){
        return 1;
    } else {
        return 0;
    }
}
// 出队操作
int deQueue(Node* Q) {
    // 判断队列是否为空
    if(isEmpty(Q)){
        return -1;
    }else {
        Node* node = Q->next;
        int data = node->data;
        Q->data--;
        free(node);
        return data;
    }
}
void printQueue(Node* Q) {
    Node* node = Q->next;
    while(node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main(int argc, char const *argv[])
{
    Node * Q = initQueue();
    enQueue(Q,1);
    enQueue(Q,2);
    enQueue(Q,3);
    printQueue(Q);
    int i = deQueue(Q);
    int o = deQueue(Q);
    printf("%d---",o);
    printf("%d<-->\n",i);
    // printf("%d<-->\n",o);
    return 0;
}

循环队列

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
61
62
63
64
65
66
67
68
69
70
71
/* 循环队列 front 代表开始起点  rear 代表 要 插入点 */
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5
#define TRUE 1
#define FALSE 0

typedef struct Queue {
    int front;
    int rear;
    int data[MAXSIZE];
}Queue;
Queue* initQueue() {
    Queue* Q = (Queue*)malloc(sizeof(Queue));
    Q->front  = Q->rear = 0;
    return Q;   
}
int isFull(Queue* Q) {
    if ((Q->rear+ 1) % MAXSIZE == Q->front) {
        return TRUE;
    }else {
        return FALSE;
    }
}
int enQueue(Queue* Q, int data) {
    if (isFull(Q)) {
        return TRUE;
    }else {
        Q->data[Q->rear] = data;
        Q->rear = (Q->rear + 1) % MAXSIZE;
        return TRUE; 
    }         
}
int isEmpty(Queue* Q) {
    if(Q->front == Q->rear ){
        return 1;
    }else {
        return 0;
    }
}
int deQueue(Queue* Q) {
    if(isEmpty(Q)){
        return FALSE; 
    } else { int data = Q->data[Q->front];
        Q->front = (Q->front + 1) %MAXSIZE;
        return data;
    }
}

void printQueue(Queue*Q) {
    // 要知道队列当前有多少元素
    int length = (Q->rear - Q->front + MAXSIZE)% MAXSIZE;
    int index  = Q->front; // 头指针 
    for(int i =0; i<length; i++){
        printf("%d -> ", Q->data[index]);
        index = (index + 1) % MAXSIZE;
    }
    printf("NULL\n");
}

int main(int argc, char const *argv[])
{
    Queue* Q = initQueue();
    enQueue(Q, 1);
    enQueue(Q, 2);
    enQueue(Q, 3);
    printQueue(Q);
    return 0;
}

双端队列

串（串也是有一个线性结构）

串（字符串） 一种特殊的线性表，其数据元素为字符

串的定义（子串的个数是等差数列，（n+2）(n-1)/2

串中子串的长度第 n-1项 必定是 2，首项是n ，总个数是n-1

则 sum(s) = ((an+a1)(n-1))/2 = ((n+2)\(n-1))/2

串是仅由字符构成的有限序列，是一种线性表，一般标记为S = a1a2s3…sn 其中是串名，单引号括起来的字符序列的串值

串的基本概念（空串、空格串、字串、串相等、串比较）0：48、a：65、A：97

  • 空串：长度为零的串称为空串，空串不包含任何字符

  • 空格串：由一个或多个空格组成的串，虽然空格是一个空白字符，但它也是一个字符

  • 子串：由串中任意长度的连续字符构成的序列称为子串

  • 串相等：指两个串长度相等，且对应序号的字符也相同

  • 串比较：两个串比较大小时以字符的ascii码值作为实质，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大，若是其中一个串先结束，则以串长较大者为大

串的模式匹配（子串和模式串）

朴素模式匹配

时间复杂度：最好o(m) 最坏o(n*m) 平均o(m+n)

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>

// 串 
typedef struct String {
    // 记录串的值
    char* data;

    // 记录串的字符数量
    int len;
}String;

String* initString() {
    // 初始化字符串
    String* s = (String*)malloc(sizeof(String));
    // 设置字符串为空
    s->data =NULL;
    // 当前字符串的数为0 
    s->len = 0;
    return s;
}

// 传入字符串 s 为字符串， data 为字符串值
void stringAssign(String* s, char* data) {
    // 清空 字符串 s 种已有的值
    if (s->data) {
        free(s->data);
    }
    // 定义开始字符串类的字符数为 0
    int len = 0;
    // 用于统计 data 字符串 有多少个字符串
    char* temp = data;
    while (*temp) {
        len++;
        temp++;
    }
    if(len == 0){
        // 如果没有字符 则重新初始化
        s->data = NULL;
        s->len = 0;
    }else {
        // 有值 则 遍历 将 值 赋值 给 string 的 data
        temp = data;
        s->len = len;
        s->data = (char*)malloc(sizeof(char)*(len+1));// 定义开辟 多大的 字符空间
        for (int i = 0; i < len; i++, temp ++){
            s->data[i] = * temp; // 遍历赋值
        }
    }
}
// 遍历字符串
void printString(String* s) {
    // 遍历字符串
    for (int i = 0; i  < s->len; i++) {
        printf(i == 0 ?"%c":"-> %c ",s->data[i]);
    }
}

// 暴力匹配
void forceMatch(String* master, String* sub) {
    int i = 0;
    int j = 0;
    // i 是 用于遍历 master 的 个数 j 是 用于 记录 sub 的 个数
    while (i < master->len && j <sub->len ){
        // 判断 master 和sub 下标 对应 的 数值 是否 相同 
    
        if(master->data[i] == sub->data[j]) {
            j++;
            i++;
        }else {
            i = i - j +1;
            j = 0;
        }
    }
    if (j == sub->len) {
        printf("force match success.\n");
    } else {
        printf("force match false.\n");
    }
}
int main(int argc, char const *argv[])
{
    String* s = initString();
    String* s1= initString();
    stringAssign(s1, "he0");
    printString(s1);
    stringAssign(s, "hello");
    printString(s);
    forceMatch(s,s1);
    return 0;
}

kmp算法

串的前缀：包含第一个字符并且不包含最后一个字符的字串

串的后缀：包含最后一个字符并且不包含第一个字符的子串

模式串中的next，第i个字符的next值 = 从 1 ~ i - 1 串中最长相等前后缀长度 +1

特殊情况：next[1] = 0 \ next[2] = 1

时间复杂度：o(n+m)

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/* kmp 算法 */
#include <stdio.h>
#include <stdlib.h>
typedef struct String{
    char* data;
    int len;
}String;
String* initString() {
    String* s = (String*)malloc(sizeof(String));
    s->data = NULL;
    s->len = 0;
    return s;
}
// kmp 算法 next 求值
int* getNext(String* S)  {
    int* next = (int*)malloc(sizeof(int)* S->len);
    int i = 0;
    int j = -1;
    next[i] = j;
    while (i < S->len -1 ) {
       if (j ==-1 || S->data[i] == S->data[j]){
            next[++i] = ++j ;
       } else {
            j = next [j];
       }
    }
    printf("i = %d - i -\n", i);
    printf("%d- ", S->len);
    return next;
}
void printNext(int* next , int len) {
    printf("-%d-\n", len);
    for (int i = 0; i < len; i++) {
        printf(i == 0? "%d" : "->%d" , next[i]);
    }
    printf("\n");
}
void kmpMatch(String* master , String* sub, int* next) {
    int i = 0 ;
    int j = 0 ;
    while (j == -1 || i < master->len && j < sub->len) {
        if (master->data[i] == sub->data[j]){
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if(j == sub->len){
        printf("kmp match success.\n");
    }else {
        printf("kmp match fail.\n");
    }
}
void stringAssign2(String* s, char* data) {
    if (s->data) {
        free(s->data);
    }
    int len = 0;
    char* temp = data;
    while (*temp) {
        len++;
        temp++;
    }
    if (len == 0){
        s->data = NULL;
        s->len = 0;
    }else {
        temp = data;
        s->len = len;
        // 有一个 \0 保存结尾
        s->data = (char*)malloc(sizeof(char)*(len+1));
        for (int i =0; i < len; i++, temp++){
            s->data[i] = *temp;
        }
    }
}
void printString(String* s) {
    for (int i = 0; i < s->len ; i++) {
        printf( i == 0 ? "%c":"->%c",s->data[i]);
    }
    printf("\n");
}
int main(int argc, char const *argv[])
{
    /* code */
    String* S = initString();
    String* S1 = initString();
    stringAssign2(S1, "ABCCA");
    stringAssign2(S,"ABCBABCCADABA");
    printString(S);
    printString(S1);
    int* next = getNext(S1);
    printNext(next, S1->len);
    kmpMatch(S,S1, next);
    return 0;
}

数组

一位数组：a[n] —-> L 是 元素大小 类型

内存是连续的存储空间 Loc ：数组的首地址

求算地址：第i个元素的地址 = loc+i*L

内存 a[0] a[1] a[2] a[3] a[4] a[5] int 类型

地址 0 4 8 12 16

二维数组：a[n][m] 数组首地址 loc ，元素大小L

a[2][2]

内存 a[0][0] a[0][1] a[1][0] a[1][1] int 类型

地址 0 4 8 12

按行优先 ： a[n][m]第 i行第j 个 元素的地址 = loc+i*Lm+j\L ()

按列优先：a[n][m]

内存 a[0][0] a[1][0] a[0][1] a[1][1] a[2][0]

地址 0 4 8 12 16

a[n][m] 第i行第j个元素的地址 = loc+j*nL+i\L

矩阵

对称矩阵 a[i][j] = a[j][i] 存储 主对角线和 下三角区

主对角线：

下三角区 i>j \ 上三角区 i<j

按行优先存储：存储的个数 = (n+1)n/2

第i行第j个的数组存储的位置：(i+1)i/2 + j + 1

上三角：(j+1)j/2 + i +1

三角矩阵

只有中间区域由数据，其他区域都是0

存储的工具从0开始：aij = 2i + j - 2

稀疏矩阵 零的 个数 过多、使用三元组或十字链表进行存储

使用三元组表的顺序存储结构 a[n][3] a[n][0] 存 行 a[n][1]存 列 a[n][3] 存储 数值

树 (一对多关系)

树结构是一种非线性结构，该结构 一个元素可以由两个或两个以上的直接后继元素，树可以用来描述客观世界中广泛存在的层次结构

树的定义（树域二叉树的定义）

树是是 n(n>=0) 个结点的有限阶符，当n = 0 时 称为空树，在 任意一非空树(n>0) 中，有且仅有一个称为根的结点，其余结点可分为m(m>=0) 个互不相交的有限子集t1,t2,t3,t4,t5，其中，每个T1又是一棵树，并且称为根结点的子树

树的定义时递归的，它证明了树本身固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成

树的基本概念

  1. 双亲、孩子、兄弟，结点的子树称的根称为该结点的孩子，相应的该节点成为子节点的双亲，具有相同双亲结点的或为兄弟
  2. 结点的度：一个节点的子树的个数记为该结点的度
  3. 叶子结点：叶子结点也称为终端结点，指度为0的结点
  4. 内部结点：度不为0的结点。也称为分支结点或者非终端结点，根结点除外，分支结点也称为内部结点
  5. 结点的层次：根为第一层，根的孩子为第二层，以此类推
  6. 树的高度，一颗树的高度的最大数记为书店高度（或深度）

树的性质1：树中的结点总数等于树的所有结点的度数之和加1（加1指的是根节点）

树的性质2：度为m的树中第i层上至多有m^i-1个结点(i>=1)

树的性质3：树的高度为h的m次至多有(m^b-1)/m-1 个结点

树的性质4：具有n个结点 、度为m的树的最小高度为logm(n(m-1)+1)

二叉树

二叉树是n个结点的有限阶符，它或者是空树，或者是由一个根结点及两个不相交的且分别称为左、右子树的二叉树

二叉树任意结点的度最大只能为2

  1. 二叉树性质1：第i层上最多有2^(i-1)个结点

  2. 二叉树性质2：高度为h的二叉树最多有2^h-1个结点

  3. 二叉树性质3：对于任何一棵二叉树，度为0的结点树等于度为2得到结点树+1

  4. 二叉树性质4：具有n个结点的完全二叉树的高度为log2(n)+1 取下限 或者log2(n+1) 取上限

完全二叉树

满二叉树

非完全二叉树