Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Динамический список!!!


Автор: kleks 16.11.2005, 18:44
Имеется дин. список элементами которого являются произвольные слова.
Надо: вывести на экран все слова, имеющие анаграммы. Слово
группируется вместе со своими анаграммами в одну строку. Слова
отделяются запятыми. Повторные анаграммы игнорируются.

Пример:

Список:
aбв
бббаб
аба
баа
авбг
ваа
баа
авб

Вывод:
абв,авб
аба,баа

Подскажите пожалуйста, как это можно организовать?! smile smile Заранее благодарен!!!

Автор: AISIN 16.11.2005, 19:02
а что именно не получается? Берешь одно слово из списка, делаешь его проверку если подходит то запоминаешь его адрес. Берешь другое слово проверяешь его, проверяешь на совподение со словами с уже выбранными адресами и т.д.

Автор: Mayk 16.11.2005, 19:12
Думаю имеется в виду оптимизация решения.


Можно так -
из оставшихся слов сделать пары слов, где
один элемент пары first - исходное слово,
второй second - отстортированное по алфавиту:

(aбв, абв)
(бббаб, абббб)
(аба, ааб)
(баа, ааб)
(авбг, абвг)
(ваа, аав)
(баа, ааб)
(авб, абв)


Потом сортируешь список по алфавиту по отсотрированным словам:
(аба, ааб)
(баа, ааб)
(баа, ааб)
(ваа, аав)
(бббаб, абббб)
(aбв, абв)
(авб, абв)
(авбг, абвг)



Потом пробегаешь по списку. И если node->second == node->next->second, то у нас анаграмма
Не думаю что это самое быстрое решение, но оно ОЧЕНЬ простое.

Автор: kleks 17.11.2005, 19:44
Спасибо ОГРОМНОЕ!!! Действительно это самое простое, что можно было придумать!!!! Но тут у меня возникла новая проблемка(относящаяся к данной задачке): у меня имеется список, элементом которого является first - исходное слово, а second - его анаграмма, так вот, я в этом списке хочу удалить повторы...я написал функцию удаления (всё проверил вроде без ошибок), но почему-то вместо того что бы удалять заданный элемент списка (вместе с освобождением памяти) он на его месте пишет такие вот чёрточки: |||||||||
Вот данные функци (поиск эл-та в списке, предыдущий эл-т в списке, удаление эл-та):
Код

// Функция поиска элемента в списке
CData * CList::FindData(char *a,char *b)
{
  // Указатель на очередные данные в списке.
    CData * pCurr = m_pFirst;
    // Если список пуст, возвращаем  NULL.
    if(pCurr == NULL)
    {
        return NULL;
    }
    // Обходим все элементы списка.
    do{
        // Есле нашли искомый, то его и возвращаем.
        if((strlen(pCurr->a) == strlen(a)) && (strlen(pCurr->b)==strlen(b)) && ((strstr(pCurr->b,b) && strstr(pCurr->a,a))!=NULL))
        {
            return pCurr;
        }
        // Переводим pCurr на след. элемент в списке.
        // Если он равенí NULL, то заканчиваем.
    }while((pCurr = pCurr->m_pNext)!=NULL);

    // Если ничего не нашли, возвращаем NULL.
    return NULL;
}

//предыдущий эл-т в списке
CData * CList::GetPrev(CData *p)
{
    // Если предыдущего эл-та нет
   // то возвращаем  NULL.
    if(p==m_pFirst)
        return NULL;
    // Если предыдущий эл- есть.
    CData * pCurr = m_pFirst;
    do{
             if(pCurr->m_pNext==p){
            // возвращаем очередной эл-т.
            return pCurr;
        }
        // Переводим pCurr на следующий эл-т в списке.
    }while((pCurr = pCurr->m_pNext)!=NULL);
    return NULL;
}


//удаление эл-та из списка

bool CList::RemoveData(char *a, char *b)
{
   // Если список пуст
    if(IsEmpty())
        // то выходим.
        return false;
    // Получаем эл-т для удаления.
    CData * pData = FindData(a,b);
    // Если его нет
    if(pData == NULL)
        // то выходим.
        return false;
    // если этот эл-т первый в списке.
    if(pData == m_pFirst){
        // Делаем первым следующий за ним эл-т.
        m_pFirst = pData->m_pNext;
        // Освобождаем память.
        delete pData;
        //И выходим.
        return true;
    }
    // Если удаляемый эл-т не первый
    // То делаем так чтобы эл-т перед ним
    // Показывал на эл-т за ним.
    GetPrev(pData)->m_pNext = pData->m_pNext;
    // Освобождаем память.
    delete pData;
    // И выходим.
    return true;
}


В основной программе я например исп. эту функцию так:
Код

...........
...........
list.RemoveData("abc","bca")


В чём проблема объясните пожалуйста?!! Я никак не могу понять... smile

Автор: Mayk 17.11.2005, 19:59
Прошу прощения, а зачем все эти телодвижения, next, prev'ы?
Ведь есть std::list и std::sort и прочие радости(например std::list::unique smile) Будьте проще, господа. Ну или дебагер в руки и вперед smile

С первого взгляда вроде удаление корректно. Хотя хз, я только с универа - плохо соображаю.
Мож ты в деструкторе что страшное творишь?

Цитата(kleks @ 17.11.2005, 23:44)

if((strlen(pCurr->a) == strlen(a)) && (strlen(pCurr->b)==strlen(b)) && ((strstr(pCurr->b,b) && strstr(pCurr->a,a))!=NULL))


эээ. А это что такое? strcmp не пойдет?

Автор: kleks 17.11.2005, 20:17
Вот ведь блин, действительно, в деструкторе напутал!!!! Спасибо!!!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)