Что такое 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);

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);

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
  • Количество просмотров: 115
  • Количество скачиваний: 0