关于二叉树递归的函数设计
本帖最后由 壳970527 于 2022-12-20 16:21 编辑// 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 哇,你这注释是日语吗:mag: ghimi 发表于 2022-12-20 15:04
哇,你这注释是日语吗:mag:
- -这个不是重点,解题。。 本帖最后由 jhq999 于 2022-12-20 15:39 编辑
壳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.
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 于 2022-12-20 15:45 编辑
第二个函数很正确 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;
int i = 0;
while (i < len){
if (x != NULL){
array = x->val;
x = x->next;
}
if (y != NULL){
array = y->val;
y = y->next;
}
}
LIST ret = NULL;
for (i = len-1; i >= 0; i--){
ret = add_top(ret,array);
}
return ret;
}
打个样 ghimi 发表于 2022-12-20 15:45
打个样
第一个divide这个函数的返回值能不能改成return divide(,p-1)这种形式尝试写一下函数
大佬第二个函数相当于再算了一次全过程呀,这样不行的 jhq999 发表于 2022-12-20 15:32
merge 代码写的很巧妙,学习了👍 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);
} ghimi 发表于 2022-12-20 16:07
感谢,看完我明白了,我一直卡在那个地方,原来添加一个参数就可以解决了 壳970527 发表于 2022-12-20 15:42
感谢大佬的回答,第一个divide这个函数的返回值能不能改成return divide(,p-1)这种形式尝试写一下函数
...
粗心大意,没想到第一个简单的叠代还需要递归,幸亏后面有人解答 jhq999 发表于 2022-12-20 16:27
粗心大意,没想到第一个简单的叠代还需要递归,幸亏后面有人解答
感谢大佬的第二个函数!
页:
[1]