Модульное программирование 3

Модульное программирование. Понятие функции. 

Один из способов решения сложной задачи – это разбиение её на части. В этом состоит метод нисходящего программирования. 

При программировании на языке Си сложная программа может быть разделена на более простые подзадачи( функции). Это позволяет: 1)упростить структуру программы; 2) избежать избыточности кода, т.к. функции записывают один раз, а вызывать её на выполнение можно многократно; 3) упростить процесс отладки и сопровождение программы, поместив часто используемые ф-ии в библ. Разработанные ф-ии можно сгруппировать в отдельные файлы (модули ) компилируемые отдельно, кот. затем объединяются в исполняемою программу с помощью компоновщика. 

Ф-ия – это самостоятельная единица программы, реализующая конкретную задачу или её часть. Каждая программа написанная на Си должна  содержать главную ф-ию «main».



Объявление и определение функции. Вызов функции.

Объявление(написание прототипа) любой функции имеет следующий вид: 

тип-результата имя-функции (спис.форм.перем.) 

Определение функции 

																{операторы}

																 Можно задать класс пам(обл видимости ф-ии) (пр:[класс] тип…)

																.extern-глобальная видимость во всех модулях прогр.(умолч.)

																.static-видимость только в пределах модуля, в кот определ ф-ия

																Тип возвр. знач может быть люб кроме масс и ф-ии. Но может быть ук. на мА или ф-ию. Если ф-ия не возвр ни какого рез, то указывается тип void.

																 Имя ф-ии – это идентиф задаваемой программистом. Список форм парам: (тип имя_пар1, тип имя_пар2) Опред величины , кот требуется передать в ф-ию при её вызове. Может быть пустым. Тело ф-ии – это либо сост опер., либо блок с описателем перем, масс и т.д. Тело ф-ии не может содерж в себе определ др ф-ий. Из всякой ф-ии возможно обращение к др. ф. Однако они всегда явл внеш по отн к вызыв-ей ф-ие.др ф-ий. ызове. ей мере 2 поля: для хранения данных, для ук.

      Вызов функции

имя-функции (список фактич. перем.) В объяв. опред и в вызове одной и той же ф-ии должно соблюдаться правило соотв типов и порядка следования парам.



Обмен информацией между функциями. Рекурсивные функции.

Способы:

С пом. глоб. перем.

Через возвращение ф-ией значения (оператор return).

- return выражение (в этом случ. знач. будет присвоено ф-ии в её типе) 

- return (завершает выполн. ф-ии и передаёт вып. след. опер-у в вызыв-ей ф-ии) 

Через параметры:  

  Три способа передачи пар-ра в ф-ию:

  а) по значению ( оп-ры работают только с копиями знач-ий фактич-их парам)

  б) по адресу (в стек заносятся копии адресов арг-тов, ф-ия осущ-ая доступ к этим адр может изм исх знач)

  в)по ссылке (в ф-ию перед адр указ-ого при вызове парам) обозн int&z

   Рекурс ф-ия – ф-ия, кот вызывает саму себя. Такая рек. наз-ся прямой. Косвенная рек.- когда 2 и более ф-ий вызывают др друга. Недостатки: расход времени и памяти на повторные вызовы ф-ий и передачу ей копий парам, а также опестн. переполн стека.



Библиотечные функции. Функции для работы в графическом режиме. 

  Любая прогр на Си содержит обращение к стандартной библ. Кроме того программист может созд собств библ. Их подключ с пом. директивы include (.h – header – заголовок).

  На стадии предпроцессорной обр.прогр. происходит подстановка прототипов перед осн. ф-ией, после чего компилятор проверяет правильность обращения к ф-иям. 

  Сами библ. ф-ий хранятся в скомпил.виде и подлюч. к осн. прогр. на этапе компан-ки.

  Библ. ф-ий можно разбить на группы по их назнач.:ввод/выв;матем.ф-ии;для управл.графич системой.

  Функции для работы в графическом режиме.

  Монитор ПК может работать в одном из 2-х режимов: тестовом и графич-ом. Наим. элем-ом изобр.яв-ся пиксель. В Си име-ся граф. библ. graphics.h. Она сод. большое кол-во ф-ий для: упр. цветом, созд.изобр.различ.формы, для вывода граф.текст.сообщ.,для упавл.курсором. Настройка этих ф-ий на работу осущ-ся путём подл.граф.драйвера. Граф.драйверы нах-ся в отдельных файлах с расш .BGI в каталоге BGI(Borl.Graph.Interf.). 

  Граф.ф-ии исп.понятие указателя текущ. позиции. Этот указатель идентиф. выбранный 

