2020-01-15
109
Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).
В программе двусвязный список можно реализовать с помощью описаний:
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); }Стеки и очереди
|
|
|
В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью.
Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >.
Допустимыми операциями над стеком являются:
- проверка стека на пустоту S=< >,
- добавление нового элемента Sn+1 в конец стека - преобразование < S1,...,Sn> в < S1,...,Sn+1>;
- изъятие последнего элемента из стека - преобразование < S1,...,Sn-1,Sn> в < S1,...,Sn-1>;
- доступ к его последнему элементу Sn, если стек не пуст.
Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху.
Очередь - это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине).
Двусторонняя очередь - это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов.
Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами.
Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.
Например, выражение
(6+8)*5-6/2в польской инверсной записи имеет вид
6 8 + 5 * 6 2 / -Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид
S = < >; <6>; <6,8>; <14>; <14,5>; <70>; <70,6>; <70,6,2>; <70,3>; <67>.Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 - операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l.
float eval (float *m, int l) { int p,n,i; float stack[50],c; for(i=0; i < l;i++) if ((n=m[i])<0) { c=st[p--]; switch(n) { case -1: stack[p]+=c; break; case -2: stack[p]-=c; break; case -3: stack[p]*=c; break; case -4: stack[p]/=c; } } else stack[++p]=n; return(stack[p]); }Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1." то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.
|
|
|
