4. Програмування пошуку за мірами близькості

Якщо ж пряма або безпосередня адреса запису таблиці наперед невідома, то для вибірки відповідного запису з таблиці необхідно виконати ряд порівнянь у відповідності з визначеними відношеннями рівності та порядку.

// вибірка за лінійним пошуком

struct recrd*selLin(struct keyStr kArg,

struct recrd*tb,int ln)

{while(--ln>=0&&cmpKey(&tb[ln], kArg));

if(ln<0)return 0;

return &tb[ln];

}

Методи двійкового пошуку можна використовувати лише у впорядкованих таблицях або у відповідних індексах. Тобто таблиці для виконання такого пошуку повинні бути попередньо відсор­то­вані і для роботи з ними треба мати функцію сортування.

// вибірка за двійковим пошуком

struct recrd*selBin

(struct keyStr kArg,// ключ аргументу пошуку

struct recrd*tb, // адреса початку таблиці

int ln) // кількість елементів таблиці

{int i, nD=-1, nU=ln, n=(nD+nU)>>1;

while(i=cmpKey(&tb[n],kArg))

{if(i>0)nU=n; else nD=n;

n=(nD+nU)>>1;

if(n==nD)return NULL;

}

return &tb[n];

}

// виведення рядка базової таблиці

void prRow(struct recrd* rw)

{if(rw==0)printf("is absent\n");

else printf("%10s %3u %5.3f\n",

rw->key.str,rw->key.nMod,rw->func._f);

}

Структура програмного шаблона виконання роботи

Для спрощення розв’язання задачі слід використовувати прототип проекту spLb1.dsp, який зберігається в робочому просторі spLb1.dsw в папці spLb1, яка зберігає шаблони прототипів для всіх практичних занять циклу «Системне програмування і операційні сис­теми». До складу проекту консольної прикладної програми, орі­єн­тованої на можливість використання в числі інших бібліотек стандартних функцій та об’єктів MFC (Microsoft Foundation Classes) входять модулі з наступними вхідними файлами заголовків і реалізацій:

• StdAfx.h і StdAfx.cpp – модуль для організації використання об’єктів класів MFC;

• tables.h і tables.cpp – модуль для опису і організації вико­ри­стан­ня структур або класів таблиць;

• vistab.h і vistab.cpp – модуль для відображення рядків або пов­них таблиць;

• spLb1.cpp – модуль контрольних прикладів для тестування функцій обробки таблиць.

При побудові проектів без функцій MFC та в інших системах, що дозволяють побудову проектів, файли StdAfx.h і StdAfx.cpp можуть бути опущені, а посилання на них в операторах #include “StdAfx.h” повинні бути виключені.

Розділ визначень і декларацій основної частини програми тестування в модулі spLb1.cpp повинен включати визначення таб­лиць, ініціалізацію їх елементів, спеціальні змінні, що зберігають довжину (тобто кількість елементів) таблиці. Виконавча частина мо­ду­ля spLb1.cpp програми повинна включати циклічно повто­рю­вані виклики функцій для перевірки та відображення різних варі­ан­тів вхідних даних так, щоб перевірити роботу функцій при типових та кінцевих значення з множини припустимих значень аргументів.

Рекомендації з модифікації і розширення функцій модулів

Для настройки виведення таблиць згідно з варіантом треба внести зміни до функції виведення рядка з потрібним форматом.

При побудові функцій вставки, вилучення і корекції таблиць для двійкового пошуку необхідне попереднє розпізнавання успіш­но­сті пошуку. Для цього зручно використати функцію двійкового пошуку struct recrd*selBin(struct keyStr kArg, struct recrd *tb, int ln), яка повертає або вказівник на запис зі знайденим ключем, або стандартне значення невизначеного вказівника NULL. Для вилучення і корекції відповідні зміни можна виконати за адресою, яку повертає функція selBin, а для вставки нового елемента треба змістити останні елементи таблиці до місця вставки в операторі циклу, а потім занести новий елемент до таблиці.