Для ряда натуральных чисел длиной N>2 представленного в виде списка, построить последовательность: A1*An, A2*A(n-1), . . . An*A1.
Задача № 5 (Простые списки) (см. "Сборник задач для начинающего программиста")
Алгоритм:
1. Создадим список используя классы:
a) класс TList -- собственно список;
b) класс TItem -- элемент списка, содержащий какую-то информацию и ссылку на след. элемент;
c) описываем конструкторы и методы (добавление эл-та в список, печать списка);
d) строим список используя метод добавления эл-та.
2. Строим необходимую последовательность A1*An, A2*A(n-1), . . . An*A1:
a) создаём новый список;
b) заводим указатели на начало/конец исходного списка и идём по ним вперёд/назад (до тех пор, пока они на что-то указывают), на каждом шаге перемножая хранящиеся в соответствующих ячейках числа и добавляя произведение в результирующий список.
c) выводим результирующий список на экран с помощью описанного нами ранее метода.
#include <stdio.h>
int N, M;
// Элемент списка (однонаправленного)
class TItem {
public:
TItem();
int info;
TItem* next;
} ;
// - - - - - - - - - - - -
// Собственно список
class TList {
private:
TItem* first;
TItem* last;
public:
TList();
TItem* First();
TItem* Last();
void AddItem(int a);
void Print();
} ;
// - - - - - - - - - - - -
TList sourceList, resultList;
int main() {
printf("N = ");
scanf("%d", &N);
for(int i=0; i<N; i++) {
scanf("%d", &M);
sourceList.AddItem(M);
}
printf("Souce list: ");
sourceList.Print();
// - - - - АЛГОРИТМ - - - -
TItem *p1 = sourceList.First(), //указатель на начало
*p2, //указатель, кот. проходит путь от начала к концу
*p2Temp = sourceList.Last()->next; //указатель на следующий элемент после последнего
while( p1 != NULL ) {
p2 = sourceList.First(); //устанавливаем *p2 в начало списка
while(p2->next != p2Temp) { //идём "вперёд", пока следующим после *p2 элементом не будет *p2Temp
p2 = p2->next;
}
resultList.AddItem( (p1->info) * (p2->info) ); //получаем необходимые эл-ты нового списка
p1 = p1->next; //вперёд по p1
p2Temp = p2; //фактически на элемент назад от p2Temp
}
// - - - - - - - - - - - -
printf("Result List: ");
resultList.Print();
return 0;
}
// - - - - - - - - - - - -
// Конструкторы и методы
TItem::TItem() {
info = 0;
next = NULL;
}
TList::TList() {
first = NULL;
last = NULL;
}
// Метод. Добавляет новый элемент в список
void TList::AddItem(int a) {
TItem* temp = new TItem();
temp->info = a;
if(!first) {
first = temp;
}
else {
last->next = temp;
}
last = temp;
}
// Метод. Выводим список на экран
void TList::Print() {
TItem* temp;
temp = first;
while(temp != NULL) {
printf("%d ", temp->info);
temp = temp->next;
}
printf("\n");
}
// Методы (фактически свойства), возвращающие первый и последний элемент списка
TItem* TList::First() {
return first;
}
TItem* TList::Last() {
return last;
}
// - - - - - - - - - - - -