5. Программная реализация очереди на основе статического массива.
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
/////////////// Queue for int positive (x>0)
typedef struct {
int *queue;
int head;
int tail;
int size;
} QUEUE;
int Init(QUEUE* Queue, int nSize);
int Extract(QUEUE* Queue);
int Add(QUEUE* Queue, int nElement);
void Clear(QUEUE* Queue);
int GetSize(QUEUE* Queue);
void Free(QUEUE* Queue);
Программа реализации кольцевой очереди на основе статического массива – queue.cpp:
#include "queue.h"
/////////////// Queue for int positive (x>0)
//////////////////////////////////////////
int Init(QUEUE* Queue, int nSize)
{
Queue->queue = (int*)malloc(nSize*(sizeof(int)));
if (Queue->queue == NULL) return -1;
Queue->size = nSize;
Queue->head = 0;
Queue->tail = 0;
return nSize;
}
///////////////////////////////////////////
int Extract(QUEUE* Queue)
{
int w;
if (Queue->head == Queue->tail) return -1;
w = Queue->queue[Queue->head];
if (Queue->head == Queue->size - 1)
Queue->head = 0;
else
Queue->head++;
return w;
}
///////////////////////////////////////////
int Add(Q* Qu, int nEl)
{
if (Qu->tail +1 == Qu->head)
return -1; // Очередь заполнена - запись невозможна!
if (Qu->tail == Qu->size )
if( Qu->head > 1)
Qu->tail = 0;
else return -1;
Qu->queue[Qu->tail++] = nEl;
return 1;
}
///////////////////////////////////////////
void Clear(QUEUE* Queue)
{
Queue->head = 0;
Queue->tail = 0;
}
///////////////////////////////////////////
int GetSize(QUEUE* Queue)
{
if (Queue->head == Queue->tail)
return 0; // Очередь пуста
if (Queue->head < Queue->tail)
return (Queue->tail - Queue->head);
else
return (Queue->size - (Queue->head - Queue->tail));
}
///////////////////////////////////////////
void Free(QUEUE* Queue)
{
free(Queue->queue);
}
Списки и их организация.
1. Структура данных «список».
Список– это упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения и исключения.
2. Ссылки.
Ссылка – это информация о связи данного компонента структуры с другими. В языке С наиболее удобно реализовать ссылки на основе использования указателей. Таким образом, компонент списка всегда состоит из двух частей:
Содержание
Ссылка
В качестве содержания может выступать любой тип данных, в том числе и агрегированный (т.е. массив или структура). В качестве ссылки – один или множество указателей, ссылающихся на элементы рассматриваемого списка.
3. Линейные списки – основные операции.
Список, отражающий отношение соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке; список нулевой длины называется пустым списком. Линейные списки являются простейшими динамическими структурами данных.
Графически связи в списках удобно изображать с помощью стрелок. Если компонента списка не связана ни с какой другой, то соответствующая ссылка остается пустой. Каждый список должен иметь особый элемент, называемый указателем начала спискаилиголовой списка, который по формату обычно отличен от остальных элементов. Список называетсяодносвязным, если в каждом его элементе используется только одна ссылка, связывающая текущий элемент со следующим.
1. Создание списка.
Эта операция предполагает определение указателя начала списка и присвоение ему NULL-значения (т.е. никакого).
2. Перебор элементов списка.
Эта операция выполняется для линейных списков очень часто и состоит в последовательном доступе к элементам списка – ко всем до конца списка либо до нахождения искомого элемента. Для каждого из перебираемых элементов осуществляется некоторая обработка его информационной части: сравнение с образцом, печать, модификация и прочее.
3. Вставка элемента в список.
Вставка элемента в середину односвязного списка показана на рис.4., а в начало – на рис. 5.
Рис. 4. Вставка элемента в середину односвязного списка
Рис. 5. Вставка элемента в начало односвязного списка
4. Удаление элемента из списка.
Удаление элемента из списка показано на рис.6.
Рис. 6. Удаление элемента из односвязного списка
На практике в односвязных списках используется преимущественно операция удаления элемента, следующего за данным или в начале списка, так как проход по всему списку - слишком дорогостоящая операция. Получается, также, что невозможно быстро удалить текущий элемент.
5. Перестановка элементов списка.
Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера на рис.7 приведена перестановка двух соседних элементов списка.
Рис. 7. Перестановка соседних элементов односвязного списка
Кроме указанных, можно придумать и другие операции. Но приведенные операции достаточно полно продемонстрировали основные принципы их реализации для односвязных списков.