C программирование связанных списков удалить узел в позиции N - PullRequest
Новая
       16

C программирование связанных списков удалить узел в позиции N

4 голосов
/ 16 февраля 2011

РЕДАКТИРОВАТЬ: выяснил проблему. Также, если вы нашли это через Google или другую поисковую систему, здесь я ошибся и как это исправить.

Мой метод deleteNode () перемещался по списку должным образом с правильной температурой и держал голову нетронутой. То, что я делал не так, было в том, что я возвращал в результате метода. Я возвращал либо temp, либо newNode, что неверно, поскольку он проходит по списку, пока не найдет определенную позицию. Как только он находит эту определенную позицию, он переназначает указатель -> next, чтобы указывать на указатель next-> next>, что правильно, но опять же я возвращал неправильную вещь. Поскольку мы перемещались по списку, используя temp / NewNode, мы потеряли заголовок, и мы возвращали найденную позицию и все, что оставалось в следующих позициях списка.

Как мы это исправим - это вернуть голову (что и передается в метод). Причина, по которой это работает, заключается в том, что мы должны понимать, как работают LinkedLists. Указатели каждого узла указывают на следующий узел. Ex. у нас есть связанный список | A | | - | B | | - | C | | - | D | | - | E | | - | F | |

Если мы хотим удалить узел C, мы перемещаемся к узлу B, используя указатель temp, а затем назначаем B-> рядом с temp-> next-> next. Таким образом, пропуская узел C и назначая узел D.

ПРИМЕЧАНИЕ: (Из того, что я знаю, это на самом деле не освобождает память узла C, так что это не лучшая практика, потому что вы можете вызвать утечки памяти таким образом). Вы должны использовать метод free () на узле C. 1017 *

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

struct node* DeleteNode(struct node* head, int pos) {

     struct node* temp = head;
     int length = LinkedListLength(temp);
     int i;

    if(pos <= 0 || pos > length){
        printf("ERROR: Node does not exist!\n");
    }else{
        if(pos == 1){
            head = head->next; //move from head (1st node) to second node
        }else{
            for(i = 1; i < pos-1; ++i){ //move through list
                    temp = temp->next;
            }
            temp->next = temp->next->next;
        }
    }
    return head;
}

Надеюсь, это поможет понять, как я решил исправить это.

/////////////////////////////////////////////// ////////////////////////////////////////////////// /
////////////////////////////////////////////////// ////////////////////////////////////////////////
ОРИГИНАЛЬНАЯ ПОЧТА
////////////////////////////////////////////////// ////////////////////////////////////////////////
////////////////////////////////////////////////// ////////////////////////////////////////////////////

РЕДАКТИРОВАТЬ: Примечание. Это домашнее задание. Я потратил несколько дней (примерно 4 часа) на программирование. Я просто застрял в этой части. Вы можете посмотреть мою попытку ниже

Мне удалось вставить и удалить с начала / конца, однако я не могу заставить свой узел удаления в позиции N в списке ссылок работать.

Мой псевдокод выглядит так:

  1. LinkedList: 1,3,5,7,9,23
  2. Grab LinkedList
  3. Создать новый структурный узел A = head
  4. Перемещаться по связанному списку до положение
  5. Назначить узел на узел-> следующий
  6. вернуть связанный список

ПРИМЕР ВХОДА 

Node structure 
int data;
struct node* next;

int values[] = {1,3,5,7,9,23};
struct node* llist = CreateList(values,6);

llist = DeleteNode(llist, 1);
llist = DeleteNode(llist, 5);
llist = DeleteNode(llist, 3);

Что должно оставить список со значениями 3, 5, 9 после запуска кода. Однако, он заменяет первый узел на 0

Фактический код: 

