Лекция: Пример создания связанного списка имен, упорядоченных по алфавиту

#include <stdio.h> #define NAME_SIZE 30

struct NODE

{

struct listnode*pred;

struct listnode*succ;

char data[NAME_SIZE]; };

main()

{

char name [NAME_SIZE];

struct NODE *root; /^Голова списка.*/

struct NODE *np; /^Используется при просмотре.*/

/*3анять блок памяти для головы списка и иницилизировать его так, чтобы он показывал сам на себя.*/ root=malloc(sizeof(struct NODE) ) ;

root->pred= root->succ=root; root->data[0]='\0' ;

/^Создать связанный список имен.*/ for (;; )

{

printf («имя:»);

gets (name);

if (strcmp(name), «конец»)==0)

break; if (insert(root, name)==0)

{

printf («не хватает динамической памяти \п»); exit(1); } } /^Изобразить содержимое списка.*/

for (np=root->succ; np!=np->succ) printf («имя=%з \n», np->data);

printf («работа закончена \п»); }

/^Зарезервировать память для нового узла списка; скопировать в него имя и вставить новый узел в список в алфавитном порядке. Возвратить либо указатель на новый узел, либо NULL, если для создания узла не хватило памяти.*/

struct NODE *insert (node, name); struct NODE *node; /*Голова списка.*/ char *name;

{

NODE *np; /*Узел списка.*/ NODE *newnode;

/*Узел, вставленный в список.*/

/*Просматривать список, пока не обнаружится узел, поле info которого имеет значение, большее введенного имени или равное ему.*/

for (np=node->succe; (np!=node) &&

strcmp (name, np->data)>0); np=np->succe);

/^Зарезервировать память для нового узла; поместить введеное имя в его поле info и вставить новый узел перед тем, на который показывает указатель пр.*/

if( (newnode=malloc(sizeof(struct NODE)))!=0 ) {

strncpy(newnode->data, name, №\ME_SIZE);

newnode->succ=np;

newnode->pred=np->pred;

/^Изменить прямой указатель в узле, предшествующем вставленному (теперь он должен показывать на вставленный узел) и изменить обратный указатель в узле, следующем за вставленным.*/

(newnode->pred)->succ=newnode; np->pred=newnode; }

return (newnode); }