Линейные списки, деревья, таблицы

компьютере абстрактных
структур данных (последовательностей, множеств, графов, др.).
Описание узла

пустой список список из 1 элемента продвижение вперед на 1 элемент

Lp first = NULL; if (p) p = p -> next;
или
if (p != NULL) p = p -> next;

прямом направлении)




Рекурсивный обход списка в прямом направлении





Рекурсивный обход списка в

Lp p = first;
while ( p != NULL ) { R (p -> ptr ); // обработка объекта в узле
p = p -> next; }

void w1 (Lp p ) {
if ( p != NULL ) { R (p -> ptr ); // обработка объекта в узле
w1 ( p -> next ); }
}

void w2 (Lp p ) {
if ( p != NULL ) { w2 ( p -> next );
R (p -> ptr ); } // обработка объекта в узле
}

node {
OBJECT *ptr;
node

Lp p = first;
while ( p != NULL && *p -> ptr != <образец> ) p = p -> next;
If ( p == NULL) < искомого элемента в списке нет > ;
else < p есть указатель на нужный узел списка > ;

начала списка:




Вставка узла в произвольное место списка:


Lp q = new

if ( first != NULL ) first = first -> next;
Обратите внимание – память из-под освободившегося узла системе не возвращается

Lp q = new L; // q – указатель на новый узел списка
q -> next = p - > next; // здесь p – указатель на произвольный узел списка
p -> next = q;
Самостоятельно сделайте поясняющий рисунок к этому фрагменту кода

двусвязного списка:
typedef struct node {
OBJECT *ptr;

// пусть p – указатель на произвольный узел списка
If ( p != NULL && p -> next != NULL )
p -> next = p -> next -> next;
Самостоятельно сделайте поясняющий рисунок к этому фрагменту кода

obj

first

…..

obj

obj

NULL

back

back

узлом есть двоичное дерево. Граф вида:

– обход)
порядок посещения узлов: 1 2 3 4 5 6

void hlr ( Tp p )
{
if ( p ) {
R ( p -> ptr ); // R - обработка объекта в узле
hlr ( p -> left );
hlr ( p -> right );
}
}

6 3 7



Алгоритм lrh – обхода:



4 5 2 6 7

void lhr ( Tp p )
{
if ( p ) {
lhr ( p -> left );
R ( p -> ptr ); // R - обработка объекта в узле
lhr ( p -> right );
}
}

void lrh ( Tp p )
{
if ( p ) {
lrh ( p -> left );
lrh ( p -> right );
R ( p -> ptr ); // R - обработка объекта в узле
}
}

полезны, когда им присущ внутренний порядок (сорт. дерево).

).
Итеративный поиск в сорт. дереве:







Рекурсивный поиск в сорт. дереве:

// Пусть задан некий < образец>
void search1 ( Tp &p) {
while ( p && *p -> ptr != <образец> )
if ( h ( *p -> ptr ) >= h ( <образец> ) ) p = p -> left;
else p = p -> right;
} // p – указатель на найденный узел или NULL

void search2 ( Tp &p) {
if ( p ) if ( <образец> != *p -> ptr)
if ( h (<образец>) <= h (*p -> ptr ) search2 ( p -> left );
else search2 ( p -> right) ;
} // p – указатель на найденный узел или NULL

---

Слайд 11Структуры, препроцессор, динамическая память
Рекурсивный поиск в сорт. дереве с включением:








После

отработки алгоритма locate сортировка есть просто lhr (rhl) –обход сорт.

дерева.
Пример:
пусть данные поступают в дерево
в следующем порядке:
4 5 2 7 3 6 1

Осуществим lhr-обход, получим:
1 2 3 4 5 6 7

// Пусть задан некий < образец> для поиска и вставки
void locate ( Tp &p )
{
if ( !p ) { p = new T; p -> ptr = &<образец>; p -> left = p -> right = NULL; }
else if ( <образец> != *p -> ptr )
if ( h ( <образец> ) <= h (*p -> ptr ) ) locate ( p -> left );
else locate ( p -> right ) ;
} // p – указатель на найденный или созданный) узел

---

Слайд 12Структуры, препроцессор, динамическая память
Задача из теории компиляторов. Вычисление выражений:
Пусть требуется

вычислить следующее выражение:
( ( a + b ) % c

) * ( d – f )
Построим следующее двоичное дерево:









Обойдем данное двоичное дерево в порядке lrh и будем вычислять выражения в узлах,
используя обратную польскую запись (постфиксную форму).
Проверьте, что при таком обходе дерева выражение будет вычислено корректно.
Исследуйте работу программного стека.

---

Слайд 13Структуры, препроцессор, динамическая память
Hash-таблицы (таблицы с перемешиванием)

---

Скачать презентацию

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

Неправильные положения плода 235

МИНИСТЕРСТВО ОБРАЗОВАНИЯ НОВГОРОДСКОЙ ОБЛАСТИ  ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ 184

Подготовка к экзамену 290

ЛЕКЦИЯ: ОРГАНИЗАЦИЯ МЕДИЦИНСКОЙ ПОМОЩИ СЕЛЬСКОМУ НАСЕЛЕНИЮ Составитель: старший 227

Государственное бюджетное образовательное учреждение среднего профессионального 258

Тема: Общее понятие о предлоге 334

Повышение мотивации медицинских работников посредством совершенствования системы стимулирующих выплат 847

Постройка и реальность 188

Филарьет Ильич Гальчев 251

Роль односоставных предложений в создании речевой характеристики героев комедии Н.В. Гоголя «Ревизор» 1041

Сходи-ка, внучек, на огород, принеси бураков для борща.  — Чего принести, 170

Элементарные частицы 908

Приёмы авторского самораскрытия как основной способ выражения лиризма творчества В.М. Гаршина 452

Палочки Кюизенера как средство развития математических способностей у детей 131

Иван IV Васильевич. Внешняя и внутренняя политика 213

Миеломенингоцеле-1 207

Гигиена почвы и санитарная очистка населенных мест 555

тапаева камилла 01-1 мк 196

Черепно – мозговые нервы 228

Человек как результат биологической и социокультурной эволюции 256

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

---

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