Вставка элемента в связанный список после самого большого элемента в списке

Question

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

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

#define MAX_TREE_STRING 100 

typedef struct Node { 
    char val; 
    struct Node *next; 
} node; 

node *create_list(char *list_string) { 
    node *momentary=NULL, *new=NULL, *head; 
    int i; 

    for(i=0; i<strlen(list_string); i++) { 
     new = (node *)malloc(sizeof(node)); 
     new->val = list_string[i]; 
     new->next = NULL; 
     if (!momentary) head = new; 
     else momentary->next = new; 
     momentary = new; 
    } 
    return head; 
} 

int print_list(node *head) { 
    node *momentary; 

    if(!head) return -1; 
    for(momentary=head; momentary!=NULL; momentary=momentary->next) 
     printf("%c ", momentary->val); 
    printf("\n"); 
    return 0; 
} 

node *find_biggest(node *head) { 
    node *momentary=NULL, *biggest=head; 

    if (head==NULL) return NULL; 
    for (momentary=head; momentary!=NULL; momentary=momentary->next) { 
     if (momentary->val > biggest->val) biggest = momentary; 

    } 

    return biggest; 
} 

void insert_after_biggest(node **head, node **biggest, char val) { 

    node *p = *head, *temp=NULL; 

    *head = p->next; 


    if(*head!=NULL){ 

     if(p->val==(*biggest)->val){ 

      temp=p; 
      p->next=temp; 
      p->val=temp->val; 

      p->next=NULL; 

      *biggest=p; 
      p->next=(*biggest); 
      p->val=(*biggest)->val; 
      //*biggest=p; 

      p->next=NULL; 

      //temp=p; 
      p->next=temp; 
      p->val=temp->val; 

     } 

     else if(p->val<(*biggest)->val){ 

      *head = p->next; 

      } 
    } 

} 

int main() { 
    node *head=NULL, *biggest=NULL; 
    int menu_choice; 
    char c, val, list_string[MAX_TREE_STRING]; 

    setbuf(stdout, NULL); 
    do { 
     menu_choice = 0; 
     printf("\n1 Create list \n2 Print"); 
     printf("\n3 Insert after biggest"); 
     printf("\n4 exit\n"); 
     scanf("%d", &menu_choice); 
     switch (menu_choice) { 
      case 1: 
       if (head) { 
        printf("List exist.\n"); 
        break; 
       } 
       printf("Enter list as digits without spaces: "); 
       scanf(" %s", list_string); 
       head = create_list(list_string); 
       break; 
      case 2: 
       print_list(head); 
       break; 
      case 3: 
       scanf(" %c", &val); 
       insert_after_biggest(&head, &biggest, val); 
       break; 
      case 4: 
       break; 
      default: 
       while((c=getchar())!='\n' && c!=EOF); 
     } 
    } while(menu_choice!=4); 
    return 0; 
} 

Теперь задача состоит в следующем:

Написать функцию «insert_after_biggest» так, что новые элементы оставить позади элемента с наибольшим значением и сложностью функции должна быть O (1) , Другими словами, функция «find_biggest» , которая имеет сложность O (n), может быть вызвана только в том случае, если «самый большой» имеет еще не определен. Если в списке нет элементов, все равно необходимо сначала указать .

Вот пример консоли, чтобы иметь более четкую картину:

1 | < -Впередать в список связанного списка | Введите список в виде цифр без пробелов: 683 | < -Процесс и введенное значение | 3 | < -Option (функция) | 2 | < -Number для вставления | 2 | < -Принт-вариант | 6 8 2 3 | < -Выход | 3 | < -Option | 8 | < -Number для вставления | 2 | < -Принт-вариант | 8 | < -Выход |

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

Конкретный: как его решить (шаг за шагом) и как он должен выглядеть (код, возможно, включен здесь?).

спасибо.

Answer 1

Если вы можете предположить, что

1) Вам не нужно удалять элементы

Вы просто должны держать дополнительный указатель, который указывает на узел с наибольшим значением во все времена. Приятно, что вам разрешено сканировать список для самого большого, если вы никогда не звонили insert_after_biggest, но это даже не нужно. Вызовите этот узел max и указатель на max p_max.

Для каждой вставки

а) значение, которое вы собираетесь вставить больше, чем значение, проведенного макс, в этом случае вы вставить новое значение, и изменить p_max = p_new.

n_new->next = p_max; 
p_max = p_new; 

б) Значение, которое вы собираетесь вставить больше, чем значение, удерживаемое на покупку не более, в этом случае просто вставить и оставить p_max без изменений.

Для insert_after_max вы явно делаете

p_new->next = p_max->next; 
p_max->next = p_new; 

Или, если новое значение больше, то сделайте, как описано выше.

Поскольку вы не должны сканировать список для вставки, сложность вставки является O (1)