пиксель и хар-ся парой цел.чмсел(гор.и верт.коорд.).

  Иниц.гр.режима осущ. ф-иёй initgraph(&gd,&gm, «путь к BGI файлам). gd-гр.драйв.,gm-гр.режим.

  Для обр.ошиб.при работе с гр-ой исп.ф-ия: graphresult().Эта ф-ия возвр. код последней исп.ф-ии. grOk=0

  Цвет в гр.режиме Си имеет свой номер и буквенное обозн. Фон-setbkcolor(цв),цв лин. и симв.-setcolor(цв).

  Парам.текста-settextstyle(шрифт,направл.,разм)

  Характер и толщина лин.геом. объектов-setlinestyle(вид,образец,толщина)

  Стиль закраски к-то области-setfillstyle(тип,закраска,цв)

  Очистка экрана-cleardevice()/

  Определ.макс.зная.по x (getmax x()) и по y (getmax y()).

  Текущ корд. указат.курсора(get x(),get y()).

  Перемещение указат-ля позиции moveto(x,y);moverel(dx,dy).

  Установка парам. по умолч.-graphdefault();

  Вывод точки на экран-putpixel(x,y,цв).

  Вывод текста-outtext(«строка»),outtextxy(x,y, «строка»).



  Графические примитивы.

  Вывод лин.-setwritemode(режим). 0-COPY_PUT,1-XOR_PUT. Если 0,то лин.затирает то,что было на экране.

  Рисов.лин.-line(x1,y1,x2,y2),lineto(x,y),linerel(dx,dy)

  Выв.прямоуг.-rectangle(x1,y1,x2,y2)

  Ломан.лин.-drawpoly(кол-во вершин,указатель на массив целых)

  Окр.(x,y,r)

  Дуга arc(x,y,нач.угол,кон.уг,r)

  Дуга эллипса (x,y,нач.угол,кон.уг,rx,ry)

  Закр.прямоуг.bar(x1,y1,x2,y2)

  Закр.параллел.bar3d(x1,y1,x2,y2,глубина,круша(от0до1))

  Закр.элипс fillellipse(x,y,rx,ry)

  Закр.круг pieslice (x,y,нач.угол,кон.уг,r)

  Закр. сектор эллипса sector(x,y,нач.угол,кон.уг,rx,ry)

  Закр.произв.замкн.обл. floodfill(x,y,граница(должен совп.с цв контура) 









Классы памяти.

  В ПК память представляется разделён.насегменты. Исп.прогр-а сост.из:

1)Сегмента кода, в кот.расположены машинные команды.

2)Сегмент данных, в кот расп. глоб.перемен. и константы.

3)Сегмент стека, в кот расположены локал.перем.

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

 Под всякую переем. исп-ую в прогр. должно быть выделено место в памяти. Выделение пам.может происходить либо на стадии компиляции прогр., либо во время выполнения прогр.(для динам.перем.)

 Каждая перем. имеет оперд. тип. Кроме того она имеет класс памяти. Существует 4 класса памяти: 1)extern(внеш.);2)auto(автоматич-ий);3)static(статический); 4)register(регистровый).

 Класс пам.опред-ся местом её описания и ключевым словом.

 Класс пам.определяет:

1)Область видимости (дей-я перем-х)

2)Время жизни пер.,т.е. продолж-ость её хранения в памяти.

 В Си может быть 3 области видимости:

1)в пределах файла

2)в пр.блока{ }

3)в пр.прототипа  ф-ии

 Время жизни может быть либо на протяжении вып. всей прогр., либо по достяж.блока.

  Внешний класс

Перем. опис. вне ф-ии наз-ся внеш. или глоб.(extern).Глоб. перем. размещается в сегменте данных и изначально обнуляется. Время жизни этой перем.-на протяж всей прогр., обл.действ-файл.

  Автоматич. класс

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

  Статический класс.

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

  Регистровый класс

 Регистровая пам.выделяется под локал. перем. Это самый быстрый и самый маленький вид памяти. Эту пам. исп. не реком., т.к. ей распоряжается компил.Размещение-регистр.пам.;обл.действ.-блок;вр.жизни-блок;иниц-нет.

       

Указатели: понятие, инициализация. 

В процессе комп.прогр.имена перем. преобр. в адреса ячеек пам., в кот хранятся значения перем. Программист может определить собств. перем. для хранения адресов обл-ёй пам. Такие перем.наз-ся указателями.

  Объявление ук.- (тип*имя перем.). Т.е. ук. не явл. самост. типом, он всегда связан с к-либо др. конкр. типом.

  Ук. могут быть константой или перем., а так же указывать на константу или перем.

   Инициализация ук. 

 Значение ук. перед его исп. обяз.должно быть иниц-но(т.е. присвоено нач.знач.)

присвоение ук. адреса сущ-его объекта

пример:

int a=5 int*pti=&a    int*p=pti

  Ук-ям можно присв. зн-я адресов объектов только того типа, кот они описаны: int b[10]; int*t=6?//присв. адр. начала масс-а

Присв. нужного знач.

 ptf=NULL (это значит что отсутств. конкрет. адр. ссылки.

Выделение участка динам. пам. и присв. её адр. перем. Доступ к выделен. участ.динам.пам.произв.только ч/з ук-и.

  Для работы с динам. пам. примен.опер-ии:NEW(для выделения пам.),delete(для освобожд.пам.)

  пример:

1)int*n=new int(выделяется достат. для размещ. величины типа int учасика динам. пам. и записывается адр. начала этого участка в перем. n).

