C语言程序设计期末例题复习

题目一：

题目
输入两个非负整数a和b，输出两个非负整数的和(a+b)。

数据规模
0<=a,b<= 10 
99
 ?1

样例1
输入
1 1
?
输出
2
?
?
样例2
输入
1844674407370955161 1
?
输出
1844674407370955162

代码实现：

void reverse(char *s){//反转字符串，便于从低位进行进位运算
    int len=strlen(s);
    for(int i=0;i<len-i-1;i++){
        char t=s[i];
        s[i]=s[len-i-1];
        s[len-i-1]=t;
    }
}
void Sum(char *a,char *b,char *sum){
    int len_a=strlen(a),len_b=strlen(b),acc=0,t,i;
    reverse(a);
    reverse(b);
    for(i=0;i<len_a || i<len_b;i++){//其中一个未到最高位即可
        //对其中一个进行进位运算
        if(i>=len_a){
            t=b[i]-'0'+acc;
        }
        else if(i>=len_b){
            t=a[i]-'0'+acc;
        }
        //都未到最高位
        else{
            t=a[i]-'0'+b[i]-'0'+acc;
        }
        //进行进位运算
        sum[i]=t%10+'0';
        //acc存储进位值
        if(t>9){
            acc=1;
        }
        else{
            acc=0;
        }
    }
    if(acc==1){
        sum[i++]='1';//最高位进位
    }
    sum[i]='\0';//字符串结束符
    reverse(sum);//反转，从高位到低位
}
int main(){
    system("chcp 936");
    char a[100],b[100],sum[250];
    scanf("%s%s",a,b);
    Sum(a,b,sum);
    printf("%s\n",sum);
}

题目二：

斐波拉契数列的实现函数

代码实现：

int fibonacci_rec(int n){
    if(n==1 || n==2)
        return n;
    else 
        return fibonacci_rec(n-1)+fibonacci_rec(n-2);
}
int fibonacci_loop(int n){
    int a[n+1];
    a[1]=1,a[2]=2;
    for(int i=3;i<n+1;i++){
        a[i]=a[i-1]+a[i-2];
    }
    return a[n];
}   

题目三：

素数的判断

代码实现：

int isPrime(int a){
    //欧拉筛简化--判断素数
    if(a<4){//5以下的素数判断
        return a>1;
    }
    if(a%6!=1 && a%6!=5){//必要性判断：素数必为6及其倍数左右相邻两数
        return 0;
    }
    for(int i=5;i<sqrt(a);i+=6){
        if(a%i==0 || a%(i+2)==0){//充分性判断
            return 0;
        }
    }
    return 1;
    //return 1-->是素数
}

题目四：

Description
小G在玩一个游戏，利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3，假如压缩后的字符串的长度不小于原字符串的长度，则输出原来的字符串。
字符串中只包含小写英文字母（a至z），每个字母的重复次数为1到9次，字符总长度为1~100。

Hint
strlen()可以用来求一个字符串的长度，需要include头文件<string.h>

Input
一行，字符串

Output
输出压缩的字符串或者原字符串

Sample Input
aabcccccaaa
?
Sample Output
a2b1c5a3
?
Sample Input2
abbccd
?
Sample Output2
abbccd
?
(因为压缩后的字符串为a1b2c2d1，长度比原字符串abbccd大，所以输出原字符串)

代码实现：

char* getMinString(char *str){
    int len=strlen(str);//原字符串长度
    int cnt=1,index=0,i;
    int new_str[100];//新字符串
    for(i=0;i<len;i++){
        if(str[i]==str[i+1]){
            cnt++;//计数
        }
        else{//不同字符
            new_str[index++]=str[i];//存入上一个重复的字符
            new_str[index++]=cnt+'0';//存入重复次数
            cnt=1;//重置次数
        }
    }
    new_str[index]='\0';//结尾符
    if(index<len){//判断长度
        for(i=0;i<=index;i++){
            str[i]=new_str[i];
        }
    }
    return str;//返回字符串
}

题目五：

题目
给定一个m x n大小的整数矩阵（m行，n列），按顺时针螺旋的顺序打印矩阵中的所有元素。

例如一个3 x 3 的 矩阵：

1 2 3

4 5 6

7 8 9

输出应为:

1 2 3 6 9 8 7 4 5

数据规模
1 <= n,m <= 10 ，矩阵中任意元素都满足 |val|<=100。

输入样例1
3 3
1 2 3
4 5 6
7 8 9
?
输出样例1
1 2 3 6 9 8 7 4 5

输入样例2
1 1
1
?
输出样例2
1

代码实现：

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

void reverseMatrix(int **matrix,int m,int n){
    int top=0,down=m-1,left=0,right=n-1;
    while(top<=down && left<=right){
        for(int i=left;i<=right;i++){
            printf("%d ",matrix[top][i]);
        }
        top++;
        if(top>down) break;
        for(int i=top;i<=down;i++){
            printf("%d ",matrix[i][right]);
        }
        right--;
        if(right<left) break;
        for(int i=right;i>=left;i--){
            printf("%d ",matrix[down][i]);
        }
        down--;
        if(top>down) break;
        for(int i=down;i>=top;i--){
            printf("%d ",matrix[i][left]);
        }
        left++;
        if(left>right) break;

    }
}   

