Лабораторная работа №4. Динамические структуры данных. Однонаправленный список




НазваниеЛабораторная работа №4. Динамические структуры данных. Однонаправленный список
Дата конвертации02.04.2013
Размер262.46 Kb.
ТипЛабораторная работа

Динамические структуры данных. Однонаправленный список. http://www.c-site.h1.ru

Лабораторная работа №4.

Динамические структуры данных. Однонаправленный список.

Бардин Павел, А10-00.
Задание.

Задано множество объектов, описываемых совокупностью некоторых признаков.

Требуется:

выбрать объекты, признаки которых удовлетворяют заданным условиям;

распечатать заданную совокупность признаков этих объектов.

Выполнить задание в следующей модификации:

из файла входных данных сформировать однонаправленный список;

вывести этот список в выходной файл согласно выходной форме;

обработав созданный исходный список, сформировать список элементов, удовлетворяющих запросу;

вывести результирующий список в выходной файл.
Объект – Анкета сотрудника. Условия выделения объектов Год рождения>=1950, Семейное положение=женат, Стаж работы>=20. Выводить на печать ФИО, год рождения, семейное положение, стаж работы.
Входные данные:

Входными данными является множество ссылок на анкеты сотрудников. Из входных данных сформируем однонаправленный список.

Описание типа информационной части:

typedef struct {

char name[31]; // ФИО 30 симв.

int year; // Год рождения

char mstatus[7]; // Семейное положение

char obraz[8]; // Образование

char swork; // Стаж работы

char doljnost[31]; // Должность 30

} type_inf1;
Описание типа элемента списка:

typedef struct elemin {

type_inf1 inf;

struct elemin* inf;

} elemin;

Пусть val_loc переменная типа информационной части:

type_inf val_loc;

Входная форма:

обр1:

обр2:

обр3:

обр4:

обр5:

обр6:

обр7:

обр8:













.....................

.....................

Выходные данные:

Выходными данными являются искомые ссылки. Информацию (согласно заданию) будем выводить из результирующего списка.

Описание типа информационной части:

typedef struct {

char name[31]; // ФИО 30 симв.

int year; // Год рождения

char mstatus[7]; // Семейное положение

char swork; // Стаж работы

} type_inf2;
Описание типа элемента результирующего списка:

typedef struct elemout {

type_inf2 inf;

struct elemout* inf;

} elemout;


Выходная форма:

обр9:

обр10:

обр11:

обр12:

обр13:

обр14:

обр15:

обр16:

обр17:

обр18:

обр19:

обр20:

обр21:

обр22:

обр23:

обр24:

обр25:

обр26:

обр27:

обр28:

обр29:
обр30:

обр31:

Анкеты сотрудников

ФИО:

Год рождения:

Семейное положение:

Образование:

Стаж работы:

Должность:

<пустая строка>

...........................
Искомые сотрудники, найдено записей:

ФИО:

Год рождения:

Семейное положение:

Стаж работы:

<пустая строка>

........................

ФИО: < val_loc.name>

Год рождения:< val_loc.year>

Семейное положение:< val_loc.mstatus>

Стаж работы: < val_loc.swork>
Таких сотрудников нет

Ищем сотрудника с годом рождения >= , семейным положением - женат и стажем работы от 20 лет.

Функционаяльные тесты.



Входные данные

Ожидаемый результат

1

Мартынов Н.Н.

1960

женат

высшее

10

Инженер-монтажник
Степанов А.В.

1950

холост

среднее

20

Радиомонтажник

вывод по обр 30.

Искомых анкет нет


2

Кулигин В.Н.

1950

женат

высшее

20

Инженер-наладчик

Жукаркин Н.Ю.

1970

женат

среднее

13

Инженер

Кулигин В.Н.

1950

женат

20

3

Пронин А.В.

1950

холост

высшее

20

Сборщик

вывод по обр 30.

Искомых анкет нет


4

Мартынов Н.Н.

1960

женат

высшее

10

инженер-монтажник

Степанов А.В.

1950

холост

среднее

20

радиомонтажник

Кулигин В.Н.

1950

женат

высшее

20

инженер-наладчик

Жукаркин Н.Ю.

1970

женат

среднее

23

механик

Пронин А.В.

1950

холост

высшее

20

сборщик


Кулигин В.Н.

1950

женат

высшее

20

инженер-наладчик
Жукаркин Н.Ю.

1970

женат

среднее

23

механик



Метод.
// указатель на тип элемента исходного списка

typedef elemin* ptrin;

// указатель на тип элемента результирующего списка

