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

– структура данных, реализующая: добавление – в конец, а удаление

– из начала.
2. Стек – структура данных, реализующая: добав-ление и удаление с одной стороны.
3. Дек – структура данных, реализующая: добав-ление и удаление с двух сторон.

Очередь

Строка

Запись

Матрица

определения следующего элемента.
Элемент списка состоит из двух частей: информационной и

адресной.
Информационная часть содержит поля данных.
Адресная – включает от одного до n указателей, содержащих адреса следующих элементов. Количество связей, между соседними элементами списка определяет его связность: односвязные, двусвязные, n-связные.

Списки

Линейные

Древовидные

N-связные

Кольцевые

{тип указателя}
char name[16];

{информационное поле 1}
char telefon[7]; {информационное поле 2}
element *p; {адресное поле}
};
Двусвяный список:
struct element { {тип указателя}
char name[16]; {информационное поле 1}
char telefon[7]; {информационное поле 2}
element *prev; {адресное поле «предыдущий»}
element *next; {адресное поле «следующий»}
};

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

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

num; {число}
element *p;

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

Описание переменной – указателя списка и нескольких переменных-указателей в статической памяти:
element * first, {адрес первого элемента}
*n,*f,*q; {вспомогательные указатели}

Исходное состояние – «список пуст»:
first=NULL;

first

∅

n

f

q

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;

first

∅

5

∅

first

5

∅

q

4

first

5

∅

q

4

∅

адресом q
f=first;
while(f->p!=q)
f=f->p;
q=q->p;
delete(f->p);
f->p=q;
3. Удаление последнего элемента
f=q=first;
while(q->p!=NULL)
{f=q; q=q->p;}
f->p=NULL;
delete(q);

{ 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);

r

det diam p

∅

Гайка

10

det diam p

∅

Гайка

10

a

Написать программу, которая формирует список деталей, содержащих наименование детали и ее диаметр. Удалить из списка все детали с диаметром, меньшим 1.

q=r;
r=new zap;

strcpy(r->det,a.det);
r->diam=a.diam;
r->p=q;
}

r

det diam p

det diam p

a

Гайка

10

r

det diam p

q

∅

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);

r

q

r

q

f

puts("No information");
else
do { printf("%s %5.1f\n",q->det,q->diam);

q=q->p; }
while (q!=NULL);
return 0;
}

"stdafx.h"
#include
int play(int n,int m)
{
struct child {

int name;
child *p;};
int i,j;
child *first,*next,*pass;

1

3

2

4

5

first

first->name=1;
pass=first;
for( i=2;i

{next=new child;
next->name=i;
pass->p=next;
pass=next; }
pass->p:=first; {Замыкание круга}

1

2

5

First

Pass

Next

3

4

for(j=1;j

{ next=pass;
pass=pass->p;}

1

2

5

First

Pass

Next

3

4

{
printf(“Result =“);
printf(“%4d\n”,play(5,7));
}

вершин, которое либо пусто, либо состоит из корня и не

более чем двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня.

Вершины, из которых не выходит ни одной ветви, называют листьями

Сортированные бинарные деревья, строятся по правилу: ключевое поле левого поддерева должно содержать значение меньше, чем в корне, а ключевое поле правого поддерева – значение больше или равное значению в корне.

2, 9, 1, 5}








Пример. Разработать программу сортировки последовательности чисел с

использованием бинарного дерева.

5

2

8

7

2

9

1

5

100
struct top_ptr
{int value;
top_ptr * left;
top_ptr * right;};
int next_number;
top_ptr * r,*pass;
Основная
программа
Add
Tree
Схема

структурная ПО

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;
}

pass

∅

∅

∅

r

5

else
{succ=*r;
while(succ!=NULL)

{next=succ;
if(pass->valuevalue)
succ=succ->left;
else succ=succ->right;
}
if(pass->valuevalue
next->left=pass;
else next->right=pass;
}
}

5

∅

r

pass

∅

∅

5

r

succ

∅

∅

2

pass

∅

∅

next

∅

rr;
rr=*r;
if(rr==NULL) *r=pass;
else
if (pass->valuevalue)
Add2(&rr->left,pass);
else Add2(&rr->right,pass);
}

* adres[lim];} memo1;
top_ptr * pass;
memo1.nom=-1;
pass=r;

{ 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;}
}

5

2

8

7

2

9

1

5