- •Предназначено студентам очной формы обучения.
- •Введение
- •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.2. Операции со списками при последовательном хранении
При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.
Пусть имеется линейный список с целыми значениями и для его хранения используется массив d (с числом элементов 100), а количество элементов в списке указывается переменной l. Реализация указанных ранее операций над списком представляется следующими фрагментами программ которые используют объявления:
float d[100],nov;
int i,j,l;
//1) печать значения i-го элемента (узла)
if (i<=0 || i>l) printf("\n нетэлемента");
else printf("d[%d]=%f ",i,d[i-1]);
//2) удаление элемента, следующего за i-тым узлом
if (i>=l) printf("Нет следующего элемента\n");
else
{
for (j=i; j<l; j++) d[j]=d[j+1];
l--;
}
//3) печать соседей i-того элемента списка
if (i<=1 || i>=l) printf("У элемента нет двух соседей\n");
else printf("\n %d %d",d[i-1],d[i+1]);
//4) добавление нового элемента nov за i-тым узлом
if (i>=l) printf("\n нельзядобавить");
else
{
for (j=l; j>i; j--) d[j]=d[j-1];
d[i]=nov; l++;
}
//5) частичное упорядочение списка с элементами К1,К2,...,Кl в список //K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l так, чтобы K1'= K1.
int t=1;
float aux;
for (i=1; i<l; i++)
{
if (d[i]==2, j--) d[j]=d[j-1];
t++;
d[i]=aux;
}
Схема движения индексов i,j,t и значения aux=d[i] при выполнении приведенного фрагмента программы приведена на рис.4.
Рис. 4. Движение индексов при выполнении операций над списком в последовательном хранении
Количество действий О, требуемых для выполнения приведенных операций над списком, определяется соотношениями: для операций 1) и 2) – О(1); для операций 3),4) – О(L); для операции 5) – O(L2).
Заметим, что вообще операцию 5) можно выполнить при количестве действий порядка O(L), а операции 3) и 4) для включения и исключения элементов в конце списка, часто встречающиеся при работе со стеками, - при количестве действий O(1).
Более сложная организация операций требуется при размещении в массиве d нескольких списков, или при размещении списка без привязки его начала к первому элементу массива.
2.3. Операции со списками при связном хранении
При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val – предназначен для хранения элемента списка, n – для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание:
typedef struct nd {
float val;
struct nd *n;
} ND;
int i,j;
ND *dl, *r, *p;
Для реализации операций могут использоваться следующие фрагменты программ:
//1) печать значения i-го элемента
r=dl;
int j;
for(j=0; j<i; j++, r=r->n) {
if( r == NULL) {
printf("i-го узла не существует\n");
return; //выход из функции
}
}
printf("%d-й элемент равен %f ", i, r->val);
//2) печать обоих соседей узла(элемента), определяемого указателем p (рис.5).
if((r=p->n)==NULL) printf("\n нет соседа справа");
else printf("\n соседсправа %f", r->val);
if(dl==p) printf("\n нет соседа слева");
else
{
r=dl;
while( r->n!=p) r=r->n;
printf("\n левыйсосед %f", r->val);
}
Рис. 5. Схема выбора соседних элементов
//3) удаление элемента, следующего за узлом, на который указывает р (рис.6).
if ((r=p->n)==NULL) printf("\n нетследующего");
p->n=r->n;
free(r);
Рис. 6. Схема удаления элемента из списка
//4) вставка нового узла со значением new за элементом, определенным указателем р (рис.7).
r=(ND*) malloc(sizeof(ND));
r->val=nov;
r->n=p->n;
p->n=r;
Рис. 7. Схема вставки элемента в список
/ /5) частичное упорядочение списка в последовательность значений <K1',..., KS', K1 , K1",..., KT", s+t+1=l, так что K1'< K1, Kj"= K1; после упорядочения указатель v указывает на элемент K1'(рис.8).
Рис. 8. Схема частичного упорядочения списка
Количество действий, требуемых для выполнения указанных операций над списком в связанном хранении, оценивается соотношениями: для операций 1) и 2) – O(L); для операций 3) и 4) – O(1); для операции 5) – O(L).