c++ - 排序 char* 数组

Question

我有一个数据结构

struct record {
    char cont[bufferSize];
    record *next;
};

当我向这个结构添加新记录时，我希望它们按字母顺序排序。我做了这个函数，在链表的正确位置(按字母)添加记录:

record *start=NULL, *p, *x;

void recAdd(char*temp) {
        p = new record;
        temp[strlen(temp)] = '\0';
        for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j];
        if (start==NULL) start=p;
        else {
            x=start;
            int c=0;
            while (recComp(x->cont,p->cont) <= 0 && x->next != NULL) {
                    x=x->next;
                    c++;
            }
            if (c == 0) {
                p->next=start;
                start=p;
            }
            else {
                x=start;
                for (int i=0;i<c;i++) x=x->next;
                p->next=x->next;
                x->next=p;
            }
        }
        for (int j=0;j<bufferSize;j++) temp[j] = NULL;
    };

但不知何故，它无法正确排序。我的功能有什么问题？

Answer 1

你的代码一团糟。在语义和逻辑上都存在许多问题，但从根本上说，决定在何处插入新节点的逻辑是最有缺陷的。将其更改为(注意我在 else block 中的新代码):

void recAdd(const char*t) {
        char temp[bufferSize];
        strcpy(temp, t);
        p = new record;
        temp[strlen(temp)] = '\0';
        for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j];
        if (start==NULL) { start=p; start->next = 0; }
        else {
            record* x = start;
            record* prev = 0;
            while( x && recComp(x->cont, p->cont) <= 0 )
            {
                prev = x;
                x = x->next;
            }

            // p is a new node. p, x and prev are arranged thusly:
            // prev -> p -> x
            // if prev is null, p is a new head
            // if x is null, p is a new tail
            // otherwise, p is inserted between prev and x

            if( !prev )
            {
                p->next = start;
                start = p;
            }
            else if( !x )   
            // note this block and the next one could be combined.  
            // done this way for clarity.
            {
                prev->next = p;
                p->next = 0;
            }
            else
            {
                p->next = x;
                prev->next = p;
            }
        }
        for (int j=0;j<bufferSize;j++) temp[j] = NULL;
    };

但是您在编写这段代码时遇到了很多困难，以至于您会寻求 SO 的帮助来修复它，这一事实说明了一个重要的观点:最好的代码是您永远不必编写的代码。您已经编写了链表类型结构(可能是最简单的结构)和排序算法。两者都有缺陷，并且都具有作为标准 C++ 库的一部分的有效、经过测试和高效的版本。你应该使用它们。使用字符串而不是 char*s。使用 vector 而不是链表。使用 sort 而不是您的手动排序算法。综上所述，您的所有代码都可以替换为:

vector<string> records;

// this for block just populates the vector with random strings
for( int i = 0; i < 10; ++i )
{
    string s;
    for( int j = 0, jx = 3+(rand()/(RAND_MAX/10)); j < jx; ++j )
        s += 'A'-1+(rand()/(RAND_MAX/26));
    cout << s << endl;
    records.push_back(s);
}

sort(records.begin(), records.end());
copy( records.begin(), records.end(), ostream_iterator<string>(cout, " "));

当您可以使用已经有效的工具并做您想做的事时，为什么还要手工制作一堆东西并将自己暴露在无数缺陷中？