Списък (List)

Списъкът е подредена последователност от 

еднотипни елементи без определена дисциплина за 
тяхно включване и изключване. Стекът, опашката и 
декът могат да се разглеждат като частен случай на 
структурата списък. Най-простият случай на 
структурата е този, когато всеки елемент на списъка 
съдържа указател към следващия елемент:

start

NULL

...

1

Основните операции със структурата 

са:

 - 

Инициализиране

 на списъка (

INIT

).

 - 

Включване

 на елемент на списъка. 

Поради липсата на дисциплина, операцията е 

възможна в няколко варианта:

2.1.

включване в началото (

ADD_1

);

2.2.

включване по средата (

ADD_2

);

2.3.

включване в края (

ADD_3

)

 - 

Изключване/изтриване

 на елемент (аналогично 

на предходната операция):

3.1.

изтриване на първия елемент (

DEL_1

);

3.2.

изтриване на междинен елемент (

DEL_2

);

3.3.

изтриване на последния елемент (

DEL_3

);

Към изброените операции могат да се добавят и 

следните:
 - 

Проверка

 за празен списък (

EMPTY

).

 - 

Търсене

 на елемент (

SEARCH

);

2

Примерно описание на структурата списък:

struct elem

{int key; elem *next;} *start;

Инициализация на списък:

void init()
{ start=NULL;}

Включване на елемент в началото на списък:

void add1(int n)
{
  elem *p=start;
  start=new elem;
  start->key=n;
  start->next=p;
}

start

n

p=start

NULL

NULL

start

3

Включване на елемент в средата на списък преди друг, 

чиято стойност е 

k

. Тук се предполага, че елементът 

k

съществува:

void add2(int n, int k)    //n – е добавяната 
стойност
{
  elem *q;
  elem *p=start;
  while (p->key!=k)

       //търсене на елемент 

със 
       p=p->next;

//стойност k

  q=new (elem);

//създаване на нов елемент

  q->next=p->next;
  q->key=p->key;

//прехвърляне на ключовата 

  p->next=q;

       //стойност в *q

  p->key=n;

//запис на n в p

}

n

p

k

q

q -> next

NULL

4

Включване на елемент в средата на списъка след друг, 

чиято стойност е 

k (

предполага се, че елементът 

k

съществува):

void add3(int n, int k) //n – е добавяната 
стойност
{
  elem *q;
  elem *p=start;
  while (p->key!=k)

//търсене на елемент със 

       p=p->next;

//стойност k

  q=new elem;

//създаване на нов елемент

  q->key=n;

//задаване на ключова стойност

  q->next=p->next;

//вмъкване на 

  p->next=q;

//новосъздадения елемент

}

n

q->next

k

p->next

p

NULL

5

Включване на елемент в края на списък (ако не е 

известна ключовата стойност на последния елемент в 
списъка):

void add4(int n)
{
  elem *p=start, *q;
  q=new elem;

       //създаване на новия елемент

  q->key=n;        //задаване на ключовата му 
стойност
  q->next=NULL;     //елементът ще е последен в 
списъка
  while (p->next) //търсене на края на списъка
    p=p->next;
  p->next=q;     //свързване на елемента *q със 
списъка
}

q

start

n

p

NULL

6

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

int del1(int &n)

//Ключовата стойност на изтрития

{

//елемент се връща в главната функция

  elem *p=start;
  if (start)

      //проверка, дали списъкът не е 

празен
    {
      n=start->key;
      start=start->next;//задаване на нов начален 
адрес
      delete p;

//изтриване

      return 1;
    }
      else

 return 0;

//списъкът е празен

}

p=start

n

start

NULL

7

Изключване на елемент в средата на списък 

преди друг, чиято ключова стойност е 

k 

(известно е, 

че елементът съществува):

void del2(int &n, int k)    //Ключовата стойност на изтрития 
елемент
{

      //се връща в главната функция

  elem *q;
  elem *p=start;
  while (p->key!=k)

      //търсене на елемента със  

стойност k
      {
       q=p;
       p=p->next;
      }
    n=q->key;

//на практика се изтрива елемента *р 

    q->next=p->next;

//но ключовата му стойност k

    q->key=p->key; //се прехвърля в предходния елемент, като 

//старата му стойност се изтрива от списъка 

    delete p;
}

q
n

p
k

k

p->next

NULL

8