|
|
ЛР1. ЛР1_БР9. Лабораторная работа по дисциплине Программирование
Министерство науки и высшего образования РФ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Новосибирский государственный технический университет»
Кафедра Автоматизированных систем управления
Лабораторная работа
по дисциплине «Программирование»
Тема: Списки
Выполнили:
Авдеев Егор Генрихович,
Трифонова София Викторовна
Группа АВТ-214
Факультет АВТ
______________________
подпись
«___» ______________ 2023 г.
|
Проверил:
Достовалов Дмитрий Николаевич
Балл: __________
______________________
подпись
«___» __________________ 2023 г.
|
Новосибирск 2023
Вариант 9
Задание.
Разработать структуру данных для хранения односвязного списка.
Реализовать функции для работы со списком: добавление элемента в список (в заданную позицию в списке), получение данных элемента списка (по номеру), получение адреса элемента в списке (по номеру), удаление элемента (по номеру), подсчет количества элементов в списке.
Найти среднее арифметическое значение элементов списка.
Определить, входит ли список L1 в L2. Вернуть адрес начала вхождения (нулевой адрес в противном случае).
Графическая интерпретация списков.
Интерпретация задания на поиск среднего арифметического элементов списка:
Интерпретация задания на проверку вхождения списка L1 в L2:
Описание разработанных функций: алгоритм работы и программная реализация с комментариями.
Имя функции
|
Описание функции
|
get_addres
|
Идёт по списку, пока не дойдёт до элемента с позицией на одну меньше заданной, после чего возвращает поле с адресом следующего элемента. В случае, если позиция отрицательная или превышает размерность списка, возвращает NULL-указатель.
|
get_value
|
Возврат поля value при помощи функции get_addres. В случае выхода за пределы размерности списка, возврат NULL.
|
find_len
|
Проходит до конца списка, поэлементно считая, возвращает длину.
|
find_midle_value
|
Последовательно суммирует элементы списка, в конце делит на их количество.
|
3insert_start
|
Создание экземпляра структуры, проверка, что память выделилась. Присвоение экземпляру структуры переданного значения текущего указателя на начало списка. Изменение указателя на начало списка на созданный экземпляр списка. В случае, если память не выделилась, возвращает «-1».
|
insert_end
|
Создание экземпляра структуры, в случае, если экземпляр успешно создан, проходит до конца списка и меняет значение поля next последнего элемента на адрес созданного экземпляра. В случае, если экземпляр не создан, возвращает «-1».
|
insert_middle
|
Создание экземпляра структуры, проверка, что память успешно выделилась, в случае, если значение заданной позиции равно нулю, освобождение памяти и запуск функции insert_start; в случае, если значение заданной позиции не равно нулю, доходит до предыдущего элемента, производит копирование указателя на следующий элемент, изменение поля next на указатель на созданный экземпляр, в созданном экземпляре изменение поля next на следующий элемент.
|
is_L1_in_L2
|
Идём по списку L2 до момента первого совпадения значений списков L1 и L2. Если элементы списков совпали, производится присвоение переменной start значения указателя на первый совпавший элемент. Далее идём параллельно по списку L1 и L2, если все элементы совпали и не произошло выхода за пределы списка L2, возврат начала вхождения. Если элемент не совпал или произошёл выход за пределы списка L1, присвоение переменной start значения NULL и поиск следующей пары совпадающих элементов. В случае, если L1 не входит в L2, возврат NULL.
|
pop
|
В случае, если требуется удалить элемент с первой позиции, присвоение указателю на начало списка адреса второго элемента, удаление первого элемента из памяти.
В случае, если список состоит из одного элемента, возврат происходит возврат ошибки. В случае, если необходимо удалить элемент с последней позиции, полю next предпоследнего элемента присваивается значение NULL, происходит удаление последнего элемента из памяти.
В остальных случаях с помощью функции get_addres получаем адреса предыдущего, последующего и удаляемого элементов, связываем предыдущий элемент с последующим, удаляем из памяти указанный элемент.
|
print_l
|
Последовательная печать значений поля value.
|
list_free
|
Поэлементное освобождение выделенной памяти списка.
|
Тестирование функций и программы в целом.
Тестовые данные для функции find_len
№
|
Ввод: список чисел L2
|
Вывод: len -количество элементов в списке L2
|
1
|
L2: 100 200 250 400
|
len = 4
|
2
|
L2: 8 800 555 3 555
|
len = 5
|
3
|
L2: 123456 345 6789 9087 0 123456 13243546
|
Len=7
|
Тестовые данные для функции insert_start
№
|
Ввод: список чисел Posl2;
A – новый элемент
|
Вывод: L1 – список чисел Posl2 с добавленным в начало элементом
|
1
|
Posl2: 12 45;
A = 256
|
L2: 256 12 45
|
2
|
Posl2: 555 3;
A = 800
|
800 555 3
|
3
|
Posl2: 98765 45678;
A = 256000
|
L2: 256000 98765 45678
|
Тестовые данные для функции insert_end
№
|
Ввод: Posl – список чисел;
B – новый элемент
|
Вывод: Posl – список Posl с добавленным в конец новым элементом
|
1
|
Posl: 100 200 300;
B = 400
|
Posl:100 200 300 400
|
2
|
Posl: 8 800 555;
B = 14112003
|
Posl: 8 800 555 14112003
|
3
|
Posl: 123456 345 6789 9087 364 123456;
B = 13243546
|
Posl: 123456 345 6789 9087 364 123456 13243546
|
Тестовые данные для функции insert_middle
№
|
Ввод: Posl - список чисел;
С – новый элемент;
Ind – позиция с списке, куда необходимо добавить элемент C
|
Вывод: Posl1 – список Posl с добавленным новым элементом (в заданную позицию в списке)
|
1
|
Posl: 100 200 300 400;
C = 250;
Ind = 2
|
Posl1: 100 200 250 300 400
|
2
|
Posl: 8 800 555 14112003 3;
C = 555;
Ind = 5
|
Posl1: 8 800 555 14112003 3 555
|
3
|
Posl: 123456 345 6789 9087 364 123456 13243546;
C = 0;
Ind = 5
|
Posl1: 123456 345 6789 9087 364 0 123456 13243546
|
Тестовые данные для функции is_L1_in_L2
№
|
Ввод: L2- список чисел;
L1 – список чисел
|
Вывод: Сообщение о том, входит ли список L2 в список L1
|
1
|
L2: 100 200 250 400;
L1: 256 12 45
|
«L1 не входит в L2.»
|
2
|
L2: 8 800 555 3 555;
L1: 800 555 3
|
«L1 входит в L2.»
|
3
|
L2: 123456 345 6789 9087 0 123456 13243546;
L1: 256000 98765 45678
|
«L1 не входит в L2.»
|
Тестовые данные для функции pop
№
|
Ввод: Posl1 – список чисел;
Num – номер удаляемого элемента
|
Вывод: L2 – список Posl с удаленным элементом (по номеру)
|
1
|
Posl1: 100 200 250 300 400;
Num = 3
|
L2: 100 200 250 400
|
2
|
Posl1: 8 800 555 14112003 3 555;
Num = 3
|
L2: 8 800 555 3 555
|
3
|
Posl1: 123456 345 6789 9087 364 0 123456 13243546;
Num = 4
|
L2: 123456 345 6789 9087 0 123456 13243546;
|
Тестовые данные для функции find_midle_value
№
|
Ввод: L2 – список чисел
|
Вывод: Mid – среднее арифметическое всех элементов списка L2
|
1
|
L2: 100 200 250 400
|
Mid = 237,5
|
2
|
L2: 8 800 555 3 555
|
Mid = 284,2
|
3
|
L2: 123456 345 6789 9087 0 123456 13243546
|
Mid = 1929525,571429
|
Тестовые данные для функции get_value
№
|
Ввод: L2 – список чисел;
Count – индекс элемента
|
Вывод: N – данные элемента индекса Count в списке L2
|
1
|
L2: 100 200 250 400;
Count = 1
|
N = 200
|
2
|
L2: 8 800 555 3 555;
Count = 3
|
N = 3
|
3
|
L2: 123456 345 6789 9087 0 123456 13243546;
Count = 3
|
N = 9087
|
Тестовые данные для программы в целом
№
|
Ввод:
Posl - список чисел
Posl2 – список чисел
|
Вывод:
Posl1 – список Posl с добавленным в определённую позицию новым элементом;
L2 – список Posl1 с удалённым по номеру элементом;
len – длина списка L2;
A – данные элемента списка, выводимые по индексу;
Mid – среднее арифметическое всех элементов списка L2;
L1- список с новым добавленным элементом в начало списка Posl2;
сообщение о том, входит ли список L1 в L2.
|
1
|
Posl: 100 200 300 400;
Posl2: 12 45
|
Posl1: 100 200 250 300 400;
L2: 100 200 250 400;
Len = 4;
A – данные об элементе с индексом 1 - = 200;
Mid = 237,5;
L1: 256 12 45;
«L1 не входит в L2.»
|
2
|
Posl: 8 800 555 14112003 3;
Posl2: 555 3
|
Posl1: 8 800 555 14112003 3 555;
L2: 8 800 555 3 555;
Len = 5;
A – данные об элементе с индексом 3 - = 3;
Mid = 384,2;
L1: 800 555 3;
«L1 входит в L2.»
|
3
|
Posl: 123456 345 6789 9087 364 123456 13243546;
Posl2: 98765 45678
|
Posl1: 123456 345 6789 9087 364 0 123456 13243546;
L2: 123456 345 6789 9087 0 123456 13243546;
Len = 7;
A – данные об элементе с индексом 3 - = 9087;
Mid = 1929525,571429;
L1: 256000 98765 45678;
«L1 не входит в L2.»
|
Снимки работы программы
Приложение: исходный код программы.
#include
#include
#include
#include
#define WORK 0
#define ERROR -1
typedef struct node {
int value;
struct node* next;
}node;
int insert_start(int n, node*& head);
int insert_end(int n, node* head);
int insert_middle(int n, int pos, node*& head);
void print_l(node* head);
int get_value(int pos, node* head);
node* get_addres(int pos, node* head);
int find_len(node* head);
int pop(int pos, node*& head);
double find_midle_value(node* head);
void list_free(node* head);
node* get_addres(int pos, node* head) {//Получение адреса по позиции , возвращает адрес
node* ptr = head;
int len = find_len(head);
if (head != NULL && pos < len && len != -1) {
for (int i = 0; i < pos; i++) {
ptr = ptr->next;
}
return ptr;
}
else { return NULL; }
}
int get_value(int pos, node* head) {//Получение значения по позиции , возвращает значение
return get_addres(pos, head)->value;
}
int find_len(node* head) {//Получение длины списка
node* i = head;
int counter = 1;
while (i->next != NULL) {
counter++;
i = i->next;
}
return counter;
}
double find_midle_value(node* head) {//Находит среднее арифметическое, при подаче пустого списка возвращает -1
int len = find_len(head);
double summ = 0;
node* ptr = head; int k = 0;
if (len <= 0) { return ERROR; }
else if (len == 1) { return head->value; }
else {
for (int i = 0; i < len; i++) {
summ += ptr->value;
k++;
ptr = ptr->next;
}
return summ / k;
}
}
int insert_start(int n, node*& head) {//Добавление элементов в начало списка, при неудаче возвращает -1
node* ptr = head, * element = (node*)malloc(sizeof(node));
if (element != NULL && head != NULL) {
element->value = n;
element->next = head;
head = element;
return WORK;
}
else { free(element); return ERROR; }
}
int insert_end(int n, node* head) {//Добавление элемента в конец списка, при неудаче возвращает -1
node* element = (node*)malloc(sizeof(node)), * i = head;
if (element != NULL && head != NULL) {
element->value = n;
element->next = NULL;
while (i->next != NULL) {
i = i->next;
}
i->next = element;
return WORK;
}
else { free(element); return ERROR; }
}
int insert_middle(int n, int pos, node*& head) {//Добавление элемента в список по позиции, при неудаче возвращает -1
node* element = (node*)malloc(sizeof(node)), * ptr = head, * help;
int len = find_len(head);
if (element != NULL && pos <= len && pos != 0 && head != NULL) {
element->value = n;
element->next = NULL;
for (int i = 0; i < pos - 1; i++) {
ptr = ptr->next;
}
help = ptr->next;
ptr->next = element;
element->next = help;
return WORK;
}
else if (element != NULL && pos == 0) {
free(element);
return insert_start(n, head);
}
else { free(element); return ERROR; }
}
node* is_L1_in_L2(node* head1, node* head2) {//проверяет входит ли список L1 в L2, если да возвращает вхождение иначе NULL
node* ptr2 = head2, * start = NULL;
int len1 = find_len(head1), len2 = find_len(head2);
for (int i = 0; i < len2; i++) {
if (head1->value == ptr2->value) {
start = ptr2; node* ptr2_h = ptr2, * ptr1 = head1;
for (int l = 0; l < len1; l++) {
if (ptr2_h == NULL) {
start = NULL;
break;
}
if (ptr2_h->value == ptr1->value) {
ptr2_h = ptr2_h->next;
ptr1 = ptr1->next;
}
else {
start = NULL;
break;
}
}
}
ptr2 = ptr2->next;
}
return start;
}
int pop(int pos, node*& head) {// Удаление элемента по позиции, при неудаче возвращает -1
node* start, * end = head;
int count = 0, len = find_len(head);
if (head != NULL) {
if (pos == 0 and len > 1) {
head = head->next;
free(end);
return WORK;
}
else if (pos == 0 && len <= 1) {
return ERROR;
}
else if (pos == len - 1) {
end = get_addres(pos, head);
get_addres(pos - 1, head)->next = NULL;
free(end);
return WORK;
}
else if (pos < len) {
end = get_addres(pos + 1, head);
start = get_addres(pos, head);
get_addres(pos - 1, head)->next = end;
free(start);
return WORK;
}
}
else { return ERROR; }
}
void print_l(node* head) { //Метод печати списка
node* ptr = head;
for (int i = 0; i < find_len(head); i++) {
printf("%d ", ptr->value);
ptr = ptr->next;
}
printf("\n");
}
void list_free(node* head) {
node* ptr = head, * next = head->next;
while (next != NULL) {
free(ptr);
ptr = next;
next = next->next;
}
free(ptr);
}
void test1() {//тестовая функция
printf("Тест 1\n");
node* first = (node*)malloc(sizeof(node)), * head = first;
node* f = (node*)malloc(sizeof(node)), * head2 = f;
first->value = 100;
first->next = NULL;
f->value = 12;
f->next = NULL;
insert_end(200, head);
insert_end(300, head);
insert_end(400, head);
printf("Список: ");
print_l(head);
printf("Список с добавленным элементом: ");
insert_middle(250, 2, head);
print_l(head);
printf("Список с удаленным элементом (L2): ");
pop(3, head);
print_l(head);
printf("Длина списка L2: %d", find_len(head));
printf("\nДанные элемента списка L2: %d", get_value(1, head));
printf("\nСреднее арифметическое всех элементов списка L2: %f\n", find_midle_value(head));
printf("Список 2: ");
insert_end(45, head2);
print_l(head2);
insert_start(256, head2);
printf("Список с добавленным в начало новым элементом (L1): ");
print_l(head2);
if (is_L1_in_L2(head2, head) != NULL) {
printf("L1 входит в L2.\n\n");
}
else {
printf("L1 не входит в L2.\n\n");
}
list_free(head);
}
void test2() {//тестовая функция
printf("Тест 2\n");
node* first = (node*)malloc(sizeof(node)), * head = first;
node* f = (node*)malloc(sizeof(node)), * head2 = f;
first->value = 8;
first->next = NULL;
f->value = 555;
f->next = NULL;
insert_end(800, head);
insert_end(555, head);
insert_end(14112003, head);
insert_end(3, head);
printf("Список 1: ");
print_l(head);
printf("Список с добавленным элементом: ");
insert_middle(555, 5, head);
print_l(head);
printf("Список с удаленным элементом (L2): ");
pop(3, head);
print_l(head);
printf("Длина списка L2: %d", find_len(head));
printf("\nДанные элемента списка L2: %d", get_value(3, head));
printf("\nСреднее арифметическое всех элементов списка L2: %f\n", find_midle_value(head));
printf("Список 2: ");
insert_end(3, head2);
print_l(head2);
insert_start(800, head2);
printf("Список с добавленным в начало новым элементом (L1): ");
print_l(head2);
if (is_L1_in_L2(head2, head) != NULL) {
printf("L1 входит в L2.\n\n");
}
else {
printf("L1 не входит в L2.\n\n");
}
list_free(head);
}
void test3() {//тестовая функция
printf("Тест 3\n");
node* first = (node*)malloc(sizeof(node)), * head = first;
node* f = (node*)malloc(sizeof(node)), * head2 = f;
first->value = 123456;
first->next = NULL;
f->value = 98765;
f->next = NULL;
insert_end(345, head);
insert_end(6789, head);
insert_end(9087, head);
insert_end(364, head);
insert_end(123456, head);
insert_end(13243546, head);
printf("Список 1: ");
print_l(head);
printf("Список с добавленным элементом: ");
insert_middle(0, 5, head);
print_l(head);
printf("Список с удаленным элементом (L2): ");
pop(4, head);
print_l(head);
printf("Длина списка L2: %d", find_len(head));
printf("\nДанные элемента списка L2: %d", get_value(3, head));
printf("\nСреднее арифметическое всех элементов списка L2: %f\n", find_midle_value(head));
printf("Список 2: ");
insert_end(45678, head2);
insert_end(9087, head);
insert_end(364, head);
print_l(head2);
insert_start(256000, head2);
printf("Список с добавленным в начало новым элементом (L1): ");
print_l(head2);
if (is_L1_in_L2(head2, head) != NULL) {
printf("L1 входит в L2.\n\n");
}
else {
printf("L1 не входит в L2.\n\n");
}
list_free(head);
}
int main() {
setlocale(LC_ALL, "Russian");
test1();
test2();
test3();
return EXIT_SUCCESS;
}
| |
|
|
Скачать 191.18 Kb.