Սկիզբ » Ուսումնական նյութեր » Ծրագրավորում » Ծրագրավորման լեզուներ » C և C++ » Տվյալների տարրական կառուցվածքներ։ Երկկապակցված գծային ցուցակ (doubly linked list)

Տվյալների տարրական կառուցվածքներ։ Երկկապակցված գծային ցուցակ (doubly linked list)

| Օգոստոս 3, 2013 | Մեկնաբանված չէ |
Գծային ցուցակում տարրերը հաջորդականորեն կարգավորված են, բայց տարրերի հաջորդման կարգը որոշվում է ոչ թե ինդեքսով, այլ ցուցիչով, որոնք հանդիսանում են «ցուցակ» տվյլաների կառուցվածքի անբաժանելի մաս և դրանով  է պայմանավորված տվյալների այս կառոցվածքի հիմնական տարբերությունը մյուսից՝ վեկտորից ( պարզ ասած՝ զանգվածից)։
 
Վեկտոր 
  1. դիմում ցանկացած տարրին ինդեքսով, ալգորիթմի բարդությունը O(1),
  2. վեկտորի սկզբում կամ միջնամասում նոր տարր ավելացնելու ալգորիթմի բարդութույունը՝ O(n),
  3. վեկտորի վերջում տարրի ավելացման ալգորիթմի բարդութույունը՝ O(1),
  4. վեկտորում տարրի փնտրման ալգորիթմի բարդութույունը՝ O(n):

Ցուցակ

  1. ցուցակի ցանկացած տարրին դիմումը կատարվում է մնացած տարրերի վրայով հաջորդական շրջանցման միջոցով, այդ պատճառով ալգորիթմի բարդութույունն էO(n),
  2. ցուցակում ցանկացած հատվածում նոր տարր ավելացնելու ալգորիթմի բարդութույունն է O(1),
  3. ցուցակում տարրի փնտրման ալգորիթմի բարդութույունն է ՝ O(n):

 

Կախված խնդրից՝ կարելի, որպես տվյալների կառուցվածք ընտրել սրանցից ցանկացածը կամ համատեղել դրանք։
Օրինակ՝ եթե մեզ նախորոք հայտնի է մուտքի տվյալների չափը, ապա նախընտրելի է օգտվել վեկտորից, քանի որ այն ավելի արագ տվյալների կառուցված է (տես վերը բերված հիմնական գործողությունների ալգորիթմական բարդությունները), իսկ եթե տվյալների չափը դինամիկ փոփոխվում է կատարման ընթացքում, ապա այստեղ ավելի հարմար է օգտվել ցուցակից, քանի որ այն չի պահանջում նախորոք նշել իր մեջ պահվող տարրերի առավելագույն քանակը, բայց այստեղ մենք ունենում ենք արագության կորուստ (տես վերը բերված հիմնական գործողությունների ալգորիթմական բարդությունները)։ Իսկ օրինակ՝ հեշ-աղյուսակներում և գրաֆերում (գրաֆի կապակցված ցուցակներով պահման դեպքում) այս երկու տվյալների կառուցվածքները համատեղվում են։

Ցուցակի յուրաքանչյուր տարր ունի key արժեք և prev ու next ցուցիչներ: «key» այն տվյալն է, որը պարունակում է տվյալ տարրը, prev– ը ցուցիչ է տվյալ տարրին նախորդղ տարրի վրա, next -ը ցուցիչ է, որը ցույց է տալիս տվյալ տարրին հաջորդող տարրի վրա։ Բացի այդ ցուցակը ունի ևս երկու ցուցիչներ, դրանք են head -ը և tail -ը։ head -ը հանդիսանում է տարր, որը պարունակում է ցուցիչ ցուցակի առաջին տարրի վրա կամ այլ կերպ ասած head-ը ցուցակի առաջին տարրն է կամ գլուխը։
tail-ը հանդիսանում է ցուցակի վերջին տարրը կամ պոչը։
Կապակցված ցուցակները լինում են մի քանի տեսակի․

  1. միակապակցված ցուցակ, երբ ամեն տարր պարունակում է միայն next ցուցիչ,
  2. երկկապակցված ցուցակ, երբ ամեն տարր պարունակում է և՛ netx և՛ prevցուցիչները,
  3. xor կապակցված ցուցակ, երբ ամեն տարր հանդիսանում է նախորդ և հաջորդ տարրերի հասցեների միջև կիրառված տրամաբանական xor գործողության արդյունք,
  4. շրջանաձև ցուցակ, երբ ցուցակի վերջին տարրը պարունակում է ցուցիչ առաջին տարրի վրա և այլն։
