Абстрактный тип данных
Доброго времени суток! Помогите, пожалуйста, с заданием:
Создать список произвольной организации. Областью данных каждого элемента является строка, содержащая название геометрической фигуры, и площадь этой фигуры. Отсортировать все элементы списка в порядке убывания по названиям фигур (длиной строки) и затем в порядке возрастания по величине занимаемой площади (имеется в виду одноименные фигуры).
P.S. или дайте другие примеры программ, организованных по принципу "FIFO" или "LIFO"...
|
Список должен быть организован по принципу FIFO / LIFO ? Это является обязательным условием? Какое отношение FIFO / LIFO имеет к заданию, которое перед этим?
Структурой, организуемой по принципу FIFO / LIFO, является очередь.
FIFO (first in first out) - первый вошел, первый вышел (дек)
LIFO (last in first out) - последним вошел, первым вышел (стек)
Под списком понимается отличная от очереди организация данных.
Если данные организованы как стек, то использование стека предполагает, что без выталкивания доступ к элементам нельзя получить. С деком аналогично. По списку же возможно итерирование без выталкивания.
То есть у меня внутри противоречие между двумя разными способами решения задачи, причем противоречащими друг другую.
Основными АТД являются список (двусвязный, односвязный) (англ linked list), очередь (англ. queue), стек (англ stack), дек (англ. deck). Данные структуры реализованы в STL. Должна ли задача быть решена с использованием готовых АТД из STL или необходимо эти структура реализовать по заданию для учебных целей?
|
mrcnn, извиняюсь, я понял, что сортировать их бессмысленно, если соблюдается правило фифо(лифо)... помогите сделать, судя по названию, список произвольной организации.
|
p1ka4y777, вопрос в алгоритме или его кодировании? если понятен алгоритм - опиши алгоритм.
|
pva, сначала опишите, пожалуйста, алгоритм и тогда я попробую скинуть свои наработки.
|
Я уже делал эту задачу, но внезапно у меня исчезает способность сделать задачу.
Ищите в поиске по запросу "сортировка односвязного списка" или по запросу "сортировка двусвзяного списка".
Наработка
Код:
#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;
}
|
Цитата:
Цитата p1ka4y777
сначала опишите, пожалуйста, алгоритм и тогда я попробую скинуть свои наработки. »
|
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";
}
}
|
Ой спасибо Вам, думал что никто уже не ответит... увы... ошибся я
в первом примере поиск идёт по "ключам"(by_area, figure_by_name) и быстрее... как бы на прямую
а во втором элементы списка хранятся последовательно, в том порядке, в котором мы их добавляем и к ним можно обращаться по индексу, если не ошибаюсь...
|
По индексу нельзя обратиться, т.к. list - это 2-связный список (а не массив).
В первом случае сортировка происходит по мере получения данных. Т.е. при получении последней строчки мы имеем сортированные данные. Здесь демонстрация хитрой особенности контейнера map.
Во втором сначала накапливаем данные, затем сортируем их.
Какой из них лучше/быстрее - спорный вопрос.
хочу обратить внимание на пользу правильно названных типов/переменных. Человек, впервые видя код чужим почерком, не особенно владея контейнерами, почти правильно ответил на вопрос. Призываю правильно называть переменные (в боевых условиях)!
|
Время: 14:09.
© OSzone.net 2001-
