сортировка 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):

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. Используйте векторы вместо вашего связанного списка. Используйте 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, " "));

Зачем рулонить кучу вещей и подвергать себя многочисленным дефектам, когда вы можете использовать инструменты, которые уже работают и делают то, что вы хотите?

Answer 2

Возможно, я не отвечаю на ваш вопрос, но почему вы не используете STL? Это сделает сортировку для вас; Вы не должны писать такие процедуры сортировки в эти дни.

Answer 3

Как уже говорили другие, STL делает жизнь намного проще. Кажется, все, что вам нужно, это отсортированный контейнер строк:

#include <iostream>
#include <set>
#include <string>

int main()
{
    std::set<std::string> words;
    words.insert("hello");
    words.insert("beautiful");
    words.insert("world");

    for (std::set<std::string>::const_iterator it = words.begin(); it != words.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
}

Answer 4

Вы можете существенно облегчить себе жизнь, если внедрите простую сортировку вставкой с использованием вектора STL (вектор имеет член 'вставка').

этот код тоже будет выглядеть чище:)

посмотрите на cplusplus.com примеры там, вы найдете это полезным.

Answer 5

Несколько советов:

• используйте strcmp для сравнения строк
• предпочитаете использовать указатели для char внутри вашей структуры. Это позволяет вам слепо назначать их без копирования, и это не будет тратить место внутри вашего struct
• если вам действительно нужно скопировать их, используйте strdup для выделения новых строк
• следите за двумя текущими элементами вместо одного, это позволит избежать подсчета того, сколько вы получили, и дважды пройти список, когда вы нашли правильную позицию