Лекции по структури от данни и програмиране


стек ще наричаме списък, при който включването на нови елементи, както и изключването на елементи се извършва само от едната страна на списъка, наречена връх



страница2/4
Дата25.07.2016
Размер0.95 Mb.
#6569
ТипЛекции
1   2   3   4

стек ще наричаме списък, при който включването на нови елементи, както и изключването на елементи се извършва само от едната страна на списъка, наречена връх на стека; възможен е пряк достъп само до елемента, който се намира във върха на стека; синоним на стек е термина LIFO (last in – first out); примери:

  • извиканата функция трябва да знае къде да върне управлението на извикващата функция, когато приключи нейното изпълнение; за целта адресът за връщане се добавя в стек, както при рекурсивно, така и при нерекурсивно обръщение;

  • стек се използва при разпределяне и освобождаване на памет за автоматичните променливи;

  • стек се използва от компилатора при пресмятане на изрази;


опашка се нарича списък, при който операцията включване на елемент е допустим само за единия край на списъка, който се нарича край на опашката, а операцията изключване на елемент е допустима само за другия край на списъка, който се нарича начало на опашката; възможен е пряк достъп само до елемента, който се намира в началото на опашката; синоним на опашка е термина

FIFO (first in – first out); примери:



  • обикновено компютрите имат един процесор и ако той се използва едновременно от няколко потребители, тогава се създава опашка за заявките за ползване на процесора;

  • буферите за вход и изход са организирани като опашка;

  • по една компютърна мрежа се предават информационни пакети; във всеки възел на мрежата постъпват пакети, те се подреждат в опашка и след това се разпределят един по един към тяхната крайна дестинация;


дек се нарича списък, при който всички добавяния и изключвания на елементи могат да се извършват както в единия, така и в другия край; в практиката понякога се използват декове при които в някой от краищата е забранено добавянето или изключването на елементи – наричат се декове с ограничен вход или изход;
13. Последователен списък и стек. Основни операции.
за представяне на последователни списъци се използва последователно разпределена памет, т.е. елементи на списъка се записват в последователно разположени полета в оперативната памет на компютъра – това означава, че разполагането е от вида:

loc (xk+1) = loc (xk) + C

тук loc (xk) е адресът на елемента xk, константата C най-често е дължината в байтове на един елемент от списъка;

в общия случай loc (xk) = L0 + C*k, където L0 е адресът на хипотетичен елемент x0, който предхожда първия елемент x1 на списъка;


алгоритъм за добавяне на елемент:

n++; x[n] = addvalue;


алгоритъм за изключване на елемент:

savevalue = x[n]; n--;


недостатъкът на тези алгоритми е, че те не отчитат случаите при които няма достатъчно памет за добавяне на нов елемент или когато се прави опит за изключване на елемент от празен стек;

ще ги модифицираме, нека M е максималният допустим за върха на стека;


алгоритъм за добавяне на елемент:

ако n==M, препълване; край;

ако n < M, n++; x[n] = addvalue;
алгоритъм за изключване на елемент:

ако n==0, празен стек; край;

ако n > 0, savevalue = x[n]; n--;
примерна програма (със средствата на C)
#include

#include

#define M 100

typedef float ElementType;

struct Stack {

int t;


ElementType StackArray[M];

} ;


void push (struct Stack *s, ElementType x)

{ if (s->t == M)

{ printf (“Препълване на стека!\n”);

exit (1);

}

s->StackArray[s->t++] = x;



}

ElementType pop ( struct Stack *s)

{ ElementType x;

if (s->t==0)

{ printf (“Празен стек!\n”);

exit (1);

}

x = s->StackArray[--s->t];



return x;

}

void main ()



{ Stack s; int i;

s.t = 0;


for (i = 1; i <= 100; i++)

push (&s, 1.1f);

for (i = 1; i <= 100; i++)

printf ("%.2f\n", pop (&s));

}
14. Последователна опашка. Основни операции.
при организация на последователни опашки се използват два номера на елементи f и r; f указва елемент, който се намира непосредствено преди първия елемент в опашката и r е номерът на последния елемент в опашката;
алгоритъм за добавяне на елемент:

r = r+1, x[r] = addvalue


алгоритъм за изключване на елемент:

f = f +1, savevalue = x[f]


