发表更新计算机基础 / 数据结构与算法20 分钟读完 (大约3005个字)0次访问

数据结构与算法-1

使用C语言实现的数据结构与算法。都非常基础。

用于自己备考和练习。

本文包含：

  • 数据结构：栈、链表
  • 算法：搜索、排序

Data Structure

栈 - Stack

栈的主要特点如下：

  1. 后进先出（LIFO）：最后插入的元素将最先被移除。类比于一叠盘子，最后放上去的盘子最先被拿走。

  2. 压栈和弹栈：栈的主要操作包括压栈（push）和弹栈（pop）。压栈将元素放入栈的顶部，弹栈将顶部元素移除。

  3. 栈顶指针：栈中用一个指针来指示栈顶元素的位置，可以称之为"栈顶指针"。

  4. 适用场景：栈常用于需要"先进后出"处理的场景，比如函数调用栈、表达式求值、逆波兰表达式求值、括号匹配等。

  5. 功能简单：相比其他数据结构如队列、链表等，栈的功能较为简单，通常只包含压栈和弹栈两种基本操作。

栈的定义与销毁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct stack
{
    int *data;
    int top;
    int max_size;
}*stack;

// 销毁栈
void destroy_stack(stack s)
{
    free(s->data);
    free(s);
}

// create a stack
stack create_stack(int max_size)
{
    stack s = (stack)malloc(sizeof(struct stack));
    s->data = (int *)malloc(sizeof(int) * max_size);// 创建动态数组
    s->top = 0;
    s->max_size = max_size;
    return s;
}

栈的一些基本操作和特性：

push(item)

将元素item压入栈的顶部。

1
2
3
4
5
6
7
8
void push(stack s, int val)
{
    if (s->top < s->max_size)
    {
        s->data[s->top++] = val;
    }
    return;
}
pop()

弹出栈顶的元素，并返回该元素。

1
2
3
4
5
6
7
int pop(stack s)
{
    if(s->top > 0){
        return s->data[--s->top];
    }
}

top()

获取栈顶的元素，但不对栈进行修改。

1
2
3
4
5
6
7
8
9
10

int top(stack s)
{
    if(s->top > 0)
    {
        return s->data[s->top - 1];
    }
    return -1;
}

isEmpty()

检查栈是否为空。

1
2
3
4
int isEmpty(stack s)
{
    return (s->top == 0);
}
size()：获取栈中元素的个数。
1
2
3
4
int size(stack s)
{
    return s->top;
}

链表 - Link

一般链表

无空头。

定义节点

这段代码定义了一个结构体类型NODE，用于表示链表中的节点。结构体中包含两个成员变量：

int val: 这是一个整数类型的变量，用于存储节点中的数据。

struct _NODE* next: 这是一个指针变量，用于指向链表中的下一个节点。由于结构体类型NODE在定义时还没有完全定义，因此需要使用struct _NODE*来表示指向自身类型的指针。

1
2
3
4
5
6
7
typedef struct _NODE
{
    /* data */
    int val; // 存储数据
    struct _NODE * next;// 指向下一个的指针
    
}NODE;
创建节点
1
2
3
4
5
6
7
NODE* create_node(int v)
{
    NODE* newNode = (NODE*) malloc(sizeof(NODE)); //创建新的结构体对象
    newNode->val = v;   //初始化
    newNode->next = NULL;
    return newNode;
}

说明：

  1. NODE* newNode: 这是一个指针变量，用于指向新创建的链表节点。NODE*表示这是一个指向NODE类型的指针。

  2. (NODE*) malloc(sizeof(NODE)): 这是动态内存分配的部分。malloc函数用于在堆上分配一块指定大小的内存空间，并返回指向该内存块的指针。sizeof(NODE)用于计算结构体类型NODE所占用的字节数，这样malloc就会为新的节点分配足够大小的内存空间。

