数据结构学习（四）
目录：
编程专练：
1、排序：
2、最短路径：
3、进制转换
4、合并表记录：
5、质数因子：
1、题目描述：
老师想知道从某某同学当中，分数最高的是多少，现在请你编程模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
输入描述:
输入包括多组测试数据。每组输入第一行是两个正整数N和M（0 < N <= 30000,0 < M < 5000）,分别代表学生的数目和操作的数目。学生ID编号从1编到N。第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。接下来又M行，每一行有一个字符C（只取‘Q’或‘U’），和两个正整数A,B,当C为'Q'的时候，表示这是一条询问操作，他询问ID从A到B（包括A,B）的学生当中，成绩最高的是多少。当C为‘U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
输出描述:
对于每一次询问操作，在一行里面输出最高成绩。
输入例子:
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
输出例子:
5
6
5
9
老师想知道从某某同学当中，分数最高的是多少，现在请你编程模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
输入描述:
输入包括多组测试数据。每组输入第一行是两个正整数N和M（0 < N <= 30000,0 < M < 5000）,分别代表学生的数目和操作的数目。学生ID编号从1编到N。第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。接下来又M行，每一行有一个字符C（只取‘Q’或‘U’），和两个正整数A,B,当C为'Q'的时候，表示这是一条询问操作，他询问ID从A到B（包括A,B）的学生当中，成绩最高的是多少。当C为‘U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
输出描述:
对于每一次询问操作，在一行里面输出最高成绩。
输入例子:
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
输出例子:
5
6
5
9
#include <stdio.h>
int main(void){
int n, m;//n为学生数目，m为操作数目
int score[30010];
int i, j, from[5010], to[5010];
int number_max, temp1, temp2;
char c[5010], ch;
while(scanf("%d %d", &n, &m) != EOF){
for(i = 1; i <= n; i++){
scanf("%d", &score[i]);
}
ch = getchar();
for(i = 0; i < m; i++){
scanf("%c %d %d", &c[i], &from[i], &to[i]);
ch = getchar();
}
for(i = 0; i < m; i++){
temp1 = from[i];
temp2 = to[i];
if(c[i] == 'U'){
score[temp1] = to[i];
}
else{
if(temp1 > temp2){
temp1 = temp1 + temp2;
temp2 = temp1 - temp2;
temp1 = temp1 - temp2;
}
number_max = score[temp1];
for(j = temp1; j <= temp2; j++){
if(score[j] > number_max){
number_max = score[j];
}
}
printf("%d\n", number_max);
}
}
}
return 0;
}
运行结果：
图1.1 运行结果
2、题目描述：
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离。
输入描述:
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路
接下来M行两个整数，表示相连的两个城市的编号
输出描述:
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
输入例子:
4 4
1 2
2 3
1 3
0 1
输出例子:
8
9
11
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离。
输入描述:
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路
接下来M行两个整数，表示相连的两个城市的编号
输出描述:
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
输入例子:
4 4
1 2
2 3
1 3
0 1
输出例子:
8
9
11
#include <stdio.h>
int main(void){
int m, n, i, j, k, citya, cityb;
int mod[500];//存放第K条道路的长度
int dis[100][100];//两个城市之间的长度
mod[0] = 1;//第一条道路的长度为1，存放在数组的零号位置
for(i = 1; i < 500; i++){
mod[i] = (mod[i -1] * 2) % 100000;//五百条道路的长度
}
scanf("%d %d", &n, &m);//输入n个城市，m条道路的n与m值
//设置城市之间的初始道路长度，为同一城市设为0，不同的城市之间的距离为-1
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
dis[i][j] = dis[j][i] = i == j ? 0 : -1;
}
}
//对这m条道路进行处理
for(i = 0; i < m; i++){
scanf("%d %d", &citya, &cityb);
//如果两个城市之间不可达，则为两个城市赋予可达路径的值
if(dis[citya][cityb] == -1){
dis[citya][cityb] = dis[cityb][citya] = mod[i];
//对所有的可能可达的城市之间的距离进行遍历更新
for(j = 0; j < n; j++){
for(k = 0; k < n; k++){
//j到k从不可达变为可达
if(dis[j][k] == -1 && dis[j][citya] != -1 && dis[cityb][k] != -1){
dis[j][k] = dis[k][j] = (dis[j][citya] + dis[cityb][k] + dis[citya][cityb]) % 100000;
}
}
}
}
//如果两个城市之间本身就可达
else{
//j到k原本可达，但新增节点的路径使得可达的最短距离变短了
if(mod[i] < dis[citya][cityb]){
dis[citya][cityb] = dis[cityb][citya] = mod[i];
//对所有的可能可达的城市之间的距离进行遍历更新
for(j = 0; j < n; j++){
for(k = 0; k < n; k++){
//j到k从不可达变为可达
if(dis[j][k] == -1 && dis[j][citya] != -1 && dis[cityb][k] != -1){
dis[j][k] = dis[k][j] = (dis[j][citya] + dis[cityb][k] + dis[citya][cityb]) % 100000;
}
}
}
}
}
}
//按题目要求输出
for(i = 1; i < n; i++){
if(dis[0][i] != -1){
printf("%d\n", dis[0][i]);
}else{
printf("-1\n");
}
}
}
运行结果：
图2.1 运行结果
3、写出一个程序，接受一个十六进制的数值字符串，输出该数值的十进制字符串。（多组同时输入 ）
输入描述:
输入一个十六进制的数值字符串。
输出描述:
输出该数值的十进制字符串。
输入描述:
输入一个十六进制的数值字符串。
输出描述:
输出该数值的十进制字符串。
输入例子:
0xA
输出例子:
10
0xA
输出例子:
10
示例一：
#include <stdio.h>
#include <string.h>
#include <math.h>
int main(){
char a[100];
double count;
while(gets(a) != NULL){
count = 0;
int b;
for(int j = strlen(a) - 3, i = 2; i <= strlen(a) - 1; i++, j--){
if(a[i] == 'A' || a[i] == 'a'){
b = 10;
}
else if(a[i] == 'b' || a[i] == 'B'){
b = 11;
}
else if(a[i] == 'c' || a[i] == 'C'){
b = 12;
}
else if(a[i] == 'd' || a[i] == 'D'){
b = 13;
}
else if(a[i] == 'e' || a[i] == 'E'){
b = 14;
}
else if(a[i] == 'f' || a[i] == 'F'){
b = 15;
}else{
b = a[i] - 48;
}
count += b * pow(16, j);
}
printf("%.0lf\n", count);
memset(a, 0 ,sizeof(char));
}
return 0;
}
示例二：
#include <stdio.h>
#include <string.h>
int main(){
char a[100];
while(gets(a)){
int i, temp = 0, count = 0;
int mul = 1;
for(i = strlen(a) - 1; i >= 2; i--){
if(a[i] >= '0' && a[i] <= '9'){
temp = a[i] - '0';
}else if(a[i] >= 'a' && a[i] <= 'f'){
temp = a[i] - 'a' + 10;
}else{
temp = a[i] - 'A' + 10;
}
count += mul * temp;
mul *= 16;
}
printf("%d\n", count);
}
return 0;
}
运行结果：
图3.1 运行结果
4、题目描述：
数据表记录包含表索引和数值，请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。
输入描述:
先输入键值对的个数
然后输入成对的index和value值，以空格隔开
输出描述:
输出合并后的键值对（多行）
输入例子:
4
0 1
0 2
1 2
3 4
输出例子:
0 3
1 2
3 4
示例一：
数据表记录包含表索引和数值，请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。
输入描述:
先输入键值对的个数
然后输入成对的index和value值，以空格隔开
输出描述:
输出合并后的键值对（多行）
输入例子:
4
0 1
0 2
1 2
3 4
输出例子:
0 3
1 2
3 4
#include <stdio.h>
int main(){
int key, value;
int data[65535] = {0};
int num;
scanf("%d", &num);
for(int i = 0; i < num; i++){
scanf("%d", &key);
scanf("%d", &value);
data[key] += value;
}
for(int i = 0; i < 1000; i++){
if(data[i]){
printf("%d %d\n", i, data[i]);
}
}
}
示例二：
#include <stdio.h>
typedef struct Node{
int key;
int value;
}Node;
//对key值进行快速升序排序
int Partition(struct Node node[], int low, int high){
node[0] = node[low];
while(low < high){
while(low < high && node[high].key > node[0].key){
--high;
}
node[low] = node[high];
while(low < high && node[low].key < node[0].key){
++low;
}
node[high] = node[low];
}
node[low] = node[0];
return low;
}
void QuickSort(struct Node node[], int s, int t){
int p;
if(s < t){
p = Partition(node, s, t);
QuickSort(node, s, p);
QuickSort(node, p + 1, t);
}
}
int main(){
int num, temp, count = 0;
struct Node node[100];
scanf("%d", &num);
for(int i = 0; i < num; i++){
scanf("%d", &node[i].key);
scanf("%d", &node[i].value);
}
QuickSort(node, 0, num - 1);
for(int i = 0; i < num - 2; i++){
temp = node[i].value;
if(node[i].key == node[i + 1].key){
count += temp;
}else{
printf("%d %d\n",node[i],count + temp);
count = 0;
}
}
}
运行结果：
图4.1 方式一运行结果
图4.2 方式二运行结果
5、功能:输入一个正整数，按照从小到大的顺序输出它的所有质数的因子（如180的质数因子为2 2 3 3 5 ）
最后一个数后面也要有空格
输入描述:
输入一个long型整数
输出描述:
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。
输入例子:
180
输出例子:
2 2 3 3 5
最后一个数后面也要有空格
输入描述:
输入一个long型整数
输出描述:
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。
输入例子:
180
输出例子:
2 2 3 3 5
方式一：
#include <stdio.h>
int main(void){
long int number;
scanf("%ld", &number);
while(number != 1){
int i = 2;
for(; i <= number; i++){
if(number % i == 0){
number /= i;
printf("%d ", i);
break;
}
}
}
return 0;
}
方式二：
#include <stdio.h>
#include <math.h>
int main(void){
//先将质数存放在一个数组
int zhishu[10000];
long int number;
zhishu[0] = 2;
zhishu[1] = 3;
int k = 2;
for(int i = 4; i < 100000; i++){
int flag = 0;
for(int j = 2; j <= sqrt(i); j++){
if(i % j == 0){
flag = 1;
break;
}
}
if(flag == 0){
zhishu[k++] = i;
}
}
scanf("%ld", &number);
while(number != 1){
int i = 0;
for(; i < k; i++){
if(number % zhishu[i] == 0){
number /= zhishu[i];
printf("%d ", zhishu[i]);
break;
}
}
}
return 0;
}
方式一和方式二在占用内存及运行时间基本相同，大整数时方式二相对较快，小整数时方式一相对较快。
运行结果：
图5.1 方式一大整数下运行结果及时间
图5.2 方式二大整数下运行结果及时间
图5.3 方式一在小整数下运行结果及时间
图5.4 方式二在小整数下运行结果及时间