Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Записи(тип Record).Поля записи.





Записи(тип Record).Поля записи.

Объединение элементов произвольных типов называется записью. Элементы записи называется её полями. Запись-это неоднородная структура данных, доступ к элементам записи произвольный. Также как у массива, характер внесения данных в запись является разрушающим.

Записи более универсальны, чем массивы, т.к. элементы могут иметь разные типы. В то же время массивы являются более гибкими структурами данных, т.к. значения индекса можно вычислять.

Описание записей имеет вид:

Type<имя>=record;

<список полей>:<тип 1>;

<-//->:<тип n>;

[<вариантная часть>]

End;

Список полей - последовательное описание полей записи, разделённых запятой. Поле записи может быть записью. Можно создавать массивы из записи.

Допускается record определять с помощью var.

Var student : record;

Name:string[20];

Group:byte;

Marks:array[1..4] of byte;

End;

Доступ к полям записи. Оператор With.

Доступ к полям записи осуществляется через полное имя поля, которое образуется с помощью:

<имя_записи>.<имя_поля>

Другим способом доступа осуществляется с помощью оператора With:

With student do

Begin

Writeln(name);

For i:=1 to 4 do read(marks[i]);

End;

Можно сказать, что оператор with сделал запись student текущей, и в операции с полями можно указывать только собственно имена полей.

Формой оператора withимеет вид:

With<имя записи> do <оператор>;

<оператор> - произвольный оператор ТР, в том числе составной. Инициализация записи может производиться в разделе констант. Для каждого поля задаётся его имя, после которого через двоеточие указываются значения:

Const s1 : studrec = (name : ’Петров’ , group: ’2’ ,marks : (4,3,5,5));

Вложенные записи:

Определение: Если элементам записи является запись, то это называется вложенной записью.



Rec 1

Pole1 rec 2

Pole A pole B

Поля записи могут хранить информацию-pole 1,pole A, pole B.

И поле как элемент записи(rec 2).

Уникальность имён полей записи.Примеры.

1)В рамках одной записи имена записи должны быть различны

2)В различных записях, в том числе во вложенных имена полей могут совпадать.

3)Допускается, чтобы имя записи и имя поля совпадали.

Массивы в структуре записи:

1)массив может быть элементом записи

2)На промежуточном уровне записи может располагаться массив.

rec

S t[1..2]

U V

Type trec=record;

U:integer;

V:real;

T_array=array[1..2] of trec;

Trec=record

S:integer;

T:tarray;

End;

Var; rec:trec;

Запись как единый объект операций.

Если записи совпадают по типу, то допускается применение операции присваивания между такими записями.

Вариантные записи.

Одно из полей записи может быть вариантной записью.

Вариантная часть записи – изменяемая часть. Все варианты этой части располагаются в памяти на одном и том же месте в конце записи.

Var zap: record

P1,p2: integer;

P3:real;

Case k:integer of

1: (v1:string[20]);

2: (v2:real; v3:array[1..10] of integer);

3: (v4: string[10])

End;

Вариантная часть начинается словом case, но это не оператор варианта, так как такая часть стоит последней в записи, то закрывающий case end не нужен.

Константы – любые порядковые значения, выбор производится не по ним а по именам полей.

Компилятор под вариантную часть выделяет память, достаточную для самого протяженного из вариантов.

Контроля за размещением вариантов нет, одна вариантная часть может быть вложена в другую.

Допускается пустой вариант:

Type rec1=record

A:byte;

B:integer;

End;

Rec2=record

C:shortint;

Case x:byte of

1: (d:word);

2: (e:record

Case Boolean of

3: (f:rec1);

3: (g:real);

‘3’: (c:integer)

end)

end;

Указание имени селектора не является обязательным, обязателен лишь тип.

Константы выбора могут повторяться, их тип необязательно будет совпадать с типом селектора.

Обращение к полям вариантной части производится не через выбор а по полному имени поля.

Множества в ТП. Описание Типа. Задание значений множественных переменных.

Перечислимый тип.

Удобна возможность введения нестандартных типов, например перечислимый. Формат описания типа имеет вид:

Type <идентификатор>=(<список значений через запятую>);

Замечание: элементами списка могут быть только идентификаторы. Нумерация элементов перечислимого типа начинается снуля.

1)Повторяющиеся элементы недопустимы

2)Переменной перечислимого типа можно назначать любое значение в пределах типа.

3)Нет представления ввода-вывода переменных перечислимого типа

