§6. Сравнительный анализ списков.

По-прежнему будем рассматривать однонаправленный список. В следующей таблице показано, с чем такой список в зависимости от информационной части его элемента можно сравнивать.

Информационная часть элемента списка

С чем сравниваем

1) Одно число. 2) Один символ. 3) Одномерный статический массив. Одномерный статический массив. 4) Строка. 5) Вложенная структура или несколько полей.

Одномерный статический или динамический числовой массив. Одномерный статический или динамический символьный массив, то есть строка. Полностью статическая матрица. Количество строк и количеством элементов в каждой строке — константы. Частично динамическая матрица. Количество строк — переменная, а количество элементов в каждой строке — константа. Статический или динамический массив строк. Статический или динамический массив структур.

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

Сравним список, в информационной части элемента которого одномерный статический массив, со статической матрицей с одинаковым количеством элементов в каждой строке.

Память для элементов списка выделяется на этапе выполнения, то есть динамически, а для матрицы — на этапе компиляции. При необходимости память для элементов списка можем освободить (см удаление). Для статической матрицы это сделать нельзя, память занята на всё время выполнения функции (или блока). В этом преимущество списков независимо от характера задачи.

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

Преимущество списков проявляется, если надо корректировать матрицу, в частности, удалять или вставлять строки. Какие проблемы возникают, например, при удалении строки статической матрицы? Для этого надо физически переместить поэлементно несколько строк “вверх”, на что требуется относительно немалое время (см. 1 семестр). При работе со списком, как было показано выше, достаточно было изменить лишь несколько адресов, а строки матрицы в памяти остаются на своих местах и никуда не перемещаются. Кроме этого, после удаления строки из списка занятую под неё память можно освободить, чего нельзя сделать при работе со статической матрицей.

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

Упражнения, тесты.

1. Пусть объявлена структура для списка:

struct tsp { int num;

tsp *next; } *P, *Q;

Какие из следующих фрагментов допустимы?

1. P=new tsp; P.num=5;

2. P=new tsp; int x=5; P->num=&x;

3. P=new tsp; cin>>(P->num);

4. P=new tsp; P->num=44; Q=P->next; Q->num=P->num;

1. Пусть объявлена структура для списка(см 1) и создан следующий список:

–10 —> 22 —> -3 —> 44 —> 50.

При этом в P — адрес первого элемента с числом -10. Что будет выведено в каждом из приведенных правильных вариантов? Если есть ошибки, указать, в каких вариантах.

1. cout<<P->next->num;

2. Q=P->next; cout<<Q->num;

3. Q=P->next; Q->num=P; cout<<Q->num;

4. Q=P->num; cout<<Q->num;

5. Q=P; Q=Q->next; cout<<Q->next->num;

6. Q=P; Q->next->num=P->num; cout<<Q->num;

3. Пусть объявлена структура для списка (см. 1) и создан список (см.2). При этом в P — адрес первого элемента с числом -10. Дан также код.

Q=P->next; //1

P->next=NULL; //2

delete(P); //3

P=Q; //4

cout<<P->num<< “ “<<Q->num; //5

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

4. Пусть объявлена структура для списка (см. 1) и создан список (см.2). При этом в P — адрес первого элемента с числом -10. Дан также код:

Q=P; //1

while (Q->next->next) Q=Q->next; //1

T=Q->next; //2

Q->next=T->next; //3

delete(T); //4

Q=P; //5

while (Q) //6

{ cout<<Q->num<<” “; //7

Q=Q->next; } //8

cout<< P->num; //9

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

5. Пусть объявлена структура для списка (см.1) и создан список без фиктивного элемента: –10 —> 22 —> -3 —> -44 —> -50 —>66 —> -70. При этом в P — адрес его первого элемента. Дан также код:

Q=P; while ( Q->next )

if (Q->next->num < 0)

{ T=Q->next;

Q->next=Q->next->next;

T->next=NULL;

cout << T->num << " " ;

delete T;

}

