- •Оглавление
- •Введение
- •Основные понятия и определения
- •Встроенные структуры данных(Pascal/с)
- •Варианты индивидуальных заданий на Pascal
- •Варианты индивидуальных заданий на c
- •Простые типы данных в Pascal
- •Вещественные типы
- •Вещественные типы языка Pascal
- •Сложный тип
- •Простые типы данных в с Целые типы
- •Целые типы языка c
- •Диапазоны значений целых типов языка c
- •Символьный тип
- •Перечисляемый тип
- •Вещественные типы
- •Вещественные типы языка c
- •Структурированные типы данных в Pascal Массив
- •Структура данных типа «запись»
- •Структура данных типа «множество»
- •Структурированные типы данных в c Структура данных типа «массив»
- •Структура данных типа «структура»
- •Производные структуры данных. Структура данных «строка» (Pascal/c)
- •Задание
- •Варианты индивидуальных заданий
- •Варианты задач
- •Варианты форматов
- •Назначение процедур и функций в модулях реализации сд типа строка в Pascal
- •Назначение процедур и функций в модулях реализации сд типа «строка» в c
- •Сравнительный анализ методов сортировки (Pascal/c)
- •1. Изучить временные характеристики алгоритмов.
- •6. Выводы по работе.
- •1. Выбираем элемент массива в качестве разделителя (например, первый).
- •Массив м
- •Массив м
- •Примеры программной реализации алгоритмов сортировки на языке Pascal
- •Примеры программной реализации алгоритмов сортировки на языке c
- •Сравнительный анализ алгоритмов поиска (Pascal/c)
- •Максимальное количество операций сравнения
- •Среднее количество операций сравнения
- •Алгоритмы поиска в неупорядоченных массивах Алгоритм линейного поиска
- •Алгоритм быстрого линейного поиска
- •Анализ алгоритмов линейного поиска
- •Алгоритмы поиска в упорядоченных массивах Алгоритм быстрого линейного поиска
- •Алгоритм бинарного поиска
- •Анализ алгоритма бинарного поиска
- •Алгоритм блочного поиска
- •Анализ алгоритма блочного поиска
- •Структуры данных «линейные списки» (Pascal/с)
- •Варианты индивидуальных заданий
- •Назначение процедур и функций
- •Структуры данных «стек» и «очередь» (Pascal/с)
- •Результаты работы программы
- •Варианты индивидуальных заданий
- •Варианты задач
- •Модули для реализации стека
- •Модули для реализации очереди
- •Очередь
- •Структуры данных «дерево» (Pascal/с)
- •Варианты индивидуальных заданий
- •Варианты задач
- •Назначение процедур и функций:
- •Принципы размещения бинарного дерева в памяти эвм
- •Алгоритмы обхода бинарного дерева
- •Обход бинарного дерева «в глубину» (в прямом порядке)
- •Обход бинарного дерева «в ширину» (по уровням)
- •Обход бинарного дерева в симметричном порядке
- •Обход бинарного дерева в обратном порядке
- •Алгоритмы формирования бинарного дерева
- •Рекурсивный алгоритм формирования бинарного дерева «в глубину»
- •Итеративный алгоритм формирования бинарного дерева «в глубину»
- •Алгоритм формирования бинарного дерева «в ширину»
- •Алгоритм формирования бинарного дерева «снизу вверх»
- •Рекурсивный алгоритм формирования бинарного дерева
- •Итеративный алгоритм формирования бинарного дерева
- •Алгоритм формирования бинарного дерева минимальной высоты
- •Итеративный алгоритм формирования сбалансированного бинарного дерева
- •Представление алгебраических выражений бинарными деревьями
- •Алгоритм формирования бинарного дерева по прямой польской записи
- •Алгоритм формирования бинарного дерева по обратной польской записи
- •Структуры данных «таблица» (Pascal/с)
- •Варианты индивидуальных заданий
- •Библиографический список
Варианты форматов
Формат 1
Спецификация СД на языке Pascal:
Unit form1;
Interface
Const {определение исключительных ситуаций}
Type string1=array[1..256] of char;
{признак конца строки–символ с кодом 0}
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:Word);
Procedure Insert(Subs:String1;var S:String1;Index:Word);
Procedure Concat( const S1, S2:string1;var srez: string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM1_H)
#define __FORM1_H
const ...; // Определение исключительных ситуаций
typedef char string1[256];
// Признак конца строки - символ '\0'
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 s);
void OutputStr(string1 s);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
int StrError; // Переменная ошибок
//...
#endif
Формат 2
Спецификация СД на языке Pascal:
Unit form2;
Interface
Const {определение исключительных ситуаций}
Type
str=array[1..65520] of char; {признак конца строки – символ с кодом 0}
p_str=^str;
string1=record
st:p_str;
n:word {количество символов в строке, определяется при инициализации}
end;
Procedure InitStr(var st:string1; n:word);
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:Word);
Procedure Insert(Subs:String1;var S:String1;Index:Word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM2_H)
#define __FORM2_H
const ...; // Определение исключительных ситуаций
typedef struct str
{
char* s; // Признак конца строки - символ '\0'
unsigned max; /* Максимальное количество символов в строке, определяющееся при инициализации */
};
typedef str *string1;
void InitStr(string1 st, unsigned n);
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
void DoneStr(string1 s)
int StrError; // Переменная ошибок
//...
#endif
Формат 3
Спецификация СД на языке Pascal:
Unit form3;
Interface
Const {определение исключительных ситуаций}
Type string1=array[-1..1024] of char;
{первые два байта содержат динамическую длину строки}
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:Word);
Procedure Insert(Subs:String1;var S:String1;Index:Word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM3_H)
#define __FORM3_H
const ...; // Определение исключительных ситуаций
typedef char string1[1024]; /* Первые два байта содержат динамическую длину строки */
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
int StrError; // Переменная ошибок
//...
#endif
Формат 4
Спецификация СД на языке Pascal:
Unit form4;
Interface
Const {определение исключительных ситуаций}
Type string1=record
St:array[1..1024] of char;
N:word{динамическая длина строки}
End;
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:word);
Procedure Insert(Subs:String1;var S:String1;Index:word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM4_H)
#define __FORM4_H
const ...; // Определение исключительных ситуаций
typedef struct str
{
char s[1024];
unsigned N; // Динамическая длина строки
};
typedef str *string1;
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count,string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
int StrError; // Переменная ошибок
//...
#endif
Формат 5
Спецификация СД на языке Pascal:
Unit form5;
Interface
Const {определение исключительных ситуаций}
Type St=array[1..65520] of char;
String1=record
p_st:^st;{указатель на строку}
max:word;{максимальное количество символов в строке, определяется при инициализации}
N:word {динамическая длина строки}
End;
Procedure InitStr(var st:string1; n:word);
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:word);
Procedure Insert(Subs:String1;var S:String1;Index:word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM5_H)
#define __FORM5_H
const ...; // Определение исключительных ситуаций
typedef struct str
{
char *s; // Указатель на строку
unsigned max; /* Максимальное количество символов в строке, определяющееся при инициализации*/
unsigned N; // Динамическая (текущая) длина строки
};
typedef str *string1;
void InitStr(string1 st, unsigned n);
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
void DoneStr(string1 s)
int StrError; // Переменная ошибок
//...
#endif
Формат 6
Спецификация СД на языке Pascal:
Unit form6;
Interface
Const {определение исключительных ситуаций}
Type St=array[1..65520] of char; {первые два байта содержат максимальную длину строки, которая определяется при инициализации}
String1=record
p_st:^st;{указатель на строку}
N:word {динамическая длина строки}
End;
Procedure InitStr(var st:string1; n:word);
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:word);
Procedure Insert(Subs:String1;var S:String1;Index:word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM6_H)
#define __FORM6_H
const ...; // Определение исключительных ситуаций
typedef struct str
{
char *s; /* Указатель на строку. Первые два байта строки s содержат максимальную длину строки, которая определяется при инициализации */
unsigned N; // Динамическая (текущая) длина строки
};
typedef str *string1;
void InitStr(string1 st, unsigned n);
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count,string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
void DoneStr(string1 s);
int StrError; // Переменная ошибок //...
#endif
Формат 7
Спецификация СД на языке Pascal:
Unit form7;
Interface
Const {определение исключительных ситуаций}
Type St=array[1..65520] of char;
{первые два байта содержат динамическую длину строки}
String1=record
p_st:^st;{указатель на строку}
max:word {максимальная длина строки, определяется при инициализации}
End;
Procedure InitStr(var st:string1; n:word);
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:word);
Procedure Insert(Subs:String1;var S:String1;Index:word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM7_H)
#define __FORM7_H
const ...; // Определение исключительных ситуаций
typedef struct str
{
char *s; /* Указатель на строку. Первые два байта строки s содержат динамическую длину строки */
unsigned max; /* Максимальное количество символов в строке, определяющееся при инициализации */
};
typedef str *string1;
void InitStr(string1 st, unsigned n);
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count,string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
void DoneStr(string1 s);
int StrError; // Переменная ошибок//...
#endif
Формат 8
Спецификация СД на языке Pascal:
Unit form8;
Interface
Const {определение исключительных ситуаций}
Type St=array[1..65520] of char; {первые два байта содержат максимальную длину строки, которая определяется при инициализации; признак конца строки – символ с кодом 0}
String1=^st; {указатель на строку}
Procedure InitStr(var st:string1; n: word);
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:word);
Procedure Insert(Subs:String1;var S:String1;Index:word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM8_H)
#define __FORM8_H
const ...; // Определение исключительных ситуаций
typedef char *string1;
/* Первые два байта содержат максимальную длину строки, которая определяется при инициализации. Признак конца строки - символ '\0' */
void InitStr(string1 *st, unsigned n);
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count,string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
void DoneStr(string1 s);
int StrError; // Переменная ошибок //...
#endif
Формат 9
Спецификация СД на языке Pascal:
Unit form9;
Interface
Const {определение исключительных ситуаций}
Type St=array[1..65520] of char;
{первые два байта содержат максимальную длину строки, которая определяется при инициализации; вторые два байта содержат динамическую длину строки}
String1=^st;{указатель на строку}
Procedure InitStr(var st:string1; n:word);
Procedure WriteToStr(var st:string1;s:string);
Procedure WriteFromStr(var s:string;st:string1);
Procedure InputStr(var st:string1);
Procedure OutputStr(const st:string1);
Function Comp(s1,s2:string1;var fl:shortint):boolean;
Procedure Delete(var S:String1;Index,Count:word);
Procedure Insert(Subs:String1;var S:String1;Index:word);
Procedure Concat( const S1, S2:string1;var srez:string1);
Procedure Copy(S:String1;Index,Count:Word; var Subs:string1);
Function Length(S: String1): word;
Function Pos(SubS, S: String1): word.
Function Pos(SubS, S: String1): word;
Var StrError: {тип переменной ошибки}
Спецификация СД на языке C:
#if !defined(__FORM9_H)
#define __FORM9_H
const ...; // Определение исключительных ситуаций
typedef char *string1;
/* Первые два байта содержат максимальную длину строки, которая определяется при инициализации. Вторые два байта содержат динамическую длину строки */
void InitStr(string1 *st, unsigned n);
void WriteToStr(string1 st, char *s);
void WriteFromStr(char *s, string1 st);
void InputStr(string1 st);
void OutputStr(string1 st);
int Comp(string1 s1, string1 s2);
void Delete(string1 s, unsigned Index, unsigned Count);
void Insert(string1 Subs, string1 s, unsigned Index);
void Concat(string1 s1, string1 s2, string1 srez);
void Copy(string1 s, unsigned Index, unsigned Count, string1 Subs);
unsigned Length(string1 s);
unsigned Pos(string1 SubS, string1 s);
void DoneStr(string1 s);
int StrError; // Переменная ошибок
//...
#endif