0

我的数据结构类的任务是实现一个创建单词的链表版本。该类称为 WORD，是字符的链表。所需的操作之一是从另一个单词中删除一个单词。例如，

WORD t1("testing");
WORD t2("es");

t1.Remove(t2);

cout<<t1; //Outputs tting

和

WORD t1("testing");
WORD t2("t");
t1.RemoveAll(t2);
cout<<t1; //Outputs esing

这两者的代码如下：

//Deletes an entire word from the list
//boolean passed to delete first occurrence of that word
//or all occurrences

void WORD::Delete(WORD & B, bool deleteAll)
{
    alpha_numeric *next, *last_word_start, *prev, *currB;

    bool found = false;
    next = last_word_start = prev = this->head;
    currB = B.head;

    while(next != NULL)
    {
        if(next->symbol == currB->symbol)
        {
            next = next->next;
            currB = currB->next;
        }
        else
        {
            prev = last_word_start;
            last_word_start = last_word_start->next;
            next = last_word_start;
            currB = B.head;
        }

        if(currB == NULL)
        {
            prev->next = next;

            while(last_word_start != next)
            {
                if(last_word_start == this->head)
                {
                    this->head = last_word_start->next;
                }
                alpha_numeric *temp = last_word_start->next;
                delete last_word_start;
                last_word_start = temp;
            }

            if(!deleteAll)
                break;

            currB = B.head;
        }
    }
}

所以我的问题是：

  1. 这个函数的运行时间是多少？我相信最坏的情况是 O(n^2)

  2. 我能做些什么来提高效率？

我开始学习优化等。尝试优化时的思考过程是什么？主要是试图将其降低到 nlog(n)。

4

0 回答 0