Помогите пожалуйста! Структуры данных в Си

[NiGHTeR]

Такая ситуация, у нас очень плохой семинарист по информатике, поэтому все приходится делать самостоятельно. Есть задача:
"Написать структуру данных, итератор по ней и тест (три файла: алгоритм, файл заголовков, тест). Тест должен демонстрировать работоспособность структуры. Помните, что требуемых структур может быть много (более одного экземпляра)

Структура данных --- упорядоченный набор с введением функции отношения"

Во-первых, что это за тип данных? Набор, насколько я понимаю, это просто $n$ упорядоченных чисел, можете, пожалуйста, пояснить что такое функция отношения?

Во-вторых, что должна содержать структура? Просто описание данных (ввод и вывод) или еще должна реализовывать какие то алгоритмы?

В-третьих, что такое итератор и что должно(может) содержаться в тесте?

Буду очень благодарен за любую информацию по вопросам) сдача на этой неделе)

[wallflower]

Тип структуры это struct. Что такое итератор в Си -- я не знаю, но видимо вам просто надо их в цикле перебирать (в структуре должен быть указатель типа struct foo *next).

Тема у вас свободная. Главное показать, что структура "работает". Например, через бинарные деревья можете сделать почти практически полезную программу: берёт, скажем, "Войну и мир" и составляет словарь всех используемых слов (кроме предлогов) в алфавитном порядке.

[NiGHTeR]

А что именно будет делать этот указатель? И что именно в каком цикле мы должны перебирать?

[Munin]

По формулировке это больше похоже на упражнение по C++, STL и шаблонам, чем по Си. Например, "введение функции отношения" на это намекает.

[wallflower]

(Оффтоп)

Munin в сообщении #549415 писал(а):

Например, "введение функции отношения" на это намекает.

А что это такое? Интересно даже стало. А "упорядоченный набор с введением функции отношения" -- это типа определение структуры в стиле а-ля ГОСТ, что ли?.

[NiGHTeR]

Munin в сообщении #549415 писал(а):

По формулировке это больше похоже на упражнение по C++, STL и шаблонам, чем по Си. Например, "введение функции отношения" на это намекает.

Не, строго надо на Си, в задании специально на этом акцент поставили.

Все таки как понять "итератор по программе" и функцию отношения? Может это что то типа суммы/разности двух наборов?

[Munin]

(Оффтоп)

wallflower в сообщении #549427 писал(а):

А что это такое? Интересно даже стало.

Я так понял, что это означает, что тип, предназначенный для хранения в контейнере, удоветворяет STL концепциям LessThan Comparable и/или Strict Weakly Comparable.

NiGHTeR в сообщении #549447 писал(а):

Все таки как понять "итератор по программе"

Итератор не по программе. Итератор по структуре данных. Итератор - это такой объект, который "указывает" на какое-то место в структуре данных, и с ним можно делать операции: извлечь указываемый элемент, перевести итератор вперёд, перевести назад, выяснить, не дошёл ли итератор до конца или начала структуры данных. Например, для массива роль итератора выполняет указатель, но для других структур данных это может быть какой-то другой тип, и операции над ним должны быть совершенно другими. Это понятие естественно выглядит в C++ и других объектно-орентированных языках, где реализация итератора может быть инкапсулирована, но в Си это странно.

[Alexu007]

Может речь идёт о связанном списке? Там есть и данные и адреса, указывающие на элементы списка.

[NiGHTeR]

Munin в сообщении #549521 писал(а):

(Оффтоп)

wallflower в сообщении #549427 писал(а):

А что это такое? Интересно даже стало.

Я так понял, что это означает, что тип, предназначенный для хранения в контейнере, удоветворяет STL концепциям LessThan Comparable и/или Strict Weakly Comparable.

NiGHTeR в сообщении #549447 писал(а):

Все таки как понять "итератор по программе"

Итератор не по программе. Итератор по структуре данных. Итератор - это такой объект, который "указывает" на какое-то место в структуре данных, и с ним можно делать операции: извлечь указываемый элемент, перевести итератор вперёд, перевести назад, выяснить, не дошёл ли итератор до конца или начала структуры данных. Например, для массива роль итератора выполняет указатель, но для других структур данных это может быть какой-то другой тип, и операции над ним должны быть совершенно другими. Это понятие естественно выглядит в C++ и других объектно-орентированных языках, где реализация итератора может быть инкапсулирована, но в Си это странно.

А можете, пожалуйса, привести какой-нибудь пример кода, использующего простенькую структуру с итератором?

[Munin]

Повторяю, мне кажется, это гвоздь не от той стенки. Концепция итератора вообще почти бесполезна в Си. Я напишу, а вы спросите: а в чём разница с простым указателем на элемент структуры? А реализация операций сильно зависит от используемой структуры, в массивах она одна, в деревьях другая.

[NiGHTeR]

А что тогда конкретно в моей задаче стоит понимать под итератором?

Указатель на элемент списка который при увеличении будет указывать на следующий элемент?

[Munin]

Дело в том, что вашу задачу не обязательно реализовывать списком. Но если списком - то да, указатель на элемент списка.

[Alexu007]

Это кусок рабочей программы, иллюстрирующий работу со связанными списками, тут есть и структуры и адреса.

Используется синтаксис C++

//связанный список
class NDSet
  {
  public:
   NDSet* pPrev;
   NDSet* pNext;

   AnsiString Dig;
  //сюда можно поместить 
  //любые данные
  };

//указатель на первый элемент списка
//указатель на последний элемент списка
NDSet* pListBeg;
NDSet* pListEnd;


pListBeg = NULL;
pListEnd = NULL;


//---------------------------------------------------------------------------
// функция сортирует список при добавлении нового элемента

void funcSortList(void)
 {
 AnsiString X;

 //копируем в pListEnd1 адрес текущего элемента
 NDSet* pListEnd1 = pListEnd;

 //продолжаем до тех пор, пока адрес не равен 0
 while(pListEnd1)
  {
  //текущий элемент
  NDSet* pNDS = pListEnd1;

  //сортировка невозможна при единственном элементе
  if(pNDS->pPrev == NULL) return;

  //предыдущий элемент
  NDSet* pNDS1 = pNDS->pPrev;

  X = pNDS1->Dig;

  if(pNDS->Dig < X) {pNDS1->Dig = pNDS->Dig; pNDS->Dig = X;}

  pListEnd1 = pNDS->pPrev;
  }

 return;
 }

[Munin]

(Оффтоп)

Прекрасный пример, как делать не надо. Впрочем, с рабочими программами это часто случается, особенно старыми.

[Joker_vD]

(Оффтоп)

Munin
Особенно замечательно, что при сортировке не "ящики" переставляются, а их "содержимое" перекладывается. А итератора как не было, так и нет. Тихий ужас, в общем.