Получение текущего значения и позиции узла в списке

Question

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

Пока мой код:

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

struct node* createNode(int,int); 

struct node { 
    int data, posi; 
    struct node *next; 
}; 

struct node *head = NULL; 
struct node *tail = NULL; 


struct node * createNode(int data, int pos) { 
    struct node *ptr = (struct node *) malloc(sizeof (struct node)); 
    ptr->data = data; 
    ptr->posi = pos; 
    ptr->next = NULL; 
    return ptr; 
} 

void insertAtPos(int pos, int data) { 
    struct node *temp, *ptr = createNode(data,pos); 
    int x = 0, i = 1, inserted = 0, duplicate = 0; 

    if (head == NULL || pos == 1) { 
      if (!head) { 
        head = ptr; 
        tail = ptr; 
        return; 
      } 
      ptr->next = head; 
      head = ptr; 
      return; 
    } 
    temp = head; 
    while (temp) { 
     x = temp->posi; 
     if (pos == i + 1) { 
      printf("pos %d - temp %d - data %d",pos,x,temp->data); 
      if(pos == x){ 
       duplicate = 1; 
       break; 
      }else{ 
       ptr->next = temp->next; 
       temp->next = ptr; 

       if (ptr->next == NULL) 
         tail = ptr; 
       inserted = 1; 
       break; 
      } 
     } 
     i++; 
     temp = temp->next; 
    } 
    if (!inserted) 
      printf("You've entered wrong position\n"); 

    if(duplicate == 1){ 
     printf("Duplicate position!\n"); 
    } 
} 

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

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

Есть ли способ получить текущее значение и положение узла в этом списке? Если да, то как мне это сделать?

Токовый выход в том, что я все еще в состоянии добавить в ту же позицию в списке

Answer 1

Общая идея вставки/обновления в разреженном массиве только добавлять узлы, когда вы прибудете в узел на больше. Конечно, для этого вам нужен указатель узла предыдущего, поэтому держите его в сканирующем режиме для сканирования, пока вы находите, где разместить свои данные.

И некоторые примечания:

• Don't cast malloc() in C programs.
• Я оставил список ыборку как задача для вас.
• Это обновляет существующий узел, если указанная позиция уже находится в списке. если вы хотите до переместить узел в это положение и прирастить элементы после до тех пор, пока не будет найден промежуток, что значительно больше работы. Однако это выполнимо.

С этим. Ну вот.

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

struct node* createNode(int,int); 

struct node { 
    int data, posi; 
    struct node *next; 
}; 

struct node *head = NULL; 
struct node *tail = NULL; 


struct node * createNode(int data, int pos) 
{ 
    struct node *ptr = malloc(sizeof(*ptr)); 
    ptr->data = data; 
    ptr->posi = pos; 
    ptr->next = NULL; 
    return ptr; 
} 

void insertAtPos(int pos, int data) 
{ 
    struct node *ptr = head, *prev = NULL; 
    while (ptr && ptr->posi < pos) 
    { 
     prev = ptr; 
     ptr = ptr->next; 
    } 

    // make sure we have a node. 
    if (ptr) 
    { 
     // Case 1: update existing element. 
     if (ptr->posi == pos) 
     { 
      // update in place 
      ptr->data = data; 
     } 

     // Case 2: insert new element 
     else if (prev) 
     { 
      prev->next = createNode(data, pos); 
      prev->next->next = ptr; 
     } 

     // Case 3: new list head. 
     else 
     { 
      head = createNode(data, pos); 
      head->next = ptr; 
     } 
    } 
    else if (prev) 
    { 
     // means we hit the end of the list. 
     prev->next = createNode(data, pos); 
    } 

    else 
    { // means empty list. new head. 
     head = createNode(data, pos); 
    } 
} 

void print() 
{ 
    struct node *p = head; 
    while (p) 
    { 
     printf("list[%d] = %d\n", p->posi, p->data); 
     p = p->next; 
    } 
    printf("\n"); 
} 

int main() 
{ 
    int i = 0; 
    srand((unsigned)time(NULL)); 

    // fill our list with some elements 
    for (i=0;i<10;++i) 
     insertAtPos(rand() % 20 + 1, rand() % 100); 
    print(); 

    // add or update element 
    insertAtPos(15, 100000); 
    print(); 

    // update element at location 20; 
    insertAtPos(15, 200000); 
    print(); 

    // prove we can add an element at beginning of list 
    insertAtPos(0, 1000); 
    print(); 

    // prove we can add an element at end of list 
    insertAtPos(100, 2000); 
    print(); 

    return 0; 
} 

Выход (Random)

list[3] = 86 
list[5] = 10 
list[9] = 63 
list[12] = 86 
list[14] = 93 
list[19] = 86 
list[20] = 49 

list[3] = 86 
list[5] = 10 
list[9] = 63 
list[12] = 86 
list[14] = 93 
list[15] = 100000 
list[19] = 86 
list[20] = 49 

list[3] = 86 
list[5] = 10 
list[9] = 63 
list[12] = 86 
list[14] = 93 
list[15] = 200000 
list[19] = 86 
list[20] = 49 

list[0] = 1000 
list[3] = 86 
list[5] = 10 
list[9] = 63 
list[12] = 86 
list[14] = 93 
list[15] = 200000 
list[19] = 86 
list[20] = 49 

list[0] = 1000 
list[3] = 86 
list[5] = 10 
list[9] = 63 
list[12] = 86 
list[14] = 93 
list[15] = 200000 
list[19] = 86 
list[20] = 49 
list[100] = 2000 

