ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 7

Тема: «Линейный однонаправленный список»

Цель: научиться создавать и просматривать линейный однонаправленный список, добавлять элементы в список, удалять элементы из списка, выполнять поиск по списку.

Ход работы

 

Теоретические обоснования

Список – линейная последовательность элементов, каждый из которых содержит указатели (ссылается) на своих соседей.

Основные свойства списка:

-                     элемент списка доступен в программе через указатель. Между указателем и элементом списка имеется такая же взаимосвязь, как между индексом в массиве и элементом массива;

-                     в программе список задается посредством заголовка – указателя на первый элемент списка;

-                     порядок следования элементов определяется последовательностью связей между элементами. Изменение порядка следования элементов (вставка, удаление) осуществляются изменением переустановкой указателей на соседние элементы.

список является структурой данных  с последовательным доступом. Для получения n-го по счету элемента необходимо последовательно пройти по цепочке от элемента, на который имеется указатель (например, от заголовка);

Список обладает свойством локальности изменений: при вставке/удалении элемента изменения касаются только текущего и его соседей. Вспомним массив: при вставке/удалении его элементов происходит физическое перемещение (сдвиг) всех элементов от текущего до конца.

Отсюда следует, что преимущества списков проявляются в таких структурах данных, где операции изменения порядка превалируют над операциями доступа и поиска.

 

Описание списка

 

struct    spisok                             // определение структурированного типа

{           int     value;                   // значение элемента (хранимые данные)

            elem *next;                    // единственный указатель или

            elem *next,*prev;            // два указателя или

            };

 

Переменная такого типа может содержать один, два и большее количество указателей на аналогичные переменные. Но это еще не список, а описание его составляющих (элементов) как типа данных.

Списковые структуры данных обычно являются динамическими по двум причинам:

-                     сами переменные таких структур создаются как динамические переменные, то есть количество их может быть произвольным;

-                     количество связей между переменными и их характер также определяются динамически в процессе работы программы.

В зависимости от связей списки бывают следующих видов:

односвязные - каждый элемент списка имеет указатель на следующий;

двусвязные - каждый элемент списка имеет указатель на следующий и на предыдущий элементы;

циклические - первый и последний элементы списка ссылаются друг на друга и цепочка представляет собой кольцо.

Отсюда же следует, что «обычные» (разомкнутые) списки имеют в качестве ограничителя последовательности NULL-указатель. Соответственно, возможет случай пустого списка, в котором заголовок - указатель на первый элемент также содержит значение NULL.

Итак, положим, что список существует. Работа со списками осуществляется исключительно через указатели. Каждый из них может перемещаться по списку (переустанавливаться с элемента на элемент), приобретая одну из смысловых интерпретаций – указатель на первый, последний, текущий, предыдущий, новый и т.п. элементы списка.

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

 

 

Список

Массив

Определение

struct spisok {int val;

spisok *next, *prev; };

int A[100];

int n;

Пустой список

spisok *head=NULL;

n=0;

Первый

spisok *p;   p= head;

int i=0;

Следующий

p->next

i+1

Предыдущий

p->prev

i-1

К следующему

p=p->next

i++

К предыдущему

p=p->prev

i--

Просмотр

for (p= head; p!=NULL; p=p->next)

         …p->val…

for (i=0; i<n; i++)

        …A[i]…

Проверка  на последний

p->next ==NULL

i==n-1

К последнему

for (p= head; p->next!=NULL;

p=p->next);

i=n-1

Новый

spisok *q = new list;

q->val = v;

int v;

Включить последним

for (p= head; p->next!=NULL;

p=p->next);

q->next=NULL; p->next=q;

A[n++]=v;

Включить первым

q->next=head; head=q;

for (i=n; i>0; i--) A[i]=A[i-1];

A[0]=v;

 

Задание 1. Создать список, просмотреть его и удалить из памяти.

Задание 2. Создать список, просмотреть его, удалить первый и последний элементы списка, найти максимальный элемент в списке, добавить после максимального элемента списка новый элемент, равный 1000, удалить список из памяти.

Задание 3. Опишите структуру, содержащую фамилию, средний балл студента, и указатель на следующий элемент. Запишите исходные данные в файл, производя чтение из файла, создайте однонаправленный список данных. В списке найдите количество студентов, имеющих средний балл больше или равный 4, выведите информацию о таких студентах.

Задание 4. Данные одного списка пополнить данными другого списка.

 

Выполнение задания 1.

 

//подключаем библиотеки

#include <iostream.h>

#include <iomanip.h>

//структура, содержащая хранимые данные и

//указатель на следующий элемент

struct spisok

{

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

            spisok *next;   //указатель на переменную типа структура spisok

};

int main()

{

            system("chcp 1251>nul");

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

            spisok *head=NULL; //создание пустого списка

            int i,n;

            cout<<"Введите количество элементов списка"<<endl; cin>>n;

            for(i=1; i<=n; i++)

            {

                        spisok *temp=new spisok;     //создание нового элемента типа spisok

                        cout<<"Введите элемент списка ";           

                        cin>>temp->value;     //запись нового значения

                        cout<<endl;

                        temp->next=head;      //введенный элемент сделать первым в списке

                        head=temp;                //первым элементом стал введенный элемент temp

            }

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

            spisok *temp=head; //Определяем указатель, который изначально равен адресу начала списка

            while (temp!=NULL) //Пока не встретит пустое значение, т.е. последний элемент

            {

                        cout<<temp->value<<" "; //Выведет значение элемента temp->value из списка

                        temp=temp->next;            //Переходим на следующий элемент

            }

            //удаление списка из памяти

            while (head!=NULL)  //Пока не встретится пустой адрес, т.е. последний элемент

     {   

        spisok *temp=head->next; //Временная переменная для хранения адреса следующего элемента

        delete head;                    //Освобождаем адрес, обозначающий начало

        head=temp;                    //Меняем адрес на следующий

     }

            system("pause");

            return 0;

}

 

Выполнение задания 2.

 

#include <iostream.h>

#include <iomanip.h>

struct spisok

{

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

            spisok *next;   //указатель на переменную типа структура spisok

};

int main()

{

            system("chcp 1251>nul");

            spisok *head=NULL;

            int i,n;

            cout<<"Enter count of the elements  "; cin>>n;

            cout<<endl;

            for (i=1; i<=n; i++)

            {

                        spisok *tmp=new spisok;

                        cout<<"Enter next element"; cin>>tmp->value;

                        cout<<endl;

                        tmp->next=head;

                        head=tmp;

            }

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

            spisok *tmp=head;

            while(tmp!=NULL)

            {

                        cout<<tmp->value<<"  ";

                        tmp=tmp->next;

            }

            //удаление первого элемента

            tmp=head;

            tmp=tmp->next;

            cout<<"second element="<<tmp->value<<endl;

            delete head;

            head=tmp;

            //дойти до последнего елемента

            spisok *q=new spisok;           //будет хранить предпоследний элемент

            tmp=head;                                          //будет хранить последний элемент

            do

            {

                        q=tmp;

                        tmp=tmp->next;        

            }

            while(tmp->next!=NULL);

            //удаление последнего элемента

            q->next=NULL;

            delete tmp;

            //находим максимальный   

            int max=-10000;

        tmp=head;

            while(tmp!=NULL)

            {

                        if (tmp->value > max)

                        max=tmp->value;

                        tmp=tmp->next;

            }

            cout<<"max="<<max<<endl;           

            //добавить после максимального элемента списка элемент = 1000

    tmp=head;

            while(tmp!=NULL)

            {

                        if (tmp->value == max)

                                   {

                                               spisok *t=new spisok;

                                               t->value=1000;                                             

                                               t->next=tmp->next;

                                               tmp->next=t;

                                               exit;                                       

                                   }

                        tmp=tmp->next;

            }

 

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

    tmp=head;

            while(tmp!=NULL)

            {

                        cout<<tmp->value<<"  ";

                        tmp=tmp->next;

            }

            //удаление списка

            while(head!=NULL)

            {

                        tmp=head->next;

                        delete head;

                        head=tmp;

            }

            system("pause");

            return 0;

}

