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; после упорядочения указатель v указывает на элемент K1' (см. рис.19)

Рис.19. Схема частичного упорядочения списка.

ND *v;

float k1;

k1=dl->val;

r=dl;

while( r->n!=NULL )

{ v=r->n;

if (v->valn=v->n;

v->n=dl;

dl=v;

}

else r=v;

}

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

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

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

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

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 в связанном хранении и возвращения указателя на его начало.</i

При решении задачи в каждый момент времени имеем упорядоченный список 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);

}