2) int*m=new int(10);(производится иниц. выделен. динам. пам. и запис. 10)

3) int*q=new int[10];(выделяется пам.под 10 величин типа int и записывается адрес начала этого участка в перем. q,кот может трактоватся как имя массива.

  Чтобы освободить пам.

…delete n; 2)…delete m; 3)…delete [];

Операции с указателями.

Оп. разадресации(*)-косвенное обращение к объекту. Оп.разадр-ии предназначены для доступа к величине адрес кот хранится в ук. Эту опер. можно исп. как для получ. так и для изменен. знач. величины.

  пример:

int a=5,b,d;

int*pti=&a;

….

b=*pti;d=pti+2;

cout<<b<<d;

Арифм. оп. 

  Арифм оп. с ук. автоматич. учитывают размер типа величин адресных ук.

 Единицей измерения значения  ук. явл.размер соответсв.ему типа. Эти оп. примен. в основном при работе со структурами данных последовательно размещённых в пам.(пр.:массивы). Если ук. на определённый тип увел. или умен. на константу его значение изм на величину этой конст. умноженную на размер объекта данного типа. Разность 2-х ук.-это разность их знач. делённая на размер типа в байтах. Суммирование ук. не допускается. Инкремент перемещает ук.к след.элем. масс., декремент – к предыдущ.

Сравнивание ук.

  Допускается только для ук. одного типа.

Взятие адреса

 Применимо к величинам имеющим имя и размещённым в оперативной памяти.



Указатели и массивы. Массив как параметр функции.

 Имя масс. обозн. как ук.-константа на массив. В массиве int x[10] x-ук. на нулевой элемент масс-ва, т.е. x=&x[0]. Поэтому для доступа к элементам масс., кроме индексированных имён можно использовать разадрессованные ук.: имя[индекс]*(имя+индекс) (пр:x[i]*(x+i))

 Т.к. имя масс. явл. ук.- константой, то его нельзя изм. в прогр., т.е. ему нельзя ничего присвоить.

  Мас. как параметр ф-ии

 При исп. в качестве парам масс-ва в ф-ию передаётся ук.на его первый элемент, т.е. масс.всегда передаётся по адресу. При этом инф. о кол-ве элем. масс. теряется и следует передавать его размерность ч/з отдельные парам. Передать масс. в ф-ию можно след. сп.:

1)func(int a[N],int N)

2)func(int a[], int N)

3)func(int *a, int N)



Динамические массивы.

 Дин. масс. применяются если до начала работы прогр. неизв.сколько в масс.элем-в. Пам. под них выделяется с пом. операции new.

 В дин. обл.пам.(heap) во время вып.прогр. Адр.её начала запис-ся в ук.(пр:int n=10; int*a=new int[n]//в дин.пам.выд.обл.пам.дост-я для размещ.10 элем.типа int.

 Дин.мас-ы нельзя при созд. иниц-ать. и они не обнуляются. 

 Преимущество дин.мас.-размерность может быть переменной, т.е. объём пам. выд-ой под масс.определяется на этапе выполнен.прогр.

 Обращение к элементу дин.мас.осущ. так же как к элементу обычного (a[3] или *(а+3)

 Если дин. масс. в к-то момент работы прогр. больше не нужен необходимо освободить область пам. кот.он занимает с пом. операции delete[]a;

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

 пример:

 int nstr=5;

 int **m=(int**)new int[nstr][10];

или

int n;

cout int m=5;

cin>>n;

int(*a)[m]=new int[n][m];

 Более универсальный способ выделения пам.под 2-мерн.мас., когда обе его размерности задаются на этапе выполнения прогр. Освобождение пам. из под мас. с любым кол-вом изменений вып. с пом. оп delete[].



Структуры: определение, инициализация. 

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

Тип стр. – обычно исп. при разработке информационных систем и баз данных.

Struct [ имя типа ]

{ тип 1 элемент_1;

тип 2 элемент_2;

…

тип n элемент_n;

}[список_описателей];

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

 пример:

 struct student

{char fam[30];

int kurs;

char group[6];

float ball;}  

student-имя стр.типа, кот. может быть назначен некот. перем.

 Описание перем: [struct] student stud1, stud2(перем.структ.типа);

Может быть совмещено описание типа стр. и объявление перем-х этого типа

пример:

 [struct] student

{char fam[30];

int kurs;

char group[6];

float ball;}  

{stud1,stud2,*pst(ук.на структуру);}

 Поля стр. могут быть в свою очередь данными типа стр.

 пример:

 struct point

{float x: float y;};

 struct line

{struct point p1;struct point p2;};

 Инициал.перем.стр.типа

 struct 1{a,b,c,d};

point z={l;2;3}

Перем.стр.типа можно размещать в дин.обл.пам. Для этого надо описать ук.на стр.и выд.под неё место.(пр:student*pst=new student)

 Доступ к элем. стр. осущ.с пом.опер.выбора (точка) при обращении к полю ч/з имя структ. и-> при обращении ч/з ук.

 пример:

struct student stud1, *ps;

ps->stip=150;

 К каждому элем. стр. перем. Stud 1 можно обратится тремя способами.

1) Stud 1. fam;

2) (* pst). fam;

