2015-05-13
406
Первая очередь:
Элемент 12
Элемент 13
Элемент 14
Вторая очередь:
Очередь пустая.
Заполнение второй очереди
Первая очередь:
Очередь пустая.
Вторая очередь:
Элемент 12
Элемент 13
Элемент 14
Удаление элементов из второй очереди
Удален из q2: 12
Удален из q2: 13
Удален из q2: 14
Вторая очередь:
Очередь пустая.
Стек
Стек (или магазин) – другая часто встречающаяся динамическая структура данных, которая отличается от очереди тем, что организована по принципу LIFO (Last In, First Out – “ последний вошел, первый вышел ”). Операция включения и удаления элемента в стеке выполняется только с одного конца, называемого вершиной стека (head).
Когда новый элемент помещается в стек, то прежний верхний элемент “ проталкивается ” вниз и становится временно недоступным. Когда же верхний элемент удаляется с вершины стека, предыдущий элемент “ выталкивается ” наверх и снова является доступным. Кроме того, верхний элемент можно “ просмотреть ”, не удаляя его из стека.
Стеки широко используются при анализе текста программ компилятором, например, при проверке баланса пар скобок, при вызове функций и передаче аргументов, при использовании рекурсивных функций, которые будут рассмотрены ниже.
|
|
|
Пример. Демонстрация работы со стеком (STACK). В программе вершина стека объявлена как переменная-указатель на указатель (**head), поскольку адрес вершины стека будет меняться при включении и удалении нового верхнего элемента в стек. Для работы со стеком использованы функции:
· push () – добавить новый элемент на вершину стека;
· pop () – извлечь (вытолкнуть) элемент из вершины стека;
· peek () – прочитать значение верхнего элемента, не удаляя его из стека.
Программа:
#include<stdio.h>
#include<alloc.h> /* функции динамического управления памятью */
#include<conio.h>
#define STACK struct stack /* новое имя шаблона */
STACK { /* шаблон элемента стека */
int info; /* поле информации элемента стека */
STACK *next; /* поле ссылки на следующий элемент стека */
};
void push (STACK **head, int item) /* функция добавления элемента */
{ STACK *new; /* указатель нового элемента */
new=(STACK*) malloc(sizeof(STACK)); /* память для элемента */
new->info = item; /* заполнение поля информации элемента */
new->next = *head; /* ссылка нового элемента на старую голову */
*head = new; /* на вершине стека новый элемент */
}
int pop (STACK **head, int *error) /* функция удаления элемента */
{ STACK *old = *head; /* ссылка на “старую” голову стека */
int info = 0; /* исходное возвращаемое значение */
if (*head) /* если стек не пустой */
{ info = old ->info; /* информация удаляемого элемента*/
*head = old ->next; /* первый в стеке – следующий элемент */
free (old); /* удаление элемента из стека и памяти */
*error = 0; /* элемент удален успешно */
|
|
|
}
else *error=1; /* ошибка удаления элемента из пустого стека */
return (info); /* возврат значения функции */
}
int peek (STACK **head, int *error) /* функция информации об элементе */
{
if (*head) /* если стек не пустой */
{ *error = 0; /* отсутствие ошибки */
return (*head)->info; /* возврат информации о первом элементе */
}
else /* если стек пустой */
{ *error = 1; /* наличие ошибки */
return 0; /* возврат значения функции */
}
}
void main() /* главная функция */
{ int error, i; /* переменные ошибки и цикла */
STACK *st1, *st2; /* указатели двух стеков */
clrscr (); /* очистка экрана */
printf ("Заполнение 1-го стека:\n");
push (&st1, 42); /* запись в стек очередного элемента */
printf(" peek(st1) = %d\n", peek(&st1, &error)); /* информация об элементе */
push (&st1, 53); /* запись в стек очередного элемента */
printf(" peek(st1) = %d\n", peek(&st1, &error)); /* информация об элементе */
push (&st1, 72); /* запись в стек очередного элемента */
printf(" peek(st1) = %d\n", peek(&st1, &error)); /*информации об элементе */
push (&st1, 86); /* запись в стек очередного элемента */
printf(" peek(st1) = %d", peek(&st1, &error)); /* информация об элементе */
printf (" –элемент на вершине 1-го стека \n");
puts ("Запись элементов 1-го стека в 2-ой и вывод данных 2-го стека:");
for (i=1; i<=4; i++) /* цикл по элементам стека */
push (&st2, pop(&st1, &error)); /* запись элементов 1-го стека во 2-ой */
for (i=1; i<=4; i++) /* цикл по элементам стека */
printf(" pop(st2) = %d - элемент %i\n",
pop(&st2, &error), i); /* вывод данных из 2-го стек */
getch(); /* задержка экрана результатов */
}
Результаты программы:
Заполнение 1-го стека:
peek (st1) = 42
peek (st1) = 53
peek (st1) = 72
peek (st1) = 86 - элемент на вершине 1-го стека
Запись элементов 1-го стека в 2-ой и вывод данных 2-го стека:
pop (st2) = 42 – элемент 1
pop (st2) = 53 – элемент 2
pop (st2) = 72 – элемент 3
pop (st2) = 86 – элемент 4
Списки
Очередь и стек являются частными случаями более широкого класса динамических структур данных – связанных списков. Список – это совокупность объектов (элементов списка), в которой каждый объект содержит и информацию о местоположении (указатель) связанного с ним объекта. В простейшем виде элемент списка представляет собой структурную переменную, содержащую указатель (или указатели) на другой элемент(ы) и любое число других полей, называемых информационными.
Односвязный (однонаправленный) список, в котором каждый элемент имеет указатель на следующий элемент (next) и поля данных, причем последний элемент имеет значение указателя NULL, можно представить схемой:
Кольцевой список образуется, когда указатель последнего элемента ссылается на первый элемент согласно схеме:
 | ||
 |
