数据结构与算法

再探C语言
18k words

一、数据结构与算法：线性表

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
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
#include <stdio.h>
#include <stdlib.h>

typedef int E;  //定义顺序表存储的数据为int

struct List
{
    E *array;    //实现顺序表的底层数组
    int capacity;   //表示底层数组的容量
    int size;   //已存多少数据
};

//插入元素
_Bool insertList(struct List *list, E element, int index){
    if (index < 1 || index > list->size + 1) return 0;  //index可能非法
    if(list->size == list->capacity){   //判断顺序表是否满了，若满，则扩容。
        int newCapacity = list->capacity + (list->capacity >> 1);   //>>1 相当于/2
        E * newList = realloc(list->array, newCapacity*sizeof(E));
        if(newList == NULL) return 0;
        list->array = newList;
        list->capacity = newCapacity;
    }
    for (int i = list->size; i>=index; --i){
        list->array[i] = list->array[i-1];
    }
    list->array[index - 1] = element;
    list->size++;
    return 1;
}

//删除元素
_Bool deleteList(struct List *list,int index){
    if(index < 1 || index > list->size) return 0;

    for(int i = index - 1; i < list->size - 1; ++i){
        list->array[i] = list->array[i+1];
    }

    list->size--;

}

//活得顺序表大小
int sizeList(struct List *list){
    return list->size;
}

//获得元素
E * getList(struct List *list, int index){
    if(index < 1 || index > list->size) return NULL;
    return &list->array[index-1];
}

//查找元素
int findList(struct List *list,E element){
    for(int i = 0; i < list->size; i++){
        if(list->array[i] == element) return i + 1;
    }
    return -1;
}

/*
**
**
*/
_Bool initList(struct List *list ){
    list->array = malloc(sizeof(E)*10); //malloc开辟的内存在堆区，函数生命周期结束后还存在（需要手动释放或程序结束后由系统释放）。
    if (list->array == NULL) return 0;  //若申请内存空间失败，则返回0.
    list->capacity = 10;
    list->size = 0;
    return 1;
}

void printList(struct List *list){
    for(int i = 0; i<list->size; ++i){
        printf("%d ", list->array[i]);
    }
    printf("\n");
}

int main(int argc,int* argv)
{
    struct List * list = malloc(sizeof(struct List *));
    /*结构体指针初始化，首先不能 “= NULL”，因为指针指向一个安全的区域，不能解析。
    **也不能，不初始化，因为指针可能指向未知地址，对其操作造成的后果是未知的，
    **初始化方式有：一、在堆区开辟一个空间；二、先定义一个结构体，用指针指向他；
    */
    if(initList(list)){
        for(int i = 0; i<10; ++i){
            insertList(list,i*10,i+1);
        }
        deleteList(list,2);
        printList(list);
        printf("%d \n",*getList(list,2));
        printf("%d",findList(list,30));
    }
    else{
        printf("shibai");
    }
    free(list);
}

顺序表是一种随机存取的存储结构。

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
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
#include <stdio.h>
#include <stdlib.h>

typedef int E;  //定义顺序表存储的数据为int

struct ListNode{
    E element;
    struct ListNode *next;
};

typedef struct ListNode* Node;

void initList(Node node){
    node->next = NULL;

}

_Bool insertList(Node head, E element, int index){
    if(index < 0) return 0;
    while(--index){
        head = head->next;
        if(head == NULL) return 0;
    }
    Node node = malloc(sizeof(struct ListNode));
    if(node == NULL) return 0;
    node->element = element;
    node->next = head->next;
    head->next = node;
    return 1;
}


_Bool deleteList(Node head, int index){
    if(index < 1) return 0;
    while(--index){
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;
    Node node = head->next; 
    head->next = head->next->next;
    free(node);
    return 1;
}

//获得元素；
E *getList(Node head, int index){
    if(index < 1) return 0;
    if (head->next == NULL) return NULL;    //若为空表，则返回为空；
    do{
        head = head->next;
        if(head == NULL) return NULL;
    }while(--index);
    return &head->element;
}

//寻找元素下标
int findList(Node head, E element){
    int i = 1;
    if(head->next == NULL) return -1;   //判断是否为空表
    do{
        head = head->next;
        if(head->element == element) return i;
        i++;
    }while(head->next);
    return -1;
}

int sizeList(Node head){
    int i = 0;
    while(head->next){
        i++;
        head = head->next;
    }
    return i;
}

//函数都是值传递，传值，值不变；传指针，指针不变；传指针，值会变
//对head->element或者head->next操作会改变值
void printfList(Node head){
    while(head->next){
        head = head->next;
        printf("%d ",head->element);
    }
    printf("\n");
}

int main()
{
    Node p1;
    struct ListNode head;
    initList(&head);
    for(int i = 0; i < 3; ++i){
        insertList(&head,i*10, i+1);
    }
    printfList(&head);
    printf("%d",sizeList(&head));
    
}

链表表是一种顺序访问的存储结构。

3、双向链表

4、循环链表w

5、堆栈（Stack）

先进后出

6、队列（Queue）

先进先出

实战1、反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <stdlib.h>

typedef int E;  //定义顺序表存储的数据为int

struct ListNode{
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode *tmp,*newHead = NULL;
    while (head)
    {
        //假设前面已被反转。
        tmp = head->next;	//保存第二个节点，用于当作下一个节点的头结点。
        head->next = newHead;	//指向前节点
        newHead = head;	//更新前节点
        head = tmp;	//新链表
    }
    return newHead;
}
解法二:递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <stdlib.h>




typedef int E;  //定义顺序表存储的数据为int

struct ListNode{
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

实战2、匹配字符串

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

方法：栈的应用

方法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
75
76
77
78
79
80
81
82
#include<stdio.h>
#include<string.h>
#include<stdlib.h>>

#define true 1
#define false 0

typedef char E;

struct LNode {
    E val;
    struct LNode *next;
};

typedef struct LNode* Node;

void initStack(Node head){
    head->next = NULL;
}

void printStack(Node head){
    printf("| ");
    head = head->next;
    while (head){
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

//入栈
_Bool pushStack(Node head, E val){
    Node node = malloc(sizeof(struct LNode));
    if(node == NULL) return 0;
    node->next = head->next;
    node->val = val;
    head->next = node;
    return 1;
}

//出栈
E popStack(Node head){
    if(head->next == NULL) return 0;
    Node node;
    node = head->next;
    E val = node->val;
    head->next = head->next->next;
    free(node);
    return val;
}
    
_Bool isValid(char* s) {
    struct LNode head;
    initStack(&head);
    unsigned int len = strlen(s);
    if(len % 2 == 1) return false;
    pushStack(&head,s[0]);
    for(int i = 1; i < len; i++){
        E top = popStack(&head);
        if(top != 0)pushStack(&head,top);
        if(top == '('){
            if(s[i] == ')') popStack(&head);
            else pushStack(&head,s[i]);
        }
        else if(top == '['){
            if(s[i] == ']') popStack(&head);
            else pushStack(&head,s[i]);
        }
        else if(top == '{'){
            if(s[i] == '}') popStack(&head);
            else pushStack(&head,s[i]);
        }
        else  pushStack(&head,s[i]);
    }
    if(head.next == NULL) return true;
    else return false;
}

int main(){
    char *s = "()[]{}";
    printf("%d ",isValid(s));
}
方法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
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
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef char E;

struct LNode {
    E element;
    struct LNode * next;
};

typedef struct LNode * Node;

void initStack(Node head){
    head->next = NULL;
}

_Bool pushStack(Node head, E element){
    Node node = malloc(sizeof(struct LNode));
    if(node == NULL) return 0;
    node->next = head->next;
    node->element = element;
    head->next = node;
    return 1;
}

_Bool isEmpty(Node head){
    return head->next == NULL;
}

E popStack(Node head){
    Node top = head->next;
    head->next = head->next->next;
    E e = top->element;
    free(top);
    return e;
}

bool isValid(char * s){
    unsigned long len = strlen(s);
    if(len % 2 == 1) return false;  //如果长度不是偶数，那么一定不能成功匹配
    struct LNode head;
    initStack(&head);
    for (int i = 0; i < len; ++i) {
        char c = s[i];
        if(c == '(' || c == '[' || c == '{') {
            pushStack(&head, c);
        }else {
            if(isEmpty(&head)) return false;
            if(c == ')') {
                if(popStack(&head) != '(') return false;
            } else if(c == ']') {
                if(popStack(&head) != '[') return false;
            } else {
                if(popStack(&head) != '{') return false;
            }
        }
    }
    return isEmpty(&head);
}
方法三：更快
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
char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}

二、数据结构与算法：树

1、树：理论

  • 我们一般称位于最上方的结点为树的根结点（Root）；

  • 每个结点连接的子结点数目（分支的数目），我们称为结点的度（Degree），而各个结点度的最大值称为树的度；

  • 每个结点延伸下去的下一个结点都可以称为一棵子树（SubTree）；

  • 每个结点的层次（Level）按照从上往下的顺序，树的根结点为1，每向下一层+1，比如G的层次就是3，整棵树中所有结点的最大层次，就是这颗树的深度（Depth）；

  • 与当前结点直接向下相连的结点，我们称为子结点（Child）；相反即为父节点；

  • 如果某个节点没有任何的子结点（结点度为0时）那么我们称这个结点为叶子结点；

  • 如果两个结点的父结点是同一个，那么称这两个节点为兄弟结点（Sibling）；

  • 从根结点开始一直到某个结点的整条路径的所有结点，都是这个结点的祖先结点（Ancestor）；

2、二叉树的性质

  • 性质一： 对于一棵二叉树，第i层的最大结点数量为 个2^i - 1;
  • 一棵深度为k的二叉树最大结点数量为 n = 2^k*−1，顺便得出，结点的边数为 E = n - 1。
  • 于任何一棵二叉树，如果其叶子结点个数为 n0，度为2的结点个数为 n2 ，那么两者满足以下公式：n0 = n2+1;
  • n个结点的完全二叉树深度为 k = log2^n + 1 ;

3、二叉树遍历：前序、中序、后序遍历

二叉树

前序遍历结果为：ABDECF；

中序遍历结果为：DBEACF；

后序遍历结果为：DEBFCA；

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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>>

typedef char E;

struct TreeNode{
    E element;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct TreeNode* Node;

//前序递归，利用函数栈的特性，不断出栈入栈
void preOrder(Node root){
    if(root == NULL) return;   
    printf("%c", root->element);
    preOrder(root->left);
    preOrder(root->right);
}

//中序遍历
void inOrder(Node root){
    if(root == NULL) return;
    inOrder(root->left);
    printf("%c",root->element);
    inOrder(root->right);
}

//后序遍历
void afOrder(Node root){
    if(root == NULL) return;
    afOrder(root->left);
    afOrder(root->right);
    printf("%c",root->element);
}

int main(){
    Node a = malloc(sizeof(struct TreeNode));
    Node b = malloc(sizeof(struct TreeNode));
    Node c = malloc(sizeof(struct TreeNode));
    Node d = malloc(sizeof(struct TreeNode));
    Node e = malloc(sizeof(struct TreeNode));
    Node f = malloc(sizeof(struct TreeNode));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';

    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->right = f;
    c->left = NULL;
    d->left = e->right = NULL;
    e->left = e->right = NULL;
    f->left = f->right = NULL;

    afOrder(a);
}

4、二叉树遍历：层序遍历

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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef char E;

typedef struct TreeNode {
    E element;    //存放元素
    struct TreeNode * left;   //指向左子树的指针
    struct TreeNode * right;   //指向右子树的指针
} *Node;

typedef struct initNode{   //定义队列初始节点
    Node element;
    struct initNode *next;
} *INode;

struct Queue{   //队列头尾指针
    INode front,rear;
};

typedef struct Queue* LinkedQueue;

_Bool initQueue(LinkedQueue queue){
    INode node = malloc(sizeof(struct initNode));
    if(node == NULL) return 0;
    node->next = NULL;
    queue->front = queue->rear = node;
}

//入队
_Bool enQueue(LinkedQueue quene, Node element){
    INode node = malloc(sizeof(struct initNode));
    if(node == NULL) return 0;
    node->next = NULL;
    node->element = element;
    quene->rear->next = node;
    quene->rear = node;
    return 1;
}

// 出队
Node deQueue(LinkedQueue queue){
    Node val = queue->front->next->element;
    INode node;
    node = queue->front->next;
    queue->front->next = queue->front->next->next;
    if(queue->rear == node) queue->rear = queue->front;
    free(node);
    return val;
}

_Bool isEmpty(LinkedQueue queue){
    return (queue->front == queue->rear);
}

void levelQueue(Node root){
    struct Queue queue;
    initQueue(&queue);
    enQueue(&queue,root);
    while(!isEmpty(&queue)){
        Node node = deQueue(&queue);
        printf("%c",node->element);
        if(node->left) enQueue(&queue,node->left);
        if(node->right) enQueue(&queue,node->right);
    }
}

int main(){
    Node a = malloc(sizeof(struct TreeNode));
    Node b = malloc(sizeof(struct TreeNode));
    Node c = malloc(sizeof(struct TreeNode));
    Node d = malloc(sizeof(struct TreeNode));
    Node e = malloc(sizeof(struct TreeNode));
    Node f = malloc(sizeof(struct TreeNode));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';

    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->right = f;
    c->left = NULL;
    d->left = e->right = NULL;
    e->left = e->right = NULL;
    f->left = f->right = NULL;

    levelQueue(a);
}

5、二叉树的线索化(以前序为例)

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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef char E;

typedef struct TreeNode {
    E element;    //存放元素
    struct TreeNode * left;   //指向左子树的指针
    struct TreeNode * right;   //指向右子树的指针
    char leftFlag,rightFlag     //线索化标志位
} *Node;

Node pre = NULL;  //这里我们需要一个pre来保存后续结点的指向
void treeOrdered(Node root){
    if(root == NULL) return;


    //线索化规则：结点的左指针，指向其当前遍历顺序的前驱结点；结点的右指针，指向其当前遍历顺序的后继结点。
    if(root->left == NULL){ //判断当前节点的左节点是否为空，若为空，则指向上一个节点。
        root->leftFlag = 1;
        root->left = pre;

    } 
    if(pre && pre->right == NULL){  //判断上一个节点的右节点是否为空，若为空，则指向当前节点
        pre->right = root;
        pre->rightFlag = 1;
    }

    pre = root;
    if(root->leftFlag == 0) treeOrdered(root->left);    //判断左节点是否是线索化的，若不是，才能继续。
    if(root->rightFlag == 0) treeOrdered(root->right);  //判断可略，因为，我们对右节点的线索化，是在后面执行的
}

void preOrder(Node root){ 
    while (root) {   //到头为止
        printf("%c", root->element);   //因为是前序遍历，所以直接按顺序打印就行了
        if(root->leftFlag == 0) 
            root = root->left;   //如果是左孩子，那么就走左边
        else
            root = root->right;   //如果左边指向是线索，那么就直接走右边。
    }
}

Node createNode(E element){   //单独写了个函数来创建结点
    Node node = malloc(sizeof(struct TreeNode));
    node->left = node->right = NULL;
    node->rightFlag = node->leftFlag = 0;
    node->element = element;
    return node;
}

int main() {
    Node a = createNode('A');
    Node b = createNode('B');
    Node c = createNode('C');
    Node d = createNode('D');
    Node e = createNode('E');

    a->left = b;
    b->left = d;
    a->right = c;
    b->right = e;

    treeOrdered(a);
    preOrder(a);
}

六、二叉搜索树（二叉查找树）

七、平衡二叉树

三、数据结构与算法：哈希表

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
#include<stdio.h>
#include<stdlib.h>

#define SIZE 9


//结构体指针，直接用E->key访问，避免用*E访问
typedef struct Element {   //这里用一个Element将值包装一下
    int key;    //这里元素设定为int
} * E;

typedef struct HashTable{   //这里把数组封装为一个哈希表
    E * table;
} * HashTable;

int hash(int key){   //哈希函数
    return key % SIZE;
}

void init(HashTable hashTable){   //初始化函数
    hashTable->table = malloc(sizeof(struct Element) * SIZE);
    for (int i = 0; i < SIZE; ++i)
        hashTable->table[i] = NULL;
}

void insert(HashTable hashTable, E element){   //插入操作，为了方便就不考虑装满的情况了
    int hashCode = hash(element->key);   //首先计算元素的哈希值
    hashTable->table[hashCode] = element;   //对号入座
}


_Bool find(HashTable hashTable, int key){
    int hashCode = hash(key);   //首先计算元素的哈希值
    if(!hashTable->table[hashCode]) return 0;   //如果为NULL那就说明没有
    return hashTable->table[hashCode]->key == key;  //如果有，直接看是不是就完事
}

E create(int key){    //创建一个新的元素
    E e = malloc(sizeof(struct Element));
    e->key = key;
    return e;
}

int main() {
    struct HashTable hashTable;
    init(&hashTable);
    insert(&hashTable, create(10));
    insert(&hashTable, create(7));
    insert(&hashTable, create(13));
    insert(&hashTable, create(29));

    printf("%d\n", find(&hashTable, 1));
    printf("%d\n", find(&hashTable, 13));
}

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
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
#include<stdio.h>
#include<stdlib.h>

#define SIZE 9

typedef struct ListNode {   //结点定义
    int key;
    struct ListNode * next;
} * Node;

typedef struct HashTable{   //哈希表
    struct ListNode * table;   //这个数组专门保存头结点
} * HashTable;

void init(HashTable hashTable){
    hashTable->table = malloc(sizeof(struct ListNode) * SIZE);
    for (int i = 0; i < SIZE; ++i) {
        hashTable->table[i].key = -1;   //将头结点key置为-1，next指向NULL
        hashTable->table[i].next = NULL;
    }
}


int hash(int key){   //哈希函数
    return key % SIZE;
}

Node createNode(int key){   //创建结点专用函数
    Node node = malloc(sizeof(struct ListNode));
    node->key = key;
    node->next = NULL;
    return node;
}

void insert(HashTable hashTable, int key){
    int hashCode = hash(key);
    Node head = hashTable->table + hashCode;   //先计算哈希值，找到位置后直接往链表后面插入结点就完事了
    while (head->next) head = head->next;
    head->next = createNode(key);   //插入新的结点
}

_Bool find(HashTable hashTable, int key){
    int hashCode = hash(key);
    Node head = hashTable->table + hashCode;
    while (head->next && head->key != key)   //直到最后或是找到为止
        head = head->next;
    return head->key == key;   //直接返回是否找到
}

int main(){
    struct HashTable table;
    init(&table);

    insert(&table, 10);
    insert(&table, 19);
    insert(&table, 20);

    printf("%d\n", find(&table, 20));
    printf("%d\n", find(&table, 17));
    printf("%d\n", find(&table, 19));
}