11. Список – упорядоченное множество, состоящее из переменного числа элементов, к которому применимы операции включения и исключения.
Если список располагается в оперативной памяти, то, как правило, информация для поиска следующего объекта – это указатель, адрес памяти. Если связный список хранится на диске в файле, то информация о следующем элементе может включать смещение элемента от начала файла к положению указателя записи или считывания файла, ключ записи и любую другую информацию, позволяющую однозначно отыскать следующий элемент списка.
В списке элементы связаны друг с другом логически. Логический порядок следования элементов списка определяется с помощью указателей. Подчеркнем, что логический порядок следования элементов списка может не совпадать с физическим порядком их расположения в памяти ЭВМ.
| Содержание | Ссылка |
– компонент списка
12. Ссылка – информация о связи данного компонента структуры с другим.
В качестве ссылки выступает один или множество указателей, ссылающихся на элементы рассматриваемого списка, а в качестве содержания – любой тип данных (в том числе структура).
13. Линейный список – список, отражающий отношение соседства между элементами.
Операции:
1) Создание списка
Заключается в определении указателя начала списка и присвоении ему значения NULL
2) Перебор элементов списка.
Эта операция выполняется для линейных списков очень часто и состоит в последовательном доступе к элементам списка – ко всем до конца списка либо до нахождения искомого элемента. Для каждого из перебираемых элементов осуществляется некоторая обработка его информационной части: сравнение с образцом, печать, модификация и прочее.
3) Вставка элемента в список.
Вставка элемента в середину односвязного списка
Вставка элемента в начало односвязного списка
4) Удаление эл-та из списка
5) Перестановка соседних элементов односвязного списка
14. Реализация списков на основе динамических структур (код большой, поэтому функции не расписаны)
Заголовочный файл list1.h выглядит так:
#ifndef LISTS1_
#define LISTS1_
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
// Данные (информация), хранящиеся в элементе списка
typedef struct {
char name[20];
double money;
} ELEMENT, *pELEMENT;
// Элемент списка
typedef struct {
pELEMENT inf; // Указатель на информацию
void *next; // Указатель на следующий блок
} LIST1, *pLIST1;
// Добавить в конец списка новый элемент
pLIST1 AddToLists1(pELEMENT pInf);
// Добавить в список после заданного элемента
pLIST1 AddToLists1Elem(char* pName, pELEMENT pInfNew);
// Удалить из списка заданный элемент (первый, если pName==NULL)
pLIST1 DelFromLists1(char* pName);
// Найти в списке заданный элемент
pLIST1 FindInLists1(char* pName);
// Вывести содержание списка
void PrintLists1(void);
15. Двусвязный список позволяет выполнять «движение» от элемента к элементу в обоих направлениях. В этом случае элемент включает два указателя: на предыдущий и последующий элементы списка. А так как список имеет и начало, и конец, описываются еще два указателя – начала и конца списка
Организация двусвязного списка
1. Удаление элемента
2. Вставка элемента
16. Кольцевые списки – получится, если замкнуть связь «вперед» последнего блока на первый блок списка, а связь «назад» первого блока на последний.