Рацеев С.М. Программирование на языке Си
.pdf#include<stdio.h> #include< stdlib.h>
typedef struct ELEMENT
{
int data;
struct ELEMENT *next; } ELEMENT;
void CreateHead(ELEMENT **head)
{
*head = (ELEMENT *)malloc(sizeof(ELEMENT)); (*head)->next = NULL;
}
/* вставка нового элемента со значением x */ void Insert(ELEMENT *head, int x)
{
ELEMENT *q, *t; q = head;
while (q->next != NULL && q->next->data < x) q = q->next;
if (q->next == NULL || x < q->next->data)
{
t = (ELEMENT *)malloc(sizeof(ELEMENT)); t->data = x;
t->next = q->next; q->next = t;
}
}
/* рекурсивная функция, которая осуществляет вывод на экран всех элементов списка
*/
void Print(ELEMENT *q)
{
if (q != NULL)
251
{
printf("%d ", q->data); Print(q->next);
}
}
/* сумма элементов списка */ int Sum(ELEMENT *head)
{
ELEMENT *q; int s = 0;
q = head->next; while (q != NULL)
{
s += q->data; q = q->next;
}
return s;
}
/* удаление списка из памяти */ void Distruct(ELEMENT *head)
{
ELEMENT *q, *t; q = head->next; while (q != NULL)
{
t = q;
q = q->next; free(t);
}
head->next = NULL;
}
int main ( )
{
ELEMENT *head;
252
int a; CreateHead(&head); printf("a = "); scanf("%d", &a); while (a !=0 )
{
Insert(head, a); printf("a = "); scanf("%d", &a);
}
Print(head->next); printf("\n");
printf("sum = %d\n", Sum(head)); Distruct(head);
return 0;
}
Пример 4. Ниже приведен алгоритм последовательного поиска элемента с заданным значением x. Функция Find возвращает адрес первого элемента со значением x. Если элемента со значением x нет в списке, то функция возвратит значение NULL.
ELEMENT *Find(ELEMENT *head, int x)
{
ELEMENT *q; q = head->next;
while (q != NULL && q->data != x) q = q->next;
return q;
}
Пример 5. Пусть имеется список целых чисел, элементы которого упорядочены по возрастанию. Написать функцию, которая добавляет в данный список элемент со значением x так, чтобы список оставался упорядоченным.
void Insert(ELEMENT *head, int x)
253
{
ELEMENT *q, *t; q = head;
while (q->next != NULL && q->next->data <= x) q = q->next;
t = (ELEMENT *)malloc(sizeof(ELEMENT)); t->data = x;
t->next = q->next; q->next = t;
}
Пример 6. Подсчитать максимальное количество одинаковых элементов в списке.
long MaxPovt(ELEMENT *head)
{
ELEMENT *q, *t; long max, n;
q = head->next; max = 0;
while (q != NULL)
{
n = 1;
t = q->next;
while (t != NULL)
{
if (q->data == t->data) n++;
t = t->next;
}
if (n > max) max = n;
q = q->next;
}
return max;
}
254
Пример 7. Написать функцию, определяющую, пуст ли список с заглавным элементом.
int IsEmpty(ELEMENT *head)
{
return (head->next == NULL);
}
Пример 8. Написать функцию, которая переворачивает список, то есть первый элемент (без учета заглавного) становится последним, второй – предпоследним и т.д.
Пусть исходный список имеет следующий вид:
Алгоритм состоит в том, чтобы в ссылочное поле очередного элемента q, хранящее адрес следующего после q элемента, записать адрес предыдущего элемента.
На первом шаге в ссылочное поле первого элемента (без учета заглавного) записываем значение NULL. i-й шаг схематично можно изобразить следующим образом.
a) Переменная t содержит адрес последнего элемента нового списка, а переменная q содержит адрес очередного элемента исходного списка, в ссылочное поле которого требуется записать адрес элемента t:
б) Изменяем значение ссылочного поля элемента q:
в) Переопределяем значения элементов t и q:
Ниже представлен алгоритм переворачивания списка.
255
void Reverse(ELEMENT *head)
{
ELEMENT *q, *r, *t; q = head->next;
t = NULL;
while (q != NULL)
{
r = q->next; q->next = t; t = q;
q = r;
}
head->next = t;
}
Пример 9. В следующей программе создается список, каждый элемент которого содержит информацию о работниках некоторой организации.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct WORKER |
|
|
{ |
|
|
char name[20]; |
/* фамилия |
*/ |
int year; |
/* год рождения |
*/ |
float earnings; |
/* заработная плата */ |
|
} WORKER; |
|
|
typedef struct ELEMENT
{
WORKER worker; struct ELEMENT *next;
} ELEMENT;
256
/* создание заглавного элемента списка */
void CreateHead(ELEMENT **head, ELEMENT **last)
{
*last = *head = (ELEMENT *)malloc(sizeof(ELEMENT)); (*head)->next = NULL;
}
/* добавление нового элемента в конец списка */
void AddElement(ELEMENT **last, WORKER *worker)
{
ELEMENT *q; /* новый элемент списка */
/* выделяем память для очередного элемента списка: */ q = (ELEMENT *)malloc(sizeof(ELEMENT));
/* заполняем информационное и ссылочное поле нового элемента: */ q->worker = *worker;
q->next = NULL; (*last)->next = q; *last = q;
}
/* вывод на экран всех элементов списка */ void Print(ELEMENT *head)
{
ELEMENT *q; q = head->next;
while (q != NULL)
{
printf("%s ", q->worker.name); printf("%d ", q->worker.year); printf("%.2f\n", q->worker.earnings); q = q->next;
}
printf("\n");
}
/* удаление всего списка, не включая заглавный элемент */ void Distruct(ELEMENT *head, ELEMENT **last)
257
{
ELEMENT *q, *t; q = head->next; while (q != NULL)
{
t = q;
q = q->next; free(t);
}
head->next = NULL; *last = head;
}
int main()
{
ELEMENT *head, *last; WORKER worker; CreateHead(&head, &last); printf("name: "); scanf("%s", worker.name);
while (strcmp(worker.name, "000"))
{
printf("year: "); scanf("%d", &worker.year); printf("earnings: ");
scanf("%f", &worker.earnings); AddElement(&last, &worker); printf("name: ");
scanf("%s", worker.name);
}
Print(head); Distruct(head, &last); return 0;
}
14.3. Задачи на односвязные списки
258
1.Найти количество максимальных элементов списка действительных чисел.
2.Написать функцию, которая по списку L строит два новых
списка: L1 – из положительных элементов и L2 – из отрицательных элементов списка L.
3.Определить, является ли список упорядоченным по возрастанию.
4.Сформировать список целых чисел, вводимых пользователем, в том порядке, в котором вводятся эти числа, но без повторений элементов.
5.Написать функцию, которая оставляет в списке L только первые вхождения одинаковых элементов.
6.Определить количество различных элементов списка действительных чисел, если известно, что его элементы образуют возрастающую последовательность.
7.Имеется список целых чисел. Продублировать в нем все четные числа.
8.Написать функцию, которая по двум данным линейным спискам формирует новый список, состоящий из элементов, одновременно входящих в оба данных списка.
9.Написать функцию, которая по двум линейным спискам L1 и L2 формирует новый список L, состоящий из элементов, входящих в L1, но не входящих в L2.
10.Написать функцию, которая в линейном списке из каждой группы подряд идущих одинаковых элементов оставляет только один.
11.Написать функцию, которая удаляет из списка элементы, входящие в него только один раз.
12.Пусть имеется список L1 действительных чисел. Записать в список L2 все элементы списка L1 в порядке возрастания их значений.
13.Пусть имеется список действительных чисел a1→a2→...→aп. Сформировать новый список b1→b2→...→bп такой же размерности по следующему правилу: элемент bk равен сумме элементов исходного списка с номерами от 1 до k.
259
Задачи для самостоятельной работы
14.Написать функцию, которая, получив в качестве параметра указатель q на один из элементов списка и некоторое число x, добавляет новый элемент со значением x после (до) элемента, на который указывает ссылка q.
15.Написать функцию, которая, получив в качестве параметра указатель q на один из элементов списка, удаляет элемент, расположенный после элемента (сам элемент), на который указывает ссылка q.
16.Сформировать список действительных чисел. Затем преобразовать его, прибавив к положительным числам максимальный элемент.
17.Удалить из списка все элементы, встречающиеся более одного раза.
18.Дан список целых чисел. Продублировать в нем все простые числа.
19.Определить, есть ли в списке действительных чисел элементы, превосходящие сумму всех элементов списка.
20.Определить, образуют ли элементы списка действительных чисел геометрическую прогрессию.
21.Удалить из списка действительных чисел все максимальные элементы.
22.Пусть имеются два списка, элементы которых упорядочены по возрастанию. Сформировать новый список из элементов первого и второго списка, элементы которого будут упорядочены.
23.Сформировать список действительных чисел a1→a2→...→aп, вводимых пользователем. Затем сформировать новый список
b1→b2→...→bп такой же размерности по следующему правилу: элемент bk является максимальным из элементов исходного списка с номерами от 1 до k.
24.Пусть имеется текстовый файл. Используя линейный список, подсчитать число появлений каждого слова и создать новый текстовый файл, каждая строка которого имеет вид "<слово>– <число его появлений>". Слова должны располагаться в лексикографическом порядке.
260