Блог

Я пытаюсь заставить метод 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("- -> ", p->value);
        p = p->next;
    }

    printf("NULLn");
}

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

Согласно вашему примеру, вы хотите вставить в первую позицию и удалить последнюю. Итак, в основном вы хотите создать новый корень, затем найти предпоследний элемент и установить для него 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();
    }
}
 

Согласно вашему основному, вы хотите вставить после определенного элемента, вы должны сначала его найти. Затем создайте новый элемент и установите для него 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();
    }
}
 

Это будет вставлено после position .

Пример:

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

Вывод:

Вам не нужно выделять новое пространство для вставки узлов без увеличения списка. Вот функция, которая вставляет узел в начало списка и удаляет последний узел:

 Node * shiftInsert(Node *n, int v) {
    Node *tail = n;

    if (n == NULL){
        return n;
    } else if (n->next == NULL) {
        n->value = v;
        return n;
    }
    while (tail->next->next != NULL)
        tail = tail->next;
    tail->next->value = v;
    tail->next->next = n;
    n = tail->next;
    tail->next = NULL;

    return n;
}
 

Обратите внимание, что эта версия shiftInsert() возвращает указатель на начало списка.

Вот вторая функция, которая позволяет вам вставить узел в любом месте списка и удалить последний узел:

 Node * shiftInsertAny(Node *root, Node *n, int v) {
    Node *tail = n;
    Node *insert = root;

    if (root == NULL){
        return root;

    } else if (root->next == NULL) {
        root->value = v;
        return root;

    }
    while (n != root amp;amp; insert->next != n)
        insert = insert->next;
    if (insert->next->next == NULL) {
        insert->next->value = v;
        return root;
    }
    while (tail->next->next != NULL)
        tail = tail->next;
    tail->next->value = v;
    tail->next->next = n;
    if (insert == root)
        root = tail->next;
    else
        insert->next = tail->next;
    tail->next = NULL;

    return root;
}
 

Эта функция также возвращает указатель на начало списка и принимает как указатель на начало списка, так и указатель на точку вставки в качестве аргументов. Новый узел вставляется перед узлом, указанным указателем n .

Если вы вызываете эти функции следующим образом в своем коде:

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

это результат:

 1 ->  2 ->  3 ->  4 ->  5 ->  6 ->  7 ->  8 ->  9 -> 10 -> NULL
88 ->  1 ->  2 ->  3 ->  4 ->  5 ->  6 ->  7 ->  8 ->  9 -> NULL
88 ->  1 ->  2 -> 33 ->  3 ->  4 ->  5 ->  6 ->  7 ->  8 -> NULL
 

Я обновил приведенный выше фрагмент кода для shiftInsertAny() функции. Я внес изменения, позволяющие вставлять узел в начало списка, но я забыл отредактировать фрагмент кода ранее. С помощью этой функции вы можете вставить в первый или последний узел. Например, со списком из 5 элементов вы можете сделать:

 printList();
root = shiftInsertAny(root, root, 88);
printList();
root = shiftInsertAny(root, root->next->next->next->next, 33);
printList();
 

который имеет вывод:

 1 ->  2 ->  3 ->  4 ->  5 -> NULL
88 ->  1 ->  2 ->  3 ->  4 -> NULL
88 ->  1 ->  2 ->  3 -> 33 -> NULL