typedef elemout* ptrout;
Пусть:

an1 – адрес начала исходного списка; ptrin an1;

an2 – адрес начала результирующего списка; ptrout an2;

ak1 – адрес конца исходного списка; ptrin ak1;

ak2 – адрес конца результирующего списка; ptrout ak2;

val_loc1 – информационная часть элемента исходного списка;

val_loc2 – информационная часть элемента результирующего списка;

k – адрес текущего элемента списка;

fin,fout – указатели на файлы;

recNum – количество ссылок удовлетворяющих условию

Вызовы функций


Схема обработки:
Вых.:an1

Вх.:нет
create_list(fin,&an1);

A1


Формирование списка из файла

print_list1(fout,an1);

Вых.:нет

Вх.:an1

Вывод входных данных

A2




Вых.:an2,recNum

formir(an1,&an2,&recNum);

A3


Вх.:an1

Формирование рез. списка


Вывод по обр31;

Если recNum!=0

Вывод(recNum) по обр19;

outrez(fout,an2);

A4


Вых.:нет

Вх.:an2

Вывод ссылок удовл. усл.


Иначе

Вывод по обр30;

Кесли;

Задача А1.

Сформировать однонаправленный список из файла.
Входные данные:

Входными данными является множество ссылок на анкеты сотрудников.
Выходные данные:

Выходными данными для этой задачи является сформированный список,

т.е. адрес начала списка an1.
Метод и алгоритм.

Пусть:

val_loc1 – переменная типа информационной части элемента type_inf1;

k – текущий адрес элемента списка;

Будем добавлять в конец списка.
Делаем список пустым(an1=NULL)

an

NULL

1

Читаем 1 ссылку в локальную переменную val_loc1;

Добавляем одну ссылку в начало списка

(это для того чтобы получить адрес начала списка)
Так как число ссылок не известно, то будем читать до конца файла.

ak

Читаем текущую ссылку в локальную переменную val_loc1;

Добавляем элемент в конец списка;
NULL

2

an

1

Закодируем.

void create_list(FILE *fp,ptrin *an1)

{

ptrin k,an,ak1;

type_inf1 val_loc1;

an=NULL;

fgets(val_loc1.name,31,fp);

fscanf(fp,"%d",&val_loc1.year);

fscanf(fp,"%s",val_loc1.mstatus);

fscanf(fp,"%s",val_loc1.obraz);

fscanf(fp,"%d\n",&val_loc1.swork);

fgets(val_loc1.doljnost,31,fp);

add_begin1(&an,val_loc1); // Задача А1.1

while(!feof(fp))

{

fgets(val_loc1.name,31,fp);

fscanf(fp,"%d",&val_loc1.year);

fscanf(fp,"%s",val_loc1.mstatus);

fscanf(fp,"%s",val_loc1.obraz);

fscanf(fp,"%d\n",&val_loc1.swork);

fgets(val_loc1.doljnost,31,fp);

add_end1(an,val_loc1,&ak1) // Задача А1.2

}

*an1=an;

}
Задача А1.1.

Добавить элемент с информационным полем val_loc1 в начало списка.
Входные данные:

an1 – адрес начала списка;

val1 – информационная часть элемента;
Выходные данные:

an1 - измененный адрес начала списка;

void add_begin1(ptrin *an1,type_inf1 val1)

{

ptrin k;

// Выделяем память по элемент

k=(elemin*)malloc(sizeof(elemin));

(*k).next=an1;

(*k).inf=val1;

*an1=k;

}
Задача А1.2.

Добавить элемент с информационным полем val_loc1 в конец списка.
Входные данные:

an1 – адрес начала списка;

val1 – информационная часть элемента;
Выходные данные:

ak1 - адрес конца списка;
void add_end1(ptrin an1,type_inf1 val1,ptrin *ak1)

{

ptrin k,ak;

adr_last1(an1,&ak);

k=(elemin*)malloc(sizeof(elemin));

(*ak).next=k;

(*k).next=NULL;

(*k).inf=val1;

ak=k;

*ak1=ak;

}

void adr_last1(ptrin an1,ptrin *ak1)

{

ptrin k;

k=an1;

while((*k).next!=NULL)

k=(*k).next;

*ak1=k;

}


Задача А2. Вывести входные данные.
Входные данные:

an - адрес начала списка;
Выходные данные:

нет.
Метод и алгоритм.

Перебираем элементы списка, и выводим их.
void print_list1(FILE *fp,ptrin an1)

