1

わかりました、これは初心者である単一リンクリストでトレーニングしている私です...しかし、どこかで私は物事を台無しにしているに違いありません。私のコードは、あなたが期待するすべての典型的な手順を含む非常に単純です..

問題:

リストにない数値を入力しても、ブール関数は常に true です

これが私のコードです。メイン関数も見て、物事が起こる順序を理解してください。ああ、あなたの助けに感謝します!! :)

#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

コンパイルするときに警告をオンにする必要があります。コンパイラの内容は次のとおりです。

% 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;）更新するつもりでした。

found2番目のエラーは、 （アドレス）が常に真である理由を説明しています。おそらくfound(...)、いくつかの引数を使用して関数を呼び出すことを意図していました。

于 2012-01-28T11:57:42.657 に答える
0

最初のことはあなたがすることです

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

おそらく

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

最初のバージョンは基本的に、「found」への関数ポインタがnullでないかどうか、つまり値があるかどうかをチェックしています。2つ目は、おそらく必要に応じて実際に関数を呼び出します。

2つ目は、尻尾を外すときです。実際にリストから削除するのではなく、単に削除するだけです。リストからもリンクを解除する必要があります。そうしないと、初期化されていないメモリを指すことになります。

于 2012-01-28T11:58:40.393 に答える
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;
}

これは安全に実行できます (他の理由でメモリが破損していないと仮定します)。これは、基本的なケースの 1 つであるかどうかhead==NULLを既に確認しているためです。head->link == NULLリンクは、不適切なポインター アクセスを提供しません。head->link->link == NULL の場合は問題ありません。

そして、なぜ無限ループ？

興味深い質問です。

少し欠陥のある哲学的な説明については、不正なポインターへのアクセスによって引き起こされる不正なメモリアクセスエラーが発生しないと仮定すると、ランダムにどこかを指すポインター値について話していることになります。実メモリは有限であるため、有限セット内のポインター参照のシーケンスは、サイクルのある時点で繰り返さなければなりません (そうでなければ、セットは有限ではありません)。もちろん、これには無限ループを停止する NULL が含まれる可能性があります。

0xcdcdcdcd を指す 0xcdcdcdcd のような、OS メモリ マネージャーによって予約された不良メモリ パターンにヒットしている可能性が高くなります。その場合、それは悪い選択です。デフォルトのメモリ パターンは、ポインターに表示された場合に不良メモリ例外が発生する可能性が高いように設計する必要があります。

デバッガーでプログラムを停止して、ポインター値が何であるかを教えていただければ、質問のその部分に答えることができます。

于 2012-01-28T11:52:11.610 に答える