Файл: Сортировка данных в массиве. Оценка эффективности метода.pdf

Задание

Написать программу, строящую следующую списочную структуру. Каждый элемент списка состоит из трех полей: первое поле – для связи элементов в одном списке, второе – информационное (заполняется вводимой последовательностью целых чисел , в которой 0 отмечает конец каждого списка; числа и не вводятся, а подсчитываются при вводе последовательности), третье поле – для связи двух линейных списков. Если , то второй список должен быть дополнен элементами с нулевыми информационными полями; при первый список должен оказаться короче второго. Ссылочным полям, которые никуда не ведут, должно быть присвоено значение NIL. Ссылочная переменная используется для доступа к списочной структуре.

Линейные списки и работа с ними

Линейный список – это способ организации элементов некоторого множества путём указания для каждого из элементов ссылки на следующий или/и предыдущий элемент.

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

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

Если последний элемент связать с первым с помощью указателя, получим кольцевой список.

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

Над списками можно выполнять следующие операции:

• начальное формирование списка (создание первого элемента);

• добавление элемента в конец списка;

• чтение элемента с заданным ключом;

• вставка элемента в заданное место списка (до или после элемента с заданным ключом);

• удаление элемента с заданным ключом;

• упорядочивание списка по ключу.

Рассмотрим однонаправленный список.

Каждый элемент списка может быть описан следующей структурой:

---

struct List {

int inf; //информационное поле

List *next; //ссылочное поле для связи элементов в списке

};

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

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

- определение нулевого адреса для начала и конца списка

pBeg=0;

pEnd=0;

pBeg

* nil

pEnd

* nil

Добавление элемента в список

а) добавление первого элемента

- исходное состояние

pBeg

* nil

pEnd

* nil

tmp

?

* ?

- выделение памяти под первый элемент списка

pBeg

* nil

pEnd

* nil

next

inf

tmp

?

*

* ?

?

- занесение информации в первый элемент

tmp->inf=d;

tmp->next=0;

pBeg

* nil

pEnd

* nil

next

inf

tmp

?

*

d

* nil

- установка указателей начала и конца списка на первый элемент

pBeg=tmp;

pEnd=tmp;

pEnd

pBeg

*

next

inf

tmp

?

*

d

* nil

*

б) добавление второго и последующих элементов в конец списка

- исходное состояние

*

pEnd

pBeg

*

d3

* nil

d2

* nil

d1

* nil

tmp

?

* ?

- выделение памяти под новый элемент списка

next

inf

tmp

?

*

* ?

?

*

pEnd

pBeg

*

d3

* nil

d2

* nil

d1

* nil

- занесение информации в новый элемент списка

tmp->inf=d;

tmp->next=0;

next

inf

tmp

?

*

d

* nil

pEnd

pBeg

*

*

d3

* nil

d2

* nil

---

d1

* nil

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

pEnd->next=tmp;

d

*

tmp

* nil

*

pEnd

pBeg

*

d3

* nil

d2

* nil

d1

* nil

- перемещение указателя конца списка на новый элемент

pEnd=tmp;

tmp

pEnd

pBeg

*

*

*

d3

* nil

d2

* nil

d1

* nil

d

* nil

Удаление элемента из списка

- исходное состояние

*

pEnd

pBeg

*

d3

* nil

d2

* nil

d1

* nil

tmp

?

*

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

tmp=pBeg;

*

pEnd

pBeg

*

d3

* nil

d2

* nil

d1

* nil

tmp

*

- перемещение указателя начала списка на следующий элемент

pBeg=tmp->next;

tmp

*

*

pEnd

pBeg

*

d3

* nil

d2

* nil

d1

* nil

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

tmp->next=0;

tmp

*

d1

* nil

pEnd

pBeg

*

*

d3

* nil

d2

* nil

- освобождение памяти, где находится удаляемый элемент

Аналогично можно реализовать и другие операции со списком.

Блок-схема алгоритма решения задачи

Программная реализация

Для реализации алгоритма формирования списочной структуры на языке C++ в среде программирования Visual Studio 2008 выполним следующие действия:

1. подключаем заголовочные файлы с помощью директивы #include и указываем, что будем использовать пространство имен std

---

#include "stdafx.h"

#include <iostream>

#include <fstream>

using namespace std;

1. описываем структуру List2 с тремя полями:

• целочисленное поле inf – информационное;
• ссылочное поле next – для связи элементов в одном списке;
• ссылочное поле nextL – для связи двух линейных списков.

struct List2 {

int inf; //информационное поле

List2 *next; //ссылочное поле для связи элементов в списке

List2 *nextL; //ссылочное поле для связи двух линейных списков

};

1. Объявляем функции

void create_List2(List2**,int,int);

void add_to_List2(List2**,int);

void print_List2(List2*);

void print_List2_to_file(List2*);

1. Описываем функцию, с которой начинается выполнение программы:

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

setlocale(LC_ALL, "Russian");//использование кириллицы в консоли

List2 *S=0; //ссылочная переменная для доступа к списочной структуре

int *a=new int[100]; //вводимая последовательность целых чисел

int n=0,k=0; //количество элементов в списке 1 и списке 2 списочной структуре

int i=0, p=0, x; //вспомогательные переменные

bool done = false;

cout<<"Введите последовательность {a} целых чисел:"<<endl;

while (p!=2)

