VPF::[C++] Сравнить двусвязные списки

AleksDDem

Дата 13.2.2007, 19:04 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 51
Регистрация: 12.2.2007

Репутация: нет
Всего: нет

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

Заранее очень благодарен! smile

Rickert

Дата 13.2.2007, 20:22 (ссылка)

(нет голосов)

Загрузка ...

Ситхи не пройдут!

Профиль
Группа: Комодератор
Сообщений: 3356
Регистрация: 11.7.2006
Где: Лакрима

Репутация: нет
Всего: 52

Что значит сравнить? Являются ли они одним и тем же? Или какие-то переменные сравнить?

--------------------

Ни что не внушает сна крепче, чем день приисполненный трудов!

AleksDDem

Дата 13.2.2007, 20:39 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 51
Регистрация: 12.2.2007

Репутация: нет
Всего: нет

Нужно сравнить елементы списка. Списки должны иметь одинаковый размер и одинаковые елементы.....

Oleg_Ci

Дата 14.2.2007, 18:12 (ссылка)

(нет голосов)

Загрузка ...

Friend

Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30

Замутил такую-вот прожку smile

Код


#include <clocale>
#include <iostream>
using namespace std;

template <typename type>
class CList{
public:
    struct Node;
    Node *m_Begin, // начало списка
        *m_End; // конец списка
    size_t m_nSize; //  количество элементов в списке

    CList(): m_Begin(NULL), m_End(NULL), m_nSize(0) {};
    ~CList(); // деструктор
    void Push_back( type Val ); // вставка элемента в конец списка
    template <typename Ty> bool operator==( const CList<Ty> & List ) const;

private:
    struct Node{
        Node *Next, *Prev; // указатель на пердыдущий и следующий элементы
        type Value; // данные
        explicit Node( type Val=0 ): Value(Val), Next(NULL), Prev(NULL) {};
    };
};

/////////////////////////////////////////////
////////////// MAIN ////////////////////
int main(int argc, char* argv[])
{
    setlocale(LC_ALL, "Russian"); // для русского текста
    CList<int> list1; // список int'ов
    CList<float> list2; // список float'ов
    // добавляем элемены в списки
    list1.Push_back(4);
    list1.Push_back(5);
    list2.Push_back(4.);
    list2.Push_back(5.);
    //list2.Push_back(7.);

    if( list1 == list2 ) // сравнение
        cout << "Списки одинаковы !\n";
    else cout << "Списки неодинаковы !\n";

    cin.get(); // пауза
    return 0;
}
/////////////// End main //////////////////
////////////////////////////////////////////////

template <typename type> CList<type>::~CList(){
    Node *nod, *pt;
    for( pt = m_Begin; pt; pt = nod ){
        nod = pt->Next;
        delete pt;
    }
}
///////////////////////////////////////////////////////
template <typename type> void CList<type>::Push_back( type Val ){
    Node *Nod = new Node( Val );
    m_nSize++;
    if( !m_Begin )
        m_Begin = m_End = Nod;
    else{
        Nod->Prev = m_End;
        m_End = m_End->Next = Nod;
    }
}
//////////////////////////////////////////////////////
template <typename type> template <typename Ty>
bool CList<type>::operator ==( const CList<Ty> & List )const{
    if( m_nSize != List.m_nSize ) // сравнение размеров
        return false;
    else{
        const CList<type>::Node *pt1;
        const CList<Ty>::Node *pt2;
        // сравнение элементов
        for( pt1 = m_Begin, pt2 = List.m_Begin;
            pt1 && pt1->Value == pt2->Value;
            pt1 = pt1->Next, pt2 = pt2->Next );

        if( !pt1 ) return true;
        else return false;
    }
}

zkv

Дата 14.2.2007, 18:20 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Цитата(Oleg_Ci @ 14.2.2007, 18:12

)

CList(): m_Begin(NULL), m_End(NULL), m_nSize(0) {};

Цитата(Oleg_Ci @ 14.2.2007, 18:12

)

explicit Node( type Val=0 ): Value(Val), Next(NULL), Prev(NULL) {};

Oleg_Ci, тут точка с запятой в конце не нужна, она только с толку сбивает (мелочь, но смотрится не профессионально как то smile

)

Oleg_Ci

Дата 14.2.2007, 20:13 (ссылка)

(нет голосов)

Загрузка ...

Friend

Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30

