Проектирование программы об автомобилях (Лабораторная работа № 5)

Министерство образования и науки

Российский Федерации

НГТУ

Кафедра прикладной математики

Лабораторная работа №5

по “Структурам данных и алгоритмов”

Факультет: ПМИ

Группа: ПМИ-51

Студент: Коновалов В.О.

Преподаватель:  Еланцева И.Л.

Новосибирск 2006

1.Условие задачи

В файле “AUTO” дана информация об автомобилях: <номер>,<марка>,<ФИО владельца>. Переписать эту информацию в таблицу «автовладельцы»: <ФИО владельца> список его машин вида: {<номер><марка>}

В таблице <ФИО> не должно повторяться. Таблицу создать упорядоченную – по возрастанию <ФИО владельца>.

2. Анализ задачи

Дано:  Файл “AUTO” с информацией в виде: <номер>,<марка>,<ФИО владельца>.

Результат: Файл “AUTO2” с видоизменённой исходной информацией, если

Метод решения:

Таблица (T)

Используем структуру вида:

n-1

…

7

6

5

4

3

2

1

0

Динамический список – Машины (mach)

next

marka

nomer

sim

…

NULL

Элемент - Номер машины (mach->nomer)

next

sim

next

…

…

…

…

NULL

NULL

NULL

NULL

Номер машины по стандарту – 7 символов.

Количество символов в частях: Фамилия Имя Отчество, Марка и количество машин ограничено только памятью компьютера.

Делаем счётчик (T.n) на количество элементов равным нулю.

Ввод таблицы:

1.  Кладём элемент на (T.n+1) позицию.

2.  Делаем счётчик идентичности=0, счётчик найденного места=0.

3.  Просматриваем таблицу справа (с (T.n-1) элемента) налево (пока T.n>-1 , мы не нашли нужную нам позицию в таблице и мы не нашли идентичные ФИО):

a.  Начинаем сравнивать элементы ФИО у таблицы слева направо.

b.  Если сравниваемый символ у элемента (T.n-1) по таблице кодировки больше сравниваемого символа у элемента (T.n+1), то переходим на следующее слово влево.

c.  Если сравниваемый символ у элемента (T.n-1) по таблице кодировки равен сравниваемому символу у элемента (T.n+1), то переходим на следующий символ в обоих элементах. Если дошли до конца в обоих элементах, то  мы нашли идентичные ФИО (счётчик идентичности = 1, выход из цикла)

d.  Если сравниваемый символ у элемента (T.n-1) по таблице кодировки меньше сравниваемого символа у элемента (T.n+1), то «мы нашли нужную позицию в таблице» (счётчик найденного места = 1, выход из цикла).

4.  Если мы не нашли идентичное слово, то :

a.  прибавляем счётчику позиции в таблице 1 (для добавления элемента после меньшего его по алфавиту).

b.  Переставляем элементы в таблице по одному вправо на одну позицию начиная с самого правого (T.n-1), пока не освободится нужная позиция. Количество перестановок : количество элементов в таблице (T.n) минус нужная позиция.

c.  Переставляем элемент (T.n+1) на освободившуюся позицию.

5.  Если мы нашли идентичное слово, то добавляем в структуру с номером этой позицию в подструктуру «Машины» новую ячейку с информацией о машине.

3. Текст программы

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct name { char sim;

              name *next; };

struct machine { char nomer[7];

                     machine *next;

                     name *marka; };

struct info { machine mach;