Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > программирование структур специального вида

Автор: milla 30.5.2012, 14:36

Добрый день! Помогите, пожалуйста, разобраться. Есть определение структуры специального вида (блоковый список): Код typedef struct BlockInt {   int idx;                 //индекс блока   int cells[9];            // сам блок   struct BlockInt *prev;    // указатель на предыдущий блок   struct BlockInt *next;    // указатель на следующий блок } BlockInt; Как мне создать переменную типа BlockInt, состоящую из трех блоков(элементы каждого блока произвольные), и как потом к ней обратиться, чтобы вывести на экран, допустим, только второй блок, или 7-й элемент третьего блока?

Автор: boostcoder 30.5.2012, 14:49

Цитата(milla @  30.5.2012,  14:36 ) структуры специального вида и что же в ней специфичного? Цитата(milla @  30.5.2012,  14:36 ) (блоковый список) хм.. еще вчера она была двусвязным списком  Цитата(milla @  30.5.2012,  14:36 ) элементы каждого блока произвольные нужно знать хотя бы возможные типы.

Автор: milla 30.5.2012, 15:11

Это название лабораторной -"Программирование структур специального вида"- преподавателю виднее, что в ней, структуре, специфичного))) блоковый список - оттуда же, из задания к лабораторной, если так удобнее, пусть будет двусвязный список, сути дела это не меняет каждый блок по сути это массив элементов типа int необходимо создать такой вот блоковый список, а затем провести над ним некоторые операции - добавление, удаление, редактирование элементов. А для этого мне нужно понять, как с этим списком обращаться. Как создать новый, как записать в него элементы, как правильно к ним обратиться.

Автор: feodorv 30.5.2012, 15:20

Цитата(milla @  30.5.2012,  15:36 ) Как мне создать переменную типа BlockInt, состоящую из трех блоков(элементы каждого блока произвольные), Думается мне, что так: Код struct BlockInt bi[3]; Цитата(milla @  30.5.2012,  15:36 ) 7-й элемент третьего блока Полагаю, что этак: Код bi[2].cells[6]

Автор: milla 30.5.2012, 16:29

спасибо, не думала, что все так просто)))) А как работать с указателями в структуре (prev и next)? Задача такая - для этой структуры реализовать функцию вставки элемента или целого блока в заданную позицию. С элементом я в принципе поняла как быть, а с целым блоком? Чтобы вставить новый блок между первым и вторым, надо ведь как-то переопределить указатели на предыдущий и следующий блоки, правильно?

Автор: feodorv 30.5.2012, 17:04

Цитата(milla @  30.5.2012,  17:29 ) Чтобы вставить новый блок между первым и вторым, надо ведь как-то переопределить указатели на предыдущий и следующий блоки, правильно?  Я что-то запутался... Цитата(boostcoder @  30.5.2012,  15:49 ) хм.. еще вчера она была двусвязным списком smile Двусвязный список - это отдельный разговор. В реализации - проще, в сортировке - труднее. Для него как раз и нужны prev и next. Сами элементы двусвязного списка могут располагаться в памяти как угодно. Но и последовательный доступ к элементу номер N затруднён - нужно проходить по связям, отсчитывая их число. Непрерывный список состоит из набора следующих друг за другом структур. Очень простой доступ к блоку номер N - &bi[N], если отсчитывать от нуля. Здесь не нужны prev и next, так как нет связей. Но вставка нового блока затруднена, особенно если требуется вставить в середину списка. Что нужно делать в таком случае: 1/ убедиться, что в списке есть память на новый блок. Если памяти нет, то нужно её перезаказать на весь список, если реализация списка предполагает его расширение за отведённые границы. Например, если Вы объявляете Код struct BlockInt bi[100]; unsigned int biCount = 0; то реализация не предусматривает расширение списка за пределы 100 штук блоков. Если же так Код struct BlockInt *bi = NULL; unsigned int biCount = 0; unsigned int biReserved = 0; то список bi можно приращивать и приращивать вплоть до нехватки памяти. 2/ сдвинуть блоки, лежащие на и ниже позиции вставки, на 1 элемент вниз (через memmove, например). Если новый блок вставляется в конец списка, то ничего сдвигать не нужно. 3/ на освободившееся свободное место записать новый блок. Цитата(milla @  30.5.2012,  17:29 ) не думала, что все так просто)))) Уже не так просто, как со связным списком?))) Впрочем, если  Цитата(milla @  30.5.2012,  17:29 ) С элементом я в принципе поняла как быть то и с блоками трудностей не должно возникнуть)))

