Двунаправленный список

Уровень сложности:

Разработать двунаправленный список.  Добавить элемент в конец списка и удалить из списка первый элемент.

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

E-mail : admin@cppstudio.com

 

Автор: admin
Дата: 12.09.2012
Поделиться:

Комментарии

  1. Tourist

    // Main.cpp
    #include <time.h>
    #include "List.h"
    #include "TEMPlete_CPP.cpp"
    
    using namespace std;
    
    void main()
    {
    	setlocale(LC_ALL, "rus");
    	srand((unsigned)time(NULL));
    	int a = 10;
    	List<int> A(a);
    	for (int i = 0; i < a; i++)
    	{
    		int b = rand() % 99;
    		A.Add_to_last(b);
    	}
    
    	for (int i = 0; i < A.Get_amount(); i++)
    	{
    		cout << A[i] << "\t";
    	}
    	cout << endl;
    
    
    	cout << endl;
    	system("pause");
    }
    //
    
    
    // TEMPlete_CPP.cpp
    #include "List.cpp"
    //
    
    
    // List.h
    
    #pragma once
    #include <iostream>
    
    #ifndef List_H
    #define List_H
    
    template<typename T>
    class List
    {
    	template <typename T>
    	struct Elem
    	{
    		T data;
    		int i;
    		Elem *next = NULL, *prev = NULL;
    
    		Elem()
    		{
    			i = 0;
    			data = 0;
    		}
    	};
    	int amount;
    	Elem<T> * Head, *Tail;
    	int que;
    public:
    
    	List();	
    	List(int);	
    	List(const List <T> &);	
    	T GetElem(const int);
    	void Add_to_last(T);	
    	void Del_Head();	
    	void Del_Tail();	
    	void Del_Pos(const int);
    	void Extract();	
    	void Del_ALL();	
    	void Show();
    	void Show_End();
    	void Add_Queue(T);	
    	void Add_que_ocher(const int);
    	void AddTail(T);		
    	List <T> operator+(const List <T>&);
    	List <T> & operator= (const List<T>&);
    	const T & operator [](const int);
    	bool operator == (const List<T>&);
    	bool operator != (const List<T>&);	
    	bool IsEmpty();
    	bool IsFull();
    	int Get_amount();
    	int Get_Que();
    	~List();
    };
    
    #endif 
    //
    
    // List.cpp
    
    #include "List.h"
    
    
    template<typename T>
    List<T>::List()
    {
    	Head = NULL;
    	que = 0;
    	Tail = NULL;
    	amount = 0;
    }
    
    template<typename T>
    List<T>::List(int s)
    {
    	if (s > 0)
    	{
    		que = s;
    	}
    }
    
    template<typename T>
    List<T>::List(const List <T> &obj)
    {
    	Head = Tail = NULL;
    	amount = 0;
    	Elem<T> *temp = obj.Head;
    	while (temp != NULL)
    	{
    		Add_to_last(temp->data);
    		temp = temp->next;
    	}
    }
    
    template<typename T>
    T List<T>::GetElem(const int i)
    {
    	Elem<T> *temp = new Elem<T>;
    	temp = Head;
    	int p = 0;
    	while (temp != NULL)
    	{
    		if (i == p)
    		{
    			return temp->data;
    		}
    		p++;
    		temp = temp->next;
    	}
    	return Elem<T>();
    }
    
    template<typename T>
    void List<T>::Add_to_last(T a)
    {
    	if (Head == NULL)
    	{
    		Head = Tail = new Elem<T>;
    		Head->data = a;
    
    		amount++;
    		Head->i = amount;
    	}
    	else
    	{
    		Elem<T> *it = new Elem<T>;
    		it->data = a;
    		it->next = NULL;
    		it->prev = Tail;
    
    		Tail->next = it;
    		Tail = it;
    		amount++;
    		it->i = amount;
    	}
    }
    
    template<typename T>
    void List<T>::Del_Head()
    {
    	if (Head != NULL)
    	{
    		Elem<T> *it = Head;
    		it->prev = NULL;
    		Head->prev = NULL;
    		Head = Head->next;
    		delete it;
    		amount--;
    	}
    }
    
    template<typename T>
    void List<T>::Del_Tail()
    {
    	Elem<T> *it1;
    	Elem<T> *it2;
    
    	for (it1 = Head, it2 = Head->next;
    		it2->next != NULL;
    		it1 = it2, it2 = it2->next)
    	{}
    
    	Tail = it1;
    	Tail = Tail->prev;
    	delete it2;
    	it1->next = NULL;
    	amount--;
    }
    
    template<typename T>
    void List<T>::Del_Pos(const int k)
    {
    	Elem<T> *temp = new Elem<T>;
    	temp = Head;
    	int count = 0;
    	if (amount >= k && k > 0)
    	{
    		while (temp != NULL)
    		{
    			if (k > 1 && k < amount)
    			{
    				if (count == k - 1)
    				{
    					Elem<T> *t = temp;
    
    					temp->prev->next = temp->next;
    					temp->next->prev = temp->prev;
    					delete t;
    					break;
    				}
    				count++;
    				temp = temp->next;
    			}
    			if (k == 1)
    			{
    				if (count == k)
    				{
    					Elem<T> *temp = Head;
    
    					Head = Head->next;
    					Head->prev = NULL;
    					delete temp;
    				}
    				count++;
    				temp = temp->next;
    			}
    			if (k == amount)
    			{
    				if (count == k - 1)
    				{
    					Elem<T> *temp = Head;
    					Tail = Tail->prev;
    					Tail->next = NULL;
    					delete temp;
    					break;
    				}
    				count++;
    				temp = temp->next;
    			}
    		}
    		amount--;
    	}
    }
    
    template<typename T>
    void List<T>::Extract()
    {
    	if (Head != NULL && IsEmpty() != true)
    	{
    		Del_Head();
    	}
    }
    
    template<typename T>
    void List<T>::Del_ALL()
    {
    	while (Head != NULL)
    	{
    		Del_Head();
    	}
    }
    
    template<typename T>
    void List<T>::Show()
    {
    	amount = 0;
    	Elem<T> *it;
    	it = Head;
    	if (Head != NULL)
    	{
    		it->i = 0;
    	}
    	while (it != NULL)
    	{
    		it->i = amount;
    		amount++;
    		cout << it->data << "  ";
    		it = it->next;
    	}
    	if (que == 0)
    	{
    		que = amount;
    	}
    	cout << endl;
    }
    
    template<typename T>
    void List<T>::Show_End()
    {
    	amount = 0;
    	Elem<T> *it;
    	it = Tail;
    	while (it != NULL)
    	{
    		amount++;
    		cout << it->data << "  ";
    		it = it->prev;
    	}
    	cout << endl;
    }
    
    template<typename T>
    void List<T>::Add_Queue(T a)
    {
    	if (IsFull() != true)
    	{
    		if (amount < que)
    		{
    			Add_to_last(a);
    		}
    	}
    }
    
    template<typename T>
    void List<T>::Add_que_ocher(const int a)
    {
    	que += a;
    }
    
    template<typename T>
    void List<T>::AddTail(T n)
    {
    	Elem<T> * temp = new Elem<T>;
    
    	temp->next = 0;
    	temp->data = n;
    	temp->prev = Tail;
    	if (Tail != 0)
    	{
    		Tail->next = temp;
    	}
    	if (amount == 0)
    	{
    		Head = Tail = temp;
    	}
    	else
    	{
    		Tail = temp;
    	}
    	cout << Tail->data << endl;
    	amount++;
    }
    
    template<typename T>
    List <T> List<T>::operator+(const List <T>& L)
    {
    	List res(*this);
    	Elem<T> * temp = L.Head;
    	while (temp != 0)
    	{
    		res.AddTail(temp->data);
    		temp = temp->next;
    	}
    	return res;
    }
    
    template<typename T>
    List <T> & List<T>::operator= (const List & L)
    {
    	if (this == &L)
    	{
    		return *this;
    	}
    	this->~List();
    	Elem<T> * temp = L.Head;
    
    	while (temp != NULL)
    	{
    		Add_to_last(temp->data);
    		temp = temp->next;
    	}
    	return *this;
    }
    
    template<typename T>
    const T & List<T>::operator [](const int k)
    {
    	Elem<T> *t = Head;
    	if (amount > 0)
    	{
    		amount = 0;
    	}
    	int j = 0;
    	while (t != NULL)
    	{
    		amount++;
    		t->i = j;
    		t = t->next;
    		j++;
    	}
    
    	Elem<T> *temp = Head;
    	for (int i = 0; (i <= this->amount) && (temp->i != k); i++, temp = temp->next)
    	{
    		if (i == this->amount)
    		{
    			return NULL;
    		}
    	}
    	return temp->data;
    }
    
    template<typename T>
    bool List<T>::operator == (const List<T>& obj)
    {
    	if (amount != obj.amount)
    	{
    		return false;
    	}
    
    	Elem<T> *t1, *t2;
    	t1 = Head;
    	t2 = obj.Head;
    	while (t1 != 0)
    	{
    		if (t1->data != t2->data)
    		{
    			return false;
    		}
    		t1 = t1->next;
    		t2 = t2->next;
    	}
    	return true;
    }
    
    template<typename T>
    bool List<T>::operator != (const List<T>& obj)
    {
    	return !(*this == obj);
    
    }
    
    template<typename T>
    bool List<T>::IsEmpty()
    {
    	if (que == 0)
    	{
    		cout << "очередь пустая" << endl;
    		return true;
    	}
    	cout << "в очереди есть элементы" << endl;
    	return false;
    }
    template<typename T>
    
    bool List<T>::IsFull()
    {
    	if (que == amount)
    	{
    		cout << "очередь заполненна" << endl;
    		return true;
    	}
    	cout << "очередь незаполненна" << endl;
    	return false;
    }
    
    template<typename T>
    int List<T>::Get_amount()
    {
    	return amount;
    }
    
    template<typename T>
    int List<T>::Get_Que()
    {
    	return que;
    }
    
    template<typename T>
    List<T>::~List()
    {
    	Del_ALL();
    	que = 0;
    }
    
    
  2. Артем Коршенко

    Вот, выкладываю на пастебин, ибо ваша форма вставки кода очень глючит (после неё нельзя писать комментарий).
    pastebin.com/cjqN6Qq8

    По умолчанию включен дебаг-режим. Выключить:
    #define debug false

  3. Котик Добрый

    template <typename T>

    class MyList
    {
        struct node{
            T value;
            struct node *nextNode;
            struct node *beforeNode;
        };
        struct node *firstNode;
        struct node *lastNode;
    public:
        MyList()
        {
            firstNode=0;
            lastNode=0;
        }
        bool append(T obj)
        {
            struct node* currentNode=lastNode;
            lastNode=new struct node;
            if(lastNode)
            {
                if(!firstNode)
                    firstNode=lastNode;
                lastNode->value=obj;
                lastNode->nextNode=0;
                lastNode->beforeNode=currentNode;
                if(currentNode!=0)
                    currentNode->nextNode=lastNode;
                return true;
            }
            else
                return false;
        }
        bool remove(int numElem)
        {
            int count=0;
            struct node* currentNode=firstNode;
            while(currentNode!=0)
            {
                if(numElem==count)
                {
                    struct node *next=currentNode->nextNode;
                    struct node *before=currentNode->beforeNode;
                    if(next!=0)
                        next->beforeNode=before;
                    else
                        next=0;
                    if(before!=0)
                        before->nextNode=next;
                    else
                        before=0;
                    if(count==0)//если удаляется первый элемент
                        firstNode=next;
                    if(count==this->getLenght())//если удаляется последний элемент
                        lastNode=before;
                    next=0;
                    before=0;
                    delete currentNode;
                    return true;
                }
                else
                {
                    count++;
                    currentNode=currentNode->nextNode;
                }
            }
            return false;
        }
        void print()
        {
            struct node *currentNode=firstNode;
            while(currentNode!=0)
            {
                cout<<currentNode->value<<endl;
                currentNode=currentNode->nextNode;
            }
        }
        int getLenght()
        {
            int len=0;
            struct node *currentNode=firstNode;
            while(currentNode!=0)
            {
                len++;
                currentNode=currentNode->nextNode;
            }
            return len;
        }
        T findElement(int numElem)
        {
            int count=0;
            struct node *currentNode=firstNode;
            while(currentNode!=0)
            {
                if(count!=numElem){
                    currentNode=currentNode->nextNode;
                    count++;
                }
                else
                {
                    return currentNode->value;
                }
            }
            return T();
        }
    };
  4. curunir

    curunir

    #include <iostream>
    
    class Node
    {
      int value;
      Node* prev, *next;
      
      public:
      Node(int VALUE)
      { 
        prev = next = NULL;
        value = VALUE;
      }
      
      Node(Node* PREV, int VALUE)
      { 
        prev = PREV;
        prev->next = this;
        next = NULL;
        value = VALUE;
      }
      
      ~Node()
      {
        if(prev != NULL)
          prev->next = next;
        if(next != NULL)
          next->prev = prev; 
      }
      
      Node* Add(int VALUE)
      {
        next = new Node(this, VALUE); 
        return prev;
      }
      
      int ShowList()
      {
        std::cout << value << ' ';
        if(next != NULL)
          next->ShowList();
      }
      
      Node* GetPrev()
      {
        return prev; 
      }
      
      Node* GetNext()
      {
        return next; 
      }
    };
    
    main()
    {
      Node* Begin = NULL, *End = NULL, *Temp;
      char option;
      int i, value;
      
      do
      {
        if(Begin == NULL)
          std::cout << "List is empty";
        else
          Begin->ShowList();
          
        std::cout << "\n1 - Add to end\n2 - Delete from begin\n3 - Exit\nMy choice: ";
        std::cin >> option;
        
        switch(option)
        {
          case '1':
          {
            std::cout << "Input value: ";
            std::cin >> value;
            
            if(End != NULL)
            {
              Temp = new Node(End, value);
              End = Temp;
            }
            else
              Begin = End = new Node(value);
          }break;
          
          case '2':
          {
            if(Begin != NULL)
            {
              Temp = Begin->GetNext();
              delete Begin;
              Begin = Temp;
              if(Begin == NULL)
                End = NULL;
            }
          }break;
        }
        
        
      }
      while(option != '3'); 
    }
  5. NaikoN

    Можно уточнить, что подразумевается под «двунаправленным списком»???

Оставить комментарий

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