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

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


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

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

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

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

Презентация на тему Абстрактный тип данных. Список

Содержание

Операции над абстрактным СпискомCreateList(List) - создает пустой список ListDeleteList(List) – уничтожает список ListIsEmpty(List) – определяет пуст ли список ListInsert(index, NewElement, List) - вставляет новый элемент NewElement в список List на позицию indexRemove(index, List) – удаляет элемент
Абстрактный тип данных список Операции над абстрактным СпискомCreateList(List) - создает пустой список ListDeleteList(List) – уничтожает список Операции над абстрактным СпискомTypeItem Retrive(index, List) – возвращает элемент, находящийся в позиции Реализация списковНеобходимо определить тип элементов и понятия «позиция» элемента: typedef  int Реализация списков посредством массивовПри реализации с помощью массивов все элементы списка располагаются Реализация списков посредством массивовОпределяем максимальное количество элементов:define max_list 100;// максимальное число элементов списка Реализация списков посредством массивовОписываем структуру List:Struct List {		 TypeItem Items [Max_ list]; Реализация списков посредством массивовVoid CreateList(List L){ L.last=0;} Viod Insert(int n,TypeItem NewItem,List L){if (L.last>=100) cout Viod Remove(int n, List L){	if (n>L.last || n Pos Find(TypeItem x, List L){for (i=n; i Реализация списков с помощью указателейВ данном случае элементы списка не обязательно расположены Реализация связанных списков с помощью указателейинформационная частьссылочная часть – указатель на следующий элемент Определение структуры List:typedef struct celltype{  TypeItem Item;// элемент списка	celltype *Next; // Описания необходимых типов и переменныхtypedef int Pos;//позицией элемента будет его номер в Функции работы со спискомVoid CreateList(List S)//создание пустого списка{ S=new celltype;  S->next=NULL; } void Insert (TypeItem x, Pos n, list S) {list temp, current;	temp=S; 	current=S->Next; i++; current=current->next;}//end while}//end of insert void Remove (Pos n, list S) {list current=S->Next, temp;		Pos i=1;	while(current!=NULL && inext;i++;)  if(i==n){	 temp=current->next;	current->next=current->next->next;	delete temp;}	}//end Pos Find (TypeItem x, list S){list temp;		Pos i=1;if (S->Next==NULL) coutNext!=NULL)	{if (temp->Item==x) return TypeItem Retrive (Pos n, list S){list temp;		Pos i=1;if (S->Next==NULL) coutNext!=NULL)	{if (i==n) return TypeItem Retrive (Pos n, list S){list temp;		Pos i=1;if (S->Next==NULL) coutNext!=NULL)	{if (i==n) return Сравнение реализацийРеализация списков с помощью массивов требует указания максимального размера массива до Сравнение реализацийРеализация списков с помощью массивов расточительна с точки зрения использования памяти, Двусвязные спискиИспользуются в приложениях, где необходимо организовать эффективное перемещение по списку как Двусвязные спискиинформационная частьуказатель на предыдущий элементуказатель на следующий элемент Описание структуры спискаtypedef struct celltype{  TypeItem Item;// элемент списка	celltype *Next; //
Слайды презентации

Слайд 2 Операции над абстрактным Списком
CreateList(List) - создает пустой список

Операции над абстрактным СпискомCreateList(List) - создает пустой список ListDeleteList(List) – уничтожает

List
DeleteList(List) – уничтожает список List
IsEmpty(List) – определяет пуст ли

список List
Insert(index, NewElement, List) - вставляет новый элемент NewElement в список List на позицию index
Remove(index, List) – удаляет элемент списка, находящийся в позиции index

Слайд 3 Операции над абстрактным Списком
TypeItem Retrive(index, List) – возвращает

Операции над абстрактным СпискомTypeItem Retrive(index, List) – возвращает элемент, находящийся в

элемент, находящийся в позиции index
Getlength(List) – возвращает количество элементов

в списке List
Pos Find(List, Element)- возвращает позицию элемента Element (Pos может быть как номером элемента, так и указателем на некоторый элемент)

Слайд 4 Реализация списков
Необходимо определить тип элементов и понятия «позиция»

Реализация списковНеобходимо определить тип элементов и понятия «позиция» элемента: typedef int

элемента:
typedef int TypeItem – тип элемента может быть

как простым, так и сложным
typedef int Pos – в данном случае позицией элемента будет его номер в списке


Слайд 5 Реализация списков посредством массивов
При реализации с помощью массивов

Реализация списков посредством массивовПри реализации с помощью массивов все элементы списка

все элементы списка располагаются в смежных ячейках, причем у

каждого элемента определен номер.
Это позволяет легко просматривать список, вставлять и удалять элементы в начало и в конец списка.
Однако, вставка элемента в середину списка потребует от нас сдвинуть все остальные элементы, также как удаление

Слайд 6 Реализация списков посредством массивов
Определяем максимальное количество элементов:

define max_list

Реализация списков посредством массивовОпределяем максимальное количество элементов:define max_list 100;// максимальное число элементов списка

100;// максимальное число элементов списка


Слайд 7 Реализация списков посредством массивов
Описываем структуру List:

