22937

СТРУКТУРИ

Лекция

Информатика, кибернетика и программирование

struct ім’я_типу { cписок_полів} список_змінних ; struct date { int day; int month; int year; char mon_name[4]; } d d1; змінніструктури dd1 типу date typedef struct { double real; double imag; } complex;...

Русский

2013-08-04

74 KB

0 чел.

ТЕМА: СТРУКТУРИ

Сем. Стуктури або записи – це  вектори фіксованої довжини з компонентами  певних фіксованих типів.    

Син.  struct  ім’я_типу { cписок_полів} список_змінних ;

         struct date {

                               int day;

                               int month;

                               int year;

                               char mon_name[4];

                            } d, d1;                                                                  /*   змінні-структури d,d1 типу date */                             

        typedef struct { double real;

                                  double imag;

                                }  complex;                                                      /*   визначення типу complex  */

       struct date d2={1, 3, 2006, “Mar”};                                     /*   ініціалізація структур  */

       struct date d3[365];  /*  МАСИВ структур  - таблиця */

       

        complex  x,y,z;                                                      

        struct date *pd;    /*   змінна pd - вказівник на структуру  */

      

Операція “->” :   pd -> year означає  (*pd).year 

 

int p[5],q[5];

       int leap;     

Доступ до полів структур забезпечують СКЛАДЕНІ ЗМІННІ вигляду:

ім’я_змінної_структури . ім’я_поля

Складені змінні мають тип полів і можуть використовуватись у  всіх контекстах, допустимих для звичайних змінних даного типу.

Нпр.       x.real=0.0;

              x.imag =0.0;

              d=d2;  /*   структури на відміну від масивів можна КОПІЮВАТИ !!!     ЗАБОРОНЕНО: p=q !!!*/                             

              d3[0]= {0,0,0,””};

              d3[0].day=1;

 Прикл.  Підрахунок входжень службових слів

struct key {char *keyword; int keycount;} keytab []= {(“break”, 0),

                                                                 (“case”, 0),

                                                                 (“char”, 0),

                                                                   ……….

                                                                           (“unsigned”, 0),

                                                                    (“while”, 0)

                                                    };

# define MAXWORD 20

# define NKEYS (sizeof(keytab)/sizeof(struct key);

  main()

   { int n,t;

     char word[MAXWORD];

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

         if(t==LETTER)

           if((n=binary(word,keytab,NKEYS))>=0)

              keytab[n].keycount++;

         for(n=0; n<NKEYS; n++)

if(keytab[n].keycount>0) printf(“%4d%s\n”,keytab[n].keycount, keytab[n].keyword);

  }

/* бінарний пошук в таблиці */

  binary (char *word, struct keytab[], int m)

   { int low, high, mid, cond;

     low=0; high=m-1;

      while(low<=high){

        mid=(low+high)/2;

      if((cond=strcmp(word, tab[mid].keyword))<0)

       high=mid-1;

      else if (cond>0) low=mid+1;

       else return (mid);

   }

    return (-1);

}

# define LETTER ‘a’

# define DIGIT     ‘0’

/* getword -  читання з клавіатури getword в w чергового ідентифікатора */

getword(char *w, int lim)

{ int c,t;

 if(type(c=*w++=getch())!=LETTER){

   *w=’\0’; return(c); }

while(--lim>0){

  t=type(c=*w++=getch());

  if(t!=LETTER && t!=DIGIT) {ungetch(c); break;}

    }

  *(w-1)=’\0’;

return(LETTER);

}

type(c)

int c;

{ if(isalpha(c)) return(LETTER);

   else if(isdigit(c)) return(DIGIT);

   else return(c);

}  

  ЛІНІЙНІ СПИСКИ

Лінійні однонаправлені списки – послідовності однотипних компонент з доступом до першої компоненти(=голови списки) та до наступної компоненти по відношенню до даної. 

 

