книги / Программирование на языке Си
..pdf544 |
Программирование на языке Си |
В конкретном задании (см. ниже) информационная динами ческая структура может быть списком, бинарным деревом, сте ком или деревом с особым строением узлов и связей. В зависимости от типа конкретной информационной структуры могут быть целесообразны разные операции по ее обработке. Ниже приведены три группы вариантов динамических структур, и для каждой группы предложен список функций, реализующих подходящий набор операций.
10.8.1. Списки
Разработать комплекс функций для обслуживания сложных структур данных в виде разнообразных списков: однонаправ ленных, двунаправленных, с ключами, без ключей, кольцевых, неоднородных и т.п.
В помещенных ниже изображениях используются следую щие обозначения: D - данные, next (либо N) - указатель на сле дующий элемент, Р - указатель на предыдущий элемент; К - ключ; begin - указатель на начало списка.
Вариант 1. Однонаправленный список
begin—И D | next 4 |
D | next |
D NULL |
Вариант 2. Однонаправленный список из элементов с клю чами
begin- К D next- |
К D next- |
К D NULL |
Вариант 3. Кольцевой список
begin
Вариант 4. Кольцевой список из элементов с ключами
begin —»{К 1Р~ next- |
К D next- |
К D next- |
Глава 10. Задачи по программированию |
547 |
Вариант 12. Двунаправленный неоднородный (гетероген ный) список с однородными подсписками из элементов с клю чами
begin—»(тйп llK|N~t^ |
ffkn |
|
~Д,Тип l|K|N*• |
Тип 2 К N" |
.Тип |
2 К N |
Тип 2 К N |
|
|
|
t 3 |
н Тип КIКIbrfct j-Тип KjKTN^ |
..3 $ Тип К| К|NUIX |
||
В программах для приведенных вариантов заданий исполь зуйте следующие обозначения:
begin - указатель на начало списка;
D- поле данных (строка произвольной длины либо указатель на строку);
К- поле ключа - дополнительное поле элемента спи ска, заполняемое уникальным значением. Правило формирования ключа предлагается выбрать само стоятельно. Простейшие варианты ключей:
•номер элемента в списке;
•номер элемента при его создании;
N, next - указатель на следующий элемент списка;
Р- указатель на предыдущий элемент списка;
NULL - нулевой указатель (используется, если для кон кретного элемента списка отсутствуют последую щий или предыдущий элементы).
Для каждого из вариантов необходимо разработать следую щие функции:
1.Создание {пустого списка).
2.Добавление элемента:
•в начало списка;
•в конец списка;
•после элемента с заданным номером;
1/г35’
548 |
Программирование на языке Си |
•(*) после элемента с заданным ключом.
3.Печать списка (вывод на экран дисплея):
•номер элемента;
•содержимое поля данных;
•(*) содержимое поля ключа;
•значение указателя на следующий элемент;
•(**) значение указателя на предыдущий элемент.
4.Удаление элемента из списка:
•из начала;
•из конца;
•с заданным номером;
•(*) с заданным ключом.
5.Запись списка в файл.
6.Уничтожение списка.
7.Восстановление (чтение) списка из файла.
8.Упорядочение элементов в списке по выбранному признаку:
•используя информацию в поле данных;
•(*) используя информацию в поле ключа.
9.Изображение структуры списка на экране дисплея.
Примечания:
1.Звездочкой С") обозначены функции списков для эле ментов с ключами.
2.Двумя звездочками (**) обозначены функции для дву направленных списков.
3.Для неоднородных списков функции обслуживания должны разрабатываться применительно, к определенному однородному подсписку.
Вариант 13. Стек.
Глава 10. Задачи по программированию |
551 |
В древовидной структуре типа В (рис. 10.4) вершина состоит всегда из 4 элементов: поля данных и 3 указателей на возмож ные вершины нижнего уровня. Указателям, не ссылающимся на вершины, присваивается значение NULL.
Вариант 4 (Г)
Рис.10.5. Древовидная структура типа Г
В древовидной структуре типа Г (рис. 10.5) каждая вершина содержит следующие поля:
•поле данных;
•поле, в котором указано число координирующих вспомога тельных полей;
•вспомогательные поля, содержащие указатель на вершину более высокого уровня (предыдущую) и указатели на вер
шины нижнего уровня.
Если с текущей вершиной не связаны вершины нижнего уровня, то в структуре даннь!х, описывающей вершину, соот ветствующие вспомогательные поля отсутствуют. Для корневой вершины нет вершины более высокого уровня, поэтому соот ветствующему указателю (помечен как 'х') должно быть при своено значение NULL.
Для каждого из приведенных выше вариантов необходимо разработать следующие функции:
1.Создание пустого дерева.
2.Добавление вершины к указанной вершине дерева.
552 |
Программирование нв языке Си |
3.Распечатка (вывод на дисплей) структуры дерева.
4.Удаление заданного элемента из дерева с уничтожением поддерева подчиненных вершин.
5.Запись дерева в файл.
6.Уничтожение дерева.
7.Восстановление (чтение) дерева из файла.
8.Изображение структуры дерева на экране.