- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
2.6. Сжатое и индексное хранение линейных списков
При хранении больших объемов информации в форме линейных списков нежелательно хранить элементы с одинаковым значением, поэтому используют различные методы сжатия списков.
Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а список B'=< K1 ', K2',..., Kn' получается из B заменой каждого элемента Ki на пару Ki'=(i, Ki). Пусть далее B"=< K1", K2",..., Km" > - подсписок B', получающийся вычеркиванием всех пар Ki=(i,V). Сжатым хранением В является метод хранения В", в котором элементы со значением V умалчиваются. Различают последовательное сжатое хранение и связанное сжатое хранение. Например, для списка B=, содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое хранения, с умалчиванием элементов со значением Х, представлены на рис.11,12.
Р ис. 11. Последовательное сжатое хранение списка
Рис. 12. Связное сжатое хранение списка
Достоинство сжатого хранения списка при большом числе элементов со значением V заключается в возможности уменьшения объема памяти для его хранения.
Поиск i-го элемента в связанном сжатом хранении осуществляется методом полного просмотра, при последовательном хранении – методом бинарного поиска.
Преимущества и недостатки последовательного сжатого и связанного сжатого хранений аналогичны преимуществам и недостаткам последовательного и связанного хранений.
Рассмотрим следующую задачу. На входе заданы две последовательности целых чисел M=< M1, M2,..., M10000>, N=<N1, N2,..., N10000>, причем 92% элементов последовательности М равны нулю. Составить программу для вычисления суммы sum= Mi * Ni.
Предположим, что список М хранится последовательно сжато в массиве структур m с объявлением:
struct {
int nm;
float val;
} m[10000];
Для определения конца списка добавим еще один элемент с порядковым номером m[j].nm=10001, который называется стоппером (stopper) и располагается за последним элементом сжатого хранения списка в массиве m.
Программа для нахождения искомой суммы имеет вид:
#include <STDIO.H>
#define MAX_I 10000
void main()
{
int i,j=0;
floatinp,sum=0;
struct{ /* объявление массива */
int nm; /* структур */
float val;
} m[MAX_I];
for(i=0; i< MAX_I; i++) /* чтениесписка M */
{
scanf("%f",&inp);
if (inp!=0)
{
m[j].nm=i;
m[j++].val=inp;
}
}
m[j].nm= MAX_I+1; /* stopper */
for(i=0,j=0; i< MAX_I; i++)
{
scanf("%f",&inp); /* чтение списка N */
if(i==m[j].nm) /* вычисление суммы */
sum+=m[j++].val*inp;
}
printf( "сумма произведений Mi*Ni равна %f",sum);
}
Индексное хранение используется для уменьшения времени поиска нужного элемента в списке и заключается в следующем. Исходный список B = < K1, K2 , ..., Kn>разбивается на несколько подсписков B1, B2 , ..., Bm таким образом, что каждый элемент списка В попадает только в один из подсписков, и дополнительно используется индексный список с М элементами, указывающими на начало списков B1, B2 , ..., Bm. Считается, что список хранится индексно с помощью подсписков B1, B2 , ..., Bm и индексного списка X = < ADG1, ADG2, ..., ADGm>, где ADGj - адрес начала подсписка Bj, j=1…m.
При индексном хранении элемент К подсписка Bj имеет индекс j. Для получения индексного хранения исходный список В часто преобразуется в список В' путем включения в каждый узел еще и его порядкового номера в исходном списке В, а в j-ый элемент индексного списка Х, кроме ADGj, может включаться некоторая дополнительная информация о подсписке Bj. Разбиение списка В на подсписки осуществляется так, чтобы все элементы В, обладающие определенным свойством Рj, попадали в один подсписок Bj.
Достоинством индексного хранения является то, что для нахождения элемента К с заданным свойством Рj достаточно просмотреть только элементы подсписка Bj; его начало находится по индексному списку Х, так как для любого КBi, при ij свойство Рj не выполняется.
В разбиении В часто используется индексная функция G(K), вычисляющая по элементу К его индекс j, т.е. G(K)=j. Функция G обычно зависит от позиции К, обозначаемой поз.K, в подсписке В или от значения определенной части компоненты К - ее ключа.
Рассмотрим список B=< K1, K2 , ..., K9> с элементами К1=(17,Y), K2=(23,H), K3=(60,I), K4=(90,S), K5=(66,T), K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).
Если для разбиения этого списка на подсписки в качестве индексной функции взять Ga (K)=1+(поз.K-1)/3, то список разделится на три подсписка:
B1a=<(17,Y),(23,H),(60,I)>,.
B2a=<(90,S),(66,T),(77,T)>,.
B3a=<(50,U),(88,W),(30,S)>.
Добавляя всюду еще и начальную позицию элемента в списке, получаем:
B1a'=<(1,17,Y),(2,23,H),(3,60,I)>,о
B2a'=<(4,90,S),(5,66,T),(6,77,T)>,о
B3a'=<(7,50,U),(8,88,W),(9,30,S)>.
Если в качестве индексной функции выбрать другую функцию Gb (K)=1+(поз.K-1)%3, то получим списки:
B1b"=<(1,17,Y),(4,90,S),(7,50,U)>,
B2b"=<(2,23,H),(5,66,T),(8,88,U)>,
B3b"=<(3,60,I),(6,77,T),(9,30,S)>.ь
Теперь для нахождения узла K6 достаточно просмотреть только одну из трех последовательностей (списков). При использовании функции Ga (K) это список B2a', а при функции Gb (K) список B3b".
Для индексной функции Gc (K)=1+ K1’ /100, где K1’ - первая компонента элемента К, находим:
B1 =<(17,Y),(23,H),(60,I),(90,S)>,
B2 =<(66,T),(77,T)>,
B3 =<(50,U),(88,W)>,
B4 =<(30,S)>.
Чтобы найти здесь узел К с первым компонентом-ключом K1’ =77, достаточно просмотреть список B2.
При реализации индексного хранения применяется методика А для хранения индексного списка Х (функция Ga (X) ) и методика C для хранения подсписков B1, B2 ,..., Bm(функция Gc (Bi)), т.е. используется, так называемое, A-C индексное хранение.
На практике часто используется последовательно-связанное индексное хранение. Так как обычно длина списка индексов известна, то его удобно хранить последовательно, обеспечивая прямой доступ к любому элементу списка индексов. Подсписки B1, B2 ,..., Bm хранятся связанно, что упрощает вставку и удаление узлов(элементов). В частности, подобный метод хранения используется в ЕС ЭВМ для организации, так называемых, индексно-последовательных наборов данных, в которых доступ к отдельным записям возможен как последовательно, так и при помощи ключа.
П оследовательно-связанное индексное хранение для приведенного примера изображено на рис.13, где X = < ADG1, ADG2, ADG3, ADG4>
Рис. 13. Последовательно-связанное индексное хранение списка
Рассмотрим еще одну задачу. На входе задана последовательность целых положительных чисел, заканчивающаяся нулем. Составить функцию для ввода этой последовательности и организации ее последовательно-связанного индексного хранения таким образом, чтобы числа, совпадающие в двух последних цифрах, помещались в один подсписок.
Выберем в качестве индексной функции G(K)=K%100+1, а в качестве индексного списка Х – массив из 100 элементов. Следующая функция решает поставленную задачу:
#include<STDIO.H>
#include<STDLIB.H>
#include <MATH.H>
typedef struct nd {
float val;
struct nd *n;
} ND;
int index (ND *x[100])
{
ND *p;
int i,j=0;
float inp;
for (i=0; i<100; i++) x[i]=NULL;
scanf("%f",&inp);
while (inp!=0)
{
j++;
p=(ND*)malloc(sizeof(ND));
i=fmod(inp,100);
p->val=inp;
p->n=x[i];
x[i]=p;
scanf("%d",&inp);
}
return j; //общее количество элементов в списках
}
Возвращаемым значением функции index будет число обработанных элементов списка.
Для индексного списка также может использоваться индексное хранение. Пусть, например, имеется список B=<K1, K2, …, K10> с элементами K1=(338,Z), K2=(145,A), K3=(136,H), K4=(214,I), K5=(146,C), K6=(334,Y), K7=(333,P), K8=(127,G), K9=(310,O), K10=(322,X).
Требуется разделить его на семь подсписков, т.е. X=<X1, X2, …, X7> таким образом, чтобы в каждый список B1, B2 ,..., B7 попадали элементы, совпадающие в первой компоненте первыми двумя цифрами. Список Х, в свою очередь, будем индексировать списком индексов Y=<Y1, Y2, Y3>, чтобы в каждый список Y1, Y2 , Y3 попадали элементы из X, у которых в первой компоненте совпадают первые цифры. Если списки B1, B2 ,..., B7 хранить связанно, а списки индексов X, Y индексно, то такой способ хранения списка B называется связанно-связанным связанным индексным хранением. Графическое изображение этого хранения приведено на рис.14.
Рис. 14. Связанно-индексное хранение списка
Задания для самоконтроля
1. Линейный список F из M целых чисел, большинство элементов которого равно нулю, хранится связанно сжато. Написать функцию для нахождения i-го элемента списка.
2. Линейный список F целых чисел хранится последовательно-связанно индексно, так что числа, совпадающие в последней цифре, помещаются в один подсписок. Написать функцию определения: имеется ли в списке элемент со значением V.
3. На входе задана последовательность целых положительных чисел, оканчивающихся нулем. Написать фрагмент программы для ввода чисел и организации их последовательно-связанного индексного хранения. При этом числа, у которых первая и третья цифры совпадают, соответственно должны помещаться в один список.
4. На входе заданна последовательность n троек (Xi, Yi, Pi), где Xi-немецкое слово; Yi- его английский эквивалент и Pi – частота использования (в %) слова Xi в «типичном немецком тексте». Последовательность пар (Xi, Yi), интерпретируемая как линейный список, хранится последовательно-связанно индексно. Элементы, совпадающие по первой букве немецкого слова, помещаются в один связанный список, где упорядочены по убыванию частоты использования (чтобы быстрее находить чаще используемые слова). Написать программу формирования этой структуры данных и осуществления пословной трансляции немецкого предложения из М слов. Если для конкретного немецкого слова нет перевода, то оставлять его не переведенным.