qlu数据结构测试

12.15测试

编程题 

1、【问题描述】
已知非空线性链表第1个链结点指针为list，链结点构造为
struct node{
    datatype data;
    node *link;
};
请写一算法，将该链表中数据域值最大的那个点移到链表的最后面。（假设链表中数据域值最大的链结点惟一）（注意：要求先写出算法的解题思路，然后再写出算法）
【输入形式】
输入为一个整数序列，整数之间以空格隔开，序列以回车结尾。
【输出形式】
输出为移动后的整数序列，整数之间以空格隔开，序列以回车结尾。
【样例输入】
3 12 4 9 5 1
【样例输出】
3 4 9 5 1 12
【样例说明】
将序列中最大的数字12移动到序列最后。
【评分标准】
本题必须采用链表来实现移动操作，其他方法不得分。

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

// 定义链表节点结构体
typedef struct node {
    int data;
    struct node *link;
} Node;

// 函数用于将链表中数据域最大的节点移到链表末尾
void moveMaxToEnd(Node **list) {
    if (*list == NULL) {
        return;
    }
    Node *maxPtr = *list;
    Node *prevMaxPtr = NULL;
    Node *curPtr = *list;
    Node *prevPtr = NULL;
    // 遍历链表找到最大值节点以及其前一个节点
    while (curPtr!= NULL) {
        if (curPtr->data > maxPtr->data) {
            maxPtr = curPtr;
            prevMaxPtr = prevPtr;
        }
        prevPtr = curPtr;
        curPtr = curPtr->link;
    }
    // 如果最大值节点就是头节点
    if (prevMaxPtr == NULL) {
        *list = (*list)->link;
    } else {
        prevMaxPtr->link = maxPtr->link;
    }
    // 找到链表尾节点
    curPtr = *list;
    while (curPtr->link!= NULL) {
        curPtr = curPtr->link;
    }
    curPtr->link = maxPtr;
    maxPtr->link = NULL;
}

// 函数用于输出链表中的数据
void printList(Node *list) {
    Node *cur = list;
    while (cur!= NULL) {
        printf("%d ", cur->data);
        cur = cur->link;
    }
    printf("\n");
}

int main() {
    Node *list = NULL;
    Node *tail = NULL;
    int num;
    while (scanf("%d", &num)!= EOF) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = num;
        newNode->link = NULL;
        if (list == NULL) {
            list = newNode;
            tail = newNode;
        } else {
            tail->link = newNode;
            tail = newNode;
        }
    }
    // 清空输入缓冲区
    while (getchar()!= '\n' && getchar()!= EOF);

    moveMaxToEnd(&list);
    printList(list);
    // 释放链表内存
    Node *temp;
    while (list!= NULL) {
        temp = list;
        list = list->link;
        free(temp);
    }
    return 0;
}

2、

【问题描述】对于1到n的所有自然数，计算0到n所有数字（0-9之间的数字）出现的次数分布。

【输入形式】一个整数n（n <= 100000）

【输出形式】10个数字，空格隔开，对应0-9数字在1..n这个序列中出现的次数总和。

【样例输入】

11

【样例输出】

1 4 1 1 1 1 1 1 1 1

【样例输入】

10000

【样例输出】

2893 4001 4000 4000 4000 4000 4000 4000 4000 4000

【评分标准】输出的10个数之间用空格区分。

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

char* intToString(int num) {
    int len = 0;
    int temp = num;
    while (temp > 0) {
        len++;
        temp /= 10;
    }
    
    char* result = (char*)malloc((len + 1) * sizeof(char));
    if (result == NULL) {
        return NULL;
    }
    result[len] = '\0';  // 设置字符串结束符
    
    while (num > 0) {
        result[--len] = num % 10 + '0';
        num /= 10;
    }
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int count[10] = {0};  // 用于记录0-9每个数字出现的次数，初始化为0
    for (int i = 1; i <= n; i++) {
        char* numStr;
        if (i < 0) {
            numStr = (char*)malloc(2 * sizeof(char));  // 为负号和数字字符串预留空间
            if (numStr == NULL) {
                return 1;
            }
            numStr[0] = '-';
            i = -i;
            char* tempStr = intToString(i);
            if (tempStr == NULL) {
                free(numStr);
                return 1;
            }
            strcpy(numStr + 1, tempStr);  // 将转换后的数字字符串复制到负号后面
            free(tempStr);
        } else {
            numStr = intToString(i);
            if (numStr == NULL) {
                return 1;
            }
        }
        // 遍历字符串
        for (size_t j = 0; j < strlen(numStr); j++) {
            int digit = numStr[j] - '0';  // 将字符转换回数字
            count[digit]++;
        }
        free(numStr);  // 释放
    }
    for (int i = 0; i < 9; i++) {
        printf("%d ", count[i]);
    }
    printf("%d\n", count[9]);
    return 0;
}