- •Описание языка программирования с
- •Элементы языка программирования с
- •Используемые символы
- •Константы
- •Идентификатор
- •Использование комментариев в тексте программы
- •Типы данных и их объявление
- •Категории типов данных
- •Целый тип данных
- •Данные плавающего типа
- •Указатели
- •Переменные перечислимого типа
- •Массивы
- •Структуры
- •Объединения (смеси)
- •Поля битов
- •Переменные с изменяемой структурой
- •Определение объектов и типов
- •Инициализация данных
- •Выражения и присваивания
- •Операнды и операции
- •Преобразования при вычислении выражений
- •Операции отрицания и дополнения
- •Операции разадресации и адреса
- •Операция sizeof
- •Мультипликативные операции
- •Аддитивные операции
- •Операции сдвига
- •Поразрядные операции
- •Логические операции
- •Операция последовательного вычисления
- •Условная операция
- •Операции увеличения и уменьшения
- •Простое присваивание
- •Составное присваивание
- •Приоритеты операций и порядок вычислений
- •Побочные эффекты операций присваивания
- •Преобразование типов
- •Операторы
- •Оператор выражение
- •Пустой оператор
- •Составной оператор
- •Оператор if
- •Оператор switch
- •Оператор break
- •Оператор for
- •Оператор while
- •Оператор do while
- •Оператор continue
- •Оператор return
- •Оператор goto
- •Определение функций
- •Определение и вызов функций
- •Вызов функции с переменным числом параметров
- •Объявление переменных
- •Исходные файлы и объявление переменных
- •Объявления функций
- •Время жизни и область видимости программных объектов
- •Инициализация глобальных и локальных переменных
- •Указатели
- •Методы доступа к элементам массивов
- •Указатели на многомерные массивы
- •Операции с указателями
- •Массивы указателей
- •Динамическое размещение массивов
- •Директивы препроцессора
- •Директива #include
- •Директива #define
- •Директива #undef
- •Организация списков и их обработка
- •Линейные списки
- •Методы организации и хранения линейных списков
- •Операции со списками при последовательном хранении
- •Операции со списками при связном хранении
- •Организация двусвязных списков
- •Стеки и очереди
- •Сжатое и индексное хранение линейных списков
- •Сортировка и слияние списков
- •Пузырьковая сортировка
- •Сортировка вставкой
- •Сортировка посредством выбора
- •Слияние списков
- •Сортировка списков путем слияния
- •Быстрая и распределяющая сортировки
- •Последовательный поиск
- •Бинарный поиск
- •М-блочный поиск
- •Методы вычисления адреса
- •Выбор в линейных списках
- •Рекурсия
Операции со списками при последовательном хранении
При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.
Пусть имеется линейный список с целыми значениями и для его хранения используется массив 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. { int t=1; float aux; for (i=2; i<=l; i++) if (d[i]=2; j--) d[j]=d[j-1]; t++; d[i]=aux; } }
Количество действий Q, требуемых для выполнения приведенных операций над списком, определяется соотношениями: для операций 1 и 2 - Q=1; для операций 3,4 - Q=l; для операции 5 - Q=l*l.
Заметим, что вообще операцию 5 можно выполнить при количестве действий порядка l, а операции 3 и 4 для включения и исключения элементов в конце списка, часто встречающиеся при работе со стеками, - при количестве действий 1.
Более сложная организация операций требуется при размещении в массиве d нескольких списков, или при размещении списка без привязки его начала к первому элементу массива.
Операции со списками при связном хранении
При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val - предназначен для хранения элемента списка, n - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание:
typedef struct nd { float val; struct nd * n; } ND; int i,j; ND * dl, * r, * p;
Для реализации операций могут использоваться следующие фрагменты программ:
1) печать значения i-го элемента
r=dl;j=1; while(r!=NULL && j++n ; if (r==NULL) printf("\n нет узла %d ",i); else printf("\n элемент %d равен %f ",i,r->val);
2) печать обоих соседей узла(элемента), определяемого указателем p
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); }
3) удаление элемента, следующего за узлом, на который указывает р
if ((r=p->n)==NULL) printf("\n нет следующего");
p->n=r->n; free(r->n);
4) вставка нового узла со значением new за элементом, определенным указателем р
r=malloc(1,sizeof(ND)); r->n=p->n; r->val=new; p->n=r;
5) частичное упорядочение списка в последовательность значений , s+t+1=l, так что K1'=K1; после упорядочения указатель v указывает на элемент K1'
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