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每个数字出现的次数，初始化为0for (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;
}
