Программирование на языке С - Организация двусвязных списков

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

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

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

     typedef struct ndd
        { float val;      /* значение элемента                */
          struct ndd * n; /* указатель на следующий элемент   */
          struct ndd * m; /* указатель на предыдующий элемент */
          } NDD;
     NDD * dl, * p, * r;

Вставка нового узла со значением 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 - на последний элемент списка.

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

Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до 9999, и пусть Fi (1<9999) последовательность, получаемая упорядочиванием элементов списка по возрастанию. Составить процедуру для формирования 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);
      }