Проблема в понимании некоторых основных функций связанного списка - PullRequest
Новая
       3

Проблема в понимании некоторых основных функций связанного списка

0 голосов
/ 07 января 2020 
void
LInsert (LIST * l, int x, int pos)
{  
    struct Node *new, *p;   // p: previous node
    // create a new node
    new = (struct Node *) malloc (sizeof (struct Node));
    new->val = x;
    if (pos == 0)
    {               // insert to start
        new->next = l->head;
        l->head = new;
    }
    else
    {               
        // insert after p
        p = l->head;

        while (p != NULL && pos > 1)
        {
            p = p->next;
            --pos;
        }

        if (p == NULL)
        {
            printf ("LInsert: Position not possible\n");
            return;
        }
        new->next = p->next;
        p->next = new;
    }
    l->size++;
}

Это функция вставки узла в связанный список. Я не понимаю несколько строк в этой программе. В первом условии if есть строка new->next=l->head;. По моему мнению, это означает, что в «следующей» части нового узла будет храниться то, что находится в главном узле (вероятно, адрес), но почему? Это делает связанный список круглым связанным списком, но это просто простой связанный список. Также ближе к концу new->next=p->next что это значит. Это делает связанный список снова круглым. Надеюсь, что отступ верен. Я всегда заставляю людей кричать на меня за неправильный отступ. Вот полный код, который включает в себя декларацию stru c и прочее 

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

struct Node {
    int  val;
    struct Node *next;
};

struct List {
    struct Node *head;
    int size;
};

// LIST is new name for "struct List"
typedef struct List LIST;

void LInit(LIST *l){ // Initialize list to empty
    l->head = NULL;  // pointer to first node
    l->size = 0;     // number of nodes
}

int LGetPos(LIST *l, int x) {
    struct Node *p;
    int i=0;
    // go through all nodes
    for (p=l->head; p!=NULL; p=p->next)
        if (p->val == x) return i;   // found
        else i++;                    // next
    return -1;   // not found in the list
}

int LGetAt(LIST *l, int pos) {
    struct Node *p=l->head;
    int i;
    // go to position
    for(i=0; p!=NULL && i<pos; i++) p = p->next;
    if(p) return p->val;  // if exists, return it
    else { printf("LDelete: Position not exist\n"); return -99; }
}

void LInsert(LIST *l, int x, int pos) {
    struct Node *new, *p;  // p: previous node
    // create a new node
    new = (struct Node *) malloc(sizeof(struct Node));
    new->val = x;
    if(pos==0) {  // insert to start
        new->next = l->head;
        l->head = new;
    }
    else {  // insert after p
        p = l->head;
        while(p!=NULL && pos>1) { p = p->next; --pos; }
        if(p==NULL) { printf("LInsert: Position not possible\n"); return; }
        new->next = p->next;
        p->next = new;
    }
    l->size++;
}

void LDelete(LIST *l, int pos) {
    struct Node *p, *d;  // p: previous
    if(l->head == NULL) return;
    if(pos==0) {  // delete first node
        d = l->head;
        l->head = d->next;
    }
    else {  // delete after p
        p = l->head;
        while(pos>1 && p) { p = p->next; --pos; }
        if(p==NULL) { printf("LDelete: Position not exist\n"); return; }
        d = p->next;
        p->next = p->next->next;
    }
    l->size--;
    free(d);
}

int LIsEmpty(LIST * l){
    return (l->size == 0);
}

int LSize(LIST * l){
     return (l->size);
}

void LDisplay(LIST *l) {
    struct Node *p;
    printf("List: ");
    for(p=l->head; p!=NULL; p=p->next)
        printf("--> %d ", p->val);
    printf("\n");
}

int LHeadOf(LIST *l) {
    if (!LIsEmpty(l)) return l->head->val;
    else {
        printf("LHeadOf: Linked list empty\n");
        return -99;
    }
}


int main() {
    LIST list;

    LInit(&list);
    LDisplay(&list);

    LInsert(&list, 3, 0);
    LInsert(&list, 4, 0);
    LInsert(&list, 5, 2);
    LDisplay(&list);

    printf("Value at 1: %d\n", LGetAt(&list, 1));

    printf("Location of 4: %d\n", LGetPos(&list, 4));

    LDelete(&list, 1);
    LDisplay(&list);

    return 0;

}

1 Ответ

0 голосов
/ 07 января 2020

Я не понимаю несколько строк в этой программе

Хорошо, давайте посмотрим на эти строки ...

вот line new->next=l->head; По моему мнению, это означает, что в «следующей» части нового узла он будет хранить то, что находится в головном узле (вероятно, адрес), но почему?

Эта строка используется для вставки нового элемента перед текущего элемента заголовка. Так что 

new->next=l->head;  // Make the new element point to current head
l->head = new;      // Change head to point to the new element as it is now the front element

Также ближе к концу new->next=p->next что это значит. Это делает связанный список снова круглым.

Ну, это не делает список циркулярный. Он просто вставляет новый элемент где-то посередине списка. 

    new->next = p->next;  // Make new point to the element after p
    p->next = new;        // Make p point to new
                          // In this way new has between inserted after p and
                          // before the element that folloed p
...