Лекция 2. Основные определения языка высокого уровня (стр. 13 )

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

#include <iostream. h>

#include <iomanip. h>

void MassOut(int m[], int r, int c)

{

int i, j;

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

{

cout << endl;

for(j=0; j<c; j++)

cout << m[i*c+j] << " " ;

}

cout << endl;

}

void main(void)

{

int mas1[2][3] = {{1, 2, 3}, {4, 5, 6}};

int mas2[3][4] = {{1, 2, 3, 5},{4, 7}};

MassOut(mas1[0], 2, 3);

MassOut(mas2[0], 3, 4);

cin >> mas1[0][0];

}

mas1[0] — указатель на первую строку массива, т. е. на одномерный массив.

mas1[1] — указатель на вторую строку массива.

mas1 — адрес ячейки памяти, где начинается массив (указатель на первую строку массива), то есть mas1 равнозначно &mas1[0].

Задачи

185. Написать функцию, которая вычисляет объем цилиндра. Параметрами функции должны быть радиус и высота цилиндра.

186. Написать функцию, которая возвращает максимальное из двух целых чисел, полученных в качестве аргумента.

187. Написать функцию, которая сравнивает два целых числа и возвращает результат сравнения в виде одного из знаков: >, < или =.

188. Написать функцию, которая вычисляет сопротивление цепи, состоящей из двух резисторов. Параметрами функции являются величины сопротивлений и тип соединения (последовательное или параллельное). Функция должна проверять корректность параметров: если неверно указан тип соединения, то функция должна возвращать - 1.

190. Написать функцию Procent, которая возвращает процент от полученного в качестве аргумента числа.

191. Написать функцию "Факториал" и программу, использующую эту функцию для вывода таблицы факториалов.

192. Написать функцию Dohod, которая вычисляет доход по вкладу. Исходными данными для функции являются: величина вклада, процентная ставка (годовых) и срок вклада (количество дней).

193. Написать функцию glasn, которая возвращает 1, если символ, полученный функцией в качестве аргумента, является гласной буквой русского алфавита, и ноль — в противном случае.

194. Написать функцию sogl, которая возвращает 1, если символ, полученный функцией в качестве аргумента, является согласной буквой русского алфавита, и О — в противном случае.

195. Написать функцию, которая возвращает преобразованную к верхнему регистру строку, полученную в качестве аргумента.

196. Написать функцию, обеспечивающую решение квадратного уравнения. Параметрами функции должны быть коэффициенты и корни уравнения. Значение, возвращаемое функцией, должно передавать в вызывающую программу информацию о наличии у уравнения корней: 2 — два разных корня, 1 — корни одинаковые, О — уравнение не имеет решения. Кроме того, функция должна проверять корректность исходных данных. Если исходные данные неверные, то функция должна возвращать - 1.

197. Написать функцию, которая выводит на экран строку, состоящую из звездочек. Длина строки (количество звездочек) является параметром функции.

198. Написать функцию, которая выводит строку, состоящую из одинаковых символов. Длина строки и символ являются параметрами процедуры.

199. Написать функцию, которая вычисляет объем и площадь поверхности параллелепипеда.

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

203. Написать программу, реализующую игру "21". Действия по выдаче очередной карты игроку и компьютеру реализуйте в виде функции.

Сортировка данных в массиве

Имеется массив m[10]. Необходимо отсортировать элементы в возрастающем порядке.

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

Сначала программа сравнивает a[0] и a[1], затем a[1] и a[2], затем a[2] и a[3] и т. д. до тех пор, пока проход не закончится сравнением a[8] и a[9]. Хотя элементов 10 проводится 9 сравнений. При первом проходе самое большое число переместится в самую последнюю позицию a[9]. При втором проходе второе по большинству значение гарантированно опустится в предпоследнюю позицию a[8]. При девятом проходе девятое значение опустится в позицию a[1]. Это приведет к тому, что самое маленькое число окажется в позиции a[0]. Таким образом, для сортировки 10 значений необходимо 9 проходов. Перестановка выполняется тремя присваиваниями через промежуточную переменную. Передавать массив в функцию как const нельзя.

#include <iostream. h>

#include <iomanip. h>