{

ptrin k;

type_inf1 val_loc1;

k=an1;

while(k!=NULL)

{

val_loc1=(*k).inf;

fprintf(fp,"Ф.И.О.:%s",val_loc1.name);

fprintf(fp,"Год рождения:%d\n",val_loc1.year);

fprintf(fp,"Семейное положение:%s\n",val_loc1.mstatus);

fprintf(fp,"Образование:%s\n",val_loc1.obraz);

fprintf(fp,"Стаж работы:%d\n",val_loc1.swork);

fprintf(fp,"Должность:%s\n",val_loc1.doljnost);

k=(*k).next; // Переход к следующему элементу

}

}
Задача А3. Сформировать результирующий список. Добавлять в результирующий список элементы, информационные части которых удовлетворяют следующим условиям:

Год рождения>=1950;

Семейное положение=женат;

Стаж работы>=20.
Входные данные:

an1 - адрес начала исходного списка;
Выходные данные:

an2 - адрес начала результирующего списка;
Метод и алгоритм.

Будем перебирать элементы исходного списка и анализировать их информационные части. Если инф. часть элемента удовлетворяет условию задачи, то добавляем новый элемент в результирующий список.

void formir(ptrin an1,ptrout *an2,int *recNum)

{

type_inf1 val_loc1;

type_inf2 val_loc2;

ptrin k;

ptrout ak2;

int flag;
flag=1; // Чтоб первый элемент добавить в начало

an2=NULL;

k=an1; // Переход на начало исходного списка
while(k!=NULL)

{

val_loc1=(*k).inf;
if(val_loc1.year>=1950 && val_loc1.swork>=20)

{

// Анализ. семейное положение

if(strcmp(val_loc1.mstatus,”женат\0”)==0)

{

// Добавляем элемент в рез. список

strcpy(val_loc2.name,val_loc1.name);

val_loc2.year=val_loc1.year;

strcpy(val_loc2.mstatus,val_loc1.mstatus);

val_loc2.swork=val_loc1.swork;

if(flag==1)

{

add_begin2(an2,val_loc2);

flag=0;

}

else

add_end2(*an2,val_loc2,&ak2);

*recNum=*recNum+1;

}

}
k=(*k).next;

}
}

Процедуры добавления в начало и конец списка

void add_begin2(ptrout *an2,type_inf2 val2)

{

ptrout k;

// Выделяем память под элемент

k=(elemout*)malloc(sizeof(elemout));

(*k).next=an2;

(*k).inf=val2;

*an2=k;

}

void adr_last2(ptrout an2,ptrout *ak2)

{

ptrout k;

k=an2;

while((*k).next!=NULL)

k=(*k).next;

*ak2=k;

}

void add_end2(ptrout an2,type_inf2 val2,ptrout *ak2)

{

ptrout k,ak;

adr_last2(an2,&ak2);

k=(elemout*)malloc(sizeof(elemout));

(*ak).next=k;

(*k).next=NULL;

(*k).inf=val2;

ak=k;

*ak2=ak;

}

Задача А4. Вывести ссылки удовлетворяющие условию.
Входные данные:

an2 - адрес начала результирующего списка;
Выходные данные:

нет.
Метод и алгоритм.
void outrez(FILE *fp,ptrout an2)

{

ptrout k;

type_inf2 val_loc2;

k=an2; // На начало списка

while(k!=NULL)

{

val_loc2=(*k).inf;

fprintf(fp,"Ф.И.О.:%s",val_loc2.name);

fprintf(fp,"Год рождения:%d\n",val_loc2.year);

fprintf(fp,"Семейное положение:%s\n",val_loc2.mstatus);

fprintf(fp,"Стаж работы:%d\n",val_loc2.swork);

k=(*k).next; // Переход к следующему элементу

}
}

Программа.

Файл “types.h

#include

#include

// Тип информационной части исходного списка

typedef struct {

char name[31]; // ФИО 30 симв.

int year; // Год рождения

char mstatus[7]; // Семейное положение

char obraz[8]; // Образование

char swork; // Стаж работы

char doljnost[31]; // Должность 30

} type_inf1;
// Тип информационной части результирующего списка

typedef struct {

char name[31]; // ФИО 30 симв.

int year; // Год рождения

char mstatus[7]; // Семейное положение

char swork; // Стаж работы

} type_inf2;
// Описание типа элемента исходного списка

typedef struct elemin {

type_inf1 inf;

struct elemin* next;

} elemin;
// Описание типа элемента результирующего списка

typedef struct elemout {

type_inf2 inf;

struct elemout* next;

} elemout;
// указатель на тип элемента исходного списка

typedef elemin* ptrin;