тази реализация на основните операции с опашка е твърде разточителна по отношение на памет, тъй като при добавяне и изключване на елементи, опашката се движи в паметта; удачно е тези алгоритми да се използват когато опашката често става празна и в този случай запълването може да започне отново в началото на участъка от паметта, разпределен за опашката;
друга реализация на опашка е методът на пръстена – при този метод се счита, че елементите образуват затворен контур в паметта с дължина M елемента – това означава, че след елемента с номер M стои елементът с номер 1; така ако общия брой на елементите не надхвърля M-1 е възможно добавяне и изключване на елементи без това да води до недостиг на оперативна памет;

за удобство ще номерираме елементите от 0 до M-1;


алгоритъм за добавяне на елемент:

r = (r+1) mod M, x[r] = addvalue


алгоритъм за изключване на елемент:

f = (f+1) mod M, savevalue = x[f]


тъй като са възможни конфликтни ситуации при добавяне на елемент към пълна опашка или при изключване на елемент от празна опашка, алгоритмите за добавяне и изключване могат да се модифицират;
алгоритъм за добавяне на елемент:

ако (r+1) mod M == f, препълване, стоп

иначе r = (r+1) mod M, x[r] = addvalue
алгоритъм за изключване на елемент:

ако r == f, празна опашка, стоп

иначе f = (f+1) mod M, savevalue = x[f]
примерна програма (със средствата на C):
#define M 100

#include

#include

typedef float ElementType;

struct Queue {

int r, f;

ElementType QueueArray[M];

} ;


void pushq (struct Queue *q, ElementType x)

{ if ( (q -> r + 1) % M == q -> f)

{ printf (“Препълване!\n”);

exit (1);

}

q -> r = (q -> r + 1) % M;



q -> QueueArray[q -> r] = x;

}

ElementType popq (struct Queue *q)



{ if (q -> r == q -> f)

{ printf (“Празна опашка!\n”);

exit (1);

}

q -> f = (q -> f + 1) % M;



return q -> QueueArray[q -> f];

}
void main ()

{ struct Queue mem = { 0, 0 } ; //създаване на празна опашка

ElementType y = 3.14f; int i;

for (i = 1; i <= 99; i++)

pushq (&mem, y+=1.1f);

for (i = 1; i <= 99; i++)

printf ("%.2f\n", popq (&mem));

}
15. Свързан списък. Създаване.
при свързаните списъци последователните елементи се съхраняват на различни места в оперативната памет, а не в последователно разположени полета; връзката между отделните елементи се осъществява чрез указател към следващия елемент; ако елементът е последен в списъка, стойността на този указател трябва да бъде някаква различима стойност (например NULL);

за задаване на списък е достатъчен указател към първия елемент на списъка; съпоставка между последователен и свързан списък:



  • при последователния списък освен адреса на първия елемент трябва да се знае и максималният брой елементи, които ще участват в списъка; при свързан списък няма нужда предварително да се знае този брой;

  • в свързан списък лесно може да се добавя или изключва елемент на произволно място вътре в списъка, докато при последователен списък трябва допълнително да се разместват елементите;

  • обединяването на списъци е лесно изпълнима операция при свързани списъци за разлика от последователните списъци;

  • при свързаните списъци за всеки елемент е нужна памет за указателите, при последователните от такива указатели няма нужда;

  • при свързаните списъци достъпът до елементите е неефективен; например за да се достигне до последния елемент на списъка трябва да се премине през всички останали; това не е така при последователните списъци – там с константна сложност можем да достигнем до произволен елемент на списъка;

в общия случай елементите на свързаните списъци се състоят от две полета – info (данните, записани в елемента) и link (указател към следващия елемент);


примерна програма (със средствата на C):
#include

#include

#include

struct Student {

unsigned long nomer;

float sr_uspeh;

struct Student *next;

} ;


void main ()

{ int n; char c;

struct Student *first, *ps;

n = sizeof (Student);

first = NULL; //създаване на празен списък

do {
ps = (struct Student *) malloc (n);

if (ps == NULL)

{ printf (“Няма свободна памет!\n”);

exit (1);

}

printf (“Въведете фак. номер: “);



scanf (“%lu”, &ps->nomer);

printf (“Въведете ср. успех: “);

scanf (“%f”, &ps->sr_uspeh);

ps -> next = first;

first = ps;

printf (“Край на въвеждането (Y/N) ?: “);

fflush (stdin);

c = getchar ();

} while ( c != ‘y’ && c != ‘Y’);

}
16. Търсене на елемент по ключ. Добавяне на нов елемент в свързан списък.


ще разгледаме функция, която търси елемент в свързан списък с определен ключ и го актуализира; ще използваме средствата на C++; елементите ще имат тип Student:

struct Student {

unsigned long nomer;

float sr_uspeh;

struct Student *next;

} ;
void Search (Student *first, unsigned long key, float value)

