Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Поиск в массиве заданного элемента




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

Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.

В листинге 5.3 приведен пример поиска заданного элемента массива простым перебором. Перебор элементов массива осуществляется инструкцией while, в теле которой инструкция if сравнивает текущий элемент массива с образцом и прерывает цикл с помощью оператора break, если текущий элемент и образец равны.

// poiskOpredElementa.cpp: Defines the entry point for the console application.

//Листинг 5.3. Простой перебор

 

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

 

int main(int argc, char* argv[])

{

const int SIZE =10;//razmer massiva

int a[SIZE];

// vvod massiva

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

{

a [i]= 1 + rand () % 10;//massiv tselyh chisel

cout << a[i] << '\t';

} // end for

 

int obr; // obrazets dlya poiska

 

// vvod obraztsa dlya poiska

cin >> obr;

 

// poisk zadannogo elementa massiva pereborom

int i=0;

while(i <= SIZE-1)

{

if (a[i]==obr)

{

cout << "Sovpadenie s elementom nomer"

<< i <<"\t" << a[i]<<endl;

break;

} // end if

else

if (i==SIZE-1)

cout <<"i= " << i << "sovpadeniya net!";

i++;

} // end while

getch();

return 0;

}

 

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

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

a[1] < a[2] < … < a[size]

где size — верхняя граница индекса массива.

Существует много методов (алгоритмов) сортировки массивов. Рассмотрим один из них - метод прямого выбора.

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.

2. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.

3. И так далее до предпоследнего элемента.

В листинге 5.4 приведена реализация этого метода.

 

// sortArr.cpp: Defines the entry point for the console application.

//

//Листинг 5.4. Сортировка массива прямым выбором

 

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

 

int main(int argc, char* argv[])

{

// vvod massiva

int a[]={5,3,17,39,33,1,2,16,18}; // massiv tselyh chisel

const int SIZE = sizeof(a)/sizeof(int);// razmer massiva

cout <<"SIZE =" <<SIZE <<endl;

 

int min; // nomer min elementa

int buf; // bufer, ispol'zuemyi pri obmene elementov massiva

int j; // nomer elementa, sravnivaemogo s min

 

for (int i=0; i<=SIZE-2; i++)

{

min=i;

for (j=i+1; j<=SIZE-1; j++)

if (a[j] < a[min])

min=j;

 

buf= a[i];

a[i]=a[min];

a[min]=buf;

} // end for i

for (int k=0; k<=SIZE-1; k++)

{

if (k==0) cout << "\nelementy massiva \n\n";

cout << a[k] << endl;

} // end for k

getch();

return 0;

}

 

Строки

 

Безусловно, наиболее важным применением одномерных массивов является создание символьных строк. С++ поддерживает строки двух видов. Первый, наиболее часто используемый, — это строка с завершающим нулем или, другими словами, массив символов, заканчивающийся нулем. Строка с завершающим нулем содержит символы, образующие эту строку, за которыми помещается ноль. Такие строки пользуются чрезвычайно широко, так как они обеспечивают высокий уровень эффективности и предоставляют программисту возможность выполнять разнообразные строковые операции. Когда программист на С++ использует термин "строка", он (или она) обычно имеет в виду и именно строку с завершающим нулем. Второй вид строк, определенный в С++ — это класс string, который входит в библиотеку классов С++. Таким образом, string не является встроенным типом. Класс string позволяет использовать объектно-ориентированный подход при обработке строк, однако он используется не так широко, как строка с завершающим нулем. Здесь мы рассмотрим первый вид строк.

 






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

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных