你能帮我解决这个混响范围函数吗

Question

我试图编写一个函数ReverseRange(struct Node **head, int x, int y)，该函数将反转给定索引范围int x和int y中的链表。我在ReverseRange()中的一个条件中使用了以前定义的函数Reverse()，但它没有反转给定的列表，只打印了一个带有数据'Q'的Node。我不知道错误是在Print()、Reverse()、ReverseRange()还是其他地方。请帮忙，谢谢。

#include <stdio.h>
#include <stdlib.h>
struct Node {
char data;
struct Node *next;
};
//insert data in the node
void Insert(struct Node **Head, char data) {
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = data;
temp->next = *Head;
*Head = temp;
}
//find length of linked list 
int LengthRec(struct Node *head) {
if (head == NULL)
return 0;
return 1 + LengthRec(head->next);
}
//Reverse a linked list when head is given;
void Reverse(struct Node **head) {
struct Node *prev = NULL;
struct Node *curr = *head;
struct Node *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
//Reverse list in range x to y;
int ReverseRange(struct Node **H, int x, int y) {
struct Node *Head = *H;
if (Head == NULL)
return -1;
else if (Head->next == NULL)
return -1;
else if (x == y)
return -1;
else if (x > y)
return -1;
else if (LengthRec(Head) >= y) {
if (x == 1 && y == LengthRec(Head)) {
Reverse(&Head);
return 1;
}
/* NOTE:: 
Code is incomplete, because I found error before
the entire code is written,
*/
}
}
void Print(struct Node **H) {
struct Node *head = *H;
if (head == NULL) {
printf("Head=NULL");
return;
}
printf("n %c", head->data);
while (head->next != NULL) {
head = head->next;
printf("t%c", head->data);
}
}
int main() {
struct Node *Head = NULL;
Insert(&Head, 'Q');
Insert(&Head, 'W');
Insert(&Head, 'E');
Insert(&Head, 'R');
Insert(&Head, 'T');
Print(&Head);
Reverse(&Head);
Print(&Head);
ReverseRange(&Head, 1, 5);
Print(&Head);
}

输出：

T      R       E       W       Q
Q      W       E       R       T
Q

Answer 1

Reverse函数看起来不错，但它应该使用H作为ReverseRange()的参数来调用，而不是使用作为局部变量的&Head。

函数开头的一些显式测试对应于合法的参数，不应返回错误值。

还要注意的是，您应该记录x和y的精确语义：在C中使用1来指定集合的第一个元素是不习惯的，0非常常见。y似乎包含在内，这也不是惯用的，但与使用1作为第一个元素一致。

您的LengthRec函数效率非常低，可能会导致非常长的列表出现堆栈溢出。使用循环而不是递归，因为此递归不是尾部递归。

这是一个修改版本：

#include <stdio.h>
#include <stdlib.h>
struct Node {
char data;
struct Node *next;
};
//insert data in the node
void Insert(struct Node **Head, char data) {
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = data;
temp->next = *Head;
*Head = temp;
}
//find length of linked list
int ListLength(const struct Node *head) {
int length = 0;
while (head != NULL) {
length++;
head = head->next;
}
return length;
}
//Reverse a linked list when head is given;
void Reverse(struct Node **head) {
struct Node *prev = NULL;
struct Node *curr = *head;
while (curr != NULL) {
struct Node *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
//Reverse list in range x to y;
int ReverseRange(struct Node **H, int x, int y) {
int length = ListLength(*H);
if (x < 1 || x > length || x > y || y > length)
return -1;
if (x == y)
return 1;
if (x == 1 && y == length) {
Reverse(H);
return 1;
} else {
struct Node **head = H;
struct Node *prev = NULL;
struct Node *curr = *head;
struct Node *last;
while (x > 1) {
head = &curr->next;
curr = *head;
x--;
y--;
}
last = curr;
while (x <= y) {
struct Node *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
x++;
}
last->next = curr;
*head = prev;
return 1;
}
}
void Print(const char *msg, const struct Node *head) {
if (msg) {
printf("%s", msg);
}
if (head == NULL) {
printf("Head=NULLn");
return;
}
printf("%c", head->data);
while (head->next != NULL) {
head = head->next;
printf("t%c", head->data);
}
printf("n");
}
int main() {
struct Node *Head = NULL;
Insert(&Head, 'E');
Insert(&Head, 'D');
Insert(&Head, 'C');
Insert(&Head, 'B');
Insert(&Head, 'A');
Print("           Initial list:t", Head);
Reverse(&Head);
Print("         Reverse(&Head):t", Head);
ReverseRange(&Head, 1, 5);
Print("ReverseRange(&Head,1,5):t", Head);
ReverseRange(&Head, 1, 1);
Print("ReverseRange(&Head,1,1):t", Head);
ReverseRange(&Head, 2, 4);
Print("ReverseRange(&Head,2,4):t", Head);
return 0;
}

输出：

Initial list:        A       B       C       D       E
Reverse(&Head):        E       D       C       B       A                                                                           ReverseRange(&Head,1,5):        A       B       C       D       E
ReverseRange(&Head,1,1):        A       B       C       D       E
ReverseRange(&Head,2,4):        A       D       C       B       E