C 语言的几个简单算法

标题的这个重温数据结构与算法可能有点不恰当，因为从来就没有“学会”这一说。大佬们总是说写博客暴露水平，啊反正这种东西重在分享，无所谓无所谓。这篇文章只是记录了一些再基础不过的数据结构和算法，其他的感觉要单独写。

冒泡排序

这个排序应该是入门学的第一个排序吧…嗯，至今还是不懂冒泡的第二次循环到底发生了什么。解释算法的Gif动图看看感觉大道理都能懂，但是第二次循环到底发生了什么？

#include <stdio.h>

void swap(int *varA, int *varB){
    int tmp = *varA;
    *varA = *varB;
    *varB = tmp;
}

void bubble(int *array, int maxN){
    int loopA, loopB;
    for (loopA = 0; loopA < maxN; loopA++) {
        for (loopB = 1; loopB < maxN - loopA; loopB++) {
            if (array[loopB - 1] > array[loopB]){
                swap( &array[loopB - 1], &array[loopB]);
            }
        }
    }
}

void printN(int *array, int maxNum){
    int loopC;
    for (loopC = 0; loopC < maxNum; loopC++) {
        printf("%d ", array[loopC]);
    }
}

int main() {
    int array[10] = {12, 21, 546, 89, 56, 36, 78, 89, 41, 10};
    bubble(array, 10);
    printN(array, 10);
    return 0;
}

选择排序

选择排序是找最小的数，然后把最小的数字放在最前面，在下次循环中忽略这个最小的数。比如有一个数组’{9, 9, 8}’ 排序结果是’{8, 9, 9}’，但因为选择排序的特性，两个9的“相对位置”也发生了变化，因此选择排序是一种不稳定的排序。

#include <stdio.h>

void swap(int *varA, int *varB){
    int tmp = *varA;
    *varA = *varB;
    *varB = tmp;
}

int minKey(int *array, int lowest, int highest){
    int minimum = lowest;
    int key = array[lowest];
    for (int loopA = lowest + 1; loopA < highest; loopA++) {
        if (key > array[loopA]){
            key = array[loopA];
            minimum = loopA;
        }
    }
    return minimum;
}

void selectionSort(int *array, int varN){
    for (int loopB = 0; loopB < varN; loopB++) {
    int varM = minKey(array, loopB, varN);
        if (loopB != varM){
            swap(&array[loopB], &array[varM]);
        }

    }
}

void printN(int *array, int allNum){
    for (int loopC = 0; loopC < allNum; loopC++) {
        printf("%d ", array[loopC]);
    }
}

int main() {
    int array[10] = {12, 21, 546, 89, 56, 36, 78, 89, 41, 10};
    selectionSort(array,10);
    printN(array, 10);
    return 0;
}

顺序查找

顺序查找属于不稳定的查找，其效率不取决于算法，而是取决于目标值在集合中的位置。

顺序查找的过程为：从表的最后一个记录开始，逐个进行记录的关键字和给定值比较，如果某个记录的关键字与给定值相等，则查找成功，反之则表明表中没有所查找记录，查找失败。

#include <stdio.h>

int seq(int *array, int minVar, int maxVar, int target){
    for (int loop = 0; loop < maxVar; loop++) {
        if (array[loop] == target){
            return loop;
        }
    }
    return -1;
}

int main(){
    int array[10] = {1, 2, 5, 7, 8, 6, 3, 4, 9, 0};
    printf("%d ", seq(array, 0, 10, 0));
}

二分查找

这种查找方法有一个先决条件，那就是在一个已经排序好的顺序表中才可以使用。

二分查找的过程是：先确定待查记录所在的区间，然后两边向内（夹逼？）逐步缩小查找范围，直到找到或者找不到该记录为止。最后返回目标值所在的下标。

#include <stdio.h>

int binSearch(int *array, int minVar, int maxVar, int target){
    while (minVar <= maxVar){
        int midVar = (minVar + maxVar) / 2;
        if (target == array[midVar]){
            return midVar;
        } else if (target > array[midVar]) {
            minVar = midVar + 1;
        } else {
            maxVar = midVar - 1;
        }
    }
    return -1;
}

int main(){
    int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    printf("%d ", binSearch(array, 0, 10, 7));
}

二分查找 （递归写法）

整体思路和标配版的二分差不多，只是在返回值处理上用了递归。不过我在用这个方法的时候编译器一直在警告：Do not use ELSE after RETURN，是我在基础知识上遗漏了什么吗？这里只贴上需要改动的函数。

int binSearch_rec(int *array, int minVar, int maxVar, int target){
    if (minVar <= maxVar){
        int midVar = (minVar + maxVar) / 2;
        if (target == array[midVar]){
            return midVar;
        } else if (target > array[midVar]){
            binSearch_rec(array, midVar + 1, maxVar, target);
        } else {
            return binSearch_rec(array, minVar, midVar - 1, target);
        }
    }
}

单向链表的实现

单向链表解决了数组插入数值时大动干戈的繁琐，但它也存在不能快速定位目标数值的缺点。