struct node* DeleteNode(struct node* head, int pos) {

struct node* temp = head;
struct node* newNode = head;
int length;
int i;

printf("DeleteNode: position = %d \nBefore: ", pos);
PrintList(temp);

if(pos <= 0){ //node does NOT exist
    printf("ERROR: Node does not exist!\n");
}else{ //node DOES exist
    length = LinkedListLength(temp);

    if(length < pos){ //if length < position Node does not exist
        printf("ERROR: Node does not exist!\n");
    }else{
        if(pos == 0){
            newNode = temp->next;
        }else if(pos == 1){
            newNode = temp->next;
        }else{
            for(i = 1; i < pos; i++){
                printf("i = %d\n", i);
                temp = temp->next;
                newNode->next;
            }
            if(temp->next == NULL){
                newNode = NULL;
            }else{
                newNode = temp->next;
            }
        }
    printf("After: ");
    PrintList(newNode);
    printf("\n");
    }
}
return newNode;
}

РЕДАКТИРОВАТЬ # 2: опечатка кода

Спасибо за любую помощь заранее. Из того, что я пришел к выводу, моя проблема в том, что я не перемещаюсь по списку должным образом, но я не уверен, почему я не.

Ответы [ 5 ]

1 голос
/ 16 февраля 2011

Ваш DeleteNode не удаляет узел, он удаляет pos-узлы в начале списка.Таким образом, вы пытаетесь удалить 9 элементов из списка, который содержит только 6, в результате, конечно, пустой список (NULL)Кроме того, ваш код слишком сложен и содержит остатки предыдущих попыток.Пожалуйста, не делайте этого ни себе, ни нам;предоставьте простой чистый код, и его будет легче понять и исправить.

1 голос
/ 16 февраля 2011

Удаление данного узла n из односвязного списка можно свести к следующей операции:

  • Установите указатель, который указывает на n, чтобы указать вместо n->next.

Вы можете разбить это на две операции:

  • Найдите указатель, указывающий на n;
  • Установите этот указатель на n->next.

Сложность возникает из-за того, что указатель, указывающий на n, может быть либо полем p->next предыдущего узла в списке, либо указателем head (если n является первым узлом в списке) .

Ваш код не выглядит полным - он никогда не устанавливает в поле ->next какого-либо узла ничего, поэтому трудно сказать, что на самом деле не так.

1 голос
/ 16 февраля 2011

В вашем коде у вас есть строка 

newNode->next;

в вашем for цикле.Эта операция ничего не делает.

У вас также есть 

newNode-> = NULL;

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

typedef struct node node_t;

node_t* delete_at_index(node_t* head, unsigned i)
{
    node_t* next;

    if(head == NULL)
        return head;

    next = head->next;

    return i == 0
             ? (free(head), next)                                 /* If i == 0, the first element needs to die. Do it. */
             : (head->next = delete_at_index(next, i - 1), head); /* If it isn't the first element, we recursively check the rest. */
}
0 голосов
/ 17 января 2016

Выяснил, что ваш цикл for не достигает желаемой позиции, которую вы хотели. Лучше использовать знак равенства для ограничения, которое будет работать. например, 

for (i=1;i<=position-1;i++)
{

}
0 голосов
/ 16 февраля 2011 
// Remove list's node located at specified position.
// Arguments:
//  head -- list's head
//  pos -- index of a node to be removed (1-based!!!)

struct node* DeleteNode(struct node* head, int pos) 
{

    struct node* node;
    struct node* prev;
    int length;
    int i;

    printf("DeleteNode: position = %d \nBefore: ", pos);
    PrintList(head);

    // Check position's lower bound. Should be >= 1
    if(pos <= 0) { //node does NOT exist
        printf("ERROR: Node does not exist!\n");
        return head;
    }

    // Seek to the specified node, and keep track of previous node.
    // We need previous node to remove specified node from the list.

    for(i=1, prev = 0, node = head; i < pos && node != 0; i++) {
        prev = node;
        node = node->next;
    }

    // Out of range
    if(0 == node) {
        printf("ERROR: Index out of bounds!\n");
        return head;
    }

    // @node points to a list's node located at index pos 
    // @prev points to a previous node.

    // Remove current node from the list.
    if(0 == prev) {
        head = node->next;
    }
    else {
        prev->next = node->next;
    }
    free(node);

    return head;   
}
...