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

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

Ссылка (reference) является альтернативным именем объекта.

Объявление ссылок:Для каждого типа T есть такой тип T&, называющийся «ссылка на T».

int i = 1;

int& r = i; //r ссылаетсяна i(целое)

r = 25; //i = 25

i = 50; //r = 50

floatf = 3.14;

float& r2 = f; //r2 ссылаетсяна f (вещественное)

r2 = sin(1.25); //тоже, что и f = sin(1.25)

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

Различия ссылок и указателей: в отличие от указателей, ссылкам не требуется дополнительной памяти; доступ к объекту производится напрямую (разыменовывания не требуется):

int main(...)

{

int i = 1;

int& r = i; // r и i ссылаются на одно и то же целое

int* x = &i; // x указывает на ячейку с r и i

r = 2; // i = 2;

*x = 5; // i = 5;

}

Связь между ссылкой и объектом задается в момент инициализации и не может быть изменена во время выполнения программы:

int i = 1, k = 2;

int& r = i; // r и i ссылаются на одно и то же целое

int* x = &r; // x указывает на ячейку с r и i

r = 2; // i = 2

*x = 5; // i = 5

x = &k; // x указывает на ячейку с k

*x = 7; // k = 7

// ...

r = k; // i = 7 (присваивает значение k переменной i)

Область применения – изменяемые параметры функций:

void addOneVal(int x)

{

x = x + 1; //увеличить значение x на 1

}

void addOneRef(int& x)

{

x = x + 1; //увеличить значение x на 1

}

int _tmain(int argc, _TCHAR* argv[])

{

int i = 1;

addOneVal(i); //i = 1 - значение i не изменилось

addOneRef(i); //i = 2(!) – значение i изменилось!

return 0;
}

2. Псевдокод. Определение, примеры хорошего и плохого псевдокода.

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

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

Пример плохого псевдокода:

Выделить структуру Student посредством
malloc()
Если malloc() вернет NULL, то
вернуть 0
Увеличить номер студента на 1
Вызвать FillStudent() для заполнения полей
Вернуть указатель на выделенный экземпляр

Пример хорошего псевдокода:

1. Выделить структуру для студента.

2. Если структура может быть выделена:

3. Учесть, что имеется еще один студент;

4. Заполнить поля структуры стандартными значениями;

5. Хранить данные студенте в вызывающей программе.

6. Конец «если».

7. Вернуть true, если студент был создан; иначе вернуть false.

Бинарные файлы. Преимущества и недостатки использования бинарных файлов, функции для записи и чтения бинарных файлов в языке C.

Бинарный (двоичный) файл:
• Последовательность произвольных байтов.
• Название связано с тем, что байты состоят из бит, т.е. двоичных (binary) цифр.

Текстовые файлы хранят только байты, соответствующие печатным символам таблицы ASCII, в то время как бинарные файлы могут хранить байты с любыми значениями [0...255]. Тестовые файлы можно редактировать в любом текстовом редакторе. Бинарные файлы необходимо редактировать в специальных Hex‐редакторах.

Преимущества:

• Выше скорость загрузки и сохранения данных в бинарном файле.
• Обычно требуется меньший объем дискового пространства для хранения данных.
• Проще реализация для программистов.

Недостатки:

• Проблемы с переносимостью на другую платформу.
• «Закрытость» данных: затруднено редактирование вне приложения.
• Негибкость: при смене порядка следования блоков файл становится нечитаемым.

Запись в бинарный файл:	Чтение из бинарного файла:
int fwrite( void *buffer, / *откуда* / int size, /*размер*/ int count, /*кол‐во*/ FILE *stream/*куда*/ );	int fread( void *buffer, /*куда*/ int size, /*размер*/ int count, /*кол‐во*/ FILE *stream/*откуда*/ );

Примерсохраненияцелогочиславбинарныйфайл:

#include<stdio.h>