Q=Q->next;

};

Что будет выведено? Какой список получится после выполнения приведенного кода?

6. Пусть объявлена структура для списка (см.1) и создан список (см. 2). Дан также код:

Q=new tsp; cin>>Q->num;

Q->next=P; P=Q;

while (P!=NULL) { cout<<P->num;

P=P->next;

}

cout<<Q->num;

Что будет выведено в результате его выполнения, если введём число 6?

7. Пусть объявлена структура для списка (см.1) и создан следующий список без фиктивного элемента:

10 —> 22 —> 3 —> 44 —> 50 —> 66 —> 70.

При этом в P — адрес его первого элемента c числом 10. Дан также код:

Q=P->next;

while (Q)

{ if (Q->num%10)

{ n++;

T=new tsp;

T->num=Q->num*10;

T->next=Q->next;

Q->next=T;

Q=Q->next->next; }

Q=Q->next; }

Какой список получится после выполнения приведенного кода (записать последовательность чисел)?

8. Сравним список, информационная часть элемента которого содержит одномерный статический массив фиксированной размерности, со статической матрицей, количество строк и столбцов которой — константы, и в каждой строке которой одинаковое количество элементов. Выберите правильные утверждения:

1. Память для элементов списка выделяется на этапе компиляции.

2. Память для элементов статической матрицы, количество строк и столбцов которой — константы, выделяется на этапе выполнения.

3. При необходимости память для элементов списка можно освободить.

4. Для статической матрицы освободить память нельзя, она занята на всё время выполнения функции (или блока).

5. Список занимает меньше памяти, чем матрица.

6. В списке все его элементы находятся рядом.

7. В задачах, в которых требуется вставлять, удалять или переставлять строки матрицы, эффективнее использовать списки.

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

Лабораторная работа 8.

Тема: “Списки”.

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

Пример 1. Работа со списком целых чисел в классе.

struct tsp

{ int num; // Информационная часть, состоящая из одного поля.

struct tsp *next; // Адресная часть, состоящая из одного поля.

};

class clsp

{ tsp *P; // Адрес начала списка.

int n; //Количество элементов списка.

public:

// Конструктор для задания количества элементов списка.

clsp(int k) { n=k;}

void CREATE1(); // Создание списка.

void LOOK(); // Просмотр элементов списка (вывод на экран).

/* Метод DEL удаляет все элементы списка, информационная часть которых содержит отрицательные числа (дальше будем писать просто“… отрицательные числа”). Возвращает количество удалённых элементов. */

void DEL (int &);

/* После каждого чётного числа вставляем это же число, увеличенное в 10 раз.*/

void INS ();

// Сортировка списка методом нахождения наименьшего числа.

void SORT();

};

void clsp::CREATE1()

{ tsp *T, *Q;

/* Создаём фиктивный элемент списка, который никогда не удаляем, и перед которым ничего не вставляем. Используется, чтобы вставка в начало списка и удаление первого элемента выполнялись с помощью одинаковых алгоритмов */

T=new tsp;

T->num=0;

P=T;

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

{ // Резервируем память для одного элемента списка.

Q=new tsp;

// Определяем информационную часть нового элемента.

cin>>Q->num;

// “Cоединяем” его с предыдущим элементом.

T->next=Q;

T=Q;

}

/*Последний элемент должен содержать адрес NULL. */

Q->next=NULL;

};

void clsp::LOOK()

{ tsp *Q;

/* Вывод количества элементов, которое после вставки или удаления будет меняться. */

cout<<"\nn="<<n<<endl;

/* Так как в начале списка размещается фиктивный элемент, то переходим на второй, то есть на первый реальный элемент. Фиктивный элемент не выводим. */

Q=P->next;

while ( Q) // или while (Q!=NULL)

{ cout<<Q->num<<" "; // Вывод информационной части

Q=Q->next; // Переход на следующий элемент

}

cout << endl;

};

