В двусвязном списке продублировать те элементы, которые меньше следующ

gvenog · 13.12.2010

В двусвязном списке продублировать те элементы, которые меньше следующего, но больше больше предыдущего.

C++:

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;

struct LIST {
int info;
LIST *next;
LIST *prev;


};

LIST *head;
int n1, n2;

void Initial()
{
head = new LIST;
head->next=head;
head->prev=head;


}

int Empty()
{
if (head->next==head && head->prev==head)
return 1;
else
return 0;


}

LIST *SearchOnward(int num)
{
LIST *tmp=head->next;
while(tmp!=head && tmp->info!=num)
{
tmp=tmp->next;
n1+=1;
}
if (tmp!=head)
return tmp;
else
return NULL;


}

LIST *SearchBack(int num)
{
LIST *tmp=head->prev;
while(tmp!=head && tmp->info!=num)
{
tmp=tmp->prev;
n2+=1;
}
if (tmp!=head)
return tmp;
else
return NULL;


}

int Del(int num)
{
LIST *current=SearchOnward(num);
if (current!=NULL)
{
current->prev->next=current->next;
current->next->prev=current->prev;
delete current;
return 1;
}
return 0;


} 

int AddAfter(int num, int point)
{
if (Empty()==1)
{
LIST *tmp=new LIST;
tmp->next=head;
tmp->prev=head;
tmp->info=num;
head->next=tmp;
head->prev=tmp;
return 1;
}
LIST *current=SearchOnward(point);
if (current!=NULL)
{
LIST *tmp=new LIST;
tmp->next=current->next;
tmp->prev=current;
tmp->info=num;
current->next->prev=tmp;
current->next=tmp;
return 1;
}
return 0;


}

int AddBefore(int num, int point)
{
LIST *current=SearchBack(point);
if(current!=NULL)
{
LIST *tmp=new LIST;
tmp->info=num;
tmp->next=current;
tmp->prev=current->prev;
current->prev->next=tmp;
current->prev=tmp;
return 1;
}
return 0;


}

void ShowOnward()
{
LIST *tmp=head->next;
cout << endl << "В прямом направлении:" << endl;
while(tmp!=head)
{
cout << tmp->info << " ";
tmp=tmp->next;
}
cout << endl;


}

void ShowBack()
{
LIST *tmp=head->prev;
cout << endl << "В обратном направлении:" << endl;
while(tmp!=head)
{
cout << tmp->info << " ";
tmp=tmp->prev;
}
cout << endl;


}

int Double()
{
}

int main()
{
setlocale(LC_ALL,"Russian");
Initial();
int num, tmp;
char otv, otv2;
do
{
cout << "1. Добавление" << endl
<< "2. Удаление" << endl
<< "3. Вывод"<< endl
<< "4. Поиск" << endl
<< "5. Дублирование" << endl
<< "0. Выход" << endl
<< " = ";
cin >> otv;
switch(otv)
{
case '1':
cout << endl << "Введите элемент = ";
cin >> num;
if (Empty()==1)
{
AddAfter(num,0);
cout << endl << "Элемент добавлен" << endl;
}
else
{
cout << endl << "1. Добавить перед" 
<< endl << "2. Добавить после"
<< endl << " = ";
cin >> otv2;
switch(otv2)
{
case '1':
cout << endl << "Перед каким элементом добавить = ";
cin >> tmp;
if (AddBefore(num,tmp)==1)
cout << endl << "Элемент добавлен" << endl;
else
cout << endl << "Такого элемента не существует" << endl;
break;


case '2':
cout << endl << "После какого элемента добавить = ";
cin >> tmp;
if (AddAfter(num,tmp)==1)
cout << endl << "Элемент добавлен" << endl;
else
cout << endl << "Такого элемента не существует" << endl;
break;


default:
cout << endl << "Ошибка" << endl;
break;


}

}
break;

case '2':
if(Empty()==1)
cout << endl << "Список пуст" << endl;
else
{
cout << endl << "Удаляемый элемент = ";
cin >> num;
if(Del(num)==1)
cout << endl << "Элемент удален" << endl;
else
cout << endl << "Такого элемента не существует" << endl;
}
break;


case '3':
if(Empty()==1)
cout << endl << "Список пуст" << endl;
else
{


cout << endl << "1. Обход в прямом напрвлении" << endl
<< "2. Обход в обратном направлении" << endl
<< " = ";
cin >> otv2;
switch(otv2)
{
case '1':
ShowOnward();
break;


case '2':
ShowBack();
break;


default:
cout << endl << "Ошибка" << endl;
break;


} 

}
break;

case '4':
if(Empty()==1)
cout << endl << "Список пуст" << endl;
else
{
cout << endl << "Элемент для поиска = ";
cin >> num;
n1=0;
n2=0;
if(SearchOnward(num)!=NULL && SearchBack(num)!=NULL)
{
cout << endl << "Элемент найден" << endl;
cout << endl << "В прямом направлении шаг = " << n1 << endl;
cout << endl << "В обратном направлении шаг = " << n2 << endl;
}
else
cout << endl << "Такого элемента не существует" << endl;


}
break;

case '5':
if(Empty()==1)
cout << endl << "Список пуст" << endl;
else
{
//Double();
//ShowOnward();
}
break;

case '0':
break;


default:
cout << endl << "Ошибка" << endl;
break;


}

}while(otv!='0');
cin.get();

}

