Dásturiy injiniringi baǵdari 2-kurs 304-22 topar studenti Bazarbayeva Muxaddastıń Maǵlıwmatlar strukturası hám algoritmler páninen

2.1 Terek tarizli maǵlıwmatlar strukturaları
" Terek tárizli maǵlıwmatlar strukturası" (Tree structure information architecture) bul sózler, maǵlıwmatlar strukturasınıń ayrıqsha struktura formasın ańlatadı. Terek tárizli struktura, maǵlıwmatlardı joqarı hám tómen basqıshlar, yamasa ata-ana munasábetler arqalı táriyplew ushın isletiledi. Bunday struktura " terek" yamasa " háreket" formasındaǵı grafik súwretler arqalı kórsetilgen bolıwı múmkin.
Bul struktura forması, qurılǵan bir hiarxik yamasa strukturalıq qatarı arqalı maǵlıwmatlardı quraydı. Hár bir qatarda bir yamasa bir neshe joqarı dárejeli maǵlıwmatlar, olardıń tómen dárejedegi baylanıslılıq qatarı menen baylanısqan bolıwı múmkin. Bul struktura qásiyetlerin atap ótiwde tómendegi maǵlıwmatlardı óz ishine aladı :
Joqarı dáreje (Root Level): Basqa dárejeler menen baylanıslı bolmaǵan, eń joqarı dárejedegi maǵlıwmatlar yamasa bas bólegi kórsetilgen. Bul dáreje bas struktura yamasa tiykarǵı maǵlıwmatlar qatarı retinde de islewi múmkin.
Tómen dárejeler (Sub-levels): Joqarı dárejedegi maǵlıwmatlar arqalı, olarǵa baylanıslı bolǵan tómen dárejedegi maǵlıwmatlarǵa ótiw múmkin. Hár bir tómen dáreje, ayriqsha struktura hám oǵan tiyisli maǵlıwmatlar menen tanısadı.
Baylanısıwlar (Links): Terek tárizli struktura, hár bir dáreje arqalı baylanıslılıq qatarların ańlatadı. Bul qatarlar, bir dárejedegi maǵlıwmatlardı basqa dárejedegi maǵlıwmatlar menen baylanıstırıp alıwda járdem beredi.
Endi maǵlıwmatlar (Leaf Nodes): Terek tárizli strukturanıń eń tómen dárejesinde jaylasqan, basqa dárejelerge baylanıslılıq qatarları almaytuǵın maǵlıwmatlar. Bul maǵlıwmatlar, eń sońǵı waqıtta ótiletuǵın, tuwrıdan-tuwrı paydalanıwshına usınıs etilgen maǵlıwmatlar bolıwı múmkin.
Terek tárizli maǵliwmatlar strukturası, sonıń menen birge, qolay hám ańsat túsinikli struktura formalarınan biri bolıp, kóplegen web-saytlar, qosımshalar, sistemalar, hám basqa platformalarda paydalanıladı. Bul struktura forması, paydalanıwshılarǵa maǵlıwmatlar menen islewde ańsatlıq hám kórsetkishlik usınıwda járdem beredi.
Uzeller (elementler) hám olardıń munasábetlerinen ibarat elementler toplamınıń ierarxik strukturasına terek tárizli maǵlıwmatlar strukturası dep ataladı. Terek - bul sonday sızıqsız baylanısqan maǵlıwmatlar strukturası, ol tómendegi belgileri menen xarakterlenedi:
- terekte sonday bir element bar, oǵan basqa elementlerden shaqırıq joq. Bul element terek túbiri dep ataladı ;
- terekte qálegen element shekli sandaǵı kórsetkishler járdeminde basqa túyinlerge shaqırıq etiwi múmkin;
- terektiń hár bir elementi tek ǵana ózinen aldınǵı kelgen bir element menen baylanısadı.
Binar tereklerdi qurıw Binar terekte hár bir túyin-elementten kóbi menen 2 shaqa shıǵadı. Tereklerdi yadta súwretlewde onıń túbirin kórsetiwshi kórsetkish beriliwi kerek. Tereklerdi kompyuter yadında súwretleniwine kóra hár bir element (binar terek túyini) tórt maydanǵa iye jazıw formasında boladı, yaǵnıy gilt maydan, informacion maydan, bul elementti ońda hám shebinde jaylasqan elementlerdiń yaddaǵı adresleri saqlanatuǵın maydanlar. Sonı este tutıw kerek, terek payda etip atırǵanda, ataga salıstırǵanda shep táreptegi bala mánisi kishi giltke, oń táreptegi bala bolsa úlken bahalı giltke iye boladı. Hár sapar terekke jańa element kelip qosılǵanda ol eń dáslep terek túbiri menen salıstırıladı. Eger element túbir gilt mánisinen kishi bolsa, onıń shep shaqasına, keri jaǵdayda oń shaqasına ótiledi. Eger ótip ketilgen shaqada túyin ámelde bolsa, bul túyin menen de salıstırıw ámelge asırıladı, keri jaǵdayda, yaǵnıy ol shaqada túyin ámeldegi bolmasa, bul element sol túyinge jaylastırıladı. Eger terektiń oń hám shep bólim terekleri basqıshlarınıń parqı birden kishi bolsa, bunday terek ideal teń salmaqlılıqlanǵan terek dep ataladı.
Algoritm basqa kórinislerde de beriliwi múmkin. Biz endi algoritmlerdiń eń kóp ushraytuǵın túrleri menen tanısamız. 1. Algoritmnıń sózler arqalı ańlatılıwı. Bul usılda atqarıwshı ushın beriletuǵın hár bir kórsetpe gápler, sózler arqalı buyrıq formasında beriledi. 2. Algoritmniń formulalar menen ańlatılıw usılınan matematika, fizika, ximiya sıyaqlı anıq pánler degi formulalardı úyreniwde paydalanıladı. Bul usıl geyde analitik ańlatıw dep ataladı. 3. Algoritmlerdiń arnawlı geometriyalıq sırtqı kórinisler járdeminde ańlatılıwında másele sheshiw procesi anıq hám tuwri súwretlenedi jáne bul kórinis blok -sxema dep ataladı. 4. Algoritmnıń keste kóriniste beriliwi.
Algoritmnıń bunday ańlatpasınan da kóp paydalanamız. Mısalı: mektepte qollanıp kelinip atırǵan tórt xanalı matematikalıq kesteler yamasa hár qıylı lotereyalar kestesi. Funksiyalardıń grafikların sızıwda da algoritmlerdiń bahaları kestesi kórinislerinen paydalanamız. Bul sıyaqlı kestelerden paydalanıw algoritmleri ápiwayı bolǵanı sebepli olardı ózlestirip alıw ańsat. Joqarıda kórilgen algoritmlardı súwretlew usıllarınıń tiykarǵı maqseti, qoyılǵan máseleni sheshiw ushın zárúr bolǵan ámeller izbe-izliginiń eń qolay jaǵdayın anıqlaw hám usınıń menen insan tárepinen programma jazıwdı jáne de ańsatlastırıwdan ibarat. Tiykarınan, programma da algoritmnıń basqa bir kórinisi bolıp, ol insannıń kompyuter menen baylanısin qolaylaw ámelge asırıw ushın mólsherlengen.
Házirgi waqıtta onlıq sanaq sistemasında arifmetik ámellerdi orınlaw usılları esaplaw algoritmlarına ápiwayıǵana mısal bóle aladı tek. Házirgi zaman kózqarasınan algoritm túsinigi neni ańlatadı? Ekenin aytıw kerek, insan kúndelik turmısında hár túrli islerdi atqaradı. Hár bir jumıstı orınlawda bolsa bir qansha elementar (mayda ) islerdi izbe-iz ámelge asırıwǵa tuwrı keledi. Mine sol izbe-izliktiń ózi atqarılatuǵın jumıstıń algoritmı bolıp tabıladı. Biraq bul izbe-izlikke itibar bersak, biz atqarıw jetip atırǵan elementar jumıslar málim qaǵıyda boyınsha orınlanıwı kerek bolǵan izbe-izlilikden ibarat ekenligin kóremiz. Eger bul izbe-izlilikdegi qaǵıydanı buzsak, maqsetke eriwmasligimiz múmkin.
Mısalı: shaxmat oyının baslawda shohni yura almaymız, sebebi bul oyın algoritmında júriwdi basqa bir shaxmat danalarınan baslaw kerek yamasa palaw pısırıw algoritmında birinshi náwbette qazanǵa suw salıp kórińshi, palaw qanday bo'lar eken. Berilgen matematikalıq ańlatpanı ápiwayılastırıwda ámellerdiń atqarılıw izbe-izligine itibar bermaslik nadurıs nátiyjege alıp keliwi barlıqǵa málim.
Sonday eken jumıstı, yaǵnıy qoyılǵan máseleni orınlawǵa mayda elementar islerdi arnawlı bir izbe-izlilikde orınlaw arqalı. Bunnan kórinip turıptı, olda, hár bir jumıs qanday da algoritmdıń orınlanıwınan ibarat esaplanadi. Algoritmdı orınlawshı algoritm atqarıwshısı bolıp tabıladı. Algoritmnıń atqarıwshısı máseleniń qanday qoyılıwına itibar bermegen halda nátiyjege jetiwi múmkin. Onıń ushın ol tek aldınan málim qaǵıyda hám kórsetpelerdi qatań orınlawı shárt. Bul bolsa algoritmnıń júdá zárúrli qásiyetlerinen biri bolıp tabıladı.
Endi terek tárizli maǵlıwmatlar strukturasına C++ dastúrlew tilinde mısal keltirip ótemis.
Mısal:
1 #include
2 #include
3 // Fudbolshı klası
4 class FootballPlayer {
5 public:
6 std::string name;
7 int goals;
8 // Konstruktor
9 FootballPlayer(std::string playerName) : name(playerName), goals(0) {}
10 // Gol qosıw
11 void scoreGoal() {
12 goals++;
13 }
14 };
15 // Komanda klası
16 class Team {
17 public:
18 std::string name;
19 std::vector players;
20 // Konstruktor
20 Team(std::string teamName) : name(teamName) {}
22 // Fudbolshi qosıw
23 void addPlayer(std::string playerName) {
24 FootballPlayer player(playerName);
25 players.push_back(player);
26 }
27 // Komandadaǵı jámi gol sanı
28 int getTotalGoals() {
29 int totalGoals = 0;
30 for (const FootballPlayer& player : players) {
31 totalGoals += player.goals;
32 }
33 return totalGoals;
34 }
35 };
36 int main() {
37 // Fudbolshılar hám komandalardı jaratiw
38 Team barcelona("Barcelona");
39 barcelona.addPlayer("Lionel Messi");
40 barcelona.addPlayer("Xavi Hernandez");
41 barcelona.addPlayer("Andres Iniesta");
42 Team realMadrid("Real Madrid");
43 realMadrid.addPlayer("Cristiano Ronaldo");
44 realMadrid.addPlayer("Sergio Ramos");
45 realMadrid.addPlayer("Karim Benzema");
46 // Gol qosıw
47 barcelona.players[0].scoreGoal(); // Messi 1 gol qostı
48 realMadrid.players[1].scoreGoal(); // Ramos 1 gol qostı
49 barcelona.players[0].scoreGoal(); // Messi jáne 1 gol qostı
50 // Jámi gol sonın shıǵarıw
51 std::cout << barcelona.name << " jámi " << barcelona.getTotalGoals() << " 52 gol" << std::endl;
53 std::cout << realMadrid.name << " jámi " << realMadrid.getTotalGoals() << 54 " gol" << std::endl;
55 return 0;
56 }
Natiyje:

Bul programmada, " FootballPlayer" klası fudbolshı obyektin ańlatadı, " Team" klası bolsa komanda obyektin quraydı. Komandaǵa fudbolshılar qosıw, gol qosıw hám jámi gol sanın alıw ushın metodlar engizilgen. Programma engizilgen mısal jol menende Barcelona hám Real Madrid komandaları hám olardıń fudbolshıları arasındaǵı gol sanın kórsetedi.
Usı programmalıq kodtıń terek tarizlı kórinisi.

Fudbolshılar

├── Barcelona
│ ├── Lionel Messi
│ ├── Xavi Hernandez
│ └── Andres Iniesta
└── Real Madrid
├── Cristiano Ronaldo
├── Sergio Ramos
└── Karim Benzema