void clsp::DEL(int &numdel)

{ tsp *T, *Q; numdel=0;

int n2; n2=n; // Запомнили количество элементов до удаления

/* При удалении должны ссылаться на элемент, который предшествует тому, который сначала проверяем на предмет удаления, а затем, возможно, будем удалять. */

Q=P;

cout << " Deleted elements : "<< endl;

while ( Q->next )

if (Q->next->num < 0)

{ n--;

numdel++;

// Удаление элемента.

T=Q->next;

Q->next=Q->next->next;

T->next=NULL;

cout << T->num << " " ;

delete T; // Освобождаем память удалённого элемента

}

else

/* На следующий элемент списка переходим только в случае, если элемент не удаляли. Если бы перешли на следующий элемент и после удаления, то элемент, находящийся после удалённого, не проверяется и, значит, никогда не удаляется. */

Q=Q->next;

if (numdel==n2) cout <<"\n We deleted all elements" ;

};

void clsp::INS()

{ tsp *Q, *T;

/* Так как в начале списка размещается фиктивный элемент, то переходим на второй, то есть на первый реальный элемент. После фиктивного элемента никогда не вставляем. */

Q=P->next;

while (Q)

if (! (Q->num % 2))

{ n++;

// Выделяем память для вставляемого элемента.

T=new tsp;

// Получаем информационную часть вставляемого элемента

T->num=Q->num*10;

/* Вставляем его, то есть “соединяем ” со следующим */

T->next=Q->next;

/* и предыдущим элементом */

Q->next=T;

/* “Обходим” элемент, который вставили, чтобы после него ничего никогда не вставлять. */

Q=Q->next->next;

}

else

// Если не вставляли, переходим на следующий элемент

Q=Q->next;

};

void clsp::SORT()

{ tsp *Q1, *Q2, *Qmin;

Q1=P->next;

while (Q1)

{ /*Находим элемент с минимальной информационной частью, т. е. наименьшее число, начиная с Q1*/

Q2=Q1->next;

Qmin=Q1;

while (Q2)

{ if (Q2->num<Qmin->num)

Qmin=Q2;

// Продолжаем находить минимальное число

Q2=Q2->next;

}

// Переставляем Q1->num и Qmin->num

int temp;

temp=Q1->num;

Q1->num=Qmin->num;

Qmin->num=temp;

// Меняем начало нахождения наименьшего элемента.

Q1=Q1->next;

} };

int main()

{ int n2, ndel, flag;

cout <<endl<< "number of elements n="; cin>>n2;

clsp OBSP(n2); // Создание объекта

OBSP.CREATE1();

cout << endl<<"Looking of elements"; OBSP.LOOK();

flag=1; while (flag)

{ cout << "1 -- DELETE"<<endl<< "2 -- INSERT"<<endl<<

"3 -- LOOK"<<endl<< "4 -- SORT"<<endl<<

"0 -- EXIT"<<endl;

cin>>flag; switch (flag)

{ case 1: OBSP.DEL(ndel);

cout << endl<<" After deleting"<<endl;

if ( !ndel) cout << " We did not change spisok ";

OBSP.LOOK(); break;

case 2: OBSP.INS(); cout << endl<<" After inserting";

OBSP.LOOK(); break;

case 3: OBSP.LOOK(); break;

case 4: cout << endl<<" Before sorting";

OBSP.LOOK(); OBSP.SORT();

cout << endl<<" After sorting"; OBSP.LOOK();

break;

case 0: flag=0; break;

default: cout<<endl<<"Error!!!!! Repeat!!!!"<<endl;

}

}

return 0; }

Пример2. (+) Работа с “матрицей” с разным количеством элементов в строках и хранящейся в виде списка. В информационной части матрицы хранится одна её строка и количество элементов в ней.

struct tsp

{ int num; // Количество чисел в строке матрицы

// Одномерный динамический массив для одной строки матрицы.

int *arr1;

struct tsp *next;

};

