Сортировка двусвязного динамического списка, структура которого содержит фамилию, год рождения, страница 2

В цикле Do… while производиться ввод списка, функция malloc выделяет динамическую память для структуры spis. Ввод осуществляется до выполнения условия while (getch()!=27) фукцией scanf(), в ответ на фукцию printf(). Далее функция if ... else проверяет наличие предыдущей структуры.  Если предыдущая структура не существует, создается первая, иначе следующая. При создании каждого элемента, будет предложено заполнить приведенные ниже поля данных:

1  Фамилия  – ввод фамилии

2  Год  – ввод года рождения

После заполнения всех полей списка, программа предлагает выйти в основное меню по нажатию клавиши <esc> - функция getch(), либо продолжить заполнение по нажатию любой клавиши.

2)  Просмотр списка - void view(spis *p).

*p – указатель на первую структуру.

В данной процедуре реализуется вывод списка в виде таблицы.

Очистка экрана - clrscr().

Выводиться шапка выходной таблицы - printf().

Проверка существования списка – if ... else. Если список существует с помощью цикла while начинают просматриваться и выводиться элементы данного списка на экран - printf(). Все элементы начиная с первого помещаются в таблицу с разделами: Фамилия, Год рождения, иначе выдодится сообщение "Список пуст" - puts(). После вывода, программа просит нажатия любой клавиши - getch(), для выхода в меню.

3)  Добавление в конец списка новой структуры - void bod(spis *p).

*p – указатель на последнюю структуру.

Очистка экрана - clrscr().

Вывод сообщения " *********** Добавление записи ***********" – printf().

malloc выделяет динамическую память для структуры spis.

Ввод осуществляется фукцией scanf(), в ответ на фукцию printf().

По окончанию ввода команда return возвращает на экран меню пользователя.

4)  Корректировка списка - bod(tail), sort(head), view(head).

Выполнение корректировки состоит из последовательно выполняемых процедур bod(tail) – добавление в конец списка новой структуры, sort(head) - сортировка, view(head)- просмотр списка.

Процедуры bod(tail) и view(head) были описаны ранее, в процедуре корректировки в них передаются конец и начало списка соответственно.

Процедура void sort(head), в качестве параметра *p передается указатель на первую структуру.

Далее в цикле while () осуществляется перебор всего списка до предпоследней структуры. В следующем цикле while() осуществляется перебор списка начиная со второй структуры до конца списка. По условию if функцией strcmp сравниваются фамилия текущей структуры с фамилией следующей структуры.

Если фамилия следующей структуры меньше фамилии текущей структуры, значение следующей структуры присваивается переменной "temp", а переменная "fl" становится равной "1"  

По окончанию второго цикла происходит проверка переменной "fl", если она равна 1 то найденная структура перемещается на место перед текущей структурой "p", иначе указатель текущей структуры перемещается на следующую структуру и второй цикл начинается заново.

Перемещение структур осуществляется следующим образом:

Если найденная структура по условию if является последней то предыдущая становится последней. Иначе в середине списка происходит перестроение указателей исключающих найденную структуру.

Затем найденная структура перемещается на место перед текущей структурой "p" и распологается либо в начале списка, тогда текущая структура становится следующей, либо в середине списка перед текущей структурой, тогда происходит перестроение указателей.         

5) Главная часть - void main()

Реализует меню и "собирает все функции воедино". Создается меню с бесконечным циклом – do … while  , которое позволяет выбирать функции для выполнения. Считывание выбранного пункта осуществляет функция – scanf(),

выполнение по условию – switch …case

6)  Выход

 Выход. При выборе этого пункта меню происходит выход в систему, при этом все введенные данные будут потеряны.

8. Исходныймодульпрограммы

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <alloc.h>

struct spis

{ char family[20]; char year[5];

  struct spis *prev;      // на предыдущую структуру

  struct spis *next;      // на следующую

};