// ...

FILE* fp = fopen("myFile.dat", "w");

int k = 25;

fwrite(&k, sizeof(int), 1, fp);

Пример чтения числа из бинарного файла:

#include<stdio.h>

// ...

FILE* fp = fopen("myFile.dat", "r");

int k = 0;

fread(&k, sizeof(int), 1, fp);

Бинарные файлы. Запись массивов и структур в бинарные файлы. Примеры.

Примерсохранениямассива структурвбинарныйфайл:

#include"stdafx.h"

#include<stdio.h>

// ...

structtovar

{

// ...

};

int _tmain(int argc, _TCHAR* argv[])

{

FILE* fp = fopen("myFile.dat", "wb");

int a = 25; // Количество элементов в массиве структур

tovar *Tov = newtovar[a];

fwrite(&a, sizeof(int), 1, fp);

for (int i = 0; i<a; i++)

fwrite(&Tov[i], sizeof(tovar), 1, fp);

return 0;

}

Пример чтения массива структур из бинарного файла:

#include"stdafx.h"

#include<stdio.h>

// ...

structtovar

{

// ...

};

int _tmain(int argc, _TCHAR* argv[])

{

FILE* fp = fopen("myFile.dat", "rb");

int a = 0; // Количество элементов в массиве структур

fread(&a, sizeof(int), 1, fp);

tovar *Tov = newtovar[a];

for (int i = 0; i<a; i++)

fread(&Tov[i], sizeof(tovar), 1, fp);

return 0;

}

Связныесписки. Добавлениеэлементавначало, вконец, впроизвольную позицию списка. Сравнение с добавлением в массив. Примеры.

Добавление элемента в конец списка:

struct books

{

//…
books* next;

};
books* end(books* book) //Поискконцасписка

{

while (book->next != NULL) //покаестьэлементы

book = book->next; //переходим к следующему элементу

return book;

}
int _tmain(int argc, _TCHAR* argv[])

{
books* start = NULL;//Указатель на первый элемент

books* current = NULL;//Указатель на текущий элемент

if (start == NULL)

{

current = new books;

start = current;

current->next = NULL;

}

else

{

current = end(start);

current->next = new books;

current = current->next;

current->next = NULL;

}
//…
return 0;

}

Добавление элемента в начало списка:

//…
books* tmp = NULL; //Указатель на временный элемент

if (start == NULL)

{//… }

else

{

tmp = new books;

tmp->next = start;

start = tmp;

}
//…
return 0;

}

Добавлениеэлементавпроизвольнуюпозициюсписка:

books* add_rand(books* leftbook, books* newbook) // leftbook - Послекотороговставляем

{ // newbook - Новыйэлемент

if (leftbook != NULL)

{

newbook->next = leftbook->next;

leftbook->next = newbook;

}

returnnewbook;

}

Для вставки элемента в массив нужно:Взять исходный массив;Выделить память под новый массив достаточного размера;Скопировать элементы старого массива в новый;Освободить память занимаемую старым массивом;Присвоить указателю на старый массив, указатель на новый.

Время выполнения операции вставки элемента в произвольную позицию массива и время удаления элемента из произвольной позиции линейно зависит от количества элементов массива. O(n).

Время выполнения операции вставки элемента в произвольную позицию списка и время удаления элемента из произвольной позиции постоянно (т.е. не зависит от количества элементов списка). O(1)

Связныесписки. Удаление элемента из списка. Сравнение с удалением из массива. Примеры.

books* poisk(books* start, intid) // функция поиска элемента списка по номеру

{

while (start != NULL)

{

if (start->nomer == id)

return start;

start = start->next;

}

return NULL;

}

//...

current = poisk(start, id);

tmp = current;

if (tmp == start) //еслипервый

start = current->next;

elseif (tmp->next == NULL) //еслипоследний

{

current = start;

while (current->next->nomer != id)

current = current->next;

current->next = NULL;

}

