IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Бинарные деревья, С++
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


У меня есть динамическая структура данных: Студент (фамилия, имя, факультет, группа), реализованная с помошью бинарного дерева. Подскажите пожалуйста как мне сделать сортировку всей базы данных, например по фамилии...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата(Nike @ 21.12.2007 19:16) *

Подскажите пожалуйста как мне сделать сортировку всей базы данных, например по фамилии...

Ну вот посмотри например здесь про сортировку с помощью бинарного дерева. Там даже пример есть, правда на Java. Википедия

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Тёмный Эльф, понимаешь, сортировка-то с помощью бинарного дерева в принципе не нужна, дерево хранит информацию уже в отсортированном виде:
Цитата
в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.


Проблема вся в том, что автор не указал, что является ключом в том представлении, которое у него есть. Если добавляются данные в бинарное дерево, скажем, по ID студента, а отсортировать надо по фамилии, то проще всего будет построить новое дерево, с ключом - фамилией, и пройти по нему в симметричном порядке...

Nike, реализацию структуры можно посмотреть?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


struct node    
{
char //®Ўкпў«Ґ­ЁҐ гЄ § ⥫Ґ© ­ §­ 祭ЁҐ вЁЇ char
*surname, //д ¬Ё«Ёп бв㤥­в
*name, //Ё¬п бв㤥­в
*fac; //Ќ §ў ­ЁҐ д Єг«мвҐв
int number; //­®¬Ґа ЈагЇЇл бв㤥­в
node *down, //гЄ § вҐ«м ­ ­Ё¦­Ё© н«Ґ¬Ґ­в
*sosed; //гЄ § вҐ«м ­ б®бҐ¤­Ё© н«Ґ¬Ґ­в
};


volvo, так мне тогда проще все засунуть в новое дерево?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


volvo, да ты прав
Nike, кстати можешь прочитать "Алгоритмы и структуры данных" Никлауса Вирта. Там очень хорошо изложено про деревья в том числе и про бинарные. (с примерами на Паскале)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Nike, смотри...

Функция, добавляющая элемент в дерево, на Паскале выглядит так (X - добавляемый элемент):
procedure Insert(var Root: TTree; X: T);
begin
if Root = nil Then CreateNode(Root, X) { создаем новый узел дерева }
else
with Root^ do begin
if value < X then Insert(Right, X)
else
if value > X Then Insert(Left, X)
else
{ Действия, производимые в случае повторного
внесения элементов в дерево}
end;
end;

, на С тоже будет что-то очень похожее... Вот если сравнения if(value < X) и if(value > X) не делать непосредственно в теле функции, а определить вспомогательную функцию, которая будет возвращать -1, когда ключ добавляемого элемента меньше ключа текущего узла, и +1, если больше, и передавать эту функцию как параметр в Insert, то вполне реально одной функцией создавать деревья с любым ключом...

То есть, просто делаешь полный обход существующего у тебя дерева в любом порядке, и добавляешь информационную структуру каждого узла в новое дерево (но ключевым уже должно быть поле surname, т.е., в функцию Insert надо передавать параметр-функцию, сравнивающую значения именно этих полей). А по новому дереву - обход в симметричном порядке даст тебе отсортированную по фамилии базу...

Если хочешь - покажи свою функцию добавления записи в дерево, я покажу, как переделать функцию, чтобы можно было создавать деревья с любым полем в качестве ключа...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


Всем спасибо! Все понятно теперь smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 24.11.2020 14:29
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name