Home > CLR, Кодинг, Компьютер, Проги, С++ > Связные списки

Связные списки

Что же такое список?

Связный список — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле.

Список бывает нескольких видов. Рассмотрим первый из них –  стек.

Стек – структура данных, работающая по принципу “первый вошел – последний вышел” (LIFO – Last In First Out). Чтобы было проще, можно представить себе запаянную с одного конца трубку, диаметром с монету. В эту трубку вы бросаете монетки так, чтобы они ложились друг на друга. Логично, что первая монетка находится в самом низу, и достать ее можно, вынув те монетки, лежащие сверху. К примеру, вот так создается структура списка в С++.

struct elements{

int data;

elements *next;

}

Как же создать этот список? Очень просто.  Вот кусок кода, позволяющий создать список из пяти элементов

int number = 5; //Количество элементов в списке
elements *p, *q;
//Собстаенно, элементы
p = NULL;
//Последний элемент ссылается на “пустоту”
for (int i = 0; i < number; i++)
{
q = (element*)calloc(1, sizeof(element));
//Выделение памяти
q->data = i+1;
//Записываем данные в элемент списка
q->next = p;
//Записываем адрес
p = q;
}

Очередь, в отличии от стека, работает по принципу “первый вошел – первый вышел” (FIFO – First In First Out). Еще одно отличие то, что в стеке известен адрес только текущего элемента, а в очереди – текущего, первого и последнего. Причем просмотр начинается с первого элемента, который обозначается буквой l (left), а запись идет после поледнего. Он обозначается буквой r (right). Создается он так же, как и стек, только необходимо сохранить адрес первого элемента.

Третий вид – циклический список. Такой же как и очередь, только последний элемент ссылается не на NULL, а на первый элемент.

Последний вид – двусвязный список. Каждый элемент ссылается одновременно на предыдущий и следующий.

struct elements{ int data;

elements *next;

elements *prev;

}

И где же используется стек? Он используется в ассемблере. К примеру, все знают задачу, в которой надо поменять местами значения двух переменных, не пользуясь третьей. Это легко осуществляется через ассеблер и стек.

Пусть переменные A, B – исходные.

int a, b;

a = 5; b = -3;

asm

{

MOV ax, a;  MOV bx, b;  PUSH ax;  PUSH bx;

POP bx;   POP ax;   MOV a, ax;   MOV b, bx;

}

Где, PUSH – поместить в стек, а POP – извлечь из стека.

Advertisements
  1. 17.03.2009 at 11:06

    Великолепно. Стока хорошего материала. Только обновляйтесь почаще )

  2. kirik444
    18.03.2009 at 16:24

    По мере воможностей буду.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: