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

Вопросы по языкам программирования Си и С++.
milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 14:23

Добрый день! Помогите, пожалуйста, разобраться.
Есть структура вида
Код: Выделить всё
typedef struct BlockInt {
  int сnt;                 //cчетчик блока
  int cells[9];            // сам блок
  struct BlockInt *prev;    // указатель на предыдущий блок
  struct BlockInt *next;    // указатель на следующий блок

} BlockInt;

Как работать с подобной структурой?
Последний раз редактировалось milla 30.05.2012 (Ср) 21:49, всего редактировалось 3 раз(а).

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.05.2012 (Ср) 15:16

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

Admiralisimys
Постоялец
Постоялец
 
Сообщения: 318
Зарегистрирован: 01.06.2009 (Пн) 10:26

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

Сообщение Admiralisimys » 30.05.2012 (Ср) 16:41

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
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 16:48

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

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 30.05.2012 (Ср) 17:37

Так в чём непосредственно вопрос то заключается?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 18:07

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

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.05.2012 (Ср) 18:16

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.05.2012 (Ср) 18:20

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

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

milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 20:04

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

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


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

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

milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 20:39

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.05.2012 (Ср) 21:22

milla писал(а):Тему переформулировала.

Наоборот. То что было там, было нормально (лучше верни). Я имел в виду поменяй
milla писал(а):как создать структуру заданного вида (согласно варианту) и как этой структурой пользоваться.
на что-нибу типа
Как работать с подобными структурами?


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

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

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

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.05.2012 (Ср) 21:48

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

milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 22:06

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

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

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.05.2012 (Ср) 22:39

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

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

milla писал(а):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
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 30.05.2012 (Ср) 23:50

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

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

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

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 31.05.2012 (Чт) 0:18

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

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

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

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

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

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

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

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

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

burik
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 514
Зарегистрирован: 03.11.2005 (Чт) 22:04
Откуда: Беларусь, Рогачев

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

Сообщение burik » 31.05.2012 (Чт) 0:26

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

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

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

Но, вообще говоря, я бы задумался над этим
milla писал(а):Используемая линейная структура: Блоковый список (размер блока 9)

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

В общем, хотелось бы увидеть какой-нибудь более конкретный вопрос.
Между слухов, сказок, мифов,
просто лжи, легенд сомнений
мы враждуем жарче скифов
за несходство заблуждений
Игорь Губерман

milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 31.05.2012 (Чт) 9:28

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

именно так

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

burik
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 514
Зарегистрирован: 03.11.2005 (Чт) 22:04
Откуда: Беларусь, Рогачев

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

Сообщение burik » 31.05.2012 (Чт) 13:45

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

И в чем вопрос? Что вообще значит "что есть поле"? Поле есть поле. Тебе нужно хранить блоки элементов, каждый элемент характеризуется ключом и данными. В задании уточнен тип ключевого поля и типы полей данных (информационных полей).
В итоге получаем элементы вида:
Код: Выделить всё
typedef struct StoredItem
{
    float key[3];
    int* intData;
    char* charData;
    float floatData;
} StoredItem;
Последний раз редактировалось burik 01.06.2012 (Пт) 0:00, всего редактировалось 2 раз(а).
Между слухов, сказок, мифов,
просто лжи, легенд сомнений
мы враждуем жарче скифов
за несходство заблуждений
Игорь Губерман

milla
Начинающий
Начинающий
 
Сообщения: 20
Зарегистрирован: 17.04.2012 (Вт) 15:26

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

Сообщение milla » 31.05.2012 (Чт) 14:51

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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 31.05.2012 (Чт) 15:13

burik писал(а):int[] intData;

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

burik
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 514
Зарегистрирован: 03.11.2005 (Чт) 22:04
Откуда: Беларусь, Рогачев

Re:

Сообщение burik » 31.05.2012 (Чт) 15:35

Qwertiy писал(а):
burik писал(а):int[] intData;

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

Ну да, что-то я ступил (копипаст - зло) :) Но автор вроде суть понял
Между слухов, сказок, мифов,
просто лжи, легенд сомнений
мы враждуем жарче скифов
за несходство заблуждений
Игорь Губерман

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 31.05.2012 (Чт) 18:46

burik писал(а):float[3] key;

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

burik писал(а):Но автор вроде суть понял

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

empirik
Начинающий
Начинающий
 
Сообщения: 1
Зарегистрирован: 13.08.2012 (Пн) 20:36

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

Сообщение empirik » 13.08.2012 (Пн) 20:42

Скажи, а стандартной библиотекой шаблонов тебе можно пользоваться? Или все на чистом C
Пиар своего бложика за счёт форума не пройдёт. Администрация


Вернуться в С/С++

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6

    TopList