Автор: milla 30.5.2012, 17:28

Я почему про указатели спросила - для реализации функции вставки есть алгоритм, дословно из лекции:  "вставка элемента в блок реализуется по следующему правилу если      блок содержит свободные ячейки, то вставить элемент(возможно со сдвигом содержимого блока на одну позицию), увеличить счетчик  иначе   создать новый блок и вставить его как узел в двусвязном списке, настроив указатели prev и next, где необходимо. Осуществить сдвиг в старом блоке,                        хвостовой элемент поместить в нулевую позицию нового блока, добавляемый элемент в освободившуюся позицию, счетчику нового блока присвоить единицу конец_если"  Так вот как настроить "указатели prev и next, где необходимо" ? Прошу прощения, если вопрос элементарный, но с указателями у меня совсем дело плохо.....

Автор: feodorv 30.5.2012, 18:42

Цитата(milla @  30.5.2012,  18:28 ) есть алгоритм Он для двусвязного списка   Цитата(boostcoder @  30.5.2012,  15:49 ) еще вчера она была двусвязным списком Значит, список как был двусвязным, так и остаётся? Цитата(milla @  30.5.2012,  15:36 ) Как мне создать переменную типа BlockInt, состоящую из трех блоков(элементы каждого блока произвольные) Тогда это иначе решается  Добавлено через 5 минут и 25 секунд Цитата(milla @  30.5.2012,  18:28 ) Так вот как настроить "указатели prev и next, где необходимо" ? В чём смысл этих двух значений? Вот согласно смыслу и настраивать   Добавлено через 8 минут и 24 секунды Цитата(milla @  30.5.2012,  18:28 ) иначе   создать новый блок Этак новых блоков с одним элементом насоздавать можно просто завались

Автор: mes 30.5.2012, 19:17

milla, сейчас Вас тут окончательно собьют.. У вас должен получиться связанный список блоков.. Создавать блоки должны не массивом, как предложено выше, а по одному, корректируя указатели prev и next, как у новосозданного элемента, так и  у списка в который этот блок добавляется.. для этого вы должны создать нужные функции.. Чтоб было проще разбейте работу на два этапа: первый это работа со списком блоков, а второй работа с элементами в этом блоке..

Автор: milla 30.5.2012, 19:41

