Массивте мәні бойынша элементтерді іздестіру

6.3 Массивте мәні бойынша элементтерді іздестіру

Д.Кнут «Искусство программирования для ЭВМ» кітабының жартысын («сұрыптау мен іздеу» сұрақтарына 3-том арналған) кейбір бір типті элементтер жиынтығында (массивте, файлда, т.б.) мән бойынша элементтерді іздестіру сұрақтарына арналған. Бұл бағдарламалауды оқу барысында іздеу алгоритмін білу қаншалықты маңызды екенін көрсетеді.

Түрлі іздеу әдістерінің ішінен олардың тек үшеуінің алгоритмдері мен бағдарламалық жүзеге асырылуын қарастырамыз – массивте элемент мәні бойынша екілік, блоктық және тізбектеп іздеу әдістері. Араластыру арқылы іздеу әдісін алгоритм деңгейінде ғана қарастырамыз.

Бізге массив элементтерінің мәндері емес іздеу алгоритмі ғана қажет, сондықтан бүтін сандардан тұратын әлементтер үшін барлық алгоритмдерді қарастырамыз. Біз «іздестіру массивінде», яғни кездейсоқ түрде құрылатын бүтін сандар массивінде ізделетін бүтін санды - «ізделетін кілтті» ұсынамыз.

6.3.1 Тізбектеп іздеу алгоритмі. Элементтің тізбектеп іздеу алгоритмі ізделетін кілтті массивтің барлық элементімен, яғни бірінші элементінен бастап соңғы элементіне дейін тізбекті түрде салыстыруға негізделген. Егер массивтің соңғы элементі қаралып қойса, онда іздеу аяқталады.

Осы алгоритмді көрсету үшін оны кітаптың керекті бетін іздеу алгоритмімен салыстырады, мысалы, үш жүзінші бет. Әрбір бет бірінші беттен үш жүзінші бетке дейін тізбекті түрде парақталады.

Осы алгоритмнің кемшілігі – массив элементтерінің саны көп болған жағдайда іздеуге айтарлықтай көп уақыт жұмсалады. Іздеу уақыты N санына пропорционал, мұндағы N - массив элементтерінің саны.

Алгоритм артықшылығы - массивте элементтерді кез келген тәртіпте және тәртіпсіз түрде орналастыруға рұқсат беру.

6.2-есеп. Іздестіру массиві 0-ден 99-дейінгі аралықтағы 20 кездейсоқ бүтін сандарынан тұрады. Диалог режімінде кез келген бүтін сан – ізделінетін кілт беріледі. Осы сан (индекстері қандай) іздестіру массивінде неше рет кездесетінін табу керек. Тізбектеп іздеу алгоритмін қолдану.

Алгоритм белгілі болғандықтан бағдарлама кодын құруға кірісеміз.

using System;

namespace ConsoleApplication1

{

class Program

static void Main()

{

int i,k,n;

int[] p = new int[20];

Random rnd = new Random();

string buf;

// массивті құру және экранға шығару

Console.WriteLine("Izdestiry massivi: ");

for (i=0;i<10;i++)

Console.Write(" {0}", i);

for (i=10;i<20;i++)

Console.Write(" {0}", i);

Console.WriteLine();

for (i = 0; i < 20; i++)

{

a[i] = rnd.Next()%100;

else Console.Write(" {0}", a[i]);

}

Console.WriteLine();

buf = Console.ReadLine();

k = Convert.ToInt32(buf);

n=0;

for (i=0;i<20;i++)

if (k == a[i]) {p[n]=i; n++;}

if (n==0)

Console.WriteLine("Izdey kiltine saikes element jok!!");

else

Console.WriteLine("Izdey kiltine saikes keletin elementter sani = {0}",n);

Console.WriteLine("Tabilgan indexter: ");

for (i=0;i

Console.Write(" {0}",p[i]);

Console.WriteLine();

}

Console.ReadLine();

}

}

Izdestiry massivi:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

43 68 85 72 14 44 45 55 57 30 94 83 52 72 77 92 0 91 29 97