{ Student *ptr = first;

while (ptr != NULL)

if (ptr -> nomer == key)

break;


else ptr = ptr -> next;

if (ptr != NULL) ptr -> sr_uspeh = value;

else cout << “Няма елемент с номер “ << key << “!” << endl;

}
ще разгледаме функция за добавяне на нов елемент в свързан списък след k-тия елемент (k  1); ще използваме средствата на C++; елементите ще имат тип Student;


void add (Student *first, int k)

{ int i = 1;

Student *ptr = first, *ptr1;

while ( i < k && ptr != NULL)

{ i++; ptr = ptr -> next; }

if (ptr == NULL)

{ cout << “Няма “ << k << “ елемента в списъка!” << endl;

return;


}

ptr1 = new Student;

if (ptr1 == NULL)
{ cout << “Няма свободна памет!” << endl;

return;


}

ptr1 -> next = ptr -> next;

ptr -> next = ptr1;

cout << “Въведете факултетен номер: “;

cin >> ptr1 -> nomer;

cout << “Въведете среден успех: “;

cin >> ptr1 -> sr_uspeh;

}


17. Пример за обектно-ориентирана реализация на свързан списък.
в примера се използват два шаблона на класове List и ListNode, като всеки обект на класа List е свързан списък от обекти на класа ListNode; програмата дава възможност да се извършват следните операции над списъци:

  • добавяне на елемент в началото на списъка;

  • добавяне на елемент в края на списъка;

  • изключване на елемент от началото на списъка;

  • изключване на елемент от края на списъка;

  • завършване обработката на списъка;

ще използваме средствата на ANSI C++;
файл listnode.h
#ifndef LISTNODE_H

#define LISTNODE_H

template class List;

template

class ListNode {

friend class List ;

public:

ListNode (const NodeType &);



NodeType getData () const;

private:


NodeType data;

ListNode *next;

} ;

template



ListNode ::ListNode (const NodeType &info)

: data (info), next (NULL) { }

template

NodeType ListNode ::getData () const

{ return data; }

#endif
файл list.h


#ifndef LIST_H

#define LIST_H

#include

#include

#include “listnode.h”

using std::cout;

using std::endl;

template

class List {

public:


List ();

~List ();

void insertAtBeg (const NodeType &);

void insertAtEnd (const NodeType &);

bool removeFromBeg (NodeType &);

bool removeFromEnd (NodeType &);

bool isEmpty () const;

void print () const;

private:

ListNode *first;

ListNode *last;

ListNode * getNewNode (const NodeType &);

} ;

template



List ::List () : first (NULL), last (NULL)

{ }


template

List ::~List ()

{ if (!isEmpty())

{ cout << “Изключване на обекти: “;

ListNode *current = first, *temp;

while (current != NULL)

{ temp = current;

cout << temp -> data << ‘\n’;

current = current -> next;

delete temp;

}

}

cout << “Всички обекти са изключени!” << endl;



}

template

bool List::isEmpty () const

{ return first==NULL; }

template

ListNode *List ::getNewNode

(const NodeType &value)

{ ListNode *ptr = new ListNode (value);

assert (ptr != NULL);

return ptr;

}

template



void List ::insertAtBeg (const NodeType &value)

{ ListNode *ptr = getNewNode (value);

if ( isEmpty () )

first = last = ptr;

else { ptr -> next = first;

first = ptr;

}

}

template



void List ::insertAtEnd (const NodeType &value)

{ ListNode *ptr = getNewNode (value);

if ( isEmpty () )

first = last = ptr;

else { last -> next = ptr;

last = ptr;

}

}

template



bool List::removeFromBeg (NodeType &value)

{ if ( isEmpty () ) return false;

ListNode *temp = first;

if (first == last)

first = last = NULL;

else first = first -> next;

value = temp -> data;

delete temp;

return true;

}

template



bool List::removeFromEnd (NodeType &value)

{ if ( isEmpty () ) return false;

ListNode *temp = last;

if (first == last)

first = last = NULL;

else { ListNode *current = first;

while (current -> next != last)

current = current -> next;

last = current;

last -> next = NULL;

}

value = temp -> data;



delete temp;

return true;

}

template



void List::print () const

{ if ( isEmpty () )

{ cout << “Списъкът е празен!\n”;

return;


}

cout << “Списък: “;

ListNode *current = first;

while (current != NULL)

{ cout << current -> data << ‘ ‘;

current = current -> next;

}

cout << endl;



}

#endif
файл testlist.cpp


