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


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


Память лучше отводить не из массива, а функцией 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; } /* вставка после 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).




- Начало -  - Назад -  - Вперед -