СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ.

Базы РАБОТЫ СО СТРУКТУРАМИ.

Структура— это совокупа нескольких переменных, нередко разных типов, сгруппированных под единым именованием для удобства воззвания. Структуры предоставляют возможность хранения огромного количества разных значений, объединенных одним общим заглавием. Это делает программку более модульной, что в свою очередь позволяет просто изменять код, так как он становится более малогабаритным. Структуры, обычно СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ., употребляют тогда, когда в программке есть много данных и их необходимо сгруппировать вкупе — к примеру, такие данные могут употребляться для хранения записей из базы данных.

Давайте представим телефонный справочник в виде структуры, другими словами в структуре должна храниться вся нужная информацию о каждом человеке — имя, адресок, номер телефона СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ., и т.д.. Синтаксис объявления структуры:

struct /*имя структуры*/ { /*переменные-члены структуры*/ };

Другими словами одно единственное имя структуры может соединять воединыжды разные переменные, они могут отличаться даже типами данных, это могут быть как массивы, строчки так и обыденные переменные. Например, давайте разглядим последующее объявление структуры:

struct home { int rooms; }; struct СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. home home1; // объявляем структуру как обыденную переменную, просто сначала дописываем слово struct home1.rooms = 4; //вот так получаем доступ к переменной

СТРУКТУРЫ И ФУНКЦИИ.

Единственно вероятные операции над структурами - это их копирование, присваивание, взятие адреса при помощи & и воплощение доступа к ее элементам. Копирование и присваивание также СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. содержат в себе передачу функциям аргументов и возврат ими значений. Структуры нельзя ассоциировать. Инициализировать структуру можно перечнем постоянных значений ее частей; автоматическую структуру также можно инициализировать присваиванием.

Чтоб лучше познакомиться со структурами, напишем несколько функций, манипулирующих точками и прямоугольниками. Существует по последней мере три подхода: передавать составляющие по отдельности, передавать всю структуру СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. полностью и передавать указатель на структуру. Каждый подход имеет свои плюсы и минусы.

1-ая функция, makepoint, получает два целых значения и возвращает структуру point.

/* makepoint: сформировывает точку по компонентам x и y */

struct point makepoint(int х, int у)

{

struct point temp;

temp.x = х;

temp СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ..у = у;

return temp;

}

Заметим: никакого конфликта меж именованием аргумента и именованием элемента структуры не появляется; более того, сходство подчеркивает родство обозначаемых им объектов.

Сейчас при помощи makepoint можно делать динамическую инициализацию хоть какой структуры либо сформировывать структурные аргументы для той либо другой функции:

Функцию makepoint можно использовать для динамической СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. инициализации хоть какой структуры либо для передачи аргументов-структур в функции:

struct rect screen;

struct point middle;

struct point makepoint(int, int);

screen.ptl = makepoint(0, 0) ;

screen.pt2 = makepoint(XMAX, YMAX);

middle = makepoint((screen.ptl.x + screen.pt2.x)/2,

(screen.ptl.у + screen.pt2.y)/2);

Последующим шагом будет создание набора функций СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. для арифметических операций над этими структурами. Вот вам наглядный пример какой-то из них:

/* addpoint: сложение координат 2-ух точек */

struct point addpoint(struct point pi, struct point p2)

{

pl.x += p2.x;

pi.у + = p2.y;

return pi;

}

Тут структурами являются как аргументы, так и возвращаемое значение. Заместо

того СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. чтоб помещать итог во временную переменную, мы инкрементировали

составляющие структуры pi, чтоб выделить тот факт, что параметры-структуры передаются по значениям, как и любые другие характеристики.

МАССИВЫ СТРУКТУР.

Массивы структур служат для обработки огромного объема инфы. Они объявляются так же, как обычно, но за ранее (выше) нужно объявить саму СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. структуру как новый тип данных. Для воззвания к полю структуры также употребляют точку, но сейчас нужно указать в квадратных скобках еще номер подходящей структуры, к примеру Book A[20]; ... A[12].pages = 50; for ( i = 0; i < 20; i ++ ) // цикл по всем структурам в массива puts(A[i].title); // вывести заглавие книжки

