Лекция тезистері
жүктеу/скачать 382.54 Kb.
|
- Бұл бет үшін навигация:
- Тақырып №11. « Деректердің сызықты емес структурасы »
| Дәріс жоспары:
Жадыда деректердің байланысының берілуі Сызықты байланысты тізімдер Сызықты емес тармақталған тізімдер Деректердің динамикалық структурасы өлшемі айнымалы, жадыдан алдын ала орын босатылмайтын, программаны орындаған сайын мәндері, мәндерінің саны өзгеріп отыратын деректер. Динамикалық деректердің элементтерінің арасында байланыс орнату үшін көрсеткіштер қолданылады. Олар әр динамикалық элементтің жадыдағы адресін көрсетіп тұрады. Динамикалық деректер структурасының элементтері екі өрістен тұрады: 1. деректер өрісі - ақпараттық өріс, ол массив, жазу, вектор т.б. бола алады. 2. байланыс өрісі - белгілі бір элементті басқа структураның элементімен байланыстыратын бір немесе бірнеше көрсеткіштер бола алады. Деректердің байланыстырылып көрінуінің жетістігі – структураларды барынша өзгерту мүмкіндігінде: структуралардың мөлшері машиналық жадының қолдануға болатын көлемімен шектеледі; структура элементтері логикалық тізбегін өзгерткенде жадыдағы деректерді ауыстырудың қажеті жоқ, оның орнына көрсеткіштер жылжиды, түзетіледі. Деректердің байланыстырылып көрінуінің кемшілігі: көрсеткіштермен жұмыс жасау үшін программисттің квалификациясы жоғары болуы керек; байланыс қрістеріне қосымша жады бөлінеді; уақытты үнемдемейді; Сызықты байланыстырылған тізімдер. Тізім дегеніміз элементтерінің саны өзгермелі, енгізу, шығару операцияларын қолдануға болатын реттелген жиын. Элементтерінің арасында көршілік қатынасты бейнелейтін тізімді сызықты тізім дейді. Бірбайланысты тізімді өңдеу тиімді емес, себебі қарама қарсы бағытта қозғалу мүмкіндігі жоқ. Ондай мүмкіндіктер екі байланысты тізімдерде бар, оларда екі көрсеткіш болады, біреуі алдыңғы біреуі келесі элементті көрсетіп тұрады. Сызықты байланысты тізімде NEXT өрісі бар – ол тізімдегі келесі элементті көрсеткіш деп аталады. PREV өрісі бар – ол тізімдегі алдыңғы элементті көрсеткіш деп аталады. Тізімдегі соңғы элементті көрсеткіш те қолданылады, ол NIL болады. Екі көрсеткішті анықтау, оларды жылжыту арқылы элементтерді өңдеу көп уақытты алады, бірақ тізімге қолданылатын кейбір операцияларға оларды қолдану тиімді. Сызықты емес тармақталған тізімдер. Сызықты емес тармақталған тізімдер деп элементтері тізім болатын тізімдерді айтады. Егер екі байланысты тізімде көрсеткіштердің біреуі басқа көрсеткіш ретіне кері ретпен берілсе, ондай тізім сызықты тізім болады, егер көрсеткіштің біреуі кез келген ретпен берілсе, онда тізім сызықты емес тізім деп аталады. Тармақталған тізім үш ұғыммен сипатталады: реті, тереңдігі, ұзындығы. Реті. Тізім ішінде элементтер пайда болатын тізбекпен анықталатын тізім элементіне транзитивті қатынас берілген. (x,y,z) тізімінде х атомы у-тің алдыңғысы, ал у атомы z-тің алдыңғысы, сонда х атомы z-тің алдыңғысы болатыны білінеді. Берілген тізім (y,z,x) тізіміне эквивалентті болмайды. Тізімді графикалық схема көмегімен бергенде тізім реті горизонтальды стрелкамен анықталады: элементтен стрелка шығып тұрса,онда ол көрсетіп тұрған элементтің алдыңғысы екенін білдіреді. Тереңдігі. Тізім ішіне сиятын элементтердің максималды деңгейі тереңдігін білдіреді. Тізім ішінде ішкі тізім болса, олар кірістірілген тізімдер болады және дөңгелек жақшаға алынады. Өзін тексеру сұрақтары Жадыда деректердің байланысы қалай беріледі? Сызықты байланысты тізімдер деген не? Сызықты емес тармақталған тізімдер деген не? Ұсынылатын әдебиеттер Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г. Острейковский В.А. Информатика, Москва, 2000 г. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990. Тақырып №11. «Деректердің сызықты емес структурасы» жүктеу/скачать 382.54 Kb. Достарыңызбен бөлісу:
|