// указатель на тип элемента результирующего списка

typedef elemout* ptrout;
void add_end1(ptrin an1,type_inf1 val1,ptrin *ak1);

void add_end2(ptrout an2,type_inf2 val2,ptrout *ak2);

void add_begin1(ptrin *an1,type_inf1 val1);

void add_begin2(ptrout *an2,type_inf2 val2);

void adr_last2(ptrout an2,ptrout *ak2);

void adr_last1(ptrin an1,ptrin *ak1);

void create_list(FILE *fp,ptrin *an1);

void formir(ptrin an1,ptrout *an2,int *recNum);

void print_list1(FILE *fp,ptrin an1);

void outrez(FILE *fp,ptrout an2);

void del_begin1(ptrin *an1);

void del_begin2(ptrout *an2);

Файл “proc.cpp”

#include "types.h"

#include

void adr_last1(ptrin an1,ptrin *ak1)

{

ptrin k;

k=an1;

while((*k).next!=NULL)

k=(*k).next;

*ak1=k;

}

void adr_last2(ptrout an2,ptrout *ak2)

{

ptrout k;

k=an2;

while((*k).next!=NULL)

k=(*k).next;

*ak2=k;

}
void add_begin1(ptrin *an1,type_inf1 val1)

{

ptrin k;

// Выделяем память по элемент

k=(elemin*)malloc(sizeof(elemin));

(*k).next=*an1;

(*k).inf=val1;

*an1=k;

}
void add_begin2(ptrout *an2,type_inf2 val2)

{

ptrout k;

// Выделяем память под элемент

k=(elemout*)malloc(sizeof(elemout));

(*k).next=*an2;

(*k).inf=val2;

*an2=k;

}

void add_end1(ptrin an1,type_inf1 val1,ptrin *ak1)

{

ptrin k,ak;

adr_last1(an1,&ak);

k=(elemin*)malloc(sizeof(elemin));

(*ak).next=k;

(*k).next=NULL;

(*k).inf=val1;

ak=k;

*ak1=ak;

}
void add_end2(ptrout an2,type_inf2 val2,ptrout *ak2)

void del_begin1(ptrin *an1)

{

ptrin k,an;

an=*an1;

k=an;

an=(*an).next;

free(k);

*an1=an;

}

void del_begin2(ptrout *an2)

{

ptrout k,an;

an=*an2;

k=an;

an=(*an).next;

free(k);

*an2=an;

}
{

ptrout k,ak;

adr_last2(an2,&ak);

k=(elemout*)malloc(sizeof(elemout));

(*ak).next=k;

(*k).next=NULL;

(*k).inf=val2;

ak=k;

*ak2=ak;

}
void create_list(FILE *fp,ptrin *an1)

{

ptrin k,an,ak1;

type_inf1 val_loc1;

an=NULL;

fgets(val_loc1.name,31,fp);

fscanf(fp,"%d",&val_loc1.year);

fscanf(fp,"%s",val_loc1.mstatus);

fscanf(fp,"%s",val_loc1.obraz);

fscanf(fp,"%d\n",&val_loc1.swork);

fgets(val_loc1.doljnost,31,fp);
add_begin1(&an,val_loc1); // Задача А1.1

while(!feof(fp))

{

fgets(val_loc1.name,31,fp);

fscanf(fp,"%d",&val_loc1.year);

fscanf(fp,"%s",val_loc1.mstatus);

fscanf(fp,"%s",val_loc1.obraz);

fscanf(fp,"%d\n",&val_loc1.swork);

fgets(val_loc1.doljnost,31,fp);

add_end1(an,val_loc1,&ak1); // Задача А1.2

}

*an1=an;

}

void print_list1(FILE *fp,ptrin an1)

{

ptrin k;

type_inf1 val_loc1;

k=an1;

while(k!=NULL)

{

val_loc1=(*k).inf;

fprintf(fp,"Ф.И.О.:%s",val_loc1.name);

fprintf(fp,"Год рождения:%d\n",val_loc1.year);

fprintf(fp,"Семейное положение:%s\n",val_loc1.mstatus);

fprintf(fp,"Образование:%s\n",val_loc1.obraz);

fprintf(fp,"Стаж работы:%d\n",val_loc1.swork);

fprintf(fp,"Должность:%s\n",val_loc1.doljnost);

k=(*k).next; // Переход к следующему элементу

}

}
void formir(ptrin an1,ptrout *an2,int *recNum)

