Добавление узла в начало связанного списка - PullRequest
Новая
       23

Добавление узла в начало связанного списка

0 голосов
/ 19 сентября 2018

Я хотел бы добавить узел в отсортированный связанный список по номеру.Это структура: 

struct node {
  int number;
  struct node *next;
}

Я могу правильно добавить в отсортированный связанный список, но не могу изменить заголовок.

К сожалению, я не могу изменить форматобъявление функции, так что это моя функция: 

int create(struct node *head, int number) {
   struct node *newNode = malloc(sizeof(struct node));
   newNode->number = number;
   struct node *current = head;

   if (current->number == -1) {
     newNode->next = NULL;
     *head= *newNode;
     return 1;
   }

   //Checking if head's number is bigger than init
   if (current->number > number) {
     newNode->next = current;
     *head = *newNode;
   } else {
     while(current->next != NULL && (current->number <= number)) {
      current = current->next;
     }
    newNode->next = current->next;
    current->next = newNode;
   }
   return 1;
}

вызов функции (Примечание, я также не могу изменить это): 

struct node *list;
list = initializeList();
int num;
num = create(list, 5);
num = create(list, 1);

После второго вызова,список должен быть 1-> 5.Но он становится 1-> 1-> 1-> 1 -> .....

Редактировать: список кодов для инициализации: 

struct node * initializeList() {
  struct node *head;
  head = malloc(sizeof(struct node));
  head->next = NULL;
  head->number = -1;
  return head;
}

Ответы [ 2 ]

0 голосов
/ 19 сентября 2018

Я сделал несколько правок для функции create, чтобы исправить проблему.

Сначала, если заголовок списка имеет number == -1, тогда новый node не должен быть выделен, так как выпросто заменил номер.

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

int create(struct node *head, int number) {
  struct node *current = head;

  if (current->number == -1) {
    current->number = number;//just replace the number, no need for anything else
    return 1;
  }

  //allocate only if we must insert
  struct node *newNode = malloc(sizeof(struct node));

  //no longer need to check if head
  while(current->next != NULL && (current->number <= number)) {
    current = current->next;
  }
  if(current->next == NULL && current->number < number) {//check if number needs to go at the end
    current->next = newNode;
    newNode->next = NULL;
    newNode->number = number;
  } else {
    *newNode = *current;//newNode will go after current, but with current's values
    current->number = number;//replace current with the number to "insert" it
    current->next = newNode;//point to the next node
  }
  return 1;
}
0 голосов
/ 19 сентября 2018

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

...