УКАЗАТЕЛИ НА СТРУКТУРЫ.

Для иллюстрации СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. неких моментов, касающихся указателей на структуры и массивов структур, перепишем программку подсчета ключевиков, пользуясь для получения частей массива заместо индексов указателями.

Наружное объявление массива keytab остается без конфигурации, a main и binsearch необходимо видоизменять.

#include

#include

#include

#define MAXWORD 100

int getword(char *, int);

struct key *binsearch(char *, struct key *, int СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ.);

/* подсчет ключевиков Си: версия с указателями */

main()

{

char word[MAXWORD];

struct key *p;

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

if (isalpha(word[0]))

if ((p = binsearch(word, keytab, NKEYS)) != NULL)

p->count++;

for (p = keytab; p < keytab + NKEYS; p++)

if (p->count > 0)

printf("%4d %s\n", p->count, p СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ.->word);

return 0;

}

/* binsearch: отыскать слово word в tab[0]...tab[n-1] */

struct key *binsearch(char *word, struct key *tab, int n)

{

int cond;

struct key *low = &tab[0];

struct key *high = &tab[n];

struct key *mid;

while (low < high) {

mid = low + (high - low) / 2;

if ((cond = strcmp(word, mid->word)) < 0)

high = mid;

else СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. if (cond > 0)

low = mid + 1;

else

return mid;

}

return NULL;

}

Во-1-х, описание функции binsearch должно отражать тот факт, что она возвращает указатель на struct key, а не целое, это объявлено как в макете функции, так и в функции binsearch. Если binsearch находит слово, то она выдает указатель на него, в СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. неприятном случае она возвращает NULL. Во-2-х, к элементам keytab доступ в нашей программке осуществляется через указатели. Это потребовало значимых конфигураций вbinsearch. Инициализаторами для low и high сейчас служат указатели на начало и на место сходу после конца массива. Вычисление положения среднего элемента при помощи формулы

mid = (low + high) / 2 /* Ошибочно */

не СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. годится, так как указатели нельзя ложить. Но к ним можно применить операцию вычитания, и потому что high-low есть число частей, присваивание

mid = low + (high-low) / 2

превратит mid в указатель на элемент, лежащий в центре меж low и high.

СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ.

Один из методов - повсевременно поддерживать упорядоченность СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. уже приобретенных слов, помещая каждое новое слово в такое место, чтоб не нарушалась имеющаяся упорядоченность. Делать это передвижкой слов в линейном массиве не следует, - хотя бы поэтому, что обозначенная процедура тоже очень долгая. Заместо этого мы воспользуемся структурой данных, именуемой бинарным деревом.

В дереве на каждое СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. отдельное слово предусмотрен "узел", который содержит:

- указатель на текст слова;

- счетчик числа встречаемости;

- указатель на левый сыновний узел;

- указатель на правый сыновний узел.

У каждого узла может быть один либо два отпрыска, либо узел вообщем может не иметь отпрыской.

Узлы в дереве размещаются так, что по отношению к хоть какому узлу левое СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое - слова, которые больше него. Ах так смотрится дерево, построенное для фразы "now is the time for all good men to come to the aid of their party" ("пришло время всем хорошим людям посодействовать СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. собственной партии"), по окончании процесса, в каком для каждого нового слова в него добавлялся новый узел:

Вернемся к описанию узла, которое комфортно представить в виде структуры с 4-мя компонентами:

struct tnode { /* узел дерева */

char *word; /* указатель на текст */

int count; /* число вхождений */

struct tnode *left; /* левый отпрыск */

struct tnode *right СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ.; /* правый отпрыск */

};

Приведенное рекурсивное определение узла может показаться рискованным, но оно правильное. Структура не может включать саму себя, но ведь

struct tnode *left;

заявляет left как указатель на tnode, а не сам tnode.

ПОИСК В ТАБЛИЦЕ.

