Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Поняття та класифікація зв'язних списків

Зв*язний список – це динамічна структура даних яка складається з вузлів які зв*язані між собою і представляють послідовність. Кожен вузол є структурою який містить інформаційні поля а також посилання на інші вузли(попередні або наступні)

Класифікація Циклічні/нециклічні, Двозв*язні/однозв*язні, Однонаправлені/ двонаправлені

 

Оголошення зв’язних циклів

кожен вузол в списку є структурою даних. Вказівники на наступний і попередній

елемент повині мати той самий тип що і вузол списку. Для роботи з

списком нам достатньо двох вказівників.

head - початок (голова)

tail - кінець (хвіст)

// оголошення вузла

struct Telefon{

string name;

int age;

Telefon *next,*prev;

Telefon(){

next=prev=NULL;

};

//оголошення структури на список

struct LstTelefon{

Telefon *head,*tail;

LstTelefon(){

hedd=tail=NULL;

};

//створення змінної списку

LstTelefon *Tel=new Telefon();

 

 

83..85

struct Film{

string name;

int age;

Film *next;

 

Film(){

next=NULL;

};

};

//оголошення структури на список

struct LstFilm{

Film *head,*tail;

LstFilm(){

heаd=tail=NULL;

};

};

//створення змінної списку

LstFilm *Tel=new Film();

 

87.Зв'язаний список в програмуванні — одна з найважливіших структур даних,

в якій елементи лінійно впорядковані, але порядок визначається не номерами елементів,

а вказівниками, які входять в склад елементів списку та вказують на наступний за даним

елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній

елементи (в двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент

та «хвіст» — останній елемент.

Операції над зс: вставка елемента в список, вилучення елемента зі списку.

перевірка чи список пустий

bool Lstfilms:: is Empty(){

if (head==NULL)

return true;

else

return false; };

88.додавання нового вузла

При додаванні до списку нового елемента необхідно динамічно виділити для гього память за доп. оператора new та присвоїти відповідні адреси вказівниками сусідніх елементів.

void LstFilms::(SFilm *f, SFilm *prevf){

SFilm *next=prev->next;

prevf->next=f;

f->next=nextf;

f->prev=prevf;

nextf->prev=f;};

 

89. Додавання елемента на початок списку: 1.Виділити память під новий елемент списка, нехай змінна р вказує на виділену память 2. Встановити необхідне значення поля напр data 3.присвоїти полю next значення елемента head 4. Присвоїти змінній head значення р.

код

p->data = ...;

p->next = head;

head = p;

Додавання елемента в список: зберегти адресу останнього елемента в тимчасовій змінної; створити новий елемент, записати в нього значення, в полі next - покажчик на попередній елемент.
node * prev = top;
top = new node;
top-> value = 'd';
top-> next = prev; / / пов'язати з попереднім

90.вилучення вузла Створюється тимчасовий вказівник, куди записується адреса об'єкту, що видаляється.
У вказівнику попереднього об'єкта на той що видаляється присвоюється адреса наступного після того що видаляється.
Видаляється об'єкт з тимчасового покажчику.

Поясню на прикладі.
Є спрямований список, в кожному елементі якого записана адреса наступного.
1> 2> 3> 4> 5
Потрібно видалити елемент номер 3. Якщо ми його просто вилучимо, то доступу до елементів 4 і 5 ми не отримаємо, тому що адресу 4 буде загублено. Тому, ми спочатку записуємо в якості наступного після 2 4 елемент, адреси третім зберігши в тимчасовій адресної змінної. Після чого за цією адресою видаляємо 3 елемент.
void Lstfilm::delete(sFilm *flm){

Sfilm *prevf=flm->prev,*next=flm->next;

Delete flm;

Prevf->next=nextf;

Nextf->prev=prevf;}

Навігація по зв’язному списку

Навігація по зв’язному списку здійснюється за допомогою вказівників. Зазвичай їх називають next, prev. В однозвязному списку використовується лише вказівник next, що дозволяє переходити на наступний елемент зв’язного списку. В двозвязному списку використовується вказівник next, prev, що дозволяє переходити по зв’язному списку і на наступний елемент і на попередній.

 

Реалізація деструктору зв’язного списку

.LstFilms::~LstFilms(){

SFilm * flm=head, *prevflm;

While (flm!=NULL){

Prevflm=flm;

Flm=flm->next;

Delete prevflm;}

93. Стек. СТЕК в інформатиці та програмуванні -- різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) "останнім прийшов -- першим пішов" (LIFO, last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім.

Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку -- "магазин", за аналогією з принципом роботи магазину в автоматичній зброї)

Операції зі стеком

push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (stack overflow)

pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (stack underflow)

Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.

Додаткові операції (присутні не у всіх реалізаціях стеку):

isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли в стеку немає елементів.

isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе

clear: звільнити стек (видалити усі елементи).

top: отримати верхній елемент (без виштовхування).

size: отримати розмір (кількість елементів) стека.

swap: поміняти два верхніх елементи місцями.

 

94. Реалізація стеку за допомогою зв’язного списку Стек у вигляді списку (pushdown list) – стек, організований таким чином, що останній елемент, що вводить в область пам'яті, розміщується на вершині списку.Стек є окремим видом зв’язного списку, у якому нові вузли можуть розміщуватися в стек і видалятися (виштовхуватися) з нього тільки на його вершині. З цієї причини стек є структурою даних типу «останнім увійшов – першим вийшов» («last-іn, fіrst-out» – LІFO). Елемент зв’язку в останньому вузлі стека встановлюється на нуль для того, щоб показати дно стека.

struct STACKNODE {

int value;

struct STACKNODE * next;

} stacknode_t;

 

 

Операції Push і Pop для стеку

- При роботі зі стеком операції занесення і витягнення елемента є основними. Такі операції називають «запхати в стек» => Push, «витягнути зі стеку» => Pop.

-Для реалізації стеку потрібно дві функції – push() I pop()

-Також потрібно виділити область памяті, яка буде використовуватися в якості стеку.

int stack[MAX];

int tos=0; /* вершина стека */

/* запхати елемент в стек */

void push(int i){

if(tos >= MAX) {

printf("Стек повний\n");

return; }

stack[tos] = i;

tos++;}

/* Отримуємо верхній елемт стеку */

int pop(void){

tos--;

if(tos < 0) {

printf("Стек пустий\n");

return 0; }

return stack[tos];}

 

 

Реалізація деструктору стеку

~CLstStack({

if(ptop!=0){

if((*ptop).prev!=0){

List *ptr;

ptr=ptop;

ptop=(*ptop).prev;

delete ptr;}

delete ptop;}}

Последнее изменение этой страницы: 2016-08-11

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...