Последователен списък.

13. Последователен списък.

Забележка

Информацията в тази статия се отнася изключително за стек. Също така не е динамичен - защото заделя константно количество памет и не си променя размера по-време-на-изпълнение. Освен това не е реализиран на C++ (а на чисто C). Реализацията печата на стандартния изход възникнали грешки - това е неприложимо на практика - използвайте изключения, връщайте подходяща стойност от функцията (указваща че операцията е неуспешна) или просто функцията abort()
Четете на собствена отговорност!

---

За представяне на последователни списъци се използва последователно разпределена памет, тоест - последователни елементи на списъка се записват в последователни полета в оперативната памет на компютъра. Това означава:
$Loc(x_{k + 1}) = Loc(x_k) + C$, където С е константа, най-често означаваща дължината в байтове на един елемент в списъка. В общия случай: $Loc(x_k) = L_0 + k * C$, където $L_0$ е адресът в оперативната памет на елемента $x_0$ на списъка.

Под динамика на структура от данни се разбира начин на включване и изключване на елемент от тази структура данни.

Динамика на последователни стекове:
<картинка>
А - стек, Х - елемент, който ще включваме или изключваме, Т - номер на елемента във върха на стека, А(Т) - елемента във върха на стека. ( Номерацията започва от 1!! )
Добавяне: $T = T + 1$, $A(T) = x$
Изключване: $x = A(T), T = T - 1$.

Недостатъкът при този алгоритъм е, че не се отчитат конфликтните случаи, при които не достига място в Оперативната памет за добавяне на нов елемент или се прави опит за изключване на елемент от празен стек. Нека с М означим максималния допустим номер на елемент в стек. Мофицираме алгоритмите до:

Добавяне: Т = Т + 1, ако Т > М, то Препълваме и спираме иначе А(Т) = х

Изключване: ако Т == 0, то Празен стек и спираме, иначе х = А(Т), Т = Т - 1.

Обикновени функции:
Много често последователните списъци и стекове се моделират чрез масив. За да направим по-модифицируеми функциите, се използват възможностите на С - дефиниране на макрос и име на нов тип.

Реализация на алгоритмите:

#define M 100
typedef float ELEMENT_TYPE;
 
struct Stack
{
    int t;
    ELEMENT_TYPE stack_array[M];
};
 
void push( Stack *s, ELEMENT_TYPE x )
{
    s->t++;
    if ( s->t > M )
    {
        printf(" \n Overflow ");
        exit(1);
    }
    s->stack_array[ s->t - 1 ] = x;
}
 
ELEMENT_TYPE pop( Stack *s )
{
    if ( s->t == 0 )
    {
        printf( " \n Empty Stack " );
        exit(1);
    }
 
    ELEMENT_TYPE     x;
    x = s->stack_array[s->t - 1];
    return x;
}
 
void main()
{
    Stack st = {0};
    ELEMENT_TYPE x = 3.14, y;
    push( &st, x );
    y = pop( &st );
}

Проверката дали стекът е празен и съобщението за грешка могат да се реализират с отделни функции.