Անկախ կապակցված ցուցակի կոնկրետ տիպից, այն պարունակում է ընդհանուր բոլոր տիպերի համար գործողություններ, որոնք փոխում են «կապակցված ցուցակ» աբստրակցիայի նմուշ հանդիսացող օբյեկտների ներքին վիճակը։ Այդ գործողություններն են․

 

  1. List-Search(L, k), կամ L ցուցակում K բանալով տարրի փնտրում․

          Այս գործողությունը ունի Ѳ(n) ալգորիթմական բարդություն կամ f(n) = Ѳ(g(n)), որտեղ n = g(n),սա նշանակում է, որ գոյություն ունեն այնպիսի c1 և c2 թվեր, որ c1*n =  f(n) <= c2*n, իսկ վերջինս էլ նշանակում է, որ այս գործողության ալգորիթմական բարդության Ѳ(n) ֆունկցիան սահմանափակված է և վերևից և ներքից, օրինակ, եթեf(n) = n, այսինքն տվյալ k տարր ըգտնելու համար պետք է անցնել n հատ տարրերի վրայով, ապա միշտ կարելի է գտնել այնպիսի երկու C1 (C1 = c1*n) C2 (C2 = c2*n) թվեր, որ C1 <= n <= C2, օրինակ՝ եթե փնտրվող թիվը ցուցակում հենց առաջին տարրն է, ապա ալգորիթմում կկատարվի ըմդամենը մեք քայլ կամ c1*n = c1, իսկ վատագույն դեպքում, երբ փնտրվող տարրը ցուցակի վերջում է կկատարվի n քայլ կամc2*n = c2*n և կստանանք՝ c1 <= n <= c2*n,այստեղ կարող ենք ընտրել կամայական երկու թիվ, այնպես, որ պահպանվի բերված անհավասարությունը․ օրինակ՝ c1 = 1, c2 = 100, կստանանք՝ 1 <= n <= 100*n :

2. List-Insert(L, x) կամ x արժեքով տարրի  ավելացում ցուցակի սկզբում

Այս գործողության ալգորիթմական բարդությունն է O(1), այսինքն կատարվում է հաստատուն ժամանակում։ Ընդանհրապես հաստատուն ժամանակը չի նշանակում, որ բոլոր համակարգիչների վրա, այս գործողությունը կատարվում է միևնույն ժամանակում, այլ նշանակում է, որ տվյալ ալգորիթմը  անկախ է մուտքի տվյալների չափից և կատարվում է սահմանափակ ժամանակահատվածում, իսկ ահա այդ սահմանափակ ժամանակահատվածը կարող է տարբեր լինել տարբեր համակարգիչներչ վրա։
      3. List-Delete(L, x) կամ x արժեքով տարրի ջնջում ցուցակից․
Զուտ տարրի ջնջման ալգորիթմական բարդությունը O(1) է, բայց քանի որ սկզբում նախ պետք է փնտրել և գտնել տարրը (կատարվում է List-Search(L, k) գործաղությունը Ѳ(n)բարդությամբ և այնուհետև նոր ջնջել, (կատարվում է զուտ ջնջումը Ѳ(1) ժամանակում ապա գործողության ալգորիթմական բարդությունը դառնում Ѳ(n), քանի որ Ѳ(f(n)) + Ѳ(g(n)) = Ѳ(max(f(n), g(n))) կամ Ѳ(n) + Ѳ(1) = Ѳ(max(n, 1)) = Ѳ(n)
Այս հոդվածում մենք կներկայացնենք երկապակցված ցուցակի իրականացումը։ Ցուցակը բաղկացած է միմյանց հետ կապակցված տարրերից (node-երից)․
Բերենք node.hpp ֆայլի կոդը․
#ifndef NODE_HPP
#define NODE_HPP

template <class T>
class list;

template <class T>
class node
{
	private:
		friend class list<T>;

	private:
		node* m_next;
		node* m_prev;
		T m_data;

	public:
		node() :  m_next(0)
				, m_prev(0)
				, m_data(0) {}

		explicit node(T d) :  m_next(0)
							, m_prev(0)
							, m_data(d) {}
		T get_data()
		{
			return m_data;
		}
};

#endif // NODE_HPP

Ցուցակը կպարունակի հետևյալ հիմնական գործողությունները․
node* find(T data) const,
void insert_at_front(T data),
void insert_at_back(T data),
void delete_at_front(),
void delete_at_back(),
bool is_empty() const ։
Բերենք ցուցակի կոդը list.hpp

#ifndef LIST_HPP
#define LIST_HPP

#include <cassert>
#include <iostream>

#include "node.hpp"

template <class T>
class list
{
	private:
		node<T>* m_head;
		node<T>* m_tail;
		unsigned m_size;

	public:
		list() :   m_size(0) 
				 , m_head(0)
				 , m_tail(0){}

		node<T>* get_new_node(T d) const;
		node<T>* find(T data) const;
		void insert_at_front(T data);
		void insert_at_back(T data);
		void delete_at_front();
		void delete_at_back();
		bool is_empty() const;
		void print() const;
		node<T>* get_begin() const
		{
			return m_head;
		}
		node<T>* get_end() const
		{
			return m_tail;
		}
		unsigned get_size() const
		{
			return m_size;
		}
		~list();

	public:
		list(const list&);
		list<T>& operator=(const list&);
};

template <class T>
list<T>::list(const list& o)
{
	this->m_size = o.m_size;
	this->m_head = new node<T>();
	this->m_tail = new node<T>();
	*(this->m_head) = *(o.m_head);
	*(this->m_tail) = *(o.m_tail);
}

template <class T>
list<T>::~list()
{
	delete m_head;
	delete m_tail;
	m_head = 0;
	m_tail = 0;
}

template <class T>
list<T>& list<T>::operator=(const list& o)
{
	if(this == &o)
	{
		return *this;
	} else
	{
		this->m_size = o.m_size;
		delete this->m_head;
		delete this->m_tail;
		this->m_head = new node<T>();
		this->m_tail = new node<T>()
		*(this->m_head) = *(o.m_head);
		*(this->m_tail) = *(o.m_tail);
		return *this;
	}
}
template <class T>
node<T>* list<T>::get_new_node(T data) const 
{
	node<T>* n = new node<T>(data);
	assert(n != 0);
	return n;
}

template <class T>
bool list<T>::is_empty() const
{
	if(m_head == 0)
	{
		return true;
	}
	return false;
}

template <class T>
void list<T>::print() const 
{
	if(is_empty())
	{
		return;
	}
	node<T>* t = m_head;
	while(t != 0)
	{
		std::cout << t->m_data << " ";
		t = t->m_next;
	}
}

template <class T>
node<T>* list<T>::find(T data) const
{
	if(is_empty())
	{
		return 0;
	}
	node<T>* t = m_head;
	while(t != 0 && t->m_data != data)
	{
		t = t->m_next;
	}
	return t;
}

template <class T>
void list<T>::insert_at_front(T data)
{
	node<T>* n = get_new_node(data);
	if(m_head == 0)
	{
		m_head = m_tail = n;
		n->m_next = n->m_prev = 0;
		++m_size;
	}
	else
	{
		n->m_next = m_head;
		if(m_head != 0)
		{
			m_head->m_prev = n;
		}
		m_head = n;
		n->m_prev = 0;
		++m_size;
	}
}

template <class T>
void list<T>::insert_at_back(T data)
{
	node<T>* n = get_new_node(data);
	if(m_tail == 0)
	{
		m_head = m_tail = n;
		n->m_next = n->m_prev = 0;
		++m_size;
	}
	else
	{
		m_tail->m_next = n;
		n->m_prev = m_tail;
		m_tail = n;
		++m_size;
	}

}

template <class T>
void list<T>::delete_at_front()
{
	if(is_empty())
	{
		return;
	}
	else
	{
		node<T>* t = m_head->m_next;
		t->m_prev = 0;
		delete m_head;
		m_head = t;
		--m_size;
	}
}

template <class T>
void list<T>::delete_at_back()
{
	if(is_empty())
	{
		return;
	}
	else
	{
		node<T>* t = m_tail->m_prev;
		t->m_next = 0;
		delete m_tail;
		m_tail = t;
		--m_size;
	}
}

#endif // LIST_HPP
Տվյալների տարրական կառուցվածքներ։ Երկկապակցված գծային ցուցակ (doubly linked list), 9.1 out of 10 based on 10 ratings

Նշագրեր: , , , ,

Բաժին: C և C++, Ալգորիթմներ, Ծրագրավորում

Կիսվել , տարածել , պահպանել

VN:F [1.9.20_1166]
Rating: 9.1/10 (10 votes cast)

Մեկնաբանեք

Կհաստատվեն միայն մեսրոպատառ հայերենով գրած մեկնաբանությունները

249