int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    int **matrix=(int**)malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++){
        matrix[i]=(int*)malloc(sizeof(int)*n);
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&matrix[i][j]);
        }
    }
    reverseMatrix(matrix,m,n);
    for(int i=0;i<m;i++){
        free(matrix[i]);
    }
    free(matrix);
}

题目六：

Description
小猫咪玩游戏，现在有n张牌依次放在地上，牌上有数字，数字的范围是-20~20，正数表示可以奖励对应数目的猫粮，负数表示减去对应数量猫粮。猫咪可以从中连续选择k张牌， 0<=k<=n（k=0表示不选牌，即0包猫粮），即能获得数量为k张牌的数字之和的猫粮。
实现一个函数，求出猫咪最多能获取几包猫粮，1<=数组长度<=100。已提供main函数解决输入输出，只需要实现函数即可

Input
n+1行
第一行一个数字，数组长度n。
接下来的n行输入数组的数字

Output
输出猫咪所能获得的最多猫粮数量

Sample Input
5 
1
2
3
4
5

?
Sample Output
15

?
Sample Input2
5 
1
2
-3
4
5

?
Sample Output2
9

代码实现：

int getMaxNum(int *a,int n){
    int max=0,temp=0;
    for(int i=0;i<n;i++){
        temp=(temp+a[i])>0?(temp+a[i]):0;
        //如果和小于0，则置为0，从下一个数重新加和
        max=max<temp?temp:max;
        //更新最大值
    }
    return max;//返回最大值
}

int main(){
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    printf("%d\n",getMaxNum(a,n));
}

题目七：

Description
给出一个升序的整数数组 A 和升序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个升序的升序数组。
数据范围：0<=n,m<=100, |Ai|<=100, |Bi|<=100
注意：

保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A 的数组空间大小为 m+n
不要返回合并的数组，将数组 B 的数据合并到 A 里面即可
Input
两行数字，m, n，分别表示两个数组的大小。接下来m行输入第一个数组A的元素，然后n行输入第二个数组B的元素。

Output
输出m+n行数字，每一行为合并后数组A的元素

Sample Input
3 3
4
5
6
1
2
3
?
Sample Output
1
2
3
4
5
6
?
Sample Input2
4 3
1
3
5
7
2
4
6
?
Sample Output2
1
2
3
4
5
6
7
1
2
3
4
5
6
7

代码实现：

void mergeTwoSequence(int *a,int *b,int m,int n){
    int p=m+n-1;//尾指针
    m-=1;n-=1;
    while(n>=0){
        while(a[m]<b[n] && n>=0){//b大，存入尾指针指向空间
            a[p--]=b[n--];
        }
        a[p--]=a[m--];
    }
}

题目八：

Description
特工770正在调查一种神秘的病毒，感染这种病毒的人有几率会在每天睡梦里梦见一只可爱的很胖的猫咪。770发现，病毒有1种初始状态，还有6天的潜伏期，在此期间每天每种状态会同时发生下述两种变异，产生两种新状态，同时旧的状态会全部消失。请注意，这两种新状态在次日会各自变异，产生2×2=4种新状态，以此类推。当潜伏期结束后，如果最后一天变异产生的状态中，存在一个状态满足下述条件，那么这个人就会开始梦见猫咪。现在特工770要求你编写一个程序，输入病毒的初始状态，计算潜伏期结束后感染者是否会开始梦见猫咪。

变异规则
病毒状态是一个unsigned int，记为V；病毒已变异次数记为T；

左移变异：若((1<<31)&V)!=0，则V左移T位产生新状态，否则V左移1位产生新状态；
右移变异：若(1&V)!=0，则V右移T位产生新状态，否则V右移1位产生新状态。
梦见猫咪的条件
记常量0x0003C000为M，若最后一天变异产生的某个状态V满足((V&M)^M)==0，则感染者会开始梦见猫咪，请输出yes；否则，感染者不会开始梦见猫咪，请输出no。

Input
一个整数，最小值是0，最大值是pow(2, 32)-1，代表病毒的初始状态。

Output
判断梦见猫咪的条件，输出yes或no（带换行）。

Sample Input
23333
?
Sample Output
no

代码实现：

# define M 0x0003C000
int test_virus(unsigned int V, int T){
    if(T==6){//变异次数达6次
        return ((V&M)^M)==0;//返回判断结果
    }
    else{
        //左变异和右变异分别递归
        return test_virus(V<<(((1<<31)&V)!=0?T:1),T+1) ||
test_virus(V>>((1&V)!=0?T:1),T+1);
    }
}

int main(){
    unsigned int V;
    int T=0;
    scanf("%u",&V);
    if(test_virus(V,T))
        printf("YES\n");
    else
        printf("NO\n");
}

