Работа с таблицей "Туризм", сортировка городов для одной страны методом Шелла (Лабораторная работа № 6)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

НГТУ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

ЛАБОРАТОРНАЯ РАБОТА №6

по дисциплине "Структуры данных и алгоритмы"

ФПМИ

ПМ-62

Выполнила: Грибач Д.

Проверила: Шапошникова Т.А.

НОВОСИБИРСК, 2007

1.  Задание

В таблице "Туризм", отсортировать города для одной страны методом Шелла. Выводить путевки, стоимость, которых не превышает заданной.

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

    Дано:

Т = {c_i | c_i € C, i = 1,n}, C = {c_i = (s_i ; G) | s_i € S, i = 1,n}, G = {(g; a; t)_j | g € Q, a € N, t € W, j = 1,m, }, e € N , где S – множество стран, Q – множество городов, W –  множество транспортных средств, а – стоимость поездки, e – предельная стоимость поездки.             

          Результат:

                         E € T, g₁<g₂<…<g_m, a ≤ e.                 

     3. Метод решения

Необходимо отсортировать таблицу методом Шелла по ключу – название города. Сравнить для каждого города стоимость путевки с заданной. Метод Шелла: сравнивать элементы g_i и g_i+h, где h = m/2, затем шаг уменьшается вполовину, пока не станет равным 1.

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

#include <stdlib.h>

#include <conio.h>

#include <stdio.h>

#include <string.h>

const N=20;

struct city

{

     char name[21];

     int coast;

     char trsp[21];

};

struct country

{

     char name[21];

     city el[N];

    int k;

};

struct table

{

     country elem[N];

     int n;

};

void sort(table *t)

{

  int m,h=t->elem[0].k/2;

  while (h>=1) {

  for (m=0; m<t->elem[0].k-h; m++)

  if (strcmp(t->elem[0].el[m].name,t->elem[0].el[m+h].name)>0)

  {

  struct city tab = t->elem[0].el[m];

  t->elem[0].el[m]=t->elem[0].el[m+h];

  t->elem[0].el[m+h]=tab;

  int s=m;

  while ((s>h) && (strcmp(t->elem[0].el[s].name,t->elem[0].el[s-h].name) <0))

  {

    tab = t->elem[0].el[s];

    t->elem[0].el[s]=t->elem[0].el[s-h];

    t->elem[0].el[s-h]=tab;

    s--;

  }

  }

  h/=2;

}

}

void readf(table *h)

{

     FILE *in;

    if ((in = fopen("input.txt", "r")) == NULL)

               {

                fprintf(stderr, "Cannot open input file.\n");

                getch();

                exit(0);

               }

               char s[21];

               int l=0,k=0;

               fscanf(in,"%s%d",s,&l);

               h->n=1;

               strcpy(h->elem[h->n-1].name,s);

               h->elem[h->n-1].k=l;

               for (k=0;k<l;k++)

               fscanf(in,"%s%d%s",h->elem[h->n-1].el[k].name,&(h->elem[h->n-1].el[k].coast),h->elem[h->n-1].el[k].trsp);

    while (!feof(in))

     {

               fscanf(in,"%s%d",s,&l);

               h->n++;

               int i=0;

               int k=0;

               while ((strcmp(s,h->elem[k].name)>0)&&(k<h->n-1))

               {

                         k++;

               }

               if (k<h->n)

                         for (i=h->n-1;i>k;i--)

                                    h->elem[i]=h->elem[i-1];

               strcpy(h->elem[k].name,s);

               h->elem[k].k=l;

               for (k=0;k<l;k++)

               fscanf(in,"%s%d%s",h->elem[i].el[k].name,&(h->elem[i].el[k].coast),h->elem[i].el[k].trsp);

     }

}

void prnt(table *h)

{

 int c;

printf ("Enter coast: ");

scanf ("%d", &c);

printf("\n%s\n",h->elem[0].name);

for (int j=0;c>=h->elem[0].el[j].coast;j++)

    {

     printf("%s %d %s\n",h->elem[0].el[j].name,h->elem[0].el[j].coast,h->elem[0].el[j].trsp);

     printf("\n");

    }

void main()

{

     table t;

     t.n=0;

        clrscr ();

     readf(&t);

     sort(&t);

     prnt(&t);

     getch();

}

5.  Тесты

input:	стоимость:	результат:
Russia 4 Novosibirsk 30 plane Moscow 10 foot Saratov 70 bus Sochi 120 car	50	Moscow 10 foot Novosibirsk 30 plane
	120	Sochi 120 car Moscow 10 foot Novosibirsk 30 plane Saratov 70 bus