39286

Двусвязные списки

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

Информатика, кибернетика и программирование

Состав списка и структуры, которая является одним из полей списка, задается программистом. Пользователь вводит информационные поля списка. Условия для обработки – элементы списка, в которых значение поля «goals» поля «info» больше значения, заданного пользователем. Также возможна сортировка исходного списка, заключающаяся в распределении элементов списка в порядке возрастания или убывания значений одного из полей

Русский

2013-10-02

62.59 KB

12 чел.

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования

«Санкт-Петербургский государственный электротехнический

университет «ЛЭТИ» им. В.И.Ульянова (Ленина)»

Факультет компьютерных технологий и информатики

Кафедра вычислительной техники

Отчет

по лабораторной работе № 2

на тему «Двусвязные списки»

по дисциплине «Программирование»

Выполнил: студент группы 2306  Титков Е.В.

Проверила: к.т.н.,  доцент Сискович Т.И.

 

Санкт-Петербург

2013 г.

Цель работы

            Получение практических навыков в работе с двусвязными списками.

Задание

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

Уточнение задания

         Состав списка и структуры, которая является одним из полей списка, задается программистом. Пользователь вводит информационные поля списка. Условия для обработки – элементы списка, в которых значение поля «goals» поля «info» больше значения, заданного пользователем. Также возможна сортировка исходного списка, заключающаяся в распределении элементов списка в порядке возрастания или убывания значений одного из полей «goals” или “age” поля «info». Поле для сортировки и тип сортировки (по возрастанию, убыванию) выбирает пользователь.

Возможно добавление  элемента в уже существующий список и удаление  элемента из списка. Место, в которое нужно добавить, выбирает пользователь (в начало, в конец, после заданного), элемент, который нужно удалить, также выбирает пользователь.  

Описание списка и структуры приведено в следующем пункте.    

Описание структуры

Шаблон:

       struct games

    {

   char name[12];         // Наименование продукта

   int year;                  // Дата выхода

   int rating;               // Рейтинг

    };

где первое поле типа char - адрес первой буквы название продукта, второе поле типа int – дата выхода, третье поле типа int – рейтинг.

Имя структурного типа: Games.

Имя нового типа:MS.

Пример объявления переменной типа NT: MS *games=NULL.

Описание структуры, используемой для организации списка

Шаблон:

      struct list

  {

    MS info;

    struct list *next;

                              struct lits *pred;

  }SP;

где первое поле – данные типа MS, второе и третье поле указатель типа   struct list *.

Имя структуры, используемой для организации список: list.

Имя нового типа: SP.

Пример объявления переменной типа SP: SP *h1=NULL.

Контрольные примеры

     Контрольные примеры обработки приведены в таблице 1 «Контрольные примеры обработки».

Таблица 1. Контрольные примеры обработки

№ п.п.

Исходные данные

Условие обработки

Результат

Наименование

Год выхода

Рейтинг

Наименование

Год выхода

Рейтинг

1

Crysis

2008

7

>8

Crysis 2

2010

9

Crysis 2

2010

9

Crysis 3

2012

10

Crysis 3

2012

10

2

Max Payne

2000

9

>10

Gears World

2012

11

Gears World

2012

11

Shake

2010

3

  Контрольные примеры сортировки по полю rating приведены в таблице 2 «Контрольные примеры сортировки».

Таблица 2. Контрольные примеры сортировки

№ п.п.

Исходные данные

Тип сортировки

Результат

Наименование

Год выхода

Рейтинг

Наименование

Год выхода

Рейтинг

1

Crysis

2008

8

По возрастанию

 Crysis 3

2012

7

Crysis 2

2010

11

Crysis 

2008

8

Crysis 3

2012

7

Crysis 2

2010

11

2

Crysis

2008

8

По убыванию

Crysis 2

2010

11

Crysis 2

2010

11

Crysis

2008

8

Crysis 3

2012

7

Crysis 3

2012

7

Описание переменных главной функции

          Описание переменных главной функции приведено в таблице 3.

Таблица 3. Описание переменных главной функции

 

Имя переменной

Тип переменной

Назначение

k, q, z

int

Вспомогательные переменные

pm, pm2

int

Переменные для выбора пунктов меню

c, ch

