算法题常用模板

单链表

// C语言种typedef只有在结构体声明后才生效，因此结构体内还得写struct
typedef struct Node{
    int data;
    struct Node* next;
}Node, *LinkList;
//typedef 的整体结构可以理解为：typedef + 原有类型声明 + 类型别名;
// Node：结点类型，等价于 struct Node
// LinkList：结点指针类型，等价于 Node *，通常用作链表头指针。其中*和Node放一块更好理解

//malloc申请结点
Node *p = (Node *)malloc(sizeof(Node)); //申请一个结点大小的内存空间。如果里面写成Node*就是一个指针的大小了
//malloc申请单链表
LinkList L = (LinkList)malloc(sizeof(Node));
    //初始化带头节点的单链表,malloc是可能失败的，因此需要if一下
if(L != NULL) L -> next = NULL;
//free结点
free(p);
//free链表时需要依次free链表中的结点（不释放头结点）
Node *p; //这里不需要新申请空间，因为是用来释放空间的，指向所要释放的结点
while(L -> next != NULL){
    p = L -> next;
    L -> next = p -> next;
    free(p);
}
//释放头结点
Node *p;
while(L != NULL){
    p = L;
    L = L -> next;
    free(p);
}

单链表寻找中间节点

快慢指针，慢指针走一步，快指针走两步，快指针走到尾了，慢指针所指即为中间节点

NODE *p = h, *q = h;
while(q -> next != NULL){
    p = p -> next;
    q = q -> next;
    if(q -> next != NULL) q = q -> next;
}

未知长度单链表找“倒数第 \(k\) 个节点”

双指针，让其中一个先跑k个另一个再出发，先出发的到终点了后出发的指针所指即为所求

NODE *fast = h, *slow = h;
while(k > 0 && fast != NULL){
    fast = fast -> next;
    k --;
}
// 链表长度不足k
if(k != 0 || fast == NULL) return 0;
while(fast != NULL){
    fast = fast -> next;
    slow = slow -> next;
}
//此时slow所指即为所求

注意事项

char data：单个字符，使用 %c。

char data[10]：字符数组，存储以 \0 结尾的字符串时使用 %s。

T.data 与 T->data：结构体变量用 ., 结构体指针用 ->。

快排

//标准填坑法，保证一趟排序可确定枢轴最终位置
// 一趟划分，返回枢轴的最终位置
int partition(int a[], int l, int r){
    int x = a[l];//第一个为枢轴，挖坑
    while(l < r){
        //找第一个小于x的
        while(l < r && a[r] >= x) r --;
        a[l] = a[r];//填左坑

        //找第一个大于x的
        while(l < r && a[l] <= x) l ++;
        a[r] = a[l];//填右坑
    }
    //剩出来的坑即为枢轴最终位置
    a[l] = x;
    return l;
}

void quick_sort(int a[], int l, int r){
    if(l >= r) return;

    int p = partition(a, l, r);

    quick_sort(a, l, p - 1);
    quick_sort(a, p + 1, r);
}

依据一趟确定一个数的最终位置，快排的思想可以在o(n)的情况下求出无序数组中第K大或第K小的元素这个算法就叫 快速选择（Quickselect）。

int partition(int a[], int l, int r){
    int x = a[l];
    while(l < r){
        while(l < r && a[r] >= x) r --;
        a[l] = a[r];
        while(l < r && a[l] <= x) l ++;
        a[r] = a[l];
    }
    a[l] = x;
    return l;
}

int find_k(int a[], int l, int r, int k){
    if(l >= r) return a[l];
    int p = partition(a, l, r);
    //以第k小为例
    if(p == k - 1) return a[p];
    else if(p > k - 1) return find_k(a, l, p - 1, k);
    else return find_k(a, p + 1, r, k);
}