Операции с памятью; динамические структуры данных

Раздел 7. Операции с памятью. Динамические структуры данных Линейные списки. Стеки. Очереди. Стеки. Стеком называется упорядоченный набор элементов, в котором размещение новых и удаление существующих происходит с одного конца, называемого вершиной. В стеке реализуется дисциплина обслуживания LIFO: последний — вошел, первый — вышел. Различают аппаратный и программный стек. Аппаратный стек используется для хранения адресов возврата из функций и их аргументов. Программный стек – это пользовательская модель (структура) данных. Операции для работы со стеком Над стеком реализованы следующие операции: • инициализация стека init(s), где s — стек; • помещение элемента в стек push(s, i), где s — стек, i — помещаемый элемент (данное); • удаление элемента из стека i=pop(s); • получение верхнего элемента стека без его удаления i=stkTop(s), где s — стек; • получение количества элементов стека; • определение, пуст ли стек isempty(s): возвращает 1, если стек пустой, и 0 в противном случае. • вывод элементов стека stkPrint(s), где s — стек. Способы реализации стека Существует несколько способов реализации стека: • с помощью одномерного массива; • с помощью связанного списка; • с помощью класса объектно-ориентированного программирования. Реализация стека с помощью связанного списка: Элемент стека можно описать в виде следующей структуры: struct Stack { int elem; // элемент данного Stack* next; // указатель на такой же следующий элемент }; Инициализация стека void init (Stack* &stk) { Stack* tmp = new Stack; // выделяем память под стек tmp->next = NULL; // инициируем первый элемент нулем tmp->elem = 0; stk = tmp; } Помещение элемента в стек void push (Stack* &stk, int a) { Stack* tmp = new Stack; tmp->elem = a; tmp->next = stk; stk = tmp; } Извлечение элемента из стека (с удалением) int pop (Stack* &stk) { int elem; if(isEmpty(stk)) { cout << "Стек пуст! \n"; return 0; } elem = stk->elem; Stack* tmp = stk; stk = tmp->next; delete tmp; return elem; } Получение значения верхнего элемента стека без его удаления int getTop (Stack *stk) { if(isEmpty(stk)) { cout << "Стек пуст! \n"; return 0; } return stk->elem; } Определение пустоты стека bool isEmpty (Stack *stk) { if(stk->next == NULL) return true; else return false; } Вывод элементов стека void stkPrint (Stack *stk) { if(isEmpty(stk)) { cout << "Стек пуст! \n"; return 0; } do { cout << stk->elem << " "; stk = stk->next; } while(stk->next !=NULL); } Пример реализации стека с помощью связанного списка: int main () { Stack *stk; int n; int elem; init(stk); printf("Введите количество элементов в стеке: "); scanf ("%d", &n); for (int i=0; itop = 0; Помещение элемента в стек void push (struct stack *stk, float f) { if(stk->top < NMAX) { stk->elem[stk->top] = f; /* В элемент массива с индексом top записывается значение f */ stk->top++; /* После этого вершина стека, соответствующая количеству элементов в массиве, перемещается на 1 элемент влево */ } else printf ("Стек полон, элементов: % d! \n", stk->top); } Удаление элемента из стека Если в массиве, соответствующем стеку, есть элементы, то количество элементов уменьшается на 1. После этого возвращается последний элемент. float pop (struct stack *stk) { float elem; if((stk->top) > 0) { stk->top--; elem = stk->elem[stk->top]; // предыдущий (или последний) элемент return elem; } else { printf ("Стек пуст! \n"); return 0; } } Получение верхнего элемента стека без его удаления float stkTop (struct stack *stk) { if((stk->top) > 0) { return stk->elem[stk->top-1]; } else { printf ("Стек пуст! \n"); return 0; } } Получение количества элементов стека int getcount (struct stack *stk) { return stk->top; } Определение, пуст ли стек Если количество элементов в стеке равно 0, то стек пуст (возвращается 1). int isempty (struct stack *stk) { if(stk->top == 0) return 1; else return 0; } Вывод элементов стека Если стек не пуст, движемся от последнего элемента к началу массива с выводом элементов. void stkPrint (struct stack *stk) { int i; i=stk->top; // i - количество элементов в стеке if(isempty(stk) == 1) return; // стек пуст do { i--; printf ("%f\n", stk->elem[i]); } while(i>0); } Пример реализации стека с помощью одномерного массива (создать стек из n элементов и извлечь их из стека ): int main () { struct stack *stk; int i, n; float elem; stk = (struct stack*) malloc (sizeof (struct stack)); init(stk); printf ("Введите количество элементов в стеке: "); scanf_s ("%d", &n); for (i=0; i 0);   do   {     printf ("%x", pop(stk)); // вывод цифры (включая A...F 16-ой с.с.   } while(isempty(stk)==0);   getchar ();  getchar ();   return 0; } Результат выполнения: Очереди. Очередью называется упорядоченный набор элементов, которые могут удаляться с её начала и помещаться в её конец. Очередь организована согласно дисциплине обслуживания FIFO: первый --- вошел, первый  — вышел. Очередь в программировании используется, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Существует несколько способов реализации очереди: • с помощью одномерного массива; • с помощью связанного списка; • с помощью класса объектно-ориентированного программирования. Простейшие операции с очередью: init() --  инициализация очереди. insert (q, x) — помещение элемента x в конец очереди q (q — указатель на очередь); x=remove (q) — удаление элемента x из очереди q; isempty(q) — возвращает 1, если очередь пуста и 0 в противном случае; print (q) – вывод элементов очереди q. Рассмотрим реализацию очереди на базе массива. Используем массив и две переменные: frnt – позиция первого элемента в очереди; rear – позиция последнего элемента в очереди Изначально frnt=1 и rear=0. Очередь пуста, если rearfrnt = 1;   q->rear = 0;   return; } Добавление элемента в очередь void insert (struct queue *q, int x)  {   if(q->rear < QMAX-1) {     q->rear++;     q->qu[q->rear] =x;   }   else     printf ("Очередь полна! \n");   return; } Проверка, пуста ли очередь int isempty (struct queue *q) {   if(q->rear < q->frnt)     return 1;   else   return 0; } Вывод элементов очереди void print (struct queue *q)  {   int h;   if(isempty(q)==1) {     printf ("Очередь пуста! \n");     return;   }   for(h = q->frnt; h<= q->rear; h++)     printf ("%d ",q->qu[h]);   return; } Удаление элемента из очереди int remove (struct queue *q)  {   int x;   if(isempty(q)==1)  {     printf ("Очередь пуста! \n");     return(0);   }   x = q->qu[q->frnt];   q->frnt++;   return x; } Недостатком в предложенной реализации очереди является то, что очередь смещается в сторону старших адресов массива, что может вызвать скорое переполнение. Для устранения этого недостатка предложена другая реализация функции удаления элемента из очереди: int removex (struct queue *q)  {   int x, h;   if(isempty(q)==1)  {     printf ("Очередь пуста! \n");     return 0;   }   x = q->qu[q->frnt];   for(h = q->frnt; h < q->rear; h++)  {     q->qu[h] = q->qu[h+1];   }   q->rear—;   return x; } Пример реализации очереди с помощью одномерного массива (Создать очередь из 8 элементов. Вывести ее на экран. Поочередно удалить все элементы очереди). int main ()  {   struct queue *q;   int a;   system("chcp 1251");   system("cls");   q = (queue*) malloc (sizeof(queue));   init(q);   print(q);   for(int i=0;i<8;i++)  {     printf ("Введите элемент очереди: ");     scanf("%d", &a);     insert(q, a);   }   printf("\n");   print(q);   while(q->frnt <= q->rear)  {     a = remove(q);     printf ("\nУдален элемент %d\n", a);     print(q);   }   getchar();  getchar ();   return 0; } Результат выполнения Реализация очереди на базе односвязного линейного списка struct list  {   int field;   struct list *ptr; }; struct queue // очередь {   struct list *frnt, *rear; }; Инициализация очереди Очередь пуста если q->front = q->rear = 0. void init (struct queue *q)  {   q->frnt = 0;   q->rear = 0; } Проверка, пуста ли очередь int isempty (struct queue *q)  {   if(q->frnt==0)     return 1;   else     return 0; } Добавление элемента в очередь void insert (struct queue *q, int x)  {   if((q->rear==0) && (q->frnt==0))  {     q->rear = init(x);     q->frnt = q->rear;   }  else     q->rear = addelem(q->rear, x); } Вывод элементов очереди void print (struct queue *q)  {   struct list *h;   if(isempty(q)==1)  {     printf ("Очередь пуста! \n");     return;   }   for(h = q->frnt; h!= NULL; h=h->ptr)     printf("%d ",h->field);   return; } Удаление элемента из очереди int remove (struct queue *q)  {   struct list *temp;   int x;   if(isempty(q)==1)  {     printf ("Очередь пуста! \n");     return 0;   }   x = q->frnt->field;   temp = q->frnt;   q->frnt = q->frnt->ptr;   free(temp);   return x; } Получение первого элемента в очереди без его удаления int test (struct queue *q)  {   int x;   x = q->frnt->field;   return x; } Пример (Создать очередь из 8 элементов на базе ОЛС. Вывести ее на экран. Поочередно удалить все элементы очереди). int main()  {   struct queue *q;   int a;   system("chcp 1251");   system("cls");   q = (queue*) malloc(sizeof(queue*));   init(q);   print(q);   for(int i=0;i<8;i++)  {     printf ("Введите элемент очереди: ");     scanf_s ("%d", &a);     insert (q, a);   }   printf("\n");   print(q);   while(q->frnt != NULL)  {     a = remove(q);     printf ("\nУдален элемент %d\n", a);     print(q);   }   getchar();  getchar ();   return 0; } Результат выполнения