【备战春招】第18天 嵌入式工程师学习笔记

课程信息

• 课程名称：物联网/嵌入式工程师
• 章节名称：第5周之第二讲 1-9 单向循环链表
• 讲师姓名：大白老师

课程内容概述

1. 简介

本节介绍了C语言中的单向循环链表。

单向循环链表是对单向链表的一种改进方式。本质是链表尾结点的指针域存放头节点的地址，

这种首尾相连的链表，叫做单向循环链表

2. 图形操作

3. 代码示例

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

typedef int data_t;

typedef struct node {
    data_t value;
    struct node *next;
} looplist_t;


/**
 * 插入
*/
void insert_node(looplist_t *head, data_t data) {
    looplist_t *tmp = (looplist_t *) malloc(sizeof(looplist_t));
    tmp->value = data;
    tmp->next = head->next;
    head->next = tmp;
    return;
}

/**
 * 打印
*/
void print_list(looplist_t *head) {
    looplist_t *p = head;
    while (head != p->next) {
        printf("%d ", p->value);
        p = p->next;
    }
    printf("%d ", p->value);
    printf("\n");
    return;
}


/**
 * 构建
*/
looplist_t *create_list(int n) {

    looplist_t *head_p;
    int i;

    head_p = (looplist_t *) malloc(sizeof(looplist_t));
    if (NULL == head_p) {
        printf("node_t fail");
    }
    head_p->value = 1;
    head_p->next = head_p;

    for (i = n; i > 1; i--) {
        insert_node(head_p, i);
    }

    return head_p;
}

/**
 * 约瑟夫问题
*/
void josephu(looplist_t *head, int k, int m) {

    looplist_t *start_node = head;
    looplist_t *p;
    int i;

    // 获取开始节点
    for (i = 1; i < k; i++) {
        start_node = start_node->next;
    }

    p = start_node;
    i = 1;
    while (p->next != p) {

        if (0 == i % (m - 1)) {
            printf("%d ", p->next->value);
            p->next = p->next->next;
        }
        p = p->next;
        i++;
    }

    printf("%d \n", p->value);

    return;
}


int main(int argc, char const *argv[]) {
    looplist_t *head;
    int n, k, m, i;

    printf("please input n,k,m: \n");
    scanf_s("%d%d%d", &n, &k, &m);

    head = create_list(n);

    print_list(head);

    josephu(head, k, m);

    return 0;
}

运行结果

please input n,k,m:
5 3 2
1 2 3 4 5
4 1 3 2 5

学习心得

C语言中的数据结构，实践练习了单向循环链表，感觉很有收获。

课程截图

1. 示例