Хрестоматия по программированию на Си в Unix


Структуры данных. Хрестоматия по программированию на Си в Unix - стр. 5


Напишите программу, реализующую список со "старением". Элемент списка, к которому обращались последним, находится в голове списка. Самый старый элемент вытесняется к хвосту списка и в конечном счете из списка удаляется. Такой алгоритм использует ядро 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(); 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--; }

© Copyright А. Богатырев, 1992-95
Си в UNIX

| |




- Начало -  - Назад -  



Книжный магазин