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

В останньому елементі збереження (кінець списку) покажчик на сусідній елемент має значення NULL. Одержуваний список зображений на мал.2.

Рис.2. Зв'язне збереження лінійного списку.

Операції зі списками при послідовному збереженні

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

Нехай мається лінійний список з цілими значеннями і для його збереження використовується масив d (з числом елементів 100), а кількість елементів у списку вказується перемінної l. Реалізація зазначених раніше операцій над списком представляється наступними фрагментами програм які використовують оголошення:

float d[100]; int i,j,l; 1) ??????? ???????? ??????? ???????? (?????) if (?<0 || ?>l) printf("\n ????? ????????"); else printf("d[%d]=%f ",?,d[?]); 2) ????????? ????????, ?? ???????? ?? i-??? ?????? if (?>=l) printf("\n ????? ?????????? "); l--; for (j=?+1;j<="1" if ????? i-???? ??????? ???? ??????? 3) d[j]="d[j+1];">=l) printf("\n ????? ??????"); else printf("\n %d %d",d[?-1],d[?+1]); 4) ????????? ?????? ???????? new ?? i-??? ?????? if (?==l || ?>l) printf("\n ?? ????? ??????"); else { for (j=l; j>i+1; j--) d[j+1]=d[j]; d[i+1]=new; l++; } 5) ???????? ????????????? ?????? ? ?????????? ??1,??2,...,?l ? ?????? K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l ???, ??? K1'= K1. { int t=1; float aux; for (i=2; i<=l; i++) if (d[i]=2; j--) d[j]=d[j-1]; t++; d[i]=aux; } }

Схема руху індексів i,j,t і значення aux=d[i] при виконанні приведеного фрагмента програми приведена на мал.3.

Рис.3. Рух індексів при виконанні операцій над списком у послідовному збереженні.

Кількість дій Q, необхідних для виконання приведених операцій над списком, визначається співвідношеннями: для операцій 1 і 2 - Q=1; для операцій 3,4 - Q=l; для операції 5 - Q=l*l.

Помітимо, що взагалі операцію 5 можна виконати при кількості дій порядку l, а операції 3 і 4 для включення і виключення елементів наприкінці списку, що часто зустрічаються при роботі зі стеками, - при кількості дій 1.

Більш складна організація операцій потрібно при розміщенні в масиві d декількох списків, або при розміщенні списку без прив'язки його початку до першого елемента масиву.

Операції зі списками при зв'язному збереженні

При простому зв'язаному збереженні кожен елемент списку являє собою структуру nd, що складається з двох елементів: val - призначений для збереження елемента списку, n - для покажчика на структуру, що містить наступний елемент списку. На перший елемент списку вказує покажчик dl. Для всіх операцій над списком використовується опис:

typedef struct nd { float val; struct nd * n; } ND; int i,j; ND * dl, * r, * p;

Для реалізації операцій можуть використовуватися наступні фрагменти програм:

1) печатка значення i-го елемента

r=dl;j=1; while(r!=NULL && j++n ; if (r==NULL) printf("\n ????? ????? %d ",i); else printf("\n ??????? %d ???????? %f ",i,r->val);

2) печатка обох сусідів вузла(елемента), обумовленого покажчиком p (див. мал.4)

Рис.4. Схема вибору сусідніх елементів.

if((r=p->n)==NULL) printf("\n ????? ?????? ????????"); else printf("\n ????? ???????? %f", r->val); if(dl==p) printf("\n ????? ?????? ???????" ); else { r=dl; while( r->n!=p ) r=r->n; printf("\n ????? ????? %f", r->val); }

3) видалення елемента, що випливає за вузлом, на який указує р (див. мал.5)

Рис.5. Схема видалення елемента зі списку.

if ((r=p->n)==NULL) printf("\n ????? ??????????"); p->n=r->n; free(r->n);

4) вставка нового вузла зі значенням new за елементом, визначеним покажчиком р (див. мал.6)

Рис.6. Схема вставки елемента в список.

r=malloc(1,sizeof(ND)); r->n=p->n; r->val=new; p->n=r;

5) часткове упорядкування списку в послідовність значень , s+t+1=l, так що K1'=K1; після упорядкування покажчик v указує на елемент K1' (див. мал.7)

Рис.7. Схема часткового упорядкування списку.

ND *v; float k1; k1=dl->val; r=dl; while( r->n!=NULL ) { v=r->n; if (v->valn=v->n; v->n=dl; dl=v; } else r=v; }

Кількість дій, необхідних для виконання зазначених операцій над списком у зв'язаному збереженні, оцінюється співвідношеннями: для операцій 1 і 2 - Q=l; для операцій 3 і 4 - Q=1; для операції 5 - Q=l.

Організація двохзв‘язних списків

Зв'язане збереження лінійного списку називається списком із двома зв'язками або двозв‘язним списком, якщо кожен елемент збереження має два компоненти покажчика (посилання на попередній і наступний елементи лінійного списку).

У програмі двозв‘язний список можна реалізувати за допомогою описів:

typedef struct ndd { float val; /* ???????? ???????? */ struct ndd * n; /* ???????? ?? ????????? ??????? */ struct ndd * m; /* ???????? ?? ?????????? ??????? */ } NDD; NDD * dl, * p, * r;