Разработка программ обработки двусвязных линейных списков

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

Федеральное государственное  автономное

образовательное учреждение

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

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ»

 

Институт Космических  и Информационных Технологий

Кафедра Информатики и  Вычислительной Техники

 

 

 

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №6

Вариант №7

Тема: Разработка программ обработки двусвязных линейных списков.

 

 

 

Преподаватель                         ______________                           Цветцих Д.В.

                                                                     подпись, дата                                       инициалы, фамилия

 

Студент    КИ11-09Б       ________________      __________     Козлов Г.А.

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

 

 

 

 

 

Красноярск 2012

 

Цель работы

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

 

Порядок выполнения работы

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

 

Задание

Построить двусвязный список из входной последовательности натуральных чисел и удалить из списка узел, содержащий первое простое число.

 

Описание хода выполнения работы

 

Код программы

#include <stdio.h>

#include <iostream>

#include <Windows.h>

 

using namespace std;

struct node //описнаие структуры списка

{

int value; //значение

node *ll;//левая ссылка

node *rl;//правая ссылка

};

void print_node(node *p, int n)

{

if(n)

{

cout<<"\nСправа на лево"<<endl;

while(p !=NULL)

{

cout<<p->value<<endl;

p = p->rl;

}

}

else

{

cout<<"\nСлева на право"<<endl;

while(p !=NULL)

{

cout<<p->value<<endl;

p = p->ll;

}

cout<<"\n";

}

}

int f_simple(int n) // функция посика простого числа

{

if(n==1)

{

return 0;

}

else

{

if(n==2) { cout<<n<<" "; return 1;}

else

{

 

for(int i=2; i<=n/2;i++)

{

if(n%i==0)

{

return 0;

}

}

cout<<n<<" ";

return 1;

}

}

}

void main()

{

SetConsoleCP(1251);

    SetConsoleOutputCP(1251); // русская локаль

node *head; //начало списка

node *tail; // конец списка

node *temp, *before; //рабочии указатели

int n=0;

//----------------------создание  первого узла

cin>>n; // ввод числа

temp = new node;

temp->value = n;

temp->ll = NULL;

temp->rl = NULL;

tail = temp; // указатель на конец

before  = temp; // Второй рабочий указатель хранит адрес предпоследнего узла

 

while(cin>>n) // пока не конец ввода

{

temp = new node;

temp->value = n;

temp->rl = before;

before->ll = temp;

before = temp;

}

temp->ll = NULL;

head = temp; // Указатель на начало

 

print_node(head,1); //вывод списка слева на право

print_node(tail,0);// вывод на оборот --//--

//-------------------------------------------------Удаление  простого числа из списка

node *w; //рабочий указатель

w = tail;

cout<<"Простые числа: ";

while(w!=NULL) // обход списка

{

if(f_simple(w->value))

{

if(w == head) // удаление с начала

{

w->rl->ll = NULL;

head = w->rl;

break;

}

else

if(w == tail) // удаление с конца

{

w->ll->rl = NULL;

tail = w->ll;

break;

}

else // удаление из середины

{

w->ll->rl = w->rl;

w->rl->ll = w->ll;

break;

}

}

w = w->ll;

}

 

print_node(head,1); //вывод списка слева на право

 

system("pause"); // задержка экрана

}

 

 

Блок-схема программы

 

 

Вывод

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