Блог

Я пытался написать функцию ReverseRange(struct Node **head, int x, int y) , которая перевернет связанный список в заданном диапазоне индексов int x и int y . Я использовал ранее определенную функцию Reverse() в одном из условий, ReverseRange() но она не изменяет данный список, а печатает только один узел с данными 'Q' . Я не знаю, есть ли ошибка в 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 amp;amp; y == LengthRec(Head)) {
            Reverse(amp;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(amp;Head, 'Q');
    Insert(amp;Head, 'W');
    Insert(amp;Head, 'E');
    Insert(amp;Head, 'R');
    Insert(amp;Head, 'T');
    Print(amp;Head);
    Reverse(amp;Head);
    Print(amp;Head);
    ReverseRange(amp;Head, 1, 5);
    Print(amp;Head);
}
 

Выход:

  T      R       E       W       Q
 Q      W       E       R       T
 Q
 

Reverse Функция кажется хорошей, но ее следует вызывать с H аргументом from ReverseRange() , а не amp;Head с локальной переменной.

Некоторые явные тесты в начале функции соответствуют допустимым аргументам и не должны возвращать значение ошибки.

Обратите также внимание, что вы должны задокументировать точную семантику для x и y : в языке Си не является идиоматичным использовать 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 amp;amp; 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 = amp;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(amp;Head, 'E');
    Insert(amp;Head, 'D');
    Insert(amp;Head, 'C');
    Insert(amp;Head, 'B');
    Insert(amp;Head, 'A');
    Print("           Initial list:t", Head);
    Reverse(amp;Head);
    Print("         Reverse(amp;Head):t", Head);
    ReverseRange(amp;Head, 1, 5);
    Print("ReverseRange(amp;Head,1,5):t", Head);
    ReverseRange(amp;Head, 1, 1);
    Print("ReverseRange(amp;Head,1,1):t", Head);
    ReverseRange(amp;Head, 2, 4);
    Print("ReverseRange(amp;Head,2,4):t", Head);
    return 0;
}
 

Выход:

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