C语言链表和递归练习

递归函数

1. 使用递归方法，求解 x的n次方。其中 n 为整数， x 不等于 0。

#include <stdio.h>

int cac(long long x, int n);

int main() {
    printf("%d", cac(2, 10));
}

int cac(long long x, int n) {
    int sum;
    if (n == 1)
        return x;
    return x * cac(x, --n);
}

3. ‌__斐波那契数列__‌

   每个数是前两个数的和，例如0、1、1、2、3、5、8、13等。

   #include <stdio.h>
   
   int f(int n) {   //生成第n项
       if (n == 0) {
           return 0;
       }
       else if (n == 1) {
           return 1;
       }
       else {
           return f(n - 1) + f(n - 2);  //直接递归到第一项和第二项,加回到第n项
       }
   }
   void gF(int n) {
       printf("Fibonacci Sequence: \n");
   
       for (int i = 0; i < n; i++) {
           printf("%d ", f(i)); //生成第1到n项
       }
       printf("\n");
   }
   
   int main() {
       int n;
   
       printf("Enter the number of terms: ");
       scanf("%d", &n);
   
       if (n <= 0) {
           printf("Please enter a positive integer.\n");
       }
       else {
           gF(n);  //进入生成数列
       }
   
       return 0;
   }
   

   这个递归算法用于计算斐波那契数列的第 n 项。其原理如下：

   1. 基本情况：
      • 如果 n == 0，返回 0。这是数列的第一个数。
      • 如果 n == 1，返回 1。这是数列的第二个数。
   2. 递归情况：
      • 对于 n > 1，算法通过调用 fibonacci(n - 1) 和 fibonacci(n - 2) 来计算第 n 项。即每一项是前两项之和。
      • 递归调用会持续进行，直到回到基本情况 n == 0 或 n == 1。

   递归流程：

   • 计算 fibonacci(n) 时，它首先计算 fibonacci(n - 1) 和 fibonacci(n - 2)，然后将结果相加。
   • 这种方法不断拆解问题，直到达到基本情况为止。

   示例：

   计算 fibonacci(4) 时：

   • fibonacci(4) = fibonacci(3) + fibonacci(2)
   • fibonacci(3) = fibonacci(2) + fibonacci(1)
   • fibonacci(2) = fibonacci(1) + fibonacci(0)
   • fibonacci(1) = 1
   • fibonacci(0) = 0

   通过这种方式，最终将得到结果。

   性能问题：

   • 这个递归算法的时间复杂度是 O(2^n)，因为每个递归调用都会引发两个子调用。对于较大的 n，这种方式会变得非常低效，重复计算了很多相同的子问题。因此，在实际应用中，通常会使用动态规划或记忆化递归来优化性能。

     ---

4. 求正整数x的各位数（按从高到低位输出）。

   #include <stdio.h>
   
   int place(int x) {
       if (x < 10) {
           printf("%d ", x); //只有一位数时直接输出
           return x;
       }
       else {
           place(x / 10);     // 递归调用，先输出高位数字
           printf("%d ", x % 10);  // 输出当前最低位数字
       }
   }
   
   int main() {
       place(123);
       return 0;
   }
   

   ---

5. 求整型数组中的最大元素。

   #include <stdio.h>
   
   // 递归函数，用于求整型数组中的最大元素
   int findMax(int arr[], int n) {
       if (n == 1) {
           // 基本情况：数组只有一个元素
           return arr[0];
       }
       else {
           // 递归调用，找到剩余部分的最大值
           int maxOfRest = findMax(arr, n - 1);
           // 返回当前元素和剩余部分最大值中的较大值
           return (arr[n - 1] > maxOfRest) ? arr[n - 1] : maxOfRest;
       }
   }
   
   int main() {
       int arr[10] = { 1,3,5,3,76,3,784,89,9,3 };
       printf("%d", findMax(arr, 10));
       return 0;
   }
   

   ---

6. 在排好序数组中查找特定元素的递归算法，通过将数组分成两半来缩小搜索范围。

   #include <stdio.h>
   
   int search(int *arr, int x, int left, int right) {
       if (left > right)return -1;   //如果左右两侧交叉，那么寻找失败
       int mid = (left + right) / 2;  //计算中间值
       if (x == arr[mid])     //找到
           return mid;
       x > arr[mid] ? search(arr , x,mid +1, right) : search(arr,x,left,mid-1);  //二分法，缩小范围继续寻找
   }
   
   int main() {
       int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
       printf("%d", search(arr,9,0,10)); //输出下标
       return 0;
   }
   

   ---

7. 求1+2+3+…+n。

   #include <stdio.h>
   
   int add(int n) {
       if (n == 1) return 1;
       return n + add(n - 1);
   }
   
   int main() {
      
       printf("%d",add(10));
       return 0;
   }
   

   ---