{

type_inf1 val_loc1;

type_inf2 val_loc2;

ptrin k;

ptrout ak2;

int flag;
flag=1; // Чтоб первый элемент добавить в начало

*an2=NULL;

k=an1; // Переход на начало исходного списка
while(k!=NULL)

{

val_loc1=(*k).inf;
if(val_loc1.year>=1950 && val_loc1.swork>=20)

{

// Анализ. семейное положение

if(strcmp(val_loc1.mstatus,"женат\0")==0)

{

// Добавляем элемент в рез. список

strcpy(val_loc2.name,val_loc1.name);

val_loc2.year=val_loc1.year;

strcpy(val_loc2.mstatus,val_loc1.mstatus);

val_loc2.swork=val_loc1.swork;

if(flag==1)

{

add_begin2(an2,val_loc2);

flag=0;

}

else

add_end2(*an2,val_loc2,&ak2);

*recNum=*recNum+1;

}

}
k=(*k).next;

}

}
void outrez(FILE *fp,ptrout an2)

{

ptrout k;

type_inf2 val_loc2;

k=an2; // На начало списка

while(k!=NULL)

{

val_loc2=(*k).inf;

fprintf(fp,"Ф.И.О.:%s",val_loc2.name);

fprintf(fp,"Год рождения:%d\n",val_loc2.year);

fprintf(fp,"Семейное положение:%s\n",val_loc2.mstatus);

fprintf(fp,"Стаж работы:%d\n\n",val_loc2.swork);

k=(*k).next; // Переход к следующему элементу

}
}
Файл “lab4.cpp

#include "types.h"

void main(int argc,char *argv[])

{

FILE *fin,*fout;

ptrin an1;

ptrout an2;

int recNum;

recNum=0;

fin=fopen(argv[1],"r");

fout=fopen(argv[2],"w");

create_list(fin,&an1);

fprintf(fout,"Входные данные:\n");

print_list1(fout,an1);

formir(an1,&an2,&recNum);

fprintf(fout,"\nИщем сотрудника с годом рождения >=1950 ,\nсемейным положением - женат и стажем работы от 20 лет\n\n");

if(recNum!=0)

{

fprintf(fout,"Искомые сотрудники, найдено %d записей:\n\n",recNum);

outrez(fout,an2);

}

else

fprintf(fout,"Таких сотрудников нет.");

while(an1!=NULL)

del_begin1(&an1);

while(an2!=NULL)

del_begin2(&an2);

fclose(fin);

fclose(fout);

}




Похожие:

Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа № ссылочная целостность данных. Создадим 2 файла: Файл- штатное расписание. 2 Файл- список должностей
Эти файлы необходимо создать как файлы базы данных. Последовательность создания этих файлов, сведения об их полях, размерах и индексации...
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа №4 Динамические модели
Привести статистические характеристики по каждой модели и дать оценку адекватности модели
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛитература структуры данных и алгоритмы в Java. Классика Computers Science. 2
Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа №7 " настройка регуляторов типовых одноконтурных систем" Цель работы
Изучение влияния настроечных параметров регулятора на динамические свойства сау и методик настройки сау на мо и со
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа №4 Тема: Пакет Control System Toolbox. Динамические и частотные характеристики систем автоматического управления (сау) Краткие сведения из теории
Рассмотрим сау, описываемую линейным (линеаризованным) дифференциальным уравнением вида
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconСистемы управления базами данных
Основная особенность субд – это наличие процедур для ввода и хранения не только самих данных, но и описаний их структуры. Файлы,...
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа №9 Агропромышленный комплекс. Задание Восстановите количественные показатели структуры земельных угодий России по круговой диаграмме в учебнике (9 класс) на странице25
Восстановите количественные показатели структуры пашни, воспользовавшись заданием 4 и диаграммой в атласе на странице 14
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа №4 Динамические модели Задание Оценить для двух рядов восемь типов моделей: статическая регрессия; процесс авторегрессии; модель опережающего показателя
Привести статистические характеристики по каждой модели и дать оценку адекватности модели
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconКурсовая работа "Структуры и алгоритмы обработки данных"
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по...
Лабораторная работа №4. Динамические структуры данных. Однонаправленный список iconЛабораторная работа 1 Тема: Структуры и классы. Инкапсуляция. Цель: Изучение отличий процедурного и объектно-ориентированного подхода. Изучение практической реализации инкапсуляции и защиты данных класса
Написать программу, описывающую объект с данными и методами (действиями над объектом), заданный в варианте, используя для описания...
Разместите кнопку на своём сайте:
kurs.znate.ru


База данных защищена авторским правом ©kurs.znate.ru 2012
обратиться к администрации
kurs.znate.ru
Главная страница