Обработка связных списков. Лабораторная работа №6

Формулировка задания
Сформировать список Z как пересечение исходных списков X и Y. Проверку принадлежности элемента списку выделить в отдельную функцию.

 

Код программы

#include "stdafx.h"

#include<stdio.h>

#include<stdlib.h>

#include<ctype.h>

#include <string.h>

#include <iostream>

/*структура для хранения одного элемента списка*/

struct spisok

{

int number; /*данные*/

struct spisok *next; /*указатель на следующий элемент списка*/

};

/*эта функция проверяет, является ли очередная введенная символьная строка натуральным числом. Возвращает 1 в случае успеха, 0 – в противном случае*/

int verify(char *str)

{

int i;

for(i=0;i<strlen(str);i++)

{

/*проверка, является ли очередной символ цифрой*/

if (isdigit(str[i])) ;

else return(0);

}

return(1);}

int proverka(spisok *ptr,spisok *head1,int n1)

{

struct spisok *ptr1;

ptr1=head1;

for(int i=1; i<=n1;i++)

{

if(ptr->number==ptr1->number) return 1;

else ptr1=ptr1->next;

}

return 0;

}

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "");

//первый список

struct spisok *head, *ptr, *old_ptr;

int num, k, n;

char filename[20], tmp[6];

FILE *in;

int verify(char *str);

printf("Введите имя файла, содержащего арифметические данные "); scanf("%s", filename);

in=fopen(filename, "rt");

if (in==NULL)

{

printf("Файла с таким именем не существует. Программа завершает работу\n");

exit(1);

}

n=0;

/*выделение памяти под голову списка*/

head=(struct spisok *)malloc(sizeof(struct spisok));

/*текущий указатель устанавливается на голову списка*/

ptr=head;

/*данные вводятся, пока не будет достигнут конец файла*/

while(fscanf(in, "%s", tmp)!=EOF)

{

k=verify(tmp);

/*введенная строка – натуральное число. Преобразоване ее к формату int*/

if (k==1) num=atoi(tmp);

else

{

printf("Недопустимый формат данных в файле - не все данные являются целыми числами. Программа завершает работу\n"); exit(1);

}

/*занесение данных в элемент списка*/

ptr->number=num;

/*увеличение счетчика количества элементов в списке*/

n++;

/*устанавливаем указатель на новый элемент списка из предыдущего элемента*/

if (ptr!=head) old_ptr->next=ptr; else;

old_ptr=ptr;

/*выделение памяти под новый элемент списка*/

ptr=(struct spisok *)malloc(sizeof(struct spisok));

}

/*ввод данных закончен. Последнее выделение памяти оказалось ненужным. Она освобождается*/

free(ptr);

/*в последнем элементе списка устанавливается пустой указатель на следующий элемент*/

if (n>0) old_ptr=NULL;

else

{

printf("Файл не содержит никаких данных. Программа завершает работу\n");

exit(1);

}

int i=1;

/*проверка корректности формирования списка – его печать*/

ptr=head;

for(i=1; i<=n;i++)

{

printf("Элемент списка с номером %d равен %d\n", i, ptr->number);

ptr=ptr->next;

}

//второй список

struct spisok *head1, *ptr1, *old_ptr1;

int n1;

int verify(char *str);

printf("Введите имя файла, содержащего арифметические данные "); scanf("%s", filename);

in=fopen(filename, "rt");

if (in==NULL)

{

printf("Файла с таким именем не существует. Программа завершает работу\n");

exit(1);

}

n1=0;

/*выделение памяти под голову списка*/

head1=(struct spisok *)malloc(sizeof(struct spisok));

/*текущий указатель устанавливается на голову списка*/

ptr1=head1;

/*данные вводятся, пока не будет достигнут конец файла*/

while(fscanf(in, "%s", tmp)!=EOF)

{

k=verify(tmp);

/*введенная строка – натуральное число. Преобразоване ее к формату int*/

if (k==1) num=atoi(tmp);

else

{

printf("Недопустимый формат данных в файле - не все данные являются целыми числами. Программа завершает работу\n"); exit(1);

}

/*занесение данных в элемент списка*/

ptr1->number=num;

/*увеличение счетчика количества элементов в списке*/

n1++;

/*устанавливаем указатель на новый элемент списка из предыдущего элемента*/

if (ptr1!=head1) old_ptr1->next=ptr1; else;

old_ptr1=ptr1;

/*выделение памяти под новый элемент списка*/

ptr1=(struct spisok *)malloc(sizeof(struct spisok));

}

/*ввод данных закончен. Последнее выделение памяти оказалось ненужным. Она освобождается*/

free(ptr1);

/*в последнем элементе списка устанавливается пустой указатель на следующий элемент*/

if (n1>0) old_ptr1=NULL;

else

{

printf("Файл не содержит никаких данных. Программа завершает работу\n");

exit(1);

}

i=1;

/*проверка корректности формирования списка – его печать*/

ptr1=head1;

for(i=1; i<=n1;i++)

{

printf("Элемент списка с номером %d равен %d\n", i, ptr1->number);

ptr1=ptr1->next;

}

/*код обработки списков*/

struct spisok *head2, *ptr2,*old_ptr2;

head2=(struct spisok *)malloc(sizeof(struct spisok));

ptr2=head2;

ptr=head;

int n2=0;

for(i=1; i<=n;i++)

{

if(proverka(ptr,head1,n1))//проверка наличия элемента первого списка второму списку

{

ptr2->number=ptr->number;

n2++;

if (ptr2!=head2) old_ptr2->next=ptr2;

old_ptr2=ptr2;

 

ptr2=(struct spisok *)malloc(sizeof(struct spisok));

}

ptr=ptr->next;

}

puts("Новый список (пересечение старых)");

/*проверка корректности формирования списка – его печать*/

ptr2=head2;

for(i=1; i<=n2;i++)

{

printf("Элемент списка с номером %d равен %d\n", i, ptr2->number);

ptr2=ptr2->next;

}

/*освобождение памяти, выделенной под список*/

ptr=head;

for(i=1; i<=n;i++)

{

old_ptr=ptr;

ptr=ptr->next;

free(old_ptr);

}

ptr1=head1;

for(i=1; i<=n1;i++)

{

old_ptr1=ptr1;

ptr1=ptr1->next;

free(old_ptr1);

}

ptr2=head2;

for(i=1; i<=n2;i++)

{

old_ptr2=ptr2;

ptr2=ptr2->next;

free(old_ptr2);

}

printf("Память, выделенная под списки, очищена\n");

system("pause");

return 0;

}