char

Переменные, управляющие циклом

h1, rez

SP *

Указатели

Краткое описание алгоритма

При разработке алгоритма предусмотрен контроль над  выполнением пунктов меню.

1) Пользователь выбирает один из пунктов меню: 1 – ввод данных; 2 – вывод данных; 3 – обработка; 4 – добавление элемента; 5 – удаление элемента ; 6 – сортировка; 7 – вывод информационных полей элемента слева и справа от заданного; 0 - выход.

2) Если пользователь выбирает первый пункт меню,  выполняется:

 2.1) ввод наименования, переход к пункту 2.2;

 2.2) ввод года выхода, переход к пункту 2.3;

 2.3) ввод рейтинга, переход к пункту 2.4;

 2.4) вывод сообщения «Завершить ввод?(n/y)».

 2.5) если сh==n, переход к пункту 2.1; если сh!=n, переход к пункту 1.

3) Если пользователь выбирает второй пункт меню, вывод данных переход к пункту 1.

4) Если пользователь выбирает третий пункт меню, выполняется обработка по заданному пользователем условию, переход к пункту 1.

5) Если выбран четвертый пункт меню, выполняется добавление элемента в список.

6) Если выбран 5 пункт, выполняется удаление элемента из списка.

7) Если выбран 6 пункт меню, выполняется сортировка элементов списка, переход к пункту 1.

8) Если выбран 7 пункт меню, завершение программы.

9) Если не выбран ни одни из 2-8 пунктов, вывод сообщения «Ошибка, выберете пункт меню снова».

Описание функций

Описание функции «enter»

Назначение: ввод данных – имени, возраста, кол-ва голов.

Прототип: SP *enter(SP *), где параметр типа SP * - указатель на голову списка, тип возвращаемого значения SP * - указатель на голову списка.

Пример вызова: names = enter(&k), где names - указатель на голову списка.

Описание переменных: описание локальных переменных функции enter приведено в таблице 4.

 Таблица 4. Описание локальных переменных функции enter

Имя переменной

Тип переменной

Назначение

p

SP *

Указатель на голову списка

Описание функции «Output»

Назначение: вывод информационных полей списка.

Прототип: void Output (SP *, char *), первый тип параметра SP * - указатель на голову списка, второй тип параметра char * - указатель на объект типа char.

Пример вызова: Output(games, "Данные:"), где games –адрес первого элемента последовательности структур.

Описание переменных: описание локальных переменны функции Output приведены в таблице 5.

Таблица 5. Описание локальных переменных функции Output

Имя переменной

Тип переменной

Назначение

q

Int

Вспомогательная переменная

Описание функции «confirming»

Назначение: функция обрабатывает исходную список и возвращает полученный список - результат.

Прототип: SP *confirming(SP *)где тип возвращаемого значения SP * - указатель на голову списка, первый тип параметра SP * - адрес первого элемента списка.

Пример вызова: rez=confirming(SP *h1), где rez –  возвращаемое значение типа SP *, h1 - указатель на голову списка.

Описание переменных: описание локальных переменных функции confirming приведено в таблице 6.

Таблица 6. Описание локальных переменных функции obraboka

Имя переменной

Тип переменной

Назначение

d

int

Переменная для хранения введенного кол-ва голов

p, h2, p1, p2

SP *

Вспомогательные переменные

Описание функции «Sort»

Назначение: функция вызывает функцию “NewSort” с соответствующими параметрами для различных типов сортировки(по возрастанию, убыванию)

Прототип: SP *Sort(SP *),где первый тип параметра SP * - указатель на голову списка, второй тип параметра int – размер исходного списка.

Пример вызова: Sort(games).

Описание переменных: описание локальных переменных функции Sort приведено в таблице 7.

Таблица 7. Описание локальных переменных функции Sort

Имя переменной

Тип переменной

Назначение

pm2, pm3, pm4

Int

Переменные для управления меню

Описание функции «Newsort»

Назначение: функция сортирует элементы списка.

Прототип: SP *Newsort(SP *, int, int), где первый параметр типа SP * - указатель на голову списка, второй тип параметра int – флаг, показывающий по какому полю сортировать, третий тип параметра int – флаг, показывающий какой тип сортировки выполнять(по возрастанию убыванию), возвращаемое значение типа SP * - указатель на голову списка.