4)Допускается использование операции сравнения для переменных перечислимого типа.

Ограниченный тип.

Описание:

Type<идентификатор> = (<начальное значение>..<конечное значение>)

Начальное и конечное значения могут быть целого или символьного типа, при этом начальное значение <= конечное значение.

Замечание: при преобразовании типа возможен выход за границы типа, {$R+} – сигнал для компилятора, так называемая директива (проверяет выход за границу).

Функция sizeof(x), возвращающая размер памяти в байтах, которую занимает переменная Х, может быть именем типа.

Writeln(sizeof(byte))

Замечание: функция sizeof может использоваться для структурированных типов.

Множества(set).

Структура описания:

Type <идентификатор>=set of <тип элементов>, тип элементов –порядковый, удовлетворяющий ограничению число элементов не более 256 (0..255)

Type letter=set of ‘A’..’Z’;

Type seol=set of (Red,Green);

Type all=set of char;

Замечание: в отличие от массива, множество-неупорядочно, сами элементы множества в памяти не записываются, там хранится только информация об их наличии или отсуствии

Var colset:scol;

Colset:=[Red];

Множество может быть задано в виде списка элементов в квадратных скобках.

[ ]-пустое множество.

Var A:All Let;

A:[‘a’ .. ’c’ , ’A’ .. ‘Z’];

Замечание: в качестве элементов списка в квадратных скобках можно использовать выражение, допустимый тип.

Если начальное и конечное значения диапазона образуют ошибку задания типа.

Операции с множеством

1)объединение множеств(+)

2)пересечение(*)

3)Разность(-)

4)Проверка принадлежности элемента множеству(“in”)

5)Отношения(<>, =, <=, >=)

Пример 1 операции:

А+В, в котором будут находиться все элементы А и В, но если есть повторяющиеся, то они пишутся один раз

Пример 2 операции:

А*В , то есть которые повторяются и в А и в В

Пример 3:

А-В

Пример 4:

А in S

Выраж. Множество

Результат-логическое значение.

А - может быть выражение базового типа(Red in Colset) или Red in [Red, Green]=true 8+1 in [1..12]=true

Type chs=set of char;

Var chs 1,chs 2,chs 3,:chs;

Chs 1:=[‘a’ , ‘x’ , ‘e’];

Chs 2:=[‘c’ , ‘x’];

Chs 3:=chs 1 + chs 2;{‘a’ , ‘x’ , ‘e’ , ‘c’};

Chs 3:=chs 1*chs 2;{‘x’};

Chs 3:=chs 1*[‘o’ , ‘n’];{[]};

Chs 3:=chs 1-chs 2; {‘a’ , ‘e’};

Пример использования множества .

Множества можно использовать вместо case или наборов операторов if.

Var sp:set of char;

DZ:char;

……………………..

Sp:=[‘A’ , ‘B’ , ‘C’ , ‘D’ , ‘a’ , ‘b’ , ‘c’ , ‘d’];

Repeat writeln(‘введите допустимое значение’);

Readln(DZ);

Until DZ in sp;

Типизированные файлы. Организация “прямого доступа” к элементам файла.

В типиз. файле все элементы имеют одну и ту же длину, т.е. занимают одинаковый объем в памяти.

В файле существуют указатель, который после операции с элементами перемещается на следующий элемент.

В типиз. файле все элементы можно пронумеровать и выбрать по номеру. Нумерация элементов в файле начинается с 0. Для перемещения указателя файла в нужную позицию можно использовать стандартную процедуру seek(f,N-1)

Для больших объемов данных типиз. файлы эффективнее текстовых – с помощью процедуры seek можно использовать прямой доступ к элементам файла.

 

 

Указатели

Для уяснения понятия указателя необходимо рассмотреть структуру и использование оперативной памяти компьютера в операционной системе MS DOS (основные принципы распределения памяти справедливы и для Windows):

 

 