3) pst -> fam

 Если элем. стр. явл. др. стр., то доступ к её элем. осущ. ч/з 2 операции выбора.

Например:

Struct A

{ int a;

double x;

}

Struct B

{ Struct A b;

double x;

} S, x;

S.b.a=1;

S, b. x= 0.5;

S.x=0.125;

x. b. a=2;

x. b. x=-0.5;

x. x.=2.5;

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

  

Операции над структурами.

Присвоение стр.,если они имеют одинак.тип.При этом происходит поэлементное копирование:

  пример:

   a) struct student stud1,stud2,*ps;

stud2=stud1;

(*ps)=stud1;

     b) struct point a,b;

       (a.x=1;a.y=1;)(bx=ax;by=ay) b=a;

2) Вв/выв стр., как и мас-ов, выполняется по элементно(пр:cin>>stud.fam>>stud.kurs; cout<<stud.fam<<” “<<stud.kurs<<endl;

3) Получение адр стр-ы(student stud1,*ps; student ps=&stud1;).В отличие от масс. имя стр.не имеет никакого значения.

 4)Стр-у можно возвращать в качестве значения ф-ии. Стр-у можно передавать в качестве парам.ф-ии.(пр: struct point make(int x, int y) {struct point temp; temp.x=x; temp.y=y; return temp;} b =make(1.1);)

 При вызове ф-ии в качестве фактич.аргум.указываются имена стр-ых перем-ых.(пр:struct complex x,y,z;….z=add1(x,y);)







Массивы структур. Объединения.

  Структуры, как и др. переменные, могут объединяться в массивы. Массив структур – это удобное ср-во представления и обработки табличной информации. Так например: сведения о ста студентах могут хранится в массиве структур:

Student stud [100];

Тогда сведения об одном студенте могут обозначатся как:

stud [1]. fam;или

stud [5]. kurs;

  Объединения

 Об. представляют собой все поля кот представл. по одному адресу.(пр: union имя_типа {определения элементов};

 Длина об. равна наибольшей из длин его полей. В каждый момент времени переменной типа об. хранится только одно значение. Об. применяются для экономии памяти в тех случаях когда известно, что больше одного поля одновременно не требуется.(пр: union s {int i; char k; long int L;};



Понятие потока. Классификация потоков. 

  Под вв/выв понимается процесс обмена инф. м/у оперативной пам. и внеш. устр-ми. Осн. понятием связанным с инф. на вне шустр явл-ся понятие «файл». Всякая опер вв/выв трактуется как опер обмена с файломи. Поэтому организация вв/выв в языке прогр-это организация работы с файлами. 

   Различают понятия внутр.(логического) и внешнего (физического). Аналогом понятия внутр. файла в Си явл понятие потока. Поток(stream)-это последовательность байтов, передаваемая в процессе вв/выв и независящая от конкретного устр., с кот производится обмен инф.

  Чтение данных из потока наз-ся помещением или подключением. 

  По направлению обмена потоки можно разделить на входные(данные вводятся в пам.) и данные выводимые из памяти.

  По виду устр. с кот. работает поток их можно разделить на:

-стандартные (для передачи данных от клав)

-файловые(для обмена инф. с файлами на внеш носит.)

-строковые(для работы с массивами симв в операт пам)

  Для поддержки потоков библ Си содержит иерархию классов построенную на основе класса ios(include output stream)

  Этот класс содержит общие для вв и выв поля и методы.

Иерархия классов













Стандартные потоки.

Прямыми потоками класса ios (производными классами) явл-ся класс istream (класс входных потоков) и ostream(класс выходных потоков); потомком этих 2-х классов явл класс iostream вв/выв).

 Объект cout принадлежит классу ofstream и представляет собой поток вывода связанный с дисплеем.Оп. поместить в поток cout<<a означает, что зн. «а» должно быть выв. из пам.на дисплей. 

  Объект cin принадлежит iostream и явл.потоком связанным с клав. Операции:взять из потока cin>>а означает что значение перем. а должно быть вв с клав в пам. 

  

Файловые потоки. Запись данных в файл. Режимы открытия файлов. 

При обработке файлов в Си исп. 3 класса:

1)ifstream-класс входных потоков,вып.опер.вв. из файла.

2)ofstream-класс выходных пот,вып.опер.выв в файл.

3)fstream-класс двунаправленных ф.пот.,вып.вв/выв инф.

 Эти классы явл. производными от классов istream,ostream,iostream. Поэтому они наследуют операции >>,<< и др.оп.

 По способу доступа файлы можно разделить на:

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

файлы с произвольным доступом(бинарные, допускающие чт.и зап. в указ. позиц.)

 Создание ф.послед.доступа и запись его данных.

