блоковый список

[yuliya]

Помогите написать код пожалуйста
завтра нужно сдавать
Написать программу, предоставляющую возможность ведения информационного массива данных заданной структуры. Для хранения информационного массива нужно использовать блоковый список (размер 5)
Ключе-вое поле Информационные поля
int char[], float

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

[Qwertiy]

Помогите написать код пожалуйста

И в чём эта помощь должна заключаться?
Спрашивай конкретно, что не получается.

Для хранения информационного массива нужно использовать блоковый список (размер 5)

А что это такое?

Ключевое поле: int
Информационные поля: char[], float

Поясни.
К тому же, тип char[] в таком виде не существует.

Давай-ка, ты расскажешь всё что знаешь о блоковом списке. А там посмотрим, возникнет ли желание тебе что-нибудь подсказать

[yuliya]

#include <stdio.h>


struct Block
{
int data1;
char data2[10] ;
float data3;

};
struct list
{
int count;
Block N[5];
list* prev;
list* next;
};

void main()
{

}



я написала объявление, я не уверена даже, что это правильно, почитала примеры просто
я не имею представления как дальше делать

[Qwertiy]

я написала объявление, я не уверена даже, что это правильно

Объявление выглядит корректно с точки зрения си и си++.
А ключевое поле логичнее назвать key, а не data

почитала примеры просто

Может что-то ещё стоит почитать?

Расскажи, какое поведение ожидается от списка. И что это такое.

PS: Используй тег code для кода.

[yuliya]

Блоковый список.
В блоковых структурах элементы объединяются в группы – блоки. Адресная информация предыдущий – следующий определяется для блока, а не для каждого элемента. Элементы внутри блока содержат неявную связь (т.е образуют массив). Использование блочной списковой структуры обуславливается необходимостью минимизировать время доступа к данным. Списки ориентированы на случаи, когда требуются частые и быстрые операции вставки – удаления в произвольную позицию последовательности, а массивы ориентированы на задачи, в который требуется эффективный доступ к элементам произвольных позиций по индексам. Несмотря на то, что для узлового списка можно эмулировать процедуру произвольного доступа, она будет мало эффективна. Блочные списки объединяют в себе скоростное удаление-добавление элементов (как в списковых структурах) и ускоренный доступ к элементам, находящимся на произвольной позиции (аналогично массивам). Блочный список реализует те же самые функции, что и узловой список.
Вставка элементов блока реализуется по следующему правилу:
• если блок содержит свободные ячейки, то элемент вставляется в этот блок, возможно со сдвигом содержимого блока на одну позицию и увеличивается счетчик элементов в блоке
• если свободных ячеек нет, то создается новый блок, добавляемый в блочный список, в старом блоке осуществляется сдвиг элементов на единицу и вытесняемый хвостовой элемент старого блока вытесняется на нулевую позицию нового блока, добавляемый элемент записывается на освободившееся место.
• альтернативная стратегия вставки элемента предусматривает вытеснение хвостового элемента из одного блока в соседний и сдвига элементов, находящихся в нем
Преимущества блоковых списков:
1. ускорение доступа к произвольной позиции в списке
2. снижение накладных расходов на служебные описатели динамической памяти

[yuliya]

нам объяснили вот это, там нужно как-то связи устанавливать еще между блоками

[Qwertiy]

Ага, примерно так я и подумал по твоим структурам. А теперь своими словами расскажи.

[yuliya]

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

[Qwertiy]

Вначале должен быть один элемент

Наверное, всё-таки 0?

мы его кладем в блок, потом добавляем еще один, тоже кладем в блок

Выглядит как добавление в конец, но ведь надо добавление в произвольную позицию?

когда блок закончится, настраиваем связи между блоками

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

Если нужно удалить, то перенастраиваем связи

В принципе, да. Однако, можно опустить этот шаг.

Расскажи словами про устройство списка. Сама. Без копипаста из книжки.
Да, у него есть не только плюсы, но и минусы.

[yuliya]

устройство? не совсем понимаю вопрос

[Qwertiy]

Ну то же самое, что ты откуда-то скопировала/переписала про блоковый список, только так, как ты это понимаешь.
Кстати, ты пишешь на Си или на Си++?

PS: А с какого ты факультета?

[yuliya]

странный вопрос) ты спрашиваешь не какой ВУЗ, а про факультет

[Qwertiy]

странный вопрос) ты спрашиваешь не какой ВУЗ, а про факультет

Ага, я спросил факультет, а не вуз
А что, по-твоему, я могу получить из названия вуза? Тем более, что я не знаю ни город, ни даже страну.

А как насчёт остальных вопросов?

[yuliya]

вообще на си нужно, но я вставляю всякие штуки из си++

[yuliya]

и вообще, ты уже три тысячи вопросов задал) помог бы лучше)

[Qwertiy]

ты уже три тысячи вопросов задал)

