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

 

2.1.2. Операции со списками при последовательном хранении

При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.

Пусть имеется линейный список с целыми значениями и для его хранения используется массив d (с числом элементов 100), а количество элементов в списке указывается переменной l. Реализация указанных ранее операций над списком представляется следующими фрагментами программ которые используют объявления:

          float d[100];
          int i,j,l;
     1) печать значения первого элемента (узла)
        if (i<0 || i>l) printf("\n нет элемента");
        else printf("d[%d]=%f ",i,d[i]);
     2) удаление элемента, следующего за i-тым  узлом
        if (i>=l) printf("\n нет следующего ");
        l--;
        for (j=i+1;j<="1" || i>=l) printf("\n нет соседа");
        else printf("\n %d  %d",d[i-1],d[i+1]);
     4) добавление нового элемента new за i-тым узлом
        if (i==l || i>l) printf("\n нельзя добавить");
        else
        {    for (j=l; j>i+1; j--) d[j+1]=d[j];
             d[i+1]=new; l++;
        }
     5) частичное упорядочение списка с элементами  К1,К2,...,Кl  в
     список K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l так, чтобы K1'= K1.

     { int t=1;
       float aux;
       for (i=2; i<=l; i++) if (d[i]=2; j--) d[j]=d[j-1];
               t++;
               d[i]=aux;
            }
     }

Количество действий Q, требуемых для выполнения приведенных операций над списком, определяется соотношениями: для операций 1 и 2 - Q=1; для операций 3,4 - Q=l; для операции 5 - Q=l*l.

Заметим, что вообще операцию 5 можно выполнить при количестве действий порядка l, а операции 3 и 4 для включения и исключения элементов в конце списка, часто встречающиеся при работе со стеками, - при количестве действий 1.

Более сложная организация операций требуется при размещении в массиве d нескольких списков, или при размещении списка без привязки его начала к первому элементу массива.