class clsp

{ tsp *P;

// Количество строк матрицы, т. е. количество элементов списка.

int n;

public:

clsp(int k)

{ n=k; };

void CREATE1(); // Создание списка.

void LOOK(); // Просмотр списка (матрицы).

void DEL (int, int &);

void INS (int);

};

void clsp::CREATE1()

{ tsp *T, *Q;

// Создаём фиктивный элемент (см. пример 1).

T=new tsp;

T->num=2;

T->arr1=new int[T->num];

for(int j=0; j<T->num; j++)

T->arr1[j]=0;

P=T; // Начало списка

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

{

// Выделяем память для одного элемента списка

Q=new tsp;

cout<<"Number (>0)=";

// Вводим количество элементов строки

cin>>Q->num;

// Выделяем память для одной строки матрицы.

Q->arr1=new int[Q->num];

// Вводим одну строку матрицы

for(int j=0; j<Q->num; j++)

cin>>Q->arr1[j];

/* “Cцепляем” с предыдущим элементом, т. е. “присоединяем” новый элемент в конец списка.*/

T->next=Q;

T=Q;

}

Q->next=NULL;

};

// Вывод матрицы на экран (см. пример 1).

void clsp::LOOK()

{ tsp *Q;

cout<<"\nn="<<n<<endl;

Q=P->next;

while ( Q)

{ cout<<" Number="<<Q->num<<" ";

for(int j=0; j<Q->num; j++)

cout<<Q->arr1[j]<<" ";

Q=Q->next;

cout << endl;

}

cout << endl;

};

/* Функция удаляет те строки матрицы, у которых наибольший элемент < max0, и возвращает количество таких удалённых строк (элементов списка ). */

void clsp::DEL(int max0,int &numdel)

{ tsp *T, *Q;

int n2, MyMax;

n2=n; /* Запомнили “старое” количество строк, чтобы затем сравнить его с количеством удалённых строк. */

numdel=0;

Q=P;

cout << " Deleted elements : "<< endl;

while ( Q->next )

/*Цикл для просмотра списка до конца, анализа каждого элемента и, возможно, его удаления. */

{

// Находим наибольший элемент (MyMax) в одной строке матрицы.

MyMax= Q->next->arr1[0];

for (int j=1; j< Q->next->num; j++)

if (Q->next->arr1[j]>MyMax)

MyMax= Q->next->arr1[j];

// Проверяем условие удаления.

if (MyMax < max0)

{ n--; numdel++;

// Удаление одного элемента списка, т. е. одной строки.

T=Q->next;

Q->next=Q->next->next;

T->next=NULL;

cout<<endl;

// Вывод удалённого элемента, т. е. одной строки.

for(int j=0; j<T->num; j++)

cout<<T->arr1[j]<<" ";

// Освобождаем память для удалённого элемента.

delete T; }

else

// Переходим на следующий элемент, если не удаляли.

Q=Q->next; }

// Если удалили все элементы…

if (numdel==n2) cout <<"\n We deleted all elements" ;

};

/* После строк матрицы, у которых количество элементов < n0, функция вставляет новую введённую с экрана строку с таким же количеством элементов */

void clsp::INS(int n0=2)

{ tsp *Q, *T;

Q=P->next;

while (Q) /* Цикл для проверки всех элементов списка и вставки новых строк матрицы. */

if (Q->num <n0)

{ n++;

// Резервируем память для нового элемента списка.

T=new tsp;

T->num=Q->num;

// Выделяем память для одной строки матрицы.

T->arr1=new int[T->num];

cout<<"\nInput "<< Q->num <<" elements\n";

// Вводим новую строку матрицы

for(int j=0; j<T->num; j++)

cin>>T->arr1[j];

// “Cцепляем” новый элемент со следующим …

T->next=Q->next;

// … и предыдущим элементом.

Q->next=T;

/* “Обходим” элемент, который вставили, чтобы после него ни чего никогда не вставлять. */

Q=Q->next->next; }

else

// Если не вставляли, переходим на следующий элемент.

Q=Q->next; };

