Алгоритмдер жєне деректер структурасы



бет22/41
Дата05.09.2020
өлшемі0,89 Mb.
#77252
1   ...   18   19   20   21   22   23   24   25   ...   41
Байланысты:
5bacf48a-311c-11e3-8846-f6d299da70eeУМК-алг (1)

Дәріс жоспары:

  1. сандық типтер

  • бүтін

  • нақты

  • ондық

  • сандық типтерге қолданылатын операциялар

  1. Биттік типтер

  2. Логикалық типтер

  3. Терілімді типтер

  4. Шектелген типтер

  5. Көрсеткіштер

Деректер структурасы қабылдайтын мәндерінің түрлеріне қарай келесі типтерге бөлінеді:



    1. Сандық типтер

    2. Биттік типтер

    3. Логикалық типтер

    4. Символдық типтер

    5. Терілімді типтер

    6. Шектелген типтер

    7. Көрсеткіштер

    8. Тізімдер

    9. Жазулар

    10. Файлдар

    11. Массивтер

    12. Жиындар

    13. Таблицалар

    14. Стектер

    15. Кезектер

    16. Дектер

    17. Жолдар

    18. Динамикалық типтер

    19. Графтар

    20. Ағаштар (бұтақтар)

Жай типтерге жататындары:

  1. Сандық

  2. Биттік

  3. Логикалық

  4. Символдық

  5. Терілімді

  6. Шектелген

  7. Көрсеткіштер

Сандық типтер нақты-ондық, бүтін типтер деп бөлінеді. Бүтін сандар көмегімен табиғаты жағынан дискретті – объектілерінің саны санаулы болатын объектілердің саны беріледі. Таңбалы сандарды ЭЕМ-ң жадысында орналастыруда екілік кодпен немесе қосымша кодпен кодтау әдісі қолданылады. Олардың ұзындығы 1,2,4 байт болуы мүмкін. Осыған байланысты бүтін типті деректердің өзі ұзын бүтін, қысқа бүтін, бүтін болып бөлінеді, оларға сәйкес байттық орындар бөлінеді.

Нақты типті деректердің өзі тұрақты нүктелі, айнымалы нүктелі болып бөлінеді, олардың да жадыдағы байттары әртүрлі. Бүтін сандардың мәні жадыда дәл анықталса, нақты сандардың мәні белгілі бір дәлдікпен анықталады.

Биттік типтер деректердің екілік разрядтарымен жұмыс жасауға көмектееді. Биттік типтер бір бірімен байланысы жоқ байттардың жиыны.

Логикалық типтер логикалық ақиқат, жалған, иә, жоқ сияқты мәндерді қабылдайтын, 1 байт орын алатын деректер.

Символдық типтер алдын ала анықталған символдар жиыныннан қабылданатын мәндер. Дербес ЭЕМ-дерде көбіне стандартты ASCII –символдар коды таблицасы орнатылған, одан басқа EBCDIC-кодтар таблицасы да бар. Символдық типті деректерге салыстыру, жалғастыру операциясы қолданылады.

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

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

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

Өзін тексеру сұрақтары

1. Деректердің қандай типтері бар?

2. Сандық типтер қалайша бқлінеді?

3. Күрделі типтер қалайша бөлінеді?

Ұсынылатын әдебиеттер


  1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.

  2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.

  3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.

  4. Острейковский В.А. Информатика, Москва, 2000 г.

  5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.


8-тақырып: «Деректердің статикалық структурасы»

Дәріс жоспары:

  1. векторлар

  2. массивтер

  3. жиындар

  4. жазулар

  5. таблицалар

Деректердің статикалық структурасы базалық, примитивті структуралардың құрылымды жиынынан тұрады. Оларға жады тұрақты-автоматты түрде бөлінеді, себебі олардың мәндері өзгермейді.

Векторлар – бір өлшемді массивтер- бір типті саны санаулы элементтер жиынынан тұратын деректер. Вектордың әр элементінің нөмірі оның тұрған орнын анықтайды. Элементтері тізбектелген ұяшықтар жиынын құрайды. Элементтің типіне қарай жадыдан байттар бөлінеді. Жады көлемі элементтер санын элементтер ұзындығына көбейту арқылы анықталады.

Массивтер – екі өлшемді, көп өлшемді болады.

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

Массивті қолдану үшін оның атауы және индексі анықталуы керек. Екі индексті массив екі өлшемді, үш индексті массив үш өлшемді деп аталады.

Жазулар (структуралар).

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

