- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Абстрактный тип данных. Список презентация
Содержание
- 1. Абстрактный тип данных. Список
- 2. Операции над абстрактным Списком CreateList(List) - создает
- 3. Операции над абстрактным Списком TypeItem Retrive(index, List)
- 4. Реализация списков Необходимо определить тип элементов и
- 5. Реализация списков посредством массивов При реализации с
- 6. Реализация списков посредством массивов Определяем максимальное количество
- 7. Реализация списков посредством массивов Описываем структуру List:
- 8. Реализация списков посредством массивов Void CreateList(List L) { L.last=0;}
- 9. Viod Insert(int n,TypeItem NewItem,List L) { if (L.last>=100) cout
- 10. Viod Remove(int n, List L) { if (n>L.last || n
- 11. Pos Find(TypeItem x, List L) {for (i=n; i
- 12. Реализация списков с помощью указателей В данном
- 13. Реализация связанных списков с помощью указателей информационная часть ссылочная часть – указатель на следующий элемент
- 14. Определение структуры List: typedef struct celltype {
- 15. Описания необходимых типов и переменных typedef int
- 16. Функции работы со списком Void CreateList(List S)//создание
- 17. void Insert (TypeItem x, Pos n, list
- 18. i++; current=current->next; }//end while }//end of insert
- 19. void Remove (Pos n, list S)
- 20. Pos Find (TypeItem x, list S) {list
- 21. TypeItem Retrive (Pos n, list S) {list
- 22. TypeItem Retrive (Pos n, list S) {list
- 23. Сравнение реализаций Реализация списков с помощью массивов
- 24. Сравнение реализаций Реализация списков с помощью массивов
- 25. Двусвязные списки Используются в приложениях, где необходимо
- 26. Двусвязные списки информационная часть указатель на предыдущий элемент указатель на следующий элемент
- 27. Описание структуры списка typedef struct celltype {
Операции над абстрактным Списком CreateList(List) - создает пустой список List DeleteList(List) – уничтожает список List IsEmpty(List) – определяет пуст ли список List Insert(index, NewElement, List) - вставляет новый элемент NewElement в
Слайд 2Операции над абстрактным Списком
CreateList(List) - создает пустой список List
DeleteList(List) – уничтожает
список List
IsEmpty(List) – определяет пуст ли список List
Insert(index, NewElement, List) - вставляет новый элемент NewElement в список List на позицию index
Remove(index, List) – удаляет элемент списка, находящийся в позиции index
IsEmpty(List) – определяет пуст ли список List
Insert(index, NewElement, List) - вставляет новый элемент NewElement в список List на позицию index
Remove(index, List) – удаляет элемент списка, находящийся в позиции index
Слайд 3Операции над абстрактным Списком
TypeItem Retrive(index, List) – возвращает элемент, находящийся в
позиции index
Getlength(List) – возвращает количество элементов в списке List
Pos Find(List, Element)- возвращает позицию элемента Element (Pos может быть как номером элемента, так и указателем на некоторый элемент)
Getlength(List) – возвращает количество элементов в списке List
Pos Find(List, Element)- возвращает позицию элемента Element (Pos может быть как номером элемента, так и указателем на некоторый элемент)
Слайд 4Реализация списков
Необходимо определить тип элементов и понятия «позиция» элемента:
typedef int
TypeItem – тип элемента может быть как простым, так и сложным
typedef int Pos – в данном случае позицией элемента будет его номер в списке
typedef int Pos – в данном случае позицией элемента будет его номер в списке
Слайд 5Реализация списков посредством массивов
При реализации с помощью массивов все элементы списка
располагаются в смежных ячейках, причем у каждого элемента определен номер.
Это позволяет легко просматривать список, вставлять и удалять элементы в начало и в конец списка.
Однако, вставка элемента в середину списка потребует от нас сдвинуть все остальные элементы, также как удаление
Это позволяет легко просматривать список, вставлять и удалять элементы в начало и в конец списка.
Однако, вставка элемента в середину списка потребует от нас сдвинуть все остальные элементы, также как удаление
Слайд 6Реализация списков посредством массивов
Определяем максимальное количество элементов:
define max_list 100;// максимальное число
элементов списка
Слайд 7Реализация списков посредством массивов
Описываем структуру List:
Struct List {
TypeItem Items [Max_
list]; //массив элементов списка
int last; //индекс следующего элемента
}
int last; //индекс следующего элемента
}
Слайд 9Viod Insert(int n,TypeItem NewItem,List L)
{
if (L.last>=100) cout
(n>L.last || n<1)
cout<<‘Такой позиции нет’;
else
{for (i=L.Last; i>=n; i--) L.Items[i+1]=L.Items[i];
L.last=L.last+1;
L.Items[n]=NewItem; }
} //end Insert
else
{for (i=L.Last; i>=n; i--) L.Items[i+1]=L.Items[i];
L.last=L.last+1;
L.Items[n]=NewItem; }
} //end Insert
Слайд 10Viod Remove(int n, List L)
{
if (n>L.last || n
else
{L.last=L.last-1;
for (i=n; i<=L.last; i++) L.Items[i]=L.Items[i+1];
}
} //end Remove
{L.last=L.last-1;
for (i=n; i<=L.last; i++) L.Items[i]=L.Items[i+1];
}
} //end Remove
Слайд 12Реализация списков с помощью указателей
В данном случае элементы списка не обязательно
расположены в смежных ячейках, для связывания элементов используются указатели.
Эта реализация освобождает нас с одной стороны от использования непрерывной области памяти
Нет необходимости перемещения элементов при вставке или удалении элемента в список.
Необходима дополнительная память для хранения указателей.
Эта реализация освобождает нас с одной стороны от использования непрерывной области памяти
Нет необходимости перемещения элементов при вставке или удалении элемента в список.
Необходима дополнительная память для хранения указателей.
Слайд 13Реализация связанных списков с помощью указателей
информационная часть
ссылочная часть – указатель на
следующий элемент
Слайд 14Определение структуры List:
typedef struct celltype
{
TypeItem Item;// элемент списка
celltype *Next;
// указатель на следующий элемент
}
typedef celltype *list;//
}
typedef celltype *list;//
Слайд 15Описания необходимых типов и переменных
typedef int Pos;//позицией элемента будет его номер
в списке
typedef celltype *Pos;// позицией элемента будет указатель на этот элемент
typedef celltype *Pos;// позицией элемента будет указатель на этот элемент
Слайд 16Функции работы со списком
Void CreateList(List S)//создание пустого списка
{ S=new celltype;
S->next=NULL;
}
}
Слайд 17void Insert (TypeItem x, Pos n, list S)
{list temp, current;
temp=S;
current=S->Next;
Pos i=1;
while(current!=0)
{if (i==n)
{temp=new celltype;
temp->Next=current->Next;
temp->Item=x;
current->Next=temp;
break;}
Pos i=1;
while(current!=0)
{if (i==n)
{temp=new celltype;
temp->Next=current->Next;
temp->Item=x;
current->Next=temp;
break;}
Слайд 19void Remove (Pos n, list S)
{list current=S->Next, temp;
Pos i=1;
while(current!=NULL &&
i { current=current->next;i++;)
if(i==n){
temp=current->next;
current->next=current->next->next;
delete temp;}
}//end
if(i==n){
temp=current->next;
current->next=current->next->next;
delete temp;}
}//end
Слайд 20Pos Find (TypeItem x, list S)
{list temp;
Pos i=1;
if (S->Next==NULL) cout
{
temp=S->Next;
while(temp->Next!=NULL)
{if (temp->Item==x) return (i);
temp=temp->next;i++;}
return (0);}
}//end
temp=S->Next;
while(temp->Next!=NULL)
{if (temp->Item==x) return (i);
temp=temp->next;i++;}
return (0);}
}//end
Слайд 21TypeItem Retrive (Pos n, list S)
{list temp;
Pos i=1;
if (S->Next==NULL) cout
{
temp=S->Next;
while(temp->Next!=NULL)
{if (i==n) return (temp->Item);
temp=temp->next;i++;}
return (0);}
}//end
temp=S->Next;
while(temp->Next!=NULL)
{if (i==n) return (temp->Item);
temp=temp->next;i++;}
return (0);}
}//end
Слайд 22TypeItem Retrive (Pos n, list S)
{list temp;
Pos i=1;
if (S->Next==NULL) cout
{
temp=S->Next;
while(temp->Next!=NULL)
{if (i==n) return (temp->Item);
temp=temp->next;i++;}
return (0);}
}//end
temp=S->Next;
while(temp->Next!=NULL)
{if (i==n) return (temp->Item);
temp=temp->next;i++;}
return (0);}
}//end
Слайд 23Сравнение реализаций
Реализация списков с помощью массивов требует указания максимального размера массива
до начала выполнения программы
Если длина списка заренее не известка, более рациональным способом будет реализация с помощью указателей.
Процедуры INSERT и DELETE в случае связных списков выполняются за конечное число шагов для списков любой длины.
Если длина списка заренее не известка, более рациональным способом будет реализация с помощью указателей.
Процедуры INSERT и DELETE в случае связных списков выполняются за конечное число шагов для списков любой длины.
Слайд 24Сравнение реализаций
Реализация списков с помощью массивов расточительна с точки зрения использования
памяти, которая резервируется сразу.
При использовании указателей необходимо место в памяти для них тоже.
При использовании указателей нужно работать очень аккуратно. Поэтому в различных случаях бывают более выгодны одни или другие реализации.
При использовании указателей необходимо место в памяти для них тоже.
При использовании указателей нужно работать очень аккуратно. Поэтому в различных случаях бывают более выгодны одни или другие реализации.
Слайд 25Двусвязные списки
Используются в приложениях, где необходимо организовать эффективное перемещение по списку
как прямом, так и в обратном направлениях
Слайд 26Двусвязные списки
информационная часть
указатель на предыдущий элемент
указатель на следующий элемент
Слайд 27Описание структуры списка
typedef struct celltype
{
TypeItem Item;// элемент списка
celltype *Next;
// указатель на следующий элемент
celltype *Previous; // указатель на предыдущий элемент
}
typedef celltype *list;//
celltype *Previous; // указатель на предыдущий элемент
}
typedef celltype *list;//
