Связанный с кругом список

Question

Мой код для кругового связанного списка отлично подходит для добавления, поиска, подсчета, просмотра, но как только я удаляет запись из списка, она испортит все остальные данные в списке. Я знаю, что ошибка находится в функции DeleteNode, но не может понять это. Пожалуйста, помогите мне с этим - Спасибо.

#include <stdio.h> 
#include <conio.h> 
#include <stdlib.h> 
struct Node{ 
    int data; 
    struct Node *next; 
}*head,*temp,*curr,*prev,*p; 
/* Prototypes */ 
void AddNode(int value); 
int CountNode(); 
void SearchNode(int value); 
void ViewAll(); 
void DeleteNode(int value); 
/* Main */ 
int main(){ 
    int choice,value; 
    printf("\n\n\n\t\t\tCircular Linked List\n\n\t\t\tSyed Danish Ali\n\n\t\t\tUBIT\n\n\n\t\t\t\tHit ENTER to continue..."); 
    while(getche() != '\r'){ 
    } 
    do{ 
     system("cls"); 
     printf("\n\nMENU\n=====\n\n[1] ADD\n[2] COUNT\n[3] SEARCH\n[4] VIEW ALL [5] DELETE\n[6] EXIT\n\nCHOICE:\t"); 
     scanf("%d",&choice); 
     if(choice == 1){ 
     printf("Enter data:\t"); scanf("%d",&value); 
     AddNode(value); 
     getch(); 
     } else if(choice == 2){ 
     printf("\n\n%d Node(s).",CountNode()); 
     getch(); 
     }else if(choice == 3){ 
     printf("Enter the data to search:\t"); 
     scanf("%d",&value); 
     SearchNode(value); 
     getch(); 
     } else if(choice == 4){ 
     ViewAll(); 
     getch(); 
     } else if(choice == 5){ 
     printf("Enter the data to search:\t"); 
     scanf("%d",&value); 
     DeleteNode(value); 
     getch(); 
     } else if(choice == 6){ 
      return 0; 
     } 

    }while(1); 
} 

void AddNode(int value){ 
    temp = (struct Node *) malloc (sizeof(struct Node)); 
    temp->data = value; 

    if(head == NULL){ 
    head = temp; 
    temp->next = head; 
    } else { 
    curr = head; 
    while(curr->next != head){ 
     curr = curr->next; 
    } 
    p = curr; 
    curr->next = temp; 
    temp->next = head; 
    } 
    printf("\n\nNode added."); 
} 
int CountNode(){ 
    int k = 0; 
    if(head == NULL){ 
    return 0; 
    } else { 
    curr = head; 
    while(curr->next != head){ 
     k++; 
     curr = curr->next; 
    } 
    return k; 
    } 
} 
void SearchNode(int value){ 
    int flag = 0,k = 0; 
    if (head == NULL){ 
    printf("\n\nList is empty."); 
    } else { 
    curr = head; 
    while(curr->next != head){ 
     if (curr->data == value){ 
     flag = 1; 
     printf("\n\n%d found at index # %d.",value,k); 
     curr = curr->next; 
     } else { 
     curr = curr->next; 
     k++; 
     } 
    } 
    } 
    if(flag == 0) 
    printf("\n\nValue %d not found.",value); 
} 
void ViewAll(){ 
    int counter = 0; 
    if(head == NULL) 
    printf("\n\nList is empty."); 
    else{ 
    curr = head; 
    printf("LIST GENERATED:\n===============\n"); 
    while(curr->next != head){ 
     printf("\nElement # %d:\nData:\t%d",counter+1,curr->data); 
     curr = curr->next; 
     counter++; 
    } 
    } 
} 
void DeleteNode(int value){ 
    int flag = 0; 
    if(head == NULL){ 
    printf("\n\nList is empty."); 
    } else { 
    curr = head; 
    while(curr->next != head){ 
     if(curr->data == value){ 
     printf("\n\nValue found."); 
     flag = 1; 
     if(curr == head){ 
      curr->next = head; 
      free(curr); 

     } else { 
      prev->next = curr->next; 
      free(curr); 
     } 
     } else { 
     prev = curr; 
     curr = curr->next; 
     } 
    } 
    printf("Node deleted."); 
    } 
    if(flag == 0) 
    printf("\n\nValue not found."); 
} 

