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;


 

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

8527. Вступ. Зміст, завдання, структура курсу новітня історія України в 10 класі 49 KB
  Вступ. Зміст, завдання, структура курсу новітня історія України в 10 класі. Мета: Визначити, який період історії України вивчатиметься цього навчального року пояснити якою була територія і населення України на початку ХХ століття ознайомити учнів ...
8528. Цінності та перспективи християнської моралі 20.98 KB
  Тема уроку: Цінності та перспективи християнської моралі (11-кл.) Мета уроку: Н: Ознайомити учнів з основними поняттями мораль, християнська мораль, визначити їхню важливість та перспективи в сучасному світі Р: Сприяти розвитку пізнавального інтере...
8529. Державний лад. Форми правління. Урок 53.61 KB
  Тема уроку. Державний лад. Форми правління. Мета уроку: ознайомити учнів з основними аспектами питання про державний лад та форми правління розвивати в учнів здатність застосовувати отримані знання на практиці виховувати в ліцеїстів...
8530. Початок Української революції. Утворення Центральної Ради 58 KB
  Початок Української революції. Утворення Центральної Ради. Мета: зясувати причини, мету, програму діяльності Центральної ради, розглянути перший етап Української революції та його особливості, розвивати навички аналізу історичних фактів, вмін...
8532. Философия науки неопозитивизма: основные концепции 23.06 KB
  Философия науки неопозитивизма: основные концепции Третий этап позитивизма: неопозитивизм. (40-е гг. 20 в.) Основные представители: Шлик, Нейрат, Карнар, Айер. Главная задача философии неопозитивизма - это анализ языка науки, поэтому этот этап ...
8533. Постпозитивизм. проблема демаркации эмпирических и теоретических наук 19.63 KB
  Постпозитивизм. проблема демаркации эмпирических и теоретических наук Позитивизм - направление в науке и философии, исходящее из позитивного, т. е. из данного, устойчивого, фактического, несомненного, и ограничивает им свое изложение и исслед...
8534. Бытие как философская категория: основные формы и диалектика бытия 21.33 KB
  Бытие как философская категория: основные формы и диалектика бытия Бытие —- это философская категория, обозначающая независимое от сознания существование объективной реальности - космоса, природы, человека. Впервые понятие...
8535. История развития философского понятия материя 20.26 KB
  История развития философского понятия материя Уже в древности философы пытались представить видимое многообразие вещей как проявление видимого начала. Это общее, несотворимая и неуничтожимая основа всех вещей получила название субстанции. Формирован...