Динамикалық тізімдермен жұмыс

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 11 бет
Таңдаулыға:

Аннотация

Курстық жұмыс С++ бағдарламалау тілінде орындалды.

Бұл курстық жұмыс «Динамикалық тізімдермен жұмыс» тақырыбында жасалды. Курстық жұмыстың мақсаты - динамикалық тізімдерді қолданып, С++ тілінде бағдарламалар құруды жетік меңгеру.

Курстық жұмыс 3 бөлімнен тұрады:Олар С++ бағдарламалау тілі, Бағдарламаны жобалау және құжаттау. Сонымен қатар, қорытынды мен қолданылған әдебиеттер және қосымша қарастырылған.

Мазмұны

Кіріспе . . . 5

1 С++ бағдарламалау тілі . . . 6

1. 1 Динамикалық құрылымдар. 8

1. 2 Тізімдермен жұмыс . . .

2 Бағдарламаны жобалау . . . 20

2. 1 Есептің шешілу әдісі . . . 20

2. 2 Бағдарламаның алгоритмі . . . 20

3 Құжаттау. 21

3. 1 Қолданушыға нұсқау. 21

3. 2 Бағдарламалаушыға нұсқау. . 21

Қорытынды . . . 22

Қолданылған әдебиеттер . . . 23

Қосымша . . . 24

Кіріспе

Бұл курстық жұмыс «Бағдарламалау технологиясы» пәні бойынша орындалған және С++ тілінде динамикалық тізімдерді қолдануға негізделген. Бағдарламаны орындау үшін осы тілде динамикалық тізімдер қолданылады. Олар С++ тілінде деректер қорын құруға мүмкіндік береді.

Курстық жұмыстың тақырыбы «Динамикалық тізімдермен жұмыс». Жұмыстың жалпы мақсаты студенттерді С++ тілінде бағдарламалар құру әдісіне үйрету және осы тілді тереңдей оқып меңгеру. Жұмыс үш бөлімнен және қорытынды мен қосымшалардан тұрады. Бірінші бөлімінде С++ тілі туралы және динамикалық құрылым, оның ішінде тізімдерге түсініктеме берілген, яғни оның мүмкіндіктері көрсетілген. Екінші бөлімде есептің шешілу әдісі көрсетілген, яғни бағдарламаның жұмысына қажетті модульдер, функциялар және т. б. Мұнда бағдарламаның алгоритмі көрсетілген. Үшінші бөлімде құжаттау, яғни бағдарламалаушыға нұсқау көрсетілген. Жұмыстың қосымша бөлімінде бағдарламаның листингі және бағдарламаның нәтижесі көрсетілген.

1 С++ бағдарламалау тілі

Қазіргі кезде кеңінен қолданылатын программалау жүйесінің бірі - С++. Американың Borland корпорациясының қызметкері Андерсон Хайлсбергтің жетекшілігімен құрастырылған. С++-тың түп нұсқасы Швейцария ғалымы Никлаус Вирт жасаған Паскаль программалау тілінен тарайды. Бастапқыда Паскаль тілі программалауды алғаш үйренушілер үшін өте тиімді құрал болып табылған. Қарапайым Паскальды өңдеудегі А. Хайлсбергтің үлкен еңбегінің нәтижесінде С++ қазіргі заман талабына сай, қуатты программалау жүйесіне айналды. С++ - жоғарғы деңгейлі программалау жүйесі. Оның логикалық құрылымы әр түрлі есептерді дәл шешуге көмегін тигізеді. Сондықтан, оқушылар мен студенттерге программалаудың негізін С++ тілін оқытып үйретуден бастап, программалаудың қыр-сырын меңгертудің маңызы зор.

1972 жылы AT&T атаулы Американың корпорациясы жаңа C (Си) программалау тілін дайындап шыкты. Ол - құрылымдық және алгоритмдерді басшылықка алып дайындалған процедуралық жоғары деңгейлі тіл.

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

Си тілі бірте-бірте дамытылып, қазіргі кезде пайдаланылып келе жаткан, 1983 жылы дүние жүзі елдері басшылықка алған ANSI C нұсқасы да жарыққа шықты (ANSI - стандарттардың Америкалық ұлттық институты) . ANSI C тілінің түрлі нұсқаларына енгізілген стандартты кітапханалар да бар. Тілдің кемшілігі де жоқ емес, ол жүйелік және қолданбалы программаларды дайындауға бейім, бірақ айнымалыларға рұқсат етілмеген қол жеткізу механизмін қамтамасыз етпейді және құрьшатын класты баска кластың ішкі класы (мұрагер) ретінде жариялау мүмкін емес. Мұндай объектілі - бағдарлы программалау (ОБП) тілдеріне енетін ерекшеліктерді ескеріп, Borland International Inc фирмасы C тілінің дамытылған жаңа Turbo C (Турбо Си) нұскасын 1980 жылдардың басында жарықка шығарды. Кейіннең Turbo C++ 2. 0, Turbo C++ 3. 0 және олардың кеңейтілген Borland C++ нұсқалары да пайда болды: Borland C++ 2. 0, Borland C++ 3. 0, Borland C++ 3. 1, Borland C++ 4. 0 және т. б.

Олардың MS DOS, Windows операциялық жүйелерінде жұмыс істеу мүмкіндіктері жеткілікті.

C++ тілі де процедуралық тіл, бірақ онда ОБП тілінің ерекшеліктері кең түрде қарастырылған. ОБП тілінде қолданылатын негізгі ұйымдар: класс, объект, оқиға, қасиеттер мен әдістер. Бұл ұғымдар:

объект - құрылымы класс типі арқылы сипатталатын айнымалы;

оқиға - объект жағдайының өзгеруі; қасиеттер - объект сипаттамалары (параметрлері) ; әдіс - класс элементтерін іздейтін команда не процедура, функция.

класс - пайдаланушы анықтайтын тип. Тип қасиеттер мен әдістерді бірге қосып сипаттайды. Программада осы кластың жеке даналары дайындалады. ОБП-да класс үшін мұрагерлік, инкапсуляция және полиморфизм принциптері енгізілген. Мұрагерлік - программада негізгі класс типінің туынды иерархиялық класта сақталуы, т. б.

Тілде жадпен жұмыс істеуге арналған арнайы конструктор, деструктор функциялары да бар. Конструктор класс типті айнымалы үшін жадтан арнайы орын бөледі, деструктор бөлінген жадты тазалайды.

Мысал үшін фигуралық объектілерді қарастырайық. Мұндағы класс - геометриялық фигуралар типі. Класс жазық және кеңістіктегі у фигуралар болып екі ішкі класқа бөлінеді (C тілінде оларды мұрагер типтер деп атайды) . Жазық фигуралар класы төбелері бар (мысалы, үшбұрыш, төртбұрыш) және төбелерсіз (мысалы, шеңбер, эллипс) болып екі ішкі класка бөлінеді (олар иерархиялық мұрагер типтер) .

1. 2 Динамикалық құрылымдар

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

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

Деректерді байланысты көрсетудің артықшылығы - құрылымның едәуір өзгеруін қамтамасыз ету мүмкіндігі;

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

Сонымен бірге, байланысты көрсетудің кемшіліктері де жоқ емес:

Байланыс өрістеріне қосымша жады шығындалады;
Байланысқан құрылым элементтеріне қатынас уақыт бойынша тиімсіздеу болуы мүмкін.

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

1. 3 Тізімдермен жұмыс

Динамикалық құрылымдардан бағдарламада сызықтық тізімдер жиі қолданылады.

Кез келген деректердің динамикалық құрылымы ең болмағанда екі өрістен тұратын, құрылымды ( struct) құрайды. Олар деректерді сақтауға және көрсеткішке арналған өрістер. Деректер өрісі және көрсеткіштер бірнеше болуы мүмкін. Деректер өрісі кез келген типте болуы мүмкін: негізгі, құрамды және көрсеткіш типті. Қарапайым элементті сипаттау төмендегідей болады:

struct Node{

Data d; // Data деректер типі алдын анықталуы тиіс Node *р:

}:

Элементтер жиынын байланыстырудың ең қарапайым тәсілі - әрбір элементте келесісіне сілтеме болу. Мұндай тізім бірбағытты (бірбайланысты) деп аталады. Егер әрбір элементке екінші сілтемені алдыңғы элементке қоссақ, екібағытты тізім алынады. Егер соңғы элементті біріншісімен көрсеткішпен байланыстырсақ, дөңгелек тізім алынады.

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

Тізімдерге келесі амалдарды орындауға болады :

тізімді бастапқы қалыптастыру (алғашқы элементті құру) ;
тізімнің соңына элементті қосу;
берілген кілтімен элементті оқу;
тізімнің берілген орнына элементті қою (берілген кілтімен элемент алдына не соңына) ;
берілген кілтімен элементті жою;
кілт бойынша тізімді реттеу.

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

struct Node{

int d;

Node *next;

Node *prev;

}:

Төменде 5 саннан тұратын тізім құрып, тізімге санды қосып және жойып, тізімді экранға шығаратын, бағдарлама келтірілген. Тізімнің басындағы көрсеткіш pbeg, тізімнің соңында - pend, көмекші көрсеткіштер - pv және pkey деп белгіленген.

#include <iostream. h>

struct Node{

int d;

Node *next;

Node *prev;

}:

Node * first(int d) ;

