Динамические структуры данных: списки - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Динамические структуры данных: списки, слайд №1

Динамические структуры данных: списки, слайд №2

Динамические структуры данных: списки, слайд №3

Динамические структуры данных: списки, слайд №4

Динамические структуры данных: списки, слайд №5

Динамические структуры данных: списки, слайд №6

Динамические структуры данных: списки, слайд №7

Динамические структуры данных: списки, слайд №8

Динамические структуры данных: списки, слайд №9

Динамические структуры данных: списки, слайд №10

Динамические структуры данных: списки, слайд №11

Динамические структуры данных: списки, слайд №12

Динамические структуры данных: списки, слайд №13

Динамические структуры данных: списки, слайд №14

Динамические структуры данных: списки, слайд №15

Динамические структуры данных: списки, слайд №16

Динамические структуры данных: списки, слайд №17

Динамические структуры данных: списки, слайд №18

Динамические структуры данных: списки, слайд №19

Динамические структуры данных: списки, слайд №20

Динамические структуры данных: списки, слайд №21

Динамические структуры данных: списки, слайд №22

Динамические структуры данных: списки, слайд №23

Динамические структуры данных: списки, слайд №24

Динамические структуры данных: списки, слайд №25

Динамические структуры данных: списки, слайд №26

Динамические структуры данных: списки, слайд №27

Динамические структуры данных: списки, слайд №28

Динамические структуры данных: списки, слайд №29

Динамические структуры данных: списки, слайд №30

Динамические структуры данных: списки, слайд №31

Динамические структуры данных: списки, слайд №32

Динамические структуры данных: списки, слайд №33

Динамические структуры данных: списки, слайд №34

Динамические структуры данных: списки, слайд №35

Динамические структуры данных: списки, слайд №36

Динамические структуры данных: списки, слайд №37

Динамические структуры данных: списки, слайд №38

Динамические структуры данных: списки, слайд №39

Динамические структуры данных: списки, слайд №40

Динамические структуры данных: списки, слайд №41

Динамические структуры данных: списки, слайд №42

Динамические структуры данных: списки, слайд №43

Динамические структуры данных: списки, слайд №44

Динамические структуры данных: списки, слайд №45

Динамические структуры данных: списки, слайд №46

Динамические структуры данных: списки, слайд №47

Динамические структуры данных: списки, слайд №48

Динамические структуры данных: списки, слайд №49

Динамические структуры данных: списки, слайд №50

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Динамические структуры данных: списки. Доклад-сообщение содержит 50 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекции 12 - 13 Динамические структуры данных: списки

Слайд 2

Описание слайда:

Динамические структуры данных Динамическая структура данных – структура данных создаваемая в процессе выполнения программы и размещаемая в динамически выделенной памяти. Классификация По способу хранения: Последовательное хранение; Связанное хранение. По методу доступа: Произвольный доступ; Упорядоченный доступ. По логической структуре: Линейные; Разветвляющиеся; Произвольные.

Слайд 3

Описание слайда:

Динамическая структура данных список Список – линейная динамическая структура данных, как правило, одного типа, произвольного доступа к элементам, каждый элемент которой имеет два соседних элемента, называемых предыдущим и последующим элементом в списке (сам элемент в этом случае называется текущим). Основные операции для работы со списками: Перемещение по списку; Добавление элементов в список; Удаление элементов из списка; Удаление всего списка; Доступ к элементам списка; Дополнительные операции (сортировка, поиск и т.д. и т.п.).

Слайд 4

Описание слайда:

Виды списков Виды списков определяются исходя из метода хранения: Последовательные списки; Связанные списки; Гибридные (смешанные) списки.

Слайд 5

Описание слайда:

Последовательные списки Основные переменные используемые для работы с последовательным списком: Указатель на начало списка; Текущий размер списка. Принцип организации списка с последовательным хранением:

Слайд 6

Описание слайда:

Переменные и типы для работы с последовательным списком Типы данных: typedef struct{ TYPE *list; int count; } LIST;

Слайд 7

Описание слайда:

Добавление элемента в конец списка int Add(LIST *ls, TYPE val) { TYPE *tmp = (TYPE*)realloc(ls->list,(ls->count+1)*sizeof(TYPE)); if(!tmp) return 0; if(tmp!=ls->list) ls->list = tmp; ls->list[ls->count] = val; ls->count++; return 1; }

Слайд 8

Описание слайда:

