· указательна заголовок связанного списка, т.е. на первый узел списка;
· параметры соответствующие полям структуры.
Для рассматриваемого примера прототип такой функции будет выглядеть как:
void newHead(PtrNode& head, char name[], int year);
Это значит, что для создания узла во-первых необходим адрес следующего узла и данные, которые будут содержаться в создаваемом узле.
void newHead(PtrNode& head, char name[], int year){
PtrNode tempPtr=new sotrudnik; //выделяется место под узел
tempPtr->name=name; //записываются данные узла
tempPtr->year=year_b;
tempPtr->link=head; //указывается адрес головного узла
/*в указатель коловного узла записывается новый адрес*/
head=tempPtr;
}
Вот код программы
#include<windows.h>
#include<iostream.h>
struct sotrudnik{
char name[30];
int year_b;
sotrudnik *link;
};
typedef sotrudnik *PtrNode;
void newHead(PtrNode& head, //адрес головного узла
char name[], int year //данные нового узла
);
main(){
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
PtrNode head;
head=new sotrudnik; //создаем первый узел
strcpy(head->name,"Иванов Иван Иванович");
head->year_b=1980;
head->link=NULL;
char str[30];
int year;
for(int i=0;i<4;i++){ //создаем еще 4 узла
cout<<endl<<"Имя: ";
cin>>str;
cout<<"Год рождения: ";
cin>>year;
newHead(head, str, year);
}
char z;
cin>>z;
}
//Функция для вставки нового головного узла
void newHead(PtrNode& head, char name[], int year){
PtrNode tempPtr=new sotrudnik;
strcpy(tempPtr->name,name);
tempPtr->year_b=year;
tempPtr->link=head;
head=tempPtr;
}
Для просмотра введенных всего списка нужно добавить функцию
PtrNode review(PtrNode head){
PtrNode h=head; //указателю присваивается значение головного узла
if(h==NULL){ //Случай пустого списка
return NULL;
}
else{
cout<<"ФИО:"<<h->name<<endl<<"Годрождения:"<<h->year_b<<endl;
return h->link; //возвращаем указатель
}
}
Тогда вся программа принимает вид
#include<windows.h>
#include<iostream.h>
struct sotrudnik{
char name[30];
int year_b;
sotrudnik *link;
|
|
};
typedef sotrudnik *PtrNode;
PtrNode review(PtrNode head);
void newHead(PtrNode& head, //адрес головного узла
char name[], int year //данные нового узла
);
main(){
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
PtrNode head, poisk;
head=new sotrudnik;
strcpy(head->name,"Иванов Иван Иванович");
head->year_b=1980;
head->link=NULL;
char str[30];
int year;
for(int i=0;i<4;i++){
cout<<endl<<"Имя: ";
cin>>str;
cout<<"Год рождения: ";
cin>>year;
newHead(head, str, year);
}
poisk= head;
for(int i=0;i<5;i++){
poisk=review(poisk); // просмотр и получение следующего адреса
}
char z;
cin>>z;
}
//Функция для вставки нового головного узла
void newHead(PtrNode& head, char name[], int year){
PtrNode tempPtr=new sotrudnik;
strcpy(tempPtr->name,name);
tempPtr->year_b=year;
tempPtr->link=head;
head=tempPtr;
}
PtrNode review(PtrNode head){
PtrNode h=head; //указателю присваивается значение головного узла
if(h==NULL){ //Случай пустого списка
return NULL;
}
else{
cout<<"ФИО:"<<h->name<<endl<<"Годрождения:"<<h->year_b<<endl;
return h->link; //возвращается указатель на следующий узел
}
}
Поиск в связанных списках
Поиск нужного уздла осуществляется путем просматривания всех узлов, начиная с головного.
Создадим функцию для поиска нужного узла. Функция должна иметь 2 параметра: адрес головного узла и какую-нибудь величину по которой происходит поиск, например год рождения, т.е. прототип функции имеет вид:
NodePtr(NodePtr head, int target);
Код самой функции выглядит так:
NodePtr search(NodePtr head, int target){
NodePtr h=head; //указателю присваивается значение головного узла
if(h==NULL){ //Случай пустого списка
return NULL;
}
else{
while(h->year_b!=target && h->link!=NULL) //год не соответствует
h=h->link; //переход к следующему узлу
if(here->year_b==target) //год соответствует
return h; //возвращаем указатель
else
return NULL;
}
}
Наконец, узел, создаваемый первым можно включить в цикл. Вся программа выглядит так:
|
|
#include<windows.h>
#include<iostream.h>
struct sotrudnik{
char name[30];
int year_b;
sotrudnik *link;
};
typedef sotrudnik *PtrNode;
PtrNode review(PtrNode head);
PtrNode search(PtrNode head, int target);
void newHead(PtrNode& head, //адрес головного узла
char name[], int year //данные нового узла
);
main(){
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
PtrNode head, poisk;
head=new sotrudnik;
char str[30];
int year;
//Формирование списка
for(int i=0;i<3;i++){
cout<<endl<<"Имя: ";
cin>>str;
cout<<"Год рождения: ";
cin>>year;
newHead(head, str, year);
if(i==0) head->link=NULL;
}
//Просмотр списка
poisk=head;
for(int i=0;i<3;i++)
poisk=review(poisk);
//Поиск
cout<<endl<<"Поиск по году рождения:";
cin>>year;
poisk=search(head,year);
cout<<"Имя: "<<poisk->name<<endl<<"Год рождения: "<<poisk->year_b;
char z;
cin>>z;
}
//Функция для вставки нового головного узла
void newHead(PtrNode& head, char name[], int year){
PtrNode tempPtr=new sotrudnik;
strcpy(tempPtr->name,name);
tempPtr->year_b=year;
tempPtr->link=head;
head=tempPtr;
}
//Функция просмотра списка
PtrNode review(PtrNode head){
PtrNode h=head; //указателю присваивается значение головного узла
if(h==NULL){ //Случай пустого списка
return NULL;
}
else{
cout<<endl<<"ФИО:"<<h->name<<endl<<"Годрождения:"<<h->year_b<<endl;
return h->link; //возвращаем указатель
}
}
//Функция поиска
PtrNode search(PtrNode head, int target){
PtrNode h=head; //указателю присваивается значение головного узла
if(h==NULL){ //Случай пустого списка
return NULL;
}
else{
while(h->year_b!=target && h->link!=NULL) //год не соответствует
h=h->link; //переход к следующему узлу
if(h->year_b==target) //год соответствует
return h; //возвращаем указатель
Else
return NULL;
}
}
Директивы препроцессора.
Любая работа начинается с её подготовки. Так поступает человек, но точно так поступает компилятор. Прежде чем перевести программу в машинные коды происходит обработка исходного текста программы. Для этого в компиляторе языка С++ есть специальная программ, которая называется препроцессором. Препроцессор может работать самостоятельно, выполняя возложенные на него операции, но многое он может делать в соответствии с указаниями содержащимися в обрабатываемой им программы. Для этого имеются специальные команды или, как их называют директивы препроцессора.
|
|
Каждая директива помещается на отдельной строке и начинается с символа # (решетка). С некоторыми директивами мы уже встречались, но с большинством нам еще предстоит познакомиться.
#include – позволяет включать в программу другие программы или
Директива #include имеет две формы записи, отличающиеся тем, что имя файла указывается либо в угловых скобках, либо в кавычках.
#include <имя_файла>
#include "имя_файла"
Это вызвано тем, что препроцессору нужно указать где искать присоединяемый файл. Имя в угловых скобках говорит о том, что файл с этим именем находится в системных каталогах. Если имя файла заключено в кавычки, то файл находится в текущий каталог, т.е. тот каталог в котором находится сама программа. Если в текущем каталоге этот файл не обнаружен, тогда поиск проводится по всем системным каталогам.
#define –производит определение идентификаторов и макросов. Может встречаться в любом месте программы. Её действие распространяется от места размещения до конца программы или до появления директивы #undefine, котораяотменяет действие команды #define. Например,
//До этого момента мог быть текст программы
#define pi 3.14169269
#define begin {
#define end }
//Далее идет текст программы
Препроцессор встретив в тексте программы идентификатор pi заменит его на 3.14169269. Подобным образом он поступит с идентификаторами логических скобок, которые встречаются в других языках программирования. В данном примере они вероятно используются потому, что программист создавший такую программу привык работать с другими языками.
Синтаксис таков
#define имя пробел имя_или_выражение
С помощью директивы #include можно даже менять имена функций. Так знакомая нам программа "Hello Word" может быть записана так.
#include <iostream.h>
#define print cout<<
main(){
print "PRIVET!";
int i;
cin>>i;
}
Иногда в директиву #define входит идентификатор, определенный ранее в другой директиве #define. Тогда происходит подстановка определенного ранее идентификатора в место его применения, например
#define pi 3.14159259
#define pi2 2*pi
Обратите внимание, что с помощью директивы #define препроцессор не заменяет одни символы на другие, а определяет имена и их замену. Поэтому имя 2pi будет воспринято как ошибка, т.е. имя 2pi нельзя использовать даже в директивах препроцессора, что соответствует правилу присвоения имен. Хотя немного ниже мы опровергнем это утверждение.
Замены вызванные директивой #define можно отменить с помощью #undefine и переопределить замены заново.
Директива #define мощный, но не всесильный инструмент. Так замены не выполняются внутри строк, символьных констант и комментариев.
Директива #define часто используется для создания больших программ из отдельных программ написанных различными программистами. В таких случаях возможны присвоение одинаковых имен разным объектам. Для того, чтобы исключить ошибки можно куски программ заключать в своеобразные скобки, состоящие из директив #define и #undefine. Например,
//Текст основной программы
x=10;
//Продолжение программы
#define x y
x=1; //Переменная x заменена на y, поэтому x по-прежнему равен 10
//Текст включаемой программы
#undefine
x++; // После этой операции значение x равно 11
//Текст основной программы
Теперь рассмотрим как с помощью директивы #define определить макрос. Напомним, что макрос это программа замены одной последовательности символов на другую. Мы уже пользовались директивой
#define имя пробел имя_или_выражение
но её можно расширить следующим образом
#define имя(список_параметров) пробел имя_или_выражение
Пример, который приводится практически во всех книгах по языку С++
#define max(a,b) (a<b?b:a)
#include <iostream.h>
main(){
int a,b;
cin>>a>>b;
cout<< max(a,b);
}
В этой программе выражение max(a,b) в главной функции main()заменяется условным оператором a<b?b:a написанным на языке "С". А как выглядит эта программа на "С++"? Например так:
#define max(a,b) if(a<b) cout<<b; else cout<<a;
#include <iostream.h>
main(){
int a,b;
cin>>a>>b;
max(a,b);
}
Вот другой пример
#define max(a,b) (a<b?b:a)
#if с модификацией #ifdef, #ifndef совместно с директивами #else, #enddif, #elif позволяют программировать обработку части кода, которая выделена с помощью этих операторов. Директивы напоминают условные операторы языка if и if-else.
Синтаксис прост
#if выражение1 выражение2
#else выражение3
#endif
Выражение1 может быть логическим или арифметическим символом или строкой. Если выражение1 имеет значение false или ноль значение отличное от нуля то выполняется выражение3, в противном случае выполняется выражение2.
Например,
#include <iostream.h>
#if 2*2 /*произведение равно 4, поэтому компилируется только
первая программа */
main(){
cout<<endl<<"2*2=4";
int i;
cin>>i;
}
#else
main(){
cout<<endl<<"2*2=5";
int i;
cin>>i;
}
#endif
Директива #if может использоваться без директивы #else, подобно тому как это принято в языке С++. Также как в языке директивы могут быть вложенными.
#line -
Интегрированная среда разработки программ Microsoft Visual C++6
Интегрированная среда разработки (Integrated Development Environment) или IDE позволяет создавать программы на языке С++ любой сложности.
В отличие от простых компиляторов программа в IDE создается не в виде отдельного файла, а как множество взаимосвязанных файлов, большинство из которых используется только при отладке программы и в дальнейшем обычно удадаляются. Совокупность таких файлов, обеспечивающих работу и отладку программы называется проектом. IDE работаетпод управлением Windows. Все программы работающие в этой операционной системе принято называть приложениями. Самыми простыми программами на языке С++, создаваемыми в IDE являются, так называемые, консольные приложения.
Консоль – это электрическая печатная машинка, которая в 70-80 годы использовалась для ввода и вывода сообщений операционной системы в вычислительную машину. Позднее машинка была заменена текстовым дисплеем с клавиатурой. Операционная система DOS, которая использовалась на ранних этапах применения персональных компьюьеров также предоставляла возможность работать в режиме консоли. В этом случае экран представлял собой черное окно на которое выводились сообщения системы, или команды вводимые с клавиатуры. DOS, по существу, отдавала все ресурсы компьютера исполняемой программе. Windows работает иначе. В этой системе одновременно работают несколько программ, большинство из которых незаметно для пользователя. Программы и ситема обмениваются между собой сообщениями. Выполнение всех программ контролируется системой. Необходимые ресурсы компьютера для выполнения каждой программы, так же отводятся системой. Таким образом, программа создаваемая в среде Windows должна уметь создавать сообщения для операционной системы и обрабатывать или, говоря иначе, реагировать на сообщения системы.
К счастью, операционная система Windows может работать в режиме имитации консоли. Это нужно для того, чтобы программы созданные под DOS выполнялись в новой операционной системе. Для нас это дает возможность создавать программы для С++ не задумываясь над тем как создавать и обрабатывать сообщения системы, ведь в DOS их нет.
Первое, что необходимо сделать когдавы приступаете к созданию новой программы это созать проект. Строго говоря, проект создаст сама IDE, вам нужно лишь сказать какого рода приложение будет создано в проекте, и дать имя проекту.
Для этого:
1. В строке меню выберите пункт меню File, а в нем команду New.
2. В появившемся диалоговом окне перейдите на вкладку Projects.
3. В поле Projects name введите имя проекта, например My first project. IDE позволяет использовать любые имена, например, имена из нескольких слов, т.е. имена содержащие пробелы. Можно использовать одни цифры. Более того, в именах можно применять кириллицу, но как делать это не рекомендуется, во избежании непонятных сбоев в работе англоязычных программ.
4. Укажите тип создаваемого проекта, выделив его из списка. В данном случае это Win32 Console Application,
5. В поле Location (Расположение) нужно указать путь к папке в которой будет гаходиться проект.
6. Нажмите кнопку ОК, после чего появится окно
7. В появившемся окне гажмите кнопку Finish.
8. Появится новое окно в котором говорится, что сделает IDE после того как будет нажата кнопка ОК. В данном случае сказано, что будет создан скелет проекта консольного приложения со следующими свойствами: чистое консольное приложение, никакие файлы не будут созданы или добавлены в проект. Внизу указана директория в которой будет находиться проект.
9. Нажмите кнопку ОК. В окне проекта появятся две закладки: ClassView (Отображение классов) и FileView (Отображение файлов). Щелкните по закладке FileView, затем на + возле названия файла, в данном случае это My first project
10. В окне проекта появится изображение пустых пока папок: Sourse Files (Исходные файлы) Header Files (Заголовочные файлы) и Resourse Files (Файлы ресурсов).
11. В папке Sourse Files хранятся исходнве файлы программы созданной программистом. Поместим туда для начала пустой файл в котором позднее запишем свою программу. Для этого в строке меню выберем Project, а затем Add To Project и New (Проект→Добавить к проекту→Новый, имеется в виду новый файл). После этого откроется окно в котором нужно выбрать тип файла из предлагаемого списка.
В данном случае следует выбрать файл типа C++SourseFile (Исходный файл С++). Этот тип файлов имеет расширение.cpp. Кроме иого в поле File Name следует указать имя файла. Пусть это будет first (первый). После чего нажмите кнопку ОК.
Теперь все готово для создания программы, которая пишется в поле редактирования.
Мы уже говорили, что проект это совокупность файлов, часть из которых создает программист, а другая чпсть часть создается средой программирования. Представим себе, что нам потребовалось создать и внести в проект второй файл с именем second.
Особенности программирования под Windows.
Язык программирования С++ создавался тогда когда, существовали две операционные системы Dos и Unix. Ни тодна из них не имела развитого графического интерфейса, поэтому, создавая программу программист был вынужден создавать интерфейс для пользователя, чтобы тот смог в дальнейшем работать с этой программой. Появление Windows в значительной степени упростило эту задачу. В самом деле, Windows имеет разветвленный графический интерфейс прикладного программирования (Application Programming Interface – API), позволяющий создавать окна, меню, кнопки, полосы прокрутки и т.п. API – это набор необходимых функций с помощью которых любое приложение может взаимодействовать с операционной системой. API – это своего рода связывающее звено между приложением и операционной системой. API для Win32 содержит более 2000 функций, несколько сотен сообщений, констант, макросов. Было бы нелепо создавать все это заново, вместо того, чтобы воспользоваться имеющимися разработками. Однако для того, чтобы это сделать нужно иметь некоторые представления о механизме работы ОС Windows. Рассмотрим лишь некоторые основные возможности этой операционной системы.
Язык программирования это набор правил, позволяющих писать инструкции для компьютера. В свою очередь компьютер это процессор и память. Все остальное – жесткий диск, дисководы, клавиатура, экран, принтер, и т.д. это устройства, которых компьютер может и не иметь. Иначе говоря, язык программировании предназначен для работы с процессором и памятью. Еще недавно использование такого подхода при создании программ было вполне оправдано. Операционная система, получив команду на выполнение программы, предоставляла последней компьютер в полное распоряжение, а та ипользовала его до своего заершения если оно было предусмотрено. Однако появление операционных систем Windows32 полность изменило технологию исполнения программ. Теперь выполнение прогаммы находится под постоянным контролем операционной системы.
В отличие от предшествующих операционных систем Win32 является многозадачной, т.е. имеет возможность одновременного выполнения нескольких задач. Впрочем, это только кажущаяся одновременность. На самом деле один процессор может только переключаться от выполнения одной задачи к другой, но операционная система сама решает какой программе предоставить в распоряжение процессор. Подобная организация позволяет, выполнять одновременного нескольких программ, и не допускает возможности полного захвата ресурсов компьютера одной задачей, защищая, таким образом, систему от "зависания" (хотя на практике это не всегда так).
Выполняемая задача, или как принято говорить в Win32 процесс, может быть разбита на несколько одновременно выполняющихся подзадач, которые называются потоками. При этом основной поток может продолжать общаться с пользователем, в то время как другие заняты выполнением возложенных на них функций.
Все потоки, принадлежащие одному процессу, выполняются в одном адресном пространство пространстве и имеют общие с этим процессом код, ресурсы и глобальные переменные. Для того чтобы несколько потоков слаженно решали поставленные задачи и не мешали друг другу при использовании каких-то общих ресурсов, применяется синхронизация потоков. Синхронизация может потребоваться, например, в случае, когда один из потоков должен дождаться завершения какой-то операции, выполняемой другим потоком, или когда потоки работают с ресурсом, способным одновременно обслуживать лишь один из них. Поскольку потоки выполняются в условиях вытесняющей многозадачности, функции их синхронизации берет на себя операционная система. Для управления потоками в Windows используются специальные флаги, на которых основано действие нескольких механизмов синхронизации.: семафоры (semaphores), исключающие (mutex) семафоры, события (event), критические секции (critical section).
Win 32 расчитана на оперативную память до 4Ггб. Для большинства персональных компюютеров это слишком большая память, поэтому вместо оперативной памяти программам предоставляется жесткий диск или иначе виртуальная оперативная память. Конечно быстродействие последней намного ниже. Один и тот же процесс может использовать частично оперативную память, а частичео виртуальную память. Операционная система следит как часто исполняемому процессу требуется оперативная память, и в зависимости от частоты обращения к ней соотношения между предоставляемой оперативной памятью и виртуальной памятью может быть изменено в любую сторону.
В Win32 каждый процесс имеет свое адресное пространство, поэтому одновременно выполняемые приложения не могут случайно повредить данные друг друга. Однако часто возникает необходимость в обмене информацией или процессами. Для этой цели в Win32 предусмотрены специальные способы, позволяющие приложениям получать совместный доступ к каким-либо данным.
Один из способов заключается в создании "Почтового ящика" (mailslot) — специальной структуры в памяти, имитирующей обычный файл на жестком диске. Приложения могут помещать данные в "ящик" и считывать их из него. Когда все приложения, работающие с ящиком, завершаются, "почтовый ящик и данные, находящиеся в нем, удаляются из памяти.
Другой способ заключается в организации коммуникационной магистрали -"канала" (pipe), соединяющего процессы. Приложение, имеющее доступ к каналу с одного его "конца", может связаться с приложением, имеющим доступ к каналу с другого его "конца", и передать ему данные. Канал может выделять приложениям односторонний или двусторонний доступ. При одностороннем доступе одно приложение может записывать данные в канал, а другое — считывать; при двустороннем — оба приложения могут выполнять операции чтения/записи. Существует возможность организовать канал, коммутирующий сразу несколько процессов.
Таким образом, особенностью операционной системы Win32 является непрерывный обмен сообщениями между потоками и системой. Поэтому создание программ под Windows имеет свои особенности, связанные именно с обработкой сообщений.