0

文字列のリンクリストを管理および操作する複数の関数を持つ StringList というクラスがあります。リストの先頭に追加する AddtoTop、AddtoBottom、文字列を追加するがアルファベット順に配置する add という関数、clear 関数、find 関数、print 関数、remove 関数があります。私はすべての関数を作成しましたが、主な問題が 1 つあります。「AddtoTop」と「AddtoBottom」を使用すると、リンクされたリストに文字列が追加されます。私の削除機能は、これらの 2 つの機能のみを使用して配置した文字列を削除するように依頼すると機能します。「add」機能で追加した単語を削除しようとすると、プログラムがクラッシュします。関数 "remove" (以下を参照) は、"AddtoBottom" および "AddtoTop" を使用して追加された文字列を削除できます。「add」を使用して追加された文字列ではなく、機能しますが、誰かが理由を理解するのを手伝ってくれますか? 別の方法で書き直そうとしていますが、行き詰まっています。ここに私の機能があります：

StringList::StringList() //constructor
{
    pTop=NULL;
    pBottom=NULL;
}

StringList::~StringList()  //destructor
{
    StringListNode *next;
    for (StringListNode *sp = pTop; sp != 0; sp = next)
    {
        next = sp->pNext;
        delete sp;
    }
}
void StringList::add(string s) //adds and places in alphabetical order
{
    if(pTop)
    {
      if( s < pTop->data )
        {
            StringListNode *A=new StringListNode;
            A->data = s;
            A->pNext = pTop;
            pTop = A;   // new top
            return;
        }
        // go further into list
        StringListNode *iter = pTop;
        while( iter->pNext )    
        {
            if(  iter->pNext->data < s )
                iter = iter->pNext;
            else
                break;
        }   
        StringListNode *in=new StringListNode;   //actuallly inserts node
        in->data = s;
        in->pNext = iter->pNext;
        iter->pNext = in;
    }
    else// new item 
    {
        pTop = new StringListNode;
        pTop->data = s;
        pTop->pNext = NULL;
    }
}

StringList::StringListNode *StringList::find(const string &s) //basic search function
{
    StringListNode *sp = pTop;   // Search
    while (sp != 0 && sp->data != s)
        sp = sp->pNext;
    return sp;
}

void StringList::addToTop(string s) //add to top of nodes
{
    if(isEmpty())
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        (*pNewNode).data = s;
        pTop=pNewNode;
        pBottom=pNewNode;
        (*pNewNode).pPrev = NULL;
        (*pNewNode).pNext = NULL;
    }
    else //it's not empty
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        (*pNewNode).data = s;
        (*pNewNode).pNext = pTop;
        (*pTop).pPrev = pNewNode;
        (*pNewNode).pPrev =NULL;
        pTop=pNewNode;
    }
}

void StringList::addToBottom(string s) // add to bottom
{
    if(isEmpty())
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        (*pNewNode).data = s;
        pTop=pNewNode;
        pBottom=pNewNode;
        (*pNewNode).pPrev = NULL;
        (*pNewNode).pNext = NULL;
    }
    else
    {
        StringListNode * pNewNode;
        pNewNode = new StringListNode;
        (*pNewNode).data = s;
        (*pBottom).pNext = pNewNode;
        (*pNewNode).pPrev =  pBottom;
        (*pNewNode).pNext =NULL;
        pBottom=pNewNode;
    }
}

string StringList::print() //prints strings in linked list
{
    string result;
    StringListNode * pCurrent;
    pCurrent=pTop;
    while(pCurrent!=NULL)
    {
        result+=(*pCurrent).data+"\n";
        pCurrent=(*pCurrent).pNext;
    }
    return result;
}

void StringList::clear()   //clears everything
{
    pTop = NULL;
    pBottom = NULL;
}

void StringList::remove(string s)  //removes a string
{
    StringListNode *curr = this->find(s);
    if (curr->pPrev != 0)
        curr->pPrev->pNext = curr->pNext;
    if (curr->pNext != 0)
        curr->pNext->pPrev = curr->pPrev;
    if (pTop == curr)
        pTop = curr->pNext;
    if (pBottom == curr)
        pBottom = curr->pPrev;
}
4

2 に答える 2

0

記述されたコードの主な問題は、ポインターadd()を設定しないことです(ただし、設定する必要があります)。pPrev「削除方法」の質問への回答で使用したものと同様の図を自分で描き、新しいノードを追加するときにどのような割り当てを行う必要があるかを確認してください。

「データ構造が健全であることを確認するにはどうすればよいか」についても検討する価値があります。たとえばcurr、リストの中央にある各ノードで、次のことをアサートできる必要があります。

assert(curr->pPrev->pNext == curr);
assert(curr->pNext->pPrev == curr);

エンド ポインターが null になるように調整すると、次のように記述できます。

assert(curr->pPrev == 0 || curr->pPrev->pNext == curr);
assert(curr->pNext == 0 || curr->pNext->pPrev == curr);

あなたのadd()コードは、これらの不変条件が維持されることを保証しません。あなたも問題に直面しています。addToTop()リストがまたはによって維持されている場合、リストがソートされた順序であることが保証されていないため、addToBottom()使用add()は確実に機能しません。

また、前の質問への回答で示したように (具体的には説明しませんでしたが)、文字列const string &sはstring s. 一般に、コードの効率に大きな影響を与えます。

于 2013-07-15T05:15:40.607 に答える