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

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

Задание
Решение

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

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

Дата: 12.09.2012

// 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;
}

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

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

Котик Добрый

04.02.2015

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();

};

curunir

27.08.2014

#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'); 
}

NaikoN
10.12.2013
Можно уточнить, что подразумевается под «двунаправленным списком»???
Войдите, чтобы ответить
- admin
  10.12.2013
  Тут все понятно написано.
  Войдите, чтобы ответить

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

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

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

Комментарии

Tourist

Артем Коршенко

Котик Добрый

curunir

NaikoN

admin

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