在第 i 个位置添加节点

Question

我想创建一个大小为 5 的 link 列表，并在第 i 个位置添加一些节点。

我将在 link 列表的随机位置添加节点，例如（0、5 和 2）。

这是在位置 0 添加节点的样子。

      0
 +---------+
 |    1    |
 +---------+ --> NULL
 |  next   | 
 +---------+

这是在位置 5 添加节点的样子。

      0             1             2             3             4
 +---------+   +---------+   +---------+   +---------+   +---------+
 |    1    |   |  Empty  |   |  Empty  |   |  Empty  |   |    2    |
 +---------+-------------------------------------------->+---------+-->NULL
 |  next   |   |  node   |   |  node   |   |  node   |   |  next   |
 +---------+   +---------+   +---------+   +---------+   +---------+

因此节点 1、2、3 为空，0 被 linked 为 4。

这是在位置 1 添加节点的样子。

      0             1             2             3             4 
 +---------+   +---------+   +---------+   +---------+   +---------+
 |    1    |   |    2    |   |  Empty  |   |  Empty  |   |    2    |
 +---------+-->+---------+------------------------------>+---------+-->NULL
 |  next   |   |  next   |   |  node   |   |  node   |   |  next   |
 +---------+   +---------+   +---------+   +---------+   +---------+

所以节点 2,3 为空，0 被 linked 为 1，1 被 linked 为 4。

我试图实现它，但它没有打印任何东西。请指教。谢谢

#include <iostream>

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

node * head = NULL;
node * newNode;
node * temp;

void addNode(int pos, int size)
{
    /*if head is null, initialize a new node
      set data = 1 for head;
    */
    if(head == NULL && pos == 0)
    {
        newNode = new node;
        head = newNode;
        head->x = 1;
        temp = head;
        temp->next=NULL;
    }
    else
    {
        /*
         Adding a node at ith position.
         1. check if the the position is less than the size of the link list.
         2. set the temp position to be 0(head)
         3. use the temp pointer and go to the ith postion.
         4. create new node at ith position.
         5. set data = 2 for the node at ith position.
     */
        if (pos < size)
        {
            for(int i=0; i < size; i++)
            {
                temp = head;
                temp = temp->next;

                if (pos == i)
                {
                    newNode = new node;
                    temp = newNode;
                    temp->x = 2;
                    temp->next = NULL;
                }
            }
        }
    }
}

void Print() {
    while(head->next != NULL)
    {
        std::cout<< head->x << std::endl;
        head=head->next;
    }
}

int main()
{
    int input = 0;
    while (true) {
        std::cout << "1. Add Node and Print " << std::endl;

        std::cin >> input;
        switch ( input ) {
            case 1:
                addNode(0, 5);
                addNode(5, 5);
                addNode(1, 5);
                Print();
                break;
            default:
                std::cout<<"Bad Input";
                break;
        }
        std::cin.get();
    }
    return 0;
}

Answer 1

我理解你的问题，你想编写一个函数来设置指定索引处的节点值，如果索引大于列表的当前大小，它将自动扩展你的列表。（如果我错了请纠正我）

这很容易。您需要在计数器 i（参见下面的代码）小于指定位置时遍历列表。如果列表较小，则创建节点并将其值标记为某个特定值 EMPTY。当counter等于position时，设置node的值为value.

#include <iostream>

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

#define EMPTY -1

node * head = NULL;

void setNode(int pos, int value) {
    if(head == NULL) {
        head = new node;
        head->data = EMPTY;
        head->next = NULL;
    }
    node* p = head;
    for(int i = 0; i < pos; i++) {
        if(p->next == NULL) {
            p->next = new node;
            p->next->data = EMPTY;
            p->next->next = NULL;
        }
        p = p->next;
    }
    p->data = value;
}

void print() {
    node* p = head;
    while(p != NULL) {
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

int main() {
    setNode(0, 1);
    setNode(5, 2);
    setNode(1, 3);
    print();
    return 0;
}

同样在您的代码中，打印函数也有错误：

您更改了 head 变量。
由于 while 循环中的条件，列表的最后一个值没有被打印出来。

在第 i 个位置添加节点

adding node at ith position

c++

nodes