Динамические структуры данных: списки

Сентябрь 7, 2022

Главная
Алгебра
Динамические структуры данных: списки

Содержание

2. Динамические структуры данных Динамическая структура данных – структура данных создаваемая в процессе выполнения программы и размещаемая
3. Динамическая структура данных список Список – линейная динамическая структура данных, как правило, одного типа, произвольного доступа
4. Виды списков Виды списков определяются исходя из метода хранения: Последовательные списки; Связанные списки; Гибридные (смешанные) списки.
5. Последовательные списки Основные переменные используемые для работы с последовательным списком: Указатель на начало списка; Текущий размер
6. Переменные и типы для работы с последовательным списком Типы данных: typedef struct{ TYPE *list; int count;
7. Добавление элемента в конец списка int Add(LIST *ls, TYPE val) { TYPE *tmp = (TYPE*)realloc(ls->list,(ls->count+1)*sizeof(TYPE)); if(!tmp)
8. Вставка элемента на определенную позицию в списке int Ins(LIST *ls,TYPE val, int ind) { if(ind if(ls->count
9. Удаление элемента из списка int Del(LIST *ls, int ind) { if((ind =ls->count)) return 0; for(int i=ind;i
10. Графическое изображение операция добавления, вставки и удаления элемента
11. Изменение и получение элемента из списка int Set(LIST *ls, TYPE val, int ind) { if((ind =ls->count))
12. Удаление всего списка, определение его размера, инициализация void Destroy(LIST *ls) { if(ls->list) free(ls->list); ls->list = NULL;
13. Пример использования Пользователь с клавиатуры вводит целые числа. Признак завершения – ввод пустой строки. Вывести на
14. Пример использования typedef int TYPE; int cmpInc(const void *p1,const void *p2) { return *((int*)p1) - *((int*)p2);
15. Пример использования printf("\nЧетные значения: "); for(int i=0,n=Count(&list2);i int val; Get(&list2,&val,i); printf("%d ",val); } printf("\nНечетные значения: ");
16. Модификация int InsInc(LIST *lst, TYPE val) { for(int i=0,n=Count(lst);i int tmp; Get(lst,&tmp,i); if(tmp>=val) return Ins(lst,val,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
18. Преимущества и недостатки списков с последовательным хранением Преимущества: Быстрый доступ к элементам списка посредством индексации. Недостатки:
19. Списки со связанным хранением Виды списков со связанным хранением: Однонаправленные списки; Двунаправленные списки.
20. Графическое изображение
21. Типы данных и переменные для работы со связанными списками Необходимо иметь элемент списка, который бы агрегировал
22. Пример для двунаправленного списка Переменные и типы: typedef struct _Element{ TYPE val; struct _Element *next, *prev;
23. Перемещение по списку int MoveHead(LIST *ls) { ls->curr = ls->head; if(ls->head == NULL) return 0; return
24. Добавление элемента в конец списка int Add(LIST *ls, TYPE val) { Element *tmp = (Element *)malloc(sizeof(Element));
25. Добавление элемента перед текущим элементом в списке int Ins(LIST *ls, TYPE val) { if(!ls->curr) return Add(ls,val);
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{
28. Удаление элемента
29. Запись и получение значения элемента int Set(LIST *ls, TYPE val) { if(ls->curr == NULL) return 0;
30. Удаление и инициализация списка void Init(LIST *ls) { ls->head = ls->curr = NULL; } void Destroy(LIST
31. Пример использования void SortInc(LIST *ls) { if((ls->head == NULL)|| (ls->head->next == NULL)) return; int flag =
32. Пример использования int main(int argc, char *argv[]) { LIST list1 = {NULL,NULL}, list2 = {NULL,NULL}; while(1){
33. Пример использования printf("\nЧетные значения: "); if(MoveHead(&list2)) do{ int val; Get(&list2,&val); printf("%d ",val); }while(MoveNext(&list2)); printf("\nНечетные значения: ");
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));
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
36. Преимущества и недостатки списков со связанным хранением Преимущество: Эффективные функции работы с памятью при добавлении или
37. Смешанный список
38. Переменные и типы данных typedef struct{ TYPE **list; //Указатель на начало списка int count; //Количество элементов
39. Инициализация и уничтожение списка void Init(LIST *ls) { ls->list = NULL; ls->count = 0; } void
40. Добавление элемента в конец списка int Add(LIST *ls, TYPE val) { TYPE *new = (TYPE*)malloc(sizeof(TYPE)); if(!new)
41. Вставка элемента в середину списка int Ins(LIST *ls, TYPE val, int ind) { if(ind if(ind >=
42. Удаление элемента из списка int Del(LIST *ls, int ind) { if((ind =ls->count)) return 0; free(ls->list[ind]); for(int
43. Запись и получение значения из списка int Set(LIST *ls, TYPE val, int ind) { if((ind =ls->count))
44. Пример использования int CmpInc(const void *p1, const void *p2) { return **((int**)p1) - **((int**)p2); } int
45. Пример использования int main(int argc, char *argv[]) { LIST list1 = {NULL,0}, list2 = {NULL,0}; while(1){
46. Пример использования printf("\nЧетные значения: "); for(int i=0,n=Count(&list2);i int val; Get(&list2,&val,i); printf("%d ",val); } printf("\nНечетные значения: ");
47. Модификация int InsInc(LIST *lst, TYPE val) { for(int i=0,n=Count(lst);i int tmp; Get(lst,&tmp,i); if(tmp>=val) return Ins(lst,val,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
49. Смешанный список Преимущество: Быстрый доступ к элементам списка посредством индексации Недостаток: Усложненность операций выделения и освобождения
51. Скачать презентацию

Слайд 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(ind<0) return 0;
if(ls->count <= ind) return Add(ls,val);
TYPE *tmp = (TYPE*)realloc(ls->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<0)||(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<0)||(ind>=ls->count)) return 0;
ls->list[ind] = val;
return 1;
}
int Get(LIST *ls, TYPE *val, int ind)
{
if((ind<0)||(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 int val; Get(&list2,&val,i); printf("%d$

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

",val);
}
printf("\nНечетные значения: ");
for(int i=0,n=Count(&list1);i int val;
Get(&list1,&val,i);
printf("%d ",val);
}
puts("");
Destroy(&list1); Destroy(&list2);
return 0;
}

Слайд 16

Модификация
int InsInc(LIST *lst, TYPE val)
{
for(int i=0,n=Count(lst);i int tmp;
Get(lst,&tmp,i);
if(tmp>=val)

return Ins(lst,val,i);
}
return Add(lst,val);
}
int InsDec(LIST *lst, TYPE val)
{
for(int i=0,n=Count(lst);i int tmp;
Get(lst,&tmp,i);
if(tmp }
return Add(lst,val);
}

Слайд 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$

Пример для двунаправленного списка
Переменные и типы:
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;
}

void SortDec(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$

Пример использования
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);
}

int InsDec(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<0) return 0;
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<0)||(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<0)||(ind>=ls->count)) return 0;
*ls->list[ind] = val;
return 1;
}
int Get(LIST *ls, TYPE *val, int ind)
{
if((ind<0)||(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 int val; Get(&list2,&val,i); printf("%d$

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

",val);
}
printf("\nНечетные значения: ");
for(int i=0,n=Count(&list1);i int val;
Get(&list1,&val,i);
printf("%d ",val);
}
puts("");
Destroy(&list2); Destroy(&list1);
return 0;
}

Слайд 47

Модификация
int InsInc(LIST *lst, TYPE val)
{
for(int i=0,n=Count(lst);i int tmp;
Get(lst,&tmp,i);
if(tmp>=val)

return Ins(lst,val,i);
}
return Add(lst,val);
}
int InsDec(LIST *lst, TYPE val)
{
for(int i=0,n=Count(lst);i int tmp;
Get(lst,&tmp,i);
if(tmp }
return Add(lst,val);
}

Слайд 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

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

освобождения памяти при добавлении и удалении элементов

Динамические структуры данных: списки

Содержание

Динамические структуры данныхДинамическая структура данных – структура данных создаваемая в процессе

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

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

Последовательные спискиОсновные переменные используемые для работы с последовательным списком:Указатель на начало

Переменные и типы для работы с последовательным спискомТипы данных:typedef struct{ TYPE

Добавление элемента в конец спискаint Add(LIST *ls, TYPE val){ TYPE *tmp

Вставка элемента на определенную позицию в спискеint Ins(LIST *ls,TYPE val, int

Удаление элемента из спискаint Del(LIST *ls, int ind){ if((ind<0)||(ind>=ls->count)) return 0;

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

Изменение и получение элемента из спискаint Set(LIST *ls, TYPE val, int

Удаление всего списка, определение его размера, инициализацияvoid Destroy(LIST *ls){ if(ls->list) free(ls->list);

Пример использованияПользователь с клавиатуры вводит целые числа. Признак завершения – ввод

Пример использованияtypedef int TYPE;int cmpInc(const void *p1,const void *p2){ return *((int*)p1)

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

Модификацияint InsInc(LIST *lst, TYPE val){ for(int i=0,n=Count(lst);i int tmp; Get(lst,&tmp,i); if(tmp>=val)

Модификация (цикл ввода)while(1){ char str[20]; gets(str); if(str[0]==0) break; int val =

Преимущества и недостатки списков с последовательным хранениемПреимущества:Быстрый доступ к элементам списка

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

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

Типы данных и переменные для работы со связанными спискамиНеобходимо иметь элемент

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

Перемещение по спискуint MoveHead(LIST *ls){ ls->curr = ls->head; if(ls->head == NULL)

Добавление элемента в конец спискаint Add(LIST *ls, TYPE val){ Element *tmp

Добавление элемента перед текущим элементом в спискеint Ins(LIST *ls, TYPE val){

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

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

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

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

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

Пример использованияvoid SortInc(LIST *ls){ if((ls->head == NULL)|| (ls->head->next == NULL)) return;

Пример использованияint main(int argc, char *argv[]){ LIST list1 = {NULL,NULL}, list2

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

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

Модификация (цикл ввода)while(1){ char str[20]; gets(str); if(str[0]==0) break; int val =

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

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

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

Инициализация и уничтожение спискаvoid Init(LIST *ls){ ls->list = NULL; ls->count =

Добавление элемента в конец спискаint Add(LIST *ls, TYPE val){ TYPE *new

Вставка элемента в середину спискаint Ins(LIST *ls, TYPE val, int ind){

Удаление элемента из спискаint Del(LIST *ls, int ind){ if((ind<0)||(ind>=ls->count)) return 0;

Запись и получение значения из спискаint Set(LIST *ls, TYPE val, int

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

Пример использованияint main(int argc, char *argv[]){ LIST list1 = {NULL,0}, list2

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

Модификацияint InsInc(LIST *lst, TYPE val){ for(int i=0,n=Count(lst);i int tmp; Get(lst,&tmp,i); if(tmp>=val)

Модификация (цикл ввода)while(1){ char str[20]; gets(str); if(str[0]==0) break; int val =

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

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

Динамические структуры данных
Динамическая структура данных – структура данных создаваемая в процессе

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

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

Последовательные списки
Основные переменные используемые для работы с последовательным списком:
Указатель на начало

Переменные и типы для работы с последовательным списком
Типы данных:
typedef struct{
TYPE

Добавление элемента в конец списка
int Add(LIST ls, TYPE val)
{
TYPE tmp

Вставка элемента на определенную позицию в списке
int Ins(LIST *ls,TYPE val, int

Удаление элемента из списка
int Del(LIST *ls, int ind)
{
if((ind<0)||(ind>=ls->count)) return 0;

Изменение и получение элемента из списка
int Set(LIST *ls, TYPE val, int

Удаление всего списка, определение его размера, инициализация
void Destroy(LIST *ls)
{
if(ls->list) free(ls->list);

Пример использования
Пользователь с клавиатуры вводит целые числа. Признак завершения – ввод

Пример использования
typedef int TYPE;
int cmpInc(const void p1,const void p2)
{
return ((int)p1)

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

Модификация
int InsInc(LIST *lst, TYPE val)
{
for(int i=0,n=Count(lst);i int tmp;
Get(lst,&tmp,i);
if(tmp>=val)

Модификация (цикл ввода)
while(1){
char str[20];
gets(str);
if(str[0]==0) break;
int val =

Преимущества и недостатки списков с последовательным хранением
Преимущества:
Быстрый доступ к элементам списка

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

Типы данных и переменные для работы со связанными списками
Необходимо иметь элемент

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

Перемещение по списку
int MoveHead(LIST *ls)
{
ls->curr = ls->head;
if(ls->head == NULL)

Добавление элемента в конец списка
int Add(LIST ls, TYPE val)
{
Element tmp

Добавление элемента перед текущим элементом в списке
int Ins(LIST *ls, TYPE val)
{

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

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

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

Пример использования
void SortInc(LIST *ls)
{
if((ls->head == NULL)||
(ls->head->next == NULL)) return;

Пример использования
int main(int argc, char *argv[])
{
LIST list1 = {NULL,NULL}, list2

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

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

Модификация (цикл ввода)
while(1){
char str[20];
gets(str);
if(str[0]==0) break;
int val =

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

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

Инициализация и уничтожение списка
void Init(LIST *ls)
{
ls->list = NULL;
ls->count =

Добавление элемента в конец списка
int Add(LIST ls, TYPE val)
{
TYPE new

Вставка элемента в середину списка
int Ins(LIST *ls, TYPE val, int ind)
{

Удаление элемента из списка
int Del(LIST *ls, int ind)
{
if((ind<0)||(ind>=ls->count)) return 0;

Запись и получение значения из списка
int Set(LIST *ls, TYPE val, int

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

Пример использования
int main(int argc, char *argv[])
{
LIST list1 = {NULL,0}, list2

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

Модификация
int InsInc(LIST *lst, TYPE val)
{
for(int i=0,n=Count(lst);i int tmp;
Get(lst,&tmp,i);
if(tmp>=val)

Модификация (цикл ввода)
while(1){
char str[20];
gets(str);
if(str[0]==0) break;
int val =

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