dsimpl.h

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

                   if(pF==pBPrev) //if two element are neighbor
				   {
				   this->insertElement(pBPrev,&eleTemp);
				   pBPrev=pBPrev->next;
				   
				   this->deleteElement(pFPrev,pF); // exchange the two element
				   this->deleteElement(pBPrev,pB);
				   this->insertElement(pFPrev,pB);
			       this->insertElement(pBPrev,pF);
				   
				   pssle pTemp=pF; //then exchange the two pointer
				   pF=pB;
				   pB=pTemp;
			       
				   pBPrev=pF;//delete the temp element
                   this->deleteElement(pBPrev,&eleTemp);
				   

				   }
                   else
				   {
				   this->deleteElement(pFPrev,pF); // exchange the two element
				   this->deleteElement(pBPrev,pB);
				   this->insertElement(pFPrev,pB);
			       this->insertElement(pBPrev,pF);
				   pssle pTemp=pF; //then exchange the two pointer
				   pF=pB;
				   pB=pTemp;
			   
				   }
			   }
		 
		      
			  pBPrev=pB;
			  pB=pBPrev->next;
		 
		   }

    //if(SDS_TRUE==isKeyUp) // if the list already key up,
     //   return SDS_OK;


	   pFPrev=pF; 
	   pF=pFPrev->next;
	   pBPrev=pF;
	   pB=pBPrev->next;
	   
   }
	   
	   
*/


	  
	break;
  
 

 case SDS_KEYDOWN_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;
 }





	   
	   
	    break;
   default:
	   return SDS_ERROR_WRONG_SORT_MODE;
   }



//clock_t theTime=::clock()-theTimeStart;
//printf("\n%4.2f",(float)theTime/CLOCKS_PER_SEC);


 return SDS_OK;
 } 
	 

 SDS_RESULT sdstd_single_list_impl::traverseThrough(SDS_RESULT (*elementProcessor)(pssle pListElement,sdstd_param inParam,sdstd_param outParam),sdstd_param inParam,sdstd_param outParam)//traverse the list with specifed processor
 {
    pssle pTmp=NULL;
	SDS_RESULT resultTmp=SDS_OK;
	
	traverseInit();
	while(hasNext())
    { 
		getNext(&pTmp);
	    resultTmp=elementProcessor(pTmp,inParam,outParam);
   	    if(SDS_OK!=resultTmp)
	      break; //if error occured,break the loop!
	}
 
	return resultTmp;
 }


 SDS_RESULT sdstd_single_list_impl::reverseList() // reverse the list 
 {
 pssle pPrev=listHead,pMid=NULL,pNext=NULL;

	if(NULL==pPrev)// if list is null, no element exist
		return SDS_OK;
   
	pMid=pPrev->next;
   if(NULL==pMid) // if only one element
	   return SDS_OK;
  
   pNext=pMid->next;// processor the first two element
  
      pMid->next=pPrev;
	  pPrev->next=NULL;
	   
   

  pPrev=pMid;
  pMid=pNext;

 while(1)
  {
	
	// if(NULL==pPrev)// if list is null, no element exist//never match,beacase pPrev=pMid
	//	break;

     if(NULL==pMid) // if touch the end of the list!
	    break;

     pNext=pMid->next;//store the element's next
     pMid->next=pPrev;//make the element's next pointer pointing to the previous element
     
	 pPrev=pMid;// the work pointer move to next element of this list
	 pMid=pNext;
  }
 
  //exchange the listhead and listtail pointer
 pMid=listHead; 
 listHead=listTail;
 listTail=pMid;
 
 return SDS_OK;
 }

 SDS_STRING (* sdstd_single_list_impl::getErrorExpositor())(SDS_RESULT errorNo)
 {
 return sdstd_single_list_impl::errorDetail;
 }


SDS_RESULT sdstd_single_list_impl::exchangeNeighbor(pssle pPrev)
{

//	if(SDS_TRUE==isEmpty()||listHead==listTail) // if list is null
//		return SDS_OK;
	pssle pTmp;
    
	if(NULL==pPrev) // if exchange the first two 
    {
	if(NULL==listHead) return SDS_FAULT; // if list null
	if(NULL==listHead->next) return SDS_FAULT;// if only one node
	
	pTmp=listHead->next;
    listHead->next=pTmp->next;
	pTmp->next=listHead;
    if(listTail==pTmp) //if noly two nodes
		listTail=listHead;

	listHead=pTmp;

    return SDS_OK;
	}
   	
	if(NULL==pPrev->next)//if no next element
       return SDS_FAULT;
	if(NULL==pPrev->next->next) //if no next next element
		return SDS_FAULT;
        
	pTmp=pPrev->next;
	pPrev->next=pTmp->next;
	pTmp->next=pPrev->next->next;
    pPrev->next->next=pTmp;
	if(pPrev->next==listTail) //if list tail be chagned
	listTail=pTmp;


return SDS_OK;
}