Прикл. Поліноми у вигляді списку.

struct  el_pln {

                       int             st;

                       int             koef;

                       el_plm    *next;

                    };

/* функція create - створення поліному, к -  кількість одночленів */

struct  el_plm *create_plm(int k)   /*створення поліному, к -  кількість одночленів */

  {       struct el_plm *beg, *head,*end ,*new_;

           int i;

           head=end=NULL;

           for(i=1; i<=k; i++)

               {/*створення чергового елементу списку*/

                   new_=(struct el_plm*)malloc(sizeof(struct el_plm));

                   scanf(“%d%d”,&new_->koef,&new->st);

              /*приєднання нового елементу до списку*/

                   if(beg==NULL) beg=new_;

                                 else end_next=new_;

                   end=new_;

                  end->next=NULL;

              }

 

           return beg;

  }

/*друкування списку-поліному */

void print_plm (struct el_plm *head)                                            

  {       printf(“\n”);

           while (head != NULL)

               { printf (“%dX**%d%c,  head->koef, head->st, (head->next!=NULL) ? ’+’:’ \n’ )

                  head=head->next;

                  

                }

  }

/*довжина списку -поліному*/

int length_plm (struct el_plm *head)                                            

  {       int k=0;

           while (head != NULL)

               { k++;

                 head=head->next;

               }

           return k;

  }

/*створення  одночлена cX**k  для списку-поліному   */

struct  el_plm *create_elplm(int c, int k, struct  el_plm *next1)   

  {       struct el_plm *new_;

           if ((new_=(struct el_plm*)malloc(sizeof(struct el_plm))== NULL) printf (“\n Немає памяті ”);          

              else {            

                   new_ ->koef=c;

                   new_ ->st=k;

                   new_ ->next=next1;

                      }

                  return new_;

  }

/*Втавка одночлена cX**k на n-е  місце в список-поліном  з головою head.  Функція повертає голову нового списку */

struct  el_plm *insert(struct el_plm *head, int n, int c, int k)   

  {       struct el_plm *p, *new_;

           

         if (n==0) { new_= create_elplm( c, k, head); head=new_;}

         if (n> length_plm (head) { p=head; while (p!=NULL) p=p->next; ;                /*пошук останнього (=p)елементу списку*/

                                                      new_= create_elplm( c, k, NULL);  

                                                      p->next=new_;

                                                  }

                     else  { for (i=1, p=head; i<k; i++)  p=p->next;                /*пошук (k-1)-ого (=p) елементу списку*/

                                 new_= create_elplm( c, k, p->next);  

                                  p->next=new_;

                               }

             return head;

  }

  СТЕКИ

Тип стек складають послідовності однотипних компонент з доступом до останньої компоненти (=вершини стека) та функціями:   pop() - читання та усуненням останньої компоненти, push(c) додавання в кінець стеку нової компоненти,  empty() - перевірка стека на порожнечу .

Cтек подається  у вигляді лінійного списку . В голові списку розташовується  вершина стека, за нею - передостанній елемент и т.д.

Прикл.  Стек цілих чисел

struct  el_stack {

                              int                  el;

                             el_stack   *next;

                    } *p;                                                /*pвказівник на  вершину стека*/

УВАГА :    p==NULL означає порожній стек  !!!!!

/* функція empty - перевірка стека на порожнечу */

int empty ()

{return p==NULL;}

int empty ()

{return p;}

/* функція pop знімає елемент з вершини стека */

int  pop ()

{ struct  el_stack *pp; int a;

 if (!empty ()) { pp=p; a= p->el;  p=p->next; free(pp); return a;}

}

void push(int c)

{ struct  el_stack *new_;

 if ((new_=(struct el_stack*)malloc(sizeof(struct el_stack))== NULL) printf (“\n Немає памяті ”);          

        else {            

                   new_ ->el=c;

                   new_ ->next=p;

                   p=new_;

                }

}

ХЕШ-ТАБЛИЦІ

Таблиці – це послідовності рядків певної фіксованої структури.  Ці послідовності можна зберігати та обробляти в ОП у вигляді лінійного  списку. Для підвищення ефективності обробки таких таблиць їх організовують у вигляді хеш-таблиць. Ідея хешування полягає в факторизації рядків на класи еквівалентності за певною ознакою. Для цього вибирається певне  фіксоване поле (= ключ рядка) і на його значеннях визначається функція (хеш-функція ) з натуральними значеннями. Рядки еквівалентні, якщо значення хеш-функції на них співпадають. Рядки у хеш-таблиця зберігаються не в одному лінійному списку,  а  в окремих списках – по одному для кожного класу еквівалентності. Голови цих списків зберігаються в спеціальному масиві. Значення хеш-функції для даного рядка задає індекс  компоненти масива, що задає голову списку  для даного рядка.     Для роботи з таблицею необхідні три функції: хеш-функцію, функцію пошуку рядка та функція для занесення нового рядка в таблицю або модифікації вже існуючого.

ПРИКЛАД.  Обробка таблиці з рядками, що містять  два поля: назву рядка та певну текстову інформацію.

…….

ОБЄДНАННЯ (СУМІШІ)

Сем.  Змінні типу об’єднання можуть приймати значення кількох різних, (але фіксованих !) типів. Їх можна трактувати як структури, всі поля яких розміщуються не в окремих, а в одній загальній ділянці пам’яті. Тим самим забезпечується можливість доступу  до однієї і  тієї ж ділянки за допомогою змінних різного типу. Визначаючи, нпр.,  на ділянці байтовий  массив, можна працювати з кожним окремим байтом ділянки, де зберігається те чи інше дане.

Синт.  union  { T1  v1;  

                         T2  v2;

                         …

                         Tn  vn;

                       }  x,y,… ;     /* змінні типу суміш з полями v1,v2,…,  vn */

Прикл.   /* друкування ASCII-  та  SCAN-кодів символів, що вводяться з клавіатури */

void main()

{ union { char hh[2];

               int   ii;

            } cc;

 unsigned char scn, asc;

 do /* цикл до Cntr+ Z */

      { printf (“\n”);

         cc.ii = bioskey(0);

         asc= cc.h[0];

         scn= cc.h[1];

         printf (“%4d  ||  %4d”, scn, asc );   

      }

while (asc!=26 ||  scn != 44)

}

БІТОВІ ПОЛЯ

З метою економії пам’яті може виникнути необхідність запакувати декілька об’єктів в одне машинне слово (типу int), наприклад группу однобітових прапорців. Інша ситуація – виникає  необхідність адресуватись не до всього слова, а до певної його частини. Таку можливість надає тип – бітові поля.  Як і  об’єднання, бітові поля  - синтаксично визначаються у вигляді спеціальних структур:

   struct  { T1  v1 : k1;  

                T2  v2 : k2;  

                     …

                 Tn  v1 : kn;  

                       }  x,y,… ;     /* змінні типу бітових полів v1,v2,…,  vn ,

                                                         T1 , T2 ,  … Tnцілий або безнаковий цілий типи */

Нпр., 1) визначення трьох прапорців  

                       struct  { unsigned int less : 1;  

                                     unsigned int eq : 1;  

                                      unsigned int gr : 1;    

                                   }  x,y,… ;     /*  x.less,  x.eq, x. gr  -  змінні прапорці  */

x.less=0;  x.eq=1;  

                                                         

          2) упаковка десяткових цифр

                     struct  { unsigned int l : 4;  

                                  unsigned int r : 4;  

                                } d,… ;     

/*  d.l,  d. r  -  змінні двійково-десяткові цифри  */

Запис в змінну d  десяткового числа 62:    d.l = 6; d.r = 2;


 

А также другие работы, которые могут Вас заинтересовать

82137. Підведення підсумків осінніх спостережень, з’ясування змін, що відбуваються в живій та неживій природі, прихід Зими 412 KB
  Мета. Дати поняття про зміни, які відбуваються в природі восени та на початку зими; розширити знання учнів про характерні ознаки зими серед рослин, тварин; розвивати спостережливість, творчу уяву, мислення; виховувати дбайливе ставлення до природи, любов до прекрасного.
82138. Історична сторінка 299.5 KB
  Скільки часу потрібно П’ятачку Вінні Пуха під дубом чекати Щоб Вінні Пух 49 метрів зміг здолати І дупла дуба яке міститься на цій висоті дістатися Та справжні чи ні бджоли які в ньому проживають дізнатися. Скільки стовпчиків потрібно Джері підготувати Щоб зводячи паркан всі ями використати.
82139. НАШІ ДРУЗІ – ДИТЯЧІ ЖУРНАЛИ 38.5 KB
  Ознайомити учнів із дитячими журналами розвивати пізнавальні інтереси розширювати читацький кругозір сприяти вихованню доброзичливості товариськості шани до рідного слова. Ми прийшли, малята, щоб вас привітати, Щастя, успіху усім радо побажати! Ви не можете, малята, все про все на світі знати.
82140. Журнали для дітей (Бібліотечний урок для 3-4 класи) 41.5 KB
  Обладнання: Сумка листоноши; виставка З поштової скриньки дитячі газети та журнали; словники папір олівці. Девіз уроку: Читай журнали та газети І подолай усі тенета Дізнаєшся про Всесвіт гарний Труди твої не будуть марні Хід уроку: Бібліотекар: Добрий день діти Сьогодні у нас незвичайний урок.
82141. ВЕЛИКА ВІТЧИЗНЯНА ВІЙНА 177.5 KB
  Учні заздалегідь готують фломастер або олівець і чистий аркуш паперу, розкреслений на декілька пронумерованих прямокутників. У кожному прямокутнику учасники повинні по порядку замалювати асоціативні тлумачення. Можуть бути запропоновані, наприклад, такі слова: відплата, смуток, горе, жах, сльози, печаль...
82142. Шкідливі звички 89.5 KB
  Мета: Дати поняття про погані звички і про їх наслідки розвивати бажання не вживати їх а якщо вони виникли то позбутися; виховувати культуру поведінки старанне ставлення й дбайливе ставлення до свого здоров’я. Життєздатність і здоров’я людей великою мірою залежить від самої людини.
82143. КОРИСНІ ТА ШКІДЛИВІ ЗВИЧКИ 53.5 KB
  Мета: Викликати прагнення у дітей зберігати й зміцнювати здоров’я. Довести до їх відома інформацію, що шкідливі звички є основною причиною порушення здоров’я. Формувати вміння піклуватися про своє здоров’я. Виховувати бажання підтримувати тпрадиції здорового способу життя.
82144. Голосні та приголосні звуки. Зимовий малюнок 140 KB
  Обладнання: Предметні картинки сніжинки різної форми таблиці для читання склади на картинках гірлянди у формі зірочок зошити ручки магнітофон. До дітей спускаєтся сніжинка Логопед: Ось і завітала перша сніжинка використовувати фон для розглядання сніжинки. Роздати дітям сніжинки з позначеннями...
82145. Звуки з, з, позначення їх буквою Зз («зе»). Дзвінке вимовляння цих звуків у кінці слів і складів. Фразеологізми. Опрацювання тексту «Весела зима». Скоромовки 117 KB
  Навчити учнів упізнавати звуки у мовленому слові та позначати їх буквою Зз зечитати слова з новою буквою чітко вимовляти звуки перед глухими приголосними та в кінці слова; розвивати спостережливість увагу логічне мислення вміння зіставляти порівнювати звукобуквений склад та їх смислове значення...