Функция bool всегда true и удаление узла хвоста в односвязном списке создает бесконечный цикл

Question

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

Проблемы:

Моя логическая функция всегда верна, даже когда я набираю цифры, которых нет в списке

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

#include <string>
#include <iostream>

using namespace std;

class Node
{
    public:
         int n;
         Node* link;
};

void display(Node* head)
{

    cout<<head->n<<" ";

    while(head->link!=NULL)
    {
        head=head->link;
        cout<<head->n<<" ";
    }
    cout<<endl;

}

void addnode(Node*& head, int x) 
{
    if(head==NULL)
    {
        head=new Node;
        head->n=x;
        head->link=NULL; // Necessary? Why?
    }

    else
    {
        Node* p=new Node;
        p->n=x;
        p->link=head;
        head=p;
    }
}

bool found(Node* head, int x)
{                            
    if(head->n==x) return true;

    while(head->link!=NULL)
    {
        head=head->link;
        if(head->n==x) return true;
    }

    return false;
}


void addtail(Node*& head, int x) 
{                                
    if(head==NULL)          
    {                        
        head=new Node;  
        head->n=x;
        head->link=NULL;
    }

    else
    {
        Node* q=NULL; 
        q=head;       
        while(q->link!=NULL) q=q->link;

        Node* r=new Node;
        r->n=x;
        r->link=NULL;
        q->link=r;
    }
}

int removehead(Node*& head) 
{
    if(head==NULL)
    {
        cout<<"The list is empty";
        return 0; 
    }             

    int x;

    if(head->link==NULL)
    {
        x=head->n;
        head=NULL;
        return x;%0stackoverflow.com 
    Node* p=NULL;    
    p=head;
    head=head->link;
    x=p->n;
    delete p;
    return x;
}

int removetail(Node*& head) 
{
    if(head==NULL)
    {
        cout<<"The list is empty";
        return 0;
    }

    int x;

    if(head->link==NULL)
    {
        x=head->n;
        delete head;
        Node* head=NULL;
        return x;
    }

    Node* p=NULL; 
    p=head;
    while(p->link!=NULL) p=p->link;

    x=p->n;
    delete p;
    return x;
}



int main()
{

    int y; int z;

    Node* p=NULL;

    while(cin>>y)
    {
        addnode(p,y);
    }

    cin.clear(); cin.ignore(); 


    cout<<endl;

    display(p);

    cout<<endl;

    cout<<removehead(p)<<" ";

    cout<<removetail(p)<<endl;

    display(p);

    cout<<endl<<"give me a number:";

    cin>>z;

    if(found) cout<<endl<<"found"; 

    else cout<<endl<<"not found";

}

Answer 1

Вы должны включить предупреждения при компиляции. Вот что говорит компилятор:

% g++ -Wall list.cc
list.cc: In function ‘int removetail(Node*&)’:
list.cc:120:15: warning: unused variable ‘head’ [-Wunused-variable]
list.cc: In function ‘int main()’:
list.cc:166:13: warning: the address of ‘bool found(Node*, int)’ will always evaluate as ‘true’ [-Waddress]

Первая ошибка указывает на то, что вы объявили локальную переменную head в функции removetail (с Node* head=NULL;), в то время как вы, вероятно, хотели обновить значение аргумента (просто head=NULL;).

Вторая ошибка объясняет, почему found (адрес) всегда верно. Возможно, вы хотели вызвать функцию found(...) с некоторыми аргументами.

Answer 2

Во-первых, вы делаете

if(found) cout<<endl<<"found"; 

, которое, вероятно, должно быть

if(found(p,z)) cout<<endl<<"found";

Первая версия в основном проверяет, не равен ли указатель функции "found" нулюто есть что оно имеет ценность.Второй фактически вызывает функцию, как вы, вероятно, хотели.

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

Answer 3

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

выглядит так:

int removetail(Node*& head) 
{
    // base cases elided

    Node* p=NULL; 
    p=head;
    while(p->link!=NULL) p=p->link;

    x=p->n;
    delete p;
    return x;
}

Предыдущая ссылка, указывающая на p, который вы удаляете, по-прежнему указывает на p. Плохой. Это должно быть что-то вроде этого:

int removetail(Node*& head) 
{
    // base cases elided

    Node* p=NULL; 
    p=head;
    while(p->link->link!=NULL) p=p->link;

    x=p->link->n;
    delete p->link;
    p->link = NULL;     // maintain linked list integrity
    return x;
}

Это безопасно сделать (при условии, что память не повреждена по другим причинам), потому что вы уже проверили, если head==NULL и head->link == NULL в одном из базовых случаев, поэтому начальный вызов p-> link- > link = head-> link-> link не даст вам неправильного доступа к указателю. Если head-> link-> link == NULL, это нормально.

---

А почему бесконечный цикл?

Интересный вопрос.

Для немного ошибочного философского объяснения: если вы не получите ошибку доступа к недопустимой памяти, вызванную обращением к неверному указателю, вы говорите о значении указателя, которое случайно указывает куда-то. Реальная память конечна, поэтому любая последовательность ссылок на указатели в конечном наборе должна повторяться в некоторой точке цикла (иначе набор не будет конечным). Конечно, это может включать NULL, который остановит бесконечный цикл.

Скорее всего, вы столкнулись с каким-то неправильным шаблоном памяти, зарезервированным диспетчером памяти ОС, например 0xcdcdcdcd, который указывает на 0xcdcdcdcd. В этом случае это плохой выбор: шаблоны памяти по умолчанию, вероятно, должны быть спроектированы так, чтобы, если они отображаются в указателе, они могли вызвать исключение плохой памяти.

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