структуры специального вида на Си

[milla]

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

Код: Выделить всё

typedef struct BlockInt {
  int сnt;                 //cчетчик блока
  int cells[9];            // сам блок
  struct BlockInt *prev;    // указатель на предыдущий блок
  struct BlockInt *next;    // указатель на следующий блок

} BlockInt;

Как работать с подобной структурой?

[Qwertiy]

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

[Admiralisimys]

milla например так (некоторые проверки отсутствуют)

Код: Выделить всё

#include <tchar.h>
#include <memory.h>

typedef struct BlockInt {
  int idx;                 //индекс блока
  int cells[9];            // сам блок
  struct BlockInt *prev;    // указатель на предыдущий блок
  struct BlockInt *next;    // указатель на следующий блок

} BlockInt;

BlockInt *GetBlockByIDX(BlockInt *bi, int idx);

int _tmain(int argc, _TCHAR* argv[])
{
   BlockInt *bi = new BlockInt();
   memset(bi, 0, sizeof(BlockInt));

   for(int i = 1; i < 3; i++)
   {
      bi -> next = new BlockInt();
      memset(bi -> next, 0, sizeof(BlockInt));

      bi -> next -> prev = bi;
      bi = bi -> next;
      bi -> idx = i;
   }

   BlockInt *bi3 = GetBlockByIDX(bi, 2);

   _tprintf(_TEXT("Third block %s\n%i\n%x\n\%x\n"), bi3 -> cells, bi3 -> idx,
                                    bi -> next, bi -> prev);
   _tprintf(_TEXT("Seven element of third block %c\n"), bi3 -> cells[6]);

   return 0;
}

BlockInt *GetBlockByIDX(BlockInt *bi, int idx)
{
   if(bi -> idx > idx)
   {
      while(bi && bi->idx != idx)
         bi = bi -> prev;
   }
   else if (idx > bi -> idx)
   {
      while(bi && bi->idx != idx)
         bi = bi -> next;
   }
   return bi;
}

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

[milla]

Это лабораторная работа, соответственно все термины из задания. Вот само задание:
Написать программу, предоставляющую возможность ведения информационного массива данных заданной структуры. Для хранения информационного массива должна ис-пользоваться линейная структура данных специального вида (в соответствие с вариантом). Программа должна реализовывать следующие функции:
1. Добавление новой записи в начало списка
2. Добавление новой записи в конец списка
3. Вставка новой записи на заданную позицию
4. Удаление записи, находящейся на заданной позиции
5. Изменение записи, находящейся на заданной позиции
6. Очистка информационного массива
7. Последовательный поиск записи в информационном массиве
8. Вывод содержимого информационного массива на экран
9. Вывод служебных данных и текущей структуры используемой структуры хранения.
Вариант:
Структура записи информационно-го массива: Ключе-вое поле - float[3]
Информационные поля - int[], char[], float
Используемая линейная структура: Блоковый список (размер блока 9)

Пример объявления структуры в первом посте взят из теории к ЛР, я хотела понять как вообще это работает.
Если можно, подскажите, как изменить объявление структуры в соответствии с вариантом. Для реализации функций обработки элементов алгоритмы есть, я там сама соображу - мне главное понять как создать структуру заданного вида и и как к ней обращаться

[Хакер]

Так в чём непосредственно вопрос то заключается?

[milla]

Так в чём непосредственно вопрос то заключается?

как создать структуру заданного вида (согласно варианту) и как этой структурой пользоваться.

[Qwertiy]

Переформулируй, пока тему не закрыли.

[Qwertiy]

В приведённом коде idx - это ключ (и он ни как не связан с позицией), а cells - данные. Верно?

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

[milla]

В приведённом коде idx - это ключ (и он ни как не связан с позицией), а cells - данные. Верно?

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

Текст задания оригинальный, по поводу idx и cells - вы правы - это я напутала.
Что касается доверия - объявление структуры, приведенное мной здесь, получено методом проб и ошибок, потому что то, что написано в методичке, даже я сочла некорректным, так что опять вы правы.
Мне правда от этого не легче.....

Тему переформулировала.

[milla]

Проштудировала еще раз методичку, выяснила idx - это даже не ключевое поле, это счетчик заполнения блока(0-если блок пустой, 1 - если в блоке 1 элемент и т.д.)
Прошу прощения за свою невнимательность.

[Qwertiy]

Тему переформулировала.

Наоборот. То что было там, было нормально (лучше верни). Я имел в виду поменяй

как создать структуру заданного вида (согласно варианту) и как этой структурой пользоваться.

