Лабораторная работа 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; }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Создать стек слов. Удалить все слова, пока не встретится слово заданной длины.