UNTIL NOT(CH IN ['А'..'Z','0'..'9'])
END ELSE
IF CH IN ['0'..'9'] THEN BEGIN
SYM := NUMBER; NUM := 0;
REPEAT
NUM - 10 * NUM + ORD(CH) - ORD('0');
READ(CH)
UNTIL NOT(CH IN ['0'..'9'])
END ELSE
IF CH IN ['<', ': ', '>'] THEN BEGIN
CH1 := CH; READ(CH);
IF CH - '-' THEN BEGIN
IF CH1 = '<' THEN SYM := LEQ ELSE
IF CH1 = '>' THEN SYM := GEQ
ELSE SYM := BECOMES;
READ(CH)
END
ELSE SYM := S[CH1]
END ELSE
BEGIN {басқа символдар}
SYM := S[CH]; READ(CH)
END
END {SCANNER};
Ұсынылатын әдебиет
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных для
персональных ЭВМ.- М.: Мир,1989.
8. Яворский В. В., Богушевская А. А. Структуры данных и алгоритмы
их обработки.- Караганда: КарГТУ, 2004.- 150с.
СӨЖ-ге арналған бақылау жұмыстары
1.
Мәліметтердің негізгі типтері мен олардың ЭЕМ
жадысында көрсетілуі
2.
Құрылым
түсінігі.
Логикалық
және
физикалық
құрылымдар.
3.
Құрылымдар классификациясы.
4.
Массив мәліметтер құрылымы ретінде.
5.
Жолдар мәліметтер құрылымы ретінде.
6.
Жазба мәліметтер құрылымы ретінде. Қосу операторы.
7.
Нұсқалары бар жазбалар.
8.
Жиын мәліметтер құрылымы ретінде.
3 БӨЛІМ. ТІЗБЕКТІ ФАЙЛ
Дәріс жоспары
1 Тізбекті файлдардың негізгі қасиеттері
2 Тізбекті файлдарды сұрыптау
3.1 Тізбекті файлдардың негізгі қасиеттері
Қайталанбау үшін файлдарға қолданылатын опреацияларды бейнелеу
бөліміне тоқталмастан, біздің пәніміздің контекстінде файлды қысқаша
қарастырамыз. Алдында қарастырылған мәліметтер құрылымының жалпы
қасиеті - оның компоненттерінің саны шекті (яғни, кардинальды сан шекті).
Күрделі құрылымдарда – тізбектер, ағаштар, графтар, т.с.с. – біз
компонент сандарын білмеуіміз мүмкін (яғни кардинальды сандар шексіз).
Осындай құрылымдардың ең қарапайымы тізбек болып табылады
(тізбекті файл). Тізбек бір типті компоненттерден тұрады. Компоненттердің
реті – табиғи, яғни бір-бірінен кейін. Элементтерге ерікті қатынау жүзеге
асатын массивтан ерекшелігі – тізбекті файлда кез келген уақытта файлдың
тек қана бір элементіне қатынай аласыз. Басқа элементтерге файл бойынша
тізбекті жылжып отырып қатынайсыз.
"Тізбекті файл" типінің құрылымын формальді (логикалық) түрде
келесі түрде анықтауға болады.
Т
0
базалық типі бар тізбек – бұл немесе бос тізбек, немесе элементтер
(Т
0
базалық типінің) тізбегінің және Т
0
типінің элементінің конкатенациясы.
Осылайша логикалық құрылымның Т типі мәндердің шексіз санына ие.
Бірақ та, әрине, әрбір нақты мән компоненттердің шекті санынан тұрады,
бірақ бұл сан шектелмеген. Кез келген ұзын тізбекке тағы бір элементті
жазып қоюға болады, бірақ тек соңына ғана.
Тізбекке қатысты тағы бір айта кететін жайт, бұл құрылым күрделі
болып табылса да, бірақ кеңінен қолданылады, яғни фундаментальді
құрылымдар құрамына енгізілген. Тізбектер сыртқы жады бойынша
орналасқан – бұнда алдыңғы қарастырылған құрылымдардан тағы бір
ерекшелігі бар: тізбек опреативті құрылым болып табылмайды.
Т
0
ретінде кез келген қарапайым және құрылымдалған тип бола алады,
бірақ файл емес.
Еске түсірейік, файлға екі нақты әрекет орындауға болады:
1) файлды көру. Бұл файл бойынша басынан бастап тізбекті
қозғалудың нәтижесінде орындалады;
2) файлды жасау. Бұл бастапқы бос файлға жаңа компоненттерді қосу
нәтижесінде орындалады.
Сонымен қатар, кейбір есте сақтау құрылғылары онда сақталған
ақпаратқа тек қана тізбекті қатынауға жол береді. Бұл, бәрінен бұрын,
магнитті ленталар. Бірақ, тіпті, магнитті ленталарда да бөлек жолдар өз
алдына тізбекті қатынауы бар есте сақтау құрылғысын көрсетеді. Қатал
айтқанда, тізбекті қатынау – механикалық ауыстырылуы бар барлық
құрылғылардың негізгі қасиеті, және кейбір басқалардың да.
3.2 Тізбекті файлдарды сұрыптау.
Жалпы түрдегі сұрыпау есебін есе түсірейік. Мынадай элементтер
берілген
.
,...
,
2
1
n
a
a
a
Сұрыптау дегеніміз осы элементтердің ауыстырылуын білдіреді, ол
мынадай
n
k
k
k
a
a
a
,...,
,
2
1
ретпен ауысу керек, берілген реттеу функциясы ƒ бойынша мына
қатынас дұрыс болу керек
)
(
...
)
(
)
(
2
1
n
k
k
k
a
f
a
f
a
f
≤
≤
≤
Әдетте реттеу функциясы элементтің өзінде нақты компонент (өріс)
түрінде сақталады және оның мәндерін элементтің кілті деп атайды.
Осыдан, a
i
элементін көрсету үшін жазбаның мына типі жақсы келеді:
TYPE ITEM
=
RECORD
KEY: INTEGER;
{басқа компоненттер}
END
"Басқа компоненттер" осы элемент туралы барлық маңызды
мәліметтерді құрайды. Сұрыптаудың міндеті үшін жалғыз маңызды
компонент кілт болып табылады.
Массивтердегі сұрыптаудың кейбір әдістерін қарастырайық. Өкінішке
орай, егер сұрыпталатын мәліметтер оперативті жадыда болса, олар
қолданылмайды, ал сыртқы ЕҚ-да тізбекті қатынау (тізбекті файлдар). Бұл
жағдайда уақыттың әрбір мезетінде тек қана бір элементке қатынауға
болады. Бұл шектеу тізбекті файлдарға сұрыптаудың басқа әдістерін
қолдануға әкеледі.
Негізгі әдіс – біріктіру арқылы сұрыптау. Біріктіру дегеніміз дәл осы
уақытта мүмкін элементтердің циклді таңдалуының көмегімен екі (немесе
одан көп) реттелген тізбектерді бір реттелген тізбекке біріктіру. Слияние –
сұрыптауға қарағанда неғұрлым қарапайым опрация.
Мұндай сұрыптаудың әдістерінің бірі қарапйым слияние деп аталады,
және келесіде тұрады.
1.
а тізбегі b және с екі бөлігіне бөлінеді.
2.
b және с тізбектері бөлек элементтерді реттелген жұптарға
біріктіру көмегімен біріктіріледі.
3.
Алынған тізбекке а аты меншіктеледі де, одан кейін 1 және
2 қадам қайталанады; бұл кезде реттелген жұптар реттелген төрттікке
біріктіріледі.
4.
Алдыңғы қадамдар қайталанады, тізбек ұзындығы әркез екі
есе үлкейгендіктен, барлық тізбек реттелгенше төрттіктер сегіздіктерге
біріктіріледі, және т.с.с.
Мысал. Тізбек
Достарыңызбен бөлісу: |