В этом параграфе, чтоб проиллюстрировать новые нюансы внедрения структур, мы напишем ядро пакета СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. программ, осуществляющих вставку частей в таблицы и их поиск снутри таблиц. Этот пакет - обычный набор программ, при помощи которых работают с таблицами имен в любом макропроцессоре либо компиляторе. Разглядим, к примеру, аннотацию #define. Когда встречается строчка вида

#define IN 1

имя IN и замещающий его текст 1 должны запоминаться в таблице. Если потом имя СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. IN повстречается в аннотации, к примеру в

state = IN;

это должно быть заменено на 1.

Есть две программки, манипулирующие с именами и замещающими их текстами. Это install(s,t), которая записывает имя s и замещающий его текст t в таблицу, где s и t - строчки, и lookup(s), осуществляющая поиск s СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. в таблице и возвращающая указатель на место, где имя s было найдено, либо NULL, если s в таблице не оказалось.

Метод основан на хэш-поиске: поступающее имя свертывается в неотрицательное число (хэш-код), которое потом употребляется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. на начало связанного перечня блоков, описывающих имена с данным хэш-кодом. Если элемент массива равен NULL, это означает, что имен с подходящим хэш-кодом нет.

Блок в перечне - это структура, содержащая указатели на имя, на замещающий текст и на последующий блок в перечне; значение NULL в указателе на последующий СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. блок значит конец перечня.

struct nlist { /* элемент таблицы */

struct nlist *next; /* указатель на последующий элемент */

char *name; /* определенное имя */

char *defn; /* замещающий текст */

};

А ах так записывается определение массива указателей:

#define HASHSIZE 101

static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */

Функция хэширования, применяемая в lookup и install, суммирует коды знаков СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. в строке и в качестве результата выдаст остаток от деления приобретенной суммы на размер массива указателей. Это не самая наилучшая функция хэширования, но довольно лаконичная и действенная.

/* hash: получает хэш-код для строчки s */

unsigned hash(char *s)

{

unsigned hashval;

for (hashval = 0; *s != '\0'; s++)

hashval = *s + 31 * hashval;

return hashval % HASHSIZE;

}

Беззнаковая СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. математика гарантирует, что хэш-код будет неотрицательным.

Хэширование порождает стартовый индекс для массива hashtab; если соответственная строчка в таблице есть, она может быть найдена исключительно в перечне блоков, на начало которого показывает элемент массива hashtab с этим индексом. Поиск осуществляется при помощи lookup. Если lookup находит элемент с СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. данной строчкой, то возвращает указатель на нее, если не находит, то возвращает NULL.

/* lookup: отыскивает s */

struct nlist *lookup(char *s)

{

struct nlist *np;

for (np = hashtab[hash(s)]; np != NULL; np = np->next)

if (strcmp(s, np->name) == 0)

return np; /* отыскали */

return NULL; /* не отыскали */

}

В for СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ.-цикле функции lookup для просмотра перечня употребляется стандартная конструкция

for (ptr = head; ptr != NULL; ptr = ptr->next)

...

Функция install обращается к lookup, чтоб найти, имеется ли уже вставляемое имя. Если это так, то старенькое определение будет заменено новым. В неприятном случае будет образован новый элемент. Если запрос памяти для нового элемента СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. не может быть удовлетворен, функция install выдает NULL.

struct nlist *lookup(char *);

char *strdup(char *);

/* install: вносит имя и текст (name, defn) в таблицу */

struct nlist *install(char *name, char *defn)

{

struct nlist *np;

unsigned hashval;

if ((np = lookup(name)) == NULL) else /* уже имеется */

free((void *) np->defn); /* освобождаем СТРУКТУРЫ СО ССЫЛКАМИ НА СЕБЯ. прежний defn */

if ((np->defn = strdup(defn)) == NULL)

return NULL;

return np;

}


strukturnij-psihoanaliz-zh-lakana.html
strukturnij-sostav-bezrabotnih-grazhdan-po-osnovaniyam-nezanyatosti-gosudarstvennij-doklad-o-sostoyanii-zanyatosti.html
strukturno-dinamicheskij-podhod-v-psihologii-lichnosti.html