struct spis *head, *tail; // указатели на начало и конец

void build();             // создает новую запись в списке

void view(spis *p);       // просмотр списка

void sort(spis *p);

void bod(spis *p);

void build()

   { spis *p, *pr;

     clrscr();

     pr=NULL;

     printf("*********** Создание списка ***********\n");

     do

       { p=(spis *)malloc(sizeof(spis));

         printf(" Фамилия: "); scanf("%s", p->family); // заполняем фамилию

         printf(" Год: "); scanf("%s", p->year);             // год

         p->prev=pr;

         if (pr!=NULL)

           pr->next=p;

         else

            head=p;

         pr=p;

         printf(" Закончить - < esc >\n");

       }

     while (getch()!=27);

        tail=p;

        tail->next=NULL;

   }

void view(spis *p)

   { clrscr();

     printf("Список\n");

     printf("===============================================\n");

     printf("|            Фамилия           |      Год     |\n");

     printf("===============================================\n");

     if (p!=NULL)

       { while (p!=NULL)

              { printf("|%30s|%14s| \n", p->family, p->year);

                p=p->next;

              }

         printf("===============================================\n");

         printf("Для выхода в меню нажмите любую клавишу.\n");

       }

     else

        puts("Список пуст");

        getch();

   }

void sort(spis *p)

  { spis *pn, *temp;

    int fl;

    fl=0;

    p=head;

    while (p->next!=NULL)

      { temp=p;

        pn=p->next;

        while (pn!=NULL)

          { if (strcmp((pn->family), (temp->family))<0)

              { temp=pn;

                fl=1;

              }

            pn=pn->next;

          }

        if (fl==1)

          { if (temp==tail)    // Удаление последней

              { tail=temp->prev;

                tail->next=NULL;

              }

            else

              { temp->next->prev=temp->prev;   // Удаление из середины

                temp->prev->next=temp->next;

              }

            if (p==head)          // Вставка первой

              { temp->prev=NULL;

                temp->next=p;

                p->prev=temp;

                head=temp;

                p=p->prev;

              }

            else

              { temp->prev=p->prev;  //Вставка в середину

                temp->next=p;

                p->prev->next=temp;

                p->prev=temp;

                p=p->prev;

              }

           fl=0;

          }

          p=p->next;

      }

  }

void bod(spis *p)

  { spis *pn;

    clrscr();

    printf("*********** Добавление записи ***********\n");

    pn=(spis *)malloc(sizeof(spis));

    printf(" Фамилия: "); scanf("%s",pn->family); // заполняем фамилию

    printf(" Год: "); scanf("%4s",pn->year);           // год

    pn->prev=tail;

    pn->next=NULL;

    p->next=pn;

    tail=pn;

    return;

  }

void main()

  { int x;

    do

    { clrscr();

      puts("*************************Меню ****************************");

      puts("\n");

      puts("              1. Создание списка");

      puts("              2. Просмотр списка");

      puts("              3. Добавление в конец списка новой структуры");

      puts("              4. Корректировка списка");

      puts("              5. Выход              ");

      printf("\n\n Введите номер выбранного пункта:  ");

      scanf("%d",&x);

      switch(x)

        { case 1: build();break;

          case 2: view(head);break;

          case 3: bod(tail);break;

          case 4: bod(tail),sort(head),view(head);break;

          default:;

        }

    }

    while(x!=5);

  }

9. Результаты тестирования выполнения программы

Общее меню

Создание списка

Просмотр списка

Добавление в конец списка новой структуры

Печать отсортированного по фамилии списка

10. Список используемой литературы

1 В. В. Подбельский. Язык СИ++. - М.: Финансы и статистика, 2003.

2 Б. И. Березин, С. Б. Березин. Начальный курс С и С++. – М.: Диалог-МИФИ, 1998.

3 Язык Си++: Учеб. пособие.-5-е изд.- М.: Финансы и статистика, 2001.-560 с.: ил.