#include “list.h”

using std::cin;

void instructions ();

template

void testList ( List &listObject, const char *type)

{ cout << “Тестване на списък със стойности от тип “ << type



<< endl;

instructions ();

int choice;

T value;


do {

cout << “? “;

cin >> choice;

switch (choice)

{ case 1 : cout << “Въведете “ << type << “: “;

cin >> value;

listObject.insertAtBeg (value);

listObject.print ();

break;

case 2 : cout << “Въведете “ << type << “: “;



cin >> value;

listObject.insertAtEnd (value);

listObject.print ();

break;


case 3 : if (listObject.removeFromBeg (value))

cout << value << “ е изключен от списъка\n”;

else cout << “Неуспешно изключване\n”;

listObject.print ();

break;

case 4 : if (listObject.removeFromEnd (value))



cout << value << “ е изключен от списъка\n”;

else cout << “Неуспешно изключване\n”;

listObject.print ();

break;


}

} while (choice != 5);

cout << “Край на тестването на списъка” << endl;

}

void instructions ()



{ cout << “Въведете номера на действието:\n”;

cout << “1 – за включване в началото на списъка\n”;

cout << “2 – за включване в края на списъка\n”;

cout << “3 – за изключване от началото на списъка\n”;

cout << “4 – за изключване от края на списъка\n”;

cout << “5 – за завършване обработката на списъка\n”;

}

void main ()



{ List integerList;

testList (integerList, “цяло число”);

List doubleList;

testList (doubleList, “число с плаваща точка”);

}
18. Свързан стек. Основни операции.
със средствата на C++ ще опишем основните операции – включване и изключване на елементи за свързан стек, т.е. стек представен чрез свързан списък;
#include

using std::cout;

typedef int INFOTYPE;

struct Stack

{ INFOTYPE info;

Stack *next;

} ;

void push (Stack *&s, INFOTYPE x)



{ Stack *p;

if ( (p = new Stack) == NULL)

{ cout << “Няма свободна памет”;

exit (1);

}

p -> info = x;



p -> next = s;

s = p;


}

INFOTYPE pop (Stack *&s)

{ INFOTYPE x;

Stack *p;

if (!s) { cout << “Стекът е празен\n”;

exit (1);

}

x = s -> info;



p = s;

s = s -> next;

delete p;

return x;

}

void main ()



{ INFOTYPE y; Stack *stack = NULL;

y = 10;


push (stack, y);

y = pop (stack);

y = pop (stack);

}
19. Пример за обектно-ориентирана реализация на свързан стек.


ще се възползваме от тясната връзка между свързаните списъци и стекове и при реализацията на клас за стек повторно ще използваме класа List; ще разгледаме две разновидности на повторното използване:

  • реализиране на клас за стек чрез закрито наследяване на класа List;

  • реализиране на клас за стек чрез влагане на класа List;

двата класа ще реализираме като шаблони, за да могат да се използват повторно;
файл stack.h
#ifndef STACK_H

#define STACK_H

#include “list.h”

template

class Stack : private List {

public :


void push (const StackType &value)

{ insertAtBeg (value); }

bool pop (StackType &value)

{ return removeFromBeg (value); }

bool isStackEmpty () const

{ return isEmpty (); }

void printStack () const

{ print (); }

} ;

#endif
чрез закрито наследяване откритите функции елементи на базовия клас List стават закрити функции елементи на производния клас Stack; при реализацията на функциите елементи на класа Stack директно се използват функциите елементи на класа List, но те не са достъпни чрез открития интерфейс на класа Stack;


файл teststack.cpp
#include “stack.h”

void main ()

{ Stack intStack;

int popint, i;

cout << “Обработка на стек с цели числа” << endl;

for (i = 0; i < 4; i++)

{ intStack.push (i);

intStack.printStack ();

}

while (!intStack.isStackEmpty())



{ intStack.pop (popint);

cout << popint << “ е изключено от стека!” << endl;

intStack.printStack ();

}

Stack doubleStack;



double val = 1.1, popval;

cout << “Обработка на стек с числа с плаваща точка” << endl;

for (i = 0; i < 4; i++)

{ doubleStack.push (val);

doubleStack.printStack ();

val += 1.1;

}

while (!doubleStack.isStackEmpty())



{ doubleStack.pop (popval);

cout << popval << “ е изключено от стека!” << endl;

doubleStack.printStack ();

}

}


сега ще опишем шаблон на клас, който реализира стек чрез влагане на класа List;

файл stack-c.h
#ifndef STACK_C_H

#define STACK_C_H

#include “list.h”

template

class Stack {

public:


void push (const StackType &value)

{ s.insertAtBeg (value); }

bool pop (StackType &value)

{ return s.removeFromEnd (value); }

bool isStackEmpty () const

{ return s.isEmpty (); }

void printStack () const

{ s.print (); }

private:

List s;

} ;

#endif
откритият интерфейс на класа Stack не позволява на потребителя да използва функциите елементи от класа List, тъй като обектът s е закрит; за тестване на stack-c.h можем да използва същия файл



teststack.h с тази разлика, че в началото включваме stack-c.h вместо

stack.h;
20. Свързана опашка. Основни операции.


ще реализираме опашка с фиктивен елемент в началото; първият реален елемент на опашката е непосредствено след фиктивния;

опашката е празна, когато указателят към фиктивния елемент съвпада с указателя към края на опашката;


#include

using std::cout;

using std::endl;

typedef float InfoType;

struct Queue_El {

InfoType info;

Queue_El *next;

} ;


void enqueue (Queue_El *&r, InfoType x)

{ Queue_El *p = new Queue_El;

if (p==NULL)

{ cout << “Няма свободна памет!” << endl;

exit (1);

}

p -> info = x; p -> next = NULL;



r -> next = p; r = p;

}

InfoType dequeue (Queue_El *f, Queue_El *&r)



{ InfoType x; Queue_El *p = f -> next;

if (p==NULL) //еквивалентно е на f == r

{ cout << “Опашката е празна!” << endl;

exit (1);

}

f -> next = p -> next;



x = p -> info;

delete p;

if (f -> next == NULL) r = f;

return x;

}

void main ()



{ Queue_El Q = { 0, NULL}, *F = &Q, *R = F;

InfoType y = 3.14f;

enqueue (R, y);

y = dequeue (F, R);

}
21. Пример за обектно-ориентирана реализация на опашка.
ще разгледаме програма, която създава шаблон на класа Queue като използва закрито наследяване на класа List; функциите елементи, необходими за обработката на опашката по същество са реализирани в шаблона на класа List; този шаблон включва други функции елементи и не е желателно те да са достъпни за шаблона на класа Queue чрез открит интерфейс; поради това използваме закрито наследяване и в резултат всички функции елементи на шаблона на класа List стават закрити функции елементи в шаблона на класа Queue;
файл queue.h
#ifndef QUEUE_H

#define QUEUE_H

#include “list.h”

template

class Queue : private List {

public:


void enqueue (const QueueType &d)

{ insertAtEnd (d); }

bool dequeue (QueueType &d)

{ return removeFromBeg (d); }

bool isQueueEmpty () const

{ return isEmpty (); }

void printQueue () const

{ print (); }

} ;

#endif
файл testqueue.cpp


#include “queue.h”

void main ()

{ Queue intQueue;

int dequeueInt, i;

cout << “Обработка на опашка с цели числа” << endl;

for (i = 0; i < 4; i++)

{ intQueue.enqueue (i);

intQueue.printQueue();

}

while (!intQueue.isQueueEmpty())



{ intQueue.dequeue (dequeueInt);

cout << dequeueInt << “ е изключено!” << endl;

intQueue.printQueue ();

}

double dequeueDouble, val = 1.1;



Queue doubleQueue;

cout << “Обработка на опашка с числа с плаваща точка” << endl;

for (i = 0; i < 4; i++)

{ doubleQueue.enqueue (val);

doubleQueue.printQueue();

val += 1.1;

}

while (!doubleQueue.isQueueEmpty())



{ doubleQueue.dequeue (dequeueDouble);

cout << dequeueDouble << “ е изключено!” << endl;

doubleQueue.printQueue ();

}

}




22. Пример за определяне на принадлежност на низ към формален език.
формален език се дефинира с формална граматика Г = < N, T, S, P >, където N е множество от нетерминални символи, T е множество от терминални символи, S  N е начален нетерминал, P е множество от продукции, които имат синтактичен характер и те определят начина по който се строят думи в езика;

в този въпрос разглеждаме формалният език, породен от следната граматика Г = < { S }, { a, b, c}, S, { S -> aSa, S -> bSb, S -> c } >;

лесно се вижда, че езикът на тази граматика се състои от всички думи c, където  е получена от  чрез инвертиране и  се състои само от a, b;

ще разгледаме програма, която разпознава дали даден низ принадлежи на този език; за целта използваме следния алгоритъм:



  • въвеждаме низа в стек до срещане на c;

  • след това сравняваме останалите символи със символите в стека и ако има пълно съвпадение, то низът е в езика;

за реализацията ще опишем шаблон на стек;
файл stack2.h
#ifndef STACK2_H

#define STACK2_H

template

struct item {

T value;

item *next;


} ;

template

class Stack {

public:


Stack ();

~Stack ();

void push (const T&);

bool pop (T&);

T top () const;

bool isEmpty () const;

private:

item *first;

} ;

template



Stack ::Stack () : first (NULL) { }
template

Stack ::~Stack ()


{ item *ptr;

while (first)

{ ptr = first;

first = first -> next;

delete ptr;

}

}



template

void Stack ::push (const T&x)

{ item *ptr = new item ;

//считаме, че е включена опция за стандартно прекъсване при

//изпълнението на new когато няма свободна памет и за това

//не правим проверка дали операцията е успешна

ptr -> value = x;

ptr -> next = first;

first = ptr;

}

template



bool Stack ::pop (T &x)

{ if (isEmpty()) return false;

item *ptr = first;

first = first -> next;

x = ptr -> value;

delete ptr;

return true;

}

template



T Stack ::top () const

{ return first -> value; }

//предполагаме, че функцията top няма да се извиква за празен стек

template

bool Stack ::isEmpty () const

{ return first==NULL; }

#endif
сега ще опишем самата програма;
#include

#include "stack2.h"

using std::cin;

using std::cout;

using std::endl;

void Error ()

{ cout << "Низът не е от езика!" << endl; }

void main ()

{ Stack chStack;

char ch, R;

cout << "Въведете низ: ";

ch = cin.get ();

if (ch < 'a' || ch > 'c') { Error(); return; }

while (ch != 'c')

{ chStack.push (ch);

ch = cin.get ();

if ( ch < 'a' || ch > 'c') { Error(); return; }

}

ch = cin.get ();



if (ch != 'a' && ch != 'b' && ch != '\n') { Error(); return; }

while (ch != '\n')

{ if (!chStack.isEmpty())

if (ch != chStack.top())

{ Error(); return; }

else;


else { Error(); return; }

chStack.pop (R);

ch = cin.get ();

if (ch != 'a' && ch != 'b' && ch != '\n') { Error(); return; }

}

if (!chStack.isEmpty ()) { Error(); return; }



cout << "Низът е от езика!" << endl;

}
23. Топологично сортиране.


нека S е крайно множество; без ограничение S = { 1, 2, …, n};

нека в S е въведена релация ≺ ; ако a  S, b  S и a ≺ b, казваме че a предшества b; предполагаме, че релацията ≺ няма контури, т.е. няма последователност от вида a ≺ b ≺ … ≺ a;

при това положение, релацията ≺ може да се допълни до линейна наредба, т.е. да са изпълнени следните свойства:


  • за всеки x, y, z  S: от x ≺ y и y ≺ z  x ≺ z; (транзитивност)

  • за всеки x, y  S е изпълнено точно едно от x ≺ y и y ≺ x; (силна антисиметричност)

  • за всяко x  S имаме x ⊀ x; (антирефлексивност)

алгоритъмът, който допълва релацията ≺ до линейна наредба се нарича топологично сортиране и той е следния:



  1. намираме елемент s  S, който не се предшества от друг елемент и го извеждаме в края на опашката за извеждане;

  2. изключваме избрания елемент s от множеството S, заедно с всички връзки на s с други елементи;

  3. ако S   - премини към 1., иначе край;

в резултат получаваме пермутация

i1, i2, …, in на 1, 2, …, n и линейната наредба се определя по следния начин: a ≺ b, ако a = is, b = it и s < t;

ако на дадена стъпка не съществува елемент, който не се предшества от друг, то първоначалната релация ≺ е съдържала контури, което е недопустимо;


за реализацията ще използваме масив от |S| структури, по една за всеки елемент от S, като всяка структура съдържа поле count – броя на непосредствените предшественици на елемента и поле stack – стек, съдържащ непосредствените наследници на елемента;

елементите с count = 0 се обединяват в опашка в края на която след всяка стъпка се добавят новополучените елементи с count = 0; полетата за връзка в тази опашка се разполагат в полетата count, които са вече непотребни;

в програмата ще въведем ограничение за броя на елементите на S;

от входа постъпват броя на елементите и двойките a ≺ b на релацията ≺; въвеждането на двойки се преустановява с въвеждане на фиктивна двойка 0 0;


#include

#include “stack2.h”

#define max 100

using std::cin;

using std::cout;

using std::endl;

void main ()

{ int n, j, k, f, r = 0;

struct Elem {

int count;

Stack stack;

} x[max+1]; //номерацията започва от 1

do {

cout << “Въведете броя на елементите: “;



cin >> n;

} while (n < 0 && n > max);

for (k = 0; k <=n; k++) x[k].count = 0;

do {


do {

cout << “Въведете отношение или 0 0 за край: “;

cin >> j >> k; if ( j==0 && k==0) break;

} while ( j < 1 || k < 1 || j > max || k > max || j == k);

if (j==0 && k==0) break;

x[k].count++;

x[j].stack.push (k);

} while (1);

for (k = 1; k <= n; k++)

if (x[k].count==0)

{ x[r].count = k;

r = k;


}

f = x[0].count;

while (1) {

if (f==0 && n!=0)

{ cout << “Релацията съдържа контури!” << endl;

return;


}

if (f==0) break;

n--;

while ( x[f].stack.pop (k))



{ x[k].count--;

if (x[k].count==0)

{ x[r].count = k;

r = k;


}

}

f = x[f].count;



}

cout << “Линейна наредба:“;

f = x[0].count;

while (f != 0)

{ cout << “ “ << f; f = x[f].count; }

cout << endl;

}
24. Циклични списъци.
при цикличните списъци, за разлика от обикновените свързани списъци, в полето за връзка на последния елемент е записан адреса на първия елемент, т.е. последният елемент сочи към първия елемент на списъка; удобно е цикличните списъци да се задават с указател към последния елемент; ще разгледаме шаблон на класа CircleList, който реализира цикличен свързан списък с данни от тип T;

функциите insert и remove реализират добавяне и изключване елемент в началото на списъка;



файл circlelist.h

#ifndef CIRCLELIST_H

#define CIRCLELIST_H

#include

template

struct Elem {

T info;

Elem *link;



} ;

template

class CircleList {

public:


CircleList ();

~CircleList ();

void insert (const T&);

bool remove (T&);

private:

Elem *ptr;

} ;

template



CircleList::CircleList ()

{ ptr = NULL; }

template

CircleList::~CircleList ()

{ if (ptr == NULL) return;

Elem *first = ptr -> link;

ptr -> link = NULL;

while (first != NULL)

{ ptr = first;

first = first -> link;

delete ptr;

}

}



template

void CircleList::insert (const T& value)

{ Elem *newel = new Elem ;

newel -> info = value;

if (ptr != NULL) newel -> link = ptr -> link;

else ptr = newel;

ptr -> link = newel;

}

template



bool CircleList::remove (T& value)

{ if (ptr == NULL) return false;

value = ptr -> link -> info;

Elem *first = ptr -> link;

if (ptr == first) ptr = NULL;

else ptr -> link = first -> link;

delete first;

return true;

}

#endif
ще използваме циклични списъци за да реализираме алгоритъм за събиране на полиноми; полиномите ще са на три променливи x, y, z и ще се представят с циклични списъци от едночлени с фиктивен елемент в края на списъка; типът на елементите ще е структура със следните полета:



  • поле C – коефициента на едночлена;

  • поле S – ‘+’, ако елементът не е фиктивен и ‘-‘, ако е фиктивен елемент;

  • поле X – степента на x;

  • поле Y – степента на y;

  • поле Z – степента на z;

  • поле link – връзка към следващия елемент;

в алгоритъма ще предполагаме, че едночлените в един полином са подредени според стандартната лексикографска наредба – първо по намаляващи степени на x, после по намаляващи степени на у, после по намаляващи степени на z; също ще предполагаме, че в полиномите е извършено приведение на подобните едночлени;

алгоритъмът е следния:

(резултатът се получава в полинома, сочен от Q)



  • създаваме списъците за двата полинома; инициализираме указателите P и Q да сочат към началото съответно на първия и втория списък; инициализираме указателите P1 и Q1 да сочат към фиктивния елемент съответно на първия и втория списък;

  • докато P -> S != ‘-‘ или Q -> S != ‘-‘:

    • ако едночленът, сочен от P е по-нисък от едночлена,

сочен от Q или P сочи към фиктивен елемент –

Q1 = Q, Q = Q -> link;



    • ако едночленът, сочен от P е по-висок от едночлена,

сочен от Q или Q сочи към фиктивен елемент – добавяне на едночлена, сочен от P след едночлена, сочен от Q1,

Q1 = Q1 -> link, P1 = P, P = P -> link;



    • ако едночленът, сочен от P е подобен на едночлена, сочен от Q – актуализиране на коефициента на Q, P1 = P,