8. 求两个数的最大公约数。

   #include <stdio.h>
   
   int maxfactor(int x, int y) {
       if (x < y) {
           int tmp = x;
           x = y;
           y = tmp;
       }
       if (y == 0) return x;
       else return maxfactor(y, x % y);
   }
   
   int main() {
       printf("%d", maxfactor(36, 40));
       return 0;
   }
   

   欧几里得算法：给定两个数 a 和 b，不断用较大的数除以较小的数，取余数，直到余数为 0，最后非零的余数即为最大公因数。

   给定两个数 aaa 和 bbb。

   计算 a mod  b（即 a 除以 b 的余数）。

   如果余数为 0，那么 b就是最大公因数。

   如果余数不为 0，将 b 和余数作为新的两个数，继续进行相同的操作。

   重复直到余数为 0。

   ---

9. 猴子吃桃问题：有一只猴子摘了一大堆桃子吃，它按照这样的规律吃桃子：第一天吃一半多一个，第二天吃第一天剩余的一半多一个，第三天吃第二天剩余的一半多一个…以此类推，当第七天时，恰好只剩下一个桃子。求猴子一共摘了多少个桃子？提示，n：表示第几天 F(n)：表示第n天有多少个桃子

   #include <stdio.h>
   
   int monekey(int day) {
       if (day == 7) return 1;
       return 2 * (monekey(day + 1) + 1);
   }
   
   int main() {
       printf("%d", monekey(1));
       return 0;
   }
   

   思路：

   1. 设 F(n) 表示第 n 天剩余的桃子数。
   2. 根据题目，每天的桃子数为：第二天吃剩下的桃子数的一半多一个。
   3. 第七天剩下一个桃子，即 F(7) = 1。
   4. 我们需要从第七天反推到第一天的桃子数。

   递推关系：

   • F(n) = (F(n+1) + 1) * 2 （因为每天剩余的桃子数等于前一天剩余的桃子数加1后乘2）

   从第七天 F(7) = 1 开始反推，直到第1天的桃子数。

   ---

10. 一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:跳上第 1 级台阶只有一种跳法：直接跳 1 级即可。跳上第 2 级台阶有两种跳法：每次跳 1 级，跳两次；或者一次跳 2 级。问要跳上第 n 级台阶有多少种跳法？

    #include <stdio.h>
    
    int jump(int n) {
        if (n <= 2) return n;
        return jump(n - 1) + jump(n - 2);
    }
    
    int main() {
        printf("%d", jump(10));
        return 0;
    }
    

    每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。

    第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。

    第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没跳，剩下的n-2个台阶的跳法有f(n-2)种。

    所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。

    ---

    链表

11. 带头/不带头结点的前插入法建链表。

    chain* appendchain(chain* head, int value) {
        chain* newchain = (chain*)malloc(sizeof(chain));
        if (!newchain) {
            printf("malloc error");
            exit(0);
        }
        newchain->next = head;
        newchain->data = value;
        newchain->last = NULL;
        return newchain;
    }
    

12. 带头/不带头结点的后插入法建链表。

    chain* appendchain(chain* head, int value) {
        chain* newchain = (chain*)malloc(sizeof(chain));
        if (!newchain) {
            printf("malloc error");
            exit(0);
        }
        newchain->next = head;
        newchain->data = value;
        newchain->last = NULL;
        return newchain;
    }
    

13. 给出（初步）结构体（结构体中的成员名不能减少，可根据需要增加）

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

typedef struct Student {
    struct Student* last;
    struct Student* next;
    int  no;
    char name[16];
    int  chinese;
    int  math;
    int  english;
    int all;
} Student;

Student* add(Student* header) {
    Student* chain = (Student*)malloc(sizeof(Student));
    chain->last = header;
    chain->next = NULL;
    scanf("%d\t%s\t%d\t%d\t%d",
        &chain->no,
        &chain->name,
        &chain->chinese,
        &chain->math,
        &chain->english
    );
        return chain;
 
}

int printchain(Student* chain) {
    chain = chain->next;
    if (chain == NULL)
        return 0;
    while (1) {
        if (chain == NULL)
            return 0;
        printf("%d\t%s\t%d\t%d\t%d",
            chain->no,
            chain->name,
            chain->chinese,
            chain->math,
            chain->english
        );
        if (chain->all >= 0) printf("\t%d\n",chain->all);
        else printf("\n");

        if (chain->last == NULL) {
            printf("NULL");
            printf("\n");
            return 0;
        }
        chain = chain->next;
    }
}

int caculate(Student* header) {
    header = header->next;
    while (header != NULL) {
        header->all = header->chinese + header->math + header->english;
        header = header->next;
    }
    return 0;
}

int exchange(Student* chain1, Student* chain2) {
    if (chain1->next != chain2 || chain2->last != chain1) {
        if (chain1->last) chain1->last->next = chain2;
        if (chain1->next) chain1->next->last = chain2;
        if (chain2->next) chain2->next->last = chain1;
        if (chain2->last)chain2->last->next = chain1;
        Student tmp;
        tmp.last = chain1->last;
        tmp.next = chain1->next;
        chain1->next = chain2->next;
        chain1->last = chain2->last;

        chain2->last = tmp.last;
        chain2->next = tmp.next;
        return 0;
    }
    if (chain1->last) chain1->last->next = chain2;
    if (chain2->next) chain2->next->last = chain1;
    Student tmp;
    tmp.last = chain1->last;
    chain1->next = chain2->next;
    chain1->last = chain2;

    chain2->last = tmp.last;
    chain2->next = chain1;
    return 0;
}