{

do

{

cin>>x;

if (x!=0) {

*(a+i)=x;

i++;

}

}while (x!=0);

p++;

if (p==1) n=i;

}

k=i-n;

//cout<<"Последовательность чисел {a}:"<<endl;

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

// cout<<*(a+i)<<' ';

if ((n==0) && (k==0)) cout<<"Списочная структура пуста."<<endl;

else{

//Формирование списочной структуры

if (n>k){

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

create_List2(&S,a[i],0);

int j=0;

for (i=n-k; i<n; i++){

create_List2(&S,a[i],a[n+j]);

j++;

}

}

else{ //Формирование списочной структуры при N<=K

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

create_List2(&S,a[i],a[n+i]);

if (n<k){

for (i=2*n; i<n+k; i++)

add_to_List2(&S,a[i]);

}

}

//Вывод списков на экран

cout<<"\nСписочная структура:"<<endl;

print_List2(S);

//Вывод списочной структуры в файл

print_List2_to_file(S);

}

//навигация по списочной структуре

char y,c;

bool end; //определяет возможность навигации

List2 *tmp,*t;

tmp=S;

n=2; //до навигации находимся во 2-м списке

y='y';

t=0;

while (y=='y'){

end=true;

cout<<"\nТекущий элемент:"<<endl;

cout<<tmp->inf;

cout<<"\nНажмите клавишу управления:"<<endl;

c=getchar();

while(c!='0'){

switch (c){

case '4':

{ //нажата клавиша влево

if (n==1) cout<<"Находимся в списке 1. Нажмите вправо(6)."<<endl;

else{

if (tmp->next!=0){

t=tmp->next;

if (t!=0){

cout<<"влево\n";

cout<<" < "<<t->inf<<endl;

tmp=t;

}

}

else cout<<"Достигнут конец списка 2. Слева пусто."<<endl;

}

break;

}

case '2':

{ //нажата клавиша вниз

if (n==1) {

cout<<"Находимся в списке 1. Внизу пусто."<<endl;

---

}

else{

if (tmp->nextL!=0){

t=tmp->nextL;

if (t!=0){

cout<<"вниз\n";

cout<<t->inf<<endl;

tmp=t;

n=1;//переход к списку 1

cout<<"Перешли в список 1. Нажмите вправо(6) или 0."<<endl;

}

}

else cout<<"Внизу пусто."<<endl;

}

break;

}

case '6':

{ //нажата клавиша вправо

if (n==2) cout<<"Находимся в списке 2. Нажмите влево(4), вниз(2) или 0."<<endl;

else{

if (tmp->next!=0){

t=tmp->next;

if (t!=0){

cout<<"вправо\n"<<endl;

cout<<" > "<<t->inf<<endl;

tmp=t;

}

}

else{

cout<<"Достигнут конец списка 1. Справа пусто."<<endl;

end=false;

}

}

break;

}

}

if (end==false) c='0';

else c=getchar();

}

y=getchar();

cout<<"\nПовторить навигацию? (y/n)"<<endl;

y=getchar();

if (y=='y') {

tmp=S;

n=2;

}

else break;

}

delete[] a;//освобождение памяти, занятой массивом a

system("pause");

return 0;

}

1. Определяем функции, необходимые для решения поставленной задачи формирования и вывода списочной структуры:

• функция create_List2 для добавления элементов в списочную структуру

Параметры функции

tmpS – указатель на списочную структуру

d1 – информационное поле элемента списка 1

d2 – информационное поле элемента списка 2

void create_List2(List2 **tmpS, int d1, int d2) {

List2 *tmp1, *tmp2;

tmp1 = new List2;

tmp2 = new List2;

tmp1->inf = d1;

tmp2->inf = d2;

tmp1->next=0;

tmp1->nextL=0;

if (*tmpS==0) { //если добавляем 1-й элемент в каждый из списков

tmp2->next=0;

tmp2->nextL=tmp1;

}

else{

tmp2->next=*tmpS;

tmp2->nextL=tmp1;

((tmp2->next)->nextL)->next=tmp1;

}

*tmpS=tmp2;

}

• функция add_to_List2 для формирования списка 2 списочной структуры при N<K

Параметры функции

tmpS – указатель на списочную структуру

d – информационное поле элемента списка 2

void add_to_List2(List2 **tmpS, int d) {

List2 *tmp = new List2;

tmp->inf = d;

tmp->next=*tmpS;

tmp->nextL=0;

*tmpS=tmp;

}

• функция print_List2 для вывода списочной структуры на экран

Параметры функции

tmpS – указатель на списочную структуру

void print_List2(List2 *tmpS) {

List2 *tmp;

tmp=tmpS;

cout<<"Список 2"<<endl;

while (tmp) {

cout <<tmp->inf<< " ";

tmp = tmp->next;

}

cout << endl;

tmp=tmpS;

cout<<"Список 1"<<endl;

while (tmp) {

if (tmp->nextL!=0)

cout << (tmp->nextL)->inf << " ";

tmp = tmp->next;

}

cout << endl;

}

• функция print_List2_to_file для вывода списочной структуры в файл

Параметры функции

tmpS – указатель на списочную структуру

void print_List2_to_file(List2 *tmpS){

List2 *tmp;

tmp=tmpS;

ofstream txtFile; //создание объекта для записи в файл

txtFile.open("fileout.txt",ios::out); // открытие файла в режиме записи данных,

---