Самая полезная информация для любого, кто связан с программированием.

Линейный список – это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. Линейный список F, состоящий из элементов D1,D2,…,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=. Например, F1=<2,3,1>,F2=<7,7,7,2,1,12>, F3=<>. Длина списков F1, F2, F3 равна соответственно 3,6,0. [...]

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

При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val – предназначен для хранения элемента списка, n – для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание: typedef struct nd { float val; struct nd * [...]

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка). В программе двусвязный список можно реализовать с помощью описаний: typedef struct ndd { float val; /* значение элемента */ struct ndd * n; /* указатель на следующий [...]

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=, в котором для любого 1<=i<=n элемент K’(i) <=»K’(i+1).» При обменной сортировке упорядоченный список В’ получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют. Наиболее [...]

В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью. Стек – это конечная последовательность некоторых однотипных элементов – скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не [...]

Упорядоченный массив B’ получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,…,N выполняется вставка узла Кi в B’ так, что B’ остается упорядоченным списком длины i. Например, для начального списка B=<20,-5,10,8,7> имеем:             B=<20,-5,10,8,7>  B’=<>             B=<-5,10,8,7>    B’=<20>             B=<10,8,7>       B’=<-5,20>             B=<8,7>         B’=<-5,10,20>             B=<7>            B’=<-5,8,10,20>             B=<>              [...]

Упорядоченный список В’ получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В’, который первоначально должен быть пустым. Например:             B=<20,10,8,-5,7>, B’=<>             B=<20,10,8,7>,    B’=<-5>             B=<20,10,8>,      B’=<-5,7>             B=<20,10>,        B’=<-5,7,8>             B=<20>,           B’=<-5,7,8,10>             B=<>,            B’=<-5,7,8,10,20> . Функция select упорядочивает массив s [...]

При хранении больших объемов информации в форме линейных списков нежелательно хранить элементы с одинаковым значением, поэтому используют различные методы сжатия списков. Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а список B’= получается из B заменой каждого элемента Ki на пару Ki’=(i,Ki). Пусть далее B»= – подсписок B’, получающийся вычеркиванием всех [...]

Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17,19,23,25,38,39,47,60> из 9 элементов. Для слияния списков А и [...]