Struct List {

Реализация списков посредством массивовОписываем структуру List:Struct List {		 TypeItem Items [Max_

TypeItem Items [Max_ list]; //массив элементов списка
int last;

//индекс следующего элемента
}

Слайд 8 Реализация списков посредством массивов
Void CreateList(List L)
{ L.last=0;}

Реализация списков посредством массивовVoid CreateList(List L){ L.last=0;}

Слайд 9 Viod Insert(int n,TypeItem NewItem,List L)
{
if (L.last>=100) cout

Viod Insert(int n,TypeItem NewItem,List L){if (L.last>=100) cout

else
if (n>L.last || n

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

Слайд 10 Viod Remove(int n, List L)
{
if (n>L.last || n

Viod Remove(int n, List L){	if (n>L.last || n

cout

L.Items[i]=L.Items[i+1];
}

} //end Remove

Слайд 11 Pos Find(TypeItem x, List L)
{for (i=n; i

Pos Find(TypeItem x, List L){for (i=n; i


if (L.Items[i]=x)
return(i); return(L.last+1);//х не найден
} //end Remove


Слайд 12 Реализация списков с помощью указателей
В данном случае элементы

Реализация списков с помощью указателейВ данном случае элементы списка не обязательно

списка не обязательно расположены в смежных ячейках, для связывания

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

Слайд 13 Реализация связанных списков с помощью указателей
информационная часть
ссылочная часть

Реализация связанных списков с помощью указателейинформационная частьссылочная часть – указатель на следующий элемент

– указатель на следующий элемент


Слайд 14 Определение структуры List:
typedef struct celltype
{
TypeItem Item;//

Определение структуры List:typedef struct celltype{ TypeItem Item;// элемент списка	celltype *Next; //

элемент списка
celltype *Next; // указатель на следующий элемент
}
typedef celltype

*list;//

Слайд 15 Описания необходимых типов и переменных
typedef int Pos;//позицией элемента

Описания необходимых типов и переменныхtypedef int Pos;//позицией элемента будет его номер

будет его номер в списке

typedef celltype *Pos;// позицией элемента

будет указатель на этот элемент



Слайд 16 Функции работы со списком
Void CreateList(List S)//создание пустого списка
{

Функции работы со спискомVoid CreateList(List S)//создание пустого списка{ S=new celltype; S->next=NULL; }

S=new celltype;
S->next=NULL;
}


Слайд 17 void Insert (TypeItem x, Pos n, list S)

void Insert (TypeItem x, Pos n, list S) {list temp, current;	temp=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;}

Слайд 18 i++;
current=current->next;
}//end while


}//end of insert

i++; current=current->next;}//end while}//end of insert

Слайд 19 void Remove (Pos n, list S)
{list current=S->Next,

void Remove (Pos n, list S) {list current=S->Next, temp;		Pos i=1;	while(current!=NULL && inext;i++;) if(i==n){	 temp=current->next;	current->next=current->next->next;	delete temp;}	}//end

temp;

Pos i=1;
while(current!=NULL && inext;i++;)
if(i==n){
temp=current->next;
current->next=current->next->next;
delete temp;}
}//end


Слайд 20 Pos Find (TypeItem x, list S)
{list temp;
Pos i=1;
if

Pos Find (TypeItem x, list S){list temp;		Pos i=1;if (S->Next==NULL) coutNext!=NULL)	{if (temp->Item==x) return (i);  temp=temp->next;i++;}return (0);}	}//end

(S->Next==NULL) coutNext!=NULL)
{if (temp->Item==x) return (i);

temp=temp->next;i++;}
return (0);}
}//end

Слайд 21 TypeItem Retrive (Pos n, list S)
{list temp;
Pos i=1;
if

TypeItem Retrive (Pos n, list S){list temp;		Pos i=1;if (S->Next==NULL) coutNext!=NULL)	{if (i==n) return (temp->Item);  temp=temp->next;i++;}return (0);}	}//end

(S->Next==NULL) coutNext!=NULL)
{if (i==n) return (temp->Item);

temp=temp->next;i++;}
return (0);}
}//end

Слайд 22 TypeItem Retrive (Pos n, list S)
{list temp;
Pos i=1;
if

TypeItem Retrive (Pos n, list S){list temp;		Pos i=1;if (S->Next==NULL) coutNext!=NULL)	{if (i==n) return (temp->Item);  temp=temp->next;i++;}return (0);}	}//end

(S->Next==NULL) coutNext!=NULL)
{if (i==n) return (temp->Item);

temp=temp->next;i++;}
return (0);}
}//end

Слайд 23 Сравнение реализаций
Реализация списков с помощью массивов требует указания

Сравнение реализацийРеализация списков с помощью массивов требует указания максимального размера массива

максимального размера массива до начала выполнения программы

Если длина списка

заренее не известка, более рациональным способом будет реализация с помощью указателей.
Процедуры INSERT и DELETE в случае связных списков выполняются за конечное число шагов для списков любой длины.

Слайд 24 Сравнение реализаций
Реализация списков с помощью массивов расточительна с

Сравнение реализацийРеализация списков с помощью массивов расточительна с точки зрения использования

точки зрения использования памяти, которая резервируется сразу.

При использовании

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

Слайд 25 Двусвязные списки
Используются в приложениях, где необходимо организовать эффективное

Двусвязные спискиИспользуются в приложениях, где необходимо организовать эффективное перемещение по списку

перемещение по списку как прямом, так и в обратном

направлениях

Слайд 26 Двусвязные списки
информационная часть
указатель на предыдущий элемент
указатель на следующий

Двусвязные спискиинформационная частьуказатель на предыдущий элементуказатель на следующий элемент

элемент


  • Имя файла: abstraktnyy-tip-dannyh-spisok.pptx
  • Количество просмотров: 136
  • Количество скачиваний: 0