Жазуларды белгілі бір заттық облыстан алынған объектіні толық анықтап, программалау үшін қолданған тиімді. Жазу өрістермен құралады. Өрістерді компоненттер деп те атайды. Жазу деректер таблицасын еске түсіреді. Таблицаның бағандарының атаулары өрістер, таблицаның әр жолы жазу немесе жазба деп аталады Программада жазулар өздерінің атауымен және өріс атауымен біріктіріліп қолданылады.

Жиындар - біртипті, мәндері қайталанбайтын деректердің жиынтығы.

Жиын базалық типке жататын деректердің бәрін қабылдайды. Базалық тип 256 мүмкін мәндерден аспауы керек, жадыда 32 байтқа дейін орын алады және массивтер сияқты орналасады, элементтері индекстеледі.

Таблицалар - элементтері жазу болатын векторды айтуға болады. Вектор сияқты әр элементі индекстелмейді. Әр өрісті толық анықтайтын кілттік өріс тағайындалып, сол кілт бойынша деректер қолданылады. Кілт - біртипті көп жазулардың жиынынан таңдалынатын мәндері қайталанбайтын белгілі бір өріс. Бір таблицада бір немесе бірнеше кілт болуы мүмкін. Таблицаға логикалық деңгейдегі операциялар қолданылады: іздеу, сұрыптау.

Іздеу операциясы екі әдіспен орындалады:

1. Біртіндеп іздеу немесе сызықты іздеу

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

2. Бинарлы іздеу.

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

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

- Қол астында бар жады ресурсы: енгізілетін және шығарылатын жиындар жадының әртүрлі облысында орналасуы керек пе, әлде шығарылатын жиындар енгізілетін жиындардың орнына жазылуы керек пе - сол зерттеледі.

- Енгізілетін жиындар бастапқы кезден бастапреттелген болуы.

- Операцияның уақытша мінездемесі: алгоритмнің жылдам орындалуы үшін кілттік өрістің мәндері сандық тип немесе символдық тип болуы ескеріледі.

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

Сұрыптау стратегиялары:

1. Таңдау стратегиясы. - енгізілетін жиыннан реттелу шартын қанағаттандыратын элемент таңдалынып алынады да номеріне байланысты орны анықталып, шығарылатын жиынға енгізіледі.

2. Енгізу стратегиясы - енгізілетін жиыннан номерлі элемент таңдалынып, реттелу шартына сәйкес орнын анықтап шығарылатын жиынға енгізіледі.

3. Тарату, орналастыру стратегиясы - енгізілетін жиын бірнеше ішкі жиынға бөлінеді де, сұрыптау әр ішкі жиында жүргізіледі.

4 Біріктіру, жымдастыру стратегиясы - Сұрыпталған әрбір ішкі жиынды жымдастыру арқылы шығарылатын жиын құрастырылады.
Көпмүшелікті Горнер схемасымен есептеу алгоритмі
y= a0xn+a1 xn-1+…+an-1 x + an теңдеуімен берілген көрсеткіші n-ге тең көпмүшеліктің мәнін есептеү керек.

Горнер схемасы бұл көпмүшеліктегі көбейту және қосу амалдарының санын максималды азайтады.

n=2 болсын, сонда көпмүшелік былай жазылады:

y= a0x2+a1x1+a2 -> 3көбейту, 2 қосу амалдары бар бұл өрнекті былай жазуға болады:

y= (a0x2+a1)x+a2 -> 2 көбейту, 2 қосу амалы болды.

n=3 болсын:

y= a0x3+a1x2+a2x+a3 – 9 амал бар

y= ((a0x+a1)x+a2)x+a3 – 6 амал бар. Сонда бұл әдіс алгоритмі 2 операциядан тұрады:



  1. x-ке көбейту

  2. келесі коэффициентті қосу



алг Горнер (бүт n, нақ x, y, нақ таб a[0, n])

арг n, x, a

нет y

басы бүт i

i:=0


y:=a[0] (немесе y:=a[i])

әзір i

қ. б.

i:=i+1


y:=y*x+a[i]

қ. с.

бітті

соңы
Өзін тексеру сұрақтары


  1. векторлар деп нені ұғасыз?

  2. массивтердің неше түрі бар?

  3. жиындар қалайша жазылады?

  4. жазулар қалайша қолданылады?

Ұсынылатын әдебиеттер

  1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.

  2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.

  3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.

  4. Острейковский В.А. Информатика, Москва, 2000 г.

  5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.




Достарыңызбен бөлісу:
1   ...   18   19   20   21   22   23   24   25   ...   41




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет