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;


 

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

72470. Введение в методику развития речи 236 KB
  Компетентностная направленность изучения темы Задание: прочитайте подчеркните важные с вашей точки зрения слова словосочетания предложения абзацы. Материал темы Введение в методику развития речи изучаемой в курсе современной Теории и методики развития речи...
72471. ПОНЯТИЕ О НЕОТЛОЖНЫХ СОСТОЯНИЯХ. ПРИЧИНЫ И ФАКТОРЫ ИХ ВЫЗЫВАЮЩИЕ И ПЕРВАЯ ДОВРАЧЕБНАЯ ПОМОЩЬ 63.5 KB
  В жизни каждого человека вследствие различных причин могут произойти случаи когда его соматическое и физическое здоровье резко меняется ему становится плохо он может даже потерять сознание. При таком состоянии человеку требуется срочная помощь.
72472. Восточные славяне в древности 89 KB
  Славянские народы принадлежат к древнему индоевропейскому единству, включающему такие народы как германские, балтийские, романские, греческие, кельтские, иранские, индийские раскинувшиеся на огромном пространстве от Атлантического океана до Индийского, от Ледовитого океана до Средиземного моря.
72473. ВОЛНОВЫЕ МЕХАНИЧЕСКИЕ ПЕРЕДАЧИ 609 KB
  Генератор устроен так чтобы деформированное гибкое колесо прижималось к внутренней цилиндрической поверхности жесткого колеса с силой достаточной для передачи нагрузки за счет сил трения. При вращении генератора волна перемещений бежит по окружности гибкого колеса.
72474. Подшипники. Назначение и классификация 473.5 KB
  Подшипники служат опорами для валов и вращающихся осей. Они воспринимают радиальные и осевые нагрузки, приложенные к валу, и передают их на раму машины. При этом вал должен фиксироваться в определенном положении и вращаться вокруг заданной геометрической оси.
72475. ПОДШИПНИКИ КАЧЕНИЯ. ОБЩИЕ СВЕДЕНИЯ И КЛАССИФИКАЦИЯ 975.5 KB
  Применение подшипников качения позволило заменить трение скольжения трением качения. Конструкция подшипников качения позволяет изготовлять их в массовых количествах как стандартную продукцию что значительно снижает стоимость производства.
72476. ЧЕРВЯЧНЫЕ ПЕРЕДАЧИ 380 KB
  Существенное отличие червячной передачи от зубчатой заключается в том, что окружные скорости червяка и колеса не совпадают как по величине, так и по направлению. Они направлены друг к другу под углом перекрещивания.
72477. ОСОБЕННОСТИ РАСЧЕТА ПЛАНЕТАРНЫХ ПЕРЕДАЧ 307.5 KB
  Планетарными называют передачи, включающие в себя зубчатые колеса с перемещающимися осями (рис.10.1,а). Передача состоит из центрального колеса с наружными зубьями, центрального колеса b с внутренними зубьями и водила Н, но котором укреплены оси сателлитов g.
72478. ПЕРЕДАТОЧНОЕ ОТНОШЕНИЕ ОДНОСТУПЕНЧАТЫХ И МНОГОСТУПЕНЧАТЫХ ЗУБЧАТЫХ ПЕРЕДАЧ 181 KB
  Масса и габариты редуктора в значительной степени зависят от того, как распределено общее передаточное отношение по ступеням передачи. Лучшие показатели имеют редукторы, у которых диаметры колес (а не шестерен) всех ступеней близки между собой.