VPF::[C++]Односвязные списки - Форум программистов

AleksDDem

Дата 16.3.2007, 19:02 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

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

Xenon

Дата 16.3.2007, 20:40 (ссылка)

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

Загрузка ...

Эксперт

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

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

Код


#include <iostream>

template <class TYPE>
class key_list
{
    private:
    struct element
    {
    public:
        TYPE data; //Хранимые данные любого типа
    private:
        template <class TYPE> friend class key_list;
        element* next;
    };
    element* m_begin;//Первый элемент списка
    element* m_end;//Последний элемент списка
    int links_count; //Количество элементов в списке
public:
    void display_all() const; //Показать все элементы списка
    void add(TYPE data); //Добавить новый элемент
    const int size() const; //Размер массива
    const element* cursor (int pos)const; //Итератор
    key_list():m_begin(NULL),m_end(NULL),links_count(0){}
    explicit key_list(const key_list<TYPE>& list);
    //Деструктор
    ~key_list();
};
//////////////////////////////////////
//Показать все элементы
template <class TYPE>
void key_list<TYPE>::display_all() const
{
    if (links_count==0)
    {
        std::cout << "Nothing to display\n";
        return;
    }
    element* current=m_begin; //Создаем указатель курсор и ставим его на начало списка
    for (int i=0;i<links_count;++i)
    {
        std::cout << i << ") " << current->data << std::endl;
        current=current->next; //Передвигаемся вперед по списку
    }
}
//////////////////////////////////////
///Добавление нового элемента
template <class TYPE>
void key_list<TYPE>::add(TYPE data)
{
    element* link=new element; //Создаем в куче новый элемен списка
    link->data=data;//Присваем переменной, содержащей данные те данные, что получили в аргументе функции
    if (m_begin==NULL) //Если мы добавляем элемент в пусток список
    {
        m_begin=link; //То первым элементом списком будет та ссылка, что мы добавляем
        m_end=link;// Она же и будет концом
        m_begin->next=link;
    }
    else //Если же в списке есть какие-то элементы
    {
        m_end->next=link; //Указываем у последнего элемента то, что после него теперь не пустота, а новый элемен
        m_end=link; //Теперь наш новый элемент - конец списка
    }
    link->next=NULL;//Так новый элемент последний (мы же добавляем в список элементы в конец) после этого элемента нет, то есть можно сказать, что дальше 0
    ++links_count; //Увеличиваем количество элементов
}
//////////////////////////////////////
///Количество элементов
template <class TYPE>
const int key_list<TYPE>::size() const
{
    return links_count;
}
//////////////////////////////////////
///Итератор
template <class TYPE>
const typename key_list<TYPE>::element* key_list<TYPE>::cursor (int pos)const
{
    if (pos<0 || pos>=links_count)
    {
        throw ("Incorrect index - item doesn`t exists\n");
    }
    element* current=m_begin;//Создаем курсор и направляем его на начало списка
    for (int i=0;i<pos;++i)//Перемещаемся на заданное количество элементов по списку
    {
        current=current->next;
    }
    return current;//Возвращаем адресс элемента на котором оставновились
}
//////////////////////////////////////
///Деструктор
template <class TYPE>
key_list<TYPE>::~key_list()
{
    try
    {
        if (links_count>0)
        {
            element* current=m_begin;//Создаем курсор и направляем его на начало
            while(current->next!=NULL)
            {
                element* previous=current;//Запоминаем элемент текущий элемент списка
                current=current->next;//Идем к следующему элементу
                delete previous;//Стираем предыдущий элемент
            }
            delete m_end;
        }
    }
    catch (...) {}
}