int main()

{ int n2,ndel,flag, Max0, Num0;

cout <<endl<< "Number of elements n=";

cin>>n2;

clsp OBSP(n2);

OBSP.CREATE1();

cout << endl<<"Looking of elements";

OBSP.LOOK();

flag=1;

while (flag)

{ cout << "1 -- DELETE"<<endl<< "2 -- INSERT"<<endl<<

"3 -- LOOK"<<endl<< "0 -- EXIT"<<endl;

cin>>flag;

switch (flag)

{ case 1: cout<<"Max0= "; cin>>Max0;

OBSP.DEL(Max0, ndel);

cout << endl<<" After deleting"<<endl;

if ( !ndel) cout << " We did not change spisok ";

OBSP.LOOK(); break;

case 2: cout<<"Num0= "; cin>>Num0;

OBSP.INS(Num0);

cout << endl<<" After inserting";

OBSP.LOOK(); break;

case 3: OBSP.LOOK(); break;

case 0: flag=0; break;

default: cout<<endl<<"Error!!!!! Repeat!!!!"<<endl;

}

}

return 0;

}

Пример3. Работа со стеком строк (+)

struct tsp

{ char *s;

struct tsp *next; };

class spisok

{ struct tsp *P;

int n;

public:

spisok();

void FORM(); // Создание стека

void LOOK(int k=5); // Просмотр стека

int NUMBER(); // Получение количества элементов стека

void INS(); // Вставка одного элемента в начало стека

void DEL(); }; // Удаление одного элемента с вершины стека

spisok::spisok()

{ P=NULL;

};

void spisok::FORM()

{ char *Str; tsp *Q;

Str=new char[80];

cout<<"### - exit\n"; n=0;

while(1)

{ gets(Str);

if (strstr(Str,"###"))break;

Q=new tsp; // Резервируем память для одного элемента стека

// Резервируем память для строки

Q->s=new char[strlen(Str)];

strcpy(Q->s, Str);

Q->next=P; //“Присоединяем” новый элемент к вершине стека

P=Q; // Новый элемент делаем вершиной стека

n++;

};

delete [] Str; //Освобождаем память для введённой строки

};

int spisok::NUMBER()

{ return n; };

// Просмотр указанного (k) количества или всех элементов стека.

void spisok::LOOK(int k)

{ tsp *Q;

cout<<endl;

Q=P; //Переход в вершину стека

for (int i=0;i<k && Q;i++)

{ puts(Q->s);

Q=Q->next; //Переход на следующий элемент стека

}

cout << endl; };

void spisok::INS()

// Аналогично FORM, только без цикла

{ tsp *Q; char *Str;

Str=new char[80];

scanf("%s",Str);

Q=new tsp;

Q->s=new char[strlen(Str)];

strcpy(Q->s, Str);

Q->next=P;

P=Q; n++;

delete [] Str; };

void spisok::DEL()

{ tsp *Q;

Q=P->next; //”Переходим ” на второй элемент стека.

delete P; // Удаляем первый элемент.

P=Q; // Второй элемент делаем первым, т. е. вершиной стека

n--; };

int main()

{ int n2, flag; spisok STECK;

STECK.FORM(); // Создание объекта

STECK.LOOK();

flag=1;

while (flag)

{ cout << "1 -- INSERT"<<endl<< "2 -- DELETE"<<endl<<

"3 -- NUMBER"<<endl<< "4 -- LOOK2"<<endl<<

"0 -- EXIT"<<endl;

cin>>flag;

switch (flag)

{ case 1: STECK.INS(); break;

case 2: STECK.DEL(); break;

case 3: cout<<"\nThere are "<<STECK.NUMBER()<<" elements\n";

break;

case 4: while(1)

{ int n0; n0=STECK.NUMBER();

cout<<"The number of elements for looking<="<< n0<<" ";

cin>>n2;

if(n2<=n0 && n2>0)

{ STECK.LOOK(n2); break; }

else cout<<"There are only "<<n0<<" elements. Repeat! \n";

} break;

case 0: flag=0; break;

default: cout<<endl<<"Error!!!!! Repeat!!!!"<<endl;

} }

return 0; }

