Курсовая работа: Програмний комплекс для роботи розробки візитних карток

Рис.8. Схема збереження двузв‘язного списку.

Вставка нового вузла зі значенням new за елементом, обумовленим покажчиком p, здійснюється за допомогою операторів:

r=malloc(NDD); r->val=new; r->n=p->n; (p->n)->m=r; p->=r;

Видалення елемента, що випливає за вузлом, на який указує p

p->n=r; p->n=(p->n)->n; ( (p->n)->n )->m=p; free(r);

Зв'язане збереження лінійного списку називається циклічним списком, якщо його останній указує на перший елемент, а покажчик dl - на останній елемент списку.

Схема циклічного збереження списку F=<2,5,7,1> приведена на мал.9.

Рис.9. Схема циклічного збереження списку.

При рішенні конкретних задач можуть виникати різні види зв'язаного збереження.

Нехай на вході задана послідовність цілих чисел B1,B2,...,Bn з інтервалу від 1 до 9999, і нехай Fi (1<I по зростанню. Скласти процедуру для формування Fn у зв'язаному збереженні і повернення покажчика на його початок.

При рішенні задачі в кожен момент часу маємо упорядкований список Fi і при введенні елемента Bi+1 уставляємо його в потрібне місце списку Fi, одержуючи упорядкований список Fi+1. Тут можливі три варіанти: у списку немає елементів; число вставляється в початок списку; число вставляється в кінець списку. Щоб уніфікувати всі можливі варіанти, початковий список організуємо як зв'язаний список із двох елементів <0,1000>.

Розглянемо програму рішення поставленої задачі, у якій покажчики dl, r, p, v мають наступне значення: dl указує початок списку; p, v - два сусідніх вузли; r фіксує вузол, що містить чергове введене значення in.

#include #include typedef struct str1 { float val; struct str1 *n; } ND; main() { ND *arrange(void); ND *p; p=arrange(); while(p!=NULL) { printf("\n %f ",p->val); p=p->n; } } ND *arrange() /* ?????????? ?????????????? ?????? */ { ND *dl, *r, *p, *v; float in=1; char *is; dl=malloc(sizeof(ND)); dl->val=0; /* ?????? ??????? */ dl->n=r=malloc(sizeof(ND)); r->val=10000; r->n=NULL; /* ???????? ??????? */ while(1) { scanf(" %s",is); if(* is=='q') break; in=atof(is); r=malloc(sizeof(ND)); r->val=in; p=dl; v=p->n; while(v->valn; } r->n=v; p->n=r; } return(dl); }

Стеки і черги

У залежності від методу доступу до елементів лінійного списку розрізняють різновиду лінійних списків називані стеком, чергою і двосторонньою чергою.

Стек - це кінцева послідовність деяких однотипних елементів - скалярних перемінних, масивів, структур або об'єднань, серед яких можуть бути й однакові. Стік позначається у виді: S= і представляє динамічну структуру даних; її кількість елементів заздалегідь не вказується й у процесі роботи, як правило змінюється. Якщо в стеці елементів ні, то він називається порожнім і позначається S=<>.

Припустимими операціями над стеком є:

- перевірка стека на порожнечу S=<>,

- додавання нового елемента Sn+1 у кінець стека - перетворення < S1,...,Sn> у < S1,...,Sn+1>;

- вилучення останнього елемента зі стека - перетворення < S1,...,Sn-1,Sn> у < S1,...,Sn-1>;

- доступ до його останнього елемента Sn, якщо стік не порожній.

Таким чином, операції додавання і видалення елемента, а також доступу до елемента виконуються тільки наприкінці списку. Стік можна представити як стопку книг на столі, де додавання або узяття нової книги можливо тільки зверху.

Черга - це лінійний список, де елементи віддаляються з початку списку, а додаються наприкінці списку (як звичайна черга в магазині).

Двостороння черга - це лінійний список, у якого операції додавання і видалення елементів і доступу до елементів можливі як спочатку так і наприкінці списку. Таку чергу можна представити як послідовність книг на полку, так що доступ до них можливий з обох кінців.

Реалізація стеков і черг у програмі може бути виконана у виді послідовного або зв'язаного збереження. Розглянемо приклади організації стека цими способами.

Однієї з форм представлення виражень є польський інверсний запис, що задає вираження так, що операції в ньому записуються в порядку виконання, а операнди знаходяться безпосередньо перед операцією.

Наприклад, вираз

(6+8)*5-6/2

у польському інверсному записі має вигляд

6 8 + 5 * 6 2 / -

Особливість такого запису полягає в тому, що значення вираження можна обчислити за один перегляд запису ліворуч праворуч, використовуючи стек, що до цього повинний бути порожній. Кожне нове число заноситься в стек, а операції виконуються над верхніми елементами стека, заміняючи ці елементи результатом операції. Для приведеного вираження динаміка зміни стека буде мати вигляд

S = <>; <6>; <6,8>; <14>; <14,5>; <70>;<70,6>; <70,6,2>; <70,3>; <67>.

Нижче приведена функція eval, що обчислює значення вираження, заданого в масиві m у формі польського інверсного запису, причому m[i]>0 означає ненегативне число, а значення m[i]<0 операції. Як кодування операцій додавання, вирахування, множення і розподіли обрані негативні числа 1, 2, 3, 4. Для організації послідовного збереження стека використовується внутрішній масив stack. Параметрами функції є вхідний масив a і його довжина l.

float eval (float *m, int l) { int p,n,i; float stack[50],c;for(i=0; i < l ;i++) if ((n=m[i])<0) { c="st[p--];" switch(n) { case 1: stack[p]+="c;" break; case 2: stack[p]-="c;" break; case 3: stack[p]*="c;" break; case 4: stack[p]/="c;" } } else stack[++p]="n;" return(stack[p]); }

Розглянемо іншу задачу. Нехай потрібно ввести деяку послідовність символів, що закінчується крапкою, і надрукувати неї в зворотному порядку (тобто якщо на вході буде "ABcEr-1." те на виході повинне бути "1-rEcBA"). Представлена нижче програма спочатку уводить усі символи послідовності, записуючи них у стек, а потім уміст стека друкується в зворотному порядку. Це основна особливість стека - чим пізніше елемент занесений у стек, тим раніш він буде витягнутий зі стека. Реалізація стека виконана в зв'язаному збереженні за допомогою покажчиків p і q на тип, іменований ім'ям STACK.

#include typedef struct st /* ?????????? ???? STACK */ { char ch; struct st *ps; } STACK; main() { STACK *p,*q; char a; p=NULL; do /* ?????????? ????? */ { a=getch(); q=malloc(sizeof(STR1)); q->ps=p; p=q; q->ch=a; } while(a!='.'); do /* ??????? ????? */ { p=q->ps;free(q);q=p; printf("%c",p->ch); } while(p->ps!=NULL); }

Стиснуте й індексне збереження лінійних списків