Answer 1

У вас есть круглый список. Это означает, что всякий раз, когда вы удаляете узел, будь он голова или нет, будет предыдущий узел.

Этот код можно укоротить и также устранить проблему.

if(curr == head){ 
     curr->next = head; 
     free(curr); 

    } else { 
     prev->next = curr->next; 
     free(curr); 
    } 

Для

prev->next = curr->next; 
    if(curr == head) 
     head = curr->next; 
    free(curr); 

Ваш исходный код устанавливает curr-> рядом с головой, а не другим способом вокруг, таким образом, заканчивающегося в curr-> рядом указывая на Curr (который равен голове).

EDIT:

Однако, вы должны также проверить, если curr-> следующая равно себе означает, что вы удаляете последний узел в списке циркулярной связи.

Answer 2

} else { 
     prev->next = curr->next; //here prev doesn't point to any memory address so 
            we can't assign value to prev->next 
     free(curr); 
    } 

Answer 3

Ваш код хорош, я полностью изучил его и нашел ошибку. Вам просто нужно добавить разрыв после освобождения узла. это оно. :) После освобождения узла это снова итерация, а ток - нуль .. поэтому он прерывается.

void DeleteNode(int value){ 
    int flag = 0; 
    if(head == NULL){ 
    printf("\n\nList is empty."); 
    } else { 
    curr = head; 
    while(curr->next != head){ 
     if(curr->data == value){ 
     printf("\n\nValue found."); 
     flag = 1; 
     if(curr == head){ 
      curr->next = head; 
      free(curr); 
      break; // this is where it break 

     } else { 
      prev->next = curr->next; 
      free(curr); 
      break; // this is where it break 
     } 
     } else { 
     prev = curr; 
     curr = curr->next; 
     } 
    } 
    printf("Node deleted."); 
    } 
    if(flag == 0) 
    printf("\n\nValue not found."); 
} 

Чтобы продолжить ittrating и удаление всех узлов с одинаковым значением, которое вы можете использовать это в другом заявлении ..

else { 
      prev->next = curr->next; 
      free(curr); 
      curr=prev; // this what you need 
      break; 
     } 

Answer 4

Хорошей реализации. я нашел следующие ошибки:

1. При перемещении списка, голова была проигнорирована. Ниже, while-loops были заменены на do-while для поиска, просмотра и удаления функций.

2. Как уже указывалось, prev не было присвоено действительное значение в функции удаления.

3. При удалении головы предыдущий-> следующий не был изменен. prev в любом случае не было установлено. В приведенном ниже коде добавлена ​​хвостовая переменная. Таким образом, prev может быть установлен уже в начале функции удаления. В противном случае список также был уверен, что глобальные переменные, такие как curr и prev, всегда имеют допустимое значение.

Я надеюсь, что это может быть полезно. Приветствия, Майкл

Модифицированный код:

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

struct Node 
{ 
    int data; 
    struct Node *next; 
}*head,*temp,*curr,*prev,*tail; 

/* Prototypes */ 
void AddNode(int value); 
int CountNode(); 
void SearchNode(int value); 
void ViewAll(); 
void DeleteNode(int value); 

