Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Різновиди зв'язаних списків
[ред.] Однобічно зв'язані списки
Однобічно зв'язаний список з трьох елементів
В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що даний елемент — останній в списку.
[ред.] Двобічно зв'язаний список
Двобічно зв'язаний список
В двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка).
[ред.] Кільцевий список
В кільцевому списку перший та останній елемент зв'язані. Тобто, поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка.
Застосування списків:
Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їх основі можуть будуватись більш складні структури даних, такі як дерева. На базі списків також можуть бути реалізовані стеки та черги.
Переваги та недоліки
В загальному випадку, якщо необхідно оперувати з динамічними множинами, де присутні інтенсивні операції з додавання або видалення елементів, існують досить переконливі аргументи для використання саме зв'язаних списків.
Зв'язані списки та масиви
Списки мають деякі переваги над масивами. Вони досить ефективні щодо операцій додавання або видалення елементу в довільному місці списка, виконуючи їх за постійний час, тоді як масиви для цього потребують часу O(n), тобто час зростає з ростом кількості елементів масиву.
В списках також не існує проблеми "розширення", яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність включити в нього додаткові елементи. Точно так, фіксований масив, з якого було видалено багато елементів (або вони просто не використовуються) є дуже неефективним з точки зору використання пам'яті. Функціонування списків можливо в ситуації, коли пам'ять комп'ютера фрагментована, тоді як масиви переважно потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ до будь-якого елементу. Однобічно зв'язані списки, натомість, потребують проходження усіх попередніх елементів. Це призводить до складнощів застосування списків в задачах, де необхідно швидко знаходити елемент за його індексом, наприклад в алгоритмах сортування. Кешування списків в таких випадках майже не дає ефекту.
Іншим очевидним недоліком списків є необхідність разом з корисною інформацією додаткового збереження інформації про вказівники, що позначається на ефективності використання пам'яті цими структурами.
Двобічне та однобічне зв'язування:
Двобічне зв'язування потребує більше пам'яті на елемент та більших обчислювальних затрат на виконання елементарних операцій. Але такими списками легше маніпулювати, тому що вони дозволяють проходження по списку в обох напрямах, що є необхідною умовою функціонування деяких алгоритмів.
Задача (на використання стеку)
Задана послідовність цілих чисел, між якими можна ставити операції (+,-,*). Обчислити всі можливі значення виразів
| program vuraz; const op:array[1..3] of char= ('+','-','*'); var a:array[1..1000] of integer; stack:array[1..1000] of integer; o:array[1..1000] of integer; i,n:integer; f1,f2:text; begin assign(f1,'input.txt'); reset(f1); readln(f1,n); for i:=1 to n do read(f1,a[i]); close(f1); assign(f2,'outpu.txt'); rewrite(f2); i:=1; stack[i]:=a[1]; while i>0 do begin {поки стек не порожній} if i<n then begin {стек не повний беремо наступну операцію і обчислюємо вираз} if o[i]<3 then begin o[i]:=o[i]+1; i:=i+1; if o[i-1]=1 then stack[i]:=stack[i-1]+a[i]; if o[i-1]=2 then stack[i]:=stack[i-1]-a[i]; if o[i-1]=3 then stack[i]:=stack[i-1]*a[i]; end else {якщо наступної операції немає то знімаємо вершину стеку } begin o[i]:=0;i:=i-1; end; end; | {якщо стек заповнили то виводимо результат і знімаємо вершину} if i=n then begin for i:=1 to n-1 do write(f2,a[i],op[o[i]]); writeln(f2,a[n],'=',stack[n]); i:=i-1; end; end; close(f2); end. |
Date: 2015-09-02; view: 361; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |