戊成的BLOG
数据结构（C语言）
Wucheng
  2022-03-24 03:04:23   2024-11-30 17:08:33

自主学习C语言数据结构一个小小的记录

示例代码来自bilibili@海贼胡船长的数据结构教学视频

链表

单链表

包含单链表的结构与基本操作
在示例代码中将创建新节点、删除节点等操作单独写成函数
且将链表置于 LinkList结构体中设置虚拟头节点并在其中用length记录链表的长度
感觉这样稍微有点绕圈子，但是确实在后续中调用非常方便

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

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

typedef struct LinkList
{
    ListNode head; //设置一个虚拟头节点方便指针移动
    int length; //链表的长度
}LinkList;

//————————————————————————————————————————————————————————————————

ListNode *init_listnode(int val) //初始化一个节点
{
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->data = val;
    p->next = NULL;
    return p;
}

LinkList *init_linklist()  //初始化链表
{
    LinkList *l = (LinkList *) malloc(sizeof(LinkList));
    l->head.next = NULL;
    l->length = 0;
    return l;
}

void clear_listnode(ListNode *node) //删除节点
{
    if(node == NULL) return ;
    free(node);
    return ;
}

void clear_linklist(LinkList *l) //删除链表
{
    if(l == NULL) return ;
    ListNode *p = l->head.next;
    ListNode *q; //用一个指针存放下一个节点防止链表丢失

    while (p)
    {
        q = p->next;
        clear_listnode(p);
        p = q;
    }
    free(l);
    return ;
  
}

//————————————————————————————————————————————————————————————————————

int insert(LinkList *l, int ind, int val) //在链表的第几个插入数值
{
    if(l == NULL) return 0;
    if(ind < 0 || ind > l->length) return 0;
    //判断输入的值是否合法
    ListNode *p = &(l->head);
    ListNode *node = init_listnode(val);

    while (ind--)
        p = p->next;

    node->next = p->next;
    p->next = node;
    l->length+=1;
    return 1;
  
}

int erase(LinkList *l, int ind) //删除第几个节点
{
    if(l == NULL) return 0;
    if(ind < 0 || ind >= l->length) return 0;
    //作用同上
    ListNode *p = &(l->head);
    ListNode *q;

    while (ind--)
        p = p->next;

    q = p->next->next;
    clear_listnode(p->next); 
    p->next = q;
    l->length-=1;
    return 1;

}

void output(LinkList *l) //输出链表
{
    printf("LinkList(%d):",l->length);
    for(ListNode *p = l->head.next; p; p = p->next)
        printf("%d -> ",p->data);
    printf("NULL\n");
    return ;
}

//——————————————————————————————————————————————————————————————————

#define MAX_OP 30

int main()
{
    srand(time(0));
    LinkList *l = init_linklist();

    for (size_t i = 0; i < MAX_OP; i++) //在链表的随机位置随机删除或者插入一个随机数字
    {
        int op = rand() % 3;
        int ind = rand() % (l->length + 1); //随机链表位置
        int val = rand() % 100; //随机生成的数值
        switch (op)
        {
        case 0:
        case 1: printf("insert %d to %d to LinkList = %d\n",val, ind, insert(l, ind ,val));
            break;
        case 2: printf("erase item at %d from LinkList = %d\n",ind , erase(l, ind));
            break;
        }
        output(l);
        printf("\n");
    }
    clear_linklist(l);
    return 0;
}

循环单链表

由于懒得写虚拟头节点，所以利用第一个节点的data存放链表长度
事实证明有一个虚拟头节点确实会方便很多
其他操作和单链表一样，就只写了一个简单的尾插

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

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

ListNode* init(){
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->data = 0;
    p->next = p;
    return p;
}

void inster(ListNode *L, int data){
    ListNode *q = (ListNode*)malloc(sizeof(ListNode));
    ListNode *p = L->next;
    q->data = data;
    for (int i = L->data-1; i > 0; i--)
    {
        p = p->next;
    }
    q->next = p->next;
    p->next = q;
    L->data++;
}

void output(ListNode *L){
    ListNode *p = L->next;
    printf("ListNode = ");
    for (int i = L->data; i > 0; i--)
    {
        printf("%d -> ",p->data);
        p = p->next;
    }
    printf("head\n");
  
}

int main()
{
    ListNode *l = init();

    for (size_t i = 0; i < 10; i++)
    {
        inster(l,i);
    }

    output(l);
  
}

队列与栈

单队列

在 pop出列函数中，本应有一个 q->head++语句的，但是代码运行后头指针总是在后一位数字上，在教学视频演示中并没有此错误
而将这一语句移动到 case 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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Queue
{
    int *data;
    int head,tail;
    int length;
}Queue;

Queue *init(int n) //队列初始化
{
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->head = q->tail = 0;
    q->length = n;
    return q;
}

int empty(Queue *q) //判断队列是否为控
{
    return q->head == q->tail;
}

int front(Queue *q) //返回头指针的值
{
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    return q->data[q->head];
}

void clear(Queue *q) //清除队列
{
    if(q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}

int push(Queue *q, int val) //队列插入
{
    if(q == NULL) return 0;
    if(q->tail == q->length)  return 0;
    q->data[q->tail++] = val;
    return 1;
}

int pop(Queue *q) //出列操作
{
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    //p->head++
    return 1;
}

void output(Queue *q)
{
    printf("queue = [");
    for(int i = q->head; i < q->tail; i++)
        printf(" %d ",q->data[i]);
    printf("]\n");
    return ;
}

int main()
{
    srand(time(0));
    #define MAX_OP 20
    Queue *q = init(MAX_OP);
    for (int i = 0; i < MAX_OP; i++)
    {
        int val = rand() % 100, op = rand() % 2;
        switch (op)
        {
        case 0: printf("push %d to queue = %d\n", val, push(q, val));
            break;
        case 1: printf("pop %d from queue = %d\n",front(q), pop(q));
        q->head++;
            break;
        }
        output(q);
    }
  

    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
typedef struct Queue
{
    int *data;
    int head,tail,count;
    int length;
}Queue;

Queue *init(int n)
{
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->head = q->tail = q->count = 0; //设置一个计数来记录队列长度，而不是用单纯的指针下标来记录
    q->length = n;
    return q;
}

int empty(Queue *q)
{
    return q->count == 0; //将此改为判断计数器是否为0
}

int push(Queue *q, int val)
{
    if(q == NULL) return 0;
    if(q->count == q->length) return 0;
    q->data[q->tail++] = val;
    if(q->tail == q->length) q->tail -= q->length; //当尾指针到末尾后，调转到前面
    q->count++; //入列计数增加
    return 1;
}

int pop(Queue *q)
{
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    q->head++;
    if(q->head == q->length) q->head -= q->length; //头指针同上
    q->count--; //出列计数减少
    return 1;
}

void output(Queue *q)
{
    printf("queue = [");
    for(int i = q->head, j = 0; j < q->count; j++)
    {
        int ind = (i + j) % q->length; //若尾指针在头指针前方，则要输出到尾指针可以余列队长度输出到前方
        printf(" %d",q->data[ind]);
    }
    printf("]\n");
    return ;
}

栈

栈相对于队列来说就非常简单，只需要一个指向最上方的指针，并且移动就可以了。
在随机输入输出栈的代码中也有前面单队列的问题，所以为了保证程序运行的先后，在 case 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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Stack
{
    int *data;
    int top,size;
}Stack;

Stack *init(int n)
{
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (int *)malloc(sizeof(int) * n);
    s->size = n;
    s->top = -1;
    return s;
}

void clear(Stack *s)
{
    if(s = NULL) return ;
    free(s->data);
    free(s);
    return ;
}

int empty(Stack *s)
{
    return s->top == -1;
}

int top(Stack *s)
{
    if(empty(s)) return 0;
    return s->data[s->top];
}

int push(Stack *s, int val)
{
    if(s == NULL) return 0;
    if(s->top + 1 == s->size) return 0;
    s->top++;
    s->data[s->top] = val;
    return 1;
}

int pop(Stack *s)
{
    if(s == NULL) return 0;
    if(s->top == -1) return 0;
    s->top--;
    return 1;
}

void output(Stack *s)
{
    printf("stack(%d) = [", s->top + 1);
    for (int i = s->top; i >= 0; i--)
        printf(" %d", s->data[i]);
    printf("]\n");
    return ;
}

int main()
{
    srand(time(0));
    #define MAX_OP 20
    Stack *s = init(MAX_OP);
    for (size_t i = 0; i < MAX_OP; i++)
    {
        int op = rand() % 2, val = rand() % 100;
        switch (op)
        {
        case 0: printf("push %d to stack = %d\n", val, push(s, val));
            break;
        case 1: {printf("pop %d from stack = ",top(s)); printf("%d\n",pop(s));}
            break;
        }
        output(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
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node
{
    int val;
    struct Node *lchild, *rchild;
}Node;

typedef struct Tree //树的头节点
{
    Node *root;
    int n;  //用于保存节点数量
}Tree;

Node *getNewNode(int val)   //新建树节点
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->val = val;
    p->lchild = p->rchild = NULL;
    return p;
}

Tree *getNewTree()  //新建树
{
    Tree *p = (Tree *)malloc(sizeof(Tree));
    p->root = NULL;
    p->n = 0;
    return p;
}

Node *insertNode(Node *root, int val,int *flag)  //节点插入
{
    if(root == NULL)    //当为节点为null时新建节点并返回给上一节点的指针
    {
        *flag = 1;   //当插入成功时flag值为1
        return getNewNode(val);
    }
    if(root->val == val) return root;   //当值相同时不做处理，直接返回本身
    if(val < root->val) root->lchild = insertNode(root->lchild, val, flag);  //递归调用在左叶插入比这一节点小的值
    else root->rchild = insertNode(root->rchild, val, flag); //递归调用在右叶插入比这一节点小的值
    return root;    //返回给头节点的指针
}

void insert(Tree *tree, int val)
{
    int flag = 0;   //设立一个值表示插入成功操作
    tree->root = insertNode(tree->root, val, &flag);
    tree->n += flag;    //插入成功后节点计数+1
    return ;
}

void clearNode(Node *root)  //清除节点
{
    if(root == NULL) return;
    clearNode(root->lchild);    //递归调用清除所有的节点
    clearNode(root->rchild);
    free(root);
    return ;
}

void clearTree(Tree *tree)  //清除树
{
    clearNode(tree->root);
    free(tree);
    return ;
}

void outputNode(Node *root) //以val(val(val,val),val(,val))的形式表示出树的各个节点
{
    if(root == NULL) return ;
    printf("%d", root->val);    //当前节点值
    if(root->lchild == NULL && root->rchild == NULL) return ;
    printf("(");
    outputNode(root->lchild);   //递归调用输出
    printf(",");
    outputNode(root->rchild);
    printf(")");
    return ;
}

void output(Tree *tree) //输出树
{
    printf("tree(%d) = ", tree->n);
    outputNode(tree->root);
    printf("\n");
}

int main()
{
    srand(time(0));
    Tree *tree = getNewTree();
    for (int i = 0; i < 10; i++)
    {
        int val = rand() % 100;
        insert(tree, val);
        output(tree);
    }

    return 0;  
}

二叉树的四种历遍方式

前序遍历

前序遍历就是先输出当前节点然后再输出左边的节点然后输出右边的节点，当有下一个节点有数值时输出下一个节点后再寻找所在左边的节点以此历遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void preorderNode(Node *node)
{
    if(node == NULL) return ;
    printf("%d ",node->val);
    preoederNode(node->lchild);
    preorderNode(node->rchild);
    return ;
}

void preorder(Tree *tree)
{
    printf("preorder = ");
    preorderNode(tree->root);
    return ;
}

中序遍历

优先输出左节点的值，再输出根节点的值，最后输出右节点的值，若下一节点有值优先输出下一节点的左节点的值
中序遍历对于排序二叉树的输出是一个有序的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void inorderNode(Node *node)
{
    if(node == NULL) return ;
    inoederNode(node->lchild);
    printf("%d ",node->val);
    inorderNode(node->rchild);
    return ;
}

void inorder(Tree *tree)
{
    printf("inorder = ");
    inorderNode(tree->root);
    return ;
}

后序遍历

<span style="font-size: 50px">略
和前面的一样懒得写了

层序遍历

前面三种遍历方式都比较的简单，层序遍历则需要与队列相结合
例如：

1
2
3
4
5
    10
   /  \
  4    13
 /     / \
2     11  15

首先10入队，再将左子4和右子13入队列，10出队
头指针到4后左子2入列，根4出列……
以此类推

1
2
3
4
第一次入列：10 | 4 | 13         出列10
第二次入列：4 | 13 | 2          出列4
第三次入列：13 | 2 | 11 | 15    出列13
后续没有节点    全部出列

逻辑关系为：在每次出列前输出根节点，然后入列根节点的两个子节点再出列根节点
则可得到代码（找bug写的想死）：

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
typedef struct Queue    //指向树节点的指针的链表
{
    Node *data;
    struct Queue *next;
}Queue;

typedef struct  //头指针和尾指针以及记录链表长度完成队列
{
    Queue *head, *tail;
    int length;
}LinkQueue;

//---------------------------------------------------

Queue *getNewQueue(Node *node)  //生成一个新的链表节点
{
    Queue *p = (Queue *)malloc(sizeof(Queue));
    p->data = node;
    p->next = NULL;
    return p;
}

LinkQueue *init_LinkQueue(Queue *queue) //初始化队列
{
    LinkQueue *p = (LinkQueue *)malloc(sizeof(LinkQueue));
    p->head = p->tail = queue;    //让头尾指针指向链表第一个节点
    p->length = 0;
    return p;
}

void push(Node *node, LinkQueue *p) //入队
{
    if(node == NULL) return;
    p->tail->next = getNewQueue(node);
    p->tail = p->tail->next;
    p->length++;
    return ;
}

void pop(LinkQueue *p)  //出队
{
    if(p->length <= 0) return ;
    Queue *q = p->head;
    p->head = p->head->next;
    p->length--;
    free(q);
    return ;
}

void traversal(LinkQueue *p)    //利用递归让各个节点都能够被遍历
{
    printf("%d ",p->head->data->data);
    push(p->head->data->lchild, p);
    push(p->head->data->rchild, p);
    if(p->length == 0) return ;
    pop(p);
    traversal(p);
    return ;
}

int main()  //主函数中建立列队链表将树的根节点传入，再建立指指针传入列队
{
    Queue *queue = getNewQueue(tree->root);
    LinkQueue *p = init_LinkQueue(queue);
    traversal(p);
}
  1. 链表
    1. 单链表
    2. 循环单链表
  2. 队列与栈
    1. 单队列
    2. 循环队列
    3. 栈
  3. 树
    1. 排序二叉树
    2. 二叉树的四种历遍方式
      1. 前序遍历
      2. 中序遍历
      3. 后序遍历
      4. 层序遍历
  1. 链表
    1. 单链表
    2. 循环单链表
  2. 队列与栈
    1. 单队列
    2. 循环队列
    3. 栈
  3. 树
    1. 排序二叉树
    2. 二叉树的四种历遍方式
      1. 前序遍历
      2. 中序遍历
      3. 后序遍历
      4. 层序遍历