P = P -> link, ако коефициентът на едночлена, сочен от Q е станал 0 (и има поне два едночлена), изтриваме го,

Q = Q1 -> link, иначе Q1 = Q, Q = Q -> link;




файл sumpoly.cpp

#include

using std::cout;

using std::endl;

using std::cin;

struct Term {

double C;

char S;


int X, Y, Z;

};

struct Poly {



Term info;

Poly *link;

};

void add (Poly *P, Term &info)



{ Poly *newel = new Poly;

newel -> info = info;

newel -> link = P -> link;

P -> link = newel;

}

bool larger (Term &A, Term &B)



{ return ( A.X > B.X ||

( A.X == B.X && A.Y > B.Y ) ||

( A.X == B.X && A.Y == B.Y && A.Z > B.Z) );

}

void remove (Poly *P)



{ Poly *temp = P -> link;

P -> link = P -> link -> link;

delete temp;

}

void getPoly (Poly *&P, const char *name)



{ Term current;

cout << name << " полином: " << endl;

cout << "Въвеждането е в нарастващ лексикографски ред!" << endl;

cout << "Въведете коефициент, степен на X, степен на Y," << endl



<< " степен на Z или -1 -1 -1 -1 за край:" << endl;

do {


cin >> current.C >> current.X >> current.Y >> current.Z;

if (current.C == -1 && current.X == -1 &&

current.Y == -1 && current.Z == -1) break;

if (current.C == 0 || current.X < 0 ||

current.Y < 0 || current.Z < 0) continue;

current.S = '+';

add (P, current);

} while (1);

}

void printPoly (Poly *P)



{ cout << "Сумата в същия формат е: " << endl;

while (P -> info.S != '-')

{ if (P -> info.C == 0) cout << 0 << endl;

cout << P -> info.C << ' ' << P -> info.X



<< ' ' << P -> info.Y << ' ' << P -> info.Z << endl;

P = P -> link;

}

}

void main ()



{ const Term fict = { 0, '-', 0, 0, 0 };

Poly *P = new Poly, *Q = new Poly, *Q1 = Q, *P1 = P;

P -> info = fict; P -> link = P;

Q -> info = fict; Q -> link = Q;

getPoly (P, "Първи");

getPoly (Q, "Втори");

P = P1 -> link; Q = Q1 -> link;

while (P -> info.S != '-' || Q -> info.S != '-')

{ if (larger (Q -> info, P -> info) || P -> info.S == '-')

{ Q1 = Q; Q = Q -> link; }

else if (larger (P -> info, Q -> info) || Q -> info.S == '-')

{ add (Q1, P -> info); Q1 = Q1 -> link;

P1 = P; P = P -> link; }

else {


Q -> info.C += P -> info.C;

P1 = P; P = P -> link;

if (Q -> info.C == 0 && Q -> link != Q1)

{ remove (Q1); Q = Q1 -> link; }

else { Q1 = Q; Q = Q -> link; }

}

}



printPoly (Q->link);

}
25. Двусвързани списъци.


при двусвързаните списъци елементите имат полета за връзка както към следващия елемент, така и към предишния елемент; възможно е двусвързаният списък да е цикличен – тогава полето за връзка към предишния елемент за първия елемент е към последния елемент и полето за връзка към следващия елемент на последния елемент е към първия елемент; елементите на списъка можем да представим като тип структура:

template

struct Elem {

InfoType info;

Elem *next, *prev;

} ;
ще опишем функция insert за включване на елемент след указан елемент и функция remove за изключване на указан елемент от двусвързан списък; предполагаме, че списъкът има фиктивен елемент, така че при извикване на функцията insert ptr има стойност различна от NULL, а при функцията delete ptr не сочи към фиктивния елемент;


template

void insert ( Elem *ptr, InfoType x )

{ Elem *p;

if ( (p = new Elem ) == NULL )

{ cout << “Няма достатъчно памет!” << endl;

exit (1);

}

p -> info = x;



p -> prev = ptr;

p -> next = ptr -> next;

ptr -> next -> prev = p;

ptr -> next = p;

}
template

InfoType remove (Elem *ptr)

{ InfoType x = ptr -> info;

ptr -> prev -> next = ptr -> next;

ptr -> next -> prev = ptr -> prev;

delete ptr;

return x;

}
26. Графи.


списъците са удобно средство при решаване на много проблеми при създаване на алгоритми, но понякога се налага използването на

по-сложни от линейните структури от данни;




Сподели с приятели:
1   2   3   4




©obuch.info 2024
отнасят до администрацията

    Начална страница