因为单向链表比较简单，我就把用法都写到一起了，当然下面这些代码是复习的时候用来读的，复制到编译器里运行肯定会直接报错…

#include <stdio.h>
#include <stdlib.h>

struct list{
    int data; // data field
    struct list *next; // pointer field
};

// Creating nodes
struct list *create_list(){
    return calloc(sizeof(struct list), 1);
}

// Insert node into designated place
struct list *insertNode(struct list *ls, int target, int data){
    struct list *p = ls;
    while (p && target--){
        p = p->next;
    }
    if (p == NULL){
        return NULL; // The position of n is larger than the number of nodes in linked list
    }
    // New a node
    struct list *node = create_list();
    // Swap connection
    node->data = data;
    node->next = p->next;
    p->next = node;
}

// Delete node
int deleteNode(struct list *ls, int target){
    struct list *p = ls;
    while (p && target--){
        p = p->next;
    }
    if (p == NULL){
        // Target in a wrong position
        return -1;
    }
    // Delete successfully
    struct list *tmp = p->next; // Recording what's p next to;
    p->next = p->next->next;
    free(tmp);
    return 0;
}

// count the number of nodes
int countNode(struct list *ls){
    struct list *p = ls;
    int count = 0;
    while(p){
        count ++;
        p = p->next;
    }
    return count;
}

// Empty all nodes in linked list except first node
void emptyList(struct list *ls){
    struct list *p = ls->next;
    while (p){
        struct list *tmp = p->next;
        free(p);
        p = tmp;
    }
    ls->next = NULL; // Delete the next of first node
}

// Determine whether a linked list is NULL
int judgeNull(struct list *ls){
    if (ls->next){
        return 0;
    }
    return -1;
}

// Return certain node in designated place
struct list *locateNode(struct list *ls, int target){
    struct list *p = ls;
    while (p && target--){
        p = p->next;
    }
    if (p == NULL){
        return NULL;
    }
    return p;
}

// Return a node whose data field equal to DATA
struct list *eqNode(struct list *ls, int data){
    struct list *p = ls;
    while (p){
        if (p->data == data){
            return p;
        }
        p = p->next;
    }
    return NULL;
}

// Return the position of node whose data field equal to DATA
int peqNodes(struct list *ls, int data){
    int index = 0;
    struct list *p = ls;
    while (p){
        index ++;
        if (p->data == data){
            return index;
        }
        p = p->next;
    }
    return -1; // No matched node
}

// Found the last node in a linked list
struct list *lastNode(struct list *ls){
    struct list *p = ls;
    while (p->next){
        p = p->next;
    }
    return p;
}

// Merge linked list
void mergeNode(struct list *ls1, struct list *ls2){
    // merging two linked list into first linked list
    lastNode(ls1)->next = ls2->next;
    free(ls2);
}

// Reverse linked list
void reverse(struct list *ls){
    if (ls->next == NULL){
        return;
    }
    if (ls->next->next == NULL){
        return;
    }

    struct list *prev = ls;
    struct list *curr = ls->next;
    struct list *next = NULL;
    struct list *last = ls->next;

    while (curr){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    ls->next = prev;
    last->next = NULL;
}

// Iterating linked list
void traverse(struct list *ls){
    struct list *p = ls;
    while (p){
        printf("%d\n", p->data);
        p = p->next; // P point to next node where it corresponding
    }
}

int main(void){
    // Creating node in heap
    struct list *first = create_list();
    struct list *second = create_list();
    struct list *third = create_list();
    // Connect every node in sequence
    first->next = second;
    second->next = third;
    third->next = NULL; // By default, set the last node in linked list as NULL

    first->data = 1;
    second->data = 2;
    third->data = 3;

    // Insert one node AFTER certain node
    insertNode(first, 0, 10);

    // Delete one node in certain place
    deleteNode(first, 1);

    // Empty nodes except first
    emptyList(first);

    // Determine whether a linked list is NULL
    judgeNull(first);

    // Locate node
    printf("%d\n", locateNode(first, 3)->data);

    // Return a node whose data field equal to DATA
    eqNode(first, 2);

    // found the last node
    printf("The last node is %d\n", lastNode(first)->data);

    // Iterating linked list
    traverse(first);

    // Count nodes
    printf("The number of nodes is %d\n", countNode(first));

    // Merge duo linked list except second header
    struct list *first1 = create_list();
    for (int loop = 0; loop < 10; loop++) {
        insertNode(first, 0 ,loop)
    }
    mergeNode(first, first1);
    traverse(first);

    // Reverse linked list
    reverse(first);

    return 0;
}

英文水平一般，可能注释的内容只有自己能看懂…简单说说里面有什么

• 建立一个节点
• 循环遍历链表
• 在指定位置插入节点
• 删除指定位置的节点
• 返回链表节点个数
• 清空链表，只保留首节点
• 查询链表是否为空
• 获取链表制定位置的节点
• 返回数据域等于Data值的节点
• 返回数据域等于Data值的节点的位置
• 得到链表最后一个节点
• 合并链表
• 链表逆置

参考资料

• C程序设计语言 - 中文版
• C程序设计语言 - 英文版

​