Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное государственное бюджетное образовательное учреждение высшего
профессионального образования
«Санкт-Петербургский государственный электротехнический
университет «ЛЭТИ» им. В.И.Ульянова (Ленина)»
Факультет компьютерных технологий и информатики
Кафедра вычислительной техники
Отчет
по лабораторной работе № 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 "Контрольные примеры". Ошибок не обнаружено.
Выводы
При выполнении лабораторной работы получены практические навыки в работе с односвязными списками на языке С/С++.