Пусть L обозначает кольцевой двунаправленный список с заглавным звеном. Описать функцию или процедуру, которая подсчитывает количество элементов списка L, у которых равные соседи. Задача №13 (Двунаправленные списки). (см. "Сборник задач для начинающего программиста")
Алгоритм:
1. Создаем шаблон структуры данных для списка;
2. Заполняем список длины N (опеределяется пользователем) случайными числами от 0 до 3;
3. Описываем функцию перебора списка от заглавного звена, до элемента, сслыка next которого указывает на заглавный (один полный проход списка) и подсчета количества элементов, у которых хотя бы один из соседей равен текущему элементу;
4. Выводим значение счетчика на экран.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
struct tList { //Объявляем структуру
int data;
tList *next;
tList *prev;
} *first, *last, *l; //экземпляры труктуры данных
/*функция заполнения списка*/
void Fill_List (int size) {
int i, stime;
long ltime;
/* Получение текущего времени для генератора случайных чисел */
ltime = time(NULL);
stime = (unsigned) ltime/2;
srand(stime);
if (first == NULL) { //Первый элемент
first = new tList;
first -> data = rand() % 3;
last = first;
printf ("%d ", first -> data);
}
for (i=1; i<size; i++) { //Последующие элементы
l = new tList;
l -> data = rand() % 3;
l -> next = NULL;
l -> prev = last;
last -> next = l;
last = l;
printf ("%d ", l -> data);
}
first -> prev = last;
last -> next = first;
}
int Counter (tList *first, tList *last) {
int c = 0;
tList *x;
for (x = first; x != last; x = x->next) {
if ((x->data == x->next->data) || (x->data == x->prev->data))
c++;
}
if (last->data == last->prev->data) {
c++;
}
return c;
}
/*Все объявили, запускаем программу*/
int main(void) {
int N;
printf ("Enter list size...\n");
scanf ("%d", &N); //Задаем размер списка
printf ("\nItial list:\n");
Fill_List(N);
int count = Counter (first, last);
printf ("\n\nNumbeer of equal entries: %d", count);
getch(); //Ожидание реакции пользователя
return 0;
}
Ключевые слова:
список, двунаправленный список, соседние элементы в списке
