|
Can you use a bag class instead of a linked list?
|
|
|
|
|
#ifndef __TREE__TEMPLATE__LISTNODE__H__
#define __TREE__TEMPLATE__LISTNODE__H__
#pragma once
template< class T, typename K>
class CListNode
{
public:
K m_key;
size_t len;
T m_Node ;
CListNode *m_pNext ;
public:
CListNode(void);
CListNode(T & obj, K &key);
~CListNode(void);
};
template <typename typename="" k="">
CListNode<t,k>::CListNode() {
m_pNext = NULL ;
}
template <typename typename="" k="">
CListNode<t,k>::~CListNode() {
}
template <typename typename="" k="">
CListNode<t,k>::CListNode(T &obj, K &key) {
m_key = key;
m_Node = obj ;
m_pNext = NULL ;
len = 0;
}
#endif
#include "listnode.h"
/******************************************************************************
-------------------------------------------------------------------------------
If ihis file works as expected, it is created
by Prateek Kumar Dubey (dubeyprateek@gamil.com),
otherwise, I dont know who has written this !
-------------------------------------------------------------------------------
_______________________________________________________________________________
Discription
_______________________________________________________________________________
Filename :: LinkList.h
Supporting Files ::
1 - ListNode.h
Used By::
Tree.h
Purpose ::
This header file declares and defines a Link List template
class CLinkList. using this template loink list of any object
or of basic data type can be created.
Example ::
CLinkList<int> objCLinkListInt ; //creating an instance of class
CLinkList<float> objCLinkListFloat ;
CLinkList<myclass> objCLinkListMyClass ;
Now use various methods of CTree for further processings.
Methods ::
Public ::
1 - bool AddToFirst(T &);
2 - bool AddToLast(T &);
3 - bool DeleteFirst();
4 - bool DeleteLast();
5 - bool GetNode(T &, CListNode<t> **) ;
Member Variables ::
private ::
1 - CListNode<t> *m_pNode ;
Pointer used in varoius funtions for various
operations, no specific purpose.
2 - CListNode<t> *m_pHead ;
Pointer to the first node of link list.
3 - CListNode<t> *m_pTail ;
Pointer to the last node of link list.
4 - int m_TotelElements ;
Totel number of elements in the link list.
******************************************************************************/
#ifndef __TREE__TEMPLATE__LINKLIST__H__
#define __TREE__TEMPLATE__LINKLIST__H__
#pragma once
template <class typename="" k="">
class CLinkList
{
CListNode<t,k> *m_pNode ;
CListNode<t,k> *m_pHead ;
CListNode<t,k> *m_pTail ;
int m_TotelElements ;
public:
CLinkList(void);
~CLinkList(void);
bool AddToFirst(T &, K&);
bool AddToLast(T &, K&);
bool DeleteFirst();
bool DeleteLast();
bool GetNode(T &, K&, CListNode<t,k> **) ;
bool DeleteANode(K&);
bool Insert(T &obj, K &key, int pos );
};
/******************************************************************************
Method Name:: CLinkList (Constutor)
Parameters:: None
Return:: None
Purpose:: Constructs CLinkList objects.
******************************************************************************/
template <typename typename="" k="">
CLinkList<t,k>::CLinkList() {
m_pNode = NULL ;
m_pHead = NULL ;
m_pTail = NULL ;
m_TotelElements = 0;
}
/******************************************************************************
Method Name:: ~CLinkList (Distructor)
Parameters:: None
Return:: None
Purpose:: Distructs CLinkList objects.
******************************************************************************/
template <typename typename="" k="">
CLinkList<t,k>::~CLinkList() {
if(m_pHead) {
while(m_pHead) {
m_pNode = m_pHead ;
m_pHead = m_pHead->m_pNext ;
if (wcslen(m_pNode->m_key) != 0)
delete m_pNode->m_key;
delete m_pNode ;
m_pNode = NULL ;
--m_TotelElements ;
}
}
m_pHead = NULL ;
m_pTail = NULL ;
m_TotelElements = 0;
}
/******************************************************************************
Method Name:: AddToFirst
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Adds the node at the first position in the link list.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,>::AddToFirst(T &obj, K &key) {
int len;
CListNode<t,> *pNode = new CListNode<t,k> ;
if(!pNode) {
return false ;
}
pNode->len = wcslen(key);
pNode->m_key = new WCHAR [(pNode->len)+1];
if(!pNode->m_key) {
return false ;
}
wcscpy_s(pNode->m_key,(pNode->len)+1,key);
pNode->m_key = key;
pNode->m_Node = obj ;
if(0 == m_TotelElements ) {
pNode->m_pNext = NULL ;
m_pHead = pNode ;
m_pTail = pNode ;
pNode->m_pNext = NULL ;
m_TotelElements =1 ;
return true ;
}
pNode->m_pNext = m_pHead->m_pNext ;
m_pHead = pNode ;
++m_TotelElements ;
return true ;
}
/******************************************************************************
Method Name:: AddToFirst
Parameters::
1- [IN] T & obj
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Adds the node at the last position in the link list.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::AddToLast(T &obj, K &key) {
CListNode<t,k> *pNode = new CListNode<t,k> ;
if(!pNode) {
return false ;
}
pNode->len = wcslen(key);
pNode->m_key = new WCHAR [(pNode->len)+1];
if(!pNode->m_key) {
return false ;
}
wcscpy_s(pNode->m_key,(pNode->len)+1,key);
pNode->m_Node = obj ;
if(0 == m_TotelElements ) {
pNode->m_pNext = NULL ;
m_pHead = pNode ;
m_pTail = pNode ;
m_TotelElements =1 ;
return true ;
}
pNode->m_pNext = NULL ;
m_pTail->m_pNext = pNode ;
m_pTail = pNode ;
++m_TotelElements ;
return true ;
}
/******************************************************************************
Method Name:: DeleteFirst
Parameters:: None
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Deletes the node at the first position in the link list.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::DeleteFirst() {
if(0 == m_TotelElements ) {
return false ;
}
m_pNode = m_pHead ;
m_pHead = m_pHead->m_pNext ;
if (m_pNode->len)
delete m_pNode->m_key;
delete m_pNode ;
--m_TotelElements ;
return true ;
}
/******************************************************************************
Method Name:: DeleteLast
Parameters:: None
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Deletes the node at the last position in the link list.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::DeleteLast() {
if(0 == m_TotelElements ) {
return false ;
}
m_pNode = m_pHead ;
while(m_pNode->m_pNext != m_pTail) {
m_pNode = m_pNode->m_pNext ;
}
if (m_pTail->len)
delete m_pTail->m_key;
delete m_pTail ;
m_pTail = m_pNode ;
--m_TotelElements ;
return true ;
}
/******************************************************************************
Method Name:: GetNode
Parameters::
1- [IN] T & obj
2- [OUT] CListNode<t> **pOut
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches a node in the link list. OUT parameter holds the
address of the searched node, and NULL if node is not found
in the linklist.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::GetNode(T &obj,K &key, CListNode<t,k> **pNode) {
int len,len1;
if(0 == m_TotelElements ) {
*pNode = NULL;
return false ;
}
m_pNode = m_pHead ;
len = wcslen(key);
if (len > 64){
*pNode = NULL;
return false;
}
len1 = max(len,m_pNode->len);
while(/*m_pNode->m_Node != obj*/wcsncmp(m_pNode->m_key,key,len1)!=0) {
m_pNode = m_pNode->m_pNext ;
if (!m_pNone)
break;
len1 = max(len,m_pNode->len);
}
*pNode = m_pNode ;
return true ;
}
/******************************************************************************
Method Name:: DeleteANode
Parameters::
1- [IN] K & key
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Searches a node in the link list. OUT parameter holds the
address of the searched node, and NULL if node is not found
in the linklist.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::DeleteANode(K &key) {
size_t len,len1;
CListNode<t,k> *prvNode;
if(0 == m_TotelElements ) {
return false ;
}
prvNode = m_pNode = m_pHead ;
len = wcslen(key);
if (len > 64)
return false;
len1 = max(len,m_pNode->len);
while(wcsncmp(m_pNode->m_key,key,len1)!=0) {
prvNode = m_pNode;
m_pNode = m_pNode->m_pNext ;
if (!m_pNode)
break;
len1 = max(len,m_pNode->len);
}
if (!m_pNode)
return false;
if (m_pHead == m_pNode)//deleteing head
{
--m_TotelElements;
m_pHead = m_pHead->m_pNext;
if(m_pNode->len)
delete m_pNode->m_key;
delete m_pNode;
}
else if (m_pNode == m_pTail){//remove tail
--m_TotelElements;
m_pTail = prvNode;
prvNode->m_pNext = NULL;
if(m_pNode->len)
delete m_pNode->m_key;
delete m_pNode;
}
else {//remove middle one
--m_TotelElements;
prvNode->m_pNext = m_pNode->m_pNext;
if(m_pNode->len)
delete m_pNode->m_key;
delete m_pNode;
}
return true ;
}
/******************************************************************************
Method Name:: Insert
Parameters::
1- [IN] T & obj
[IN] K & key
[IN] int pos
Return:: bool
true - On Success.
false - On Failure.
Purpose::
Adds the node at the last position in the link list.
******************************************************************************/
template <typename typename="" k="">
bool CLinkList<t,k>::Insert(T &obj, K &key, int pos ) {
int indx = 0;
CListNode<t,k> *prvNode;
if (pos == 0){
return AddToFirst(obj, key);
}
if (m_TotelElements >= pos){
return AddToLast(obj, key);
}
CListNode<t,k> *pNode = new CListNode<t,k> ;
if(!pNode) {
return false ;
}
pNode->len = wcslen(key);
pNode->m_key = new WCHAR [(pNode->len)+1];
if(!pNode->m_key) {
return false ;
}
wcscpy_s(pNode->m_key,(pNode->len)+1,key);
pNode->m_Node = obj ;
m_pNode = m_pHead ;
for (int i=1; i<= pos; i++){
prvNode = m_pNode;
m_pNode = m_pNode->m_pNext;
if (!m_pNode){
delete pNode->m_key;
delete pNode;
return false;
}
}
pNode->m_pNext = prvNode->m_pNext;
prvNode->m_pNext = pNode;
++m_TotelElements ;
return true ;
}
#endif
|
|
|
|
|
...*THIS* is a nice written one : http://www.codeproject.com/cpp/BinaryTree.asp
What's your implementation have to offer HatemMostafa's doesn't ? You article isn't even better documented, illustrated, explained...
If you cannot follow the easy CP's article guidelines, please refrain yourself from posting. Or scrub the mess up BEFORE submission, don't plan the future on an article update.
Kochise
EDIT : Since you edited your article, it's kindly better. But there is room for improvements... Thanks anyway, all of this is interresting stuff.
In Code we trust !
|
|
|
|