题目九：

Description
给定两个字符串，把它们拼接到一起以后反向输出出来。比如“ab”和"cd"，拼接成"abcd"后按照"dcba"输出。字符串没有空格且长度小于等于40。

Input
输入的第一行为第一个字符串，第二行为第二个字符串。

Output
输入为拼接后的反向输出。

Sample Input
abcdefg
hijklmn
?
Sample Output
nmlkjihgfedcba

代码实现：

void reverse(char *str1,char *str2){
    strcat(str1,str2);//拼接
    int len=strlen(str1);
    for(int i=0;i<len-i-1;i++){//反转字符串
        char ch=str1[i];
        str1[i]=str1[len-i-1];
        str1[len-i-1]=ch;
    }
}

题目十：

Description
如果一个字符串翻转后还是它本身，我们称这个字符串是漂亮的字符串。

实现一个函数，判断一个字符串是否是一个漂亮的字符串，是则输出true，否则输出false。

strlen()可以求一个字符串的长度（需要include<string.h>）

Input
一行，输入的字符串。1<=字符串的大小<=100，每个字符为小写字母，即'a'<=字符<='z'

Output
如果字符串为漂亮的字符串，返回true，否则返回false

Sample Input
aba
?
Sample Output
true
?
Sample Input2
abaa
?
Sample Output2
false
?
Sample Input3
a
?
Sample Output3
true
true

代码实现：

int beautifulString(char *str){
    int len=strlen(str),flag=1;
    for(int i=0;i<len-i-1;i++){
        //首尾字符串比对
        if(str[i]!=str[len-i-1]){
            flag=0;
            break;
        }
    }
    return flag;//flag为1表示这是beautiful字符串
}

题目十一：

Description
现在给定两条字符串，如“abcdabc”和"abc"，要求字符串"abc"在"abcdabc"的最大字符串长度。最大字符串长度指的是"abc"在"abcdabc"连续出现的长度，当匹配的次数大于等于1的时候，不要求"abc"在后面也要保持完整。如"abcab"和“abc”的最大字符串长度为5。
字符串长度不大于10000。

Input
输入的第一个数字 N 代表测试样例数目，接下来有 2?N 行字符串。
每两行字符串的第一个字符串为待匹配的字符串，第二个字符串为要匹配的字符串。

Output
题意要求的最大字符串匹配长度。

Sample Input
2
abcdabc
abc
abcdabcd
abcd
?
Sample Output
3
8
?

代码实现：

int maxStrMatchLen(char *str_a,char *str_b){
    int cnt=0,sum=0,index_b=0;
    int len_a=strlen(str_a);
    int len_b=strlen(str_b);
    if(strstr(str_a,str_b)){//长字符串中是否存在一个短字符串
        cnt++;
        sum+=len_b;
    }
    if(cnt==1){//如果已经存在一个
        //非完整字符也可算入长度
        for(int i=strstr(str_a,str_b)-str_a+len_b;i<len_a;i++){
            if(str_a[i]!=str_b[index_b])
                break;
            else{
                sum++;//更新长度
                if(index_b==len_b-1){//更新短字符串比对下标
                    index_b=0;
                }
                index_b++;//短下标增加
            }
        }
    }
    return sum;
}

int main(){
    char str_a[10000],str_b[10000];
    int n;
    scanf("%d",&n);
    while(n--){
        scanf("%s%s",str_a,str_b);
        printf("the max match str len is : %d\n",maxStrMatchLen(str_a,str_b));
    }
    
}

题目十二：

Description
给定一个字符串s1（只包含小写字母），再给定密钥 n 后将其加密为s2。
输出加密后字符串

加密规则：对于密钥n，将字符串中每一个字符替换为字母表顺序（从左至右）后的第n位字母。
注意'z' 后面是 'a'
例如：密钥n=1， "aabb" -> "bbcc", 'z' -> 'a'

Input
输入的第一行为加密位n，
输入的第二行为字符串s1。
0 <= n <= 26
0 <= s1长度 <= 100

Output
输入字符串s2

Sample Input1
2
abc
?
Sample Output1
cde
?
Sample Input2
0
abc
?
Sample Output2
abc

代码实现：

void transform(int n,char *str){
    char alphabet1[26],alphabet2[26];
    //alphabet1-->正常字母表
    //alphabet2-->转换后的字母表
    for(int i=0;i<26;i++){
        alphabet1[i]='a'+i;
    }
    for(int i=0;i<26;i++){
        if(i+n<26){//未超过26字母
            alphabet2[i]=alphabet1[i]+n;
        }
        else{//超过，从a开始
            alphabet2[i]='a'+i+n-26;
        }
    }
    int len=strlen(str);
    for(int i=0;i<len;i++){
        str[i]=alphabet2[strchr(alphabet1,str[i])-alphabet1];
        //将str[i]在正常字母表中的位置放到转换后的字母表中，进行转换
    }
}

题目十三：

Description
给你一个正整数组成的数组 nums ，返回 nums 中一个 降序 子数组的最大可能元素和。子数组是数组中的一个连续数字序列。

