Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Операции
Односвязные списки. Понятия и операции.
Связный список – структура, элементами которой служат записи с одним и тем же форматом, связанные с друг другом с помощью указателя, хранящегося в самом элементе структуры. Простейшие связные списки – линейные (односвязные и двухсвязные).
Элемент односвязного списка состоит из двух полей: информационного (хранит информацию, как угодно сложно) и поля указателя (переход на другой элемент). Есть указатель на начало списка, указатель последнего элемента списка нулевой.
 |
Логическая структура списка.
Физическая структура отличается от логической тем, что элементы располагаются раздельно.
Операции.
Data –информационное поле. Next – поле указателя. Start – указатель на начало списка. Work – рабочий указатель. Если Work указатель на элемент списка, то значения полей: Work→Data, Work→Next. При работе с динамическими структурами память выделяется динамически. ВП(Work) – процедура выделения памяти. ОП(Work) – процедура освобождения памяти.
Включение элемента в список.
а) Включение элемента в голову списка.
Необходимо включить элемент Х в начало списка.
1. ВП(Work)
2. Work→Data = X
3. Work→Next = Start
4. Start = Work
б) Формирование списка путем добавления элемента в его начало.
Необходимо сформировать список из n элементов со значением от 0 до n.
1. Start=0;создали нулевой список
2. ВП(Work)
3. Work→Data = n; n задано раньше
4. Work→Next = Start
5. Start = Work
6. n=n-1
7. Если n=0, то выход, иначе см. пункт 2.
Недостаток – список формируется в обратном порядке. Алгоритм легко программируется.
в) Включение элемента в список после заданного.
Необходимо включить элемент, заданный ссылкой Work1, после элемента списка, заданного ссылкой Work2.
1. Work1→Next = Work2→Next
2.
 |
Work2→Next = Work1
г) Включение элемента в конец списка.
Алгоритм создания списка основан на алгоритме в). Хорош, если список не большой. Если большой – завести указатель на конец списка. Недостаток – первый элемент обрабатывается не так как все остальные.
д) Включение элемента в список перед заданным элементом.
Включаем новый элемент после текущего, а потом меняем местами информационные поля.
1. Work1→Next = Work2→Next
2. Work1→Data = Work2→Data
3. Work2→Data=X
4. Work2→Next =Work1
Удаление элемента из списка.
а) Удаление элемента, следующего за заданным.
Исключить элемент, следующий за элементом на который указывает Work1.
1. Work2 = Work1→Next
2. Work1→Next = Work2→Next
3.
 |
ОП(Work2)
б) Удаление элемента на который указывает указатель.
1. Work2 = Work1→Next
2. Work1→Next = Work2→Next
3. Work1→Data = Work2→Data
4. ОП(Work2)
Вывод элементов списка.
Работает и для пустого, и для очень большого списка.
1. Work=Start
2. Пока Work<>0
3. Печать Work→Data
4. Work = Work→Next
5. Конец Пока
Циклические списки - линейный список, последний элемент которого содержит указатель на первый его элемент. Из любого элемента можно достичь любой другой элемент. Особенность алгоритма – он будет работать вечно, надо организовать прерывание.
Date: 2015-09-05; view: 272; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |