Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Основні властивості списків
В інформатиці, список (англ. list) - це абстрактний тип даних, що представляє собою упорядкований набір значень, в якому деякий значення може зустрічатися більше одного разу.
- Розмір списку - кількість елементів у ньому , виключаючи останній « нульовий» елемент, що є за визначенням порожнім списком .
Тип елементів - той самий тип A , над якими будується список ; всі елементи в списку повинні бути цього типу.
Відсортованість - список може бути відсортований відповідно з деякими критеріями сортування ( наприклад , за зростанням цілочисельних значень , якщо список складається з цілих чисел).
Можливості доступу - деякі списки залежно від реалізації можуть забезпечувати програміста селекторами для доступу безпосередньо до заданого за номером елементу .
Порівнюваємость - списки можна порівнювати один з одним на відповідність , причому залежно від реалізації операція порівняння списків може використовувати різні технології .
Однонаправлений список це
Найбільш природним і простим типом списку є однонаправлений, призначений для того, щоб проглядати його в одному напрямі - від початку до кінця. Однонаправлений список найчастіше зображують у вигляді ланцюга, тому його називають також ланцюговим, або лінійним однозв‘язним (рис.8.2).
Рис.8.2. Приклад однонаправленого списку
Який список називається лінійним?
Список, що відображає відношення сусідства між елементами, називають лінійним
Двонаправлені списки
Двонаправлені списки це такі списки, які дозволяють рухатися вперед і назад при перегляді його елементів. Вони зображуються у вигляді ланцюга, кожна ділянка якого містить вказівники на наступний і попередній елементи.
Що називають "збиранням сміття"?
Процедуру, пов‘язану з поверненням вільних квантів пам'яті у список вільної пам'яті, називають "збиранням сміття".
З чого складається елемент списку?
Елемент списку складається як мінімум з двох полів - безпосереднього значення елемента даних і вказівника на наступний елемент списку. У деяких випадках значення елементів даних можуть зберігатися окремо, тоді у полі "значення" елемента списку може знаходитися вказівник на місцезнаходження цього елемента даних. Вказівники елементів списку називають також адресами зв'язку, або зв'язками.
Що записано в заголовку списку?
заголовок, у якому зберігається посилання на перший елемент списку. Заголовок списку називають також іменем списку
Які дії виконуються при обробці списків ?
При обробці списків найчастіше виконуються такі дії:
1) доступ до к -го елемента списку з метою аналізу і заміни його полів;
2) включення нового елемента безпосередньо перед заданим;
3) виключення заданого елемента;
4) об’єднання декількох списків в один;
5) розбиття списку на два або більше списки;
6) копіювання списку;
7) визначення кількості елементів у списку;
8) знаходження елемента за заданими властивостями;
9) пересортування або впорядкування елементів списку у висхідному або низхідному порядку.
Зі скількох значень складається довідка однонаправленого списку?
Довідка кожної ділянки такого списку складається з двох значень. Першим є довжина Ni i-ї ділянки, яка, в свою чергу, складається з довжини запису і довжини довідки. Другим значенням довідки є посилання на початок наступної ділянки. Далі розміщується тіло ділянки або безпосередньо запис.
Схема процедури включення нового запису в однонаправленому списку?
Схема процедури включення нового запису Z після ділянки з індексом і показана на рис. 8.3. При цьому спочатку формується нова ділянка з записом Z, яка розміщується на вільному місці пам‘яті, а потім коректується зв‘язок і -ї ділянки.
Рис.8.3. Схема процедури включення елемента в ланцюговий список
Схема процедури виключення нового запису в однонаправленому списку.
Процедура виключення елемента з такого списку також зводиться до корекції зв‘язків між ділянками (рис.8.4). Припустимо, що потрібно виключити зі списку ділянку, яка розміщується після ділянки з індексом і . Отже, індекс ділянки, що виключається, розміщений в S[і+1]. Значення S[і+1] заміняється на значення, яке зберігалось у довідці ділянки, що виключається.
Рис. 8.4. Схема процедури виключення елемента
з однонаправленого списку
Які бувають списки за кількістю зв'язків та за типом функції зв'язку?
За кількістю зв'язків розрізняють списки одно- і багатозв'язні, а за типом функції зв'язку - лінійні і нелінійні.
Які є способи зображення списків?
Існує два способи зображення списків : 1) графічний (рис.8.1,а); 2) дужковий (рис.8.1,б).
Рис.8.1. Приклади зображення списків: а) графічний; б) дужковий
2 Тема 10 Масиви. Множини i кортежі. Зберігання множин і масивів. Зберігання розріджених матриць. Операції з масивами, множинами та кортежами
Масив це
Масив - це набір однотипних елементів даних, з кожним з яких пов'язана впорядкована послідовність цілих чисел, які називають індексами. Індекси однозначно визначають місце даного елемента в масиві і забезпечують прямий доступ до нього. Локалізувати елемент у масиві означає задати його індекс. Кількість індексів визначає розмірність масиву. Кількість елементів визначають розмір масиву.
Операції над массивами.
Найбільш поширеними операціями над структурами масивів є:
1) пошук елемента за заданим індексом;
2) локалізація елемента в масиві;
3) запис елемента в масив;
4) злиття масивів і розбиття масиву на частини;
5) сортування елементів масиву за деякими правилами;
6) копіювання масивів.
Множина – це...
Множина - найпростіша структура, в якій між окремими ізольованими елементами немає ніякого внутрішнього зв'язку. Набір таких елементів являє собою множину, яка не має ніякої структури. Це сукупність даних деякого типу, елементи якої мають певну властивість. Але повинні бути чітко встановлені область визначення елементів даних і правила їх відбору у множину.
Основні операції над множинами.
Основними операціями над множинами є об’єднання, перетин і різниця.
Кортеж це...
Кортеж - елемент n - кратного добутку множини X : Х*Х*..*Х=Хn. На відміну від скінченної впорядкованої множини, яка є підмножиною декартового добутку деяких множин Х1, X2 , ..., Хn елементи кортежу можуть повторюватись
Що запезпечує прямий доступ до елементів масивів?
Індекси однозначно визначають місце даного елемента в масиві і забезпечують прямий доступ до нього.
Що визначає розмірність масиву?
Кількість індексів визначає розмірність масиву.
Як зберігати розріджену матрицю?
Розрідженими називають такі матриці, більшість елементів яких дорівнює нулю. Одним з основних способів їх зберігання є табличний. Він полягає у запам'ятовуванні ненульових елементів матриці в одномірному масиві та ідентифікації кожного елемента масиву індексами рядка і стовпця.
Її можна зберігати у вигляді трьох векторів, які містять відповідно ненульові елементи матриці, а також індекси їх рядків та індекси стовпців
Способи зображення множини в пам‘яті комп‘ютера.
як тільки множина виявиться записаною в пам‘яті, спосіб її зображення визначає на ній індексацію, і різні методи зображення дозволяють по-різному її обробляти.
Найпростіший масиводномірний, який ототожнюється з вектором. Багатомірні масиви також зображуються векторами.
За якою формулою обчислюється адреса елемента двовимірного масиву при зберіганні його "по стовпцях"?
Індекс елемента bij двомірного масиву, що складається із n рядків та т стовпців, при зберіганні в пам'яті комп‘ютера "по стовпцях", обчислюється за формулою (j-1)*n + (i-1) , а при зберіганні його "по рядках" - за формулою (i-1)*m+(j-1).
Тема 11 Нелінійні структури даних. Класифікація нелінійних структур даних. Таблиці. Зображення таблиць. Основні операції з таблицями.
Таблиця це…
Таблиця це набір поіменованих об’єктів (або записів) довільної природи, з кожним з яких однозначно пов‘язане його ім‘я. Ім‘я запису називають його ключем. Таблиці є основною структурою запам‘ятовування у файлових структурах, організованих на зовнішній пам'яті комп‘ютера.
Основні операції з таблицями.
Основні операції з таблицями:
1) включення : дана пара (ключ і запис); включити запис в таблицю так, щоб його потім можна було знайти за ключем;
2) заміна: дана пара (ключ і запис); знайти запис із заданим ключем і замінити його на задане значення;
3) виключення елемента за заданим ключем;
4) пошук : за заданим ключем знайти відповідний запис;
5) друк елементів таблиці.
У загальному випадку названі операції можна звести до двох основних: сортування і пошук.
Основні властивості ключа запису в таблиці
Основні властивості ключа:
1) однозначна ідентифікація елемента;
2) відсутність надмірності.
Первинний ключ це…
Ключ, який буде використовуватися для ідентифікації записів, називають первинним
В залежності від методу доступу до елементів таблиці поділяються на…
Залежно від методу доступу до елементів таблиці поділяються на послідовні, деревоподібні і з обчислювальними адресами.
Як визначається адреса запису в таблиці з прямим доступом?
Як визначається адреса запису в таблиці з прямим доступом?
Як поділяються сіткові структури за типом елементів?
Сіткова структура це …
сіткова структура це орієнтований зв‘язний граф без циклів, у якого будь-який породжений вузол може мати більше одного породжуючого вузла і, крім того, всі вузли розміщуються так, що породжені елементи розміщуються нижче породжуючих. У сітковій структурі будь-який елемент може бути пов‘язаний з будь-яким іншим елементом
Петля у сітковій структурі це…
Деколи записи файлу зв‘язані з іншими записами цього ж файлу. Таку ситуацію називають петлею.
Цикл у сітковій структурі.
Циклом у такій схемі вважається ситуація, коли попередник вузла в той же час є його послідовником.
Решітка це…
Решіткою називають частковий випадок сіткової структури, в якій граф є кореневим і вхідні вузли деякого породженого вузла належать одному і тому ж рівню.
Тема 13. Пошук даних. Послідовний пошук. Двійковий пошук. Алгоритм Кнута, Моріса, Пратта. Алгоритм Бойера-Мурра. Порівняння алгоритмічної складності методів
Алгоритм послідовного або лінійного пошуку. Складність алгоритму.
складністьалгоритму - O(n)
Алгоритм L.
Таблиця містить п записів R1 ,..., Rп з ключами k1 ,..., kп . Необхідно знайти запис iз заданим ключем k.
L1. Ініціалізація індексу проходження таблиці: і=1.
L2. Якщо k=ki - кінець успішний; якщо ні, перехід на L3.
L3. Зміна індексу і =i+1.
L4. Перевірка умови i<n? Так: перехід на L2. Ні - кінець неуспішний.
int search(int *arr, int key,int li,int size)
{int A;
for(int i=0; i<size;i++)
if(arr[i]==key)
A=i+1;
if(A)
return A;
else return -1;
Алгоритм двійкового пошуку. Складність алгоритму.
Максимальне число порівнянь дорівнює О(log2 n), де n- кількість елементів даних.
Тоді алгоритм D пошуку ключа К у векторі КЛЮЧ(і;j) можна записати наступною послідовністю кроків:
Алгоритм D
D0. Ініціалізація індексів і, j .
D1. Повторювати кроки D2 - D5 доти, доки i<j.
D2. Обчислення індекcа кореня дерева: m=[(i+j)/2].
D3. Якщо [КЛЮЧ (m)]= К, то REZ= т, кінець.
D4. Інакше: якщо [ КЛЮЧ (т)] <K,
тo і=т +1 (пошук справа); перехід на D2.
D5. Інакше j=m-1 (пошук зліва); перехід на D2;
int search(int *arr, int key,int li,int size)
{
int l=li;
int r=size;
while(l <= r)
{
int i = (l + r) / 2;
if(arr[i] == key)
{
return i + 1;
}
if(arr[i] > key)
{
r=i-1; search(arr, key,li,r );
}
if(arr[i]<key)
{
l=i+1; search(arr,key,l,size);
}
}
return -1;
}
Алгоритм прямого пошуку стрічки. Складність алгоритму.
Нехай задано масив S з n елементів та масив P з m елементів, m<=n. Необхідно знайти перше входження масиву P у масив S . Алгоритм зводиться до повтору порівнянь окремих елементів.
Алгоритм R
R1. Встановити і=1.. n-m, j=1..m.
R2. Якщо S[i] = P[j] , то зафіксувати перше співпадіння k=i, та перевірити співпадіння всього масиву P у масиві S. При першому неспівпадінні відмінити значення k та продовжити пошук.
R3. Кінець.
Кількість порівнянь дорівнює n*m.
int search(char* str, char* word)
{
int sstr = strlen(str);
int skey = strlen(word);
int index = -1;
for (int i=0; i<sstr; i++)//цикли проходження по тексту
{
if (str[i] == word[0])// перевірка співпадіння першої букви слова з поточним символом стрічки
{
index = i;
for (int j = 1; j<skey; j++)// цикл проходження по слові
{
if (word[j] == str[i+j])
{
if (j == skey-1 )
return index;
}
else
index = -1;
}
}
}
return index;
}
Алгоритм Кнута, Моріса і Прата пошуку в стрічці. Складність алгоритму.
Маємо масив символів S з n елементів (текст) та масив P з m – взірець
Алгоритм КМП
КМП 1. Встановити і=0.
КМП 2. j=0, d=1.
КМП 3. Поки j<m, i<n
Перевірка: якщо S[i]=P[j], то d++, i++.j++ поки d != m.
КМП 4. Інакше встановити зсув взірця на d позицій по тексту якщо d <. Dmax , або на Dmax позицій якщо d > Dmax .Перейти на крок КМП 2.
КМП 5. Кінець.
Складність алгоритму становить O(n+m).
int dmax(char* str)
{
int n = strlen(str);
int dmax = n;
//for (int i = 0; i < n - 1; i++)
// for (int j = i + 1, k = 1; j < n; j++, k++)
// if (str[i] == str[j] && k < dmax)
// dmax = k;
//return dmax;
int* b = new int[256];
for (int i = 0; i < 256;i++ ) b[i] = -1;
for (int i = 0; i < n; i++)
{
if (b[(int)str[i]] < 0)
b[(int)str[i]] = i;
else
{
if (dmax > i - b[(int)str[i]])
dmax = i - b[(int)str[i]];
b[(int)str[i]] = i;
}
}
return dmax;
}
int kmp_search(int dmax, char* str, char* word)
{
cout<<"Dmax= " <<dmax<<endl;
int m=strlen(word), n=strlen(str);
int i = 0, j=0, d=1;
while (i < n)
{
int k = i;
j = 0;
d = 0;
while (k < n && j < m)
{
if (str[k] == word[j])
{
d++;
k++; j++;
}
else break;
}
if (d == m) return i;
d = min(dmax, d);
i +=d==0?1:d;
if(i<n)
cout<<"d="<<d<<"; Offset to str["<<i<<"]='"<<str[i]<<"'"<<endl;
}
return -1;
}
Алгоритм Бойера – Мура пошуку у стрічці. Складність алгоритму.
Ск – n/m
В даному алгоритмі розглядається поняття стоп-символа - це є символ в тексті, який є першим неспівпадінням тексту і взірця при порівнянні справа (з кінця взірця). Розглянемо три можливих ситуації:
У третій ситуації необхідно знайти співпадіння взірця і тексту. Якщо у взірці є ще один такий самий символ, то необхідно зсунути взірець до співпадіння цього символу з символом в тексті. Інакше зсув дорівнює 1.
int bmSearch(char* sentence, char* word)
{
int ssize = strlen(sentence);
int wsize = strlen(word);
int dx = 0; //Загальний зсув
int indexWord = 0;//індекс
int count = 0;// кількість збігів
while (dx + indexWord <= ssize) // щоб не вийти за межі речення
{
count = 0;// обнуляэмо каинт
for (indexWord = wsize-1; indexWord>=0; --indexWord) // пробігаємося по символах слова з кінця
{
if (word[indexWord] == sentence[indexWord + dx])//порівнюємо стопсимвол стлова із стопсимволом речення яке знаходиться над ним
{
count++;
// richTextBox1.Text += "1";
}
else // якщо немає збігу, вираховуємо зсув
{
int d = 0;// поточний зсув
for (int i = wsize - 1; i > 0; --i)// вираховуємо зсув
{
if (word[i] != sentence[indexWord + dx])// якщо немає збігу - збільшуємо зсув
d++;
else// коли стопсимвол в слові знаходиться правіше ніж стопсимвол в реченні
{
if (ssize - indexWord + dx - wsize < 0)// в такому випадку звус дорив 1
d = 1;
break;
}
}
dx += d;// збыльш зсув на поточгний
if (dx + indexWord >= ssize)//якщо вийшли за межі речення значить що збігів немає
return -1;
//richTextBox1.Text += "d = " + System.Convert.ToString(d)+"\n";
//richTextBox1.Text += "dx = " + System.Convert.ToString(dx) + "\n";
break;
}
}
if (count == wsize)// якщо кількість збігів дорівнює довжині слова - це значить що ми його знайшли
return indexWord+dx+1;// індекс початку слова в реченні
}
return -1;
}
Тема 14. Дерева порівнянь на векторній пам‘яті. Дерева порівнянь на зчепленій пам‘яті. Пошук у таблицях з обчислюваними адресами. Таблиці з прямим доступом. Хеш-таблиці. Задача колізії.
Функція хешування це…
Функція, що відображає ім‘я або ключ елемента таблиці у деяке ціле число.
Колізія це…
Ситуацію, при якій h(ki)= h(kj) при ki!= kj, називають колізією.
Алгоритм пошуку у таблицях з обчислюваними адресами.
Для цього таблиці треба організовувати так, щоб місцезнаходження її елементів визначалося за допомогою обчислюваної адреси. Це так звані таблиці з обчислюваними адресами. Загальна ідея організації таких таблиць полягає у тому, щоб використовувати ключ безпосередньо в ролі адреси або визначати адресу за допомогою функції від ключа і запам‘ятовувати запис за цією адресою.
Функції, що відображають ім‘я або ключ у деяке ціле число, називають функціями хешування h(k) для ключа k. Їх також називають функціями перемішування або рандомізації.
Ситуацію, при якій h(ki)= h(kj) при ki!= kj, називають колізією.
Таблиці з обчислюваними адресами поділяються на таблиці з прямим або безпосереднім доступом і перемішані, або хеш-таблиці. Задача колізії має місце тільки в хеш-таблицях.
Алгоритм пошуку у таблиці з прямим доступом.
Таблицю називають таблицею з прямим або безпосереднім доступом, якщо для визначення місцезнаходження кожного запису використовується його ключ. Функція хешування визначається як відображення К->A , де К- множина ключів, які можуть ідентифікувати записи в таблиці з прямим доступом; А - множина адрес. Доступ до запису за ключем k здійснюється в такому випадку за значенням функції h(k).
Мірою використання пам‘яті в таблицях з прямим доступом є коефіцієнт заповнення q , що визначається як відношення числа записів n до числа місць m в таблиці: q=n/m.
Вибір функції адресації, що забезпечує взаємну однозначність перетворення ключа в адресу її зберігання, взагалі достатньо складна задача. На практиці її можна розв‘язати тільки для постійних таблиць із заздалегідь відомим набором значень ключа. Такі таблиці застосовуються в трансляторах (наприклад, таблиця символів вхідної мови є таблицею з прямим доступом).