else //не первый и не последний

{

current = start;

while (current->next->nomer != id)

current = current->next;

current->next = tmp->next;

}

deletetmp;

Для удаления элемента из массива нужно: Взять исходный массив; Выделить память под новый массив достаточного размера; Скопировать элементы старого массива в новый не копируя удаляемый элемент; Освободить память занимаемую старым массивом; Присвоить указателю на старый массив, указатель на новый.

Время выполнения операции вставки элемента в произвольную позицию массива и время удаления элемента из произвольной позиции линейно зависит от количества элементов массива. O(n).

Время выполнения операции вставки элемента в произвольную позицию списка и время удаления элемента из произвольной позиции постоянно (т.е. не зависит от количества элементов списка). O(1)

Связные списки. Обход списка. Сортировка списка. Примеры.

Обход с первого элемента:

books* end(books* start)

{

while (start->next != NULL) //пока есть элементы

start = start->next; //переходим к следующему элементу

returnstart;

}

Сортировка:

structbooks

{

intnomer;

string name;

string author;

int page;

int cost;

books* next;

};

//...

do

{

sortOK = false;

current = start;

while (current->next != NULL)

{

if (current->name > current->next->name)

{

swap(current->name, current->next->name);

swap(current->author, current->next->author);

swap(current->page, current->next->page);

swap(current->cost, current->next->cost);

sortOK = true;

}

current = current->next;

}

} while (sortOK);

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

Ссылка (reference) является альтернативным именем объекта.

Объявление ссылок:Для каждого типа T есть такой тип T&, называющийся «ссылка на T».

int i = 1;

int& r = i; //r ссылаетсяна i(целое)

r = 25; //i = 25

i = 50; //r = 50

floatf = 3.14;

float& r2 = f; //r2 ссылаетсяна f (вещественное)

r2 = sin(1.25); //тоже, что и f = sin(1.25)

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

Различия ссылок и указателей: в отличие от указателей, ссылкам не требуется дополнительной памяти; доступ к объекту производится напрямую (разыменовывания не требуется):

int main(...)

{

int i = 1;

int& r = i; // r и i ссылаются на одно и то же целое

int* x = &i; // x указывает на ячейку с r и i

r = 2; // i = 2;

*x = 5; // i = 5;

}

Связь между ссылкой и объектом задается в момент инициализации и не может быть изменена во время выполнения программы:

int i = 1, k = 2;

int& r = i; // r и i ссылаются на одно и то же целое

int* x = &r; // x указывает на ячейку с r и i

r = 2; // i = 2

*x = 5; // i = 5

x = &k; // x указывает на ячейку с k

*x = 7; // k = 7

// ...

r = k; // i = 7 (присваивает значение k переменной i)

Область применения – изменяемые параметры функций:

void addOneVal(int x)

{

x = x + 1; //увеличить значение x на 1

}

void addOneRef(int& x)

{

x = x + 1; //увеличить значение x на 1

}

int _tmain(int argc, _TCHAR* argv[])

{

int i = 1;

addOneVal(i); //i = 1 - значение i не изменилось

addOneRef(i); //i = 2(!) – значение i изменилось!

return 0;
}

2. Псевдокод. Определение, примеры хорошего и плохого псевдокода.

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

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

Пример плохого псевдокода:

Выделить структуру Student посредством
malloc()
Если malloc() вернет NULL, то
вернуть 0
Увеличить номер студента на 1
Вызвать FillStudent() для заполнения полей
Вернуть указатель на выделенный экземпляр

Пример хорошего псевдокода:

1. Выделить структуру для студента.

2. Если структура может быть выделена:

3. Учесть, что имеется еще один студент;

4. Заполнить поля структуры стандартными значениями;

5. Хранить данные студенте в вызывающей программе.

6. Конец «если».

7. Вернуть true, если студент был создан; иначе вернуть false.