c++ - 在第 i 个位置添加节点

Question

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

我将在链接列表的随机位置(例如(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 链接到 4。

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

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

所以节点 2,3 为空，0 链接到 1，1 链接到 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。当计数器等于位置时，将节点的值设置为值。

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

在您的代码中，打印功能也存在错误:

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