关于二叉树递归的函数设计

壳970527

1. // pae12-2.c
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. struct node {
   
6.    int val;
   
7.    struct node *next;
   
8. };
   
9. typedef struct node *LIST;
   
10. LIST divide(LIST x, int p) ;
    
11. LIST merge(LIST x, LIST y) ;
    
12. 
    
13. int list_len(LIST x) {//リストの要素数を求める関数
    
14.    if (x == NULL) return 0;
    
15.    return 1 + list_len(x->next);
    
16. }
    
17. void list_show(char *m, LIST x) {//リストにある値を表示する関数
    
18.    printf("%s:", m);
    
19.    while (x != NULL) {
    
20.       printf("%d ", x->val);
    
21.       x = x->next;
    
22.    }
    
23.    printf("\n");
    
24. }
    
25. LIST add_top(LIST x, int v) {//リストxの先頭に、値vを繋げたリストを返す関数
    
26.    LIST t;
    
27.    t = (LIST) malloc(sizeof(struct node));
    
28.    if (t == NULL) {
    
29.       printf("malloc failed");
    
30.       exit(-1);
    
31.    }
    
32.    t->val = v;
    
33.    t->next = x;
    
34.    return t;
    
35. }
    
36. int main(void) {
    
37.    int i, len;
    
38.    LIST list1 = NULL, list2, mix;
    
39.    printf("length: ");fflush(stdout);
    
40.    scanf("%d", &len);
    
41.    for (i = len; i >= 1; i--)
    
42.       list1 = add_top(list1, 100+i);
    
43.    list2 = divide(list1, list_len(list1) / 2);
    
44.    list_show("list1", list1);
    
45.    list_show("list2", list2);
    
46.    mix = merge(list2, list1);
    
47.    list_show("mixed", mix);
    
48.    return 0;
    
49. }
    
50. 
    
51. LIST divide(LIST x, int p) {
    
52. return(,p-1)
    
53. }
    
54. LIST merge(LIST x, LIST y) {
    
55. 
    
56. }
    

复制代码

最下面的2个函数风别是divide和merge，divide的意思是需要把这个函数给断开，也就是让他的next为NULL，断开的下一个结构体为一个新的list2；2个函数需要利用递归，第一个函数返回值要是return(,p-1)这个格式的，再把这两个组合起来，让list2和list1交叉起来，我思考了很久可是不知道从何下手
下面是当函数设计成功后运行程序之后输入数字5或者6出来的结果
length: 5
  list1:101 102
  list2:103 104 105
  mixed:103 101 104 102 105

length: 6
  list1:101 102 103
  list2:104 105 106
  mixed:104 101 105 102 106 103

ghimi

哇，你这注释是日语吗:mag:

壳970527

ghimi 发表于 2022-12-20 15:04
哇，你这注释是日语吗:mag:

- -这个不是重点，解题。。

jhq999

壳970527 发表于 2022-12-20 15:08
- -这个不是重点，解题。。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. struct node {
   
5.    int val;
   
6.    struct node *next;
   
7. };
   
8. typedef struct node *LIST;
   
9. LIST divide(LIST x, int p) ;
   
10. LIST merge(LIST x, LIST y) ;
    
11. 
    
12. int list_len(LIST x) {//リストの要素数を求める関数
    
13.    if (x == NULL) return 0;
    
14.    return 1 + list_len(x->next);
    
15. }
    
16. void list_show(char *m, LIST x) {//リストにある値を表示する関数
    
17.    printf("%s:", m);
    
18.    while (x != NULL) {
    
19.       printf("%d ", x->val);
    
20.       x = x->next;
    
21.    }
    
22.    printf("\n");
    
23. }
    
24. LIST add_top(LIST x, int v) {//リストxの先頭に、値vを繋げたリストを返す関数
    
25.    LIST t;
    
26.    t = (LIST) malloc(sizeof(struct node));
    
27.    if (t == NULL) {
    
28.       printf("malloc failed");
    
29.       exit(-1);
    
30.    }
    
31.    t->val = v;
    
32.    t->next = x;
    
33.    return t;
    
34. }
    
35. int main(void) {
    
36.    int i, len;
    
37.    LIST list1 = NULL, list2, mix;
    
38.    printf("length: ");fflush(stdout);
    
39.    scanf("%d", &len);
    
40.    for (i = len; i >= 1; i--)
    
41.       list1 = add_top(list1, 100+i);
    
42.    list2 = divide(list1, list_len(list1) / 2);
    
43.    list_show("list1", list1);
    
44.    list_show("list2", list2);
    
45.    mix = merge(list2, list1);
    
46.    list_show("mixed", mix);
    
47.    return 0;
    
48. }
    
49. 
    
50. LIST divide(LIST x, int p) {
    
51.     if(p&&x)
    
52.     {
    
53.         p--;
    
54.         while(p&&x->next)
    
55.         {
    
56.             x=x->next;
    
57.             p--;
    
58.         }
    
59.         LIST tmp=x->next;
    
60.         x->next=NULL;
    
61.         return tmp;
    
62.     }
    
63. 
    
64.     return x;
    
65. }
    
66. LIST merge(LIST x, LIST y) {
    
67.     if(NULL==x)
    
68.     {
    
69.         return y;
    
70. 
    
71.     }
    
72.     if(NULL==y)
    
73.     {
    
74.         return x;
    
75. 
    
76.     }
    
77.     LIST tmp=merge(x->next,y->next);
    
78.     x->next=y;
    
79.     y->next=tmp;
    
80.     return x;
    
81. 
    
82. }

复制代码

1. length: 6
   
2. list1:101 102 103
   
3. list2:104 105 106
   
4. mixed:104 101 105 102 106 103
   
5. 
   
6. Process returned 0 (0x0)   execution time : 1.877 s
   
7. Press any key to continue.

复制代码

1. length: 5
   
2. list1:101 102
   
3. list2:103 104 105
   
4. mixed:103 101 104 102 105
   
5. 
   
6. Process returned 0 (0x0)   execution time : 2.032 s
   
7. Press any key to continue.
   

复制代码

壳970527

jhq999 发表于 2022-12-20 15:32

感谢大佬的回答，第一个divide这个函数的返回值能不能改成return divide(,p-1)这种形式尝试写一下函数

1. LIST divide(LIST x, int p) {
   
2.    if (p=0)
   
3.    {
   
4.       return x;
   
5.    }
   
6.    else
   
7.    {
   
8.       x = x->next;
   
9.    }
   
10.    return divide(x,p-1)
    
11.    
    
12. }

复制代码

我自己写的但是还是有问题，就是无法让那个x.next为NULL要不然又进行不下去了- -

壳970527

第二个函数很正确

ghimi

1. LIST divide(LIST x, int p){
   
2.     int len = list_len(x);
   
3.     LIST prev;
   
4.     for (int i = 0; i < p; i++){
   
5.         prev = x;
   
6.         x = x->next;
   
7.     }
   
8.     prev->next = NULL;
   
9.     return x;
   
10. }
    
11. LIST merge(LIST x, LIST y){
    
12.     int len = list_len(x) + list_len(y);
    
13.     int array[len];
    
14.     int i = 0;
    
15.     while (i < len){
    
16.         if (x != NULL){
    
17.             array[i++] = x->val;
    
18.             x = x->next;
    
19.         }
    
20. 
    
21.         if (y != NULL){
    
22.             array[i++] = y->val;
    
23.             y = y->next;
    
24.         }
    
25.     }
    
26.     LIST ret = NULL;
    
27.     for (i = len-1; i >= 0; i--){
    
28.         ret = add_top(ret,array[i]);
    
29.     }
    
30.     return ret;
    
31. }
    

复制代码

打个样

壳970527

ghimi 发表于 2022-12-20 15:45
打个样

第一个divide这个函数的返回值能不能改成return divide(,p-1)这种形式尝试写一下函数
大佬第二个函数相当于再算了一次全过程呀，这样不行的

ghimi

jhq999 发表于 2022-12-20 15:32

merge 代码写的很巧妙，学习了&#128077;

ghimi

1. LIST divide(LIST x, int p)
   
2. {
   
3.     LIST tmp;
   
4.     if (p == 0)
   
5.         return x;
   
6.     else {
   
7.         tmp = x->next;
   
8.         if(p == 1){
   
9.         x->next = NULL;
   
10. 
    
11.         }
    
12.     }
    
13.     return divide(tmp, p - 1);
    
14. }

复制代码

壳970527

ghimi 发表于 2022-12-20 16:07

感谢，看完我明白了，我一直卡在那个地方，原来添加一个参数就可以解决了

jhq999

壳970527 发表于 2022-12-20 15:42
感谢大佬的回答，第一个divide这个函数的返回值能不能改成return divide(,p-1)这种形式尝试写一下函数

...

粗心大意，没想到第一个简单的叠代还需要递归，幸亏后面有人解答

壳970527

jhq999 发表于 2022-12-20 16:27
粗心大意，没想到第一个简单的叠代还需要递归，幸亏后面有人解答

感谢大佬的第二个函数！