已知子数组

[nums 
l
?
 ,nums 
l+1
?
 ,...,nums 
r?1
?
 ,nums 
r
?
 ]
，若对所有 i（l <= i < r），nums 
i
?
 >nums 
i+1
?
 都成立，则称这一子数组为 降序 子数组。注意，大小为1 的子数组也视作 降序 子数组。

Input
第一行输入数组长度 n
第二个输入数组元素：1, 2, 3, ... （n个）

0 <= n<= 1000
0 <= nums[i] <= 10000

Output
降序子数组最大和

Sample Input1
6
10 20 30 5 10 50
?
Sample Output1
50
?
解释：[50] 是元素和最大的降序子数组，最大元素和为 50 。

Sample Input2
1
10
?
Sample Output2
10
?
Sample Input3
0
?
Sample Output3
0
0

代码实现：

int maxSum(int *num,int len){
    int sum=0,max=0,index=0;
    while(index<len){//防止越界
        int sum=num[index++];//存入当前值
        //防止越界且要满足降序
        while(index<len && num[index]<num[index-1]){
            sum+=num[index++];//存入下一个值，并后移
        }
        max=max<sum?sum:max;//更新最大值
    }
    return max;
}

题目十四：

Description
给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

保证字符c出现在字符串s中。
ps: 若字符串s为空，应输出距离0

Input
第一行字符串长度n
第二行字符串s
第三行字符c

0<= num长度<=500

Output
返回距离数组

Sample Input
12
aobeoeeiqote
e
?
Sample Output
3 2 1 0 1 0 0 1 2 2 1 0
?
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

代码实现：

