分类目录计算机基础

单链表反转

实现单链表反转的思路

实现单链表反转的难点在于,如果让当前节点的next指向前驱节点,那么链表就断了,所以解决的办法就是在进行反转操作之前用一个临时指针变量保存后继节点的地址。

单链表反转的代码实现

 
 
#include <stdio.h>
#include <stdlib.h>
typedef struct LIST_NODE {
    int data;
    struct LIST_NODE* next;
} LIST_NODE;
void show_list(LIST_NODE *head) {
    LIST_NODE *p = head->next;
    while(p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
void reverse_list(LIST_NODE *head) {
    LIST_NODE *p, *q, *tmp;
    p = head;
    q = p->next;
    while (q != NULL) {
        tmp = q->next;
        if (p == head) {
            q->next = NULL;
        } else {
            q->next = p;
        }
        p = q;
        q = tmp;
    }
    head->next = p;
}
int main(int argc, char **argv) {
    LIST_NODE head = {
        .data = 0,
        .next = NULL
    };
    int data;
    LIST_NODE *tail = &head;
    while (1) {
        printf("Please input a number: (0 to stop input)\n");
        scanf("%d", &data);
        if (data == 0) {
            break;
        }
        LIST_NODE *new_node = malloc(sizeof(LIST_NODE));
        new_node->data = data;
        new_node->next = NULL;
        tail->next = new_node;
        tail = new_node;
    }
    show_list(&head);
    reverse_list(&head);
    show_list(&head);
    return 0;
}

冒泡排序、插入法排序及选择排序

冒泡排序、插入法排序以及选择排序是排序算法中比较基础的三种,其平均时间复杂度都是O(n^2)。

原理介绍

冒泡排序

冒泡排序的步骤是:比较相邻两个数,看是否满足大小关系,如果不满足则交换这两个数,使他们满足大小关系,这样可以保证最大(最小)的数始终会向后流动,循环一次之后,最大(最小)的数就会被交换到数组的最后。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

插入法排序

插入法排序的思路是:把数组分成两个部分:排好序的,和未排序的。开始的时候,数组的第一个元素会被当做拍好序的部分,对其余未排好序的数值进行迭代,将其插入到排好序的部分中合适的位置。

选择法排序

选择法排序和插入法排序类似,都是将数组分为排好序的和未排序的两个部分。不同的是,选择法排序每次迭代都会选择未排序部分中的最小(最大)值,将其插入到排好序部分的队首(队尾)。

C语言实现

需要实现四个函数, 第一个是打印数组,接下来三个函数分别实现三种排序算法:

  • void print_arry(int *a, int len)
  • static inline void insertion_sort(int *a, int len)
  • static inline void bubble_sort(int *a, int len)
  • static inline void selection_sort(int *a, int len)

main函数中,首先需要用户输入指定数目(#define LEN 10)的数值,如果用户输入-1则随机生成这些数值。然后需要用户输入排序算法。输入完成后打印排序前的数组,然后根据相应的排序算法进行排序,最后再打印出排序后的数组。代码如下:

 

 
 
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define LEN 10
#define NR_METHOD 3
#define RAND_RANGE 100
void print_arry(int *a, int len) {
    int i = 0;
    for (int i = 0; i < len; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}
static inline void insertion_sort(int *a, int len) {
    int tmp = 0;
    int i, j;
    for (i = 1; i < len; i++) {
        tmp = a[i];
        for (j = i - 1; j >= 0; j--) {
            if (a[j] > tmp) {
                a[j + 1] = a[j];
            } else {
                break;
            }
        }
        a[j + 1] = tmp;
    }
}
static inline void bubble_sort(int *a, int len) {
    int i, j;
    int tmp;
    int swapped = 0;
    for (i = len - 1; i >= 0; i--) {
        for (j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) {
            break;
        }
    }
}
static inline void selection_sort(int *a, int len) {
    int i, j, min, tmp;
    for (i = 0; i < len -1; i++) {
        min = i;
        for (j = i + 1; j < len; j++) {
            if(a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            tmp = a[min];
            a[min] = a[i];
            a[i] = tmp;
        }
    }
}
int main(int argc, char **argv) {
    srand(time(NULL));
    int a[LEN];
    int data;
    for (int i = 0; i < LEN; i++) {
        printf("Please input a number: %d left: (-1 for random numbers)", LEN - i);
        scanf("%d", &data);
        if(data != -1) {
            a[i] = data;
        } else {
            for (int j = 0; j < LEN; j++) {
                a[j] = rand() % RAND_RANGE;
            }
            break;
        }
    }
    while (1) {
        printf("Please select a sort method:\n");
        printf("0: Insertion sort\n");
        printf("1: Bubble sort \n");
        printf("2: Selection sort \n");
        scanf("%d", &data);
        if(data >= 0 && data < NR_METHOD) {
            break;
        } else {
            printf("Please input a valid number!\n");
        }
    }
    printf("Original Array: \n");
    print_arry(a, LEN);
    switch(data) {
        case 0:
        printf("You selected insertion sort\n");
        insertion_sort(a, LEN);
        break;
        case 1:
        printf("You selected bubble sort\n");
        bubble_sort(a, LEN);
        break;
        case 2:
        printf("You selected selection sort\n");
        selection_sort(a, LEN);
        break;
    }
    printf("Sorted Array: \n");
    print_arry(a, LEN);
    return 0;
}

用单链表实现LRU缓存置换算法

缓存置换算法所解决的问题

在存储系统的金字塔结构中,缓存的存取速度比内存快,然而成本比内存高,所以缓存的容量有限。缓存置换算法所要解决的问题便是在容量有限的缓存中,存放哪些数据可以提升缓存命中率。

 

LRU缓存置换算法的核心思想

LRU算法认为最近访问过的数据被再次访问的可能性最大,所以缓存中存放的是最近使用过的数据。具体的做法是:

  • 把缓存当做一个队列,队首的数据是最近被访问的数据,而队尾的数据则是即将被置换出缓存的数据。
  • 每当有新数据被访问时,会在队列中查找该数据,如果存在,就被该数据挪到队首。
  • 如果被访问的数据没有在队列(缓存)中,而且缓存未满,则该数据被放到队首。
  • 如果被访问的数据没有在队列中,然而缓存已经满了,则把队尾的数据从队列中删除,再把新数据放置到队首。

 

用C语言实现LRU缓存置换算法

 
 
#include <stdio.h>
#include <stdlib.h>
#define CACHE_SIZE 20
int nr_of_list = 0;
typedef struct CACHE_ITEM {
    int data;
    struct CACHE_ITEM *next;
} CACHE_ITEM;
CACHE_ITEM list_head;
int init_list_head(CACHE_ITEM *head) {
    if (!head) {
        printf("%s: parameter error - no list head\n", __func__);
        return -1;
    }
    head->data = 0;
    head->next = NULL;
    return 0;
}
int insert_node(CACHE_ITEM *head, CACHE_ITEM *node) {
    if (!head || !node) {
        printf("%s: parameter error - no list head or node\n", __func__);
        return -1;
    }
    node->next = head->next;
    head->next = node;
    nr_of_list += 1;
    return 0;
}
int remove_node(CACHE_ITEM *head, CACHE_ITEM *node) {
    if (!head || !node) {
        printf("%s: parameter error - no list head or node\n", __func__);
        return -1;
    }
    CACHE_ITEM *p = head;
    while(p->next) {
        if(p->next == node) {
            p->next = node->next;
               nr_of_list -= 1;
           } else {
            p = p->next;
        }
    }
    return 0;
}
int remove_tail_node(CACHE_ITEM *head) {
    if (!head) {
        printf("%s: parameter error - no list head\n", __func__);
        return -1;
    }
    CACHE_ITEM *p = head;
    while(p->next) {
        if(p->next && !p->next->next) {
            p->next = NULL;
            nr_of_list -= 1;
        } else {
            p = p->next;
        }
    }
    return 0;
}
CACHE_ITEM *search_list(CACHE_ITEM *head, int number) {
    if (!head) {
        printf("%s: parameter error - no list head\n", __func__);
        return NULL;
    }
    CACHE_ITEM *p = head->next;
    CACHE_ITEM *q = NULL;
    while(p) {
        if(p->data == number) {
            q = p;
            break;
        } else {
            p = p->next;
        }
    }
    return q;
}
void show_list(CACHE_ITEM *head) {
    CACHE_ITEM *p = head->next;
    while(p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    printf("List Length: %d\n", nr_of_list);
}
int lru(CACHE_ITEM *head, int number) {
    if (!head) {
        printf("%s: parameter error - no list head\n", __func__);
        return -1;
    }
    CACHE_ITEM *p = search_list(head, number);
    if (p) {
        remove_node(head, p);
        insert_node(head, p);
    } else if (nr_of_list < CACHE_SIZE) {
        CACHE_ITEM *new_node = (CACHE_ITEM *)malloc(sizeof(CACHE_ITEM));
        new_node->data = number;
        insert_node(head, new_node);
    } else {
        remove_tail_node(head);
        CACHE_ITEM *new_node = (CACHE_ITEM *)malloc(sizeof(CACHE_ITEM));
        new_node->data = number;
        insert_node(head, new_node);
    }
    return 0;
}
int main(int argc, char **argv) {
    CACHE_ITEM *head = &list_head;
    init_list_head(head);
    int num = 0;
    while(1) {
        printf("请输入数字:\n");
        scanf("%d", &num);
        lru(head, num);
        show_list(head);
    }
    return 0;
}

运行结果

 
 
请输入数字:
1
1
List Length: 1
请输入数字:
2
2 1
List Length: 2
请输入数字:
3
3 2 1
List Length: 3
请输入数字:
4
4 3 2 1
List Length: 4
请输入数字:
5
5 4 3 2 1
List Length: 5
请输入数字:
3
3 5 4 2 1
List Length: 5
请输入数字:
1
1 3 5 4 2
List Length: 5
请输入数字:
6
6 1 3 5 4 2
List Length: 6
请输入数字:
7
7 6 1 3 5 4 2
List Length: 7
请输入数字:
8
8 7 6 1 3 5 4 2
List Length: 8
请输入数字:
9
9 8 7 6 1 3 5 4 2
List Length: 9
请输入数字:
10
10 9 8 7 6 1 3 5 4 2
List Length: 10
请输入数字:
11
11 10 9 8 7 6 1 3 5 4 2
List Length: 11
请输入数字:
12
12 11 10 9 8 7 6 1 3 5 4 2
List Length: 12
请输入数字:
13
13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 13
请输入数字:
14
14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 14
请输入数字:
15
15 14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 15
请输入数字:
16
16 15 14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 16
请输入数字:
17
17 16 15 14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 17
请输入数字:
18
18 17 16 15 14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 18
请输入数字:
19
19 18 17 16 15 14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 19
请输入数字:
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 1 3 5 4 2
List Length: 20
请输入数字:
21
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 1 3 5 4
List Length: 20
请输入数字:
22
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 1 3 5
List Length: 20
请输入数字:
23
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 1 3
List Length: 20
请输入数字:
1
1 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 3
List Length: 20
请输入数字:
4
4 1 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
List Length: 20

顺序存储线性表的实现

最近复习数据结构,写了一个顺序存储的线性表,代码粘在这里:)

代码下载:git@github.com:Wang-Sen/algorithm.git

/*
 * Simple array implementation.
 */

#include <stdbool.h>

#define MAX_SIZE 50
#define data_t int
#define array_length_t int

#define ERR_OUT_OF_RANGE -1
#define ERR_EMPTY_ARRAY -2
#define ERR_INVALID_ARGS -3

typedef struct {
    data_t data[MAX_SIZE];
    array_length_t length;
} array;

static inline void array_init(array *arr)
{
    for (int i = 0; i < MAX_SIZE; i++) {
        arr->data[i] = 0;
    }
    arr->length = 0;
}

static inline void show_array(array *arr)
{
    for (int i=0; i < arr->length; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
}

static inline bool is_array_empty(array *arr)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    return !arr->length;
}

static inline array_length_t len(array *arr) {
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    return arr->length;
}

static inline int locate_entry(array *arr, data_t entry) {
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    int ret = -1;
    for (int i = 0; i < MAX_SIZE; i++) {
        if (arr->data[i] == entry) {
            ret = i;
            return ret;
        }
    }
    return ret;
}

static inline int array_push(array *arr, data_t entry)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    if ((arr->length + 1) > MAX_SIZE) {
        return ERR_OUT_OF_RANGE;
    }
    arr->data[arr->length] = entry;
    (arr->length)++;
    return 0;
}

static inline int array_pop(array *arr, data_t *p_entry)
{
    if (arr->length <= 0) {
        return ERR_EMPTY_ARRAY;
    }
    if (!p_entry || !arr) {
        return ERR_INVALID_ARGS;
    }

    *p_entry = arr->data[arr->length - 1];
    (arr->length)--;

    return 0;
}

static inline int array_insert(array *arr, int loc, data_t entry)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    if ((arr->length + 1) > MAX_SIZE || loc < 0 || loc >= MAX_SIZE) {
        return ERR_OUT_OF_RANGE;
    }
    for (int i = arr->length; i > loc; i--) {
        arr->data[i] = arr->data[i - 1];
    }
    arr->data[loc] = entry;
    (arr->length)++;
    return 0;
}

static inline int array_delete(array *arr, int loc, data_t *entry)
{
    if (!arr || !entry) {
        return ERR_INVALID_ARGS;
    }
    if (loc < 0 || loc >= arr->length) {
        return ERR_OUT_OF_RANGE;
    }

    *entry = arr->data[loc];
    for (int i = loc; i < (arr->length) - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }
    (arr->length)--;
    return 0;
}

static inline int array_update(array *arr, int loc, data_t entry)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    if (!arr->length) {
        return ERR_EMPTY_ARRAY;
    }
    if (loc < 0 || loc >= arr->length) {
        return ERR_OUT_OF_RANGE;
    }
    arr->data[loc] = entry;
    return 0;
}

static inline int array_reverse(array *arr)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }

    int i, j, tmp;
    for (i = 0, j = (arr->length - 1); j - i > 0; i++, j--) {
        if (arr->data[i] == arr->data[j]) {
            tmp = arr->data[i];
            arr->data[i] = arr->data[j];
            arr->data[j] = tmp;
        } else {
            arr->data[i] ^= arr->data[j];
            arr->data[j] ^= arr->data[i];
            arr->data[i] ^= arr->data[j];
        }
    }

    return 0;
}

