Как удалить узел из связанного списка?

Как я могу удалить узел (между двумя узлами) из одного связанного списка, не передавая никаких параметров функции класса?

Например, у меня есть список из 6 узлов с одним головным узлом, и я хочу удалить два из них (без предварительного знания их адреса или положения) из функции класса, как мне это сделать?

void WordList::deleteNode(){
Node *temp;
temp=head;
if(temp->count<=10)
{
//delete this node... not sure how though
}
else
temp=temp->next;
}

где WordList — мой класс, Node — моя структура, содержащая слово, число и указатель. Я хочу удалить любой узел со счетчиком 10 или меньше.


c++ abstract-class linked-list
person Chase Sawyer    schedule 17.09.2010    source источник
comment
извините, как только я опубликовал это, я пошел редактировать его, потому что понял, насколько расплывчатым/запутанным был мой вопрос. Надеюсь теперь более понятно   -  person Chase Sawyer    schedule 17.09.2010
comment
Это домашнее задание? Подумайте (или начертите на черновике), как выглядит структура данных, прежде чем удалять узел, и как должны измениться указатели узлов, чтобы разъединить узел из цепочки. Также подумайте, куда указывает temp во время отключения целевого узла и куда он должен указывать после отключения, а также нужно ли еще temp продвигаться вперед (temp=temp->next).   -  person Bert F    schedule 17.09.2010

Ответы (4)


arrow_upward
2
arrow_downward

В вашем редактировании есть предыдущая информация, бит, указывающий на "счетчик ‹= 10" :-)

Псевдокод для удаления элементов, соответствующих этим критериям, в односвязном списке:

def delLessThanTen:
    # Delete heads meeting criteria, stop when list empty.

    while head != NULL and head->count <= 10:
        temp = head->next
        free head
        head = temp
    if head == NULL:
        return

    # Head exists, with count > 10, process starting there (we check
    #    NEXT element for criteria then delete if met).

    ptr = head
    while ptr->next != NULL:
        # If next in list meets criteria, delete it, otherwise advance.

        if ptr->next->count <= 10:
            temp = ptr->next->next
            free ptr->next
            ptr->next = temp
        else:
            ptr = ptr->next

    return
person Community    schedule 17.09.2010

arrow_upward
2
arrow_downward

Я нахожу вопрос слишком запутанным.

Удаление узла из списка всегда основывается на некоторых критериях, например. содержимое элемента, положение элемента и т. д. (если вы не удаляете все элементы в списке)

person Chubsdad    schedule 17.09.2010
comment
Спасибо, я отредактировал вопрос. Надеюсь, теперь стало более понятно. Я хочу удалить его на основе содержимого элемента - person Chase Sawyer; 17.09.2010

arrow_upward
2
arrow_downward

что-то вроде этого:

void WordList::deleteNode(){
Node *prev=NULL;
temp=head;
bool done=false;
while (!done)
{
  if (temp->count<=10)
  {
    if (prev == NULL)
    {
      head = temp->next;
    } else
    {
      prev->next = temp->next;

    }
    // delete data in temp, and the node if necessary
    temp = temp->next;
    done = (temp==NULL) || // some other condition, like deleted 2
  } else
  {
    prev=temp;
    temp = temp->next;
    done = (temp==NULL);
  }
}
person paquetp    schedule 17.09.2010
comment
@ sje397: согласен ... Я предполагал, что ОП хочет каких-то других условий, кроме «я повторил весь список». спасибо за повышение - person paquetp; 19.09.2010

arrow_upward
1
arrow_downward

Иметь предыдущую переменную, инициализированную нулем. Если вы удаляете узел, измените предыдущий рядом со следующим элементом, если предыдущий не равен нулю (вы находитесь в начале списка), когда вы оставляете предыдущий нуль и меняете корень на следующий удаленный элемент. Если вы не удаляете элемент, измените предыдущий элемент.

Здесь предыдущее всегда будет указывать на предыдущий элемент или будет нулевым, если вы находитесь в начале списка.

void WordList::deleteNode() {
    Node *temp = head;
    Node *previous = null;
    while (temp != null) {
        if(temp->count <= 10) {
            // delete node
            if (previous == null) {
                // there is no previous node, so point head of list past the current node
                head = temp->next;
            } else {
                // there is a previous node, so just point it past the current node
                previous->next = temp->next;
            }
        } else {
            // not deleting, so set previous to temp
            previous = temp;
        }
        temp = temp->next;
    }
}
person Jason Goemaat    schedule 17.09.2010