1

我的循环链表代码适用于添加、搜索、计数、查看，但是一旦我从列表中删除一个条目，它就会与列表中的所有其他数据混淆。我知道错误在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.");
}
4

4 回答 4

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);
    }
于 2013-12-12T10:14:31.740 回答
0

您的代码很好，我仔细查看并发现了错误。您只需要在释放节点后添加中断。而已。:) 释放节点后，它再次进行迭代并且当前为空..所以它中断了。

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.");
}

要继续迭代和删除具有相同值的所有节点，您可以在 else 语句中使用它。

else {
            prev->next = curr->next;
            free(curr);
            curr=prev; // this what you need
            break;  
        }
于 2013-12-12T10:51:27.273 回答
0

你有一个循环列表。这意味着无论何时删除一个节点，无论是否是头，都会有前一个节点。

此代码可以缩短，也可以解决您的问题。

    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->next 设置为 head 而不是相反，因此最终以 curr->next 指向 curr （等于 head）。

编辑：

但是，您还应该检查 curr->next 是否等于自身，这意味着您正在删除循环链接列表中的最后一个节点。

于 2013-12-12T10:08:28.367 回答
0

很好的实施。我发现了以下错误：

  1. 遍历列表时，头部被忽略。下面，用于搜索、查看和删除功能的 while 循环已被 do-while 取代。

  2. 正如已经指出的，prev 没有在 delete 函数中分配一个有效值。

  3. 删除头部时，prev->next 没有改变。在这种情况下，无论如何都没有设置 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.");
  }
}
于 2013-12-12T12:34:43.150 回答