int main(){
    char str[500],ch;
    int n;
    scanf("%d",&n);
    if(n==0){//一个字符，返回0
        printf("0\n");
        return 0;
    }
    scanf("%s",str);
    scanf(" %c",&ch);//预留一个空格，区分str和ch输入
    int arr[n],target[500],index=0,len=0;
    for(int i=0;i<n;i++){
        if(str[i]==ch){
            target[len++]=i;//标记目标字符数量与位置
        }
    }
    for(int i=0;i<n;i++){
        int min=9999,temp;
        for(int j=0;j<len;j++){
            temp=abs(target[j]-i);//记录每个目标字符与当前字符距离
            min=min>temp?temp:min;//更新最小距离
        }
        arr[index++]=min;//存入距离
    }
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

题目十五：

题目描述
根据主函数和头文件提示，编写两个子函数void removeDigits(char *s);和void reverseStr(char *s);，其功能分别为：删除字符串s中的数字字符；将字符串 s 逆序。其中，当s的长度为0时，void reverseStr(char *s);需要在s中保存表示"NoCharacters"的字符串。

输入格式
输入一个长度不超过100的字符串 s。

输出格式
先移除字符串s中的所有数字符号，再输出处理后的字符串的逆序。

输入样例1
11A2b3C45
?
输出样例1
CbA
?
输入样例2
AAbbccDD
?
输出样例2
DDccbbAA
?
输入样例3
1234567
?
输出样例3
NoCharacters
?
说明：输入的字符串全是数字字符，移除数字字符后字符串长度为0，此时void  reverseStr(char *s);需要在s中保存表示"NoCharacters"的字符串。

代码实现：

void removeDigits(char *s){
    int len=strlen(s);
    int index=0;//慢指针
    for(int i=0;i<len;i++){
        if(!isdigit(s[i])){//非数字
            s[index++]=s[i];//填充
        }
    }
    s[index]='\0';//结尾结束符
}


void reverseStr(char *s){
    int len=strlen(s);
    if(len==0){
        char str[]="NoCharacters";
        int l=strlen(str);
        strcpy(s,str);
        s[l]='\0';//结束符
        return;
    }
    //标准反转法
    for(int i=0;i<len-i-1;i++){
        char ch=s[i];
        s[i]=s[len-i-1];
        s[len-i-1]=ch;
    }
}

题目十六：

题目描述
编写函数void oddReverse(char *s),将所有奇数位的字符反转。

输入格式
输入一个字符串 s

保证输入字符串 s 的长度大于等于1小于等于100

输出格式
输出修改后的字符串 s。

输入样例1
012345

输出样例1
052341

输入样例2
01234

输出样例2
03214

输入样例3
0

输出样例3
0

代码实现：

int main(){
    char str[100];
    scanf("%s",str);
    int len=strlen(str);
    //只有一位奇数位
    if(len<4){
        return 0;
    }
    //两位奇数位及以上
    //偶数位数情况
    if(len%2==0){
        for(int i=1,j=len-1;i<j;i+=2,j-=2){
            char ch=str[i];
            str[i]=str[j];
            str[j]=ch;
        }
    }
    //奇数位数情况
    else{
        for(int i=1,j=len-2;i<j;i+=2,j-=2){
            char ch=str[i];
            str[i]=str[j];
            str[j]=ch;
        }
    }
    printf("%s\n",str);
}

题目十七：

请根据主函数和头文件提示，编写子函数

void merge(int *arr, int start, int mid, int end);
void mergeSort(int *arr, int start, int end);
?
以实现归并排序。

void merge(int *arr, int start, int mid, int end); ：将两个已排序的子数组进行合并，第一个子数组从下标start开始到下标mid结束，第二个子数组从下标mid+1开始到下标end结束。
void mergeSort(int *arr, int start, int end);： 输入数组arr、起始下标start和结束下标end，将arr中从下标start到下标end的子数组进行排序。

代码实现：

void merge(int *arr, int start, int mid, int end){
    int m=start,n=mid,p=mid+1,q=end,index=0;
    int b[end-start+1];//临时存储数组(可以用malloc，之后free掉)
    while(m<=n && p<=q){//都没有越界
        if(arr[m]<arr[p]){
            b[index++]=arr[m++];
        }
        else{
            b[index++]=arr[p++];
        }
    }
    while(m<=n){//只剩前半段
        b[index++]=arr[m++];
    }
    while(p<=q){//只剩后半段
        b[index++]=arr[p++];
    }
    for(int i=start;i<=end;i++){
        arr[i]=b[i-start];//复制到原数组
    }
}

void mergeSort(int *arr, int start, int end){
    if(start>=end)//段中元素为1
        return;
    else{
        int mid=(start+end)/2;//中间位置
        mergeSort(arr,start,mid);//前半段排序
        mergeSort(arr,mid+1,end);//后半段排序
        merge(arr,start,mid,end);//两段合并
    }
}

题目十八：

题目描述
编写函数void rotate(int ** matrix,int n)将一个n*n的矩阵顺时针旋转90度。

输入格式
第一行输入n，
后面输入n*n个数字
1=<n<=10，矩阵中数字非负数

输出格式
按照n*n方阵格式输出矩阵

输入样例1
3
1 2 3
4 5 6
7 8 9

输出样例1
7 4 1
8 5 2
9 6 3

输入样例2
1
1

输出样例2
1

代码实现：

void rotate(int ** matrix,int n){
    int temp;
    for(int i=0;i<n/2;i++){
        for(int j=0;j<n-i-1;j++){
            temp=matrix[i][j];//存储左上角
            matrix[i][j]=matrix[n-1-j][i];//左下角代替左上角
            matrix[n-1-j][i]=matrix[n-i-1][n-j-1];//右下角代替左下角
            matrix[n-i-1][n-j-1]=matrix[j][n-i-1];//右上角代替右下角
            matrix[j][n-i-1]=temp;//原先的左上角代替右上角
        }
    }
}

题目十九：

题目描述
编写函数void myshift(char *s),在不打乱s原本相对位置情况下，将偶数位上的字符全部挪到奇数位字符的前面。

输入格式
输入一个字符串 s

保证输入字符串 s 的长度大于等于1小于等于100

输出格式
输出修改后的字符串 s。

输入样例1
012345

输出样例1
024135

输入样例2
01234

输出样例2
02413

输入样例3
0

输出样例3
0

代码实现：

int len=strlen(s);
    int len1=0;
    int len2=0;
    char tmp[105];
    for(int i=0;i<len;i++){
        if(i%2==0){
            s[len1]=s[i];
            len1++;
        }
        else{
            tmp[len2]=s[i];
            len2++;
        }
    }
    for(int i=0;i<len2;i++)
        s[i+len1]=tmp[i];
}

题目二十：

题目描述
n (n<=100)个学生排队报数，编号为1到n，然后从1数到3循环报数，每次数到3的人就退出，最后留下来的是编号多少的学生。比如，总共4名学生，编号为1，2，3，4。第一次报数1（报数1），2（报数2），3（报数3），4（报数1），3号退出，第二次报数1（报数2），2（报数3），4（报数1），2号退出，依此类推，直到只剩1名学生，输出其编号。

示例输入1
4

示例输出1
1

示例输入2
10

示例输出2
4

代码实现：

int main(){
    int n,k=1,i=0;
    scanf("%d",&n);
    int count=n,end;
    int nums[n];
    for(int i=0;i<n;i++){
        nums[i]=i+1;
    }
    while(count>1){//结束条件：只剩一个编号
        if(nums[i]!=0){//未被标记，则进行报数
            nums[i]=k++;
        }
        if(k>3){//重置报数
            k=1;
        }
        if(nums[i]==3){//标记
            nums[i]=0;
            count--;
        }
        i++;
        if(i==n){//从头进行
            i=0;
        }
    }
    for(int j=0;j<n;j++){
        if(nums[j]!=0){
            printf("%d\n",j+1);
            break;
        }
    }
}

题目二十一：

题目描述
设计一个程序，实现对输入字符串数组按字符串长度进行排序功能。具体要求如下：

编写函数void sortByLength(char *strArray[], int numStrings);，用于对输入的字符串数组 strArray 按字符串长度进行升序排序。

在主程序中，接受用户输入的字符串数组，然后调用函数进行排序。