Вставка элемента на определенную позицию в списке int Ins(LIST *ls,TYPE val, int ind) { if(indcount list,(ls->count+1)*sizeof(TYPE)); if(!tmp) return 0; if(tmp!=ls->list) ls->list = tmp; for(int i=ls->count;i>ind;i--) ls->list[i] = ls->list[i-1]; ls->list[ind] = val; ls->count++; return 1; }

Слайд 9

Описание слайда:

Удаление элемента из списка int Del(LIST *ls, int ind) { if((ind=ls->count)) return 0; for(int i=ind;icount-1;i++) ls->list[i] = ls->list[i+1]; ls->list = (TYPE*)realloc(ls->list,(ls->count-1)*sizeof(TYPE)); ls->count--; return 1; }

Слайд 10

Описание слайда:

Графическое изображение операция добавления, вставки и удаления элемента

Слайд 11

Описание слайда:

Изменение и получение элемента из списка int Set(LIST *ls, TYPE val, int ind) { if((ind=ls->count)) return 0; ls->list[ind] = val; return 1; } int Get(LIST *ls, TYPE *val, int ind) { if((ind=ls->count)) return 0; *val = ls->list[ind]; return 1; }

Слайд 12

Описание слайда:

Удаление всего списка, определение его размера, инициализация void Destroy(LIST *ls) { if(ls->list) free(ls->list); ls->list = NULL; ls->count = 0; } int Count(LIST *ls) { return ls->count; } void Init(LIST *ls) { ls->list = NULL; ls->count = 0; }

Слайд 13

Описание слайда:

Пример использования Пользователь с клавиатуры вводит целые числа. Признак завершения – ввод пустой строки. Вывести на экран сначала четные значения, упорядоченные по возрастанию, а затем нечетные значения, упорядоченные по убыванию).

Слайд 14

Описание слайда:

Пример использования typedef int TYPE; int cmpInc(const void *p1,const void *p2) { return *((int*)p1) - *((int*)p2); } int cmpDec(const void *p1,const void *p2) { return *((int*)p2) - *((int*)p1); } int main(int argc, char *argv[]) { LIST list1 = {NULL,0}, list2 = {NULL,0}; while(1){ char str[20]; gets(str); if(str[0]==0) break; int val = atoi(str); Add((val%2==0)?&list2:&list1,val); } qsort(list2.list,list2.count,sizeof(TYPE),cmpInc); qsort(list1.list,list1.count,sizeof(TYPE),cmpDec);

Слайд 15

$Пример использования printf("\nЧетные значения: "); for(int i=0,n=Count(&list2);i$

Описание слайда:

Пример использования printf("\nЧетные значения: "); for(int i=0,n=Count(&list2);i

Слайд 16

Описание слайда:

Модификация int InsInc(LIST *lst, TYPE val) { for(int i=0,n=Count(lst);i=val) return Ins(lst,val,i); } return Add(lst,val); } int InsDec(LIST *lst, TYPE val) { for(int i=0,n=Count(lst);i

Слайд 17

Описание слайда:

Модификация (цикл ввода) while(1){ char str[20]; gets(str); if(str[0]==0) break; int val = atoi(str); if(val%2==0) InsInc(&list2,val); else InsDec(&list1,val); }

Слайд 18

Описание слайда:

Преимущества и недостатки списков с последовательным хранением Преимущества: Быстрый доступ к элементам списка посредством индексации. Недостатки: Усложненность операций добавления и удаления элементов.

Слайд 19

Описание слайда:

Списки со связанным хранением Виды списков со связанным хранением: Однонаправленные списки; Двунаправленные списки.

Слайд 20

Описание слайда:

Графическое изображение

Слайд 21

Описание слайда:

Типы данных и переменные для работы со связанными списками Необходимо иметь элемент списка, который бы агрегировал три поля: Данные заносимые в список; Указатель на следующий элемент в списке; Указатель на предыдущий элемент списка.

Слайд 22

$Пример для двунаправленного списка Переменные и типы: typedef struct _Element{ TYPE val; struct _Element *next, *prev; } Element; typedef struct{...$

Описание слайда:

Пример для двунаправленного списка Переменные и типы: typedef struct _Element{ TYPE val; struct _Element *next, *prev; } Element; typedef struct{ Element *head, *curr; } LIST;

Слайд 23

Описание слайда:

Перемещение по списку int MoveHead(LIST *ls) { ls->curr = ls->head; if(ls->head == NULL) return 0; return 1; } int MoveNext(LIST *ls) { if((ls->curr == NULL)||(ls->curr->next==NULL)) return 0; ls->curr = ls->curr->next; return 1; } int MovePrev(LIST *ls) { if((ls->curr == NULL)||(ls->curr->prev==NULL)) return 0; ls->curr = ls->curr->prev; return 1; }

Слайд 24

Описание слайда:

Добавление элемента в конец списка int Add(LIST *ls, TYPE val) { Element *tmp = (Element *)malloc(sizeof(Element)); if(!tmp) return 0; if(!ls->head){ ls->head=tmp; tmp->prev=NULL; tmp->next=NULL; }else{ if(!ls->curr) ls->curr=ls->head; while(ls->curr->next) ls->curr=ls->curr->next; ls->curr->next=tmp; tmp->prev=ls->curr; tmp->next=NULL; } tmp->val=val; ls->curr=tmp; return 1; }

Слайд 25

Описание слайда:

Добавление элемента перед текущим элементом в списке int Ins(LIST *ls, TYPE val) { if(!ls->curr) return Add(ls,val); Element * tmp=(Element *)malloc(sizeof(Element)); if(!tmp) return 0; tmp->next=ls->curr; tmp->prev=ls->curr->prev; ls->curr->prev=tmp; if(tmp->prev) tmp->prev->next=tmp; else ls->head=tmp; tmp->val=val; ls->curr = tmp; return 1; }

Слайд 26

Описание слайда:

Вставка элемента

Слайд 27

Описание слайда:

Удаление текущего элемента int Del(LIST *ls) { if(ls->curr==NULL) return 0; Element *tmp=ls->curr->prev; if(!tmp){ ls->head=ls->head->next; ls->head->prev=NULL; }else{ tmp->next=ls->curr->next; if(ls->curr->next) ls->curr->next->prev=tmp; } free(ls->curr); ls->curr=tmp; return 1; }

Слайд 28

Описание слайда:

Удаление элемента

Слайд 29

Описание слайда:

Запись и получение значения элемента int Set(LIST *ls, TYPE val) { if(ls->curr == NULL) return 0; ls->curr->val = val; return 1; } int Get(LIST *ls,TYPE *val) { if(ls->curr == NULL) return 0; *val = ls->curr->val; return 1; }

Слайд 30

Описание слайда:

Удаление и инициализация списка void Init(LIST *ls) { ls->head = ls->curr = NULL; } void Destroy(LIST *ls) { while(ls->head != NULL){ ls->curr = ls->head; ls->head = ls->head->next; free(ls->curr); } ls->curr = NULL; }

Слайд 31

Описание слайда:

Пример использования void SortInc(LIST *ls) { if((ls->head == NULL)|| (ls->head->next == NULL)) return; int flag = 1; while(flag){ flag = 0; ls->curr = ls->head; while(ls->curr->next != NULL){ if(ls->curr->val > ls->curr->next->val){ TYPE tmp = ls->curr->val; ls->curr->val = ls->curr->next->val; ls->curr->next->val = tmp; flag = 1; } ls->curr = ls->curr->next; } } ls->curr = ls->head; }

Слайд 32

Описание слайда:

Пример использования int main(int argc, char *argv[]) { LIST list1 = {NULL,NULL}, list2 = {NULL,NULL}; while(1){ char str[20]; gets(str); if(str[0]==0) break; int val = atoi(str); Add((val%2==0)?&list2:&list1,val); } SortInc(&list2); SortDec(&list1);

Слайд 33

$Пример использования printf("\nЧетные значения: "); if(MoveHead(&list2)) do{ int val; Get(&list2,&val); printf("%d ",val);...$

Описание слайда:

Пример использования printf("\nЧетные значения: "); if(MoveHead(&list2)) do{ int val; Get(&list2,&val); printf("%d ",val); }while(MoveNext(&list2)); printf("\nНечетные значения: "); if(MoveHead(&list1)) do{ int val; Get(&list1,&val); printf("%d ",val); }while(MoveNext(&list1)); puts(""); Destroy(&list1); Destroy(&list2); return 0; }

Слайд 34

Описание слайда:

Модификация int InsInc(LIST *ls, TYPE val) { if(MoveHead(ls)) do{ int tmp; Get(ls,&tmp); if(tmp>=val) return Ins(ls,val); }while(MoveNext(ls)); return Add(ls,val); }

Слайд 35

Описание слайда:

Модификация (цикл ввода) while(1){ char str[20]; gets(str); if(str[0]==0) break; int val = atoi(str); if(val%2==0) InsInc(&list2,val); else InsInc(&list1,val); }

Слайд 36

Описание слайда:

Преимущества и недостатки списков со связанным хранением Преимущество: Эффективные функции работы с памятью при добавлении или удалении элементов Недостаток: Нет возможности произвольного обращения к элементам списка.

Слайд 37

Описание слайда:

Смешанный список

Слайд 38

Описание слайда:

Переменные и типы данных typedef struct{ TYPE **list; //Указатель на начало списка int count; //Количество элементов в списке } LIST;

Слайд 39

Описание слайда:

Инициализация и уничтожение списка void Init(LIST *ls) { ls->list = NULL; ls->count = 0; } void Destroy(LIST *ls) { for(int i=0;icount;i++) free(ls->list[i]); free(ls->list); ls->list = NULL; ls->count = 0; }

Слайд 40

Описание слайда:

Добавление элемента в конец списка int Add(LIST *ls, TYPE val) { TYPE *new = (TYPE*)malloc(sizeof(TYPE)); if(!new) return 0; TYPE **tmp = (TYPE**)realloc(ls->list,(ls->count+1)*sizeof(TYPE*)); if(!tmp) {free(new); return 0;} *new = val; if(ls->list != tmp) ls->list = tmp; ls->list[ls->count++] = new; return 1; }

Слайд 41

Описание слайда:

Вставка элемента в середину списка int Ins(LIST *ls, TYPE val, int ind) { if(ind= ls->count) return Add(ls,val); TYPE *new = (TYPE*)malloc(sizeof(TYPE)); if(!new) return 0; TYPE **tmp = (TYPE**)realloc(ls->list,(ls->count+1)*sizeof(TYPE*)); if(!tmp) {free(new); return 0;} *new = val; if(ls->list != tmp) ls->list = tmp; for(int i=ls->count;i>ind;i--) ls->list[i] = ls->list[i-1]; ls->list[ind] = new; ls->count++; return 1; }

Слайд 42

Описание слайда:

Удаление элемента из списка int Del(LIST *ls, int ind) { if((ind=ls->count)) return 0; free(ls->list[ind]); for(int i=ind;icount-1;i++) ls->list[i] = ls->list[i+1]; ls->list = (TYPE**)realloc(ls->list,(ls->count-1)*sizeof(TYPE*)); ls->count--; return 1; }

Слайд 43

Описание слайда:

Запись и получение значения из списка int Set(LIST *ls, TYPE val, int ind) { if((ind=ls->count)) return 0; *ls->list[ind] = val; return 1; } int Get(LIST *ls, TYPE *val, int ind) { if((ind=ls->count)) return 0; *val = *ls->list[ind]; return 1; }

Слайд 44

Описание слайда:

Пример использования int CmpInc(const void *p1, const void *p2) { return **((int**)p1) - **((int**)p2); } int CmpDec(const void *p1, const void *p2) { return **((int**)p2) - **((int**)p1); }

Слайд 45

Описание слайда:

Пример использования int main(int argc, char *argv[]) { LIST list1 = {NULL,0}, list2 = {NULL,0}; while(1){ char str[20]; gets(str); if(str[0]==0) break; int val = atoi(str); Add((val%2==0)?&list2:&list1,val); } qsort(list1.list,list1.count,sizeof(TYPE*),CmpDec); qsort(list2.list,list2.count,sizeof(TYPE*),CmpInc);

Слайд 46

$Пример использования printf("\nЧетные значения: "); for(int i=0,n=Count(&list2);i$

Описание слайда:

Пример использования printf("\nЧетные значения: "); for(int i=0,n=Count(&list2);i

Слайд 47

Описание слайда:

Модификация int InsInc(LIST *lst, TYPE val) { for(int i=0,n=Count(lst);i=val) return Ins(lst,val,i); } return Add(lst,val); } int InsDec(LIST *lst, TYPE val) { for(int i=0,n=Count(lst);i

Слайд 48

Описание слайда:

Модификация (цикл ввода) while(1){ char str[20]; gets(str); if(str[0]==0) break; int val = atoi(str); if(val%2==0) InsInc(&list2,val); else InsDec(&list1,val); }

Слайд 49

Описание слайда:

Смешанный список Преимущество: Быстрый доступ к элементам списка посредством индексации Недостаток: Усложненность операций выделения и освобождения памяти при добавлении и удалении элементов