测试代码:

#include <stdio.h>
#include <unistd.h>
#include "array.h"

int main(int argc, char **argv) {
    int ret = 0, i;
    array list;
    array_init(&list);

    /* test is_empty_array */
    printf("Empty array: %d\n", is_array_empty(&list));
    list.data[0] = 2400;
    list.length += 1;
    printf("Empty array: %d\n", is_array_empty(&list));
    /* end test is_empty_array */

    /* test push */
    for (i = list.length; i < MAX_SIZE; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }

    show_array(&list);

    if ((ret = array_push(&list, 20))) {
        printf("Err: %d\n", ret);
        printf("length: %d\n", list.length);
        printf("Entry: %d\n", 20);
    }
    /* end test push */

    /* test insert */
    array_init(&list);
    for (i = list.length; i < MAX_SIZE-1; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    array_insert(&list, 3, 5);
    show_array(&list);

    array_insert(&list, 3, 6);
    show_array(&list);

    array_init(&list);
    for (i = list.length; i < MAX_SIZE-1; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    array_insert(&list, MAX_SIZE, 5);
    show_array(&list);
    /* end test insert */

    /* test locate_entry */
    array_init(&list);
    for (i = list.length; i < MAX_SIZE; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    printf("location of 5 is: %d\n", locate_entry(&list, 5));
    printf("location of 10 is: %d\n", locate_entry(&list, 10));
    printf("location of 100 is: %d\n", locate_entry(&list, 100));
    printf("location of -100 is: %d\n", locate_entry(&list, -100));
    /* end test locate_entry */

    /* test len*/
    array_init(&list);
    for (i = 0; i < 38; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    printf("len : %d\n", len(&list));
    /* end test len */

    /* test pop */
    array_init(&list);
    int j = 0;
    for (i = 0; i < 26; i++) {
        array_push(&list, j);
        j += 2;
    }
    show_array(&list);
    for (i = 0; i < 27; i++) {
        array_pop(&list, &j);
        printf("Pop Entry: %d\n", j);
        show_array(&list);
    }
    /* end test pop */

    /* test delete*/
    array_init(&list);
    for (i = 0; i < 26; i++) {
        array_push(&list, j);
        j += 2;
    }
    show_array(&list);
    for (i = 0; i < 27; i++) {
        if (array_delete(&list, i, &j) != 0) {
            printf("Delete %dth entry error!\n", i);
            break;
        }
        printf("Deleted Entry: %d\n", j);
        show_array(&list);
    }
    /* end test delete */

    /* test update*/
    array_init(&list);
    for (i = 0, j = 0; i < 26; i++) {
        array_push(&list, j);
        j += 2;
    }
    show_array(&list);
    for (i = 0; i < 28; i++) {
        if (array_update(&list, i, 99) != 0) {
            printf("Update %dth entry error!\n", i);
            break;
        }
        printf("Updated %dth Entry: %d\n", i, j);
        show_array(&list);
    }
    /* end test update */

    /* test reverse*/
    array_init(&list);
    for (i = 0; i < MAX_SIZE; i++) {
        array_push(&list, i);
    }
    show_array(&list);
    array_reverse(&list);
    show_array(&list);
    /* end test reverse */
}

插入法排序

何谓算法?算法就是计算机解决问题的方法和步骤。之所以强调计算机三个字,是因为计算机处理问题的方式和我们人类解决问题的方式有所不同。比如,在电视剧《宫》里看到一个智力题:把一头大象放进骄子里需要哪几个步骤?答案是:第一步,掀开轿帘;第二步,把大象放进去;第三步,放下轿帘。当然,可行性我们暂时不去考虑。然而,对于计算机来说,它没法去掀开轿帘,或者把大象放进轿子里。它只能通过计算机系统特有的指令去处理数据,以此来解决问题。

知道了什么是算法,那么如何去描述问题和算法呢?

以排序问题为例,描述一个问题可以用以下的方式:

输入:n个整数,存放于一个数组a之中。

输出:这n个数在数组a之中按从小到大的顺序存放。

给出了一个问题的输入和要求的输出,这个问题就确定了。描述一种算法,可以用伪代码或者是计算机语言。

对于排序问题,有多种算法。下面谈谈Insertion sort——插入法排序:

插入法排序的大概思想和摸扑克牌类似:当然,我们要求只有一个人摸牌,初始的数组就是放在桌上的一堆牌,而拿到手上的牌是排好序的。当我们摸起一张牌时,会按大小插入到已排好序的手牌之中。下面是基于linux系统,用C语言对改算法的实现:

#include <stdio.h>
#define MAX 10

int sort(int*);

int main()
{
    int input_array[MAX];
    int ret,i;

    printf("Please input the numbers :\n");
    for(i = 0; i < MAX; i++){
        scanf("%d", &input_array[i]);
    }

    printf("The numbers before being sorted :\n");
    for(i = 0; i < MAX; i++){
        printf("%d ", input_array[i]);
        }
    printf("\n");

    ret = sort(input_array);
    printf("The sorted numbers :\n");
    for(i = 0; i < MAX; i++){
        printf("%d ", input_array[i]);
        }
    printf("\n");

    return 0;
}

int sort(int* p)
{
    int i,j,temp;
    for(i = 1; i < MAX; i++){
        temp = p[i];
        for(j = i-1; j >= 0 && p[j] > temp; j--){
            p[j+1] = p[j];
        }
        p[j+1] = temp;
    }
}
"