void add(Node **pend, int d) ;

Node * find(Node * const pbeg, int i) ;

bool remove(Node **pbeg, Node **pend, int key) ;

Node * insert(Node * const pbeg, Node **pend, int key, int d) ;

int main() {

Node *pbeg = first(l) ; // Тізімнің бірінші элементін қалыптастыру
Node *pend = pbeg; // Тізім басталмай жатып аяқталады

for (int i - 2; i<6; i++)

add(Spend, i) ; //Тізімнің соңына төрт элемент қосу- 2, 3, 4, 5

insert(pbeg, Spend, 2, 200) ;

if(!remove (&pbeg, Spend, 5) ) cout << "табылмады";

Node *pv = pbeg; // 5 элементті жою

while (pv) { // тізімді экранға шығару

cout <<pv->d << ' ';

pv = pv->next;

}

return 0;

}

// Алғашқы элементті қалыптастыру Node * first(int d)

{ Node *pv = new Node;

pv->d = d; pv->next = 0;

pv->prev = 0;

return pv;

}

// Тізімнің соңына қосу

void add(Node **pend, int d) {

Node *pv = new Node;

pv->d = d;

pv->next = 0;

pv->prev = *pend;

(*pend) ->next = pv;

*pend = pv; }

// Кілт бойынша элементті іздеу

Node * find(Node * const pbeg, int d)

{ Node *pv = pbeg; while (pv) {

if(pv->d == d) break; pv = pv->next;

}

return pv;

}

// Элементті жою

bool remove(Node **pbeg, Node **pend, int key)

{ if(Node *pkey = find(*pbeg, key) ) {

if (pkey == *pbeg) {

*pbeg = (*pbeg) ->next;

(*pbeg) ->prev = 0; }

else if (pkey == *pend)

{ *pend = (*pend) ->prev;

(*pend) ->next = 0; }

else{

(pkey->prev) ->next = pkey->next;

(pkey->next) ->prev = pkey->prev; }

delete pkey;

return true;

}

return false;

}

// Элементті қою

Node * insert(Node * const pbeg, Node **pend, int key, int d) {

if(Node *pkey = find(pbeg, key) )

{ Node *pv = new Node;

pv->d = d;

pv->next = pkey->next;

pv->prev = pkey;

pkey->next = pv;

if( pkey != *pend) (pv->next) ->prev = pv;

else *pend = pv;

return pv;

}

return 0; }

Бағдарлама жұмысының нәтижесі: 1 2 200 3 4

Функцияның ішінде өзгертілмейтін барлық параметрлер const модификаторымен берілуі қажет. Өзгертілуі мүмкін көрсеткіштер (мысалы, тізімнен соңғы элементі жою кезінде тізімнің соңында көрсеткішті түзету қажет болады) адрес бойынша беріледі.

Тізімнен элементті жою функциясы remove. Оның параметрлері тізімнің басына және соңына көрсеткіштер, жойылуға жататын элементтің кілті. 1 қатарда pkey жергілікті көрсеткішімен жады бөлінеді, оған find кілті бойынша элементті табу функциясының нәтижесі меншіктеледі. Бұл функция іздеу сәтті болғанда элементке көрсеткішті, тізімде мұндай кілтпен элемент жоқ болса, 0 қайтарады. Егер pkey нөлдік емес мән алса, if операторындағы шарт ақиқат болады да, басқару 2 операторға беріледі, егер элемент жоқ болса, функциядан false мәнімен қайтару орындалады (оператор 6) .

Тізімнен жою элементтің тізімнің басында, ортасында немесе соңында орналасқанына байланысты әр түрлі жүргізіледі. 2 операторда жойылатын элемент тізімнің басында тұр ма деп тексеріледі - бұл жағдайда pbeg көрсеткішін бірінші элементтің next өрісінде тұрған адрестегі тізімнің келесі элементіне көрсететін, тізімнің басына түзету керек. Тізімнің жаңа бастапқы элементі өзінің көрсеткіш өрісінде алдыңғы элементке 0 мәнінде болуы керек.

Егер жойылатын элемент тізімнің соңында болса (оператор 3), тізімнің соңындағы pend көрсеткішін алғашқы элементке ығыстыру керек, адресін соңғы элементтің prev өрісінен алуға болады. Сонымен бірге, жаңа соңғы элемент үшін келесі элементке көрсеткішті нөлдеу қажет.

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

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

2 БАҒДАРЛАМАНЫ ЖОБАЛАУ

С++ тілінде динамикалық тізімдермен жұмысты жүзеге асыру үшін С++ тілінің динамикалық құрылымдары қолданылады. Бағдарламаның нәтижесінде деректер қорын құру мүмкіндігіне ие боламыз.

2. 1 Есептің шешілу әдісі

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.