Получение текущего значения и положения узла в списке
Я пытаюсь создать код, который будет вставлен в любом месте списка. Я также преобразую это, чтобы заменить значение узла в данной позиции.
Пока что мой код:
#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 одновременно.
Есть ли способ для меня, чтобы получить текущее значение и положение узла в этом списке? Если так, как бы я это сделал?
Текущий вывод, что я все еще могу добавить к той же позиции в списке
2 ответа
Общая идея вставки / обновления в разреженный массив состоит в том, чтобы добавлять узлы только тогда, когда вы достигаете узла в более крупной позиции. Конечно, для этого вам нужен указатель предыдущего узла, поэтому следите за сканированием, пока не найдете место для размещения ваших данных.
И некоторые заметки:
- Не бросать
malloc()в C программах. - Я оставил очистку списка как задачу для вас.
- Это обновляет существующий узел, если указанная позиция уже находится в списке. если вы хотите поместить узел в это положение и увеличивать элементы после него до тех пор, пока не будет найден пробел, это значительно больше работы. Это выполнимо, однако.
С этим. Ну вот.
#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;
}
Выход (Случайный)
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
РЕДАКТИРОВАТЬ Запрос о том, как производится вставка.
Чтобы вставить новый элемент в данный индекс, возможно, потребуется обновить существующие индексы после него. Предпосылка состоит в том, что следующее должно составить список с возрастанием 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
Как и ожидалось.
Вот моя функция, которая позволяет вам вставлять в любом месте списка, учитывая номер позиции. Он неявно присваивает каждому элементу номер, основанный на том, сколько элементов нужно было пройти, чтобы добраться до него + 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
}
}
Эта функция была написана в рамках, что доступ к списку всеми функциями вставки будет через ссылку на заголовок или указатель на указатель на заголовок, следовательно, аргумент узла **head_ref. Второй аргумент в этой функции, link, должен быть head->next, так как текущий узел не может получить доступ к следующему указателю, содержащемуся в узле head, из ссылки на заголовок. Пример его использования
insertAtPos(&head,head->next,10,2)
вставит значение 10 в узел после второго узла.
Интересно, что если вы введете позицию, превышающую размер списка, она просто поместит ее в конец.