1)#include<fstream.h>

2)объединяем файловую перем.выходного ф-ого потока.

 ofstream fout:

 открываем физ-ий файл fout.open (“имя физ.файла”)

 ofstream fout(“output.txt [режим открытия ф.]);

3) Записываем в ф.инф. fout<<”z=”<<z<<endl;

4) Закр.ф. fout.close();

Режимы открытия файлов.

ios::app – отрк.ф.для добав. в конец

ios::ate – установить ук.на конец ф.

ios::in – откр.ф.для вв.

ios::out – откр.ф.для выв.(зап.)

ios::trunt – если ф.сущ.,то удалить. По умолч.устан.для ios::out 

ios::nocreate – если ф.не сущ,выдать ош.

ios::noreplace – если ф. сущ., выдать Ош.

ios::binary – откр.ф. в двоичном режиме.

пример: ifstream fin(“input.txt”,ios::in|ios::nocreate)



Чтение данных из файла.

Подкл.библ. fstream

Объявл.ф-вую перем входного ф.потока.

откр.физ.ф. ifstream.fin(“input.txt”,[режим откр.ф.])

Вв данные из ф. fin>>a

Закрываем fin.close();



Форматирование данных: флаги форматирования. Манипуляторы.

Ф. может осущ 3-мя способами:

1) с пом. флагов

2) с пом. манипуляторов

3) с пом. форматирующих методов

  1 способ

Флаги представл.собой отдельные виды объединенные в поле x_flags класса ios.

left-выравн. по левому краю

right-по правому(умолч)

dec: десятичн.сис.счисл.(умолч)

oсt: 8-ая сис.сч.

hex: 16-ая сис.сч.

scientific:выв вещ.чисел в форме мантиссы с порядком.

fixet: выв вещ чисел в форме с фиксир. точкой.

 Кроме флагов для форм-я исп.след.поля класса ios:

x_width- задаёт мин. ширину выв.

x_precision- задаёт кол-во цифр дроб.части при выв значения fixed или общее кол-во значащих цифр при выв знач scientific.

 Манипуляторы. (<iomanip.h>)

М. делятся на:

1)простые, не требующие указания аргумента.

2)параметризированные: требуют парам.

 Пользоваться манн.проще чем флагами.

 Параметриз.ман.

 setbase(int n)-задаёт парам сис.сч.

setfill-устанавливает символ заполнитель с кодом равным значению парам

setprecision- устанавливает макс.кол-во в дробной части, если число с фикс точкой, или если число представлено её мант. и парядком.

setw(int)-задаёт макс. ширину поля вв.



Строки: описание, ввод/вывод. 

 В Си 2 вида строк: Си строки и Класс стандартные библ Си, класс стринг. Си строка представл. собой масс симв завершающийся сим-м с кодом нуль(‘\0’) «нуль символ».

 char s[10]=”строка”;

s[0]…s[6]…s[9]=’\0’

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

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

 Для размещения строки в динам. пам. надо описать ук. на char, а затем выделить пам. с пом. new.(пр: char *p=new char[m])

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

   Вв/выв строк.

#include <iostream.h>

int main()

