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

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

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

# include <stdlib.h>

// talloc : tnode-ті құрайды

struct tnode * talloc ( void)

{  return ( struct tnode * ) malloc ( sizeof (struct tnode));

}

   // strdup: аргументте көрсетілген стрингті

//malloc көмегімен алынған орынға көшіреді.

char * strdup ( char*s)

{  char *p;

   p=(char*) malloc ( strlen (s) + 1);              // +1  -  ‘\0’ үшін

   if (p!=NULL)                                                // егер жады бөлінсе

     strcpy (p,s);

   return p;

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

// treeprintp ағашын ретімен басып шығару

void treeprint (struct tnode * p)

{  if (p!=NULL)                               //ағашты ең болмағанда бір түйін бар

   {   treeprint ( p→left);

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

             treeprint (p→right);

   }

}

 

Құрылымдарды қолдануда жаңа аспектрлердің мысалын келтіру элементтерді кестеге қою мен оларды кестелерден іздеуді жүзеге асыратын, программаның ядро пакетіне әкелеміз. Бұл пакет – кез-келген макропроцессорда немесе компиляторда кесте аттарымен жұмыс істейтін әдеттегі программа жиынтығы. Мысалы, #define нұсқауын қарастырайық.

#define IN 1 түрінде жол кездескенде, оның 1 мәтінінің орнын басатын және IN  аты кестеде сақталынуы керек. Егер одан кейін бұл IN аты нұсқауда кездессе, мысалы, state=IN-де, ол бірге ауыстырылуы тиіс.

Аттармен манипуляциалайтын және мәтіндерімен орын ауыстыратын екі программа бар. Бұл – s атын жазатын install (s,t) және оның t мәтінінің орнын кестеге (s және t – стрингтер) ауыстыратын және кестеде s іздеуін жүзеге асыратын lookup(s) және s аты табылатын көрсеткішті қайтарушы орын, немесе NULL – егер s кестеде болмаған жағдайда.

Алгоритм «хэширлеу»-ге (функцияларды орналастыру) негізделеген: түскен атар көрсеткіштер массивінің индексі ретінде кейін қолданылатын теріс емес санға (хэш-код) жинақталады. Осы массивтің әр элементі хэш-кодтың мәліметтерінің атынсипаттайтын блок тізімдерінің бастапқы сілтемелерімен байланысқан көрсеткіштері болып табылады. Егер массив элементіNULL-ден тұрса, яғни бұл хэш-кодымен аттардың арасында бірде-біреуі сәйкес келмегендігін білдіреді.

Тізімнің блогы – бұл аттың көрсеткіштерінен мәтіндер орнын ауыстырудан және тізімдегі келесі блоктан тұратын құрылым; NULL мәні көрсеткіште келесі блок тізімінің соңы екенін білдіреді.  

struct nlist                                                       \\ кесте элементі

             {        struct nlist * next;  \\ келесі тізім блогының көрсеткіші

                      char * name;                   \\ анықталған ат

                      char * defn;          \\ мәтіннің орнын басады

             };

Ал көрсеткіштер массивін анықтау былайша жазылады:

             #define HASHSIZE 101

             static struct nlist *hashtab[HASHSIZE];      \\ көрсеткіштер кестесі

             \\ hash: s стрингісі бойынша хэш-код алынады.

              unsigned hash (char * s)

             {        unsigned hashval;

                      for (hashval=0; *s!=’\0’; s++)

                      hashval = *s+31*hashval;

                      return hashval %HASHSIZE;

             }

                      \\ lookup: s-дан элементті іздеу

             struct nlist * lookup (char * s)

             {        struct nlist *np;

                      for (np = hashtab [hash(s)]; np!=NULL; np=np->next)

                      if (strcmp (s,np->name)= =0)

                      return np;              \\ қойылған стрингті тапты

                      return NULL;                 \\ таппады

             }

install функциясы қойылған стрингтің бар екенін анықтау үшін lookup-қа қатынас жасайдыЕгер бұл осылай болсаондаескі анықтама жаңамен ауыстырыладыкері жағдайда жаңа элемент құрылады.

             struct nlist * lookup (char *);

             char * strdup (char *);

             \\ install: (name, defn) кестеге кіргізу

             struct nlist * install ( char * name, char * defn)

             {        struct nlist * np;

                      unsigned hashval;

                      if (( np=(lookup (name))= =NULL)           \\ табылмады

                      {        np =(struct nlist*) malloc(sizeof(*np));

                                if (np = =NULL      (np -> name =strdup(name))= =NULL)

                                return NULL;

                                hashval = hash (name);

                                np -> next = hashtab [hashval];

                                hashtab [hashval] = np;

                      }

                      else                                          \\ бар

                      free ((void *) np-> defn);                \\ бұрынғы defn-ті босатамыз

                      if (( np -> defn = strdup (defn)) = =NULL)

                      return NULL;

                      return np;

             }

 

Категория: Информатика | Добавил: admin_ (17.11.2013)
Просмотров: 805 | Рейтинг: 0.0/0
Всего комментариев: 0

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