1

好的，这是我在单链表上的训练，作为一个新手......但是，我必须在某个地方搞砸了。我的代码非常简单，包含您期望的所有典型过程。

问题：

即使我输入不在列表中的数字，我的布尔函数也始终为真

这是我的代码，同时查看 main 函数以了解事情发生的顺序。哦，谢谢你的帮助！！:)

#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";

}
4

3 回答 3

0

.（当我删除尾节点时，前一个节点的链接现在是否只是指向内存的某个随机部分？这是问题吗？为什么是无限循环？

看起来像：

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->链接不会给你任何不正确的指针访问。如果 head->link->link == NULL，没关系。

为什么无限循环？

一个有趣的问题。

对于一个稍微有缺陷的哲学解释：假设您没有因访问错误指针而导致非法内存访问错误，那么您正在谈论一个随机指向某处的指针值。实际内存是有限的，因此有限集中的任何指针引用序列都必须在循环中的某个点重复（否则该集将不是有限的）。当然，这可能包括一个 NULL 来停止无限循环。

您更有可能遇到操作系统内存管理器保留的一些错误内存模式，例如指向 0xcdcdcdcd 的 0xcdcdcdcd。在这种情况下，这是一个糟糕的选择：可能应该设计默认内存模式，以便如果它们出现在指针中，它们可能会导致错误的内存异常。

您可以在调试器中停止程序并告诉我们指针值是什么，这将回答问题的那一部分。

于 2012-01-28T11:52:11.610 回答
0

编译时应该打开警告。这是编译器所说的：

% 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(...)使用一些参数调用该函数。

于 2012-01-28T11:57:42.657 回答
0

第一件事是你做

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

这可能应该是

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

第一个版本基本上是检查指向“found”的函数指针是否不为空，即它是否有值。第二个实际上调用了您可能想要的函数。

第二件事是当你去掉尾巴时。您实际上并没有将其从列表中删除，而只是将其删除。您也需要从列表中取消链接，否则您将指向未初始化的内存。

于 2012-01-28T11:58:40.393 回答