{const int n=80;

char s[n];

cin>>s;

cout<<s;

return 0;}

 Если будем вв стр. из неск. слов, то будет выв. только первое. Это связанно с тем, что вв вып только до перого пробельного слова. Если требуется вв строку из неск слов в одну стр. перем. исп. метод get и getline класса istream объектом кот. явл cin.

 пример:…

   Символ перевода строки так же считывается, но не запис в перем., а запис в нуль симв. Метод get работает аналогично, но оставляет символ перевода строки. Чтобы удалить его из потока необходимо вызвать cin.get без парам(). Если необх. вв неск строк, то метод getline исп в цикле.(пр.:while(cin.getline(s,n))

 Для вв/выв строк можно исп. след ф-ии Си: gets, puts. (пр: gets(s))

 Для вв/выв 1 симв. исп. getchar(), putchar().

Операции со строками. Строка как параметр функции.

Библ. <string.h> содержит след ф-ии работы с ф-иями.

Инициализация строки

Общий метод инициализации строки:

char stringVar[stringSize] = stringLiteral;

Пример

char a3tring[81] = "Borland C++ 5 in 21 days";

char Named = "Rene Kinner";

Второй способ присвоить значение строке — это вызвать функцию, которая копирует содержимое одной строки в другую, — не забывая при этом и нуль-символ. Эта функция называется strcpy. Она предполагает, что копируемая строка оканчивается символом NUL и прекращает копирование, как только встретит этот символ.

     Функция strcpy

Прототип функции strcpy таков:

char* strcpy(char *target, const char *source);

Функция копирует строку source в строку target. Функция предполагает, что целевая строка имеет размер, достаточный для того, чтобы вместить содержимое строки-источника.                               

  Пример

char name[41] ;

strcpy(name, "Borland C++ 5");

        Функция strdup

Функция strdup копирует одну строку в другую, при этом отводит необходимое количество памяти для целевой строки.

Прототип функции strdup таков:

char* strdup(const char *source);

Функция копирует строку source и возвращает указатель на строку-копию.

Пример

char *string1 = "Монархия в Испании";

char *string2;

string2 = strdup(string1);

После того, как будет отведено необходимое количество памяти для строки string2, строка string1будет скопирована в строку string2. 

        Функция strncpy

Библиотека строковых функций предлагает также функцию strncpy, копирующую заданное количество символов из одной строки в другую.

Прототип функции strncpy таков:

char * strncpy(char *target, const char *source, size_t num);

Функция копирует num символов из строки source в строку target. Функция не выполняет ни усечение, ни заполнение строки.

Пример

char str1[] = "Pascal";

char str2[] = "Hello there";

strcnpy(strl, str2, 5);

Переменная strl содержит строку "Hellol". Заметьте, что символ ‘l’ строки-приемника, следующий за скопированной частью строки, сохранился.

         Функция strlen

Функция strlen  возвращает количество символов в строке, в которое не включается нуль-терминатор.

Прототип функции strncpy таков:

size_t strlen (const char *string) ,

Функция strlen возвращает длину строки string. size_t — это имя, приписанное типу unsigned int оператором typedef.

   Пример

char str[] = "1234567890";

size_t i;

i = strlen(str), 

Переменной i будет присвоено значение 10.

      Функция strcat

Конкатенация строк означает их последовательное присоединение друг к другу.

Прототип функции strcat таков:

char *strcat(char *target, const char *source) ;

Функция добавляет к содержимому целевой строки содержимое строки-источника и возвращает указатель на целевую строку. Функция предполагает, что целевая строка может вместить содержимое объединенной строки.

Пример

char string[81] ;

strcpy(string, "Turbo");

strcat (string, " C++");

Переменная string содержит строку "Turbo C++".

         Функция strncat                                            

Функция strncat добавляет к содержимому целевой строки указанное количество символов из строки-источника.

Прототип функции strcat :                                     

char *strncat(char *target, const char *source, size_t num);

Функция добавляет к содержимому целевой строки num символов из строки-источника и возвращает указатель на целевую строку.

char strl[81] = "Hello I am ";                          

char str2[41] = "Keith Thompson";                                

strncat(strl, str2, 5);        

        Функция strcmp

Функция strcmp выполняет сравнение двух строк с учетом регистра символов.

Прототип функции strcmp:

int strcmp(const char *strl, const char *str2);

Функция сравнивает строки strl и str2. Возвращает в качестве результата сравнения целую величину:

< 0 когда strl меньше, чем str2;

= 0 когда strl равна str2;

> 0 когда strl больше, чем str2.

Пример

char stringl[] = "Borland C++";

char string2[] = "BORLAND C++";

i = strcmp(string1, string2);



В последнем операторе переменной i присваивается положительное значение, так как string1 больше string2 (ASCII-коды символов в нижнем регистре больше ASCII-кодов символов в верхнем.)

Функция stricmp

Функция stricmp выполняет сравнение двух строк, не учитывая регистра символов.

Прототип функции stricmp:

int stricmp(const char *strl, const char *str2);

Функция сравнивает строки strl и str2, не делая различия между символами в нижнем и верхнем регистре. Возвращает в качестве результата сравнения целую величину:

< 0 когда strl меньше, чем str24

= 0 когда strl равна str24      

> 0 когда strl больше, чем str2.

Пример

char string1[] = "Borland C++";

char string2[] = "BORLAND C++";

int i = strcmp(string1, string2);



В последнем операторе переменной i присваивается значение 0, так как string1 и string2 отличаются друг от друга только регистром символов.

Функция strncmp выполняет сравнение заданного количества символов двух строк с учетом регистра символов.

Функция strncmp

Прототип функции strncmp:

int strncmp(const char *strl, const char *str2, size_t num);

Функция сравнивает первые num символов строк strl и str2. Возвращает в качестве результата сравнения целую величину:

< 0 когда strl меньше, чем str2;

= 0 когда strl равна str2;

> 0 когда strl больше, чем str2.

Пример

char string1[] = "Borland C++";

char string2[] = "Borland Pascal";

i = stricmp(string1, string2, 9);

В последнем операторе переменной i присваивается отрицательное значение, так как значение "Borland С" меньше, чем "Borland Р".

Функция strnicmp

Функция strnicmp выполняет сравнение заданного количества символов двух строк без учета регистра символов.

Прототип функции strnicmp :

int strnicmp(const char *strl, const char *str2, size_t num);

Функция сравнивает первые num символов строк strl и str2, не делая различия в регистре символов. Возвращает в качестве результата сравнения целую величину:

< 0 когда strl меньше, чем str2;

= 0 когда strl равна str2;

> 0 когда strl больше, чем str2.

Пример

char string1[] = "Borland C++";

char string2[] = "BORLAND Pascal";

i = strnicmp(string1, string2, 7);

Функция strlwr

Прототип функции strlwr:

char* strlwr (char *source)

Функция преобразует символы верхнего регистра в символы нижнего регистра в строке source. Другие символы не затрагиваются. Функция возвращает указатель на строку source.

Пример

char str[] = "HELLO THERE";

strlwr(str);

Переменная str теперь содержит строку "hello there".

Функция strupr

Прототип функции strupr:

char* strupr(char *source)

Функция преобразует символы нижнего регистра в символы верхнего регистра в строке source. Другие символы не затрагиваются. Функция возвращает указатель на строку source.

Пример

char str[] = "Borland C++";

strupr(str);

Переменная str теперь содержит строку "BORLAND С ++".

Функция strrev

Прототип функции strrev:

char* strrev(char *str)

Функция обращает порядок символов в строке str и возвращает указатель на строку str. char str[] = "Hello";

strrev(str) ;

cout « str;

Будет выведено "olleH".

Функция strchr

Функция strchr определяет первое вхождение символа в строку.

Прототип функции strchr:

char* strchr(const char *target, int c)

Функция находит первое вхождение символа с в строку target. Функция возвращает указатель на символ в строке target, который соответствует заданному образцу с. Если символ с в строке не обнаруживается, функция возвращает 0.

Пример

char str[81] = "Borland C++";

char *strPtr;

strPtr = strchr(str, '+');



Указатель strPtr теперь содержит адрес подстроки "++" в строке str. 

Функция strrchr

Функция strrchr определяет последнее вхождение символа в строке.

Прототип функции strrchr:

char* strrchr(const char *target, int c)

Функция находит последнее вхождение символа с в строку target. Функция возвращает указатель на символ в строке target, который соответствует заданному образцу с. Если символ с в строке не обнаруживается, функция возвращает 0.

Пример 

char str[81] = "Borland C++ is here";

char* strPtr;

strPtr = strrchr(str, '+');

Указатель strPtr теперь указывает на подстроку "+ is here " в строке str.

Функция Strspn

Функция strspn возвращает число символов с начала строки, совпадающих с любым символом из шаблона.

Прототип для функции strspn:

size_t strspn(const char *target, const char *pattern)

Функция strspn возвращает число символов от начала строки target, совпадающих с любым символом из шаблона pattern.

Пример

char str[] = "Borland C++ 5";

char substr[] = "narlBod";

int index;

index = strspn(str, substr);



Этот оператор присваивает 8 переменной index, потому что первые восемь символов из str содержатся в подстроке substr.

Функция strcspn

Функция strcspn просматривает строку и выдает число первых символов в строке, которые не содержатся в шаблоне.

Прототип функции strcspn:

size_t strcspn(const char* str1, const char* str2)

Функция strcspn просматривает строку str1 и выдает длину подстроки, отсчитываемой с начала строки, символы которой полностью отсутствуют в строке str2.

Пример

char strng[] = "The rain in Spain";

int i = strcspn(strng, " in");             

Этот пример возвращает 3 (расположение первого пробела в строке strng) переменной i.

Функция strpbrk

Функция strpbrk просматривает строку и определяет первое вхождение любого символа из образца.

Прототип функции strpbrk:

char* strpbrk(const char* target, const char* pattern)

Функция strpbrk ищет в строке target первое вхождение любого символа из образца pattern. Если символы из образца не содержатся в строке, функция возвращает 0.

Пример

char *str = "Hello there how are you";

char *substr = "hr";

char *ptr;

ptr = strpbrk(str, substr);

cout « ptr « endl;

Вы увидите на экране строку "here how are you", потому что 'h' встречается в строке str раньше, чем 'r'.

Функция strstr

Прототип функции strstr:

char* strstr(const char *str, const char *substr);

Функция ищет в строке str первое вхождение подстроки substr. Функция возвращает указатель на первый символ найденной в строке str подстроки substr. Если строка substr не обнаружена в строке str, функция возвращает 0.

Пример

char str[] = "Hello there! how are you";

char substr[] = "how";

char *ptr;

ptr = strstr (str, substr);

cout « ptr « endl ;

Это приведет к выводу строки "how are you", поскольку в строке str ,      была обнаружена подстрока "how". Указатель ptr содержит адрес остатка первоначальной строки, начинающегося с подстроки "how".

Функция strtok

Библиотека функций для работы со строками имеет функцию strtok, которая дает вам возможность разбить строку на подстроки на основании заданного набора символов-ограничителей.

Подстроки иногда называются лексемами.

Прототип функции strtok:

char* strtok(char *target, const char * delimiters);

Функция разбивает строку на лексемы, согласно символам-ограничителям, заданным в параметре delimeters. В следующем примере показано, как работать с этой функцией и как получать лексемы, на которые была разбита строка. Функция strtok вводит символ '\0' после каждой лексемы. (Опять же не забудьте сохранить копию вашей строки в другой строковой переменной.)

  

 Библиотека <stdlib.h>. Здесь содержатся ф-ии преобразования строки в числа.

atoi(st) – преобр целое число строк (пр: r=atoi(“_ _ +121”)

atol(st)- преобр стр string в тип long

atof(st) – преобр в тип double 

 Если строку нельзя преобразовать в число возвращается нуль

  Библ. <ctype.h>. В этой библ содержатся ф-ии для работы форматом.

isalpha(ch) истина если симв-буква

isalnum(ch) истина если симв-бук или цифра

iscntrl(ch) истина если симв

isdigit(ch) истина если симв десятич цифры

islower(ch) истина если строчн буква

ispunct (ch) истина если симв пункт

isspace(ch) ис если симв пустого места или пробела

islower(ch) опр принадл к верх рег

isupper(ch) преобр к верхнему регистру

tolower(ch) toupper(ch) перевод в ниж и верх рег

Строка как параметр функции

Исп. строки в качестве парам ф-ии аналогично исп массивов в др. типа, однако имя масс есть ук. на его …, а имя строки явл-ся ук.перем., следовательно его значен может изм-сяю.



Сортировка данных. Алгоритмы сортировки.

Под сортировкой понимают процесс перестановки объектов данного множества в определённом порядке. Цель сорт.- обеспечить последующий поиск элем в отсортированном множестве. Метод сортировки разделяют на 2 категории:

Внутр.-сорт. масс.(масс располог во внут или отсорт пам)

Внешн – сорт ф-ов (ф. расп во внеш пам)

Как правило, сортируемые данные располагаются в массиве. А простейшем случае-это числовые мА-ы, однако для алг более хар-на сит, когда сорт масс структур. Поле, по знач кот производится сорт наз-ся ключом сорт. Основное требование к методам сорт-экономное исп пам. В этом смысле говорят что сортировку нужно вып in site – на том же месте.

  Удобной мерой эффективности алг сорт на месте явл:

число С(compore) необходимых сравнений ключей

число M (move) необходимых пересылок элем-в.

 Эффективн. алг. сорт треб порядка С~N*log2N сравнений где N – число элем сортируемого масс. Эти методы требуют меньшего числа оп,но эти оп. более сложные. 

 Простые методы сорт порядка С~N2  сравнений: 

Они хорошо подходят для разъяснения св-в большинства принципов сорт.

Прогр. основан. на этих методах лёгкие для понимания и коротки.

При достаточно малых значениях N они раб также быстро как и сложные => больших N исп не эффективно.



Сортировка выбором.

выбир-ся элем с наиб значением ключа и меняется местами с послед элем.

выбирается наиб элем из первых (n-1) элем-в и меняется местами с послед элем и т.д.

void sort (float a[N], int n)

{float t; int k,i,j;

for (k=n;k>1;k--)

{i=0;

for (i=1;i<k;i++)

if (a[j]<a[i]) j=I;

t=a[k-1];

a[k-1]=a[j];

a[j]=t;}}

Эффективность сортр число C=(N-1)*N/2~N2  M=(3+N/4)*(N-1)~N2 



Сортировка обменом .

Просм массив сначала при этом сравнив 2 сосед элем ai,ai+1 если ai> ai+1 то элем-ы меняются местами в рез 1-го просмотра масс-а мах знач переместится в конец.

Повторив ту же процедуру до предпоследнего элем и т.д. Сорт законч либо после очередного прохода не сделано ни одного обмена либо сделано (n-1) просмотров.

void sort (struct str a[N], int n)

{struct str t;

int fl,I,j;

do {fl=0; n--;

for (i=0;i<n;i++)

if (a[i].x>a[i+1].x)

{t=a[i]; a[i]=a[i+1]; a[i+1]=t; fl=1;}

}while (fl);

 б) for(i=0;i<n-1;i++)

 for(j=0;j<n-i-1;j++)

if (a[i].x>a[i+1].x)

{t=a[i]; a[i]=a[i+1]; a[i+1]=t;}

Эффективность сорт:  C=N2/4  M=1.5*(N2/4)



Сортировка включением.

Элем разделяются на упорядоч инее упорядоч части.В начале упоряд часть содержит только один элем очередной элемент из начала неуп части вставляется на подход место в уп часть при этом уп часть удлин на 1 мм а неуп укорач. Сорт заканч при исчезнов не упорядоч части

 void sort (float a[N],int n)

{float t; int i,j;

for (j=1;j<n;j++)

{t=a[j];//заполн знач кот нужно поставить на своё место в 1 части

i=j-1;

while (i>=0 &&t<a[i])

{a[i+1]=a[i];i--;}//продвиж дырки в лев части мас до той позиц в кот долж быть включ элем 

a[i+1]=t;}}//вкл элем в левую часть

  Эффективность сорт: C=((N-2)+(N+1)*(N-2)/2)/2)  M=(3*(N-2)+(N+5)*(N-2)/2)/2



Динамические структуры данных. Линейные списки.

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

  Дин стр прим для более эффек раб прогр:

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

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

 Элем люб дин стр данных предст собой стр сод-ую по крайней мере 2 поля: для хранения данных, для ук.

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