Лекция 3 - Массивы и указатели

Массивы

Одномерные массивы
int a[10];
Нумерация индекса начинается с нуля!
В описании указывается число элементов, а не верхняя граница
Выход за пределы индекса – одна из самых распространенных ошибок!

Многомерные массивы
Нумерация всех индексов начинается с нуля!
int a[20][8];

Классические задачи, возникающие при работе с массивами
Ввод/вывод
(сохранение в файл, передача по сети и т.п.)
Сортировка
(упорядочение по какому-либо признаку, не прибегая к дублированию массива)
Поиск
(найти номер элемента массива по его значению)

Линейная сортировка
Число просмотров ~ ½ (N-1)2
Число перестановок ~ ¼ (N-1)2

Сортировка «пузырьком»
Число просмотров ~ ½ (N-1)2
Число перестановок ~ ¼ (N-1)2
Можно остановится, как только не будет ни одной перестановки

Ввод массива
#define N 10
#include
main()
{
int a[N],x;
int i,j;
/* Ввод массива */
for (i=0; i
{ printf("a[%d]=",i);
scanf("%d",&a[i]);
}

Сортировка массива
/* Линейная сортировка массива */
for (i=0; i
for (j=i+1; j
if (a[i]>a[j])
{x=a[j];
a[j]=a[i];
a[i]=x;
}

Вывод массива
/* Вывод отсортированного массива */
for (i=0; i printf("\n");
return 0; // Код возврата
}

Вся программа целиком
/* Сортировка массива */
#define N 10
#include
main()
{
int a[N],x; int i,j;
/* Ввод массива */
for (i=0; i
{ printf("a[%d]=",i);
scanf("%d",&a[i]);
}
/* Вывод исходного массива */
for (i=0; i
printf("\n");
/* Линейная сортировка массива */
for (i=0; i
for (j=i+1; j
if (a[i]>a[j]) {x=a[j]; a[j]=a[i]; a[i]=x; }
/* Вывод отсортированного массива */
for (i=0; i
printf("\n");
return 0; // Код возврата
}

Бинарный поиск
L=0; R=9; N=(L+R)/2; // N==4; A[N]==55; A[N]<72
L=N+1; R=9; N=(L+R)/2; // N==7; A[N]==73; A[N]>72
L=5; R=N; N=(L+R)/2; // N==6; A[N]==72;

Бинарный поиск
// Бинарный поиск элемента массива равного b
int L, R, n; bool f = true;
L=0; R=N-1;
do {
n=(L+R)/2;
if (a[n]==b) { f=false; break; }
if (a[n]
}
while (L<=R);
if (f) n=-1;
}

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

char str[12] = "Borland C++";
Ввод строки с клавиатуры:
scanf("%s",str); или gets(str);
Вывод строки: printf("%s",str); или puts(str);
Строка символов – массив

Функции для работы со строками
strcpy(s1,s2) – копирует содержимое строки s2 в s1, возвращает указатель на s1
strcat(s1,s2) – присоединяет строку s2 к s1, возвращает указатель на s1
strlen(s1) – возвращает длину строки, последний нулевой байт не учитывается
strcmp(s1,s2) – сравнивает строки, возвращает положительное, нулевое или отрицательное значение

Простейшая программа работы со строками
/* Подсчет количества слов */
#define N 80
#include
#include
main()
{
char s[N];
int i;
int k=0;
printf("\nEnter a string: ");
gets(s);
strcat(s," ");
printf("\n\"%s\"\n%d characters\n",s,strlen(s));
for (i=0; i
if ((s[i]!=' ') && (s[i+1]==' ')) k++;
printf("The string contains %d words.\n",k);
}

Копирование строки
while (s2[i]=s1[i]) i++;
или
while (s2[i]=s1[i++]);

Указатели

Типизированные указатели
char *c; // указатель на char
int *i, j; // указатель на int и просто int
i=&j; // i присвоить адрес j
*i=1; // разыменованный указатель j=1

Указатели на void
void *p; // нетипизированный указатель
float *pf, f; // типизированный указатель
pf=&f; // pf присвоить адрес f
p=pf; // одному указателю присвоить значение другого
pf=(float *) p; // явное указание типа при разыменовании

Указатели и массивы
int a[10], * p;
char *p;
char str="Strings With Capital Words";
p=str;
while (*p) putc(*p++);

Указатели и массивы

Массивы указателей
char *ext[]={"exe", "com", "dat", "c", "pas", "cpp"}
int **p;
printf("%s",ext[0]);

Динамическое размещение данных
Неинициализированный указатель
int *p;
Выделение памяти (N элементов)
p=malloc(sizeof(int)*N);
Использование
p[i] либо *(p+i)
Освобождение памяти
free(p);

Динамическое создание двумерного массива
#include
#include
main()
{
int M; // Число строк
int N; // Число столбцов
int i,j; // Индексы для цикла for
int **a; // Двумерный массив
printf("\nEnter M: "); scanf("%d",&M);
printf("\nEnter N: "); scanf("%d",&N);
a=(int**) malloc(sizeof(int*)*M);
for (i=0; i
for (i=0; i
for (j=0; j
for (i=0; i
{ for (j=0; j
printf("\n");
}
}