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

//при этом информация в существующем файле уничтожается (режим по умолчанию для потоков ofstream)

txtFile<<"Списочная структура:"; //запись строки в файл fileout.txt

txtFile << "\nСписок 2\n"; //запись значения переменной ch в файл fileout.txt

while (tmp) {

txtFile << tmp->inf;

txtFile << " ";

tmp = tmp->next;

}

tmp=tmpS;

txtFile << "\nСписок 1\n";

while (tmp) {

if (tmp->nextL!=0){

txtFile << (tmp->nextL)->inf;

txtFile << " ";

}

tmp = tmp->next;

}

txtFile.close(); // закрытие файла fileout.txt

}

Результаты работы программы

а) Количество элементов в каждом из двух линейных списков списочной структуры одинаково () (рис. 1-2):

Рис. 1. Вид консоли после выполнения программы при

Рис. 2. Списочная структура при

б) Количество элементов в первом списке больше, чем во втором списке () (рис. 3-4):

Рис. 3. Вид консоли после выполнения программы при ,

Рис. 4. Списочная структура при ,

(добавлено три нуля во второй список)

в) Количество элементов во втором списке больше, чем в первом списке () (рис. 5-6):

Рис. 5. Вид консоли после выполнения программы при ,

Рис. 6. Списочная структура при ,

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

а) Последовательная навигация по всем элементам структуры (рис. 7):

Рис. 7. Последовательная навигация по всем элементам структуры

---

б) Повторная навигация с указанием неверных направлений и завершение навигации путем введения символа «0» (рис. 8):

Рис. 8. Повторная навигация

Инструкция пользователя

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

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

Если ввести два нуля, то программа выдаст сообщение «Списочная структура пуста».

После завершения ввода последовательности целых чисел программа выполняет формирование списочной структуры и её вывод на экран и текстовый файл fileout.txt, расположенный в папке проекта (…/List/List/ fileout.txt).

Вывод построенной списочной структуры на экран осуществляется в следующем виде:

а) при одинаковом количестве элементов в каждом из линейных списков и в случае, если во втором списке больше элементов, чем в первом

Списочная структура:

Список 2

Список 1

б) в случае, если в первом списке больше элементов, чем во втором

Списочная структура:

Список 2

Список 1

(количество нулей во втором списке определяется разницей между количеством элементов в списках)

После вывода списочной структуры осуществляем навигацию по ней с помощью клавиш (влево – 4, вниз – 2, вправо – 6, завершение – 0).

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

Выводы

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

---

Приложение

Листинг (файл List.cpp)

// List.cpp: определяет точку входа для консольного приложения.

//

#include "stdafx.h"

#include <iostream>

#include <fstream>

#include <fstream>

using namespace std;

//Списочная структура

struct List2 {

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

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

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

};

//Объявление функций

void create_List2(List2**,int,int); //начальное формирование списка

void add_to_List2(List2**,int);

void print_List2(List2*);

void print_List2_to_file(List2*);

void navigate_element(int,List2*);

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

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

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

cout<<"Курсовая работа по информатике."<<endl;

cout<<"Выполнил студент группы АП-84"<<endl;

cout<<"Брумм Евгений"<<endl;

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

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

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

int n=0,k=0;

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;

}

//начальное формирование списка

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;

}

//формирование списка 2 при N<K

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

List2 *tmp = new List2;

tmp->inf = d;

tmp->next=*tmpS;

tmp->nextL=0;

*tmpS=tmp;

}

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

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;

}

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

void print_List2_to_file(List2 *tmpS){

List2 *tmp;

tmp=tmpS;

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

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

//при этом информация в существующем файле уничтожается (режим по умолчанию для потоков ofstream)

txtFile<<"Списочная структура:"; //запись строки в файл fileout.txt

txtFile << "\nСписок 2\n"; //запись значения переменной ch в файл fileout.txt

while (tmp) {

txtFile << tmp->inf;

txtFile << " ";

tmp = tmp->next;

}

tmp=tmpS;

txtFile << "\nСписок 1\n";

while (tmp) {

if (tmp->nextL!=0){

txtFile << (tmp->nextL)->inf;

txtFile << " ";

}

tmp = tmp->next;

}

txtFile.close(); // закрытие файла fileout.txt

}

Приложение

Листинг (файл List.cpp)

// List.cpp: определяет точку входа для консольного приложения.

---

//

#include "stdafx.h"

#include <iostream>

#include <fstream>

#include <fstream>

using namespace std;

//Списочная структура

struct List2 {

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

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

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

};

//Объявление функций

void create_List2(List2**,int,int); //начальное формирование списка

void add_to_List2(List2**,int);

void print_List2(List2*);

void print_List2_to_file(List2*);

void navigate_element(int,List2*);

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

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

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

cout<<"Курсовая работа по информатике."<<endl;

cout<<"Выполнил студент группы АП-84"<<endl;

cout<<"Брумм Евгений"<<endl;

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

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

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

int n=0,k=0;

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;

---