В функции Double() хотела сделать это самое дублирование, но столкнулась с проблемой сравнения элементов и копирования со сдвигом элементов в списке. Можете объяснить как это сделать?

lazybiz · 13.12.2010

Подожди, подожди.. Что означает слово "продублировать" ??

gvenog · 13.12.2010

lazybiz сказал(а):
Подожди, подожди.. Что означает слово "продублировать" ??

Это значит что, если элемент больше предыдущего, но меньше следующего, то нужно его скопировать и вставить за ним, ну типа:

был неупорядоченный список:
1, 4, 2, 6, 8, 7, 10

Элемент 6 больше 2 и меньше 8, значит нужно его скопировать:
1, 4, 2, 6, 6, 8, 7, 10

Вот так.

lazybiz · 14.12.2010

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

C++:

#include <iostream.h>
#include <conio.h>

typedef struct _list {
int		v;
_list *	prev;
_list *	next;
} list;

list *	top = NULL;

void list_add( int v )
{
if ( !top ) {
top = new list;
top->prev = NULL;
top->next = NULL;
top->v = v;
} else {
list *	last = top;
while ( last->next ) last = last->next;
last->next = new list;
last->next->next = NULL;
last->next->prev = last;
last->next->v = v;
}
}

void list_double( void )
{
list *	p = top;
while ( p ) {
if ( p->prev && p->next ) {
if ( p->prev->v < p->v && p->v < p->next->v ) {
//
// insert between p->prev and p
//
list *d = new list;
d->prev = p->prev;
d->next = p;
d->v = p->v;

p->prev->next = d;
p->prev = d;
}
}
p = p->next;
}
}

void list_print( void )
{
list *	p = top;
while ( p ) {
cout << p->v << endl;
p = p->next;
}
}

int main()
{
list_add( 1 );
list_add( 4 );
list_add( 2 );
list_add( 6 );
list_add( 8 );
list_add( 7 );
list_add( 10 );

list_double();

list_print();
return 0;
}

gvenog · 14.12.2010

lazybiz сказал(а):

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

C++:

#include <iostream.h>
#include <conio.h>

typedef struct _list {
int		v;
_list *	prev;
_list *	next;
} list;

list *	top = NULL;

void list_add( int v )
{
if ( !top ) {
top = new list;
top->prev = NULL;
top->next = NULL;
top->v = v;
} else {
list *	last = top;
while ( last->next ) last = last->next;
last->next = new list;
last->next->next = NULL;
last->next->prev = last;
last->next->v = v;
}
}

void list_double( void )
{
list *	p = top;
while ( p ) {
if ( p->prev && p->next ) {
if ( p->prev->v < p->v && p->v < p->next->v ) {
//
// insert between p->prev and p
//
list *d = new list;
d->prev = p->prev;
d->next = p;
d->v = p->v;

p->prev->next = d;
p->prev = d;
}
}
p = p->next;
}
}

void list_print( void )
{
list *	p = top;
while ( p ) {
cout << p->v << endl;
p = p->next;
}
}

int main()
{
list_add( 1 );
list_add( 4 );
list_add( 2 );
list_add( 6 );
list_add( 8 );
list_add( 7 );
list_add( 10 );

list_double();

list_print();
return 0;
}

Большое вам спасибо, теперь я поняла!

lazybiz · 14.12.2010

Спасибо не прокатит, а вот плюсик - вполне!

В двусвязном списке продублировать те элементы, которые меньше следующ

gvenog

lazybiz

gvenog

lazybiz

gvenog

lazybiz