Пример вызова: h1=Newsort(h1, 1, 1), где первый параметр  h1- указатель на голову списка, второй параметр 1 – флаг, показывающий по какому полю сортировать, третий параметр int – флаг, показывающий какой тип сортировки выполнять(по возрастанию убыванию), возвращаемое значение типа SP * - указатель на голову списка.

Описание переменных: описание локальных переменных функции Newsort приведено в таблице 8.

Таблица 8. Описание локальных переменных функции NewSort

Имя переменной

Тип переменной

Назначение

p,p1,p2,p3

SP *

Вспомогательные переменные

z

int

Вспомогательная переменная

Описание функции «Add»

Назначение: функция добавляет элемент в существующий список.

Прототип: SP *Add(SP *), где тип возвращаемого значения SP *-  указатель на голову списка, первый тип параметра SP * - указатель на голову списка.

Пример вызова: h1=Addh1), где h1 указатель на голову списка.

Описание переменных: описание локальных переменных функции dobav приведено в таблице 9.

Таблица 9. Описание локальных переменных функции dobav.

Имя переменной

Тип переменной

Назначение

d, k

int

Вспомогательные переменные

pm2

int

Переменная  для управления меню

p1,p

SP *

Вспомогательные переменные

Описание функции «Del»

Назначение: функция удаляет элемент из списка.

Прототип:  SP *Del(SP *), где тип возвращаемого значения SP *- указатель на голову списка, первый тип параметра SP *- указатель на голову списка.

Пример вызова: h1=Del(h1), где h1 - указатель на голову списка.

Описание переменных: описание локальных переменных функции Del приведено в таблице 10.

Таблица 10. Описание переменных функции Del

Имя переменной

Тип переменной

Назначение

d,k

int

Вспомогательные переменные

p1, p

SP *

Вспомогательные переменные

Описание функции «Output_2»

Назначение: функция выводит информационные поля элементов, расположенных справа и слева от заданного.

Прототип: void Output_2(SP *), где первый тип параметра SP * - указатель на голову списка.

Пример вызова: Output_2 (h1), где h1 - указатель на голову списка.

Описание переменных: описание локальных переменных функции Output_2 приведено в таблице 11.

Таблица 11. Описание локальных переменных функции Output_2

Имя переменной

Тип переменной

Назначение

k,z

int

Вспомогательные переменные

p, p1, h2, p2

SP *

Вспомогательные переменные

 

Код программы на языке C

#include "stdafx.h"

#include "stdio.h"

#include  <conio.h>

#include <stdlib.h>

#include <tchar.h>

#include <string.h>

#include <locale>

typedef struct games

 {

  char name[12]; //Название продукта

  int year; //Дата выхода

  int rating;//Рейтинг

       }MS;

typedef struct list

  {

   MS info;

   struct list* pred;

   struct list* next;

  }SP;

SP* enter(SP*);  //ввод данныз

void Output(SP*,char*); //вывод данных

SP *confirming(SP*);

SP *Sort(SP*);

SP *NewSort(SP*,int,int);

SP *Add(SP*);

SP *Del(SP*);

void Output_2(SP*);

SP *Free(SP*);

char End(void);

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