на что-нибу типа

Как работать с подобными структурами?

Проштудировала еще раз методичку, выяснила idx - это даже не ключевое поле, это счетчик заполнения блока(0-если блок пустой, 1 - если в блоке 1 элемент и т.д.)

Т. е. количество использованных элементов массива? Хоть n его назвать, или size, length, count... Ну индексом-то зачем?

Что в итоге ключевое поле, а что данные? И зачем вообще нужно ключевое поле? Связному списку от него ни жарко, ни холодно.
Или в том примере этого не было? По чему ведётся поиск? В твоём случае это должен быть массив из трёх float'ов?
Сколько информационных полей?
Гадость какая-то...

Для начала напиши задание по пунктам, как ты его понимаешь.

[Qwertiy]

И ещё. По-хорошему, должна быть ещё одна структура, содержащая указатели на первый и последний элемент. Хотя можно обойтись и без неё.
Хотя, при таких формулировках (особенно поиски и выбор по индексу), меня уже не удивит, если там про это ничего нету...
Что вообще означает фраза "на заданной позиции"? Может всё-таки "заданный элемент", а не индекс?

[milla]

вернула все назад, idx переименовала согласно его смыслу.

Что в итоге ключевое поле, а что данные? И зачем вообще нужно ключевое поле? Связному списку от него ни жарко, ни холодно.Или в том примере этого не было? По чему ведётся поиск? В твоём случае это должен быть массив из трёх float'ов?Сколько информационных полей?

вот если бы я на эти вопросы сама знала ответы, может и не пришлось бы совета здесь просить)
у меня были подозрения, что это глупость какая-то, но решила спросить у умных людей, как оказалось, это действительно так....
завтра отправлюсь искать правды по месту создания этой "гадости", может что прояснится.

Что вообще означает фраза "на заданной позиции"? Может всё-таки "заданный элемент", а не индекс?

думаю, что здесь имеется в виду такой вариант: "хочу вставить/изменить/удалить элемент, который находится в i-том блоке на j-той позиции", i, j и значение элемента задает пользователь.

[Qwertiy]

думаю, что здесь имеется в виду такой вариант: "хочу вставить/изменить/удалить элемент, который находится в i-том блоке на j-той позиции", i, j и значение элемента задает пользователь.

Ты понимаешь, что связный список не предназначен для эффективной работы с индексами? Т. е. чтобы найти элемент по индексу, нужно от первого элемента последовательно дойти до него. Ну или от последнего, если число элементов известно.

1. Добавление новой записи в начало списка
2. Добавление новой записи в конец списка
3. Вставка новой записи на заданную позицию
4. Удаление записи, находящейся на заданной позиции
5. Изменение записи, находящейся на заданной позиции
6. Очистка информационного массива
7. Последовательный поиск записи в информационном массиве
8. Вывод содержимого информационного массива на экран
9. Вывод служебных данных и текущей структуры используемой структуры хранения.

Давай так. Код пишу тут, могут быть ошибки. В случае с массивами шаблонность не пройдёт.

Есть элемент списка:

Код: Выделить всё

template <typename key_type, typename value_type>
struct item
  {
  key_type key;
  value_type value;
  item *prev, *next;
  }

Есть сам список

Код: Выделить всё

template <typename key_type, typename value_type>
struct list
  {
  item <key_type, value_type> first, last;
  }

Что с этим надо сделать:
0. Создать список. first = last = 0
1. Добавление в начало. Создать новый item, его next должен указывать на старый first, обновить first. Аккутатно обработать случай, когда список пуст.
2. Добавление в конец. Аналогично 1.
3. Добавление после текущего. Новому поставить задать предыдущий cur и следующий cur->next. На созданный элемент направить cur->next, и cur->next->prev. Осторожно обработать случаи, когда что-то не существует.
4. Удалить текущий. Собственно изменить ссылки cur->next->prev и cur->prev->next, чтобы пропустить cur. Уничтожить cur. Рекомендую возвращать указатель на следующий. Осторожно обработать случаи, когда что-то не существует.
5. Изменение текущей записи. Просто поменять значение.
6. Очистка. Уничтожить все элементы списка пройдя по нему. Присвоить first = last = 0, как при создании.
7. Поиск. Идти по списку, пока не найдёшь.
8. Вывод. Идти по списку до конца и что-то выводить.
9. ???

Чтобы это работало с индексом, надо в цикле дойти до нужного элемента.

[milla]

Ты понимаешь, что связный список не предназначен для эффективной работы с индексами? Т. е. чтобы найти элемент по индексу, нужно от первого элемента последовательно дойти до него. Ну или от последнего, если число элементов известно.

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

9. ???

Те же эмоции, пока не буду это трогать, надо со всем остальным разобраться.
Вот еще вопрос возник в голове, по заданию - а возможно, чтобы одна структура содержала информационные поля разных типов (как в варианте int, char и float)? В один блок напихать все подряд все таки нельзя, а вот блоки разных типов загнать в один список можно? Или тогда совсем абра-кадабра получится?

В любом случае, большое спасибо, Qwertiy

[Qwertiy]

Вот еще вопрос возник в голове, по заданию - а возможно, чтобы одна структура содержала информационные поля разных типов (как в варианте int, char и float)? В один блок напихать все подряд все таки нельзя, а вот блоки разных типов загнать в один список можно? Или тогда совсем абра-кадабра получится?

Ты сейчас куда-то не туда роешь. В любом случае, ответ да на все вопросы. Существует union, например. А ещё - void*. А вот как это разгребать потом - зависит только от того, как ты позаботишься сохранить информацию о том, что там лежит.

В один блок напихать все подряд все таки нельзя

Даже это можно

Скорее всего, надо просто сделать несколько полей в каждом элементе. Или для всех информационных полей сделать структуру, и уже её (или массив таких) пихать в элемент.

Не думаю, что задание рассчитано на использование union.

так же понимаю, что заново изобретать велосипед бессмысленно

А вот это не так
1. Научишься работать с указателями.
2. Поймёшь, как устроен связный список.
3. Можно сделать эффективнее, чем то, что есть. Эффективнее для конкретной задачи, естественно.

Мне когда-то было нужно что-то типа гибрида двумерного связного списка и бинарного дерева. Попробуй-ка найди такое. Правда, я его так и не написал (даже не начинал, кажется), и уже не помню, зачем оно мне было надо
Хотя нет, примерно представляю. Использование связных списков для реализации онлайн сжатия координат в дереве отрезков. Вот

[burik]

Что-то развели тут писанину.. Стандартнейшее учебное задание.
Как обычно сформировано общее задание - перечень операций, нужных для работы с некоторой абстрактной структурой данных (список пар ключ-значение), без учета конкретной реализации и дан вариант - конкретная структура.

Если считать, что это так:

Ты понимаешь, что связный список не предназначен для эффективной работы с индексами? Т. е. чтобы найти элемент по индексу, нужно от первого элемента последовательно дойти до него. Ну или от последнего, если число элементов известно.

Понимаю прекрасно, ...

то автор знает что такое двусвязный список и каким образом происходит работа с ним.

Но, вообще говоря, я бы задумался над этим

Используемая линейная структура: Блоковый список (размер блока 9)

По-моему автору следует либо внимательней почитать методичку, либо обратиться к преподавателю дабы точно уяснить что имеется ввиду под блоковым списком. Как можно понять (как понял я) из приведенного фрагмента кода, блоковый список - это двусвязный список, в котором каждый элемент содержит группу из 0..9 элементов (собственно хранимых элементов).
Если автору точно известно какая структура должна быть, то неясно что конкретно непонятно, если вопрос и заключается в том, как выглядит структура, то он довольно странно сформулирован.

В общем, хотелось бы увидеть какой-нибудь более конкретный вопрос.

[milla]

блоковый список - это двусвязный список, в котором каждый элемент содержит группу из 0..9 элементов (собственно хранимых элементов).

именно так

как такой структурой пользоваться, уже просветили, тут вопросов больше нет, осталось понять, что есть ключевое поле типа float[3], а что информационные поля типа int[], char[], float

[burik]

что есть ключевое поле типа float[3], а что информационные поля типа int[], char[], float

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

Код: Выделить всё

typedef struct StoredItem
{
    float key[3];
    int* intData;
    char* charData;
    float floatData;
} StoredItem;

[milla]

Burik, и вам спасибо большое, наконец-то до меня дошло, что и как надо делать))))

[Qwertiy]

int[] intData;

А вот такого не надо лучше...

[burik]

int[] intData;

А вот такого не надо лучше...

Ну да, что-то я ступил (копипаст - зло) Но автор вроде суть понял

[Qwertiy]

float[3] key;

Это тоже float key[3];

Но автор вроде суть понял

Я вроде тоже писал:

Скорее всего, надо просто сделать несколько полей в каждом элементе. Или для всех информационных полей сделать структуру, и уже её (или массив таких) пихать в элемент.

[empirik]

Скажи, а стандартной библиотекой шаблонов тебе можно пользоваться? Или все на чистом C