Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Динамические структуры данных: очереди и стеки

Содержание

ОчередиОчередь – динамическая структура данных с упорядоченным доступом к элементам, функционирующая по принципу FIFO. FirstInFirstOut
Лекция 15Динамические структуры данных: очереди и стеки ОчередиОчередь – динамическая структура данных с упорядоченным доступом к Последовательное хранениеТипы и переменныеtypedef struct{ TYPE *list; int size,count,head,tail;} QUEUE; Создание очередиint Create(QUEUE *queue,int sz){ queue->list = (TYPE*)calloc(sz,sizeof(TYPE)); if(!queue->list) return 0; queue->size Удаление очередиvoid Clear(QUEUE *queue){ if(queue->list) free(queue->list); queue->list = NULL; queue->size = queue->count Помещение элемента в очередьint Put(QUEUE *queue, TYPE val){ if(queue->count == queue->size) return Изъятие элемента из очередиint Get(QUEUE *queue, TYPE *val){ if(queue->count == 0) return ПримерРеализовать программу, которая в интерактивном режиме запрашивает у пользователя команду и выполняет Программаint main(int argc, char *argv[]){ QUEUE q; Create(&q,20); while(1){ char cmd[21]; Связанное хранениеТипы и переменные:typedef struct _ELEMENT{ TYPE value; struct _ELEMENT *next;} ELEMENT;typedef struct{ ELEMENT *head, *tail;}QUEUE; Создание и удаление очередиvoid Create(QUEUE *queue){ queue->head = queue->tail = NULL;}void Clear(QUEUE Помещение элемента в очередьint Put(QUEUE *queue, TYPE val){ ELEMENT *tmp = (ELEMENT*)malloc(sizeof(ELEMENT)); Изъятие элемента из очередиint Get(QUEUE *queue, TYPE *val){ if(!queue->head) return 0; ELEMENT СтекСтек – динамическая структура данных c упорядоченным доступом к элементам, функционирующая по принципу LIFO.LastInFirstOut Последовательное хранениеТипы и переменные:typedef struct{ TYPE *list; int size,head;} STACK; Создание стекаint Create(STACK *stack, int sz){ stack->list = (TYPE*)calloc(sz,sizeof(TYPE)); if(!stack->list) return 0; Удаление стекаvoid Clear(STACK *stack){ if(stack->list) free(stack->list); stack->list = NULL; stack->head = 0; stack->size = 0;} Помещение элемента в стекint Push(STACK *stack, TYPE val){ if(stack->head == stack->size-1) return Изъятие элемента из стекаint Pop(STACK *stack, TYPE *val){ if(stack->head == -1) return ПримерРеализовать программу, которая в интерактивном режиме запрашивает у пользователя команду и выполняет Программаint main(int argc, char *argv[]){ STACK q; Create(&q,20); while(1){ char cmd[21]; Связанное хранениеТипы и переменные:typedef struct _ELEMENT{ TYPE value; struct _ELEMENT *next;} ELEMENT;typedef ELEMENT* STACK; Создание и удаление стекаvoid Create(STACK *stack){ *stack = NULL;}void Clear(STACK *stack){ while(*stack){ Помещение элемента в стекint Push(STACK *stack, TYPE val){ ELEMENT *tmp = (ELEMENT*)malloc(sizeof(ELEMENT)); Изъятие элемента из стекаint Pop(STACK *stack, TYPE *val){ if(!*stack) return 0; ELEMENT
Слайды презентации

Слайд 2 Очереди
Очередь – динамическая структура данных с упорядоченным

ОчередиОчередь – динамическая структура данных с упорядоченным доступом к элементам, функционирующая по принципу FIFO. FirstInFirstOut

доступом к элементам, функционирующая по принципу FIFO.



First
In
First
Out

Слайд 3 Последовательное хранение

Типы и переменные

typedef struct{
TYPE *list;
int

Последовательное хранениеТипы и переменныеtypedef struct{ TYPE *list; int size,count,head,tail;} QUEUE;

size,count,head,tail;
} QUEUE;

Слайд 4 Создание очереди
int Create(QUEUE *queue,int sz)
{
queue->list = (TYPE*)calloc(sz,sizeof(TYPE));

Создание очередиint Create(QUEUE *queue,int sz){ queue->list = (TYPE*)calloc(sz,sizeof(TYPE)); if(!queue->list) return 0;

if(!queue->list) return 0;
queue->size = sz;
queue->count = queue->head

= queue->tail = 0;
return 1;
}

Слайд 5 Удаление очереди
void Clear(QUEUE *queue)
{
if(queue->list) free(queue->list);
queue->list =

Удаление очередиvoid Clear(QUEUE *queue){ if(queue->list) free(queue->list); queue->list = NULL; queue->size =

NULL;
queue->size = queue->count = 0;
queue->head = queue->tail

= 0;
}

Слайд 6 Помещение элемента в очередь
int Put(QUEUE *queue, TYPE val)
{

Помещение элемента в очередьint Put(QUEUE *queue, TYPE val){ if(queue->count == queue->size)

if(queue->count == queue->size) return 0;
queue->list[queue->tail++] = val;
if(queue->tail

== queue->size) queue->tail = 0;
queue->count++;
return 1;
}

Слайд 7 Изъятие элемента из очереди
int Get(QUEUE *queue, TYPE *val)
{

Изъятие элемента из очередиint Get(QUEUE *queue, TYPE *val){ if(queue->count == 0)

if(queue->count == 0) return 0;
*val = queue->list[queue->head++];
if(queue->head

== queue->size) queue->head = 0;
queue->count--;
return 1;
}

Слайд 8 Пример
Реализовать программу, которая в интерактивном режиме запрашивает у

ПримерРеализовать программу, которая в интерактивном режиме запрашивает у пользователя команду и

пользователя команду и выполняет ее.

Команды:
exit – завершение программы,
put N

– помещение N в очередь,
get – изъять элемент из очереди и вывести его значение на экран.

Дополнительно программа должна выводить сообщения о невозможности выполнения операции

Слайд 9 Программа
int main(int argc, char *argv[])
{
QUEUE q;
Create(&q,20);

: "); gets(cmd); if(strncmp(cmd,"exit",4)==0) break; if(strncmp(cmd,"put",3)==0){ char *tail = NULL; value = strtol(&cmd[3],&tail,10); if(strlen(tail)==0){ if(!Put(&q,value)) puts("Очередь заполнена!"); } else puts("Некорректная команда"); }else if(strcmp(cmd,"get")==0){ if(Get(&q,&value)) printf("%d\n",value); else puts("Очередь пуста!"); } else puts("Неизвестная команда!"); } Clear(&q); return 0;}">Программаint main(int argc, char *argv[]){ QUEUE q; Create(&q,20); while(1){ char cmd[21];

while(1){
char cmd[21]; int value;
printf(">: ");

gets(cmd);
if(strncmp(cmd,"exit",4)==0) break;
if(strncmp(cmd,"put",3)==0){
char *tail = NULL;
value = strtol(&cmd[3],&tail,10);
if(strlen(tail)==0){
if(!Put(&q,value)) puts("Очередь заполнена!");
} else puts("Некорректная команда");
}else if(strcmp(cmd,"get")==0){
if(Get(&q,&value)) printf("%d\n",value);
else puts("Очередь пуста!");
} else puts("Неизвестная команда!");
}
Clear(&q);
return 0;
}

Слайд 10 Связанное хранение

Типы и переменные:

typedef struct _ELEMENT{
TYPE value;

Связанное хранениеТипы и переменные:typedef struct _ELEMENT{ TYPE value; struct _ELEMENT *next;} ELEMENT;typedef struct{ ELEMENT *head, *tail;}QUEUE;

struct _ELEMENT *next;
} ELEMENT;
typedef struct{
ELEMENT *head, *tail;
}QUEUE;

Слайд 11 Создание и удаление очереди
void Create(QUEUE *queue)
{
queue->head =

Создание и удаление очередиvoid Create(QUEUE *queue){ queue->head = queue->tail = NULL;}void

queue->tail = NULL;
}

void Clear(QUEUE *queue)
{
while(queue->head){
ELEMENT *tmp

= queue->head;
queue->head = tmp->next;
free(tmp);
}
queue->tail = NULL;
}

Слайд 12 Помещение элемента в очередь
int Put(QUEUE *queue, TYPE val)
{

Помещение элемента в очередьint Put(QUEUE *queue, TYPE val){ ELEMENT *tmp =

ELEMENT *tmp = (ELEMENT*)malloc(sizeof(ELEMENT));
if(!tmp) return 0;
tmp->next =

NULL;
tmp->value = val;
if(queue->tail) queue->tail->next = tmp;
queue->tail = tmp;
if(!queue->head) queue->head = queue->tail;
return 1;
}

Слайд 13 Изъятие элемента из очереди
int Get(QUEUE *queue, TYPE *val)
{

Изъятие элемента из очередиint Get(QUEUE *queue, TYPE *val){ if(!queue->head) return 0;

if(!queue->head) return 0;
ELEMENT *tmp = queue->head;
queue->head =

tmp->next;
*val = tmp->value;
free(tmp);
if(!queue->head) queue->tail = NULL;
return 1;
}

Слайд 14 Стек
Стек – динамическая структура данных c упорядоченным доступом

СтекСтек – динамическая структура данных c упорядоченным доступом к элементам, функционирующая по принципу LIFO.LastInFirstOut

к элементам, функционирующая по принципу LIFO.

Last
In
First
Out

Слайд 15 Последовательное хранение

Типы и переменные:

typedef struct{
TYPE *list;
int

Последовательное хранениеТипы и переменные:typedef struct{ TYPE *list; int size,head;} STACK;

size,head;
} STACK;

Слайд 16 Создание стека
int Create(STACK *stack, int sz)
{
stack->list =

Создание стекаint Create(STACK *stack, int sz){ stack->list = (TYPE*)calloc(sz,sizeof(TYPE)); if(!stack->list) return

(TYPE*)calloc(sz,sizeof(TYPE));
if(!stack->list) return 0;
stack->head = -1;
stack->size =

sz;
return 1;
}

Слайд 17 Удаление стека
void Clear(STACK *stack)
{
if(stack->list) free(stack->list);
stack->list =

Удаление стекаvoid Clear(STACK *stack){ if(stack->list) free(stack->list); stack->list = NULL; stack->head = 0; stack->size = 0;}

NULL;
stack->head = 0;
stack->size = 0;
}

Слайд 18 Помещение элемента в стек
int Push(STACK *stack, TYPE val)
{

Помещение элемента в стекint Push(STACK *stack, TYPE val){ if(stack->head == stack->size-1)

if(stack->head == stack->size-1) return 0;
stack->list[++stack->head] = val;
return

1;
}

Слайд 19 Изъятие элемента из стека
int Pop(STACK *stack, TYPE *val)
{

Изъятие элемента из стекаint Pop(STACK *stack, TYPE *val){ if(stack->head == -1)

if(stack->head == -1) return 0;
*val = stack->list[stack->head--];
return

1;
}

Слайд 20 Пример
Реализовать программу, которая в интерактивном режиме запрашивает у

ПримерРеализовать программу, которая в интерактивном режиме запрашивает у пользователя команду и

пользователя команду и выполняет ее.

Команды:
exit – завершение программы,
push N

– помещение N в стек,
pop – изъять элемент из стека и вывести его значение на экран.

Дополнительно программа должна выводить сообщения о невозможности выполнения операции

Слайд 21 Программа
int main(int argc, char *argv[])
{
STACK q;
Create(&q,20);

: "); gets(cmd); if(strncmp(cmd,"exit",4)==0) break; if(strncmp(cmd,"push",4)==0){ char *tail = NULL; value = strtol(&cmd[4],&tail,10); if(strlen(tail)==0){ if(!Push(&q,value)) puts("Стек заполнен!"); } else puts("Некорректная команда"); }else if(strcmp(cmd,"get")==0){ if(Pop(&q,&value)) printf("%d\n",value); else puts("Стек пуст!"); } else puts("Неизвестная команда!"); } Clear(&q); return 0;}">Программаint main(int argc, char *argv[]){ STACK q; Create(&q,20); while(1){ char cmd[21];

while(1){
char cmd[21]; int value;
printf(">: ");

gets(cmd);
if(strncmp(cmd,"exit",4)==0) break;
if(strncmp(cmd,"push",4)==0){
char *tail = NULL;
value = strtol(&cmd[4],&tail,10);
if(strlen(tail)==0){
if(!Push(&q,value)) puts("Стек заполнен!");
} else puts("Некорректная команда");
}else if(strcmp(cmd,"get")==0){
if(Pop(&q,&value)) printf("%d\n",value);
else puts("Стек пуст!");
} else puts("Неизвестная команда!");
}
Clear(&q);
return 0;
}

Слайд 22 Связанное хранение
Типы и переменные:

typedef struct _ELEMENT{
TYPE value;

Связанное хранениеТипы и переменные:typedef struct _ELEMENT{ TYPE value; struct _ELEMENT *next;} ELEMENT;typedef ELEMENT* STACK;

struct _ELEMENT *next;
} ELEMENT;
typedef ELEMENT* STACK;

Слайд 23 Создание и удаление стека
void Create(STACK *stack)
{
*stack =

Создание и удаление стекаvoid Create(STACK *stack){ *stack = NULL;}void Clear(STACK *stack){

NULL;
}

void Clear(STACK *stack)
{
while(*stack){
ELEMENT *tmp = *stack;

*stack = tmp->next;
free(tmp);
}
}

Слайд 24 Помещение элемента в стек
int Push(STACK *stack, TYPE val)
{

Помещение элемента в стекint Push(STACK *stack, TYPE val){ ELEMENT *tmp =

ELEMENT *tmp = (ELEMENT*)malloc(sizeof(ELEMENT));
if(!tmp) return 0;
tmp->next =

*stack;
tmp->value = val;
*stack = tmp;
return 1;
}
  • Имя файла: dinamicheskie-struktury-dannyh-ocheredi-i-steki.pptx
  • Количество просмотров: 136
  • Количество скачиваний: 0
- Предыдущая Реализация политики занятости молодежи на примере работы государственного казенного учреждения Волгоградской области
Следующая - Аттестационная работа. Индивидуальный образовательный маршрут

Похожие презентации

Системы счисления Системы счисления 115
мультимедиа мультимедиа 131
Задачи на блок-схемы. Линейный алгоритм Задачи на блок-схемы. Линейный алгоритм 133
Компьютерные вирусы!! Компьютерные вирусы!! 127
Сбалансированные деревья поиска Сбалансированные деревья поиска 116
От первых счётных приборов до персональных компьютеров От первых счётных приборов до персональных компьютеров 147
Y2K problem Y2K problem 98
Информация и компьютер Информация и компьютер 191
Программное обеспечение (ПО) Программное обеспечение (ПО) 159
Моделирование в среде графического редактора PAINT Моделирование в среде графического редактора PAINT 127
Файлы и файловая система Файлы и файловая система 162
АТД дерево - общее представление АТД дерево - общее представление 118
Control: operators, loops, conditions Control: operators, loops, conditions 140
Презентация по информатике на тему: Правила набора текста. Перемещение по тексту Презентация по информатике на тему: Правила набора текста. Перемещение по тексту 156
Алгоритмы ветвления Алгоритмы ветвления 117
Логика на уроках информатики Логика на уроках информатики 141
Интернет - урок Интернет - урок 176
Общие сведения о разрезах (с использованием программы КОМПАС-3D) Общие сведения о разрезах (с использованием программы КОМПАС-3D) 118
ИНФОРМАЦИЯ. Виды и свойства ИНФОРМАЦИЯ. Виды и свойства 146
Устройства компьютера Устройства компьютера 120
Кодирование и обработка информации Кодирование и обработка информации 136
Единицы измерения информации Единицы измерения информации 143
компьютерные вирусы компьютерные вирусы 134
SpamAssassin SpamAssassin 121
Двоичное кодирование графической и звуковой информации Двоичное кодирование графической и звуковой информации 120
Подготовка к контрольной работе Подготовка к контрольной работе 129
Компьютер Компьютер 154
Презентация по информатике на тему Компьютерные сети Презентация по информатике на тему Компьютерные сети 154
Системный блок. Устройство. Характеристика Системный блок. Устройство. Характеристика 147
Системы счисления. КВН Системы счисления. КВН 117