Связные списки. Очередь

1.

СВЯЗНЫЕ СПИСКИ.
ОЧЕРЕДЬ

2.

ОЧЕРЕДЬ
Очередь –линейный список, организованный по принципу первый
пришел – последний ушел (FIFO – first in first out).
Бывает однонаправленная и двунаправленная
Голова (вершина) очереди – самый верхний элемент
Хвост (конец) очереди – самый нижний (последний) элемент
Добавление новых элементов допустимо только с хвоста очереди.
Удаление существующих элементов допустимо только с головы очереди

3.

ОЧЕРЕДЬ
Однонапрвленная
struct FIFO {
int data;
struct FIFO *next;
};
Двунаправленная
struct FIFO {
int data;
struct FIFO *next;
struct FIFO *prev;
};

4.

ОЧЕРЕДЬ
Добавление
Удаление
Неразрушающий просмотр

5.

ДОБАВЛЕНИЕ
Создать временный указатель
Выделить место
Записать данные в информационное поле
Указатель next сделать NULL
Проверить хвост
Если NULL
Хвост=временный указатель
Иначе
Хвост->Next = временный указатель
Хвост = временный указатель
Вернуть голову

6.

ДОБАВЛЕНИЕ
struct FIFO * create(struct FIFO *tail, int x)
{
struct FIFO *n;
n = (struct FIFO *)malloc(sizeof(struct FIFO));
n->next = NULL;
n->data = x;
if (tail == NULL)
{
tail= n;
}
else
{
tail->next=n;
tail=n;
}
return tail;
}

7.

ДОБАВЛЕНИЕ
void create(struct FIFO **head, struct FIFO **tail, int x)
{
struct FIFO *n;
n = (struct FIFO *)malloc(sizeof(struct FIFO));
n->next = NULL;
n->data = x;
if (*head == NULL)
{
*head = n;
*tail = n;
}
else
{
(*tail)->next=n;
*tail=n;
}
}

8.

УДАЛЕНИЕ
Если голова не NULL
Голова = голова ->next;
Вернуть голову
Иначе
Вернуть NULL

9.

УДАЛЕНИЕ
struct FIFO *pop(struct FIFO * head)
{
if (head != NULL)
{
head = head->next;
return head;
}
else return NULL;
}

10.

УДАЛЕНИЕ
void pop(struct FIFO **head, struct FIFO ** tail)
{
if (*head != NULL)
{
*head = (*head)->next;
}
else
{
*tail=NULL;
}
}

11.

ПРОСМОТР
Создать временный указатель
Временный указатель = голова
Пока временный указатель не равен NULL
Вывод на экран информационного поля временного указателя
Передвинуть временный указатель на следующий элемент

12.

ПРОСМОТР
struct FIFO *p = head;
while (p != NULL)
{
printf("%d -->", p->data);
p = p->next;
}

13.

ПРИМЕР 1
Создать очередь из натуральных чисел до N. Вывести на экран.

14.

ПРИМЕР 2
Создать очередь из чисел введенных пользователем. Вывести
на экран.
Посчитать сумму элементов

15.

ПРИМЕР 3
Создать очередь из чисел введенных пользователем. Вывести
на экран. Удалить первые K чисел

16.

ПРИМЕР 4
Найти максимальное значение в очереди. Удалить все
элементы до/после него

17.

ОЧЕРЕДЬ ДВУНАПРАВЛЕННАЯ
struct FIFO {
int data;
struct FIFO *next;
struct FIFO *prev;
};

18.

ОЧЕРЕДЬ ДВУНАПРАВЛЕННАЯ
Добавление
Удаление
Неразрушающий просмотр

19.

ДОБАВЛЕНИЕ
Создать временный указатель tmp
Выделить место
Записать данные в информационное поле
Указатель tmp->next сделать NULL
Указатель tmp->prev сделать NULL
Проверить хвост
Если NULL
Хвост=временный указатель
Иначе
tmp->prev = хвост
Хвост->Next = tmp
хвост = tmp
Вернуть хвост

20.

ДОБАВЛЕНИЕ
struct FIFO * create(struct FIFO *tail, int x)
{
struct FIFO *n;
n = (struct FIFO *)malloc(sizeof(struct FIFO));
n->next = NULL;
n->prev = NULL;
n->data = x;
if (tail == NULL)
{
tail= n;
}
else
{
n->prev=tail;
tail->next=n;
tail=n;
}
return tail;
}

21.

ДОБАВЛЕНИЕ
void create(struct FIFO **head, struct FIFO **tail, int x)
{
struct FIFO *n;
n = (struct FIFO *)malloc(sizeof(struct FIFO));
n->next = NULL;
n->prev = NULL;
n->data = x;
if (*head == NULL)
{
*head = n;
*tail = n;
}
else
{
n->prev=(*tail);
(*tail)->next=n;
*tail=n;
}
}

22.

УДАЛЕНИЕ
Удаление только с головы!
Если голова не NULL
голова = голова ->next;
голова->prev =NULL;
Вернуть голову
Иначе
Вернуть NULL

23.

УДАЛЕНИЕ
struct FIFO *pop(struct FIFO * head)
{
if (head != NULL)
{
head = head->next;
head->prev=NULL;
return head;
}
else return NULL;
}

24.

УДАЛЕНИЕ
void pop(struct FIFO **head, struct FIFO ** tail)
{
if (*head != NULL)
{
*head = (*head)->next;
(*head)->prev=NULL;
}
else
{
*tail=NULL;
}
}

25.

ПРОСМОТР
С головы:
Создать временный указатель
Временный указатель = голова
Пока временный указатель не равен NULL
Вывод на экран информационного поля временного указателя
Передвинуть временный указатель на следующий элемент
С хвоста:
Создать временный указатель
Временный указатель = хвост
Пока временный указатель не равен NULL
Вывод на экран информационного поля временного указателя
Передвинуть временный указатель на предыдущий элемент

26.

ПРОСМОТР
struct FIFO *p = head;
while (p != NULL)
{
printf("%d -->", p->data);
p = p->next;
}
struct FIFO *p = tail;
while (p != NULL)
{
printf("%d -->", p->data);
p = p->prev;
}

27.

ПРИМЕР 5
Создать двунаправленную очередь из натуральных чисел до N. Вывести
на экран.

28.

ПРИМЕР 6
Первая очередь упорядочена по возрастанию, вторая по
убыванию. Создать третью упорядоченную по неубыванию.