c - 将节点添加到链表中的随机位置

Question

所以我有一个函数可以将节点添加到链接列表中，但我不只是在链接列表的末尾添加元素，而是尝试获取用户想要添加它的位置的用户输入。然后需要添加它并转移其他所有内容而不删除其他任何内容。我在这方面遇到了很多麻烦。

下面我将展示我的代码，它有点困惑，但我会尽力解释。

void InsertGraphicElement(struct RasterGraphic *pA) {
    int counter = 1;
    int response = 0;
    char tempString[256];
    struct GraphicElement *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL)
        return;

    newNode->fileName = malloc(256 * sizeof(char));
    if (newNode->fileName == NULL)
        return;
    newNode->pNext = NULL;

    printf("Insert a GraphicElement in the RasterGraphic\nPlease enter the GraphicElement filename: ");
    scanf("%s", newNode->fileName);

    if (pA->GraphicElements == NULL) {
        pA->GraphicElements = newNode;
        printf("This is the first GraphicElement in the list\n");
    } else {
        struct GraphicElement *tempHead = pA->GraphicElements;
        struct GraphicElement *tempTail = pA->GraphicElements;
        while (tempHead->pNext != NULL) {
            tempHead = tempHead->pNext;
            counter++;
        }
        tempHead->pNext = newNode;

        printf("There are %d GraphicElement(s) in the list. Please specify the position (<= %d) to insert at :", counter, counter);
        scanf("%d", &response);

        if (response == counter) {
            return;
        } else {
            while (response < counter) {
                tempTail = tempTail->pNext;
                response++;
            }       
        }
    }
    return;
}

它是不完整的，我一直在弄乱代码试图弄清楚它，但正如你所看到的，我可以毫无问题地在列表末尾添加。我遇到的问题是，如果列表中有 5 个元素 1,2,3,4,,5 并且我添加第六个元素，列表显然会像这样 1 ,2,3,4,5,6。我想要做的是获取用户输入，例如他们想要将第六个元素添加到位置 3，这样列表将如下所示 1,2,6,3,4,5。我已经尝试了很多正确方向的事情，或者提供一些帮助将不胜感激。谢谢，

下面是我的结构定义

struct GraphicElement {
    char *fileName;
    struct GraphicElement *pNext;
};
struct RasterGraphic {
    //int numNodes;
    struct GraphicElement *GraphicElements;
};

Answer 1

您目前拥有以下内容:

if (response == counter) {
    return;
}
else {
    while(response < counter){
        tempTail = tempTail->pNext;
        response++;
    }
}       

我会将其修改为:

if (response > counter+1 || response < 1) { // These are all invalid values
    return;
}
else if (response == 1) { // We are replacing the head node
    newNode->pNext = tempTail->pNext;
    pA->GraphicElements = newNode;
}
else {
    while(response-- > 2) { // Responses are 1-indexed
        tempTail = tempTail->pNext;
    }
    newNode->pNext = tempTail->pNext; // IMPORTANT: Update newNode reference FIRST
    tempTail->pNext = newNode; // Update tempTail to point to newNode
}  

免责声明 - 未经任何方式测试

我试图在这里或那里评论我认为重要的事情。这里要记住的关键一点是，为了将某些内容插入到单链表中，您必须在更新新节点以指向链表的其余部分之前更新它之前的节点的引用，否则列表的最后一位将永远丢失，并且您将拥有对最后一个节点的循环引用。

作为旁注，每次您想要向其中添加新元素时，您都会遍历整个链接列表两次。我可能建议保留一个滚动计数器，记录每次向链表中添加内容时更新的链表中有多少项，以避免在您重视效率时重新计算该值的开销。

希望这有帮助!

编辑:但是，您必须删除将新节点添加到函数中较高列表末尾的行才能使其正常工作。 “tempHead->pNext = newNode;”