template <class TYPE>
bool compare(const key_list<TYPE>& list1,const key_list<TYPE>& list2)
{
    if (list1.size()!=list1.size()) return false;//Если количество элемнтов в списке разное, то уже можно сказать, что они неодинаковые - возвращаем ЛОЖЬ
    for (int i=0; i<list1.size(); ++i)
    {
        if(list1.cursor(i)->data!=list2.cursor(i)->data) return false; //Если данные i элемента не равны данным элемта i другого списка, значит списки неодинаковые - возвращаем ЛОЖЬ
    }
    return true; //Если до этого мы не возвратили ложь, значит у нас списки одинакового размера и жлементы с них соотвествуют равенству == , поэтому возвращем ПРАВДУ
}
int main(int argc, char* argv[])
{
    try
    {
        key_list<int> list1;
        key_list<int> list2;
        list1.add(10);
        list1.add(23);
        list2.add(10);
        list2.add(23);
        if (compare(list1,list2)==true)
        {
            std::cout << "They are equal\n";
        }
        else
        {
            std::cout << "They are not equal";
        }
    }
    catch (char* msg)
    {
        std::cout << msg;
    }
    catch (...)
    {
        std::cout << "An error";
    }
    getchar();
    return 0;
}

Добавлено @ 20:46
Проще

Код


#include <iostream>
#include <list>

template <class TYPE>
bool compare(std::list<TYPE>& list1,std::list<TYPE>& list2)
{
    typedef std::list<TYPE>::iterator ListIter; //Для удобства заменяем std::list<TYPE>::iterator на ListIter (меньше печатать)
    if (list1.size()!=list1.size()) return false; //Если количество элементов разное, значит списки неодинаковы
    for (ListIter iter=list1.begin(),iter2=list2.begin(); iter!=list1.end() && iter2!=list2.end(); ++iter,++iter2) //Создаем два курсора(итератора), которые направляем на начало первого и второго списка и идем вверх по списку, пока не достигнем концов списка
    {
        if(*iter!=*iter2) return false;//Если данные текущего элемента первого списка неравны данным текущего элемента второго списка, значит списки уже неравны
    }
    return true;
}

int main(int argc, char* argv[])
{
    std::list<int> list1;
    std::list<int> list2;
    list1.push_back(19);
    list1.push_back(35);
    list2.push_back(19);
    list2.push_back(35);
    if (compare(list1,list2)==true)
    {
        std::cout << "They are equal\n";
    }
    else
    {
        std::cout << "They are not equal";
    }
    getchar();
    return 0;
}

Это сообщение отредактировал(а) Xenon - 17.3.2007, 04:04

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

AleksDDem

Дата 17.3.2007, 02:50 (ссылка)

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

Загрузка ...

Шустрый

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

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

Спасибо большое smile

Если можете распишите пожалуйста поподробнее что какая строчка делает... А то я юзер, мало что понимаю. БУДУ ОЧЕНЬ ПРИЗНАТЕЛЕН....

Это сообщение отредактировал(а) AleksDDem - 17.3.2007, 02:57

Xenon

Дата 17.3.2007, 04:05 (ссылка)

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

Загрузка ...

Эксперт

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

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

Поправил пост - попытался объяснить ... мне просто все и так понятно, поэтому я не знаю как некоторые простые для меня уже вещи объяснить smile

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

AleksDDem

Дата 17.3.2007, 13:01 (ссылка)

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

Загрузка ...

Шустрый

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

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

а  что  такое std::?  Зачем  его  так   часто  употреблять?
А  как   вообще  вписать  в   программу  эти  списки?

template <class TYPE>
bool compare(std::list<TYPE>& list1,std::list<TYPE>& list2)
{
    typedef std::list<TYPE>::iterator ListIter; //Для удобства заменяем std::list<TYPE>::iterator на ListIter

И   этот  кусок  программы   мне  вообще  не   понятен...

ЗЫ. Тугодум  я   однако.... smile

Xenon

Дата 17.3.2007, 16:27 (ссылка)

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

Загрузка ...

Эксперт

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

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

std - пространство имен, в котором находятся все функции и прочее, типа cout, cin и т.д.
Можно так часто не писать, а в начале программы написать:

Код


using namespace std;

Но это не безопасно. Лучше уже тогда каждую функцию/тип подключать конкретно:

Код


using std::cout;
using std::cin;
using std::endl;
//и т.д.

Код


typedef std::list<TYPE>::iterator ListIter;

Здесь мы, буквально, говорим компилятору. что если он увидит ListIter, то вместо ListIter он должен подставлять std::list<TYPE>::iterator (это я сделал чтобы меньше потом печатать).
template <class TYPE> - это определение шаблона. По этому лучше читай книжки.

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

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