Проверил...
правду говоришь smile

AleksDDem

Дата 16.2.2007, 16:35 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 51
Регистрация: 12.2.2007

Репутация: нет
Всего: нет

Спасибо великое! Не проверял работает ли программа, но видно что писал профи так что уверен что работает. Только вот одно меня смущает программа очень круто написана.Мы здесь много чего не учили...например классы. Можно ее как то упростить?

Проге вручную задаються списки. Потом проверяються их размеры - если они не совпадают то сразу пишеться что списки не равны, а если совпадают то потом проверяеться есть ли каждый елемент первого списка в другом. - вот такой мне алгоритм обьяснил препод.вроде просто smile

Это сообщение отредактировал(а) AleksDDem - 16.2.2007, 16:46

cardinal

Дата 16.2.2007, 16:47 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 15
Всего: 99

Выкладывай код, что есть, чтобы понятно было, что вы там уже прошли, а что нет...

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

V.A.KeRneL

Дата 16.2.2007, 19:46 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14

Да, блин, понятно, что он просит на чистых Сях написать... Просто, как и многие, пишут C++ попривычке, потому что сейчас это самый популярный уже ЯП. (Типа, «слышу звон, но не знаю, где он».) Может даже и не знают некоторые, что C без плюсов бывает... smile

З.Ы. Будет время, напишу на Сях. Или кто другой сделает... Сдесь добрых людей много! smile

Это сообщение отредактировал(а) V.A.KeRneL - 16.2.2007, 19:49

--------------------

«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")

Oleg_Ci

Дата 19.2.2007, 15:59 (ссылка)

(нет голосов)

Загрузка ...

Friend

Профиль
Группа: Участник
Сообщений: 485
Регистрация: 28.5.2006
Где: Новосиб.обл.

Репутация: 25
Всего: 30

Ещё замутил прожку.
Списки считаются одинаковыми если они имеют одинаковые элементы и они расположены в одинаковой последовательности в обоих списках.

Код


#include <stdio.h>
#include <stdlib.h>

typedef struct NODE{ // узел списка
    int value; // данные
    struct NODE *next, *prew; // указатель на пердыдущий и следующий элементы
}Node;

Node *add( Node *list, int val ); // добавление элемента в список
int compare( const Node *list1, const Node *list2 ); // сравнение двух списков
void del( Node *list ); // удаление списка
Node *getlist( Node *list ); // считывание данных с консоли
void outlist( Node *list ); // вывод данных списка на консоль

////////////// MAIN ////////////////////
int main(int argc, char* argv[])
{
    Node *list1, *list2; // списки
    list1 = list2 = NULL;
    
    ////// заполнение списков значениями //////

    puts("Enter number list1:");
    list1 = getlist( list1 );
    puts("\n\n\nEnter number list2:");
    list2 = getlist( list2 );

    ////// сравнивание ////////////////////
    
    if( compare( list1, list2 ))
        puts("the lists are identical (Ok)"); // списки одинаковы
    else
        puts("the lists are not identical (Error)"); // списки не одинаковы

    ///// конец программы //////////////
    del(list1); // удаление списка
    del(list2);
    getchar(); // пауза
    return 0;
}
/////////////// End main //////////////////
////////////////////////////////////////////////

Node *add( Node *list, int val ){
    Node *n = (Node*)malloc(sizeof(Node));
    n->next = NULL;
    n->value = val;
    if( !list ){
        n->prew = NULL;
        return n;
    }
    else{
        Node *x;
        for( x=list; x->next; x=x->next ); // в конец списка
        x->next = n;
        n->prew = x;
        return list;
    }
}
/////////////////////////////////////////////
int compare( const Node *list1, const Node *list2 ){
    for(; list1 && list2 &&   list1->value == list2->value;
        list1=list1->next,    list2=list2->next );
    return !( list1 || list2 );
}
///////////////////////////////////////////
void del( Node *list ){
    Node *n;
    for( n=list; n; n=list ){
        list = list->next;
        free(n);
    }
}
/////////////////////////////////////////
Node *getlist( Node *list ){
    int num;
    while( scanf("%d", &num)>0 )
        list = add( list, num ); // добавление числа в список
    fflush(stdin);
    return list;
}
/////////////////////////////////////////
void outlist( Node *list ){
    for(; list; list=list->next )
        printf("%d\n", list->value );
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »