5. Структуры данных.
Структуры ("записи") представляют собой агрегаты разнородных данных (полей раз-
ного типа); в отличие от массивов, где все элементы имеют один и тот же тип.
struct {
int x, y; /* два целых поля */
char s[10]; /* и одно - для строки */
} s1;
Структурный тип может иметь имя:
struct XYS {
int x, y; /* два целых поля */
char str[10]; /* и одно - для строки */
};
Здесь мы объявили тип, но не отвели ни одной переменной этого типа (хотя могли бы).
Теперь опишем переменную этого типа и указатель на нее:
struct XYS s2, *sptr = &s2;
Доступ к полям структуры производится по имени поля (а не по индексу, как у масси-
вов):
имя_структурной_переменной.имя_поля
указатель_на_структуру ->> имя_поля
то есть
не а
#define ВЕС 0 struct { int вес, рост; } x;
#define РОСТ 1 x.рост = 175;
int x[2]; x[РОСТ] = 175;
Например
s1.x = 13;
strcpy(s2.str, "Finish");
sptr->y = 27;
Структура может содержать структуры другого типа в качестве полей:
struct XYS_Z {
struct XYS xys;
int z;
} a1;
a1.xys.x = 71; a1.z = 12;
Структура того же самого типа не может содержаться в качестве поля - рекурсивные
определения запрещены. Зато нередко используются поля - ссылки на структуры такого
же типа (или другого). Это позволяет организовывать списки структур:
struct node {
int value;
struct node *next;
};
Очень часто используются массивы структур:
А. Богатырев, 1992-95 - 173 - Си в UNIX
struct XYS array[20]; int i = 5, j;
array[i].x = 12;
j = array[i].x;
Статические структуры можно описывать с инициализацией, перечисляя значения их полей
в {} через запятую:
extern struct node n2;
struct node n1 = { 1, &n2 },
n2 = { 2, &n1 },
n3 = { 3, NULL };
В этом примере n2 описано предварительно для того, чтобы &n2 в строке инициализации
n1 было определено.
Структуры одинакового типа можно присваивать целиком (что соответствует присваи-
ванию каждого из полей):
struct XYS s1, s2; ...
s2 = s1;
в отличие от массивов, которые присваивать целиком нельзя:
int a[5], b[5]; a = b; /* ОШИБОЧНО ! */
Пример обращения к полям структуры:
typedef struct _Point {
short x, y; /* координаты точки */
char *s; /* метка точки */
} Point;
Point p; Point *pptr; short *iptr;
struct _Curve {
Point points[25]; /* вершины ломанной */
int color; /* цвет линии */
} aLine[10], *linePtr = & aLine[0];
...
pptr = &p; /* указатель на структуру p */
p.x = 1; p.y = 2; p.s = "Grue";
linePtr->points[2].x = 54; aLine[5].points[0].y = 17;
В ы р а ж е н и е значение
---------+------------+------------+-----------+-----------
p.x | pptr->x | (*pptr).x | (&p)->x | 1
---------+------------+------------+-----------+-----------
&p->x | ошибка
-----------+----------------+------------------+-----------
iptr= &p.x | iptr= &pptr->x | iptr= &(pptr->x) | адрес поля
-----------+----------------+--------+---------+-----------
*pptr->s | *(pptr->s) | *p.s | p.s[0] | 'G'
-----------+----------------+--------+---------+-----------
pptr->s[1] | (&p)->s[1] | p.s[1] | 'r'
-----------+----------------+------------------+-----------
&p->s[1] | ошибка
-----------+----------------+------------------+-----------
(*pptr).s | pptr->s | p.s | "Grue"
-----------+----------------+------------------+-----------
*pptr.s | ошибка
-----------------------------------------------+-----------
А. Богатырев, 1992-95 - 174 - Си в UNIX
Вообще (&p)->field = p.field
pptr->field = (*pptr).field
Объединения - это агрегаты данных, которые могут хранить в себе значения данных
разных типов на одном и том же месте.
struct a{ int x, y; char *s; } A;
union b{ int i; char *s; struct a aa; } B;
Структура:
________________________
A: | A.x int | Три поля
------------------------ расположены подряд.
| A.y int | Получается как бы
------------------------ "карточка" с графами.
| A.s char * |
------------------------
А у объединений поля расположены "параллельно",
на одном месте в памяти.
_______________________________________________________
B: | B.i int | B.s char * | B.aa : B.aa.x int |
-----------| | struct a : B.aa.y int |
---------------| : B.aa.s char * |
|___________________________|
Это как бы "ящик" в который можно поместить значение любого типа из перечисленных, но
не ВСЕ ВМЕСТЕ ("и то и это", как у структур), а ПО ОЧЕРЕДИ ("или/или"). Размер его
достаточно велик, чтоб вместить самый большой из перечисленных типов данных.
Мы можем занести в union значение и интерпретировать его как другой тип данных -
это иногда используется в машинно-зависимых программах. Вот пример, выясняющий поря-
док байтов в short числах:
union lb {
char s[2]; short i;
} x;
unsigned hi, lo;
x.i = (02 << 8) | 01;
hi = x.s[1]; lo = x.s[0];
printf( "%d %d\n", hi, lo);
или так:
#include <stdio.h>
union {
int i;
unsigned char s[sizeof(int)];
} u;
void main(){
unsigned char *p;
int n;
u.i = 0x12345678;
for(n=0, p=u.s; n < sizeof(int); n++, p++){
printf("%02X ", *p);
}
putchar('\n');
}
А. Богатырев, 1992-95 - 175 - Си в UNIX
или порядок слов в long числах:
union xx {
long l;
struct ab {
short a; /* low word */
short b; /* high word */
} ab;
} c;
main(){ /* На IBM PC 80386 печатает 00020001 */
c.ab.a = 1; c.ab.b = 2; printf("%08lx\n", c.l );
}
5.1. Найдите ошибки в описании структурного шаблона:
structure { int arr[12],
char string,
int *sum
}
5.2. Разработайте структурный шаблон, который содержал бы название месяца, трехбук-
венную аббревиатуру месяца, количество дней в месяце и номер месяца. Инициализируйте
его для невисокосного года.
struct month {
char name[10]; /* или char *name; */
char abbrev[4]; /* или char *abbrev; */
int days;
int num;
};
struct month months[12] = { /* индекс */
{"Январь" , "Янв", 31, 1 }, /* 0 */
{"Февраль", "Фев", 28, 2 }, /* 1 */
...
{"Декабрь", "Дек", 31, 12}, /* 11 */
}, *mptr = & months[0]; /* или *mptr = months */
main(){
struct month *mptr;
printf( "%s\n", mptr[1].name );
printf( "%s %d\n", mptr->name, mptr->num );
}
Напишите функцию, сохраняющую массив months в файл; функцию, считывающую его из
файла. Используйте fprintf и fscanf.
В чем будет разница в функции чтения, когда поле name описано как char name[10]
и как char *name?
Ответ: во втором случае для сохранения прочитанной строки надо заказывать память
динамически при помощи malloc() и сохранять в ней строку при помощи strcpy(), т.к.
память для хранения самой строки в структуре не зарезервирована (а только для указа-
теля на нее).
Найдите ошибку в операторах функции main(). Почему печатается не "Февраль", а
какой-то мусор? Указание: куда указывает указатель mptr, описанный в main()? Ответ: в
"неизвестно куда" - это локальная переменная (причем не получившая начального значе-
ния - в ней содержится мусор), а не то же самое, что указатель mptr, описанный выше!
Уберите описание mptr из main.
А. Богатырев, 1992-95 - 176 - Си в UNIX
Заметим, что для распечатки всех или нескольких полей структуры следует ЯВНО
перечислить в printf() все нужные поля и указать форматы, соответствующие типам этих
полей. Не существует формата или стандартной функции, позволяющей распечатать все
поля сразу (однако такая функция может быть написана вами для конкретного типа струк-
тур). Также не существует формата для scanf(), который вводил бы структуру целиком.
Вводить можно только по частям - каждое поле отдельно.
5.3. Напишите программу, которая по номеру месяца возвращает общее число дней года
вплоть до этого месяца.
5.4. Переделайте предыдущую программу таким образом, чтобы она по написанному бук-
вами названию месяца возвращала общее число дней года вплоть до этого месяца. В прог-
рамме используйте функцию strcmp().
5.5. Переделайте предыдущую программу таким образом, чтобы она запрашивала у пользо-
вателя день, месяц, год и выдавала общее количество дней в году вплоть до данного
дня. Месяц может обозначаться номером, названием месяца или его аббревиатурой.
5.6. Составьте структуру для учетной картотеки служащего, которая содержала бы сле-
дующие сведения: фамилию, имя, отчество; год рождения; домашний адрес; место работы,
должность; зарплату; дату поступления на работу.
5.7. Что печатает программа?
struct man {
char name[20];
int salary;
} workers[] = {
{ "Иванов", 200 },
{ "Петров", 180 },
{ "Сидоров", 150 }
}, *wptr, chief = { "начальник", 550 };
main(){
struct man *ptr, *cptr, save;
ptr = wptr = workers + 1;
cptr = &chief;
save = workers[2]; workers[2] = *wptr; *wptr = save;
wptr++; ptr--; ptr->salary = save.salary;
printf( "%c %s %s %s %s\n%d %d %d %d\n%d %d %c\n",
*workers[1].name, workers[2].name, cptr->name,
ptr[1].name, save.name,
wptr->salary, chief.salary,
(*ptr).salary, workers->salary,
wptr - ptr, wptr - workers, *ptr->name );
}
Ответ:
С Петров начальник Сидоров Сидоров
180 550 150 150
2 2 И
5.8. Разберите следующий пример:
#include <stdio.h>
struct man{
А. Богатырев, 1992-95 - 177 - Си в UNIX
char *name, town[4]; int salary;
int addr[2];
} men[] = {
{ "Вася", "Msc", 100, { 12, 7 } },
{ "Гриша", "Len", 120, { 6, 51 } },
{ "Петя", "Rig", 140, { 23, 84 } },
{ NULL, "" , -1, { -1, -1 } }
};
main(){
struct man *ptr, **ptrptr;
int i;
ptrptr = &ptr;
*ptrptr = &men[1]; /* men+1 */
printf( "%s %d %s %d %c\n",
ptr->name,
ptr->salary,
ptr->town,
ptr->addr[1],
ptr[1].town[2] );
(*ptrptr)++;
/* копируем *ptr в men[0] */
men[0].name = ptr->name; /* (char *) #1 */
strcpy( men[0].town, ptr->town ); /* char [] #2 */
men[0].salary = ptr->salary; /* int #3 */
for( i=0; i < 2; i++ )
men[0].addr[i] = ptr->addr[i]; /* массив #4 */
/* распечатываем массив структур */
for(ptr=men; ptr->name; ptr++ )
printf( "%s %s %d\n",
ptr->name, ptr->town, ptr->addr[0]);
}
Обратите внимание на такие моменты:
1) Как производится работа с указателем на указатель (ptrptr).
2) При копировании структур отдельными полями, поля скалярных типов (int, char,
long, ..., указатели) копируются операцией присваивания (см. строки с пометками
#1 и #3). Поля векторных типов (массивы) копируются при помощи цикла, поэле-
ментно пересылающего массив (строка #4). Строки (массивы букв) пересылаются
стандартной функцией strcpy (строка #2). Все это относится не только к полям
структур, но и к переменным таких типов. Структуры можно также копировать не по
полям, а целиком: men[0]= *ptr;
3) Запись аргументов функции printf() лесенкой позволяет лучше видеть, какому фор-
мату соответствует каждый аргумент.
4) При распечатке массива структур мы печатаем не определенное их количество (рав-
ное размеру массива), а пользуемся указателем NULL в поле name последней струк-
туры как признаком конца массива.
5) В поле town мы храним строки из 3х букв, однако выделяем для хранения массив из
4х байт. Это необходимо потому, что строка "Msc" состоит не из 3х, а из 4х бай-
тов: 'M','s','c','\0'.
При работе со структурами и указателями большую помощь могут оказать рисунки. Вот как
(например) можно нарисовать данные из этого примера (массив men изображен не весь):
А. Богатырев, 1992-95 - 178 - Си в UNIX
--ptr-- --ptrptr--
ptr | * |<------|---* |
---|--- ----------
|
/ =========men[0]==
/ men:|name | *---|-----> "Вася"
| |---------------|
| |town |M|s|c|\0|
| |---------------|
| |salary| 100 |
| |---------------|
| |addr | 12 | 7 |
\ -----------------
\ =========men[1]==
\-->|name | *---|-----> "Гриша"
............
5.9. Составьте программу "справочник по таблице Менделеева", которая по названию
химического элемента выдавала бы его характеристики. Таблицу инициализируйте массивом
структур.
5.10. При записи данных в файл (да и вообще) используйте структуры вместо массивов,
если элементы массива имеют разное смысловое назначение. Не воспринимайте структуру
просто как средство объединения данных разных типов, она может быть и средством объе-
динения данных одного типа, если это добавляет осмысленности нашей программе. Чем
плох фрагмент?
int data[2];
data[0] = my_key;
data[1] = my_value;
write(fd, (char *) data, 2 * sizeof(int));
Во-первых, тогда уж лучше указать размер всего массива сразу (хотя бы на тот случай,
если мы изменим его размер на 3 и забудем поправить множитель с 2 на 3).
write(fd, (char *) data, sizeof data);
Кстати, почему мы пишем data, а не &data? (ответ: потому что имя массива и есть его
адрес). Во-вторых, элементы массива имеют разный смысл, так не использовать ли тут
структуру?
struct _data {
int key;
int value;
} data;
data.key = my_key;
data.value = my_value;
write(fd, &data, sizeof data);
5.11. Что напечатает следующая программа? Нарисуйте расположение указателей по окон-
чании данной программы.
#include <stdio.h>
struct lnk{
char c;
А. Богатырев, 1992-95 - 179 - Си в UNIX
struct lnk *prev, *next;
} chain[20], *head = chain;
add(c) char c;
{
head->c = c;
head->next = head+1;
head->next->prev = head;
head++;
}
main(){
char *s = "012345";
while( *s ) add( *s++ );
head->c = '-';
head->next = (struct lnk *)NULL;
chain->prev = chain->next;
while( head->prev ){
putchar( head->prev->c );
head = head->prev;
if( head->next )
head->next->prev = head->next->next;
}
}
5.12. Напишите программу, составлящую двунаправленный список букв, вводимых с клави-
атуры. Конец ввода - буква '\n'. После третьей буквы вставьте букву '+'. Удалите
пятую букву. Распечатайте список в обратном порядке. Оформите операции
вставки/удаления как функции. Элемент списка должен иметь вид:
struct elem{
char letter; /* буква */
char *word; /* слово */
struct elem *prev; /* ссылка назад */
struct elem *next; /* ссылка вперед */
};
struct elem *head, /* первый элемент списка */
*tail, /* последний элемент */
*ptr, /* рабочая переменная */
*prev; /* предыдущий элемент при просмотре */
int c, cmp;
...
while((c = getchar()) != '\n' )
Insert(c, tail);
for(ptr=head; ptr != NULL; ptr=ptr->next)
printf("буква %c\n", ptr->letter);
Память лучше отводить не из массива, а функцией calloc(), которая аналогична функции
malloc(), но дополнительно расписывает выделенную память байтом '\0' (0, NULL). Вот
функции вставки и удаления:
extern char *calloc();
/* создать новое звено списка для буквы c */
struct elem *NewElem(c) char c; {
struct elem *p = (struct elem *)
calloc(1, sizeof(struct elem));
/* calloc автоматически обнуляет все поля,
* в том числе prev и next
*/
p->letter = c; return p;
}
А. Богатырев, 1992-95 - 180 - Си в UNIX
/* вставка после ptr (обычно - после tail) */
Insert(c, ptr) char c; struct elem *ptr;
{ struct elem *newelem = NewElem(c), *right;
if(head == NULL){ /* список был пуст */
head=tail=newelem; return; }
right = ptr->next; ptr->next = newelem;
newelem->prev = ptr; newelem->next = right;
if( right ) right->prev = newelem;
else tail = newelem;
}
/* удалить ptr из списка */
Delete( ptr ) struct elem *ptr; {
struct elem *left=ptr->prev, *right=ptr->next;
if( right ) right->prev = left;
if( left ) left->next = right;
if( tail == ptr ) tail = left;
if( head == ptr ) head = right;
free((char *) ptr);
}
Напишите аналогичную программу для списка слов.
struct elem *NewElem(char *s) {
struct elem *p = (struct elem *)
calloc(1, sizeof(struct elem));
p->word = strdup(s);
return p;
}
void DeleteElem(struct elem *ptr){
free(ptr->word);
free(ptr);
}
Усложнение: вставляйте слова в список в алфавитном порядке. Используйте для этого
функцию strcmp(), просматривайте список так:
struct elem *newelem;
if (head == NULL){ /* список пуст */
head = tail = NewElem(новое_слово);
return;
}
/* поиск места в списке */
for(cmp= -1, ptr=head, prev=NULL;
ptr;
prev=ptr, ptr=ptr->next
)
if((cmp = strcmp(новое_слово, ptr->word)) <= 0 )
break;
Если цикл окончился с cmp==0, то такое слово уже есть в списке. Если cmp < 0, то
такого слова не было и ptr указывает элемент, перед которым надо вставить слово
новое_слово, а prev - после которого (prev==NULL означает, что надо вставить в начало
списка); т.е. слово вставляется между prev и ptr. Если cmp > 0, то слово надо доба-
вить в конец списка (при этом ptr==NULL).
head ==> "a" ==> "b" ==> "d" ==> NULL
| |
prev "c" ptr
А. Богатырев, 1992-95 - 181 - Си в UNIX
if(cmp == 0) return; /* слово уже есть */
newelem = NewElem( новое_слово );
if(prev == NULL){ /* в начало */
newelem->next = head;
newelem->prev = NULL;
head->prev = newelem;
head = newelem;
} else if(ptr == NULL){ /* в конец */
newelem->next = NULL;
newelem->prev = tail;
tail->next = newelem;
tail = newelem;
} else { /* между prev и ptr */
newelem->next = ptr;
newelem->prev = prev;
prev->next = newelem;
ptr ->prev = newelem;
}
5.13. Напишите функции для работы с комплексными числами
struct complex {
double re, im;
};
Например, сложение выглядит так:
struct complex add( c1, c2 )
struct complex c1, c2;
{
struct complex sum;
sum.re = c1.re + c2.re;
sum.im = c1.im + c2.im;
return sum;
}
struct complex a = { 12.0, 14.0 },
b = { 13.0, 2.0 };
main(){
struct complex c;
c = add( a, b );
printf( "(%g,%g)\n", c.re, c.im );
}
5.14. Массивы в Си нельзя присваивать целиком, зато структуры - можно. Иногда
используют такой трюк: структуру из единственного поля-массива
typedef struct {
int ai[5];
} intarray5;
intarray5 a, b = { 1, 2, 3, 4, 5 };
и теперь законно
a = b;
Зато доступ к ячейкам массива выглядит теперь менее изящно:
А. Богатырев, 1992-95 - 182 - Си в UNIX
a.ai[2] = 14;
for(i=0; i < 5; i++) printf( "%d\n", a.ai[i] );
Также невозможно передать копию массива в качестве фактического параметра функции.
Даже если мы напишем:
typedef int ARR16[16];
ARR16 d;
void f(ARR16 a){
printf( "%d %d\n", a[3], a[15]);
a[3] = 2345;
}
void main(void){
d[3] = 9; d[15] = 98;
f(d);
printf("Now it is %d\n", d[3]);
}
то последний printf напечатает "Now it is 2345", поскольку в f передается адрес мас-
сива, но не его копия; поэтому оператор a[3]=2345 изменяет исходный массив. Обойти
это можно, использовав тот же трюк, поскольку при передаче структуры в качестве пара-
метра передается уже не ее адрес, а копия всей структуры (как это и принято в Си во
всех случаях, кроме массивов).
5.15. Напоследок упомянем про битовые поля - элементы структуры, занимающие только
часть машинного слова - только несколько битов в нем. Размер поля в битах задается
конструкцией :число_битов. Битовые поля используются для более компактного хранения
информации в структурах (для экономии места).
struct XYZ {
/* битовые поля должны быть unsigned */
unsigned x:2; /* 0 .. 2**2 - 1 */
unsigned y:5; /* 0 .. 2**5 - 1 */
unsigned z:1; /* YES=1 NO=0 */
} xyz;
main(){
printf("%u\n", sizeof(xyz)); /* == sizeof(int) */
xyz.z = 1; xyz.y = 21; xyz.x = 3;
printf("%u %u %u\n", xyz.x, ++xyz.y, xyz.z);
/* Значение битового поля берется по модулю
* максимально допустимого числа 2**число_битов - 1
*/
xyz.y = 32 /* максимум */ + 7; xyz.x = 16+2; xyz.z = 11;
printf("%u %u %u\n", xyz.x, xyz.y, xyz.z); /* 2 7 1 */
}
Поле ширины 1 часто используется в качестве битового флага: вместо
#define FLAG1 01
#define FLAG2 02
#define FLAG3 04
int x; /* слово для нескольких флагов */
x |= FLAG1; x &= ~FLAG2; if(x & FLAG3) ...;
используется
struct flags {
unsigned flag1:1, flag2:1, flag3:1;
} x;
x.flag1 = 1; x.flag2 = 0; if( x.flag3 ) ...;
А. Богатырев, 1992-95 - 183 - Си в UNIX
Следует однако учесть, что машинный код для работы с битовыми полями более сложен и
занимает больше команд (т.е. медленнее и длиннее).
К битовым полям нельзя применить операцию взятия адреса "&", у них нет адресов и
смещений!
5.16. Пример на использование структур с полем переменного размера. Часть перемен-
ной длины может быть лишь одна и обязана быть последним полем структуры. Внимание:
это программистский трюк, использовать осторожно!
#include <stdio.h>
#define SZ 5
extern char *malloc();
#define VARTYPE char
struct obj {
struct header { /* постоянная часть */
int cls;
int size; /* размер переменной части */
} hdr;
VARTYPE body [1]; /* часть переменного размера:
в описании ровно ОДИН элемент массива */
} *items [SZ]; /* указатели на структуры */
#define OFFSET(field, ptr) ((char *) &ptr->field - (char *)ptr)
int body_offset;
/* создание новой структуры */
struct obj *newObj( int cl, char *s )
{
char *ptr; struct obj *op;
int n = strlen(s); /* длина переменной части (штук VARTYPE) */
int newsize = sizeof(struct header) + n * sizeof(VARTYPE);
printf("[n=%d newsize=%d]\n", n, newsize);
/* newsize = (sizeof(struct obj) - sizeof(op->body)) + n * sizeof(op->body);
При использовании этого размера не учитывается, что struct(obj)
выровнена на границу sizeof(int).
Но в частности следует учитывать и то, на границу чего выровнено
начало поля op->body. То есть самым правильным будет
newsize = body_offset + n * sizeof(op->body);
*/
/* отвести массив байт без внутренней структуры */
ptr = (char *) malloc(newsize);
/* наложить поверх него структуру */
op = (struct obj *) ptr;
op->hdr.cls = cl;
op->hdr.size = n;
strncpy(op->body, s, n);
return op;
}
А. Богатырев, 1992-95 - 184 - Си в UNIX
void printobj( struct obj *p )
{
register i;
printf( "OBJECT(cls=%d,size=%d)\n", p->hdr.cls, p->hdr.size);
for(i=0; i < p->hdr.size; i++ )
putchar( p->body[i] );
putchar( '\n' );
}
char *strs[] = { "a tree", "a maple", "an oak", "the birch", "the fir" };
int main(int ac, char *av[]){
int i;
printf("sizeof(struct header)=%d sizeof(struct obj)=%d\n",
sizeof(struct header), sizeof(struct obj));
{
struct obj *sample;
printf("offset(cls)=%d\n", OFFSET(hdr.cls, sample));
printf("offset(size)=%d\n", OFFSET(hdr.size, sample));
printf("offset(body)=%d\n", body_offset = OFFSET(body, sample));
}
for( i=0; i < SZ; i++ )
items[i] = newObj( i, strs[i] );
for( i=0; i < SZ; i++ ){
printobj( items[i] ); free( items[i] ); items[i] = NULL;
}
return 0;
}
5.17. Напишите программу, реализующую список со "старением". Элемент списка, к
которому обращались последним, находится в голове списка. Самый старый элемент
вытесняется к хвосту списка и в конечном счете из списка удаляется. Такой алгоритм
использует ядро UNIX для кэширования блоков файла в оперативной памяти: блоки, к
которым часто бывают обращения оседают в памяти (а не на диске).
/* Список строк, упорядоченных по времени их добавления в список,
* т.е. самая "свежая" строка - в начале, самая "древняя" - в конце.
* Строки при поступлении могут и повторяться! По подобному принципу
* можно организовать буферизацию блоков при обмене с диском.
*/
#include <stdio.h>
extern char *malloc(), *gets();
#define MAX 3 /* максимальная длина списка */
int nelems = 0; /* текущая длина списка */
struct elem { /* СТРУКТУРА ЭЛЕМЕНТА СПИСКА */
char *key; /* Для блоков - это целое - номер блока */
struct elem *next; /* следующий элемент списка */
/* ... и может что-то еще ... */
} *head; /* голова списка */
void printList(), addList(char *), forget();
А. Богатырев, 1992-95 - 185 - Си в UNIX
void main(){ /* Введите a b c d b a c */
char buf[128];
while(gets(buf)) addList(buf), printList();
}
/* Распечатка списка */
void printList(){ register struct elem *ptr;
printf( "В списке %d элементов\n", nelems );
for(ptr = head; ptr != NULL; ptr = ptr->next )
printf( "\t\"%s\"\n", ptr->key );
}
/* Добавление в начало списка */
void addList(char *s)
{ register struct elem *p, *new;
/* Анализ - нет ли уже в списке */
for(p = head; p != NULL; p = p->next )
if( !strcmp(s, p->key)){ /* Есть. Перенести в начало списка */
if( head == p ) return; /* Уже в начале */
/* Удаляем из середины списка */
new = p; /* Удаляемый элемент */
for(p = head; p->next != new; p = p->next );
/* p указывает на предшественника new */
p->next = new->next; goto Insert;
}
/* Нет в списке */
if( nelems >= MAX ) forget(); /* Забыть старейший */
if((new = (struct elem *) malloc(sizeof(struct elem)))==NULL) goto bad;
if((new->key = malloc(strlen(s) + 1)) == NULL) goto bad;
strcpy(new->key, s); nelems++;
Insert: new->next = head; head = new; return;
bad: printf( "Нет памяти\n" ); exit(13);
}
/* Забыть хвост списка */
void forget(){ struct elem *prev = head, *tail;
if( head == NULL ) return; /* Список пуст */
/* Единственный элемент ? */
if((tail = head->next) == NULL){ tail=head; head=NULL; goto Del; }
for( ; tail->next != NULL; prev = tail, tail = tail->next );
prev->next = NULL;
Del: free(tail->key); free(tail); nelems--;
}