7. Линейни структури от данни -- Основни структури от данни - 1 елемент, линейна структури, дървета, графи -- Основни операции (действия) с линейни стуктури: * достъп до елемент * обхождане (претърсване) * размяна на два елемента * добавяне на елемент * изтриване (премахване) на елемент -- Реализация (модел) на линейна структура с масив. Функции на С++ за основните операции. -- Успоредни масиви, таблици -- Сортировка на масив без разместване на елементите на масива. Индексни масиви, обратни индексни масиви Пример 1: масив C: масив A: индекси масив B: масив D: 2 - 4 [1] 5 - 2 3 - 5 [2] 1 - 4 5 - 9 [3] 2 - 5 4 - 8 [4] 4 - 8 1 - 2 [5] 3 - 9 A е масив от цели числа A[1], A[2], A[3], A[4], A[5] B е индексен масив на сортирания масив A A[B[1]] < A[B[2]] < A[B[3]] < A[B[4]] < A[B[5]] C е обратен индексен масив на A A[i] е на C[i]-то място в сортирания масив D D е сортираният масив A D[i]=A[B[i]] Пример 2. Кандидат-студентски списъци -- Матрици и представянето им като едномерни масиви * "пълна" mxn матрица a_ij --> масив b[0], b[1], ..., b[(i-1)*n+j-1], ..., b[(m-1)*n+(n-1)] * долна триъгълна mxn матрица a_ij --> масив b[0], b[1], ..., b[(2n-i)(i-1)/2+j-1], ... * разредени матрици -- Статични и динамични обекти * Статични обекти - за тях автоматично се резервира и освобождава памет (от операционната система в частите от ОП, определени за данни). Достъпът до статични обекти се осъществява посредством името на обекта (променливата). * Динамични обекти - за резервиране и освобождаване памет се грижи програмата (програмиста) в частта от ОП наречена heap. Достъпът до динамични обекти се осъществява посредством променливи от тип указатели. -- Динамична памет - операциите new и delete new <тип>; връща стойност адрес към променлива от указания тип delete <име на променлива от тип указател>; не връща стойност Премер 1: int *k; k=new int; *k=1; еквивалентво на: int *k=new int(1); Пример 2: class Point { private: double x,y; public: Point(double xx=0.0; double yy=0.0) {x=xx; y=yy;} ... }; Point *p1=new Point, *p2=new Point(1.5,2.0); -- Свързани списъци struct Item { int key; Item *next;//указател, съдържащ адрес на следващия елемент от списъка ... }; Item *pb; //указател към началото на свързания списък * Достъп до първия елемент от списъка: pb->key, pb->next Item *p; //yказател към текущия елемент до произволен елемент от списъка: p->key, p->next за последния елемент от списъка е вярно (p->next)==0 * Създаване на свързан списък от n елемента void CreateList(int n) { Item *p; //yказател към текущия елемент p=new Item; pb=p; for (int i=1; i<=n; i++) { (p->key)=random(100); (p->next)=new Item; p=(p->next); } (p->next)=0; } * Обхождане void TraceList() { Item *p; //yказател към текущия елемент p=pb; while ((p->next)!=0) { cout << (p->key); p=(p->next); } } * Pазмяна на два елемента void ExchangeList(Item *p1, Item *p2) { Item it; it=*p1; *p1=*p2; *p2=it; it.next=(p1->next); (p1->next)=(p2->next); (p2->next)=it.next; } * Добавяне на нов елемент ** в началото на списъка void AddBegList(Item *newp) { (newp->next)=pb; pb=newp; } ** в края на списъка void AddEndList(Item *newp, Item *endp) { (newp->next)=0; (endp->next)=newp; } ** в средата на списъка - след елемента, чийто адрес е в p void AddList(Item *newp, Item *p) { (newp->next)=(p->next); (p->next)=newp; } * Изтриване на елемент от списъка ** в началото на списъка void DelBegList() { Item *p; p=pb; pb=(pb->next); delete p; } ** в края на списъка - endp сочи предпоследния елемент от списъка void DelEndList(Item *endp) { delete (endp->next); (endp->next)=0; } ** в средата на списъка - след елемента, чийто адрес е в p void DelList(Item *p) { Item *pp; pp=(p->next); (p->next)=(pp->next); delete pp; } * Сортирани свързани списъци - търсене в свързан списък -- Двусвързани списъци struct Item { int key; Item *next;//указател, съдържащ адрес на следващия елемент от списъка Item *pred;//указател, съдържащ адрес на предишния елемент от списъка ... }; Item *pb; //указател към началото на свързания списък -- Топологично сортиране * Частична наредба ацикличен насочен граф или множество S с зададена наредба (<) между някои от елементите му със свойствата: 1. транзитивност - ако x struct Leader { int key, count; void *tr; //cannot write Trailer *tr because Trailer is not yet defined Leader *next; }; struct Trailer { Leader *id; Trailer *next; }; Leader *head=new Leader; void Create(); Leader *L(int x); void Zero(); void Tsort(); void main() { Create(); Zero(); Tsort(); } void Create() { Leader *p, *q; int x, y; Trailer *t; head=0; cout << endl; cin >> x; while (x) { cin >> y; p=L(x); q=L(y); t = new Trailer; t->id=q; t->next=(Trailer *)(p->tr); //casting because tr is defined as void p->tr=t; (q->count)++; cin >> x; } } Leader *L(int x) { Leader *p, *q; p=head; q=p; // q is the last element of the list if (p) { while (p) { if ((p->key)==x) return p; q=p; p=p->next; } } p = new Leader; p->key=x; p->count=0; p->tr=0; p->next=0; if (q) q->next=p; else head=p; return p; } void Zero() { Leader *p, *q; p=head; head=0; while (p) { q=p; p=p->next; if (!(q->count)) { q->next=head; head=q; } } } void Tsort() { Leader *p, *q; Trailer *t; q=head; while (q) { cout << (q->key) << ' '; t=(Trailer *)q->tr; //casting because tr is defined as void q=q->next; while (t) { p=t->id; (p->count)--; if (!(p->count)) { p->next=q; q=p; } t=t->next; } } } ----------------------------------------