从头插入
1
2
3
4
5
6
NODE* insert_head(NODE *h, int v){
    NODE* newNode = create_node(v);
    newNode->val = v;
    newNode->next = h;
    return newNode;
}
删除特定值
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
// 删除值为v的节点
NODE* del(NODE* h, int v)
{
    NODE *p, *q;
    p = h, q = h;

    // 若头就是目标节点
    if(h->val == v){
        p = h->next;
        free(h);
        return p;
    }

    // 其余情况
    while(p->val != v)
    {
        q = p;// q记录要删掉的节点的前一个节点
        p = p->next;

        if(p == NULL){
            // check
            printf("This Node is not exist.\n");
            return h;
        }
    }
    
    // 此时p指向被删节点，q在前一个

    printf("The target number: %d, current Node: %d \n", v, p->val );
    
    // q->next指向被删节点的下一个节点，链接两部分。
    q->next = p->next;
    // 删除节点
    free(p);

    return h;
}
按照升序插入
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
NODE* insert_ordered(NODE* h, int v)
{
    if (h == NULL){
        h = create_node(v);
        return;
    }
    // 若插入的梳子小于head，则作为新的头
    if(h->val >= v)
    {
        h = insert_head(h,v);
        return h;
    }

    // 一般情况
    NODE* p = h, *q = h;
    while(p->val < v){
        q = p;
        p = p->next;

        // 要插到尾巴,跳出循环
        if(p == NULL){
            break;
        }
    }

    NODE *newNode = create_node(v);
    q->next = newNode;
    newNode->next = p;

    return h;

}
链表反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
NODE *reverse(NODE* h){
    if(h->next == NULL){
        return h;
    }


    // p记录反转后的头
    // q源列表剩下的头
    // tmp 暂存源列表的下一个
    NODE *p, *q, *tmp;
    p = h; q = h->next;
    h->next = NULL;// head变成tail
    while(q){
        tmp = q->next; //剩下的头
        q->next = p;    // 
        p = q;
        q = tmp;
        
    }
    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
NODE* merge(NODE *h1, NODE *h2)
{
    printf("START MERGE:\n");
    if (h1 == NULL) return h2;
	if (h2 == NULL) return h1;

    NODE* result, *p, *q;// p记录1，q记录2
    p = h1, q = h2;
    
    // 先确定头
    printf("SETTING HEAD.....\n");
    if(p->val < q->val){
        result = p;
        p = p->next;
    }else{
        result = q;
        q = q->next;
    }

    // body 这里都是result的尾插
    NODE *tail = result;
        printf("MERGING.....\n");

    
    while(p && q){

        if(p->val <= q->val){
            tail->next = p;
            p = p->next;
      
        }else{
            tail->next = q;
            q = q->next;

        }
        tail = tail->next;  
    }

    if(p){
        tail->next = p;
    }
    if(q){
        tail->next = q;
    }

    return result;
}

算法 - Algorithm

Search Algorithm

  • 手动定义顺序数组
  • input： target
  • output：find or not.

线性查找 - Linear Search

线性查找计算量为O(n)。

1
懒得写

二分查找 - Binary Search

使用二分查找的前提是，数组为有序数组，且数组钟不可以有重复元素（因为可能返回的下下标不止一个）。

注意二分查找的边界，left 和 right 该如何定义与变化。

主要需要注意，right在边界是如何取值的，是否包含有边界会影响终止条件与对目标的搜索范围。

时间复杂度：O(log n)

1. binary_search1：左闭右闭

建议死记硬背这一种

被初始化为 ```SIZE - 1```，即数组 a 的最后一个元素的索引。这使得待搜索区间为全封闭区间 ```[l, r]```，包括了边界上的元素。
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
循环条件是 ```while (l <= r)```，即当左边界 l 小于或等于右边界 r 时继续循环。

当搜索区间为空——```l > r```的时候终止循环。

```C
void binary_search1(int a[], int t)
{
    // 当 t 定义在全封闭[l,r]的范围内。

    int l,r,mid;
    l = 0; r = SIZE - 1; // 这里r注意
    

    // 因为left == right是有意义的
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(t < a[mid]){
            r = mid - 1;
        }
        else if(t > a[mid])
        {
            l = mid + 1;
        }
        else{
            printf("True.");
            return ;
        }

    }
    printf("False");
    return ;

}
2. binary_search2：左闭右开
被初始化为 ```SIZE```，即数组 a 的长度。这使得待搜索区间为半关半开区间 ```[l, r)```，不包括右边界。
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
循环条件是 while (l < r)，即当左边界 l 小于右边界 r 时继续循环。

当搜索区间为空——```l == r```的时候终止循环。

```C
void binary_search2(int a[], int t)
{
    // 当 t 定义在半关半开[l,r)的范围内。

    int l,r,mid;
    l = 0; r = SIZE; // 这里r注意
    

    // 因为left == right没有意义了
    while(l < r)
    {
        mid = l + ((r-l)>>1);

        if(t < a[mid]){
            r = mid ;  // 这里，右边始终保持开区间
        }
        else if(t > a[mid])
        {
            l = mid + 1;
        }
        else{
            printf("True.");
            return ;
        }

    }
    printf("False");
    return ;
}
3. 使用递归的方法
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

void binary_search(int a[], int t){
    int flag = _binary_search(a,0,SIZE - 1,t);
    if(flag == 1){
        printf("True.\n");
    }
    if(flag == -1){
        printf("False.\n");

    }
}
int _binary_search(int a[], int l, int r, int t)
{
    if(r >= l)
    {
        int mid = (l + r) / 2;

        if( a[mid] == t)
            return 1;
        else if(a[mid] > t)
            return _binary_search(a,l,mid-1,t);
        else 
            return _binary_search(a, mid + 1, r, t);
        
    }
    return -1;
}

排序算法 - Sort

插入排序 - Insertion_Sort

将数组A[0…n-1]分为两个部分，已排序部分A[0…j-1] 和未排序部分A[j…n-1]。

  • 每次将未排序部分的第一个数，有序地插入已排序的部分。
  • 时间复杂度：$$ O(n^2)$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void insertion_sort(int nums[])
{
    printf("-------- Insertion_Sort_Optimized ----------\n");
    for(int j = 1; j<SIZE; j++)
    {
        int key = nums[j];
        // insert nums[j] into sorted sequence A[0...j-1]
        int i = j - 1;
        while(i >= 0 && nums[i] > key)
        {
            nums[i+1] = nums[i];
            i--;
        }
        nums[i+1] = key;
        printf("Loop %d: ",j-1);
        print_array(nums);
    }
    printf("END:");
    print_array(nums);
    printf("==================================\n");
}

-------- Insertion_Sort_Optimized ----------
Loop 0: 3 6 2 7 9 8 0 1 5 4
Loop 1: 2 3 6 7 9 8 0 1 5 4
Loop 2: 2 3 6 7 9 8 0 1 5 4
Loop 3: 2 3 6 7 9 8 0 1 5 4
Loop 4: 2 3 6 7 8 9 0 1 5 4
Loop 5: 0 2 3 6 7 8 9 1 5 4
Loop 6: 0 1 2 3 6 7 8 9 5 4
Loop 7: 0 1 2 3 5 6 7 8 9 4
Loop 8: 0 1 2 3 4 5 6 7 8 9
END:0 1 2 3 4 5 6 7 8 9

选择排序 - select sort

将数组A[0…n-1]分为两个部分，已排序部分A[0…j-1] 和未排序部分A[j…n-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
void select_sort(int nums[])
{
    printf("-------- Select_Sort_Optimized ----------\n");
    int pos =  0,tail = 0;
    int tmp ;

    while(tail< SIZE)
    {
        // find the smallest one, remember the position.
        for(int i = tail;i<SIZE;i++)
        {
            if(nums[i] < nums[pos])
            {
                pos = i;
            }
        }

        // exchange
        tmp = nums[tail];
        nums[tail] = nums[pos];
        nums[pos] = tmp;
        tail++;
        pos = tail;

        printf("\nloop %d: ",tail);
        print_array(nums);
    }
    printf("END:");
    print_array(nums);
    printf("==================================\n");
}

-------- Select_Sort_Optimized ----------
loop 1: 0 6 2 7 9 8 3 1 5 4
loop 2: 0 1 2 7 9 8 3 6 5 4
loop 3: 0 1 2 7 9 8 3 6 5 4
loop 4: 0 1 2 3 9 8 7 6 5 4
loop 5: 0 1 2 3 4 8 7 6 5 9
loop 6: 0 1 2 3 4 5 7 6 8 9
loop 7: 0 1 2 3 4 5 6 7 8 9
loop 8: 0 1 2 3 4 5 6 7 8 9
loop 9: 0 1 2 3 4 5 6 7 8 9
loop 10: 0 1 2 3 4 5 6 7 8 9
END:0 1 2 3 4 5 6 7 8 9
==================================

冒泡排序及其优化 - Bubble Sort

常规

反复交换相邻的未按次序排序的元素。低效但常用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void bubble_sort(int nums[])
{
    printf("-------- Bubble_Sort ----------\n");
    int i, j,tmp;
    for(i = 0; i < SIZE; i++)
    {
        for(j = 1; j< SIZE- i ; j++)
        {
            if(nums[j] < nums[j-1])
            {
                tmp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = tmp;
            }
        }

        printf("bubble loop %d: ",i);
        print_array(nums);
    }

    printf("END:");
    print_array(nums);
    printf("==================================\n");
}

-------- Bubble_Sort ----------
bubble loop 0: 3 2 6 7 8 0 1 5 4 9
bubble loop 1: 2 3 6 7 0 1 5 4 8 9
bubble loop 2: 2 3 6 0 1 5 4 7 8 9
bubble loop 3: 2 3 0 1 5 4 6 7 8 9
bubble loop 4: 2 0 1 3 4 5 6 7 8 9
bubble loop 5: 0 1 2 3 4 5 6 7 8 9
bubble loop 6: 0 1 2 3 4 5 6 7 8 9
bubble loop 7: 0 1 2 3 4 5 6 7 8 9
bubble loop 8: 0 1 2 3 4 5 6 7 8 9
bubble loop 9: 0 1 2 3 4 5 6 7 8 9
END:0 1 2 3 4 5 6 7 8 9
==================================

优化
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
void bubble_sort_optimized(int nums[])
{
    printf("-------- Bubble_Sort_Optimized ----------\n");
    int j,tmp,last,cnt;
    last = SIZE-1; // last will remember the last time where the swap happened.
    cnt = 0;
    while(last)
    {
        last = 0; // Ever time reset to 0 because we start from the first position.


        for(j = 1; j < SIZE; j++)
        {
            if(nums[j] < nums[j-1])
            {
                tmp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = tmp;

                last = j-1;
                printf("last = %d; ",last);
            }
        }

        printf("\nbubble loop %d: ",cnt);
        print_array(nums);
    }
    printf("END:");
    print_array(nums);
    printf("==================================\n");

}

-------- Bubble_Sort_Optimized ----------
last = 1; last = 4; last = 5; last = 6; last = 7; last = 8;
bubble loop 0: 3 2 6 7 8 0 1 5 4 9
last = 0; last = 4; last = 5; last = 6; last = 7;
bubble loop 0: 2 3 6 7 0 1 5 4 8 9
last = 3; last = 4; last = 5; last = 6;
bubble loop 0: 2 3 6 0 1 5 4 7 8 9
last = 2; last = 3; last = 4; last = 5;
bubble loop 0: 2 3 0 1 5 4 6 7 8 9
last = 1; last = 2; last = 4;
bubble loop 0: 2 0 1 3 4 5 6 7 8 9
last = 0; last = 1;
bubble loop 0: 0 1 2 3 4 5 6 7 8 9
bubble loop 0: 0 1 2 3 4 5 6 7 8 9
END:0 1 2 3 4 5 6 7 8 9

快速排序 - Quick Sort

  • 最坏时间复杂度：$$ O(n^2) $$
  • 期望时间复杂度：$$ O(nlg n) $$

将数组分为三个部分：

  • 左段：所有元素不得大于middle
  • 右段：所有元素不得小于middle
  • middle：一个轴元素，可称为支点（pivot）

这个middle不代表是这个数组的中间值，仅是用于分段。

  1. 首先对nums[0:n-1]进行快排，找到一个元素作为支点（此时这个元素已经在排序后的位置）
  2. 对左边进行快排
  3. 对右半部分进行快排
  4. 直到子序列长度为0

使用两个函数：

  • 递归入口quick_sort ：记录轴函数位置，以及对子序列进行排序
  • PARTITION ：子数组进行原地址重排。
    • x：记录轴元素的啊小
    • i：表示已经处理过的元素中，最后一个小于等于轴元素 x 的元素的索引。
    • j：遍历子数组，与x对比看是否需要换到左边。

代码：

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
void quick_sort(int nums[], int p, int r)
{
    /*
    传入进行排序的数组，起始位置p和终止为止r
        */
    if(p<r){
        int q = PARTITION(nums,p,r);
        quick_sort(nums,p,q-1);
        quick_sort(nums,q+1,r);

    }
    // print_array(nums);
    return ;
}

int PARTITION(int nums[], int p, int r)

{
    /*对子数组进行原地址重排*/

    int x = nums[r]; // x为轴元素
    int i = p - 1; //i 的值表示已经处理过的元素中，最后一个小于等于轴元素 x 的元素的索引。
    int j = p;
    for( j; j<r;j++)
    {
        if (nums[j]<= x)
        {
            i++;
            // 交换
            swap(nums,i,j);
        }
    }

    swap(nums,i+1,r);
    printf("%d  %d  ",p,r);
    for(int i =0;i<r;i++){
        printf("%d  ",nums[i]);
    }

    printf("\n");
    return i+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
void quick_sort_inOne(int nums[], int l, int r)

{
    /*将两个函数结合在一起完成快排*/
    if(l>= r) return ;
    int i = l; int j = r; int pivot = nums[l];// 以最左边的为基准
    // i 找到左边大于pivot的，j 找到小于pivot的。
    while(i < j)
    {
        while(nums[i] < pivot)
        {
            i++;
        }
        while(nums[j] > pivot)
        {
            j--;
        }
        if(i < j)
            swap(nums,i,j);
        else
            break;

    }

    printf("tmp: "); print_array(nums);
    quick_sort_inOne(nums,l,i-1);
    quick_sort_inOne(nums,i+1,r);

    return;

  

}

和老师的不一样，这是老师的写法：

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
void  quick_r(vector<int>& nums, int l, int r)
{
	if (l >= r) return;

	int i = l; int j = r; int pivot = nums[l];// 以最左边的为基准
	while (i < j)
	{
		while (i<j && nums[j] > pivot) j--;// 必须先从右往左扫，找到第一个小于p的位置
		if (i < j) {
			nums[i] = nums[j];// 应该也可以写作：nums[i++] = a[j]; 一行
			i++;
		}
		while (i < j && nums[i] < pivot) i++;// 从左到右扫，直到找到大于p的
		if (i < j) {
			nums[j] = nums[i];
			j--;
		}

	}

	// 最后i的位置就是p应该在的位置
	nums[i] = pivot;

	// 稍微看看快排每次啥情况
	cout << "快排调用：";
	printArry(nums);
	// 处理左半边和右半边
	if (l < i - 1) quick_r(nums, l, i - 1);
	if (i + 1 < r) quick_r(nums, i + 1, r);

}

数据结构与算法-1

https://zhouwentong7.github.io/2025/04/01/数据结构与算法-1/

作者

Zhou

发布于

2025-04-01

更新于

2025-04-01

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

最新文章

分类

标签

AMP1
Activation Function2
Attention2
BFS1
BatchNorm1
BitNet1
C语言1
DFS1
Hexo5
Image Segmentation1
Java1
LLM1
LayerNorm1
Leaky ReLU1
Linux4
Python3
ReLU1
Sigmoid1
Software Development1
Windows4
deep learning12
front end1
git2
github2
hexo4
machine learning4
markdown1
pytorch8
softmax1
ssh1
vscode1
wsl1
写作1
哈希1
图1
排序算法1
搜索算法2
数据恢复2
数据结构与算法3
文件读取2
栈1
激活函数1
生活1
硬件2
碎碎念1
科研1
终端命令1
评价指标2
读后感1
链表1
随拍1
随笔5
项目分享1
项目管理2
+ + +
×