Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Абстрактный тип данных

Ответить
Настройки темы
C/C++ - Абстрактный тип данных

Новый участник


Сообщения: 12
Благодарности: 0

Профиль | Отправить PM | Цитировать


Доброго времени суток! Помогите, пожалуйста, с заданием:
Создать список произвольной организации. Областью данных каждого элемента является строка, содержащая название геометрической фигуры, и площадь этой фигуры. Отсортировать все элементы списка в порядке убывания по названиям фигур (длиной строки) и затем в порядке возрастания по величине занимаемой площади (имеется в виду одноименные фигуры).

P.S. или дайте другие примеры программ, организованных по принципу "FIFO" или "LIFO"...

Отправлено: 06:13, 08-11-2013

 

Ветеран


Сообщения: 1404
Благодарности: 135

Профиль | Отправить PM | Цитировать


Список должен быть организован по принципу FIFO / LIFO ? Это является обязательным условием? Какое отношение FIFO / LIFO имеет к заданию, которое перед этим?
Структурой, организуемой по принципу FIFO / LIFO, является очередь.
FIFO (first in first out) - первый вошел, первый вышел (дек)
LIFO (last in first out) - последним вошел, первым вышел (стек)
Под списком понимается отличная от очереди организация данных.
Если данные организованы как стек, то использование стека предполагает, что без выталкивания доступ к элементам нельзя получить. С деком аналогично. По списку же возможно итерирование без выталкивания.
То есть у меня внутри противоречие между двумя разными способами решения задачи, причем противоречащими друг другую.
Основными АТД являются список (двусвязный, односвязный) (англ linked list), очередь (англ. queue), стек (англ stack), дек (англ. deck). Данные структуры реализованы в STL. Должна ли задача быть решена с использованием готовых АТД из STL или необходимо эти структура реализовать по заданию для учебных целей?

-------
Ehhh.. what's up, doc?..

Это сообщение посчитали полезным следующие участники:

Отправлено: 16:15, 08-11-2013 | #2



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

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


Новый участник


Сообщения: 12
Благодарности: 0

Профиль | Отправить PM | Цитировать


mrcnn, извиняюсь, я понял, что сортировать их бессмысленно, если соблюдается правило фифо(лифо)... помогите сделать, судя по названию, список произвольной организации.

Последний раз редактировалось p1ka4y777, 09-11-2013 в 04:38.


Отправлено: 02:40, 09-11-2013 | #3

pva pva вне форума

Аватара для pva

Ветеран


Сообщения: 1180
Благодарности: 279

Профиль | Отправить PM | Цитировать


p1ka4y777, вопрос в алгоритме или его кодировании? если понятен алгоритм - опиши алгоритм.

Отправлено: 20:38, 09-11-2013 | #4


Новый участник


Сообщения: 12
Благодарности: 0

Профиль | Отправить PM | Цитировать


pva, сначала опишите, пожалуйста, алгоритм и тогда я попробую скинуть свои наработки.

Отправлено: 05:28, 10-11-2013 | #5


Ветеран


Сообщения: 1404
Благодарности: 135

Профиль | Отправить 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;
}

-------
Ehhh.. what's up, doc?..


Отправлено: 09:41, 10-11-2013 | #6

pva pva вне форума

Аватара для pva

Ветеран


Сообщения: 1180
Благодарности: 279

Профиль | Отправить PM | Цитировать


Цитата 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";
	}
}
Это сообщение посчитали полезным следующие участники:

Отправлено: 13:08, 10-11-2013 | #7


Новый участник


Сообщения: 12
Благодарности: 0

Профиль | Отправить PM | Цитировать


Ой спасибо Вам, думал что никто уже не ответит... увы... ошибся я
в первом примере поиск идёт по "ключам"(by_area, figure_by_name) и быстрее... как бы на прямую
а во втором элементы списка хранятся последовательно, в том порядке, в котором мы их добавляем и к ним можно обращаться по индексу, если не ошибаюсь...

Отправлено: 02:11, 20-11-2013 | #8

pva pva вне форума

Аватара для pva

Ветеран


Сообщения: 1180
Благодарности: 279

Профиль | Отправить PM | Цитировать


По индексу нельзя обратиться, т.к. list - это 2-связный список (а не массив).
В первом случае сортировка происходит по мере получения данных. Т.е. при получении последней строчки мы имеем сортированные данные. Здесь демонстрация хитрой особенности контейнера map.
Во втором сначала накапливаем данные, затем сортируем их.
Какой из них лучше/быстрее - спорный вопрос.

хочу обратить внимание на пользу правильно названных типов/переменных. Человек, впервые видя код чужим почерком, не особенно владея контейнерами, почти правильно ответил на вопрос. Призываю правильно называть переменные (в боевых условиях)!
Это сообщение посчитали полезным следующие участники:

Отправлено: 15:52, 21-11-2013 | #9



Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Абстрактный тип данных

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
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




 
Переход