1.3. Иерархиялық және желілік құрылымдарды көрсету.
Тоғай тәрізді және желілік құрылымды физикалық ұйымдастыру кезінде екі сұрақты шешу қажет:
құрылымның төбесімен (тораппен) көрсетілген деректерді ұйымдастыру;
құрылым доғасымен көрсетілген деректер арасында байланыстарды ұйымдастыру.
Жадыны тізбектей бөлуді пайдалануға негізделген тоғай тәріздес құрылымды көрсетудің келесі әдістері бар:
1) Адрестік арифметика әдісі. Берілген әдісті жетілдірудің екі әдісі бар – олардың бірі бірінші тораптан бастап, тізімдер торабын тізбектей орналастыруға негізделген. Берілген жоба балансталған тоғайларды жетілдіру үшін ыңғайлы, яғни кез келген тораптан туындаған тораптар саны, соңғысынан басқа, тоғайлар бірдей болады. Кез келген тораптың адресі алдында келтірілген адрестік функция көмегімен табылады; бірақ ең қызықтысы торап-ұрпақтардың (потомок) адрестік функциясы болып табылады. Үшінші ретті тоғай үшін белгілі бір k торабының ұрпағы 3k-1, 3k, 3k+1 тізімінің ерекшеленген торабына жады квантасында орналасады. Негізді кемшілігі төртінші және одан да жоғары ретті балансталған тоғайлар үшін адрестік функция күрделілігі болып табылады. Екінші әдіс екілік тоғайлар (екінші ретті балансталған тоғайлар) үшін ғана қолданбалы және тізімді орналастыру үшін бөлінген жады векторының ортасына тізімнің бірінші торабын орналастыруға негізделген, яғни  адресімен жады ұяшығына, мұндағы i және j – тізімді орналастыру үшін бөлінетін жадының бастапқы және соңғы квантасының адресі. i -ден l-1-ге дейін жады квантасында сол жақ тоғайасты деп аталатын, ал l+1 –ден j-ге дейін оң жақ тоғайасты орналастырылады.
2) Сол жақ тізімді құрылым әдісі алғашқы тоғай тәріздес құрылымды жоғарыдан төмен және сол жақтан оң жаққа айналып өту (обход) жолымен тізім құруға негізделген. Сол жақ тізімді құрылым әдісі кез келген тоғайлар үшін қолданбалы.
Байланысқан жадыны бөлуді пайдалануда тоғай тәріздес құрылымды көрсетудің келесі әдістері негізделген:
1) Туындаған жазбаларға көрсеткіштер әдісі – берілген әдіс тоғай бойымен түзу бағытта қозғалуды өндіруге мүмкіндік береді. Бұл әдісті пайдаланған жағдайда кез келген жазба, төменгі деңгейдің жазбасынан басқа, туындаған жазбада бар көрсеткіштер санымен тең болуы керек.
2) Алғашқы жазбаға көрсеткіштер әдісі тоғай бойымен кері бағытта – түпкі тораптардан түбіне жүруді ұйымдастыру үшін пайдаланылады.
3) Алғашқы және туындаған жазбаларға көрсеткіштер әдісі – берілген әдіс тоғайдың түзу де, кері де бағытта жүріп өтуін қамтамасыз етеді, өйткені екібағытты тізім пайдаланылады. Әдістің кемшілігі – туындаған жазбаларға көрсеткіштер әдісі сияқты, өйткені тораптарда көрсеткіштер саны ауыспалы және туындаған жазбалар санымен анықталады.
4) Туындаған және сол сияқты жазбаларға көрсеткіштер әдісі тоғайдың түзу бағытта өтуін қамтамасыз етеді. Туындаған жазбаларға көрсеткіштер әдісімен салыстырғанда берілген әдістің ерекшелігі көрсеткіштердің шектеулі саны – соңғы торабында бір көрсеткіштен және қалғандарында екеуден болып табылады. Бірақ сол сияқты жазбалар санының өсуімен жазбаларға кіру уақыты көрсеткіштер тізбегі бойынша кіру тізбегі есебімен өседі.
5) Алғашқы, туындаған және сол сияқты жазбаларға көрсеткіштер әдісі – берілген әдістің артықшылығы мен кемшілігі алдыңғы әдістер үшін қарастырылғандарға ұқсас; ерекшелігі берілген әдісті пайдалану кезінде тоғай бойымен кері жүруді ұйымдастырудан тұрады.
6) Сақиналы құрылым әдісі – бірбағытты циклді тізімдер туындаған және сол сияқты жазбаларға әрбір торапқа екі көрсеткіштен енгізе отырып, алғашқы тоғай тәріздес құрылымды алуға мүмкіндік береді. Берілген әдістер жазбаларға кіру уақыты туындаған және сол сияқты жазбаларға көрсеткіштер әдісін пайдалану кезінде жазбаларға кіру уақытына тең. Екібағытты циклді тізімдерді пайдалану кезінде әрбір торапқа туындаған және сол сияқты жазбалардың сақинасы бойымен түзу және кері айналым үшін төрт көрсеткіш қосылады.
7) Анықтамалар әдісі – берілген әдісте көрсеткіштер жазбалардан жойылады және арнайы файлдар – анықтамаларға ұйымдастырылады. Әдістің артықшылығы: анықтамаларда тек көрсеткіштер сақталатындықтан олар өлшемі бойынша көбінесе кіші, оларда алғашқы деректердің жазбалары сақталады. Сондықтан анықтама жедел жадыға оқылуы мүмкін және байланыстың барлық өңделуі жедел жадыда орындалады, содан кейін қажет алғашқы жазбалар сыртқы жадыдан оқылады, ол өңдеудің жылдамдығын ұлғайтады.
Желілік құрылымды көрсету үшін желілік құрылымды өндіруге мүмкіндік беретін жоғарыда қарастырылған әдістердің белгілі бір комбинациясын пайдаланады. Мысалы, туындаған, сол сияқты және алғашқы жазбаларға көрсеткіштермен әдістердің комбинациясын пайдаланады. Көбінесе сақиналы құрылым пайдаланылады.
Егер жазбада көрсеткіштер саны шектеулі болған жағдайда, онда күрделі емес желілік құрылым өндіруге болады. Күрделі желілік құрылым үшін айнымалының әрбір жазбасы үшін көрсеткіштер енгізу қажет.
Желілік құрылымды ұйымдастырудың ең тиімді әдісі анықтамаларды пайдалану болып табылады. Сонымен қатар, көрсеткіштер жазбалардан алынып, жеке файлдарға – анықтамаларға орналастырылады. Анықтаманы сәйкес бөлімде деректерді іздеуді тез орындайтындай етіп оптималды түрде ұйымдастыруға болады. Анықтамаларды пайдалану желілік құрылым күрделілігіне тура пропорционал деп айтуға болады.
Достарыңызбен бөлісу: |
