c - 获取列表中节点的当前值和位置

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。

有什么办法可以获取节点在这个列表中的当前值和位置吗？如果可以，我该怎么做？

Current output is that I am still able to add to the same position in the list

Answer 1

插入/更新到稀疏数组的一般想法是仅当您到达位于较大 位置的节点时才添加节点。当然，您需要previous 节点指针来执行此操作，因此在找到放置数据的位置时，请继续扫描一跳。

还有一些注意事项:

• 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;
}

输出(随机)

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) 的列表结束。要滑动一个值并相应地调整列表，我们应该为 posi 设置一个完美的 0..9 值序列。这可以按如下方式完成:

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() 有两个插入循环，一个总是在 slot-0 插入，另一个总是在 slot-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

正如预期的那样。