如何改进链表搜索.C++

Question

我在C++中有一个简单的方法,它在链表中搜索字符串.这很好但我需要让它更快.可能吗？也许我需要按字母顺序将项目插入列表？但我不认为它可能会有助于列表清单.在列表中有大约30万个项目(单词).

int GetItemPosition(const char* stringToFind)
{
    int i = 0;
    MyList* Tmp = FistListItem;
    while (Tmp){
        if (!strcmp(Tmp->Value, stringToFind))
        {
            return i;
        }
        Tmp = Tmp->NextItem;
        i++;
    }
    return -1;
}

如果找到项,则返回位置编号,否则返回-1.任何sugesstion将是有帮助的.

谢谢你的回答,我可以改变结构.我只有一个约束.代码必须实现以下接口:

int Count(void);
int AddItem(const char* StringValue, int WordOccurrence);
int GetItemPosition(const char* StringValue);
char* GetString(int Index);
int GetOccurrenceNum(int Index);
void SetInteger(int Index, int WordOccurrence);

那么哪种结构在您看来最合适？

Answer 1

搜索链表是线性的,因此您需要逐个迭代,因此它是O(n).链接列表不是最好的,如果你将它用于搜索,你可以使用更合适的数据结构,如二叉树.

订购元素没有多大帮助,因为仍然需要迭代每个元素.

维基百科的文章说:

在无序列表中,一个用于减少平均搜索时间的简单启发式算法是移动到前端的启发式算法,它只需将元素移动到列表的开头即可.此方案可以方便地创建简单的缓存,确保最近使用的项目也是最快查找的.

另一种常见方法是使用更有效的外部数据结构"索引"链表.例如,可以构建一个红黑树或哈希表,其元素是对链表节点的引用.可以在单个列表上构建多个这样的索引.缺点是每次添加或删除节点时(或者至少在再次使用该索引之前)可能需要更新这些索引.

因此,在第一种情况下,您可以通过移动先前更接近列表开头的项目来略微改进(通过统计假设)您的搜索性能.这假设将更频繁地搜索先前找到的元素.

第二种方法需要使用其他数据结构.

如果使用链表不是一项硬性要求,请考虑使用哈希表,排序数组(随机访问)或平衡树.