Организация двусвязных списков

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).

В программе двусвязный список можно реализовать с помощью описаний:

     typedef struct ndd

        { float val;      /* значение элемента                */

          struct ndd * n; /* указатель на следующий элемент   */

          struct ndd * m; /* указатель на предыдующий элемент */

          } NDD;

     NDD * dl, * p, * r;

Графическая интерпретация метода связанного хранения списка F=< 2,5,7,1 > как списка с двумя связями приведена на рис.20.

 

Рис.20. Схема хранения двусвязного списка.

 

Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:

          r=malloc(NDD);

          r->val=new;

          r->n=p->n;

          (p->n)->m=r;

          p->=r;

Удаление элемента, следующего за узлом, на который указывает p

          p->n=r;

          p->n=(p->n)->n;

          ( (p->n)->n )->m=p;

          free(r);

Связанное хранение линейного списка называется циклическим списком, если его последний указывает на первый элемент, а указатель dl - на последний элемент списка.

Схема циклического хранение списка F=< 2,5,7,1 > приведена на рис.21.

 

Рис.21. Схема циклического хранения списка.

 

При решении конкретных задач могут возникать разные виды связанного хранения.

Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до 9999, и пусть Fi (1<I по возрастанию. Составить процедуру для формирования Fn в связанном хранении и возвращения указателя на его начало.

При решении задачи в каждый момент времени имеем упорядоченный список Fi и при вводе элемента Bi+1 вставляем его в нужное место списка Fi, получая упорядоченный список Fi+1. Здесь возможны три варианта: в списке нет элементов; число вставляется в начало списка; число вставляется в конец списка. Чтобы унифицировать все возможные варианты, начальный список организуем как связанный список из двух элементов <0,1000>.

Рассмотрим программу решения поставленной задачи, в которой указатели dl, r, p, v имеют следующее значение: dl указывает начало списка; p, v - два соседних узла; r фиксирует узел, содержащий очередное введенное значение in.

     #include

     #include

     typedef struct str1

       { float val;

         struct str1 *n; }  ND;

     main()

      {  ND *arrange(void);

         ND *p;

         p=arrange();

         while(p!=NULL)

           {

            printf("\n %f ",p->val);

            p=p->n;

           }

      }

     ND *arrange() /*   формирование упорядоченного списка */

      {  ND *dl, *r, *p, *v;

         float in=1;

         char *is;

         dl=malloc(sizeof(ND));

         dl->val=0;                  /*  первый элемент     */

         dl->n=r=malloc(sizeof(ND));

         r->val=10000; r->n=NULL;    /*  последний элемент  */

         while(1)

         {

            scanf(" %s",is);

            if(* is=='q') break;

            in=atof(is);

            r=malloc(sizeof(ND));

            r->val=in;

            p=dl;

            v=p->n;

            while(v->valn;

            }

            r->n=v;

            p->n=r;

        }

        return(dl);

      }

Оглавление.