0

我有一个名为 StringList 的类，它具有多个管理和操作字符串链接列表的函数。我有一个 AddtoTop，它添加到列表的顶部，AddtoBottom，一个名为 add 的函数，它添加一个字符串但按字母顺序放置它，一个 clear 函数，一个 find 函数，一个 print 和一个 remove 函数。我已经编写了每一个函数，但是我有一个主要问题。当我使用“AddtoTop”和“AddtoBottom”时，我将一个字符串添加到链接列表中。当我要求删除仅使用这两个函数放置的字符串时，我的删除函数起作用。当我尝试删除使用“添加”功能添加的单词时，我的程序崩溃了。函数“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);

调整结束指针为空，您可能会写：

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

您的add()代码不能确保维护这些不变量。你也面临一个问题；如果列表由维护addToTop()或addToBottom()随后使用add()将无法可靠地工作，因为不能保证列表按排序顺序。

此外，正如我在对您之前的问题的回答中所展示的（但没有具体讨论），您应该真正传递字符串 asconst string &s而不是使用string s. 一般来说，它对代码的效率有很大的影响。

于 2013-07-15T05:15:40.607 回答
0

尝试这样的事情：

void StringList::add(string s) //adds and places in alphabetical order
{
    if(pTop)
    {
        StringListNode *iter = pTop;
        while (iter && s > iter->data)
            iter = iter->pNext;

        if (iter)
        {
            // insert before
            StringListNode *A=new StringListNode;
            A->data = s;
            A->pNext = iter;
            A->pPrev = iter->pPrev;
            if (iter->pPrev)
                iter->pPrev->pNext = A;
            else
                pTop = A;
            iter->pPrev = A;
            return;
        }
    }

    // add to bottom
    addToBottom(s);
}

请注意，您最好使用std::set(or std::multiset) 而不是滚动您自己的列表代码，因为这将使字符串自动排序，并且查找和随机插入通常是对数时间而不是线性时间。

于 2013-07-14T23:30:42.497 回答