Содержание:

Задание

Написать программу, строящую следующую списочную структуру. Каждый элемент списка состоит из трех полей: первое поле – для связи элементов в одном списке, второе – информационное (заполняется вводимой последовательностью целых чисел , в которой 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); // открытие файла в режиме записи данных,

//при этом информация в существующем файле уничтожается (режим по умолчанию для потоков 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;

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;

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

}