Вставить элемент в связанный список - индекс не существует

avatar
amr125
8 апреля 2018 в 12:23
153
1
-1

Мне дали пример кода C для вставки нового элемента в связанный список по заданному индексу. Но с исходным кодом я всегда получаю сообщение об ошибке, что индекс неверен, и я не знаю, то ли я не понимаю код, то ли в коде есть ошибка.

Операция insert определяется следующим образом:

void insert (list *l, int e, int index) {
    int i;
    node *tmp;
    node *prev;
    i=1;
    prev=l->first;
    while (!end(prev) && (i<index-1)) {
        i++;
        prev=prev->next;
    }
    if ( ((i+1) <= index) ) {
        printf("\n Error: index position doesn't exist\n");
    }
    else {
        tmp = (node *)malloc(sizeof(node));
        if (tmp == NULL) {
            printf("\n Error: Not enough free memory\n");
        }
        else {
            tmp->e = e;
            if (emptyList(*l)) {
                /* empty list */
                tmp->next=NULL;
                l->first=tmp;
            }
            else {
                if (index == 1) {
                    /* no previous element */
                    tmp->next=l->first;
                    l->first=tmp;
                }
                else {
                    /* standard case */
                    tmp->next=prev->next;
                    prev->next=tmp;
                }
            }
        }
    }
}

Я всегда получаю ошибку позиция индекса не существует для любого индекса, отличного от 1. И я понимаю, что допустимый индекс должен находиться в диапазоне (1 <= индекс <= число_элементов+1)

Если я изменю условие, которое дает ошибку следующим образом:

if ( ((i+1) < index) ) {
    printf("\n Error: index position doesn't exist\n");
}

Тогда это работает, за исключением случаев, когда индекс представляет собой количество элементов списка +2, что приводит к ошибке сегментации.

Можно ли это исправить? Я придумал способ, используя вспомогательную функцию, которая подсчитывает количество элементов списка:

if ( index > count_elements(l)+1 ) {
    printf("\n Error: index position doesn't exist\n");
}

Но я хотел бы знать, как решить эту проблему, используя переменную i в функции insert.

Вот короткая версия рабочего кода, который я использую:

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

typedef struct tnode {
    int e;
    struct tnode *next;
} node;

typedef struct {
    node *first;
} list;


int end(node *n)
{
       return (n==NULL);
}

int emptyList (list l)
{
       return(l.first==NULL);
}

void createList(list *l)
{
    l->first=NULL;
}


    void insert (list *l, int e, int index) {
        int i;
        node *tmp;
        node *prev;
        i=1;
        prev=l->first;
        while (!end(prev) && (i<index-1)) {
            i++;
            prev=prev->next;
        }
        if ( ((i+1) <= index) ) {
            printf("\n Error: index position doesn't exist\n");
        }
        else {
            tmp = (node *)malloc(sizeof(node));
            if (tmp == NULL) {
                printf("\n Error: Not enough free memory\n");
            }
            else {
                tmp->e = e;
                if (emptyList(*l)) {
                    /* empty list */
                    tmp->next=NULL;
                    l->first=tmp;
                }
                else {
                    if (index == 1) {
                        /* no previous element */
                        tmp->next=l->first;
                        l->first=tmp;
                    }
                    else {
                        /* standard case */
                        tmp->next=prev->next;
                        prev->next=tmp;
                    }
                }
            }
        }
    }

int main(int argc, char **argv)
{

    list l;

    createList(&l);

    printf("insert at index 1\n");
    insert(&l, 10, 1);

    printf("insert at index 1\n");
    insert(&l, 20, 1);

    printf("insert at index 2\n");
    insert(&l, 30, 2);

    return 0;
}

Спасибо

Источник
Sami Kuhmonen
8 апреля 2018 в 12:28
2

Ваше первое условие: «Я должен быть меньше индекса-1», что означает, что если узлов достаточно, я в конечном итоге стану индексом-1. Затем вы проверяете, меньше ли i+1 или равно индексу, и если это так, вы показываете ошибку. Что всегда будет происходить. Итак, одно из этих условий явно неверно. В этих случаях используйте отладчик, чтобы запустить код и посмотреть, что произойдет.

Ответы (1)

avatar
purec
8 апреля 2018 в 12:56
0
if ( ((i+1) <= index) ) 

Может быть, это то условие, которое вам нужно?

if ( ((i+1) <= index) && end(prev))