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;


 

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

39911. Информационные системы. Понятие, задачи и функции ИС 814.2 KB
  Также в достаточно широком смысле[2] трактует понятие информационной системы Федеральный закон РФ от 27 июля 2006 года № 149ФЗ Об информации информационных технологиях и о защите информации: информационная система совокупность содержащейся в базах данных информации и обеспечивающих ее обработку информационных технологий и технических средств[3]. Классификация по степени автоматизации По степени автоматизации ИС делятся на: автоматизированные: информационные системы в которых автоматизация может быть неполной то есть требуется...
39912. Модель парной линейной регрессии. Метод наименьших квадратов для оценки параметров уравнения регрессии и проверка его адекватности 210.22 KB
  Метод наименьших квадратов для оценки параметров уравнения регрессии и проверка его адекватности. Регрессии нелинейные по включенным переменным приводятся к линейному виду простой заменой переменных а дальнейшая оценка параметров производится с помощью метода наименьших квадратов. Выделяют следующие методы экстраполяции: среднего абсолютного прироста может быть выполнено в том случае если есть уверенность считать общую тенденцию линейной то есть метод основан на предположении о равномерном изменении уровня под равномерностью понимается...
39914. Формы и способы представления данных 1.31 MB
  2 Единицы измерения данных. binry digit] Простое двоичное число цифра или символ принимающее значения 1 или 0 и служащее для записи и хранения данных в ЭВМ. Байт [byte ] Двоичное слово способное записывать и хранить в памяти ЭВМ один буквенноцифровой или другой символ данных.
39915. Единицы измерения данных 898.34 KB
  Другие файловые системы оперируют схожими понятиями зоны в Minix блоки в Unix. 4 Системы счисления. Все системы счисления можно разделить на два класса: позиционные и непозиционные. Число таких знаков в позиционной системе счисления называется основанием системы счисления.
39916. Основы информационной культуры. Понятие информации и данных 721 KB
  Формы и способы представления данных. 2 способа представления данных: в текстовом и числовом виде Текстовые данные воспринимаются передающими системами как текст записанный на какомлибо языке. 2 Единицы измерения данных Объем данных V количество байт которое требуется для их хранения в памяти электронного носителя информации. Байт мельчайшая адресуемая единица информации Килобайт базовая единица Машинное слово машиннозависимая и платформозависимая величина измеряемая в битах или байтах равная разрядности регистров процессора и...
39918. Модель парной линейной регрессии 531.5 KB
  Этот коэффициент характеризует степень финансового риска проекта для собственников предприятия и кредиторов и обычно анализируется банками при решении вопроса о предоставлении долгосрочного кредита; коэффициент покрытия долгосрочных обязательств отношение чистого прироста свободных средств сумма чистой прибыли после уплаты налога амортизации и чистого прироста собственных и заемных средств за вычетом осуществленных в отчетном периоде инвестиций к величине платежей по долгосрочным обязательствам погашение займов проценты по ним. Для...
39919. Модели сетевого планирования и управления, назначения, область применения и основные характеристики 66.75 KB
  Сетевой моделью СМ называется экономикоматематическая модель отражающая весь комплекс работ и событий связанных с реализацией проекта в их логической и технологической последовательности и связи. Модели сетевого планирования и управления модели СПУ предназначены для планирования и управления сложными комплексами работ проектами направленными на достижение определенной цели в заданные сроки строительство разработка и производство сложных объектов и др. Область применения: сетевое планирование позволяет осуществлять анализ проекта...