{

setlocale(LC_CTYPE, "russian");

 SP*h1=NULL,*rez=NULL;

 int pm,pm2;

 char c=NULL,ch=NULL;

 do

 {

  system("cls");

  puts("******************MAIN MENU*********************");

  puts("1 - Ввод данных\n");

  puts("2 - Вывод списка\n");

  puts("3 - Формирование нового списка\n");

  puts("4 - Добавление элемента в список \n");

     puts("5 - Удаление элемента из списка\n");

  puts("6 - Сортировка\n");

  puts("7 - Вывод слева и справа от заданного элемента\n");

  puts("0 - Выход из программы \n");

  fflush(stdin);

  scanf("%d",&pm);

  switch(pm)

  {

   case 1:

    if(h1==NULL)

     {

       while(h1!=NULL)

        h1=Free(h1);

       while(ch!='y')

      {

       h1=enter(h1);

       puts("\n Закончить ввод данных? (y/n)?\n");

       ch=getch();

      }

    }

    else

     puts("Вы уже вводили данные!Используйте пункты добавление элементов\n");

    getch();

    break;

   case 2:

    if(h1!=NULL)

     Output(h1,"Список:");

    else

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

    getch();

    break;

               case 3:

    if(h1!=NULL)

      {

       while(rez!=NULL)

        rez=Free(rez);

       rez=confirming(h1);

       if(rez!=NULL)

         Output(rez,"Результат обработки:");

       else

        puts("В списке нет элементов с заданным условием \n");

       getch();

    }

    else

     puts("Обработка невозможна - список пуст.\n");

    getch();

    break;

   case 4:

    if(h1!=NULL)

     h1=Add(h1);

    else

     puts("Добавление элементов невозможно т.к. список пуст\n");

    getch();

    break;

   case 5:

    if (h1!=NULL)

     h1=Del(h1);

    else

     puts("Удаление невозможно.список пуст.\n");

    getch();

    break;

   case 6:

    if (h1!=NULL)

     h1=Sort(h1);

    else

     puts("Сортировка невозможно ,список пуст.\n");

    getch();

    break;

   case 7:

    if (h1!=NULL)

    Output_2(h1);

    else

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

    getch();

    break;

   case 0:

    puts("Выполнение программы завершено");

    c='y';

    break;

   default:

    puts("Ошибка ввода пункта меню");

    getch();

    break;

  }

 }

 while(c!='y');

 return 0;

}

//***************************************************************************//

SP *enter(SP* head)

{

 SP *p=NULL;

fflush(stdin);

p=(SP*)malloc(sizeof(SP));

 puts("Введите название продукта");

gets(p->info.name);

puts("Введите дату выхода продукта");

 scanf("%d",&(p->info.year));

puts("Введите рейтинг продукта");

scanf("%d",&(p->info.rating));

p->next=head;

 if(head!=NULL)

 head->pred=p;

 head=p;

 return head;

}

//****************************************************************************//

void Output(SP *h1,char *s)

{

puts(s);

puts("  Название    Дата выхода     Рейтинг");

 while(h1!=NULL)

 {

  printf("");

  puts(h1->info.name);

  printf("          %d         %d",h1->info.year,h1->info.rating);

  printf("/n");

  fflush(stdin);

  h1=h1->next;

 }

}

//***********************************************************************//

SP* confirming(SP *h1)

{

 int d;

 SP*h2=NULL, *p=NULL;

 puts("Введите рейтинг продукта");

 scanf("%d",&d);

 h2=h1;

 scanf("%d", &d);

h2=h1;

 while(h2!=NULL)

  {

 if((h2->info.rating)<d)

   {

    p=h2->next;

    if(h2->next!=NULL || h2->pred!=NULL)

   {

     if(h2->next!=NULL)

    {

      if(h2->pred!=NULL)

     {

       h2->next->pred=h2->pred;

       h2->pred->next=h2->next;

     }

      else

     {

       h2->next->pred=NULL;

       h1=h2->next;

     }

    }

     else

    h2->pred->next=NULL;

     free(h2);

     h2=p;

   }

    else

      {

     free(h1);

     h2=h1=NULL;

   }

  }

 else

  h2=h2->next;

  }

puts("Обработка завершена\n");

 return h1;

}

     

SP *Sort(SP*h1)

{

 int pm2=0,pm3=0,pm4=0;

 int z=0;

 puts("Выберите тип сортировки");

 puts("1-сортировка по году");

 puts("2-сортировка по рейтингу");

 puts("3-Выход в главное в меню");

 scanf("%d",&pm2);

 do

   {

    switch(pm2)

     {

    case 1:

     puts("Выберите тип сортировки");

     puts("1-сортировка по убыванию");

                 puts("2-сортировка по возрастанию");

                 puts("3-Выход в под-меню");

     scanf("%d",&pm3);

     switch(pm3)

      {

       case 1:

         h1=NewSort(h1,1,1);

         z=1;

         break;

       case 2:

         h1=NewSort(h1,1,2);

         z=1;

         break;

       case 3:

           break;

       default:

         puts("Вы ошиблись с выбором пункта меню,введите еще раз!");

         getch();

         break;

      }

    break;

    

    case 2:

       puts("Выберите тип сортировки");

       puts("1-сортировка по убыванию");

                   puts("2-сортировка по возрастанию");

                   puts("3-Выход в под-меню");

       getch();

       scanf("%d",&pm4);

       switch(pm4)

          {

       case 1:

          h1=NewSort(h1,2,1);

          z=1;

          break;

       case 2:

          h1=NewSort(h1,2,2);

          z=1;

          break;

       case 3:

          break;

       default:

          puts("Вы ошиблись с выбором пункта меню,введите еще раз!");

          getch();

          break;

       }

    case 3:

     break;

    default:

        puts("Вы ошиблись с выбором пункта меню,введите еще раз!");

     getch();

     break;

    }

    }

    while (z==0);

 return h1;

   }