|
|
|
|
|
Кольцевой двунаправленный список можно получить, если в предыдущем варианте списка задать в указателе next последнего элемента ссылку на первый элемент, в указателе pred первого элемента – ссылку на последний элемент.
Пример. Демонстрация работы кольцевого двунаправленного списка. В программе можно ввести в произвольном порядке некоторые слова, например, фамилии студентов, которые вставляются в список в алфавитном порядке. Прием слов заканчивается после ввода слова конец. Упорядоченный список выводится на экран.
Программа:
#include<stdio.h>
#include<conio.h>
#include<alloc.h> /* функции динамического выделения памяти */
#include<string.h> /* для функции strcmp() */
#define NAME_SIZE 30 /* максимальная длина слов */
#define LIST struct LIST /* идентификатор структуры элемента списка */
|
|
|
LIST { /* шаблон структуры списка */
char data [NAME_SIZE]; /* поле данных (для слов) */
LIST *next; /* указатель на следующий элемент */
LIST *pred; /* указатель на предшественника */
};
LIST *insert (LIST *elem, char name[]); /* прототип функции включения */
void main() /* главная программа */
{ char name [NAME_SIZE]; /* массив для слов */
LIST *head; /* указатель на голову списка */
LIST *tek; /* текущий указатель */
clrscr(); /* очистка экрана */
head = (LIST*) malloc(sizeof(LIST)); /* блок памяти для головы списка */
head->pred = head->next = head; /* инициирование указателей головы списка на себя */
puts ("Ввод данных (для окончания введите слово - конец.):");
for (;;) /* цикл создания связного списка */
{ printf ("Введите слово (фамилию): ");
gets (name);
if (strcmp (name, "конец") == 0) break; /* конец ввода данных */
if (insert(head, name) == NULL) /*включение нового элемента в список */
{ printf("Не хватает динамической памяти!\n"); /* ошибка распределения*/
exit(1); /* аварийный выход их программы */
}
}
puts ("\nВывод упорядоченного списка:");
for (tek = head->next; tek!= head; tek = tek->next) /* цикл по элементам */
printf ("%s\n", tek->data); /* вывод из поля данных */
puts ("Работа закончена!");
getch(); /* задержка экрана результатов */
}
/* Функция insert () резервирует память для нового элемента списка, копирует введенное в него слово и вставляет новый элемент в список в алфавитном порядке. Возвращает либо указатель на новый элемент, либо NULL, если для создания нового элемента не хватило памяти:
*/
LIST *insert(LIST *head, char name[])
{ LIST *tek, /* текущий указатель */
*new_elem; /* указатель на новый элемент */
/* Просмотр списка, пока не будет обнаружен элемент, поле данных которого имеет значение большее или равное введенному слова (по коду символов):
*/
for (tek = head->next;
(tek!= head) && strcmp(name, tek->data) > 0; tek = tek->next);
/* Зарезервировать память для нового элемента, поместить введенное слово в поле данных и вставить новый элемент перед тем, на который показывает указатель tek:
*/
if ((new_elem = (LIST*)malloc(sizeof(LIST)))!= NULL) /* блок памяти для нового элемента*/
{
strncpy (new_elem->data, name, NAME_SIZE); /* копирование слова name в поле data */
new_elem->next = tek; /* указатель next показывает на элемент tek */
new_elem->pred = tek->pred; /* указатель pred нового элемента показывает на предыдущий элемент */
|
|
|
/* Изменить указатель next в элементе перед вставленным (теперь он должен показывать на вставленный элемент), и изменить указатель pred в элементе, следующем за вставленным (он также должен показывать на вставленный элемент):
*/
(new_elem->pred)->next = new_elem; /* предыдущий элемент указывает на новый элемент */
tek->pred = new_elem; /* текущий элемент указывает на новый элемент */
}
return (new_elem); /* возврат указателя на новый элемент */
}
Результаты программы:
Ввод данных (для окончания введите слово – конец).
Введите слово (фамилию): Сидоров
Введите слово (фамилию): Иванов
Введите слово (фамилию): Петров
Введите слово (фамилию): конец
Вывод упорядоченного списка
Иванов
Петров
Сидоров
Работа закончена!