Так ты ж на них не отвечаешь

помог бы лучше)

А я чем занимаюсь?

[Qwertiy]

Представим массив неограниченного размера. Недостатком работы с ним является то, что при вставке куда-нибудь между имеющимися данными требуется перемещать весь хвост массива. Кроме того, реальный массив имеет ограниченный размер, поэтому при необходимости добавить элемент, весь массив надо пересоздать заново. Эта проблема решается при помощи предварительного резервирования памяти и хранения реальной длины массива. Сответствующий класс в Си++ называется vector<smth>. При своём создании он резервирует 16 элементов и заново выделяет память только когда появися 17-й - размер буфера составит 32 элемента, затем 64 и т. д. Но проблема перемещения хвоста при вставке в произвольную позицию сохраняется.

Теперь список, точнее, двунаправленный список. Каждый его узел кроме данных содержит указатель на предыдущий и следующий элемент. Это позволяет, имея указатель на узел списка, мгновенно выполнять операции вставки и удаления элемента. Однако, при этом теряется возможность определить положение элемента по номеру, поэтому для получения i-го элемента требуется пройти все i первых элементов. В Си++ этот класс называется list<smth>.

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

То, что у тебя названо блоковым списком позволяет занять некоторую промежуточную позицию между массивом и списком. В идеальных условиях, он способен сделать нечто типа sqrt-декомпозиции, что даст существенно более быстрый доступ и немного более медленную вставку по сравнению со списком. Идея заключается в том, что каждый элемент списка содержит в себе вектор, размер которого не может превышать заданного числа. Если при вставке мы пытаемся его превысить, то создаётся новый узел списка и последний элемент массива текущего узла вытесняется в него. Так написану у тебя, но мне это не нравится, т. к. постоянное добавление в заполнеенй узел будет создавать новый. Также, у тебя упоминается альтернативный вариант, но он мне не нравится, т. к. он портит ассимптотику вставки смещением элементов. Если бы я писал реализацию, то я бы перекидывал половину элементов с целью уравновесить размеры узлов. Таким образом получается нечто вроде list<vector<smth>>.

Но есть небольшое отличие в реализации итератора. Теоретически, вектор позволяет в качестве итератора использовать указатель на элемент с данными, а список - указатель на узел. Однако, во варианте со списком векторов, итератором является лишь пара из указателя на узел списка и индекса элемета в нём. Да, ещё одним недостатком такой структуры является то, что операция вставки может разрушать итераторы, сохранённые до неё.

* smth - something - некий тип, в соответствии с тем, что мы держим в коллекции.

Да, забыл про удаление элемента. Собственно, ничего особенного в неём нет, достаточно просто удалить элемент из соответствующего массива. Даже если узел с пустым массивом останется в списке, то ничего страшного не произойдёт.

Какие вопросы остались?

[yuliya]

сложно как-то все

может ты мне с алгоритмом поможешь?

[Qwertiy]

может ты мне с алгоритмом поможешь?

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

сложно как-то все

Постарайся всё-таки разобраться. Я ведь это не просто так полчаса писал. И это не скопированный текст, а то, что по идее, должно тебе помочь, если ты знаешь достаточно.
Спрашивай конкретнее то что непонятно, я отвечу. Можешь показывать код, если что-то не получается или не работает - тоже посмотрю.

PS: Ты так и не ответила про факультет

[yuliya]

судя по моим талантам в программировании я с физкультурного)

[yuliya]

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

[Qwertiy]

мне нужна информация по реализации

Хм.. А я тебе не информацию дал?

[yuliya]

неа

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

[Qwertiy]

мне нужна информация по реализации

Структура записи record. Она состоит из ключа и данных, как ты писала.
Структура узла списка node. Он содержит массив из заданного числа record'ов и число - заполненность массива. Кроме этого там есть указатели на следующий и предыдущий узлы списка. Реализуется обычный двусвязный список.
Структура списка list. Содержит указатели на первый и последний узлы списка (возможно, private, но можно и public) и предоставляет возможность получения итератора для первого и последнего элементов, а также ссылочный доступ к элементу по его индексу.
Структура итератора iterator. Содержит указатель на элемент и предоставляет возможность ссылочного доступа к элементу. Кроме этого предоставляет возможность вставки (перед и после) и удаления элемента. Следует предусмотреть способ добавления элемента в пустой список.

Под структурой вполне можно понимать класс. В общем-то, разница между ними только в дефаултной доступности методов. Хотя, я написал с точки зрения Си++. В Си private нет, да и методы внутрь структур не помещали, кажется.

[Qwertiy]

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

Если ты хочешь узнать что-то конкретное, то стоит спросить что-то конкретное.
Счётчик - только количество элементов массива.
Указатели - в соответствии со стандартной реализацией связного списка.
Кстати, при неудалении узлов списка, можно отделаться односвязным списком.