Izdey kiltin engiziniz

91

Izdey kiltine saikes keletin elementter sani = 1

17
6.3.2 Блоктық іздеу алгоритмі. Блоктық іздеу алгоритмі іздестіру массивінің элементтерін реттелген түрде орналасыруды талап етеді, мысалы, түйінді элементтерді өсу немесе кему ретімен, алфавиттік тәртіпте, т.б.

Іздестіруді іздестіру массивінің түйінді элементі арқылы ғана орындауға болады, мұндағы түйінді элемент іздестіру массивін реттейді.

Іздестіру массивінің элементтері мәндері бойынша өсу ретімен орналасқан деп жорамалдайық.

Бүкіл іздестіру массиві шартты түрде блоктарға бөлінеді, мысалы, бір блокта жүз элементтен. Сұратудың ізделетін кілті ретті түрде бірінші блоктан бастап әрбір блоктың соңғы элементімен салыстырылады.

Егер сұратудың ізделетін кілті кезекті массив блогының соңғы элементінен үлкен болса, онда келесі блоктың соңғы элементіне көшу керек, әйтпесе соңғы салыстыру орындалған блокта тізбекті іздеуді орындау керек.

0-ден 99-ға дейінгі аралықта жүз кездейсоқ құрылған бүтін сандарға арналған алгоритмді орындайтын бағдарламаның коды мынандай:

using System;

using System;

namespace ConsoleApplication1

{

class Program

static void Main()

{

int i,j,b,k,n,f,m;

int[] p = new int[21];

Random rnd = new Random();

string buf;

f = 0; m = 0;

// іздестіру массивіy құру және экранға шығару

Console.WriteLine("Izdestiry massivi: ");

for (i = 0; i < 100; i++)

{

a[i] = rnd.Next() % 100;

else Console.Write(" {0}", a[i]);

if ((i + 1) % 20 == 0) Console.WriteLine();

}

Console.WriteLine();

for (i=0;i<99;i++)

for (j=i+1;j<100;j++)

if (a[i]>a[j])

{b=a[i];a[i]=a[j];a[j]=b;}

Console.WriteLine("Sandardi syriptalgannan kein izdestiry massivi :");

for (i = 0; i < 100; i++)

{

if (a[i] < 10) Console.Write(" {0}", a[i]);

if ((i + 1) % 20 == 0) Console.WriteLine();

}

Console.WriteLine();

buf = Console.ReadLine();

k = Convert.ToInt32(buf);

Console.WriteLine("Blok olshemin engiziniz");

buf = Console.ReadLine();

b = Convert.ToInt32(buf);

// Блоктық іздеу алгоритмі

for (i=b-1;i<100;i=i+b)

if(k<=a[i])

{

j=i-b+1;n=i;

{

if (k==a[j])

f=1;i=100;

Console.WriteLine("Nomer:{0}", j);

}

j++;

}

if (f==0)

Console.ReadLine();

}

}

}

Izdestiry massivi:

26 3 28 95 59 6 49 15 46 21 26 61 91 72 37 60 14 34 36 88

48 65 91 14 48 47 46 52 45 75 18 43 29 15 55 56 35 64 37 56

56 73 8 57 10 68 22 64 45 78 54 41 6 42 0 8 12 14 47 12

7 44 70 18 50 30 32 23 64 81 72 50 97 27 79 75 57 81 51 80

72 82 7 14 21 77 84 87 15 47 44 68 17 25 49 12 50 37 54 80
Sandardi syriptalgannan kein izdestiry massivi :

0 3 6 6 7 7 8 8 10 12 12 12 14 14 14 14 15 15 15 17

18 18 21 21 22 23 25 26 26 27 28 29 30 32 34 35 36 37 37 37

41 42 43 44 44 45 45 46 46 47 47 47 48 48 49 49 50 50 50 51

52 54 54 55 56 56 56 57 57 59 60 61 64 64 64 65 68 68 70 72