//********************************************************************************//

SP* NewSort(SP*h1,int place,int s)

 {

   SP *p=NULL,*p1=NULL,*p2=NULL,*p3=NULL;

  int z=0;

  p=h1;

  if(p->next!=NULL)

{

  while(p!=NULL)

 {

   p1=p->next;

   p2=p1;

   if(p1!=NULL)

     p3=p1->next;

   while(p1!=NULL)

  {

    if((((p1->info.year>p->info.year && s==1) || (p1->info.year<p->info.year && s==2))&&place==1) || (((p1->info.rating>p->info.rating && s==1) || ((p1->info.rating<p->info.rating && s==2)))&&place==2) || ((((strcmp(p1->info.name, p->info.name)>0) && s==1) || ((strcmp(p1->info.name, p->info.name)<0)&&s==2)) && place==3))

   {

     if(p->next!=p)

    {

      p1->pred->next=p;

      p->next->pred=p1;

      p1->next=p->next;

    }

     else

    p1->next=p;

     if(p->pred!=NULL)

    p->pred->next=p;

     p1->pred=p->pred;

     p->pred=p2;

     p->next=p2;

     if(p3!=NULL)

    p3->pred=p;

     p=p1;

   }

    p=p3;

    if(p1!=NULL)

   {

     p2=p1->pred;

     p3=p1->next;

   }

  }

   if(p->pred==NULL)

  h1=p;

   p=p->next;

 }

}

 else

puts("В списке всего один элемент\n");

 puts("Операция сортировки завершена\n");

 getch();

 return h1;

}

//****************************************************************************************///

SP *Add(SP *h1)

{

 SP *p1=NULL,*p=NULL;

 int pm2=0;

 int d=0,k=1;

 p=h1;

p1=enter(p1);

puts("Куда необходимо добавить элемент?");

puts("1 - В начало");

puts("2 - В конец");

puts("3 - После заданного");

 scanf("%d",&pm2);

 switch(pm2)

 {

  case 1:

    p1->next=h1;

    h1->pred=p1;

    h1=p1;

    h1->pred=NULL;

    break;

  case 2:

    while((p->next)!=NULL)

     p=p->next;

    p->next=p1;

    p1->next=NULL;

    p1->pred=p;

    break;

  case 3:

    puts("Задайте элемент,после которого нужно добавить информацию");

    scanf("%d",&d);

     while(p!=NULL && k!=d)

    {

   p=p->next;

   k++;

    }

  if(k==d)

    {

   if(p->next!=NULL)

     {

    p1->next=p->next;

    p->next->pred=p1;

    p->next=p1;

     }

   else

     {

    p->next=p1;

    p1->pred=p;

    p1->next=NULL;

              }

    }

  else

    printf("Элемента номер %d не существует!", d);

  break;

   default:

    puts("Ошибка ввода пункта меню");

    getch();

    break;

}

puts("Операция добавление успешно завершена");

getch();

 return h1;

}

//**************************************************************************************//

SP *Del(SP *h1)

 {

  SP *p=NULL,*p1=NULL;

  int d=0,k=0;

  p=h1;

  puts("Введите номер элемента ,который нужно удалить. \n");

  scanf("%d",&d);

   while(p->next!=NULL && k!=d)

{

  p=p->next;

  k++;

}

 if(k==d)

 {

  if(d!=1)      // если заданный элемент не первый

 {

   if(p->next!=NULL)

  {

    p->pred->next=p->next;

    p->next->pred=p->pred;

  }

   else

  p->pred->next=NULL;

 }

  else         // заданный элемент первый

 {

   if(p->next!=NULL)

  {

    h1=p->next;

    h1->pred=NULL;

  }

   else

     h1=NULL;

 }

  }

 else

printf("Элемента  %d не существует!", d);

 free(p);

 puts("Операция удаления успешно завершена\n");

 return h1;

}

