Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
25 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
680.00 kB
Просмотров:
60
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Динамические структуры данных](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img0.jpg)
Содержание слайда: 10 Динамические структуры данных
№2 слайд![. Списки Список способ](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img1.jpg)
Содержание слайда: 10.1 Списки
Список – способ организации данных, предполагающий использова-ние указателей для определения следующего элемента.
Элемент списка состоит из двух частей: информационной и адресной.
Информационная часть содержит поля данных.
Адресная – включает от одного до n указателей, содержащих адреса следующих элементов. Количество связей, между соседними элементами списка определяет его связность: односвязные, двусвязные, n-связные.
№3 слайд![Виды списков](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img2.jpg)
Содержание слайда: Виды списков
№4 слайд![Примеры описания элементов](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img3.jpg)
Содержание слайда: Примеры описания элементов списка
Односвяный список:
struct element { {тип указателя}
char name[16]; {информационное поле 1}
char telefon[7]; {информационное поле 2}
element *p; {адресное поле}
};
Двусвяный список:
struct element { {тип указателя}
char name[16]; {информационное поле 1}
char telefon[7]; {информационное поле 2}
element *prev; {адресное поле «предыдущий»}
element *next; {адресное поле «следующий»}
};
№5 слайд![. Односвязные списки](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img4.jpg)
Содержание слайда: 10.2 Односвязные списки
Аналогично одномерным массивам односвязные списки реализуют последовательность элементов. Однако в отличие от одномерных массивов позволяют:
работать с произвольным количеством элементов, добавляя и удаляя их по мере необходимости;
осуществлять вставку и удаление записей, не перемещая остальных элементов последовательности;
но
не допускают прямого обращения к элементу по индексу;
требуют больше памяти для размещения.
№6 слайд![Основные приемы работы](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img5.jpg)
Содержание слайда: Основные приемы работы
Описание элемента списка:
struct element {тип на элемента}
{int num; {число}
element *p; {указатель на следующий элемент}
};
Описание переменной – указателя списка и нескольких переменных-указателей в статической памяти:
element * first, {адрес первого элемента}
*n,*f,*q; {вспомогательные указатели}
Исходное состояние – «список пуст»:
first=NULL;
№7 слайд![Основные приемы работы](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img6.jpg)
Содержание слайда: Основные приемы работы (2)
1 Добавление элемента к пустому списку:
first=new element;
first ->num=5;
first->p=NULL;
2 Добавление элемента перед первым (по типу стека):
q=new element;
q->num=4;
q->p=first;
first=q;
3 Добавление элемента после первого (по типу очереди):
q=new element;
q->num=4;
q->p=NULL;
first->p=q;
№8 слайд![Варианты удаления элементов](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img7.jpg)
Содержание слайда: Варианты удаления элементов
№9 слайд![Динамические структуры данных](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img8.jpg)
Содержание слайда: Динамические структуры данных (Ex10_1)
Пример. Стек записей.
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
struct zap { char det[10]; float diam; zap *p; };
int main(int argc, char* argv[])
{ zap a,*r,*q,*f;
r=new zap;
r->p=NULL;
puts("Input strings");
scanf("%s %f\n",r->det,&r->diam);
№10 слайд![Динамические структуры данных](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img9.jpg)
Содержание слайда: Динамические структуры данных (2)
while((scanf("\n%s",a.det)),strcmp(a.det,"end")!=0)
{ scanf("%f",&a.diam);
q=r;
r=new zap;
strcpy(r->det,a.det);
r->diam=a.diam;
r->p=q;
}
№11 слайд![Динамические структуры](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img10.jpg)
Содержание слайда: Динамические структуры (3)
Удаление записей
q=r;
do
{if (q->diam<1)
if( q==r){
r=r->p;
delete(q);
q=r;
}
else
{q=q->p;
delete(f->p);
f->p:=q
}
else
{f=q;
q=q->p;
}
}while(q!=NULL);
№12 слайд![Динамические структуры данных](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img11.jpg)
Содержание слайда: Динамические структуры данных (4)
q=r;
puts("Result");
if(q==NULL) puts("No information");
else
do { printf("%s %5.1f\n",q->det,q->diam);
q=q->p; }
while (q!=NULL);
return 0;
}
№13 слайд![Кольцевой список Ex .cpp](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img12.jpg)
Содержание слайда: Кольцевой список
1 2 3 4 5
// Ex10_2.cpp
#include "stdafx.h"
#include <stdio.h>
int play(int n,int m)
{
struct child {
int name;
child *p;};
int i,j;
child *first,*next,*pass;
№14 слайд![Создание списка Создание](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img13.jpg)
Содержание слайда: Создание списка
{ Создание списка }
first=new child;
first->name=1;
pass=first;
for( i=2;i<=n;i++)
{next=new child;
next->name=i;
pass->p=next;
pass=next; }
pass->p:=first; {Замыкание круга}
№15 слайд![Проход по кольцу m- раз pass](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img14.jpg)
Содержание слайда: Проход по кольцу m-1 раз
pass=first;
for{i=n;i>1;i++)
{
for(j=1;j<m;j++)
{ next=pass;
pass=pass->p;}
№16 слайд![Удаление m-го элемента.](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img15.jpg)
Содержание слайда: Удаление m-го элемента. Основная программа
printf(“%2d\n”,pass->name);
next->p=pass->p;
delete(pass);
pass=next->p;
}
//Возврат результата
return pass->name;
}
№17 слайд![. Бинарные сортированные](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img16.jpg)
Содержание слайда: 10.3 Бинарные сортированные деревья
В математике бинарным деревом называют конечное множество вершин, которое либо пусто, либо состоит из корня и не более чем двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня.
№18 слайд![Построение бинарного дерева](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img17.jpg)
Содержание слайда: Построение бинарного дерева
Рассмотрим последовательность целых чисел: {5, 2, 8, 7, 2, 9, 1, 5}
Пример. Разработать программу сортировки последовательности чисел с использованием бинарного дерева.
№19 слайд![Описание элемента дерева Ex](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img18.jpg)
Содержание слайда: Описание элемента дерева
// Ex10_3.cpp
#include "stdafx.h"
#include <stdio.h>
#include <STDLIB.H>
#include <conio.h>
#define lim 100
struct top_ptr
{int value;
top_ptr * left;
top_ptr * right;};
int next_number;
top_ptr * r,*pass;
№20 слайд![Основная программа int main](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img19.jpg)
Содержание слайда: Основная программа
int main(int argc,char argv[])
{ r=NULL;
puts(“input value or 1000 for end”);
scanf(“%d”,&next_number);
while(next_number!=1000)
{ pass=new top_ptr;
pass->value=next_number;
pass->left=NULL;
pass->right=NULL;
Add1(&r,pass);
scanf(“%d”,&next_number);
}
puts(“===Result===”);
Tree1(r); printf(“\n”);
getch();return 0;
}
№21 слайд![Нерекурсивная процедура](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img20.jpg)
Содержание слайда: Нерекурсивная процедура построения дерева
void Add1(top_pt **r,top_ptr *pass);
{top_ptr *next,*succ;
if(*r==NULL) *r=pass;
else
{succ=*r;
while(succ!=NULL)
{next=succ;
if(pass->value<succ->value)
succ=succ->left;
else succ=succ->right;
}
if(pass->value<next->value
next->left=pass;
else next->right=pass;
}
}
№22 слайд![Рекурсивная процедура](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img21.jpg)
Содержание слайда: Рекурсивная процедура построения дерева
void Add2(top_ptr **r,top_ptr *pass)
{ top_ptr * rr;
rr=*r;
if(rr==NULL) *r=pass;
else
if (pass->value<rr->value)
Add2(&rr->left,pass);
else Add2(&rr->right,pass);
}
№23 слайд![Нерекурсивная процедура](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img22.jpg)
Содержание слайда: Нерекурсивная процедура обхода дерева
void Tree1(top_ptr *r)
{ struct memo{
short int nom;
top_ptr * adres[lim];} memo1;
top_ptr * pass;
memo1.nom=-1;
pass=r;
№24 слайд![Нерекурсивная процедура](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img23.jpg)
Содержание слайда: Нерекурсивная процедура обхода дерева (2)
while ((pass!=NULL)||(memo1.nom!=-1))
if (pass!=NULL)
{ if( memo1.nom==lim-1)
{ puts(" Error lim"); exit(1);}
memo1.nom=memo1.nom+1;
memo1.adres[memo1.nom]=pass;
pass=pass->left;
}
else{ pass=memo1.adres[memo1.nom];
memo1.nom=memo1.nom-1;
printf("%4d\n",pass->value);
pass=pass->right;}
}
№25 слайд![Рекурсивная процедура обхода](/documents_5/4be96a67a528e5f8cdeb640d7ba7eb95/img24.jpg)
Содержание слайда: Рекурсивная процедура обхода дерева
void Tree2(top_ptr *r)
{
if(r!=NULL)
{ Tree2(r->left);
printf("%4d",r->value);
Tree2(r->right);
}
}