Варианты заданий.

1. Задачи первого простого уровня.

   1. Создать список вещественных чисел. Найти разность между наибольшим и наименьшим элементами.

   2. Создать список, в информационной части элементов которого находятся координаты вершин многоугольника плоскости. Найдите периметр многоугольника

   3. Создать список, в информационной части элементов которого находятся координатами вершин многоугольника плоскости. Определите, находится ли точка с заданными координатами на одной из сторон многоугольника.

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

   5. Создать список, в информационной части элементов которого находятся координаты одной точки плоскости. Найти количество точек каждой из четвертей плоскости.

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

   7. Создать список, в информационной части элементов которого находятся координаты одной точки плоскости. найти количество точек, находящихся внутри кольца, ограниченного окружностями с общим центром, радиусы которых r и R (r < R).

8. Создать список целых чисел. Есть ли среди них общий делитель? Есть ли среди них общее кратное?

9. Создать список слов. Найти количество слов, начинающихся и заканчивающихся одинаковой буквой.

10. Создать список слов. Найти и вывести слова, у которых гласных больше половины.

11. Создать список слов. Найти и вывести слова, длина которых меньше средней длины всех слов.

12. Создать список, в информационной части элемента которого одномерный массив фиксированной размерности, т. е. в виде списка представить матрицу, количество строк (элементов списка) которой произвольное, а количество чисел в каждой строке одинаковое и задано в виде константы. Найти количество строк, в которых больше половины чисел имеют значение, меньшее, чем среднеарифметическое данной строки.

13. Создать список, в информационной части элемента которого одномерный массив оценок одного студента фиксированной размерности, т. е. в виде списка представить матрицу, количество строк (элементов списка) которой произвольное, а количество оценок в каждой строке одинаковое и задано в виде константы. Найти количество отличников.

2. Задачи второго среднего уровня.

1. Из не рассортированного списка целых чисел удалить все наибольшие элементы, оставив первый из них.

2. Из рассортированного списка целых чисел удалить все наибольшие элементы, кроме одного.

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

4. В не рассортированный список целых чисел после каждого положительного числа вставить его номер в исходном списке.

5. В не рассортированный список вещественных чисел после каждого максимального числа вставить номер в списке и номер среди максимальных элементов этого же списка.

6. В не рассортированный список вещественных чисел после каждой тройки чисел вставить их среднеарифметическое значение. Если в конце списка осталось меньше трёх чисел, вставить среднеарифметическое значение из двух чисел или вставить последнее число.

7. Создать список, информационная часть каждого элемента которого содержит фамилию и массив из 10 оценок. Из списка удалить двоечников, то есть те элементы, в которых есть хотя бы одна 1 или 2 или 3.

8. Создать список, элементом которого является прямая плоскости y=k*x +b, т. е. два числа k и b. Удалить все прямые, перпендикулярные оси OX.

9. Создать список, элементом которого является прямая плоскости y=k*x +b, т. е. два числа k и b. Удалить все прямые, параллельные первой прямой этого же списка.

10. Создать список, элементом которого являются координаты вершин треугольников на плоскости. Удалить все треугольники с одинаковым наименьшим периметром.

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

12. Создать список, элементом которого являются координаты центра и радиус окружности на плоскости. После каждой окружности первой четверти вставить окружность, центр которой сдвинут на r (радиус) величин вправо.

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

14. Создать список, в информационной части элемента которого одномерный массив фиксированной размерности, т. е. в виде списка представить матрицу, количество строк (элементов списка) которой произвольное, а количество чисел в каждой строке одинаковое и задано в виде константы. Из матрицы удалить все строки, в которых одни нули.

