dsimpl.h

用列表实现的队列和栈的算法

#ifndef _BASIC_DATA_STRUCTURE_TYPE_IMPLEMENTATION_SPIRIT_
#define _BASIC_DATA_STRUCTURE_TYPE_IMPLEMENTATION_SPIRIT_
#include "dstype.h"

//define the error number range for every implementation

#define SDS_ERROR_BASE_SINGLE_LIST_LOW_1 SDS_ERROR_BASE+1 //for single list impl, 50 private error number
#define SDS_ERROR_BASE_SINGLE_LIST_HIGH_1 SDS_ERROR_BASE_SINGLE_LIST_LOW_1+50

#define SDS_ERROR_BASE_QUEUE_LOW_2 SDS_ERROR_BASE_SINGLE_LIST_HIGH_1+1 //for queue impl, 50 private error number
#define SDS_ERROR_BASE_QUEUE_HIGH_2 SDS_ERROR_BASE_QUEUE_LOW_2+50

#define SDS_ERROR_BASE_STACK_LOW_3 SDS_ERROR_BASE_QUEUE_HIGH_2+1 //for stack impl, 50 private error number
#define SDS_ERROR_BASE_STACK_HIGH_3 SDS_ERROR_BASE_STACK_LOW_3+50




//CLOCKS_PER_SEC

#if !(defined(_PROGRAMMING_WITH_C_PLUS_PLUS_) && defined(_PROGRAMMING_WITH_C_))// cannot defined both at the same time
 
#if defined(_PROGRAMMING_WITH_C_PLUS_PLUS_)    // if C++ Language


/////////////////////////////////////////////////////////////////
// one single linked list implementation written by Spirit
/////////////////////////////////////////////////////////////////
class sdstd_single_list_impl:public sdstd_single_list
{
public:
	sdstd_single_list_impl(){
		listHead=NULL;
		listTail=NULL;
		listCurrent=NULL;
	}
    virtual ~sdstd_single_list_impl()
	{
		destroyList();
	}
   
virtual SDS_RESULT addHead(pssle inData); // add an element before list head
virtual SDS_RESULT addTail(pssle inData); // add an element after list tail

virtual SDS_RESULT getHead(pssle *pElement)const; // get the head element and store it to pElement buffer
virtual SDS_RESULT getTail(pssle *pElement)const; // get the tail element and store it to pElement buffer


virtual SDS_RESULT insertElement(pssle pUsher,pssle inData); // add an element after the pUsher
virtual SDS_RESULT deleteElement(pssle pUsher,pssle pElement); // deleting the element


virtual SDS_RESULT traverseInit(); //Initialization for list traverse
virtual SDS_BOOL   hasNext()const;      // detecting whether list contains more element
virtual SDS_RESULT getNext(pssle *pElement); // get the element and store it to pElement buffer

virtual SDS_BOOL   isEmpty() const;

virtual SDS_RESULT sortList(SDS_KEYTYPE (*getSortKey)(pssle pListElement),SDS_SORTMODE sortMode); // sorting this list with the specifed mode <key-up or key-down>
virtual SDS_RESULT traverseThrough(SDS_RESULT (*elementProcessor)(pssle pListElement,sdstd_param inParam,sdstd_param outParam),sdstd_param inParam=(sdstd_param)0,sdstd_param outParam=(sdstd_param)0); //traverse the list with specifed processor

virtual SDS_RESULT reverseList(); // reverse the list 
virtual SDS_STRING (*getErrorExpositor())(SDS_RESULT errorNo);

virtual SDS_RESULT setSequence(SDS_SORTMODE sortMode); //Set the list to obey a mode of sequence

virtual SDS_RESULT copyList(const sdstd_single_list * pSource); // copy thd source list to this list


static  SDS_STRING errorDetail(SDS_RESULT errorNo);//get the error detail description according to error number
static  SDS_STRING errDescription[SDS_ERROR_BASE_SINGLE_LIST_HIGH_1-SDS_ERROR_BASE_SINGLE_LIST_LOW_1+1];//error description buffer



protected:

private:
	pssle listHead,listTail,listCurrent; // list head node pointer,list tail node pointer and list current not pointer 
    SDS_RESULT destroyList();
	SDS_RESULT deleteElements(pssle &pElement); //delete all elements after this pElement,including itself, 
    SDS_RESULT deleteElements_1(pssle &pElement); //delete all elements after this pElement,including itself,recursion 
    SDS_RESULT exchangeNeighbor(pssle pPrev); // exchange two neighbor node after the prev node.
	                                          // as the below figure, Node A & Node B got changed

//    -----    -----    -----
//... |   |--->|   |--->|   |  ....
//    -----    -----    -----
//    pPrev    Node A   Node B



};