输出排序后的字符串数组。

第一行输入字符串数量n（n<=20）
第2-（n+1）行输入字符串，每个字符串长度小于100

说明：相同长度的字符串排序按照输入顺序排序

示例输入1：
4

Apple

Banana

Orange

Grapes

示例输出1：
Apple

Banana

Orange

Grapes

代码实现：

void sortByLength(char *strArray[], int numStrings){
    for(int i=0;i<numStrings-1;i++){
        for(int j=numStrings-1;j>i;j--){
            if(strlen(strArray[j])<strlen(strArray[j-1])){
                char *ch=strArray[j];
                strArray[j]=strArray[j-1];
                strArray[j-1]=ch;
            }
        }
    }
}


int main(){
    int numStrings;
    scanf("%d",&numStrings);
    char *strArray[numStrings];
    char inputString[100];
    for(int i=0;i<numStrings;i++){
        scanf("%s",inputString);
        strArray[i]=(char*)malloc(sizeof(char)*100);
        strcpy(strArray[i],inputString);
    }

    sortByLength(strArray,numStrings);

    for(int i=0;i<numStrings;i++){
        printf("%s\n",strArray[i]);
        free(strArray[i]);
        strArray[i]=NULL;
    }
    free(strArray);
    
}

题目二十二：

题目描述
大宝和阿里正在进行一场有趣的翻转游戏。大宝首先写下一个句子，而阿里的任务是写出这个句子的翻转版本。期待你能和他们成功完成这个有趣的挑战！

设计一个程序实现对输入句子中每个单词的反转功能。具体要求如下：

编写一个函数 ?void reverseWords(char *sentence);?，用于对输入句子中的每个单词进行反转。
在主程序中，接受用户输入的句子，然后调用函数进行单词反转。
输出反转后的句子。
示例输入1：
Hello World! Have a nice day.

示例输出1：
olleH dlroW! evaH a ecin yad.

示例输入2：
ni hao, wo shi SYSU

示例输出2：
in oah, ow ihs USYS
?
提示
使用以下函数需声明#include <ctype.h>
函数isspace(a)可判断a字符是否为空格，函数ispunct(a)可判断a字符是否为标点符号
函数strcspn(s, "\n")表示去除数组s中的换行符

代码实现：

void reverse(char *sentence,int start,int m){//反转单个单词
    for(int j=start;j<m-j+start;j++){
        char ch=sentence[j];
        sentence[j]=sentence[m-j+start];
        sentence[m-j+start]=ch;
    }
}

void reverseWords(char *sentence){
    int len=strlen(sentence);
    int start=0,i;
    if(len==0)
        return;
    for(i=1;i<len;i++){
        if(isspace(sentence[i]) && ispunct(sentence[i-1])){
            reverse(sentence,start,i-2);
            // for(int j=start;j<i-2-j+start;j++){
            //     char ch=sentence[j];
            //     sentence[j]=sentence[i-2-j+start];
            //     sentence[i-2-j+start]=ch;
            // }
            start=i+1;//更新反转的起点
        }
        else if(isspace(sentence[i]) && !ispunct(sentence[i-1])){
            reverse(sentence,start,i-1);
            // for(int j=start;j<i-1-j+start;j++){
            //     char ch=sentence[j];
            //     sentence[j]=sentence[i-1-j+start];
            //     sentence[i-1-j+start]=ch;
            // }
            start=i+1;
        }
    }
    //处理末尾
    if(ispunct(sentence[i-1])){
        reverse(sentence,start,i-2);
        // for(int j=start;j<i-2-j+start;j++){
        //     char ch=sentence[j];
        //     sentence[j]=sentence[i-2-j+start];
        //     sentence[i-2-j+start]=ch;
        // }
    }
    else{
        reverse(sentence,start,i-1);
        // for(int j=start;j<i-1-j+start;j++){
        //     char ch=sentence[j];
        //     sentence[j]=sentence[i-1-j+start];
        //     sentence[i-1-j+start]=ch;
        // }
    }
    sentence[i]='\0';//结束符
}

题目二十三：

题目描述
编写一个程序，从用户输入中读取两个整数数组 A 和 B，然后判断数组 B 是否是数组 A 的子数组。如果是，输出 "Yes"以及B 在 A 中的起始位置；如果不是，输出 "No"。
第一行输入数组A的大小
第二行输入数组A
第三行输入数组B的大小
第四行输入数组B
输出结果：如果是子数组，输出"yes"以及B 在 A 中的起始位置；如果不是，输出"No"

示例输入1
5
1 2 3 4 5
3
1 2 3

示例输出1
Yes,0

示例输入2
10
2 4 5 6 2 6 7 4 21 11
5
3 5 2 5 4

示例输出2
No

代码实现：

int main(){
    int m,n;
    scanf("%d",&m);
    int a[m];
    for(int i=0;i<m;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&n);
    int b[n];
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
    }
    int flag=1;
    for(int i=0;i<m-n;i++){
        for(int j=0;j<n;j++){
            if(a[i+j]!=b[j]){
                flag=0;
                break;
            }
            if(j=n-1){
                flag=1;
            }
        }
        if(flag){
            printf("Yes,%d\n",i);
            return 0;
        }
    }
    printf("No\n");
}