Области самых младших и самых старших адресов занимают системные ресурсы, обеспечивающие функционирование операционной системы.
Сразу за системной областью младших адресов располагается исполняемый код прикладной программы.
Сегмент данных содержит ячейки для хранения значений глобальных констант и переменных.
Стек представляет собой буфер для временного хранения промежуточных (локальных) переменных и констант.
Перечисленные фрагменты ОЗУ составляют так называемую статическую память, которая заполняется сразу при запуске программы и не освобождается до ее завершения.
Следующий участок ОЗУ (по ходу возрастания адресов) представляет собой динамическую память, или кучу. Ячейки кучи могут неоднократно выделяться и освобождаться по мере необходимости во время выполнения программы, т.е. динамически.
В Паскале все константы и переменные, объявленные в разделе const и var основной программы или модуля, располагаются в сегменте данных, т.е. статической памяти. Размер сегмента данных и стека составляет соответственно 64 К и 16 К, что сильно ограничивает разработку программ, оперирующих большими массивами переменных емкого типа. Кардинальным решением этой проблемы является использование указателей и соответствующих средств доступа к динамической памяти.
Указатель, или ссылка – это переменная, значением которой является физический адрес некоторой ячейки памяти (чаще всего динамической).
Адрес каждой ячейки памяти ПК занимает 4 байта, или два машинных слова. Первое слово задает смещение адреса относительно начала сегмента, а второе – абсолютный адрес сегмента. Сегмент – это участок памяти, имеющий длину 64К и начинающийся с физического адреса, кратного 16 (0, 16, 32, 48 и т.д.). Смещение показывает, сколько байтов от начала сегмента нужно пропустить, чтобы достичь нужного адреса. Обычно слова адреса записываются в шестнадцатиричной системе через двоеточие, например:
F3A1 : 128D
смещение сегмент

Фрагмент памяти в 16 байтов называется параграфом, поэтому сегмент адресует память с точностью до параграфа, а смещение – с точностью до байта. Поскольку большинство типов данных занимают несколько смежных байтов, то указатель содержит адрес первого байта ячейки памяти, при этом сам указатель занимает 4 байта (два слова).

Указатели в Паскале бывают двух типов:

- типизированный указатель (ссылка), который адресует ячейку для данных определенного типа;

- нетипизированный указатель (стандартный тип Pointer), который ссылается на начало области памяти для данных неопределенного, или произвольного типа. Другими словами, нетипизированный указатель содержит просто адрес некоторой ячейки памяти.

 

 

Операции над указателями

Над указателями определено 5 основных операций.

§ Определение адреса указателя: &p, где p – указатель (&p – адрес ячейки, в которой находится указатель).

§ Присваивание. Указателю можно присвоить адрес переменной p=&q, где p – указатель, q – идентификатор переменной.

§ Определение значения, на которое ссылается указатель: *p (операция косвенной адресации).

§ Увеличение (уменьшение) указателя. Увеличение выполняется как с помощью операции сложения (+), так и с помощью операции инкремента (++). Уменьшение – с помощью операции вычитания (–) либо декремента (––).

Например, пусть p1 – указатель, тогда р1++ перемещает указатель на:

o 1 байт, если *p1 имеет тип char;

o 4 байта, если *p1 имеет тип int (в 32 разрядной операционной системе) или 2 байта (в 16 разрядной операционной системе);

o 4 байта, если *p1 имеет тип float.

§ Разность двух указателей. Пусть р1 и р2 – указатели одного и того же типа. Можно определить разность р1 и р2, чтобы найти, на каком расстоянии друг от друга находятся элементы массива.

Пример программы.

Даны адреса переменных &a=63384,&b=64390,&c=64404. Что напечатает ЭВМ?

#include<stdio.h>

intmain()

{

floata,*p1;

intb,*p2;

charc,*p3;

a=2.5;b=3;c='A';

p1=&a;p2=&b; p3=&c;

p1++;p2++;p3++;

printf("\np1=%u,p2=%u,p3=%u",p1,p2,p3);

return0;

}

Ответ: р1=63388,р2=64392,р3=64405.

Операции адресной арифметики подчиняются следующим правилам. После увеличения значения переменной-указателя на 1 данный указатель будет ссылаться на следующий объект своего базового типа. После уменьшения – на предыдущий объект. Для всех указателей адрес увеличивается или уменьшается на величину, равную размеру объекта того типа, на который они указывают. Поэтому указатель всегда ссылается на объект с типом, тождественным базовому типу указателя.

Применительно к указателям на объект типа char операции адресной арифметики выполняются как обычные арифметические операции, потому что длина объекта char всегда равна 1.

Операции адресной арифметики не ограничены увеличением (инкрементом) и уменьшением (декрементом). К указателям, например, можно добавлять или вычитать из них целые числа.

При операции вычитания двух указателей можно определить количество объектов, расположенных между адресами, на которые указывают эти два указателя. При этом необходимо, чтобы указатели имели один и тот же тип. Кроме того, стандартом C допускается сравнение двух указателей. Как правило, сравнение указателей может оказаться полезным только тогда, когда два указателя ссылаются на общий объект, например, на массив.

