用C语言构建高效、清晰思路的嵌入式程序：猴子选大王问题解析

原创玩转单片机与嵌入式 2023-12-20 23:08 645浏览 0评论 0点赞

解密5G NR定位在分布式能源系统的同步控制应用 电子元器件采购与技术方案，工程师专属平台

1、引言

嵌入式工程师在编写C语言程序时，需要注重效率和清晰的思路。本文将通过解析经典问题“猴子选大王”来展示如何用C语言思维方式构建高效、清晰的程序。

2、问题描述

考虑一群猴子，手拉手排成一个圆，从任意一只猴子开始从1开始报数，当遇到要排除的数时该猴子退出圈，从下一只猴子开始继续从1报数，如此反复，最终剩下的猴子为大王。

3、程序构架

数据获取

通过printf和scanf获取猴子的总数、起始位置和要排除的数。注意处理异常情况，确保输入合法性。

printf("input total num:");scanf("%d", &n);printf("from which num begin:");scanf("%d", &k);if(k > n || k == 0) {    printf("please input the right begin num");    return 1; }printf("input the out num:");scanf("%d", &m);if(m > n || m == 0) {     printf("please input the right del num");    return 2; }

数据运算

使用循环链表构建“猴子”的圆圈，灵活运用C语言指针操作。注意内存的动态分配和释放。

typedef struct node {    int data;    struct node *next;} linklist;
/* 创建循环链表，头节点也存信息 */linklist *head = (linklist*)malloc(sizeof(linklist));linklist *p = head;p->data = 1;p->next = p;
/* 初始化循环链表 */for (int i = 2; i <= n; i++) {    linklist *s = (linklist*)malloc(sizeof(linklist));    s->data = i;    s->next = p->next;    p->next = s;    p = p->next;}

提高程序运行速率

避免过度使用循环，更多地使用指针操作

/* 找到第 k 个节点 */p = head;for (int i = 1; i <= k; i++) {    p = p->next;}

4、逻辑实现

保存初始“猴子”圆圈参数

/* 保存节点总数 */int total = n;printf("\nthe out num:");linklist *q = head;

猴子查数

猴子查数是关键，需要找到开始的“猴子”数、删除该“猴子”、将删除的循环链表首尾连接起来。

/* 只剩一个节点时停止循环 */while (total != 1) {    /* 报数过程，p指向要删除的节点 */    for (int i = 1; i < m; i++) {        p = p->next;    }
    /* 打印要删除的节点序号 */    printf("[%d] ", p->data);
    /* q 指向 p 节点的前驱 */    while (q->next != p) {        q = q->next;    }
    /* 删除 p 节点 */    q->next = p->next;
    /* 保存被删除节点指针 */    linklist *s = p;
    /* p 指向被删除节点的后继 */    p = p->next;
    /* 释放被删除的节点 */    free(s);
    /* 节点个数减一 */    total--;}
/* 打印最后剩下的节点序号 */printf("\n\nthe last num:[%d] \n\n", p->data);free(p);