题目二十四：

题目描述
编写一个函数void insertAndSort(int n, int a[], int *size);，将n插入到数组a[]中，并按从小到大的顺序输出插入新数后的数组a[]。
输入要求：
第一行输入要插入的数n
第二行输入数组的元素个数size（size<=50）
第三行输入数组元素a[i]

示例输入1
52
6
32 45 353 24 234 564

示例输出1
24 32 45 52 234 353 564

示例输入2
846
10
23 543 5657 232 56 767 744 231 351 31

示例输出2
23 31 56 231 232 351 543 744 767 846 5657

代码实现：

void insertAndSort(int n, int a[], int *size){
    a[*size]=n;
    //bubble sort
    for(int i=0;i<*size;i++){
        for(int j=*size;j>i;j--){
            if(a[j]<a[j-1]){
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
    for(int i=0;i<*size+1;i++)
        printf("%d ",a[i]);
    printf("\n");
}

int main(){
    int n,size;
    scanf("%d%d",&n,&size);
    int a[size+1];
    for(int i=0;i<size;i++)
        scanf("%d",&a[i]);
    insertAndSort(n,a,&size);    
}

题目二十五：

题目描述
请你实现一个函数，它将删除一个链表中节点值为 value 的节点（如果有的话），并将该节点的前后节点（如果有的话）拼接起来以保持链表的连贯性，最后返回链表头，如删除后链表为空则返回NULL。
ListNode.h文件中已经给出链表节点 ListNode 以及函数 deleteNodeOfList 的声明，请在ListNode.c 中实现该函数。

输入输出描述
（你无需处理输入和输出，只需要实现删除函数即可）
输入：第一行输入两个数 n value 分别代表链表的节点数和需要删除的值，第二行输入n个数表示这个链表的每个节点值
输出：删除后的链表的每个节点值，如果链表为空则输出 NULL

链表节点数 n 范围为 [0, 50]
value 以及链表的每个节点的值 val范围为[-100, 100]
保证链表内的节点值两两互不相同
样例输入 1
4 2
1 4 2 3
?
样例输出 1
1 4 3
?
样例输入 2
1 3
5
?
样例输出 2
5
?
样例输入 3
0 1
?
样例输出 3
NULL
?

代码实现：

struct ListNode* deleteNodeOfList(struct ListNode* list, int value){
    if(list==NULL)
        return list;
    struct ListNode *head=list,*prev=list;
    if(head->val==value){
        head=head->next;
        free(prev);
        return head;
    }

    struct ListNode *curr=prev->next;
    while(curr){
        if(curr->val==value){
            prev->next=curr->next;
            free(curr);
            curr=prev->next;
            continue;
        }
        prev=curr;
        curr=prev->next;
    }   
    return head;
}
//递归法
struct ListNode* deleteNodeOfList(struct ListNode* list, int value){
    if(list==NULL)
        return list;
    if(list->val==value){
        struct ListNode *newhead=list->next;
        free(list);
        list=newhead;
        list=deleteNodeOfList(list,value);
    }
    else{
        list->next=deleteNodeOfList(list->next,value);
    }
    return list;//返回最初的head指针
}

题目二十六：

题目描述
请你定义一个结构体表示课程信息，它包括课程名、上课时间和下课时间。现在你要编写一个程序，输入当天的所有课程，然后按照上课时间从早到晚的顺序输出当天课表。

输入输出描述
输入：第一行为当天课程总数 n，接下来 n 行每行有三个值 class_name、start_time 、end_time 分别表示课程名、上课时间和下课时间。
输出：按照上课时间从早到晚的顺序输出当天课表，输出格式类似 08:00 ~ 09:00 : C_Programing，如当天没有课程则输出 QiDong

// printf的格式化字符串输出可参考:
printf("%02d:00 ~ %02d:00 : %s\n", start_time, end_time, class_name);
?
n 范围为 [0, 20]
class_name 是只包含大小写字母以及下划线的字符串，长度范围为 [1, 15]
上下课时间都是整数，且 6≤ start_time < end_time ≤22
保证每门课的上课时间两两互不相同
样例输入 1
5
C_Programing 10 12
English 7 9
Physics 13 15
Calculus 18 19
PE 16 17
?
样例输出 1
07:00 ~ 09:00 : English
10:00 ~ 12:00 : C_Programing
13:00 ~ 15:00 : Physics
16:00 ~ 17:00 : PE
18:00 ~ 19:00 : Calculus
?
样例输入 2
0
0
?
样例输出 2
QiDong

代码实现：

struct Class{
    char class_name[20];
    int start_time;
    int end_time;
};

int cmp(const void *a,const void *b){
    return (*(struct Class*)a).start_time-(*(struct Class*)b).start_time;
}
int main(){
    int n;
    scanf("%d",&n);
    if(n==0){
        printf("QiDong!\n");
        return 0;
    }
    struct Class lesson[n];
    for(int i=0;i<n;i++)
        scanf("%s%d%d",lesson[i].class_name,&lesson[i].start_time,&lesson[i].end_time);
    qsort(lesson,n,sizeof(struct Class),cmp);
    for(int i=0;i<n;i++){
        printf("%02d:00 ~ %02d:00 : %s\n", lesson[i].start_time,lesson[i].end_time,
        lesson[i].class_name);
    }
}

题目二十七：

题目描述
请对链表排序问题使用归并排序吧！

从小到大排序，尽量不使用数组而在原链表上进行排序。

输入描述
第一行为正整数n，代表链表节点个数。0 <= n <= 200000
第二行为n个数，代表链表节点的数值。

样例输入
5
5 4 2 1 3
?
样例输出
1 -> 2 -> 3 -> 4 -> 5 -> null
?
提示
归并排序的实现可能需要使用到以下知识：

递归
链表拆分 -- 快慢指针
链表合并 -- 尽量使用迭代(递归可能会爆栈)

代码实现：

struct ListNode {
	int val;
	struct ListNode* next;
};

struct ListNode* mergeSort(struct ListNode* head){
    if(head==NULL || head->next==NULL)
        return head;
    struct ListNode *prev=NULL;
    struct ListNode *slow=head,*fast=head;
    while(fast!=NULL && fast->next!=NULL){
        prev=slow;
        slow=slow->next;
        fast=fast->next->next;
    }

    prev->next=NULL;
    struct ListNode *list1=mergeSort(head);
    struct ListNode *list2=mergeSort(slow);

    return merge(list1,list2);
}

struct ListNode* merge(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *head=(struct ListNode*)malloc(sizeof(struct ListNode));
    head->next=NULL;
    struct ListNode *curr=head;
    while(list1!=NULL || list2!=NULL){
        if(list1==NULL){
            curr->next=list2;
            curr=curr->next;
            list2=list2->next;
        }
        else if(list2==NULL){
            curr->next=list1;
            curr=curr->next;
            list1=list1->next;
        }
        else{
            int val1=list1->val;
            int val2=list2->val;
            if(val1<val2){
                curr->next=list1;
                curr=curr->next;
                list1=list1->next;
            }
            else{
                curr->next=list1;
                curr=curr->next;
                list1=list1->next;
            }
        }
    }
    curr->next=NULL;
    struct ListNode *res=head->next;
    free(head);
    return res;
}

题目二十八：

题目描述
用链表实现一个栈及相关函数，需要实现的函数如下：

struct Stack* initStack();初始化一个栈，返回其指针。
int top(struct Stack* stack);获取栈顶元素，若栈为空，返回-1。
void push(struct Stack* stack, int val);插入一个元素。
int pop(struct Stack* stack);删除一个元素，返回元素值，若栈为空，返回-1。
int empty(struct Stack* stack);检查栈是否为空，若为空返回1，若不空返回0。
void freeStack(struct Stack* stack);释放栈的内存。
保证栈中每一个元素val都大于等于0。

输入描述
第一行输入正整数n，代表程序需要执行的操作数。
接下来n行，每行包含字符串s(操作种类)及操作需要的参数。

1 <= n <= 1000

样例输入
15
top
empty
push 2
push 3
top
empty
pop
push 6
push 7
pop
pop
pop
pop
push 9
top
?
样例输出
top: fail
stack empty: true
push: 2
push: 3
top: 3
stack empty: false
pop: 3
push: 6
push: 7
pop: 7
pop: 6
pop: 2
pop: fail
push: 9
top: 9

?
提示
栈 -- 先进后出

代码实现：

struct ListNode {
	int val;
	struct ListNode* next;
};

struct Stack {
	struct ListNode* head;
};

struct Stack* initStack(){
    struct Stack *stack=(struct Stack*)malloc(sizeof(struct Stack));
    struct ListNode *head=(struct ListNode*)malloc(sizeof(struct ListNode));
    head->next=NULL;
    stack->head=head;
    return stack;
}

int top(struct Stack* stack){
    if(stack->head=NULL)
        return -1;
    else
        return stack->head->val;
}

void push(struct Stack* stack, int val){
    struct ListNode *newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    newnode->val=val;
    newnode->next=stack->head->next;
    stack->head->next=newnode;
}
int pop(struct Stack* stack){
    if(empty(stack)) return -1;
    struct ListNode *head=stack->head;
    struct ListNode *curr=head->next;
    int val=curr->val;
    head->next=curr->next;
    curr->next=NULL;
    free(curr);
    return val;
}

int empty(struct Stack* stack){
    return stack->head->next==NULL;
}

void freeStack(struct Stack* stack){
    struct ListNode *head=stack->head;
    while(head!=NULL){
        struct ListNode *temp=head;
        head=head->next;
        temp->next=NULL;
        free(temp);
    }
    free(stack);
}

暂时写这么多，后续复习补充