01.06.2011, 02:00
общий
это ответ
Здравствуйте, Посетитель - 351942!
Вот код, проверяла, правда, под Visual Studio, ничего другого нет под рукой, но, думаю, и для Вас подойдёт.
Всё должно быть более-менее ясно, если что непонятно, спрашивайте.
Удачи!
Приложение:
#include<conio.h>
#include <iostream>
using namespace std;
struct Item {
int data; /* данные */
Item *next; /* указатель на следующий элемент */
};
//функции списка
bool Add (Item* &sp, int rel) //добавление в сортированный список
{
Item* tmp = sp;
if (tmp!=NULL) { //если список не пуст
while (tmp->next!=NULL && tmp->next->data<rel) tmp = tmp->next; //ищем место по порядку
if (tmp->next!=NULL && tmp->next->data == rel) return false; //если повторный - не добавляем
if (tmp->data==rel) return false;
if (tmp == sp && tmp->data>rel) { //если меньше первого, вставляем в начало
tmp = new Item;
tmp->data = rel;
tmp->next = sp;
sp = tmp;
return true;
}
tmp->next = new Item;
tmp = tmp->next;
} else { //если список новый
tmp = new Item;
sp = tmp;
}
tmp->next = NULL;
tmp->data = rel;
return true;
}
int Find (Item* sp, int f) //поиск элемента с данными f
{
Item* b = sp;
int i = 0;
while (b!=NULL && b->data<f) { b = b->next; i++; }
if (b->data==f) return i;
else return -1;
}
void Divide (Item* f, Item* &f1, Item* &f2, int el) //разделение f на f1 и f2 по el
{
f1 = NULL; f2 = NULL;
f1 = f;
Item* b = f;
while (b!=NULL && b->next!=NULL && b->next->data<el) b = b->next;
f2 = b->next;
b->next = NULL;
}
void Concat (Item* f, Item* g, Item* &result) //конкатенация
{
result = NULL;
Item* fb = f, *gb = g;
while (fb!=NULL) {
Add (result, fb->data);
fb = fb->next;
}
while (gb!=NULL) {
Add (result, gb->data);
gb = gb->next;
}
/*
если f гарантированно < g, то можно сделать так:
result = f;
fb = f;
while (fb!=NULL && fb->next!=NULL) fb = fb->next;
fb->next = g;
*/
}
void Print (Item* sp) //вывод списка на экран
{
Item* tmp = sp;
while (tmp!=NULL) {
cout << tmp->data << "; ";
tmp = tmp->next;
}
}
void Clear (Item* &sp) //очистка памяти из-под списка
{
Item* tmp = sp, *d;
while (tmp!=NULL) {
d = tmp; //сохраняем ссылку
tmp = tmp->next; //переходим на следующий
delete d; //удаляем элемент
d = NULL;
}
}
int main(void)
{
Item *list1 = NULL, *list2 = NULL, *list3 = NULL;
int n, d;
cout << "Vvedite dlinu spiska 1 ";
cin >> n;
cout << "\nVvedite chisla\n";
for (int i=0; i<n; i++) {
cin >> d;
Add (list1, d);
}
cout << "\nVvedite dlinu spiska 2 ";
cin >> n;
cout << "\nVvedite chisla\n";
for (int i=0; i<n; i++) {
cin >> d;
Add (list2, d);
}
cout << "\nSpisok 1: ";
Print (list1);
cout << "\nSpisok 2: ";
Print (list2);
Concat (list1, list2, list3);
cout << "\nConcat: ";
Print (list3);
cout << "\nInput element: ";
cin >> d;
Divide (list3, list2, list1, d);
cout << "\nSpisok 1: ";
Print (list1);
cout << "\nSpisok 2: ";
Print (list2);
Clear (list1); //очистка памяти
Clear (list2);
_getch();
return 0;
}