Правильный способ удаления узла в дважды круговом связанном списке - PullRequest
Новая
       57

Правильный способ удаления узла в дважды круговом связанном списке

0 голосов
/ 16 октября 2018

Целью этого кода является управление вставкой, удалением и визуализацией.Я просто хочу знать, все ли я делаю правильно, дайте мне знать, если есть еще возможные способы сделать это.Это моя первая попытка, я не следовал ни одному учебнику. 

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



typedef struct Node {
  int n;
  struct Node *next;
  struct Node *prev;

}TNode;
typedef TNode* Node;



void NewNode(Node *pp, int n)
{
  Node temp, last;

  temp = (Node)malloc(sizeof(struct Node));

  temp->n = n;
  temp->next = temp;
  temp->prev = temp;

  if(*pp != NULL)
    {
      last = (*pp)->prev;
      temp->next = (*pp);
      temp->prev = last;
      last->next = (*pp)->prev = temp;
    }

  *pp = temp;

}

void ViewList(Node head)
{
  if(head == NULL)
  {
    return;
  }
  Node node = head->prev;
 do
  {
    printf("Curr: %d\n", node->n);
    node = node->prev;
  }while(node != head->prev);
}

void ReadData(Node * head, int * n)
{
  printf("\nInsert a number:");
  scanf("%d", n);
  NewNode(head, *n);
}

Node SearchNode(Node head)
{
  int d;
  printf("\nElement to Delete:");
  scanf("%d", &d);

  while(head != NULL)
    {
      if(head->n == d)
        {
          return head;
        }
      head = head->next;
    }
  printf("\nNo Element [%d] Found", d);
  return NULL;
}

void Delete(Node * head)
{
  Node del = SearchNode(*head);

       if(*head == NULL || del == NULL)
        {
          return;
        }
      if(*head == del && del->next == *head)
      {
        *head = NULL;
        free(del);
        return;
      }
      if(*head == del)
      {
        *head = del->next;
        del->prev->next = *head;
        (*head)->prev = del->prev;
        free(del);
        return;
      }
      if((*head)->prev == del)
        {
          (*head)->prev = del->prev;
          del->prev->next = *head;
          free(del);
          return;
        }
        del->next->prev = del->prev;
        del->prev->next = del->next;
        free(del);
}

int Menu()
{
  int c;

  printf("\n*** M E N U ***\n"
     "1 - New Node\n"
     "2 - View List\n"
     "3 - Delete\n"
     "0 - Exit\n"
     "\n>> ");
  scanf(" %d", &c);

  return c;
}

int main()
{
  int c,n;
  Node head = NULL;

  do {
    c = Menu();

    switch (c)
    {
      case 1: ReadData(&head, &n); break;
      case 2: ViewList(head); break;
      case 3: Delete(&head); break;
      default: c = 0;
    }

  } while (c != 0);

  return 0;
}

Как я могу проверить, является ли это реальный круговой двусвязный список, а не простой двусвязный список?

1 Ответ

0 голосов
/ 16 октября 2018

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

Исправленная версия:

Node SearchNode(Node head)
{
  int d;
  printf("\nElement to Delete:");
  scanf("%d", &d);

  Node start = head;     // remember where we started

  while (head != NULL)
  {
    if (head->n == d)
    {
      return head;
    }
    head = head->next;

    if (head == start)   // if we are back to where we started
      break;             // the element hasn't been found and we stop the loop
  }

  printf("\nNo Element [%d] Found", d);
  return NULL;
}

Существуют также некоторые недостатки проектирования, которые не мешают программе работать правильно:

Один из них таков: переменная n не используется вне ReadData, поэтому бессмысленно объявлять это в main и передавать его указатель на ReadData.

Исправленная версия: 

void ReadData(Node * head)
{
  int n;  // declare n locally
  printf("\nInsert a number:");
  scanf("%d", &n);
  NewNode(head, n);
}

Называть это так: ReadData(&head) и удалить int n; от main.

...