C链表: Placing number infront of the list and making all numbers shift

Question

我正在尝试让方法 shiftInsert 工作。我想在列表中插入一个数字并使最后一个数字消失。如果这是列表 p 1 -> 2 -> 3 -> 4 -> 5，在 shiftInsert(8) 之后列表需要看起来像这样 p 8 -> 1 -> 2 -> 3 -> 4。如您所见，最后一个数字需要消失。我该如何实现？

#include <stdio.h>
#include <stdlib.h>

struct elem {
    int value;
    struct elem *next;
};

typedef struct elem Node;

Node *root;

Node * addElem(Node *p, int value) {
    p->next = malloc(sizeof *p);
    p = p->next;
    p->value = value;
    p->next = NULL;
    return p;
}

void shiftInsert(Node *n, int v) {
    int tmp;

    while (n != NULL) {
        Node * new_node;
        new_node = malloc(sizeof (new_node));
        n = n->next;
    }
}

void printList() {
    Node *p = root;

    while (p != NULL) {
        printf("%2d -> ", p->value);
        p = p->next;
    }

    printf("NULL\n");
}

int main(int argc, char **argv) {
    Node *p;
    int i = 0;

    root = p = malloc(sizeof (Node));
    p->value = 1;

    for (i = 2; i <= 10; i++) {
        p = addElem(p, i);
    }

    printList();
    shiftInsert(root, 88);
    printList();
    shiftInsert(root->next->next->next, 33);
    printList();

    return 0;
} 

Answer 1

根据您的示例，您想插入第一个位置并删除最后一个位置。所以基本上你想创建一个新的根，然后找到最后一个元素并将其 next 设置为 NULL。

首先是删除函数:

void deleteLast()
{
    int i, before_last = 0;
    Node *temp;

    /* Find last element to remove it*/
    temp = root;

    for(i = 0; temp->next != NULL; i++) { // "i" will be the index of the last element
        temp = temp->next;
    }

    before_last = i - 1; // the one before "i" will be the new last element
    temp = root;

    for(i = 0; i < before_last; i++) { // find the one before last and set its "next" NULL
        temp = temp->next;
    }

    free(temp->next);
    temp->next = NULL;
}

新根，创建一个元素作为新根。将其next设置为root，然后将新元素设为root。

void shiftInsertRoot(int v) {

    if (root != NULL) {
        Node * new_root;
        /* Create new root */
        new_root = malloc(sizeof (new_root));
        new_root->next = root; // save previous root
        new_root->value = v;   // set new value
        root = new_root;       // update root pointer

        deleteLast();
    }
}

---

根据你的main，你想在某个元素之后插入，你得先找到它。然后创建一个新元素并将其 next 设置为原始元素的 next，这样您就不会丢失列表的其余部分。最后将原元素的next设置为新元素。

void shiftInsertAnywhere(Node *position, int v) {
    int i;
    Node *temp;

    temp = root;

    for(i = 0; temp->value != position->value; i++) {

        temp = temp->next;
    }

    if (temp != NULL) {
        Node * new_root;
        /* Create new root */
        new_root = malloc(sizeof (new_root));
        new_root->next = temp->next; // save the rest of the list
        new_root->value = v;         // set new value
        position->next = new_root;   // insert the new element after "position" element

        deleteLast();
    }
}

这将在位置之后插入。

例子:

printList();
shiftInsertRoot(88);
printList();
shiftInsertRoot(33);
printList();
shiftInsertAnywhere(root->next->next, 99);
printList();
shiftInsertAnywhere(root, 17171);
printList();

输出: