Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Написать программу для получения из односвязного, двусвязного и двусвязного списка с головой циклического списка уникальных элементов.
Oписаны структуры данных, для каждой написан метод поиска уникальных элементов, но работает он не правильно. В этом главная проблема. Не знаю правильно ли я поняла и описала двусвязный и двусвязный список с головой
Еще вызывает затруднения создания самого списка уникальных элементов.
Код местами корявый и запутанный, а может и не местами
Приложение:
#pragma once
#include <iostream>
#include "stdlib.h"
using namespace std;
struct One_List {//структура данных
int Data; //информационное поле
One_List *Next; //адресное поле
};
int GetElement(One_List *Head, int pos, int Count)
{
One_List *temp = Head;
// Позиция от 1 до Count?
if (pos < 1 || pos > Count)
{
// Неверная позиция
cout << "Incorrect position !!!\n";
return 0;
}
int i = 1;
// Ищем нужный нам элемент
while (i < pos && temp != 0)
{
temp = temp->Next;
i++;
}
if (temp == 0)
return 0;
else
return temp->Data;
}
void Creation_List(int n, One_List** Head)
{
if (n > 0)
{
(*Head) = new One_List(); //выделяем память под новый элемент
cout << "Введите значение ";
cin >> (*Head)->Data; //вводим значение информационного поля
(*Head)->Next = NULL; //обнуление адресного поля
Creation_List(n - 1, &((*Head)->Next));
}
}
void Print_List(One_List* Head)
{
if (Head != NULL)
{
cout << Head->Data << "\t";
Print_List(Head->Next);
//переход к следующему элементу
}
else cout << "\n";
}
void Delete_List(One_List* Head)
{
if (Head != NULL) {
Delete_List(Head->Next);
delete Head;
}
}
One_List* Insert_Item_List(One_List* Head, int Number, int DataItem)
{
Number--;
One_List *NewItem = new One_List();
NewItem->Data = DataItem;
NewItem->Next = NULL;
if (Head == NULL) //список пуст
{
Head = NewItem; //создаем первый элемент списка
}
else //список не пуст
{
One_List *Current = Head;
for (int i = 1; i < Number && Current->Next != NULL; i++)
Current = Current->Next;
if (Number == 0)
{
//вставляем новый элемент на первое место
NewItem->Next = Head;
Head = NewItem;
}
else //вставляем новый элемент на непервое место
{
if (Current->Next != NULL)
NewItem->Next = Current->Next;
Current->Next = NewItem;
}
}
return Head;
}
void Delete_Item_List(One_List** Head, int Number) {
One_List *ptr;//вспомогательный указатель
One_List *Current = (*Head);
for (int i = 1; i < Number && Current != NULL; i++)
Current = Current->Next;
if (Current != NULL) //проверка на корректность
{
if (Current == (*Head)) //удаляем первый элемент
{
(*Head) = (*Head)->Next;
delete(Current);
Current = (*Head);
}
else if (Current->Next == NULL)
{
ptr = (*Head);
while (ptr->Next != Current)
ptr = ptr->Next;
ptr->Next = NULL;
delete(Current);
Current = ptr;
}
else //удаляем непервый элемент
{
ptr = (*Head);
while (ptr->Next != Current)
ptr = ptr->Next;
ptr->Next = Current->Next;
delete(Current);
Current = ptr;
}
}
}
void Find_Item_List(One_List* Head)
{
One_List *t, *l, *q, *p, *i;
bool flag = false;
p = Head;
i = Head;
l = Head;
while (p != NULL)
{
flag = false;
for (t = i = p->Next; i != NULL; )
{
if (p->Data == i->Data)
{
flag = true;
q = i->Next;
if (t == i)
t = p->Next = i->Next;
else
t->Next = i->Next;
delete i;
i = q;
continue;
}
t = i;
i = i->Next;
}
if (flag) {
l = p->Next;
delete p;
p = l;
}
else
p = p->Next;
}
}
struct Double_List //структура данных
{
int Data; //информационное поле
Double_List *Next; //адресное поле
Double_List *Previous; //адресное поле
};
int GetDoubleElement(Double_List *Head, int pos, int Count)
{
Double_List *temp = Head;
// Позиция от 1 до Count?
if (pos < 1 || pos > Count)
{
// Неверная позиция
cout << "Incorrect position !!!\n";
return 0;
}
int i = 1;
// Ищем нужный нам элемент
while (i < pos && temp != 0)
{
temp = temp->Next;
i++;
}
if (temp == 0)
return 0;
else
return temp->Data;
}
//создание двунаправленного списка (добавления в конец)
void Creation_Double_List(int n, Double_List** Head, Double_List* Previous)
{
(*Head) = new Double_List();
if (n > 0) {
//выделяем память под новый элемент
cout << "Введите значение ";
cin >> (*Head)->Data;
//вводим значение информационного поля
(*Head)->Previous = Previous;
(*Head)->Next = NULL;//обнуление адресного поля
Creation_Double_List(n - 1, &((*Head)->Next), (*Head));
}
else (*Head) = NULL;
}
//печать двунаправленного списка
void Print_Double_List(Double_List* Head)
{
if (Head != NULL) {
cout << Head->Data << "\t";
Print_Double_List(Head->Next);
//переход к следующему элементу
}
else cout << "\n";
}
//освобождение памяти, выделенной под двунаправленный список
void Delete_Double_List(Double_List* Head)
{
if (Head != NULL) {
Delete_Double_List(Head->Next);
delete Head;
}
}
Double_List* Insert_To_Double_List(Double_List* Head, int Number, int Data)
{
Number--;
Double_List *NewItem = new Double_List;
NewItem->Data = Data;
NewItem->Previous = NULL;
NewItem->Next = NULL;
if (Head == NULL) {//список пуст
Head = NewItem;
}
else {//список не пуст
Double_List *Current = Head;
for (int i = 1; i < Number && Current->Next != NULL; i++)
Current = Current->Next;
if (Number == 0) {
//вставляем новый элемент на первое место
NewItem->Next = Head;
Head->Previous = NewItem;
Head = NewItem;
}
else {//вставляем новый элемент на непервое место
if (Current->Next != NULL) {
Current->Next->Previous = NewItem;
NewItem->Next = Current->Next;
Current->Next = NewItem;
NewItem->Previous = Current;
Current = NewItem;
}
}
}
return Head;
}
void Find_Item_Double_List(Double_List* Head)
{
Double_List *t, *l, *q, *p, *i;
bool flag = false;
p = Head;
i = Head;
l = Head;
while (p != NULL)
{
flag = false;
for (t = i = p->Next; i != NULL; )
{
if (p->Data == i->Data)
{
flag = true;
q = i->Next;
if (t == i)
t = p->Next = i->Next;
else
t->Next = i->Next;
delete i;
i = q;
continue;
}
t = i;
i = i->Next;
}
if (flag) {
l = p->Next;
delete p;
p = l;
}
else p = p->Next;
}
//(*Head) = p;
}
struct Elem
{
int Data; // данные
Elem * Next, *Prev;
};
class List
{
// Голова, хвост
Elem * Head, *Tail;
// Количество элементов
int Count;
public:
// Конструктор
List();
// Конструктор копирования
List(const List&);
// Деструктор
~List();
// Получить количество
int GetCount();
// Получить элемент списка
int GetElem(int);
// Удалить весь список
void DelAll();
// Удаление элемента, если параметр не указывается,
// то функция его запрашивает
void Del(int pos = 0);
// Вставка элемента, если параметр не указывается,
// то функция его запрашивает
void Insert(int pos = 0);
// Добавление в конец списка
void AddTail(int n);
// Добавление в начало списка
void AddHead(int n);
// Печать списка
void Print();
// Печать определенного элемента
void Print(int pos);
// Поиск уникальных элементов
void Find_Unic_Item_List();
};
List::List()
{
// Изначально список пуст
Head = Tail = NULL;
Count = 0;
}
List::List(const List & L)
{
Head = Tail = NULL;
Count = 0;
// Голова списка, из которого копируем
Elem * temp = L.Head;
// Пока не конец списка
while (temp != 0)
{
// Передираем данные
AddTail(temp->Data);
temp = temp->Next;
}
}
List::~List()
{
// Удаляем все элементы
DelAll();
}
void List::AddHead(int n)
{
// новый элемент
Elem * temp = new Elem;
// Предыдущего нет
temp->Prev = 0;
// Заполняем данные
temp->Data = n;
// Следующий - бывшая голова
temp->Next = Head;
// Если элементы есть?
if (Head != 0)
Head->Prev = temp;
// Если элемент первый, то он одновременно и голова и хвост
if (Count == 0)
Head = Tail = temp;
else
// иначе новый элемент - головной
Head = temp;
Count++;
}
void List::AddTail(int n)
{
// Создаем новый элемент
Elem * temp = new Elem;
// Следующего нет
temp->Next = 0;
// Заполняем данные
temp->Data = n;
// Предыдущий - бывший хвост
temp->Prev = Tail;
// Если элементы есть?
if (Tail != 0)
Tail->Next = temp;
// Если элемент первый, то он одновременно и голова и хвост
if (Count == 0)
Head = Tail = temp;
else
// иначе новый элемент - хвостовой
Tail = temp;
Count++;
}
void List::Insert(int pos)
{
// если параметр отсутствует или равен 0, то запрашиваем его
if (pos == 0)
{
cout << "Input position: ";
cin >> pos;
}
// Позиция от 1 до Count?
if (pos < 1 || pos > Count + 1)
{
// Неверная позиция
cout << "Incorrect position !!!\n";
return;
}
// Если вставка в конец списка
if (pos == Count + 1)
{
// Вставляемые данные
int data;
cout << "Input new number: ";
cin >> data;
// Добавление в конец списка
AddTail(data);
return;
}
else if (pos == 1)
{
// Вставляемые данные
int data;
cout << "Input new number: ";
cin >> data;
// Добавление в начало списка
AddHead(data);
return;
}
// Счетчик
int i = 1;
// Отсчитываем от головы n - 1 элементов
Elem * Ins = Head;
while (i < pos)
{
// Доходим до элемента,
// перед которым вставляемся
Ins = Ins->Next;
i++;
}
// Доходим до элемента,
// который предшествует
Elem * PrevIns = Ins->Prev;
// Создаем новый элемент
Elem * temp = new Elem;
// Вводим данные
cout << "Input new number: ";
cin >> temp->Data;
// настройка связей
if (PrevIns != 0 && Count != 1)
PrevIns->Next = temp;
temp->Next = Ins;
temp->Prev = PrevIns;
Ins->Prev = temp;
Count++;
}
void List::Del(int pos)
{
// если параметр отсутствует или равен 0, то запрашиваем его
if (pos == 0)
{
cout << "Input position: ";
cin >> pos;
}
// Позиция от 1 до Count?
if (pos < 1 || pos > Count)
{
// Неверная позиция
cout << "Incorrect position !!!\n";
return;
}
// Счетчик
int i = 1;
Elem * Del = Head;
while (i < pos)
{
// Доходим до элемента,
// который удаляется
Del = Del->Next;
i++;
}
// Доходим до элемента,
// который предшествует удаляемому
Elem * PrevDel = Del->Prev;
// Доходим до элемента, который следует за удаляемым
Elem * AfterDel = Del->Next;
// Если удаляем не голову
if (PrevDel != 0 && Count != 1)
PrevDel->Next = AfterDel;
// Если удаляем не хвост
if (AfterDel != 0 && Count != 1)
AfterDel->Prev = PrevDel;
// Удаляются крайние?
if (pos == 1)
Head = AfterDel;
if (pos == Count)
Tail = PrevDel;
// Удаление элемента
delete Del;
Count--;
}
void List::Print(int pos)
{
// Позиция от 1 до Count?
if (pos < 1 || pos > Count)
{
// Неверная позиция
cout << "Incorrect position !!!\n";
return;
}
Elem * temp;
// Определяем с какой стороны
// быстрее двигаться
if (pos <= Count / 2)
{
// Отсчет с головы
temp = Head;
int i = 1;
while (i < pos)
{
// Двигаемся до нужного элемента
temp = temp->Next;
i++;
}
}
else
{
// Отсчет с хвоста
temp = Tail;
int i = 1;
while (i <= Count - pos)
{
// Двигаемся до нужного элемента
temp = temp->Prev;
i++;
}
}
// Вывод элемента
cout << pos << " element: ";
cout << temp->Data << endl;
}
void List::Print()
{
// Если в списке присутствуют элементы, то пробегаем по нему
// и печатаем элементы, начиная с головного
if (Count != 0)
{
Elem * temp = Head;
cout << "( ";
while (temp->Next != 0)
{
cout << temp->Data << ", ";
temp = temp->Next;
}
cout << temp->Data << " )\n";
}
}
void List::DelAll()
{
// Пока остаются элементы, удаляем по одному с головы
while (Count != 0)
Del(1);
}
int List::GetCount()
{
return Count;
}
int List::GetElem(int pos)
{
Elem *temp = Head;
// Позиция от 1 до Count?
if (pos < 1 || pos > Count)
{
// Неверная позиция
cout << "Incorrect position !!!\n";
return 0;
}
int i = 1;
// Ищем нужный нам элемент
while (i < pos && temp != 0)
{
temp = temp->Next;
i++;
}
if (temp == 0)
return 0;
else
return temp->Data;
}
/*
// сложение двух списков
List List::operator + (const List& L)
{
// Заносим во временный список элементы первого списка
List Result(*this);
// List Result = *this;
Elem * temp = L.Head;
// Добавляем во временный список элементы второго списка
while (temp != 0)
{
Result.AddTail(temp->data);
temp = temp->next;
}
return Result;
}*/
void List::Find_Unic_Item_List()
{
Elem *t, *l, *q, *p, *i;
bool flag = false;
p = Head;
i = Head;
l = Head;
while (p != NULL)
{
flag = false;
for (t = i = p->Next; i != NULL; )
{
if (p->Data == i->Data)
{
flag = true;
q = i->Next;
if (t == i)
t = p->Next = i->Next;
else
t->Next = i->Next;
delete i;
i = q;
continue;
}
t = i;
i = i->Next;
}
if (flag) {
l = p->Next;
delete p;
p = l;
}
else p = p->Next;
}
Head = p;
}
struct Circle_Double_List //структура данных
{
int Data; //информационное поле
Circle_Double_List *Next; //адресное поле
Circle_Double_List *Prior; //адресное поле
};
//создание циклического двунаправленного списка
Circle_Double_List* Make_Circle_Double_List(int n, Circle_Double_List** Head, Circle_Double_List* Loop) {
Circle_Double_List* ptr;//вспомогательный указатель
if (n > 0) {
(*Head) = new Circle_Double_List();
//выделяем память под новый элемент
if (Loop == NULL) Loop = (*Head);
cout << "Введите значение ";
cin >> (*Head)->Data;
//вводим значение информационного поля
(*Head)->Next = NULL;//обнуление адресного поля
ptr = Make_Circle_Double_List(n - 1, &((*Head)->Next), Loop);
if ((*Head)->Next != NULL)
(*Head)->Next->Prior = (*Head);
if ((*Head)->Prior == NULL)
(*Head)->Prior = ptr;
if (ptr == NULL)
return *Head;
else return ptr;
}
else {
(*Head) = Loop;
return NULL;
}
}
//печать циклического двунаправленного списка
void Print_Circle_Double_List(Circle_Double_List* Head)
{
Circle_Double_List* ptr = Head;
//вспомогательный указатель
do {
cout << ptr->Data << "\t";
ptr = ptr->Next;
} while (ptr != Head);
cout << "\n";
}
/*вставка элемента после заданного номера в циклический двунаправленный список*/
void Insert_List_Circle_Double_List(Circle_Double_List** Head, int Number, int DataItem) {
Circle_Double_List *Current = (*Head);
//встали на первый элемент
Circle_Double_List *NewItem = new(Circle_Double_List);
//создали новый элемент
NewItem->Data = DataItem;
if ((*Head) == NULL) {//список пуст
NewItem->Next = NewItem;
NewItem->Prior = NewItem;
(*Head) = NewItem;
}
else {//список не пуст
for (int i = 1; i < Number; i++)
Current = Current->Next;
NewItem->Next = Current->Next;
Current->Next = NewItem;
NewItem->Prior = Current;
NewItem->Next->Prior = NewItem;
}
}
/*удаление элемента с заданным номером из циклического двунаправленного списка*/
Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head, int Number) {
if (Head != NULL) {
Circle_Double_List *Current = Head;
if (Head->Next != Head) {
for (int i = 1; i < Number; i++)
Current = Current->Next;
Circle_Double_List *ptr = Current->Next;
Current->Prior->Next = Current->Next;
Current->Next->Prior = Current->Prior;
if (Head = Current) //удаляем первый
Head = Current->Next;
delete(Current);
}
else {
Head = NULL;
delete(Current);
}
}
return Head;
}
//поиск элемента в циклическом двунаправленном списке
bool Find_Item_Circle_Double_List(Circle_Double_List* Head, int DataItem) {
Circle_Double_List *ptr = Head;
//вспомогательный указатель
do {
if (DataItem == ptr->Data)
return true;
else ptr = ptr->Next;
} while (ptr != Head);
return false;
}
//проверка пустоты циклического двунаправленного списка
bool Empty_Circle_Double_List(Circle_Double_List* Head) {
return (Head != NULL ? false : true);
}
//удаление циклического двунаправленного списка
void Delete_Circle_Double_List(Circle_Double_List* Head) {
if (Head != NULL) {
Head = Delete_Item_Circle_Double_List(Head, 1);
Delete_Circle_Double_List(Head);
}
}
void Creation_Circle_List(One_List **Head, Double_List **Head2, List Head3, Circle_Double_List** Head4, int Count)
{
int p = 0;
Circle_Double_List *ptr = (*Head4);
for (int i = 0; i < Count; i++) {
for (int j = 0; j < Count; j++) {
for (int k = 0; k < Count; k++)
Insert_List_Circle_Double_List(&ptr, p++, GetElement(*Head, k, Count));
Insert_List_Circle_Double_List(&ptr, p++, GetDoubleElement(*Head2, j, Count));
}
Insert_List_Circle_Double_List(&ptr, p++, Head3.GetElem(i));
}
}