/* Main */ 
int main() 
{ 
    int choice,value; 
    printf("\n\n\n\t\t\tCircular Linked List\n\n\t\t\tSyed Danish Ali\n\n\t\t\tUBIT\n\n\n\t\t\t\tHit ENTER to continue..."); 
    while(getche() != '\r') 
    { 
    } 
    do 
    { 
    system("cls"); 
    printf("\n\nMENU\n=====\n\n[1] ADD\n[2] COUNT\n[3] SEARCH\n[4] VIEW ALL\n[5] DELETE\n[6] EXIT\n\nCHOICE:\t"); 
    scanf("%d",&choice); 
    if(choice == 1){ 
     printf("Enter data:\t"); scanf("%d",&value); 
     AddNode(value); 
     getch(); 
    } else if(choice == 2){ 
     printf("\n\n%d Node(s).",CountNode()); 
     getch(); 
    }else if(choice == 3){ 
     printf("Enter the data to search:\t"); 
     scanf("%d",&value); 
     SearchNode(value); 
     getch(); 
    } else if(choice == 4){ 
     ViewAll(); 
     getch(); 
    } else if(choice == 5){ 
     printf("Enter the data to search:\t"); 
     scanf("%d",&value); 
     DeleteNode(value); 
     getch(); 
    } else if(choice == 6){ 
     return 0; 
    } 
    } while(1); 
} 

void AddNode(int value) 
{ 
    temp = (struct Node *) malloc (sizeof(struct Node)); 
    temp->data = value; 

    if(head == NULL) 
    { 
    head = temp; 
    tail = temp; 
    curr = temp; 
    temp->next = head; 
    } else { 
    // remember prev if needed 
    prev  = tail; 
    prev->next = temp; 
    tail  = temp; 
    curr  = temp; 
    temp->next = head; 
    } 
    // remember tail 
    printf("\n\nNode added."); 
    } 
    int CountNode(){ 
    int k = 0; 
    if(head == NULL){ 
    return 0; 
    } else { 
    temp = head; 
    // count head, too 
    do 
    { 
     k++; 
     temp = temp->next; 
    } while(temp != head); 
    return k; 
    } 
} 

void SearchNode(int value){ 
    int flag = 0,k = 0; 
    if (head == NULL){ 
    printf("\n\nList is empty."); 
    } else { 
    curr = head; 
    // search head, too 
    do 
    { 
     if (curr->data == value){ 
     flag = 1; 
     printf("\n\n%d found at index # %d.",value,k); 
     curr = curr->next; 
     } else { 
     curr = curr->next; 
     k++; 
     } 
    } while(curr != head); 
    } 
    if(flag == 0) 
    { 
    printf("\n\nValue %d not found.",value); 
    } 
} 

void ViewAll(){ 
    int counter = 0; 
    if(head == NULL) 
    { 
    printf("\n\nList is empty."); 
    } else { 
    curr = head; 
    printf("LIST GENERATED:\n===============\n"); 
    // show head, too 
    do 
    { 
     printf("\nElement # %d:\nData:\t%d",counter+1,curr->data); 
     curr = curr->next; 
     counter++; 
    } while(curr != head); 
    } 
} 

void DeleteNode(int value){ 
    int flag = 0; 
    if(head == NULL) 
    { 
    printf("\n\nList is empty."); 
    } else { 
    curr = head; 
    prev = tail; 
    // delete head, too, if it contains the searched value 
    do{ 
     if(curr->data == value) 
     { 
     printf("\n\nValue found."); 
     flag = 1; 
     if(curr == head) 
     { 
      if(tail == head) 
      { 
      // list contains only one element 
      free(head); 
      temp = NULL; 
      head = NULL; 
      prev = NULL; 
      curr = NULL; 
      tail = NULL; 
      } else { 
      // list contains more than one element 
      temp = curr; 
      free(temp); 
      temp = tail; // ensure, temp is valid 
      curr = head->next; 
      head = curr; 
      tail->next = curr; 
      // prev = tail; 
      } 

     } else { 
      // curr != head 
      prev->next = curr->next; 
      if(curr == tail){ 
      tail = prev; // tail may be head as well, now 
      } else { 
      // nothing to do ;O) 
      } 
      free(curr); 
      curr = prev->next; 
      temp = prev; // ensure, temp is valid 
     } 
     } else { 
     // don't delete, just advance 
     prev = curr; 
     curr = curr->next; 
     } 
    } while(curr != head); 
    printf("Node deleted."); 
    } 
    if(flag == 0) 
    { 
    printf("\n\nValue not found."); 
    } 
}