void InputMass(int m [10], const int n)

{

for(int i=0; i<n; i++) cin >> m[i];

}

void SortMass(int m [10], const int n)

{

int i, j, temp;

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

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

{

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

{

tmp = m[i];

m[i] = m[j];

m[j] = tmp;

}

}

}

void OutMass(const int m[], const int n)

{

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

cout << setprecision(3) << setiosflags(ios::fixed | ios::showpoint)

<< m[i] << " ";

}

void main(void)

{

int n[10]={5, 3, 2, 1, 5, 6, 8, 9, 8, 6};

InputMass(m, 10);

SortMass(m, 10);

OutMass(m, 10);

}

Определить: находится ли в массиве число k.

#include <iostream. h>

#include <iomanip. h>

void InputMass(int m[10], const int n)

{

for(int i=0; i<n; i++) cin >> m[i];

}

bool FindMass(const int m[10], const int n, const int k)

{

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

if (a[i] == k)

return true;

return false;

}

int Input()

{

cout << "Введите число для поиска";

int k;

cin >> k;

return k;

}

void main(void)

{

int n[10]={5, 3, 2, 1, 5, 6, 8, 9, 8, 6};

InputMass(m, 10);

int k = Input();

if (Find(m, 10, k)) cout << "Содержится";

else cout << "Не содержится";

}

Лекция 11. Динамические структуры данных

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

int m[100];

T a;

или во время выполнения программы.

int * m;

m = new double[100];

T * a;

a = new T;

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

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

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

Динамические структуры широко используют и для более эффективной работы с данными, размер которых известен, поскольку динамические структуры данных по сравнению с одномерными массивами позволяют за меньшее время удалять и добавлять элементы в произвольную позицию,

переставлять элементы.

Линейные списки

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

Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный).

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

Над списками можно выполнять следующие операции:

— добавление элемента в список (в произвольное место);

— чтение элемента из произвольного места;

— удаление элемента из произвольного места;

— поиск элемента с заданным ключом;

— упорядочивание списка по ключу и т. д.

Для простоты предположим, что список состоит из целых чисел. Тогда каждый элемент списка помимо целого числа должен содержать указатель на следующий элемент и указатель на предудущий элемент.

Введем класс для абстракции "элемент списка":

class CItem2

{

public:

int el;

CItem * next;

CItem * prev;

};

Тогда класс "Двунаправленный список" будет иметь следующий вид. Он должен содержать указатель на первый элемент, конструктор и функции. Для удобства можно завести указатель на последний элемент списка. Для удобства можно завести переменную под количество элементов списка.

class CList2

{

CItem2 * first;

CItem2 * end;

int count;

public:

CList2(void);

void AddToEnd(int a);

void Add(int i, int a);

CItem2 * GetLast(void);

CItem2 * Get(int i);

int DelLast(void);

int Del(int i);

CItem2 * find(int kl);

int Sort(void);

void Show(void);

};

CList2::CList2(void)

{

first = NULL;

end = NULL;

count =0;

}

void CList2::AddToEnd(int a)

{

CItem2 * it = new CItem2; //нельзя писать CItem2 it;

end->next = it;

it->prev = end;

end = it;

++count;

}

void CList2::Add(int i, int a)

{

if (i>count) then return; //или throw "неверный индекс"

int j=1;

CItem2 * it = first;

while (j<i)

{

it = it-> next;

j++;

}

itprev = it->prev;

itnext = it->next;

CItem2 * itins = new CItem2;

itins->next = itnext;

itins->prev = itprev;

itprev->next = itins;

itnext->prev = itins;

if (it == end) end = it;

if (it == begin) begin = it;

++count;

}

CItem2 * CList2::GetLast(void)

{

return end;

}

Стек

stack. h

---------

#ifndef __STACK_H__

#define __STACK_H__

class CItem

{

public:

int el;

CItem * next;

};

class CStack

{

CItem * first;

public:

CStack(void);

void Push(int a);

int Pop(void);

int Get(void);

void Show(void);

};

#endif

stack. cpp

----------

#include "stdafx. h"

#include "stack. h"

#include <iostream. h>

//using namespace std;

CStack::CStack(void)

{

first = NULL;