Класс "Односвязный список"

[mixon-21]

Добавить в класс "Односвязный список" следующие функции: вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента (функция возвращает позицию найденного элемента в случае успеха или NULL в случае неудачи).

#include <iostream>

using namespace std;

class List{
 public:
	 List();
     ~List();
??????????????????????????
 private:
	 char text;
	 int count;
 };
 
 void main()
 {
??????????????
 }

обясните плиз на примерах

[SAMOUCHKA]

А что конкретно объяснить?

Писал я подобное, только двусвязный список.
вот нашел проект

/ Класс узла списка (используется как структура)

template <class T> class Node

{

public:

    T v;

    Node<T> *next;

    Node<T> *previos;



    Node()

    {

        previos = next = NULL;

    }

    Node(T val)

    {

        previos = next = NULL;

        v = val;

    }

    Node(const Node *nod)

    {

        v = nod->v;

        next = nod->next;

        previos = nod->previos;

    }

[SAMOUCHKA]

// Класс итератор



template <class T> class Iterator

{

private:

    Node<T> *node;



public:

    Iterator(){node = NULL;}

    Iterator(Node<T> *nod)

    {

        node = nod;

    }

    Iterator<T> operator++ ()

    {

        node = node->next;

        return *this;

    }

    Iterator<T> operator-- ()

    {

        node = node->previos;

        return *this;

    }

    Iterator<T> operator= (const Iterator<T> &it)

    {

        node = it.node;

        return *this;

    }



    Iterator<T> operator+ (int di)

    {

        Iterator<T> temp;

        temp.node = node;

        for(int i = 1; i < di; i++)

        {

            ++temp;

        }

        return temp;

    }

    Iterator<T> operator- (int di)

    {

        Iterator<T> temp;

        temp.node = node;

        for(int i = 1; i < di; i++)

        {

            --temp;

        }

        return temp;

    }



    void setNode(Node<T> *nod)

    {

        node = nod;

    }



    Node<T>* getNode()

    {

        return node;

    }



    T value()

    {

        return node->v;

    }

};

[SAMOUCHKA]

// Класс список



template <class T> class List

{

private:

    Node<T> *frontNode; // Указатель на первый узел списка

    Node<T> *backNode;  // Указатель на последний узел списка



public:

    List()

    {

        frontNode = NULL;

        backNode = NULL;

    }

    ~List()

    {

         while(1)

        {

            Node<T> *temp;



            // Эта строка не нужна

            // использовалась, чтобы посмотреть как действует деструктор

            //std::cout<<"nnbackNode: "<<backNode<<std::endl;



            if(frontNode == NULL)

                return;

            if(frontNode == backNode)

            {

                delete frontNode;

                return;

            }

            temp = backNode->previos;

            delete backNode;

            backNode = temp;

        }

    }



    // Добавляет элемент в конец списка

    void pushBack(T val)

    {

        if(frontNode == NULL) // Если список пуст

        {

            frontNode = new Node<T>(val);

            backNode = frontNode;

            backNode->previos = frontNode;

            frontNode->next = backNode;

            backNode->next = NULL;

        }

        else

        {

            Node<T> *temp = backNode; // Запоминаем адресс последнего узла

            backNode = new Node<T>(val);

            temp->next = backNode;

            backNode->previos = temp;

            backNode->next = NULL;

        }

    }



    // Добавляет элемент в начало списка

    void pushFront(T val)

    {

        if(frontNode == NULL) // Если список пуст

        {

            frontNode = new Node<T>(val);

            backNode = frontNode;

            backNode->previos = frontNode;

            frontNode->next = backNode;

            backNode->next = NULL;

        }

        else

        {

            Node<T> *temp = frontNode; // Запоминаем адреосс первого узла

            frontNode = new Node<T>(val);

            temp->previos = frontNode;

            frontNode->next = temp;

            frontNode->previos = NULL;

        }

    }

[SAMOUCHKA]

продолжение

  // Удаляет последний элемент

    void popBack()

    {

        if(frontNode == NULL) // Если список пуст

            return; // выходим из функции

        if(backNode == NULL) // Если в списке один элемент

        {

            delete frontNode; // Удаляем первый элемент

            frontNode = NULL;

            return;

        }

        Node<T> *temp = backNode; // Запоминаем адресс последнего узла

        backNode = temp->previos;

        delete temp;

        backNode->next = NULL;

    }



    //

    void popFront()

    {

        if(frontNode == NULL) // Если список пуст

            return; // выходим из функции

        if(backNode == NULL) // Если в списке один элемент

        {

            delete frontNode; // Удаляем первый элемент

            frontNode = NULL;

            return;

        }

        Node<T> *temp;

        temp = frontNode; // Запоминаем адресс первого элемента

        frontNode = frontNode->next;

        delete temp;

        frontNode->previos = NULL;

    }



    // Вставляет элемент со значением val, в позицию

    // сразу следующую за позицией, на которую указывает итератор itr

    void isert(T val, Iterator<T> itr)

    {

        Node<T> *temp;

        if(itr.getNode()->next == NULL) // Если элемент последний

        {

            temp = backNode;

            backNode = new Node<T>(val);

            temp->next = backNode;

            backNode->previos = temp;

            return;

        }

        temp = itr.getNode()->next;

        Node<T> *insertNode = new Node<T>(val);

        itr.getNode()->next = insertNode;

        insertNode->previos = itr.getNode();

        insertNode->next = temp;

        temp->previos = insertNode;

    }



    // Возвращает итератор на первый элемент списка

    Iterator<T> begin()

    {

        Iterator<T> it(frontNode);

        return it;

    }



    // Возвращает итератор на последний элемент списка

    Iterator<T> end()

    {

        Iterator<T> it(backNode);

        return it;

    }



    // Возвращает размер списка

    int size()

    {

        int count = 0;

        Node<T> *temp = frontNode;

        while(temp != NULL)

        {

            count++;

            temp = temp->next;

        }

        return count;

    }



    // Возвращает true если список пуст, иначе возвращает false

    bool emty()

    {

        if(frontNode == NULL)

            return true;

        return false;

    }



    // Удаляет элемент на который ссылается itr

    void erase(Iterator<T> itr)

    {

        Node<T> *delNode;

        delNode = itr.getNode();

        if(delNode->next == NULL) // Если элемент последний

        {

            popBack();

            return;

        }

        if(delNode->previos == NULL) // Если элемент первый

        {

            popFront();

            return;

        }

        Node<T> *n_Node, *p_Node;

        n_Node = delNode->next;

        p_Node = delNode->previos;

        p_Node->next = n_Node;

        n_Node->previos = p_Node;

        delete delNode;

    }



    // Удаляет все элементы списка

    void clear()

    {

        while(1)

        {

            Node<T> *temp;

            if(backNode == frontNode)

            {

                delete frontNode;

                backNode = NULL;

                frontNode = NULL;

                return;

            }

            temp = backNode->previos;

            delete backNode;

            backNode = temp;

        }

    }

};

[SAMOUCHKA]

тестирование

#include <iostream>

using namespace std;



int main()

{

    List<char> list0; // Создаем список елементов типа char



    cout<<"list0.emty: "<<list0.emty()<<endl; // Если список пуст emty вернет 1, иначе 0

    cout<<"list0.size: "<<list0.size()<<endl<<endl;  // Размер списка



    // Вставляем четыре елемента в конец списка

    list0.pushBack('a');

    list0.pushBack('b');

    list0.pushBack('c');

    list0.pushBack('d');

    // Вставляем три елемента в начало списка

    list0.pushFront('A');

    list0.pushFront('B');

    list0.pushFront('C');



    cout<<"list0.emty: "<<list0.emty()<<endl; // Если список пуст emty вернет 1, иначе 0

    cout<<"list0.size: "<<list0.size()<<endl<<endl;  // Размер списка



    // Обход списка с помощью итератора

    Iterator<char> itr; // Создаем итератор

    itr = list0.begin(); // устанавливаем его в начало

    for(int i = 0; i < list0.size(); i++)

    {

        char ch;



        ch = itr.value();

        cout<<ch<<' ';



        ++itr;

    }

    cout<<endl<<endl;



    cout<<"list0.popBack"<<endl;

    list0.popBack(); // Удаляем последний елемент списка

    // Посмотрим результат удаления

    itr = list0.begin(); //устанавливаем итератор в начало

    for(int i = 0; i < list0.size(); i++)

    {

        char ch;



        ch = itr.value();

        cout<<ch<<' ';



        ++itr;

    }

    cout<<endl<<endl;



    cout<<"list0.popFront"<<endl;

    list0.popFront(); // Удаляем первый елемент списка

    itr = list0.begin(); //устанавливаем итератор в начало

    for(int i = 0; i < list0.size(); i++)

    {

        char ch;



        ch = itr.value();

        cout<<ch<<' ';



        ++itr;

    }

    cout<<endl<<endl;



    // Перегруженный оператор + и функция value, класса Iterator

    itr = list0.begin(); //устанавливаем итератор в начало

    cout<<"(itr + 3).value: "<<(itr + 3).value()<<endl<<endl;



    // Функция isert(T val, Iterator<T> itr)

    cout<<"list0.isert(T val, Iterator<T> itr)"<<endl;

    list0.isert('I', itr + 3);

    itr = list0.begin(); //устанавливаем итератор в начало

    for(int i = 0; i < list0.size(); i++)

    {

        char ch;



        ch = itr.value();

        cout<<ch<<' ';



        ++itr;

    }

    cout<<endl<<endl;



    // Функция erase

    cout<<"list0.erase: "<<endl;

    itr = list0.begin(); //устанавливаем итератор в начало

    list0.erase(itr + 4);

    for(int i = 0; i < list0.size(); i++)

    {

        char ch;



        ch = itr.value();

        cout<<ch<<' ';



        ++itr;

    }

    cout<<endl<<endl;



    // Удаление всех элементов, функция clear

    cout<<"list0.clear"<<endl;

    list0.clear();

    cout<<"list0.emty: "<<list0.emty()<<endl; // Если список пуст emty вернет 1, иначе 0

    cout<<"list0.size: "<<list0.size()<<endl<<endl;  // Размер списка



    return 0;

}

в одном посте не уместилось, пришлось разделить

[Гром]

Воспользовались бы вы поиском по форуму, сотню раз ведь уже объясняли, как списки создавать. Но, так и быть, базу еще раз повторю.

Список состоит из узлов

struct MyData { /**/ };   //Данные, которые хранятся в списке

struct Node
{
MyData data;   //Если в списке хранятся целые числа, можно записать int data; со структурой - более общий случай
Node* next;   //Указатель на следующий узел
};

Суть в следующем - класс списка содержит указатель на голову списка (на первый из узлов), каждый узел содержит указатель на следующий за ним. Если указатель == 0, то этот узел был последним, за ним ничего нет. Работа со списком обычно заключается в том, что начиная с головы переходим к следующему элементу и что-то с ним делаем.
Примеры:

class List
{
public:
List();   //Создаем пустой список
~List();
void PrintAll();   //Распечатать все
bool IsMember(const MyData& d);   //Содержится ли такой элемент в списке
private:
Node* top;
};
void List::PrintAll()
{
if (top)   //Если указатель на голову не ноль, т.е. список не пуст
 {
 Node* x = top;
 while(x)   //Пока указатель на текущий не ноль, т.е. указывает на один из узлов
  {
  std::cout << x -> data;   //Распечатать
  x = x -> Next;   //Перейти к следующему
  }
 }
}
bool List::IsMember(const MyData& d)
{
Node* x = top;
while (x)
 {
 if (x -> data == d)   //Сравнили данные из этого узла с образцом
  return true;   //Если равны - вернули истину, закончили
 x = x -> next;   //Если нет - переходим к следующему
 }
return false;   //Если прошли до конца, и так и не нашли образец, значит его в списке нет
}

Вставка элемента после X делается так: создаем новый узел, устанавливаем его указатель Next на X -> Next, а у икса меняем этот некст на адрес нового узла. Удаление элемента после икса - говорим, что за иксом идет тот, что раньше шел через один после него (икс-некст = икс-некст-некст), освобождаем память икс-некст. Плюс проверки на нулевые указатели.

Дальше, надеюсь, разберетесь.

[SAMOUCHKA]

Воспользовались бы вы поиском по форуму, сотню раз ведь уже объясняли, как списки создавать. Но, так и быть, базу еще раз повторю.

так не интересно хотелось самому с нуля

[Гром]

Сообщение от SAMOUCHKA

так не интересно хотелось самому с нуля

В общем-то, я топикстартеру, а пока писал - тут и вы написали. Хотя форматирование у вас ужасное. Почему бы не сократить объем в два-три раза, выкинув все пустые строки? Я бы, если честно, в такой простыне даже разбираться не стал, невзирая на содержание. Читать же невозможно.

[SAMOUCHKA]

Сообщение от Гром

В общем-то, я топикстартеру, а пока писал - тут и вы написали. Хотя форматирование у вас ужасное. Почему бы не сократить объем в два-три раза, выкинув все пустые строки? Я бы, если честно, в такой простыне даже разбираться не стал, невзирая на содержание. Читать же невозможно.

да согласен. Давно это было Сейчас бы я по другому сделал.