---

EDIT Запрос как засунуть в вставки делается.

Чтобы пропустить новый элемент в данный индекс, потенциально необходимо обновить существующие индексы после. Предпосылкой является то, что следующий должен создать список с восходящей posi значения:

int main() 
{ 
    int i = 0; 
    srand((unsigned)time(NULL)); 

    // fill our list with some elements 
    for (i=0;i<10;++i) 
     insertAtPos(0, rand() % 100); 
    print(); 

    return 0; 
} 

Обратите внимание на индекс мы вставки с. Он всегда равен нулю. Предварительная версия insertAtPos() просто заменила существующее значение повторно, и мы закончили бы список одного узла (posi = 0). Чтобы скопировать значение и отрегулировать список соответственно, мы должны вместо этого иметь совершенную последовательность значений 0..9 для posi.Это может быть сделано следующим образом:

void insertAtPos(int pos, int data) 
{ 
    // same as before. find the right slot 
    struct node *ptr = head, *prev = NULL; 
    while (ptr && ptr->posi < pos) 
    { 
     prev = ptr; 
     ptr = ptr->next; 
    } 

    if (prev) 
    { 
     // slip new node in. 
     prev->next = createNode(data, pos); 
     prev->next->next = ptr; 
    } 
    else 
    { // no prev means this goes to the head of the list. 
     head = createNode(data, pos); 
     head->next = ptr; 
    } 

    // it is possible the new node has the same 
    // index as its successor. to account for this 
    // we must walk successor nodes, incrementing 
    // their posi values until a gap is found (or 
    // end of list). 
    while (ptr && (ptr->posi == pos++)) 
    { 
     ptr->posi++; 
     ptr = ptr->next; 
    } 
} 

Запуск с упомянутой выше main() ..

list[0] = 90 
list[1] = 34 
list[2] = 45 
list[3] = 27 
list[4] = 45 
list[5] = 88 
list[6] = 75 
list[7] = 50 
list[8] = 68 
list[9] = 41 

И, конечно, ваши ценности будут изменяться в зависимости от характера rand(). Немного отличается main() с двумя петлями вставки, которые всегда вставляются в слот-0, другой, который всегда вставлен в слот-4.

int main() 
{ 
    int i = 0; 
    srand((unsigned)time(NULL)); 

    // fill our list with some elements 
    for (i=0;i<5;++i) 
     insertAtPos(0, rand() % 100); 
    print(); 
    for (i=0;i<5;++i) 
     insertAtPos(4, rand() % 100); 
    print(); 

    return 0;  
} 

Должно появляться идентичное индексирование, но, очевидно, разные значения (опять же, это «rand()).

list[0] = 74 
list[1] = 35 
list[2] = 72 
list[3] = 22 
list[4] = 0 

list[0] = 74 
list[1] = 35 
list[2] = 72 
list[3] = 22 
list[4] = 40 
list[5] = 38 
list[6] = 31 
list[7] = 57 
list[8] = 42 
list[9] = 0 

Обратите внимание, как значение 0 толкнули весь путь до конца списка. Это было в 4-индексе, поэтому он был «нажат» вниз с каждой вставкой, так как каждый номер мы вставили один за другим.

Наконец, чтобы доказать это правильно только не регулирует индексацию до обнаруженного разрыва, считают это:

int main() 
{ 
    int i = 0; 
    srand((unsigned)time(NULL)); 

    // fill our list with some elements 
    for (i=0;i<10;i+=2) 
     insertAtPos(i, rand() % 100); 
    print(); 
    for (i=0;i<2;++i) 
     insertAtPos(3, rand() % 100); 
    print(); 

    return 0; 
} 

Это должно вставить значения в индексах 0,2,4,6,8 вначале, а затем вставить два значения в слоте «3». Первая вставка должна давать нам показатели 0,2,3,4,6,8. Вторая вставка должна давать нам показатели 0,2,3,4,5,6,8.

list[0] = 22 
list[2] = 3 
list[4] = 91 
list[6] = 15 
list[8] = 68 

list[0] = 22 
list[2] = 3 
list[3] = 94 
list[4] = 48 
list[5] = 91 
list[6] = 15 
list[8] = 68 

Как и ожидалось.

Answer 2

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

void insertAfterPos(struct node** head_ref, struct node* link, int new_data, int pos) 
{ 

// allocate new node 
struct node* new_node = malloc(sizeof(struct node)); 
struct node* cur = *head_ref; //initialise current node as head 
cur->next = link; 
int nodenum = 1; 
// put in the data 
new_node->data = new_data; 
while (cur !=NULL || nodenum <= pos) { 
    if (nodenum == pos) { 
    //Make next of new node next of current node 
    new_node->next = cur->next; 

    //Make the next of current node new_node 
    cur->next = new_node; 
    } 
    nodenum++; 
    cur = cur->next; //move forward 
    } 
} 

Эта функция была написана в рамках, что доступ к список всеми функциями вставки будет через ссылку на голову или указатель на указатель на голову, следовательно, аргумент node ** head_ref. Второй аргумент в этой функции, ссылка, должен быть head-> next, так как текущий узел не может получить доступ к следующему указателю, содержащемуся в головном узле из ссылки на головку. Примером его использование

insertAtPos(&head,head->next,10,2) 

вставляет значение 10 в узле после того, как во втором узле.

Интересно, что если вы введете позицию, превышающую размер списка, она просто поместит ее в конец.