15. Пусть матрица записана в оперативной памяти в виде списка (см. пример 14). Из матрицы удалить строки, у которых первый ненулевой элемент положительный, а последний ненулевой элемент – отрицательный.

16. Пусть матрица записана в оперативной памяти в виде списка (см. пример 14). После каждой строки, содержащей только отрицательные числа, вставить новую строку, которая получается умножением каждого элемента этой строки на (-1).

17. Пусть матрица записана в оперативной памяти в виде списка (см. пример 14). Поменять местами первую строку с той, в которой находится наибольший элемент всей матрицы.

18. Пусть матрица записана в оперативной памяти в виде списка (см. пример 14). Поменять местами строку с наибольшим элементом со строкой с наименьшим элементом матрицы. Если таких строк несколько, т. е. наибольших (наименьших) элементов матрицы несколько и они находятся в разных строках, то переставить любые такие строки.

19. Создать список слов. Из списка удалить слова наименьшей длины, кроме первого.

20. Создать список слов. Из списка удалить слова, у которых гласных больше половины и которые начинаются с гласной буквы.

21. Из введённого текста создать список слов. Из списка удалить те слова, которые начинаются на заданную букву.

22. Создать стек слов. Удалить все слова, пока не встретится слово заданной длины.

С. Задачи повышенной сложности

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

2. Создать список вещественных чисел. После серии подряд идущих повторяющихся чисел вставить количество их повторений.

3. Создать два списка целых чисел. Рассортировать каждый из них, использую алгоритм обмена. Из двух рассортированных списков путём их слияния получить новый рассортированный список, не используя третий раз алгоритм сортировки.

4. Создать список, информационная часть каждого элемента которого содержит фамилию и инициалы студента и массив из пяти оценок. Рассортировать список по категориям (отличники, хорошисты, троечники, двоечники). Внутри каждой категории часть списка должна быть рассортирована в алфавитном порядке фамилий.

5. Создать список, информационная часть каждого элемента которого содержит фамилию и имя студента и массив из пяти оценок. Рассортировать список по среднему баллу. Вставить новые введённые фамилии и их оценки в нужное место списка так, чтобы изменённый список оставался рассортированным.

6. Создать список, в информационной части элемента которого одномерный массив фиксированной размерности, т. е. в виде списка представить матрицу, количество строк (элементов списка) которой произвольное, а количество чисел в каждой строке одинаковое и задано в виде константы. Рассортировать строки матрицы по возрастанию их первых элементов. Для сортировки использовать алгоритм выбора.

7. Создать список слов. Рассортировать список (слова) по их длине. Слова с одинаковой длиной сортировать по двум первым буквам.

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

Г л а в а 5

ФАЙЛЫ

Что общего во всех изученных ранее темах, методах программирования, алгоритмах и программах? Все они для хранения входной и выходной информации использовали только оперативную память. Как для простых, так и для структурированных данных (статические и динамические массивы, строки, структуры и другие) внешнюю память мы не использовали. В этой главе будет изучен один из методов программирования для работы с информацией разного типа, сохранённой на внешнем устройстве в файлах. Рассматривается создание, чтение, анализ и корректировка файлов.

Есть несколько подходов для работы с файлами.

Первый из них основан на использовании самостоятельных, то есть не включённых ни в какие стандартные классы, встроенных функций для работы с файлами. Набор таких функций называют системой ввода-вывода классического “старого” языка С. Язык C++ также поддерживает весь набор таких функций.

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

Нельзя здесь не упомянуть о базах данных и системах управления ими (СУБД). В отличие от предыдущих двух способов этот предполагает работу не с одним или двумя небольшими файлами, а с несколькими взаимосвязанными большими по объёму файлами, которые объединяются в базу данных. При этом можно использовать как самостоятельные СУБД (системы управления базами данных), так и встроенные в другие системы (например, Delphi, Builder).

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