mes, вы все правильно говорите, только вся проблема в том, что я не умею работать с указателями - для меня это один большой пробел((((( Покажите на примере простеньком,  как с этими самыми указателями работать, ну чему, например равны эти prev и next для моего случая, когда структура содержит 3 блока? И как они изменятся при добавлении нового блока? Как ими манипулировать, как настраивать....

Автор: mes 30.5.2012, 21:01

Цитата(milla @  30.5.2012,  18:41 )  ну чему, например равны эти prev и next для моего случая prev  = NULL или адресу предыдущего элемента (для  всегда NULL (если не  кольцевой список) ) next =  NULL или адресу следующего элемента (для tail/back всегда NULL (если не  кольцевой список) ) для списка из одного элемента оба указателя этого элмента равны нулю.. добавление нового блока состоит из двух операций : создание и линковка .. под линковкой подразумевается связывание указателей,  условно так : Код void link_blocks(block * prev,  block * mid, block * next) {      if (prev) prev->next = mid;      if (next) next->prev = mid;      if (mid) {              mid->prev = prev;             mid->next = next;       } }   тогда добавление в список нового элемента  Код void append_next (block * prev,  block * new_block) {     if (prev && new_block) link_blocks (prev, new_block, prev->next); } по связанным спискам в гугле информации больше, чем достаточно..в том числе и с полноценные примеры кода..

Автор: feodorv 30.5.2012, 21:08

Цитата(milla @  30.5.2012,  20:41 ) И как они изменятся при добавлении нового блока? Как ими манипулировать, как настраивать....    Цитата(milla @  30.5.2012,  15:36 ) typedef struct BlockInt {   int count;                 //счетчик блока - число элементов в блоке   int cells[9];            // сам блок   struct BlockInt *prev;    // указатель на предыдущий блок   struct BlockInt *next;    // указатель на следующий блок } BlockInt; Создадим новый блок: Код struct BlockInt *BlockCreate( void ) {   struct BlockInt *block = (struct BlockInt *) malloc( sizeof( struct BlockInt ) );   if( block != NULL )   {      // Инициализируем новый блок     block->count = 0; // в блоке нет элементов, он пустой     block->prev = NULL; // у блока нет предыдущего элемента     block->next = NULL; // у блока нет следующего элемента   }   return block; } Теперь напишем подпрограмму вставки одного блока после другого, пока не учитывая тот факт, что список может быть пустым (то есть и b и newBlock отличны от NULLа): Код void BlockInsert( struct BlockInt *b, struct BlockInt *newBlock) {   // Поскольку после b может следовать ещё какой-то блок, запомним его   struct BlockInt *after = b->next;   // Он может и не существовать, тогда after имеет значение NULL   if( after == NULL )   {     b->next = newBlock;     newBlock->prev = b;     newBlock->next = NULL; // на всякий случай     return;   }   // Следующий блок существует, поэтому аккуратно вставим между ними новый блок   after->prev = newBlock;   newBlock->next = after;   newBlock->prev = b;   b->next = newBlock; }

Автор: mes 30.5.2012, 21:11

Цитата(milla @  30.5.2012,  13:36 ) Код typedef struct BlockInt {   int idx;                 //индекс блока   int cells[9];            // сам блок   struct BlockInt *prev;    // указатель на предыдущий блок   struct BlockInt *next;    // указатель на следующий блок } BlockInt; в С желательно более общую информацию указывать до  более конкретной,т.е  Код typedef struct BlockInt {   struct BlockInt *prev;    // указатель на предыдущий блок   struct BlockInt *next;    // указатель на следующий блок   int idx;                 //индекс блока   int cells[9];            // сам блок } BlockInt;

Автор: feodorv 30.5.2012, 21:27

Цитата(milla @  30.5.2012,  20:41 ) структура содержит 3 блока Я так понимаю, что имелось в виду - список содержит три блока... Код #include <alloc.h> struct BlockInt *list = NULL; // сам список, изначально пустой int main( void ) {   struct BlockInt *second, *third; // вставим первый блок   list = BlockCreate();   if( list == NULL ){ ...error...; return 1; } // вставим второй блок   second = BlockCreate();   if( second == NULL ){ ...error...; return 1; }   BlockInsert( list, second); // вставим третий блок   third = BlockCreate();   if( third == NULL ){ ...error...; return 1; }   BlockInsert( second, third);   return 0; } Добавлено через 1 минуту и 18 секунд Цитата(mes @  30.5.2012,  22:11 ) в С желательно более общую информацию указывать до  более конкретной Согласен, но в данном случае я использую уже предложенный порядок

Автор: milla 30.5.2012, 21:46

mes,  feodorv, спасибо вам преогромное!!! Вразумили)))  Теперь в голове более-менее прояснилось. Буду колдовать над этой лабой, вооружившись вашими советами)))) idx - действительно счетчик блока, это моя невнимательность...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)