72 72 73 75 75 77 78 79 80 80 81 81 82 84 87 88 91 91 95 97

44

Blok olshemin engiziniz

Nomer:43

Алгоритмнің кемшіліктері: іздестіру уақытының көп жұмсалуы, іздестіру массивін дайындау, яғни түйінді элемент бойынша сұрыптау.

6.3.3 Екілік іздеу алгоритмі. Екілік іздеу алгоритмі іздестіру массивінің элементтерін реттелген тәртіпте орналасуын талап етеді.

Іздестіру массивінің элементтері өсу ретімен орналасқан болсын. Сұратудың ізделетін кілті іздестіру массивінің орта элементімен салыстырылады.

Егер сұратудың ізделетін кілті іздестіру массивінің орта элементінен кіші болса, онда массивтің ортасы мен соңына дейінгі аралықтағы барлық элементтер кейінгі іздестіруде қолданылмайды, ал іздестіру массиві болып басынан ортасына дейінгі аралықта орналасқан барлық элементтер есептеледі.

Егер сұратудың ізделетін кілті іздестіру массивінің орта элементінен үлкен болса, онда массивтің басынан ортасына дейінгі аралықта орналасқан барлық элементтері кейінгі іздестіруде қолданылмайды, ал іздестіру массиві болып ортаншыдан кейін тұрған элементтен соңғы элементке дейін орналасқан барлық элементтер есептеледі.

Сонымен салыстыру операциясынан кейін іздестіру массивінің жартысы кейінгі іздестіруден шығарылды, сондықтан осы алгоритмді жартылай бөлу әдісі деп атайды .

Ары қарай бөлу процессі жаңа іздестіру массивімен қайталанады. Сұратуға сай элемент табылса немесе іздестіру массиві сұратуға сәйкес емес бір элементімен берілсе, онда іздестіру аяқталады.

Алпыс кездейсоқ, өсу тәртібінде құрылған бүтін сандарға арналған екілік іздеу алгоритмін орындайтын бағдарламаның коды мынандай:

using System;

namespace ConsoleApplication1

{

class Program

static void Main()

{ int i, n, k, x, f, m, c, p;

f = 0; m = 0; c = 0;

int[] a = new int[61];

Random rnd = new Random();

string buf;

// іздестіру массивін құру және экранға шығару

Console.WriteLine("Izdestiry massivi: ");

a[0] = rnd.Next() % 2 + 1;

for (i = 1; i < 60; i++)

{

a[i] = a[i - 1] + rnd.Next() % 2 + 1;

else Console.Write(" {0}", a[i-1]);

if ((i) % 20 == 0) Console.WriteLine();

}

if (a[i-1] < 10) Console.Write(" {0}", a[i-1]);

Console.WriteLine();

Console.WriteLine("Izdey kiltin engiziniz");

buf = Console.ReadLine();

p = Convert.ToInt32(buf);

// екілік іздеу алгоритмі

n = 0; k = 59;

while (n <= k)

{

x = (n + k) / 2;

if (p <= a[x]) k = x - 1; else n = x + 1;

c++;

}

// Іздеудің нәтижесін шығару

Console.Write("Izdey kiltine saikes element jok!");

else Console.WriteLine("Nomer:{0}", m+1);

Console.ReadLine();

}

}

}

Izdestiry massivi:

1 2 4 6 8 10 12 14 15 16 18 20 22 23 24 26 28 29 31 33

34 35 36 38 39 40 42 43 45 46 48 49 50 51 53 54 55 57 58 60

62 64 65 67 68 69 70 72 73 75 77 79 81 83 85 86 87 89 90 92

Izdey kiltin engiziniz

67

Nomer:44

Izdestiry massivi:

1 2 4 5 7 8 10 11 13 15 17 18 20 21 22 23 24 25 27 29

31 33 34 36 38 39 41 43 45 46 48 49 50 51 53 55 57 58 59 60

61 62 64 66 67 68 69 70 72 73 75 77 78 79 81 82 84 86 88 89

Izdey kiltin engiziniz