Выполнение задания 3.

 

#include <iostream.h>

#include <iomanip.h>

#include <fstream.h>

//структура, содержащая фамилию, средний балл студента, и указатель на следующий элемент

struct spisok

{

            char fam[20];

            float bal;

            spisok *next;   //указатель на переменную типа структура spisok

};

struct stud

{

            char fam[20];

            float bal;

};

int main()

{

            system("chcp 1251>nul");

            //создание файла

            ofstream f1;

            f1.open("students.dat",ios::binary);

            int i,n;

            cout<<"Введите количество студентов"<<endl;

            cin>>n; cin.get();

            stud s;

            for(i=1; i<=n; i++)

            {

                        cout<<"Введите фамилию студента: ";     

                        cin.getline(s.fam,20);

                        cout<<"Введите средний бал: ";    

                        cin>>s.bal;

                        cin.get();                    

                        cout<<endl;

                        f1.write((char*)&s,sizeof s);

            }

            f1.clear()                     ;

            f1.close();

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

            spisok *head=NULL;

            ifstream f2;

            f2.open("students.dat",ios::binary);

            while(f2.read((char*)&s,sizeof s))

            {

                        spisok *tmp=new spisok;      

                        strcpy(tmp->fam , s.fam);

                        tmp->bal=s.bal;

                        //введенный элемент сделать первым в списке

                        tmp->next=head;                                          

                        //первым элементом стал введенный элемент tmp

                        head=tmp;                             

            }

            f2.clear();

            f2.close();

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

            spisok *tmp=head; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {

                        cout<<setw(20)<<left<<tmp->fam<<" "<<setw(5)<<tmp->bal<<endl; //Выводим значение элемента tmp из списка

                        tmp=tmp->next; //Переходим на следующий элемент

            }

            // посчитать количество студентов, имеющих ср балл >=4

            cout<<endl<<"Cтуденты со средним баллом >=4:"<<endl;

            int kol=0;

            tmp=head;

            while(tmp!=NULL)

            {

                        if (tmp->bal >=4)

                                   {

                                               cout<<tmp->fam<<"  "<<tmp->bal<<endl;

                                               kol++;

                                   }

                                   tmp=tmp->next;

            }

            //удаление списка из памяти

            while (head!=NULL)  //Пока не втретится пустой адрес, т.е. последний элемент

     {   

        spisok *tmp=head->next; //Временная переменная для хранения адреса следующего элемента

        delete head; //Освобождаем адрес, обозначающий начало

        head=tmp; //Меняем адрес на следующий

     }

            system("pause");

            return 0;

}

 

Выполнение задания 4.

 

#include <iostream.h>

#include <iomanip.h>

#include <ctime>

//структура, содержащая фамилию, средний балл студента, и указатель на следующий элемент

struct spisok

{

            char fam[20];

            float bal;

            spisok *next;   //указатель на переменную типа структура spisok

};

 

int main()