int range(Student* stu) {
    Student* tmp = stu->next;
    int flag = 0;
    do {
        flag = 0;
        tmp = stu->next;
        while (tmp != NULL && tmp->next != NULL) {
            if (tmp->all < tmp->next->all) {
                exchange(tmp, tmp->next);
                flag = 1;
            }
            tmp = tmp->next;
        }

    } while (flag);
    return 0;
}

int main() {
    Student* header = (Student*)malloc(sizeof(Student));
    Student* tmp = header;
    for (int i = 0; i < 30; i++) {
        tmp->next = add(tmp);
        tmp = tmp->next;
    }

    caculate(header);
    range(header);
    printchain(header);


    return 0;
}

编程要求：（提示：不改变链接指针，只交换数据域即可）

①对30人的班级按３门课总分从高到低的次序给出排名，输出形式如下：

　　　学号　姓名　语文　数学　英语　总分　排名

②必须用循环实现，__不能__用现成的排序函数；

③需体现模块化思想。

1. 连接两个链表。

   int attach(Student* header1, Student* header2) {
       if (header1 == NULL || header2 == NULL) return 0;
       Student* tmp = header1;
       while (tmp->next == NULL) {
           tmp = tmp->next;
       }
       tmp->next = header2;
       header2->last = tmp;
       return 0;
   }
   

2. 反向输出一个链表。

   int reprintchain(Student* chain) {  //从尾部节点往前输出
       Student* tmp =chain;   //链表头节点没有数据从下一个节点开始
       chain = chain->next;   //如果头节点有数据请删除前两行
       if (chain == NULL)
           return 0;
       while (chain->next != NULL) {
           chain = chain->next;
       }
       while (1) {
           if (chain == tmp)
               return 0;
           printf("%d\t%s\t%d\t%d\t%d",
               chain->no,
               chain->name,
               chain->chinese,
               chain->math,
               chain->english
           );
           if (chain->all >= 0) printf("\t%d\n", chain->all);
           else printf("\n");
           chain = chain->last;
       }
   }
   

3. 设一个单向链表结点的数据类型定义为：

struct node{

int x;

struct node * next;

};

定义一个 fun 函数遍历 h 所指向的链表的所有结点，当遇到 x 值为奇数的结点时，将该结点移到 h 链表的第一个结点之前，函数返回链表首结点地址。分别输出原始链表及修改后链表中所有结点的 x 值。

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

typedef struct node{
    int x;
    struct node * next;
} node;

node* appendchain(node* head, int value) {
    node* newchain = (node*)malloc(sizeof(node));
    if (!newchain) {
        printf("malloc error");
        exit(0);
    }
    newchain->x = value;
    newchain->next = NULL;
    return newchain;
}

node* search(node* header) {  //寻找奇数找到返回地址，没找到返回NULL
    if (header == NULL) {
        printf("no\n");
        return NULL;
    }
    if (header->x % 2 == 1) {
        printf("y");
        return header;
    }
    else return NULL;
    if (header->next == NULL) {
        printf("no\n");
        return NULL;
    }
}

int main() {
    node* header = (node*)malloc(sizeof(node));
    node* tmp = header;
    int x;
    for (int i = 0; i < 4; i++) { //创建链表，头节点不含数据
        scanf("%d", &x);
        tmp->next = appendchain(tmp,x);
        tmp = tmp->next;
    }
    
    tmp = header ->next;
    node* index;
    do {
        index = search(tmp);
        if (index == NULL || index == header->next) {  //处理第一个是奇数和不是奇数的情况
            tmp = tmp->next;
            if(tmp == NULL) break;
            continue;
        }
        node* tmp2 = header;
        while (tmp2->next != index) { //处理奇数节点上一个节点的next
            tmp2 = tmp2->next;
        }
        if (index->next == NULL) {  //处理最后一个节点是奇数的情况，上一个节点的next=NULL
            tmp2->next = NULL;
        }
        else tmp2->next = tmp2->next->next; //不是最后一个节点，处理奇数节点前一个节点的next为奇数节点的后一个节点
        tmp = tmp->next;  //更新tmp
        index->next = header->next; //交换节点数据
        header->next = index;
        
    } while (tmp != NULL);  //遍历到末尾节点

}

1. 设一个单向链表结点的数据类型定义为： struct node{int x;struct node *next;};在 head 指向的单向链表中查找是否出现多个x值相同的结点。如果发现存在这样的结点，则保留第一个结点，删除其他重复出现的结点。
2. 统计候选人选票。设有十个候选人，每次输入一个得票的候选人的名字，要求最后输出十个候选人的得票结果。