-->
Главная » Статьи » Информатика

ҚҰРЫЛЫМНЫҢ КӨРСЕТКІШТЕРІ

ҚҰРЫЛЫМНЫҢ КӨРСЕТКІШТЕРІ

 

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

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

int getword (char*, int);

struct key * binsearch (char*, struct key *, int);

   \\ Си-де кілттік сөздерді есептеу

main ( )

{  char word [MAXWORD];

   struct key *p;

   while (getword (word, MAXWORD)!=EOF)

   if (isalpha(word[0]))

if ((p=binsearch(word, keytab, NKEYS))!=NULL)

             p->count++;

   for (p=keytab; p<keytab+NKEYS; p++)

   if (p->count > 0)

   printf ("%4d%s\n”,p->count, p->word);

   return 0;

}

// binsearch: tab[0]…tab[n-1-тағы сөзді табу]

   struct key * binsearch (char *word, struct key *tab, int n)

{  int cond;

   struct key *low=&tab[0];

   struct key * high = &tab[n];

   struct key *mid;

   while (low<high);

   {        mid=low+(high – low)/2;

             if ((cond=strcmp (word,mid->word))<0)

                                high=mid;

             else if (cond > 0)

                                low=mid+1;

             else

                                return mid;

   }

   return NULL;

}

Егер binsearch функциясы кілттік сөзді тапсаонда ол көрсеткішті оған бередікері жағдайда ол NULL-ді қайтарады. keytabмассивінің элементіне қатысу көрсеткіш арқылы жүзеге асады. low және high үшін инициализаторлар ретінде басына жәнемассивтің соңынан кейінгі орынға көрсету қызмет атқарады. mid = (low +high)/2 формуласы арқылы орташа элементтіесептеуге болмайдыөйткені көрсеткіштерді қосуға болмайдыБірақта оларға алу амалын қолдануға болады, high-lowэлементтер саны болғандықтан,

             mid = low + ( high – low )/2

меншіктеуді low және high-тің ортасында жатқан mid-тің элементінің көрсеткішін орнатады.

for циклінде p++ операторы р-ны массивтің келесі құрылымдық элементіне өсіредіҚұрылым өлшемі оның мүшелерініңөлшемдерінің қосындысына тең болады деп ұйғаруға болмайды. Sizeof операторы дұрыс мәнді қайтарады. Getwordфункциясы кіру ағынының келесін сөзін немесе литерін қабылдайдыСөз ретінде әріптен немесе жеке бос орынсызлитерлерден басталатын цифр - әріптер шынжыры деген түсінік алынадыФайлдың соңы бойынша функция EOF-ты бередіалқалған жағдайларда сөздің бірінші литерінің коды немесе жеке литер кодыегер ол әріп болмасаоның мәні болып табылады.

   \\ getword: келесі сөзді немесе литерді қабылдайды

   int getword (char * word, int lim)

   {        int c, getch (void);

             void ungetch (int);

             char * w =word;

             while (isspace (c=getch( ))

                                ;

             if (c!=EOF) *w++=c;

             if (!isalpha(c))

             {        *w=’\0’;

                      return c;

             }

             for (; --lim >0; w++)

             if (!isalnum (*w=getch( )))

             {        ungetch (*w);

                      break;

             }

             *w=’\0’;

return word [0];

   }

ungetch-ті пайдалану кіру ағынындағы артық литерді қайтаруға мүмкіндік береді. getword-та бос орынды литерді жіберуүшін  - isspace, әріпті идентификациялау (ұқсастыруүшін - isalpha және әріп цифрдың бейнесін тану үшін isalnumқолданыладыОлардың барлығы <ctype.h> стандартты бас файлда сипатталады. getch және ungetch функциялары қалайжұмыс істейдіКөп жағдайдапрограмма артықтарын оқып болғанша қажеттілердің барлығын оқыды маәлде жоқ па соны"түсінбейді”. Бұдан программа керектісіне қарағандабір литерге артық оқығанынәсіресе санаққа кірмейтін литердіоқығанын білдіредіСодықтан артық литерді қайтаратын операция қажетКерісінше литерді жіберу механизмі енгізу кезіндеgetch кезекті литерді қоятынал кіру ағынынан ungetch литерді кері жіберетінбір-бірімен келісілетін функциялар жұбыныңкөмегімен оңай моделденеді.

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

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

Ағашта әр жеке сөзге "түйін” қарастырылған, ол:

 сөздің мәтініне көрсеткіш:

сөздің мәтініне көрсеткіш;

кездесетіндердің санын есептеу;

сол жақ балалық түйінге көрсеткіш;

оң жақ балалық түйінге көрсеткіш;

Әр түйіннің бір немесе екі баласы бар, немесе түйінің типті баласы жоқ. Мұрагері жоқ түйінді жапырақ деп атайды.

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

Бинарлы ағаштың түйінін сипаттауды төрт компонентті құрылым түрінде көрсетейік:

struct tnode    //ағаш түйіні

{  char *word; //мәтінге көрсеткіш

   int count;              //кіру саны

   struct tnode*left;   //сол жақ бала

struct tnode*right;    // оң жақ бала

};

 

Құрылым өз-өзін қоса алмайды, бірақ

struct tnode*left;

tnode түйініне left-ті көрсеткіш ретінде, анықтайды, ал tnode өзі анықтамайды.

Кейде өзара жіберілетін құрылымдар қажеттілігі туындайды: бір-біріне жіберілетін екі құрылымдар. Осындай мәселені шеше алатын тәсіл келесі фрагментті ұйымдастырады:

struct t

{  …

   struct s *p;  // p s-ті көрсетеді

};

struct s

{  …

   struct t *q;  // q t-ны көрсетеді

};

Біздің есебіміздің басты программасы getword функциясының көмегімен сөзді оқиды және оларды addtree функциясы арқылы ағашқа қояды.

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

struct tnode * addtree (struct tnode *, char *);

void treeprint (struct tnode *);

int getword ( char * , int );

   // кездесетін сөздің жиілігін есептеу

main ()

{  struct tnode * root;                  // түпкі түйінге көрсеткіш

   char word [MAXWORD];

root = NULL;

while ( getword(word, MAXWORD)!=EOF)

if ( isalpha (word[0]))

   root = addtree(root,word);

treeprint(root);

return 0 ;

}

addtree функциясы рекурсивті. Әр қайтадан түскен сөздер үшін оның көшірмесі ізделінеді және саны 1-ге артады, немесе ол үшін жаңа түйін енгізіледі, егер мұндай сөз ағашта болмаған жағдайда жаңа түйіннің құрылуы, түйіннің ата-анасына қойылатындай, оған көрсеткішті addtree қайтарумен қосақтала жүреді.

struct tnode * talloc ( void);

char * strdup ( char *);

// addtree: w сөзімен p-ға немесе одан төменге түйін қосылады

struct tnode * addtree ( struct tnode *p, char * w)

{  int cond;

if ( p= = NULL)                 //сөз бірінші рет кездесіп тұр

   { p=talloc();                       // жаңа түйін құрылады

   p→word = strdup (w);

   p→count =1;

   p→left = p→ right = NULL;

              }

else if (( cond = strcmp( w,p→word))= = 0)

             p→count + + ;                  // бұл сөз кездескен

   else if ( cond<0)                             // түбір < сол жақ ағаштың

     p→left=addtree( p→left,w);

   else

      p→right=addtree( p→right,w);

   return p;

}

Категория: Информатика | Добавил: admin_ (17.11.2013)
Просмотров: 1015 | Теги: ҚҰРЫЛЫМНЫҢ КӨРСЕТКІШТЕРІ с++ қазақш | Рейтинг: 0.0/0
Всего комментариев: 0

Имя *:
Email:
Код *: