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

壳970527

// pae12-2.c
#include <stdio.h>
#include <stdlib.h>

struct node {
   int val;
   struct node *next;
};
typedef struct node *LIST;
LIST divide(LIST x, int p) ;
LIST merge(LIST x, LIST y) ;

int list_len(LIST x) {//リストの要素数を求める関数
   if (x == NULL) return 0;
   return 1 + list_len(x->next);
}
void list_show(char *m, LIST x) {//リストにある値を表示する関数
   printf("%s:", m);
   while (x != NULL) {
      printf("%d ", x->val);
      x = x->next;
   }
   printf("\n");
}
LIST add_top(LIST x, int v) {//リストxの先頭に、値vを繋げたリストを返す関数
   LIST t;
   t = (LIST) malloc(sizeof(struct node));
   if (t == NULL) {
      printf("malloc failed");
      exit(-1);
   }
   t->val = v;
   t->next = x;
   return t;
}
int main(void) {
   int i, len;
   LIST list1 = NULL, list2, mix;
   printf("length: ");fflush(stdout);
   scanf("%d", &len);
   for (i = len; i >= 1; i--)
      list1 = add_top(list1, 100+i);
   list2 = divide(list1, list_len(list1) / 2);
   list_show("list1", list1);
   list_show("list2", list2);
   mix = merge(list2, list1);
   list_show("mixed", mix);
   return 0;
}

LIST divide(LIST x, int p) {
return(,p-1)
}
LIST merge(LIST x, LIST y) {

}

最下面的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
- -这个不是重点，解题。。

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

struct node {
   int val;
   struct node *next;
};
typedef struct node *LIST;
LIST divide(LIST x, int p) ;
LIST merge(LIST x, LIST y) ;

int list_len(LIST x) {//リストの要素数を求める関数
   if (x == NULL) return 0;
   return 1 + list_len(x->next);
}
void list_show(char *m, LIST x) {//リストにある値を表示する関数
   printf("%s:", m);
   while (x != NULL) {
      printf("%d ", x->val);
      x = x->next;
   }
   printf("\n");
}
LIST add_top(LIST x, int v) {//リストxの先頭に、値vを繋げたリストを返す関数
   LIST t;
   t = (LIST) malloc(sizeof(struct node));
   if (t == NULL) {
      printf("malloc failed");
      exit(-1);
   }
   t->val = v;
   t->next = x;
   return t;
}
int main(void) {
   int i, len;
   LIST list1 = NULL, list2, mix;
   printf("length: ");fflush(stdout);
   scanf("%d", &len);
   for (i = len; i >= 1; i--)
      list1 = add_top(list1, 100+i);
   list2 = divide(list1, list_len(list1) / 2);
   list_show("list1", list1);
   list_show("list2", list2);
   mix = merge(list2, list1);
   list_show("mixed", mix);
   return 0;
}

LIST divide(LIST x, int p) {
    if(p&&x)
    {
        p--;
        while(p&&x->next)
        {
            x=x->next;
            p--;
        }
        LIST tmp=x->next;
        x->next=NULL;
        return tmp;
    }

    return x;
}
LIST merge(LIST x, LIST y) {
    if(NULL==x)
    {
        return y;

    }
    if(NULL==y)
    {
        return x;

    }
    LIST tmp=merge(x->next,y->next);
    x->next=y;
    y->next=tmp;
    return x;

}

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

Process returned 0 (0x0)   execution time : 1.877 s
Press any key to continue.

length: 5
list1:101 102
list2:103 104 105
mixed:103 101 104 102 105

Process returned 0 (0x0)   execution time : 2.032 s
Press any key to continue.

壳970527

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

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

LIST divide(LIST x, int p) {
   if (p=0)
   {
      return x;
   }
   else
   {
      x = x->next;
   }
   return divide(x,p-1)
   
}

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

壳970527

第二个函数很正确

ghimi

LIST divide(LIST x, int p){
    int len = list_len(x);
    LIST prev;
    for (int i = 0; i < p; i++){
        prev = x;
        x = x->next;
    }
    prev->next = NULL;
    return x;
}
LIST merge(LIST x, LIST y){
    int len = list_len(x) + list_len(y);
    int array[len];
    int i = 0;
    while (i < len){
        if (x != NULL){
            array[i++] = x->val;
            x = x->next;
        }

        if (y != NULL){
            array[i++] = y->val;
            y = y->next;
        }
    }
    LIST ret = NULL;
    for (i = len-1; i >= 0; i--){
        ret = add_top(ret,array[i]);
    }
    return ret;
}

打个样

壳970527

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

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

ghimi

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

merge 代码写的很巧妙，学习了👍

ghimi

LIST divide(LIST x, int p)
{
    LIST tmp;
    if (p == 0)
        return x;
    else {
        tmp = x->next;
        if(p == 1){
        x->next = NULL;

        }
    }
    return divide(tmp, p - 1);
}

壳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
粗心大意，没想到第一个简单的叠代还需要递归，幸亏后面有人解答

感谢大佬的第二个函数！