Все остальные операции над указателями запрещены.

Сортировка массива

1) Метод прямого включения

Дан массив a[1..n], x-буферная переменная. Во время сортировки массив делится на 2 части – упорядоченную и неупорядоченную. При каждом шаге с i=2 (Iувеличивается на 1 при каждом проходе цикла) из исходной последовательности (неупорядоченной) извлекается i-тый элемент и перекладывается в нужное место готовой части (упорядоченной). Алгоритм:
для i=2 до nвыполнить
x:=a[i]
включить xна соответствующее место среди a[1]..a[i]

В процессе включения xна нужное место представляет собой цикл из сравнений и обменов соседних элементов. Окончание цикла, если найдено число в массиве, меньшее x, либо xпопал на первое место в массиве. Возможные варианты: 1-внутренний цикл с заданным числом повторений, следовательно, возможны лишние сравнения, можно при этом поставить дополнительную проверку. 2-внутренний цикл с предусловием, которое объединяет оба условия (усложнение процесса). 3-установка барьера a[0]:=x. В этом случае проверяется только одно условие окончания цикла.
2) Метод прямого выбора

Действия:

- выбирается элемент с наименьшим ключом

- обменивается местами с первым элементом

- процесс повторяется с n-1 элементом, потом с n-2 и т.д., пока не останется 1 самый большой элемент.

Алгоритм:

Для i=1 до n-1 выполнить

Присвоить k– индекс наименьшего из a[i]..a[n]

Поменять местами a[i] и a[k].

Данный метод в среднем показывает число перестановок M=O*(n*ln(n)). Данный метод быстрее метода прямого включения.

3) Метод прямого обмена (метод пузырька)

Алгоритм основан на смене мест для пары соседних элементов до упорядочивания.

Алгоритм:

Для i:=2 до n выполнить

Для i:=nдо I (шаг -1) выполнить

Еслиa[j-1]>a[j] то

x:=a[j-1];

a[j-1]:=a[i]
a[j]:=x;

все если

все для

все для

 

Поиски

1) Линейный поиск

Если нет никакой дополнительной информации о разыскиваемых данных, то необходим просмотр всей структуры. Такой поиск называется линейным. Условия его окончания: элемент найден или весь массив просмотрен, но совпадений нет.

Алгоритм:
a:[0..N-1]

i:=0;

while (i<N) and (a[i]<>x) do i:=i+1;

Возможно улучшение алгоритма установкой барьера.

a:[0..N]
a[N]:=x;

i:=0;

while a[i]<>x do i:=i+1;

2) Двоичный поиск (поиск деления пополам)

Если нет дополнительных сведений о данных, то линейный поиск – единственный вариант. Если данные упорядочить, то поиск можно сделать более эффективным. Поэтому операциям поиска часто предшествует сортировке.

Пусть массив упорядочен по возрастанию, выберем некоторый элемент amи сравним с x. Если am=x, то поиск заканчивается, если am<x, то все элементы с индексами больше mможно исключить, если am>x, то все элементы с индексами меньше mможно исключить.

Алгоритм:

L,R

Found: boolean;

L:=0;

R:=N-1;
found:=false;

While (L<=R) and not(found) do

Begin

m:=любое значение между Lи R (желательно средний элемент)

if a[m]:=x then found:=true else

if a[m]<x then L:=m+1 else

R:=m-1;

end;

Для ускорения алгоритма можно отказаться от проверки на совпадение

L,R

L:=0;

R:=N;
While L<R do

Begin

m:= (L+R) div 2;

if a[m]<x then L:=m+1 else

R:=m;

end;

В данном случае условие окончания – L>=R. При L=Rцикл заканчивается, но это не свидетельствует о совпадении. При R=Nсовпадений нет. В других случаях a[R] не участвует в проверке, следовательно, необходимо дополнительно проверить a[R]=x.

 

Препроцессор языка Си

Препроцессор языка Си – это текстовый процессор, просматривающий программу до компиляции. Он преобразует программу последовательность символов исходной программы в последовательность лексем.

Лексема – фрагмент исходного текста, имеющий самостоятельный смысл для компилятора и не содержащие других лексем.

Лексемы:

- служебные слова

- константы

- идентификаторы

- знаки операции

- строки (набор символов в кавычках)

- разделители (; , . , (), [], {}…)

Пробельные символы не относятся к лексемам.

A+2*k – 5 лексем

“nom+2” – 3 лексемы.

 

Директивы препроцессора

Можно облегчить модификацию исходных программ и сделать ее более независимой.

Директивы начинаются со знака # и позволяют:

- заменить идентификаторы программы некоторыми значениями

- ставить в исходный файл содержимое другого исходного файла

- запретить компиляцию некоторой части исходного файла

1) включение файла

#include<имя файла> или “имя файла”
В первом случае(<>) – файл должен находить в специальной папке, а во втором(“”) – в любой папке.

2) макро-определения

#define<идентификатор><строка-замещения>

Пример: #define Pi 3,141592

#define NAME “Borland C”

Макрос может иметь аргумент. При каждой замене препроцессора аргументы заменяются на те, которые встречаются в программе. Если в строке замещения макроса аргументы заключены в круглые скобки, то вместо них могут подставлятьсявыражения.

Директивы препроцессора могут быть где угодно а программе.

Директивы записываются в отдельных строках, после них «;»не ставится.

Между# и defineможет ставиться пробел.

Принято описывать макро-определения БОЛЬШИМИ БУКВАМИ.

3) отмена макро-определения

#undef<идентификатор>

Структура программы Си

Программой называется:

- текст на алгоритмическом языке, который подается на комп;

- конечный продукт программирования *.ехе, содержащий двоичный код;

- с логич. точки зрения, программа – это исполнитель, который может обращаться к другим подпрограммам.

Программа на Си – набор функционально законченных модулей, один из них – главный, другой – начальный. Главный модуль вызывается для исполнения ОС.

Модули называются функциями и имеют заданные программистом имена.

Главный модуль имеет служебное имя “main”.

После имени функции обязательно ставятся круглые скобки.

Часть модулей может быть заранее переведена в двоичный код. Такие модули называются объектными, они не участвуют в компиляции и подключаются при компоновке.

Тексты модулей могут храниться в нескольких файлах. Эти файлы называются компонентами трансляции.

Активизация работы модуля производится с помощью спец. Конструкции – “вызов функции”.

Описание действий по обработке информации вып. ф-цией дается в определении ф-ции.

Опред. ф-ции состоит из:

- заголовок

- тело

Тело (или блок) – часть тексты между открывающей и закрывающей фигурой скобкой{}

Ф-цияmainдолжна присутствовать в любой проге Си. Ей управление передает ОС.

Любая ф-ция может содержать обращение к другой ф-ции, кроме main.

В языке Си недопустимы сложенные ф-ции.

Любая ф-ция может содержать предварительное объявление другой ф-ции – декларацию прототипа(в ней объявляется тип ф-ции и тип параметров). Если в текущей компоненте трансляции опред. ф-ции помещено ранее ее вызова, то прототип не нужен

Поразрядные операции

Предназначены для работы с целочисленными данными. Результат – целое значение.

1) &результат“и”

2) | результат “или”

3) ^ (xor)

4) ~ поразрядное отрицание (not)

5) <<сдвиг влево

6) >>сдвиг вправо

Для 5 и 6 - <value><число позиций>

Для<< освобождающиеся справа разряды заменяются нулями.

Для>>разряды слева заменяются нулями, если левый операнд (value) имеет тип unsigned.

Левый операнд не замещается результатом.

31.Операция “?:”

“?:” - единственная тернарная операция.

<выр1>?<выр2>:<выр3>

Работа: 1) вычисляется выр1 и сравнивается с нулем. 2) если выр1≠0, то выполняется выр2, иначе выр3

 

Записи(тип Record).Поля записи.

Объединение элементов произвольных типов называется записью. Элементы записи называется её полями. Запись-это неоднородная структура данных, доступ к элементам записи произвольный. Также как у массива, характер внесения данных в запись является разрушающим.

Записи более универсальны, чем массивы, т.к. элементы могут иметь разные типы. В то же время массивы являются более гибкими структурами данных, т.к. значения индекса можно вычислять.

Описание записей имеет вид:

Type<имя>=record;

<список полей>:<тип 1>;

<-//->:<тип n>;

[<вариантная часть>]

End;

Список полей - последовательное описание полей записи, разделённых запятой. Поле записи может быть записью. Можно создавать массивы из записи.

Допускается record определять с помощью var.

Var student : record;

Name:string[20];

Group:byte;

Marks:array[1..4] of byte;

End;









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.