{

            system("chcp 1251>nul");

            //Создание первого списка

            spisok *head1=NULL;

            int i,n1;

            cout<<"Введите количество студентов"<<endl;

            cin>>n1;

            cin.get();

            for(i=1; i<=n1; i++)

            {

                        spisok *tmp=new spisok;       //создание нового элемента типа spisok

                        cout<<"Введите фамилию студента: ";     

                        cin.getline(tmp->fam,20);

                        cout<<"Введите средний бал: ";    

                        cin>>tmp->bal;

                        cin.get();                     cout<<endl;

                        tmp->next=head1;      //введенный элемент сделать первым в списке

                        head1=tmp;    //первым элементом стал введенный элемент tmp

            }

            //Создание второго списка

            spisok *head2=NULL;

            int n2;

            cout<<"Введите количество студентов"<<endl;

            cin>>n2;

            cin.get();

            for(i=1; i<=n2; i++)

            {

                        spisok *tmp=new spisok;       //создание нового элемента типа spisok

                        cout<<"Введите фамилию студента: ";     

                        cin.getline(tmp->fam,20);

                        cout<<"Введите средний бал: ";    

                        cin>>tmp->bal;

                        cin.get();                     cout<<endl;

                        tmp->next=head2;      //введенный элемент сделать первым в списке

                        head2=tmp;    //первым элементом стал введенный элемент tmp

            }

            //просмотр первого списка

            cout<<"First spisok"<<endl;

            spisok *tmp=head1; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {

                        //Выведет значение элемента tmp из списка

                        cout<<setw(20)<<left<<tmp->fam<<" "<<setw(5)<<tmp->bal<<endl;

                        tmp=tmp->next; //Переходим на следующий элемент

            }

            //просмотр второго списка 

            cout<<endl<<"Second spisok"<<endl;

            tmp=head2; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {          //Выведет значение элемента tmp из списка

                        cout<<setw(20)<<left<<tmp->fam<<" "<<setw(5)<<tmp->bal<<endl;

                        tmp=tmp->next; //Переходим на следующий элемент

            }

            //добавление к первому списку элементов второго списка

            cout<<endl<<"ADD"<<endl;

            tmp=head1; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp->next!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {

                        //Выведет значение элемента tmp из списка

                        cout<<setw(20)<<left<<tmp->fam<<" "<<setw(5)<<tmp->bal<<endl;                             tmp=tmp->next; //Переходим на следующий элемент

            }

            tmp->next=head2;

            //просмотр общего списка  

            cout<<endl<<"Third spisok"<<endl;

            tmp=head1; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {

                        //Выведет значение элемента tmp из списка

                        cout<<setw(20)<<left<<tmp->fam<<" "<<setw(5)<<tmp->bal<<endl;                             tmp=tmp->next; //Переходим на следующий элемент

            }

            //добавление к первому списку четных элементов второго списка

            spisok *tmp1=head1; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp1->next!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {

                        tmp1=tmp1->next; //Переходим на следующий элемент

            }

            int k=1;                       //переменная для определения четного или нечетного элемента

            spisok *tmp2=head2;

            while (tmp2!=NULL)

            {

                        if (k%2==1)   

                         tmp2=tmp2->next; //Переходим на следующий элемент

                         else

                                    { spisok *tmp=new spisok;    //создание нового элемента типа spisok

                                     tmp1->next=tmp;

                                    strcpy(tmp->fam, tmp2->fam);

                                     tmp->bal=tmp2->bal;

                                     tmp->next=NULL;

                                     tmp1=tmp;

                                    tmp2=tmp2->next;

                                   }

                        k++;

            }

            //просмотр общего списка  

            cout<<endl<<"Third spisok"<<endl;

            tmp=head1; //Определяем указатель, который изначально он равен адресу начала списка

            while (tmp!=NULL) //До тех пор пока не встретится пустое значение, т.е. последний элемент

            {

                        cout<<setw(20)<<left<<tmp->fam<<" "<<setw(5)<<tmp->bal<<endl;                             tmp=tmp->next;

            }

            //удаление первого списка из памяти

            while (head1!=NULL) 

   {   

        tmp=head1->next; //Временная переменная для хранения адреса следующего элемента

        delete head1; //Освобождаем адрес, обозначающий начало

        head1=tmp; //Меняем адрес на следующий

     }

            //удаление второго списка из памяти

            while (head2!=NULL)      

    {   

        tmp=head2->next; //Временная переменная для хранения адреса следующего элемента

        delete head2; //Освобождаем адрес, обозначающий начало

        head2=tmp; //Меняем адрес на следующий

     }

            system("pause");

            return 0;

}

 

Решить самостоятельно:

 

Написать программу, которая создает, просматривает список и решает следующие задачи:

 

            Найти максимальный элемент в списке. Добавить его в начало списка.

Найти произведение элементов в списке. Последний элемент списка заменить на полученное значение произведения.

Найти количество элементов списка, кратных трем.

Найти количество четных элементов списка.

Удалить последний элемент списка, если он равен нулю. Удалить первый элемент списка, если он отрицательный.