SDS_STRING sdstd_single_list_impl::errDescription[SDS_ERROR_BASE_SINGLE_LIST_HIGH_1-SDS_ERROR_BASE_SINGLE_LIST_LOW_1+1]={ // define the error detail readable info
"Processing completed successfully!",
"Fatal error!",
"Other error!",
};

SDS_RESULT sdstd_single_list_impl::setSequence(SDS_SORTMODE sortMode)
{

return SDS_OK;
}


 SDS_STRING sdstd_single_list_impl::errorDetail(SDS_RESULT errorNo)
 {
     if(errorNo>SDS_ERROR_BASE_SINGLE_LIST_HIGH_1) //if error number not in the range of this error expositor
	    return NULL;

	 return (errorNo<=SDS_ERROR_BASE?sdstd_single_list::errorDetail(errorNo):errDescription[errorNo-SDS_ERROR_BASE-1]);
 
	 // SDS_ERROR_BASE_SINGLE_LIST_HIGH_1-SDS_ERROR_BASE_SINGLE_LIST_LOW_1+1
	 
	 //
 
 }


 SDS_RESULT sdstd_single_list_impl::copyList(const sdstd_single_list *pSource)
 {

	 if(NULL==pSource)//if source param is NULL
		 return SDS_ERROR_INPUT_PARAM_NULL;

	 if(this==pSource) //if copy it self,just do nothing and return
		 return SDS_OK;

	 const sdstd_single_list_impl *pTmpSource=(sdstd_single_list_impl *) pSource; // the pSource must be a pointer pointing to a sdstd_single_list_impl object
	
	 if(isEmpty()!=SDS_TRUE) // if this list not null, destroy it at first!
		 this->destroyList();
	 
	  pssle pTmp,pTar=NULL,pTarPrev=NULL;

	  pTmpSource->getHead(&pTmp);
      
	  if(NULL==pTmp) //if no element is source list
	  {
	   listHead=listTail=NULL; //set this list null,too!
	   return SDS_OK;
	  }

	  
	  pTar=new sdstd_single_list_element;
      sdstd_single_list::copyElement(pTar,pTmp);      

	  listHead=pTar;// store the list's head
      
	  pTarPrev=pTar; //store the new element as previous element
   
	  pTmp=pTmp->next;//to next element

	  while(1)
	  {
	    if(NULL==pTmp) // if get the end of the source list
		{
		 listTail=pTarPrev; //store the list Tail pointer
         listTail->next=NULL;
	     break;
		}
      
	  pTar=new sdstd_single_list_element; //creat new element
      sdstd_single_list::copyElement(pTar,pTmp);//copy source element to target
      
	  pTarPrev->next=pTar;//link the new element to new list
	  pTarPrev=pTar;//store the new element as previous element
	  pTmp=pTmp->next;
	  }

	return SDS_OK;

 }
 

 SDS_RESULT sdstd_single_list_impl::deleteElements_1(pssle &pElement)
 {  
    SDS_RESULT errorNo=SDS_OK;

	if(NULL!=pElement)
	{
	errorNo=deleteElements_1(pElement->next);
	delete pElement;
	pElement=NULL;
	}

    return errorNo;
}


 SDS_RESULT sdstd_single_list_impl::deleteElements(pssle &pElement)
{  
    pssle pTemp1=pElement,pTemp2=NULL; // defining 2 temp pointer
	while(pTemp1!=NULL)
	{
	pTemp2=pTemp1->next;
    delete pTemp1;
	pTemp1=pTemp2;
    }

    pElement=NULL;
    return SDS_OK;
}


 SDS_RESULT sdstd_single_list_impl::destroyList()
{
	 SDS_RESULT errNo=this->deleteElements(listHead);
	if(SDS_OK==errNo)
	{listTail=NULL;}//initialize the listTail=NULL
	return errNo;	
}


 SDS_RESULT sdstd_single_list_impl::addHead(pssle inData) // add an element before list head
 {
  if(NULL==listHead) //if list is null
  {
  listTail=listHead=inData;
  inData->next=NULL;
  }
  else // if list not null
  {
  inData->next=listHead;
  listHead=inData;
  }

 return SDS_OK;
 }
 
 SDS_RESULT sdstd_single_list_impl::addTail(pssle inData)// add an element after list tail
 {
  if(NULL==listHead) //if list is null
  {
   listTail=listHead=inData;
   inData->next=NULL;
  }
  else // if list not null
  {
  listTail->next=inData;
  listTail=inData;
  inData->next=NULL;
  }
 return SDS_OK;
 }
 
 SDS_RESULT sdstd_single_list_impl::insertElement(pssle pUsher,pssle inData) // add an element after the pUsher
  {
 
	 if(NULL==pUsher)//if add at the begin
		 return addHead(inData);
	 if(NULL==pUsher->next) // if add at tail
         return addTail(inData);

	 inData->next=pUsher->next; // if normal situation
	 pUsher->next=inData;
	 return SDS_OK;
 }
 

 SDS_RESULT sdstd_single_list_impl::getHead(pssle *pElement)const  // get the head element and store it to pElement buffer
 {
	 *pElement=listHead;
	 return SDS_OK;
 }
 SDS_RESULT sdstd_single_list_impl::getTail(pssle *pElement)const  // get the tail element and store it to pElement buffer
{
     *pElement=listTail;
	 return SDS_OK;
}
	 
 SDS_RESULT sdstd_single_list_impl::deleteElement(pssle pUsher,pssle pElement) // deleting the element
 {
	 if(NULL==pElement) // if no element exist in this list
		 return SDS_ERROR_DELETING_NULL_ELEMENT;

 
	 if(NULL==pUsher) // if delete head
	 {
	   if(pElement!=listHead) // if not try to deleting the first head
		   return SDS_ERROR_NOT_DELETE_LIST_HEAD_WHEN_USHER_NULL;

       listHead=pElement->next;
	   if(NULL==pElement->next)//if only one element
	   {
		 listTail=NULL;
	   }
      else // if not only one element, wipe the linked pointer to list
		 pElement->next=NULL;
	 
     return SDS_OK;
	 }
  
	 if(pUsher->next!=pElement) // if pElement not the subsquence of the pUsher
       return SDS_ERROR_WRONG_USHER_SUBSEQUENCE;

     if(NULL==pElement->next) // if delete tail
	 {
   
	  listTail=pUsher;
	  if(NULL==listTail) // if only one element
		 listHead=NULL;
	  else
	     listTail->next=NULL; // if not only element, make the tail element's next pointer pointing to NULL 

      return SDS_OK;
	 }

    pUsher->next=pElement->next;// if normal situation
    pElement->next=NULL;

    return SDS_OK;
 }

 SDS_RESULT sdstd_single_list_impl::traverseInit() //Initialization for list traverse
  {
 listCurrent=listHead;
 return SDS_OK;
 }
 
 SDS_BOOL   sdstd_single_list_impl::hasNext() const   // detecting whether list contains more element
  {
 return NULL!=listCurrent;
 }
 
 
 SDS_RESULT sdstd_single_list_impl::getNext(pssle *pElement)// get the element and store it to pElement buffer
 {
 (*pElement)=listCurrent;
 listCurrent=listCurrent->next;

 return SDS_OK;
 }
 
 SDS_BOOL   sdstd_single_list_impl::isEmpty() const
 {
 
 return listHead==NULL;
 }
 
 SDS_RESULT sdstd_single_list_impl::sortList(SDS_KEYTYPE (*getSortKey)(pssle pListElement),SDS_SORTMODE sortMode)// sorting this list with the specifed mode <key-up or key-down>
 {

   if(SDS_TRUE==this->isEmpty()) //if list is null,no element
     return SDS_OK;
  
   if(NULL==getSortKey)//if the getkey function pointer is null,return null
     return SDS_ERROR_INPUT_PARAM_NULL;
   
   if(listHead==listTail) //if only one element
     return SDS_OK;
   // clock_t theTimeStart=::clock();
   //SDS_RESULT errorNo=SDS_OK;
   SDS_BOOL isSortOk=SDS_TRUE;
   pssle pF=listHead,pFPrev=NULL,pB=listTail,pBPrev=NULL; // front point and back point 
  
  
  //pssle pF=listHead,pFPrev=NULL,pB=pF->next,pBPrev=pF; // front point and back point 
  
  //sdstd_single_list_element eleTemp;


 switch(sortMode)
  {
   case SDS_KEYUP_SORT:
 
   while(pB!=listHead)
   {
     
	 while(1)
	 {
	 
       if(getSortKey(pF)>getSortKey(pF->next))
	   {  
		   isSortOk=SDS_FALSE;
   	       if(pF->next==pB)//get the Pointer pB to right position
		       pB=pF;
		   
		
		   pF=pF->next;  //exchange the position of the two element
		   
		   exchangeNeighbor(pFPrev);
		   	    
	   }

	   if(pF->next==pB)
	   {
	        pBPrev=pF;
            break;
	   }
	
	   pFPrev=pF; 
 	   pF=pF->next; 
 	 }
	
	 if(SDS_TRUE==isSortOk)
		 break;
    
	isSortOk=SDS_TRUE;
    
	pF=listHead;
	pFPrev=NULL;
	pB=pBPrev;
 }

  /*
	  while(1)
	   {
		   if(NULL==pF->next) //get to the list end
			   break;
          // SDS_BOOL isKeyUp=SDS_TRUE;
	       while(1)
		   {
			   if(NULL==pB)
				   break;

			   if(getSortKey(pF)>getSortKey(pB))
			   { 

				//   isKeyUp=SDS_FALSE;