63

Izdey kiltine saikes element jok!

Алгоритмнің кемшілігі – массивті реттеу талабы. Егер іздестіру массивінде бірдей элементтер болса, онда алгоритмді «жетілдіру» керек. Мысалы, тауарлардың атаулары немесе қызметкерлердің тегі.

6.3.4 Кілтті адреске түрлендіретін іздеу алгоритмдері хештеу (хеширование) деп аталады. Іздестіру операцияларын орындау тұрғысынан деректерді ұйымдстырудың ең жақсы әдісі деректерді массив түрінде ұйымдастыру болып табылады, ал іздеу кілті ретінде индекс мәні қолданылады. Осы жағдайда керекті элементті табу үшін деректер массивіне бір рет жүгіну жеткілікті.

Әрине осындай жүйелер «таза» түрінде сирек кездеседі. Әдетте олар шағын жүйелер, мысалы, студент нөмірі немесе оқытушы коды бойынша керекті жазбаны табуға болады.

Деректер массивінің индексін табу үшін кілттерге арнайы хеш-функция (HF) арқылы кейбір түрлендірулерді орындау керек.

Хеш-функция ізделетін элементтің кілтін 0 мен n-1 аралығындағы сандық мәнге (индекске) түрлендіреді. Әлбетте элементтер мәнін сақтау үшін N ұяшығы (хеш-кесте) бар массив керек.

Егер мүмкін болатын кілттер n-ге тең немесе одан кіші болса, онда жүйе адреске баламалы кілтті жүйеге түрленеді.

Егер мүмкін болатын кілттер n-нен үлкен болса, онда хеш-функцияны қолдану керек. Ол 0 мен n-1 аралығында кілттерді біркелкі «таратуды» қамтамасыз етеді.

Әлбетте түрлі кілттерге бірдей индекстер тағайындалуы мүмкін, өйткені хеш-функция «көпшілігі біреуге» қағидасымен жұмыс істейді. Осындай жағдайды қақтығыс деп атайды.

Берілген мәнде ықтимал қақтығыстарды шектеуге мүмкіндік беретін хеш-функцияларды ұйымдастырудың түрлі әдістері бар.

Хеш-функцияны дайындау кезінде әдетте бөлу әдісін қолданады.

Ол бастапқы кезеңде кілтті бүтін санға түрлендіреді, ал одан кейін осы сан 0 мен n-1 аралығына қосылады.

Жолдық кілттер үшін сандық мәнді алуға арналған белгілі алгоритмнің бірі былай орындалады: әрбір жолдың байтына алдынғы мән мен белгілі бір тиянақталған көбейткіштің (хэш) көбейтіндісі қосылады.

Тәжірибе түрінде анықталған, 31 мен 37 мәндері хеш-функциясының ASCII жолдары үшін тиімді жиын болып келеді. Атап өту керек, бір деректерге арналған жақсы жұмыс істеп тұрған «хеш-функция» басқа түрге арналғандарға «жаман» жұмыс істеуі мүмкін. Мысалы, бір топ адамдардың (мысалы, студенттердің) туған жылдарына байланысты кілттер бойынша хеш-функциясын пайдалану өте қиын. Коллизияны алудың нұсқасының бірі әр хеш-кесте торына арналған тізімдік құрылымын пайдалану. Хеш-кесте мен жай тізімдерді пайдалануды көптеген авторлар информатиканың ең негізгі жаңалығы деп санайды.

Мысалы, «автомобильдер» анықтама жүйесін құру барысында автомобильдер нөмірінің сандық бөлігі бойынша хеш-функциясын пайдалануға болады.

Сандық бөлігі бойынша сәйкес келетін автомобилдерді (олар айырмашылығы әріптік бөлігінде) жай тізімге ұйымдастыру.

Осындай жүйеде іздеу екі кезеңде орындалады: біріншіде – нөмірдің сандық бөлігі бойынша, ал екіншіде нөмірдің әріптік бөлігінің тізімдегі реттілік іздеуінде.