/////////////////////////////////////////////////////////////////
// one queue implementation written by Spirit
/////////////////////////////////////////////////////////////////
class sdstd_queue_impl:public sdstd_queue // Abstract interface of queue
{
public:
virtual ~sdstd_queue_impl(){
if(NULL!=innerList)
  delete innerList;
}

sdstd_queue_impl()
{
	innerList=new sdstd_single_list_impl;
	queueSize=-1; //size is not limited
	currentSize=0;
}

virtual SDS_RESULT setSize(int queueSize)  // set the size of the queue
{
if(queueSize<=0) return SDS_ERROR_INVALID_PARAM;

this->queueSize=queueSize;

return SDS_OK;
}


virtual SDS_RESULT inQueue(sdstd_data inData)  // get data into queue
{
  if(queueSize>0)
	if(currentSize>=queueSize) //if touch the limited size
	  return SDS_ERROR_BUFFER_FULL;

 SDS_RESULT errorNo=innerList->addTail(sdstd_single_list::createElement(inData));
 if(SDS_OK==errorNo) currentSize++; //increase the currentSize with one
 return errorNo; 
}


virtual SDS_RESULT outQueue(sdstd_data *outData)  // get data out of queue
{
if(SDS_TRUE==isEmpty()) return SDS_ERROR_REQUIREMENT_OBJECT_NULL; // if the list is null
pssle pOuter=NULL;
innerList->getHead(&pOuter);
*outData=pOuter->data;
SDS_RESULT errorNo=innerList->deleteElement(NULL,pOuter);//delete the list head
if(SDS_OK==errorNo)// if successful
{
	delete pOuter;//delete element node
    currentSize--;
}
return errorNo;
}

virtual SDS_RESULT peekQueue(sdstd_data *outData)  // peek the data which will be outQueue next time,but not get the data out of the queue
{
if(SDS_TRUE==isEmpty()) return SDS_ERROR_REQUIREMENT_OBJECT_NULL; // if the list is null
pssle pOuter=NULL;
innerList->getHead(&pOuter);
*outData=pOuter->data;
return SDS_OK;
}


virtual SDS_BOOL   isEmpty() const // test whether the queue is null or not
{
return innerList->isEmpty();
}


private:
	sdstd_single_list *innerList;
    int queueSize;
	int currentSize;

};



/////////////////////////////////////////////////////////////////
// one stack implementation written by Spirit
/////////////////////////////////////////////////////////////////
class sdstd_stack_impl:public sdstd_stack // Abstract interface of queue
{
public:
virtual ~sdstd_stack_impl(){
//just for dynamic deleting object and avoid memory leak
	if(NULL!=innerList)
      delete innerList;
}

sdstd_stack_impl()
{
  innerList=new sdstd_single_list_impl;
  stackSize=-1; //size is not limited
  currentSize=0;
}

virtual SDS_RESULT push(sdstd_data inData) // push data to stack
{
 
	if(stackSize>0)
 	 if(currentSize>=stackSize) //if touch the limited size
	   return SDS_ERROR_BUFFER_FULL;

 SDS_RESULT errorNo=innerList->addHead(sdstd_single_list::createElement(inData));
 if(SDS_OK==errorNo) currentSize++; //increase the currentSize with one
 return errorNo; 
}



virtual SDS_RESULT pop(sdstd_data *outData)  //pop the data
{
if(SDS_TRUE==isEmpty()) return SDS_ERROR_REQUIREMENT_OBJECT_NULL; // if the list is null
pssle pOuter=NULL;
innerList->getHead(&pOuter);
*outData=pOuter->data;
SDS_RESULT errorNo=innerList->deleteElement(NULL,pOuter);//delete the list head
if(SDS_OK==errorNo)// if successful
{
	delete pOuter;//delete element node
    currentSize--;
}
return errorNo;

}


virtual SDS_RESULT peek(sdstd_data *outData) // peek the data which will be pop next time,but not get the data out of the stack
{
if(SDS_TRUE==isEmpty()) return SDS_ERROR_REQUIREMENT_OBJECT_NULL; // if the list is null
pssle pOuter=NULL;
innerList->getHead(&pOuter);
*outData=pOuter->data;
return SDS_OK;

}


virtual SDS_BOOL   isEmpty() const// test whether the stack is null or not
{
return innerList->isEmpty();
}


virtual SDS_RESULT setSize(int stackSize) // set the size of the stack
{

	if(stackSize<=0) return SDS_ERROR_INVALID_PARAM;

    this->stackSize=stackSize;

    return SDS_OK;


}


private:
	sdstd_single_list *innerList;
	int stackSize;
	int currentSize;
};










#elif defined(_PROGRAMMING_WITH_C_)              // if C Language
     

     


#else                                            //if define nothing,error
        
//you do NOT define programming language // just for causing error!


#endif
 
#endif

#endif