|
Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Абстрактный тип данных |
|
C/C++ - Абстрактный тип данных
|
Новый участник Сообщения: 12 |
Доброго времени суток! Помогите, пожалуйста, с заданием:
Создать список произвольной организации. Областью данных каждого элемента является строка, содержащая название геометрической фигуры, и площадь этой фигуры. Отсортировать все элементы списка в порядке убывания по названиям фигур (длиной строки) и затем в порядке возрастания по величине занимаемой площади (имеется в виду одноименные фигуры). P.S. или дайте другие примеры программ, организованных по принципу "FIFO" или "LIFO"... |
|
Отправлено: 06:13, 08-11-2013 |
Ветеран Сообщения: 1404
|
Профиль | Отправить PM | Цитировать Список должен быть организован по принципу FIFO / LIFO ? Это является обязательным условием? Какое отношение FIFO / LIFO имеет к заданию, которое перед этим?
Структурой, организуемой по принципу FIFO / LIFO, является очередь. FIFO (first in first out) - первый вошел, первый вышел (дек) LIFO (last in first out) - последним вошел, первым вышел (стек) Под списком понимается отличная от очереди организация данных. Если данные организованы как стек, то использование стека предполагает, что без выталкивания доступ к элементам нельзя получить. С деком аналогично. По списку же возможно итерирование без выталкивания. То есть у меня внутри противоречие между двумя разными способами решения задачи, причем противоречащими друг другую. Основными АТД являются список (двусвязный, односвязный) (англ linked list), очередь (англ. queue), стек (англ stack), дек (англ. deck). Данные структуры реализованы в STL. Должна ли задача быть решена с использованием готовых АТД из STL или необходимо эти структура реализовать по заданию для учебных целей? |
------- Отправлено: 16:15, 08-11-2013 | #2 |
Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети. Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля. |
Новый участник Сообщения: 12
|
Профиль | Отправить PM | Цитировать mrcnn, извиняюсь, я понял, что сортировать их бессмысленно, если соблюдается правило фифо(лифо)... помогите сделать, судя по названию, список произвольной организации.
|
Последний раз редактировалось p1ka4y777, 09-11-2013 в 04:38. Отправлено: 02:40, 09-11-2013 | #3 |
![]() Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать p1ka4y777, вопрос в алгоритме или его кодировании? если понятен алгоритм - опиши алгоритм.
|
Отправлено: 20:38, 09-11-2013 | #4 |
Новый участник Сообщения: 12
|
Профиль | Отправить PM | Цитировать pva, сначала опишите, пожалуйста, алгоритм и тогда я попробую скинуть свои наработки.
|
|
Отправлено: 05:28, 10-11-2013 | #5 |
Ветеран Сообщения: 1404
|
Профиль | Отправить PM | Цитировать Я уже делал эту задачу, но внезапно у меня исчезает способность сделать задачу.
Ищите в поиске по запросу "сортировка односвязного списка" или по запросу "сортировка двусвзяного списка". Наработка #include <stdio.h> template<class T> class list { public: list<T>* next; T* e; list() { this->next = NULL; this->e = new e; } list(int a) { this->next = NULL; this->e = new e; (this->e)->a = a; } void add_next() { list<T>* iterator; iterator = this; while (iterator->next != NULL) { iterator = iterator->next; } iterator->next = new list<T> ; } void add_next(int a) { list<T>* iterator; iterator = this; while (iterator->next != NULL) { iterator = iterator->next; } iterator->next = new list<T> (a) ; } void print_list() { list<T>* iterator; iterator = this; while (iterator != NULL) { printf("%x %d\n", iterator, (iterator->e)->a); iterator = iterator->next; } } // сортировка по e.a (пузырьковая сортировка) void sort_list() { list<T>* iterator; list<T>* iterator1; list<T>* iterator2; list<T>* iterator3; list<T>* iterator4; list<T>* temp; list<T>* iterator5; iterator = this; iterator2 = NULL; while (iterator != NULL) { iterator1 = iterator->next; iterator4 = iterator; // iterator4 - это то, что указывает на iterator1 iterator5 = iterator->next; // iterator5 - это то, на что указывает iterator while ( iterator1 != NULL ) { iterator3 = iterator1->next; if ( (iterator1->e)->a > (iterator->e)->a) //сравнение для сортировки { // данные шаблонного класса не должны трогаться (так как объект может быть очень крупным по размеру) // кто указывает на iterator (iterator2) // кто указывает на iterator должен указывать на iterator1 // if (iterator2 != NULL) { iterator2->next = iterator1; } else { // //? // я попал в тупик } // если iterator указывает на iterator1; if (iterator-> next == iterator1) { iterator1->next = iterator; iterator->next = iterator3; } else { iterator1->next = iterator5; iterator->next = iterator3; iterator4->next = iterator; } } // end if iterator4 = iterator1; iterator1 = iterator1->next; } // end while ( iterator1 != NULL) iterator2 = iterator; iterator = iterator->next; } // end while (iterator != NULL ) } // end sort_list() }; // наследование от list не нужно для atd. , class atd { public: int a; void print_class() { printf("%d\n", a); } }; int main() { // один элемент списка list <atd> t; //t.a = 5; (t.e)->a = 5; (t.e)->print_class(); t.add_next(); ((t.next)->e)->a = 6; ((t.next)->e)->print_class(); printf("\n"); t.print_list(); printf("\n"); t.add_next(7); t.print_list(); //t.sort_list(); printf("\n"); t.add_next(8); t.print_list(); printf("\n"); t.sort_list(); t.print_list(); return 0; } |
------- Отправлено: 09:41, 10-11-2013 | #6 |
![]() Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать Цитата p1ka4y777:
Возможны два разных подхода: (у тебя есть шанс реабилитироваться, если ты расскажешь, какой принцип заложен в каждый из них) #include <iostream> #include <iomanip> #include <string> #include <map> using namespace std; int main() { typedef map<long, bool> by_area; typedef map<string, by_area> figure_by_name; figure_by_name database; string name; long size; while(cin >> name >> size) { database[name][size]; } for(figure_by_name::iterator fig=database.begin(), efig=database.end(); fig!=efig; ) { --efig; cout << efig->first << ":\n"; for(by_area::iterator area=efig->second.begin(), earea=efig->second.end(); area!=earea; ++area) { cout << " " << area->first << "\n"; } } } #include <iostream> #include <iomanip> #include <string> #include <list> using namespace std; typedef pair<string,long> data_type; typedef list<data_type> figure_list; inline bool figure_order(data_type const &a, data_type const &b) { return a.first > b.first || (a.first == b.first && a.second < b.second); } int main() { figure_list figures; data_type sample; while(cin >> sample.first >> sample.second) { figures.push_back(sample); } figures.sort(figure_order); for(figure_list::iterator fig=figures.begin(), efig=figures.end(); fig!=efig; ++fig) { cout << fig->first << ": " << fig->second << "\n"; } } |
|
Отправлено: 13:08, 10-11-2013 | #7 |
Новый участник Сообщения: 12
|
Профиль | Отправить PM | Цитировать Ой спасибо Вам, думал что никто уже не ответит... увы... ошибся я
в первом примере поиск идёт по "ключам"(by_area, figure_by_name) и быстрее... как бы на прямую а во втором элементы списка хранятся последовательно, в том порядке, в котором мы их добавляем и к ним можно обращаться по индексу, если не ошибаюсь... |
Отправлено: 02:11, 20-11-2013 | #8 |
![]() Ветеран Сообщения: 1180
|
Профиль | Отправить PM | Цитировать По индексу нельзя обратиться, т.к. list - это 2-связный список (а не массив).
В первом случае сортировка происходит по мере получения данных. Т.е. при получении последней строчки мы имеем сортированные данные. Здесь демонстрация хитрой особенности контейнера map. Во втором сначала накапливаем данные, затем сортируем их. Какой из них лучше/быстрее - спорный вопрос. хочу обратить внимание на пользу правильно названных типов/переменных. Человек, впервые видя код чужим почерком, не особенно владея контейнерами, почти правильно ответил на вопрос. Призываю правильно называть переменные (в боевых условиях)! |
Отправлено: 15:52, 21-11-2013 | #9 |
![]() |
Участник сейчас на форуме |
![]() |
Участник вне форума |
![]() |
Автор темы |
![]() |
Сообщение прикреплено |
| |||||
Название темы | Автор | Информация о форуме | Ответов | Последнее сообщение | |
C/C++ - [решено] Абстрактный шаблон | crashtuak | Программирование и базы данных | 2 | 25-01-2013 21:56 | |
Разное - Паскаль (множествненый тип данных) | sanazak | Тест-форум | 1 | 30-12-2011 18:19 | |
Разное - Паскаль!Проектирование БД.Используя файловый тип данных, создать файл записей | ___Vampir___ | Программирование и базы данных | 1 | 09-05-2011 23:25 | |
export-reg2inf (как узнать тип данных в реестре) | semiono | AutoIt | 1 | 31-12-2009 00:34 | |
C/C++ - Как правильно задать тип данных в массиве | ShadowMas | Программирование и базы данных | 4 | 18-04-2009 22:26 |
|