//*************************************************************************************//

void Output_2(SP *h1)

{

 SP *p=NULL,*p1=NULL,*p2=NULL;

 int k=0,z=1;

p=h1;

puts("Sleva i sprava ot kakogo elemena vivesti?\n");

 scanf("%d", &k);

 while(p->next!=NULL && z!=k)

 {

  p=p->next;

  k++;

}

 if(k==z)     // заданный элемент существует

{

  if(k==1) // выбран первый элемент

 {

   puts("Элемент слева отсуствует\n");

   if(p->next!=NULL)

  {

    p1=p->next;

    p2=p->next->next;

    p1->next=NULL;

    Output(p1, "");

    p1->next=p2;

  }

   else

  puts("Элемент справа отсуствует\n");

 }

  else    // выбран не первый элемент

 {

   if(p->next!=NULL)

  {

    p1=p->pred;

    p2=p->next->next;

    p1->next=p->next;

    p1->next->next=NULL;

    Output(p1, "");

    p1->next->next=p2;

    p1->next=p;

  }

   else

  {

    puts("Элементы справа отсуствуют\n");

    p1=p->pred;

    p1->next=NULL;

    Output(p1, "");

             p1->next=p;

           }

 }

}

 else

   printf("Элемента %d не сушесвует!",k);

 getch();

}

SP *Free(SP *h1)

{

 SP *temp=NULL;

 temp=h1;

 while(temp!=NULL)

   {

    temp=h1->next;

    free(h1);

    h1=temp;

 }

 return NULL;

 }

//************************************************************************************//Результаты выполнения программы

При выполнении программы полученные результаты совпадают с приведенными в таблице 1 "Контрольные примеры". Ошибок не обнаружено.

Выводы

При выполнении лабораторной работы получены практические навыки в работе с односвязными списками на языке С/С++.


 

А также другие работы, которые могут Вас заинтересовать

58662. Морфологический разбор имени прилагательного 41.5 KB
  Напомню что наша тема называется морфологический разбор имени прилагательного. Во-вторых постоянные признаки разряд прилагательного: качественное относительное или притяжательное непостоянные признаки число род падеж.
58664. Имя существительное 37.5 KB
  Какие у вас возникли вопросы Как называется На какие вопросы отвечает Что обозначает Это и есть цель нашей деятельности. Мы: 1 познакомимся с новой частью речи; 2 узнаем на какие вопросы она отвечает; 3 а также научимся распознавать её среди других слов.
58665. Изменение имен существительных по числам 51.5 KB
  Цель урока: Развивать умение изменять существительные по числам различать род. Образовательные цели научиться употреблять в речи имена существительные классифицировать их;...
58666. М.В.Ломоносов. Оды 48.5 KB
  В чём необычность курса обучения пройденного Ломоносовым Что такое теория трёх штилей 2 Запись в тетрадях. Он ценит в царе то что он царствуя служил свои законы сам примером утвердил монаршу власть скрывал чтоб нам открыть науки о том как...
58667. Отечественная война 1812 года 37 KB
  Цель: Создать условия для формирования исторического представления об Отечественной войне 1812 года на уроке истории при помощи ЦОР Задачи: Образовательные: познакомить с событиями Отечественной войны 1812 года, научить анализировать историческую видео информацию...
58669. Создание web-страниц. Ссылки (гиперссылки) 49.5 KB
  У Вас имеется две страницы. shablon.html и index.html. Создадим ссылку со второго на первый, так как, обычно, файл первой страницы любого сайта называют именно index.html.
58670. Решение алгебраических уравнений высших степеней методом замены переменной 185 KB
  Суть этого метода заключается в том что путём замены некоторого выражения входящего в уравнение понижается его степень. Представитель каждой группы находит на доске свое уравнение записанное в общем виде и раскрывает суть его решения сначала решаются обычные уравнения.