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;


 

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

45190. Определение затрат на строительство и разборку временных зданий и сооружений 15.38 KB
  Определение затрат: на строительство и разборку временных зданий и сооружений дополнительных затрат при производстве работ в зимнее время резерв на непредвиденные работы и затраты. Склады вспомогательные здания и сооружения необходимые для производства и обслуживания работников строительства временная столовая и т. зданий и сооружений ГСН 8105012001 для стрва и сборнике сметных норм затрат на стрво временных зданий и сооружений ремонтные работы ГСНр 8105012001 Нормативы приводятся в и считаются от сметной стоимости...
45191. Законодательные и методические документы, регулирующие градостроительную деятельность и вопросы определения стоимости строительства 14.37 KB
  Методика определения стоимости строительной продукции на территории Российской Федерации МДС 81-365.2004 (внесена в Федеральный реестр сметных нормативов, подлежащих применению при определении сметной стоимости объектов капитального строительства, под регистрационным номером 94 от 15.12.2009)
45192. Определение сметных норм и единичных расценок, перечислить виды ГЭСН, ТЕР, ФЭР 16.71 KB
  Индивидуальные новые технологии разработанные для отдельного объекта Элементные расценки цены Абсолютные укрупненные показатели и нормативы Сметная норма совокупность ресурсов материальных трудовых технологических установленная на принятый измеритель в строительных монтажных ремонтностроительных и пусконаладочных работах. Государственные сметные нормативы: Государственные элементные сметные нормативы на строительные и специальные работыГЭСН2001 Государственные элементные сметные нормативы на ремонтностроительные...
45193. Определение понятий: стройка, объект капитального строительства, реконструкция 13.89 KB
  Определение понятий: стройка объект капитального строительства реконструкция. Стройка комплекс объектов капитального строительства различного назначения строительство капитальный ремонт реконструкция которых осуществляется по единой проектной документации объединенной свободным сметным расчетом. Объект капитального строительства здания строения сооружения строительство которого может быть не завершено. строительства относятся: непроизводственные объекты объекты производственного назначения линейные объекты траншеи мосты...
45194. Определение понятий: сметная стоимость строительства, капитальный ремонт, заказчик, подрядчик, инвестор 14.58 KB
  Определение понятий: сметная стоимость строительства капитальный ремонт заказчик подрядчик инвестор. Сметная стоимость строительства – стоимостная оценка полного перечня затрат Заказчика Инвестора на реализацию проектных решений по объектам капитального строительства строящимся реконструируемым в границах принадлежащего Застройщику земельного участка а также в случае проведения капитального ремонта объекта капитального строительства в уровне цен определенном Заказчиком в Техническом задании на разработку Проектной в том числе...
45195. Смета на строительство объектов капитального строительства» в соответствии с постановлением Правительства РФ №87 от 16.02.2008 14.7 KB
  Содержание раздела 11 проектной документации Смета на строительство объектов капитального строительства в соответствии с постановлением Правительства РФ №87 от 16. №87 О СОСТАВЕ РАЗДЕЛОВ ПРОЕКТНОЙ ДОКУМЕНТАЦИИ И ТРЕБОВАНИЯ К ИХ СОДЕРЖАНИЮ Извлечения Раздел 11 Смета на строительство объектов капитального строительства должен содержать текстовую часть в составе пояснительной записки к сметной документации и сметную документацию. Пояснительная записка к сметной документации должна содержать следующую информацию: а сведения о месте...
45196. Определение стоимости проектных работ 19.42 KB
  Определение стоимости проектных работ Расчет на основании Справочника базовых цен на проектные работы для строительства на территории Самарской области 2я редакция Спр=Срасчед Уарх К1арх.КnобщSобщ 100 где Срасч ед стоимость строительства единицы мощности площади объёма объектов различного функционального назначения из журнала укрупнённых показателей стоимости строительства Уарх Уконстр. удельный показатель стоимости отдельных разделов проектаПриложение 2 таблица 3 и повышающих коэффициентов к ним табл. учитывающий...
45197. Определение затрат на проведение строительного контроля 15.51 KB
  Установить что в отношении объектов капитального строительства финансируемых полностью или частично с привлечением средств федерального бюджета: а если подготовка проектной документации завершена до вступления в силу настоящего Постановления заказчик проектной документации вправе направить ее на государственную экспертизу без проведения дополнительных работ связанных с осуществлением расчета размера затрат на проведение строительного контроля; б отсутствие расчета размера затрат на проведение строительного контроля в проектной...