linked3.txt

链表的bubble

//     h empty nodes


    CList::CList(int nNumberOfNodes){
    	
    	m_nCount = 0;
    	m_pHead = NULL;
    	
    	for (int nIndex = 0; nIndex < nNumberOfNodes ; nIndex++)
    		this->InsertAtTail(0);
}
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// create a list of randomly generated n
//     odes if szFlag = 'r' || 'R'


    CList::CList(const char *szOption, int nListLength){
    	
    	this->m_nCount = 0;
    	this->m_pHead = NULL;
    	


        	if (strcmp(szOption, "r") || strcmp(szOption, "R")){
        		//MessageBox(NULL,"Random nodes comming up!", "", MB_OK);
        		for (int nIndex = 0; nIndex < nListLength; nIndex++)
        			this->InsertAtTail((int)rand() % 100);
        		
        	}
    }
    ////////////////////////////////////////
    //     ////////////////////////////////////////
    /////////////////
    // class destructor


        CList::~CList(void){
        	// do nothing
    }
    ////////////////////////////////////////
    //     ////////////////////////////////////////
    /////////////////
    // function to return the current count


        int CList::getCount(void){
        CNode *pCurrent = this->m_pHead;
        	
        	int nCount = 0;


            	while (pCurrent != NULL){
            		pCurrent = pCurrent->m_pLink; 
            		nCount++;
            	}
            	return nCount;
        }
        ////////////////////////////////////////
        //     ////////////////////////////////////////
        /////////////////
        // function to return the head


            CNode *CList::getHead(void){
            	return this->m_pHead;
        }
        ////////////////////////////////////////
        //     ////////////////////////////////////////
        /////////////////
        // function to insert a new node into th
        //     e list with the given data


            void CList::InsertAtHead(int nValue){
            CNode *pNew = new CNode(nValue);
            	


                	if (this->m_pHead == NULL){
                		this->m_pHead = pNew;
                	}


                    	else{
                    		pNew->m_pLink = this->m_pHead;
                    		this->m_pHead = pNew;
                    	}
                }
                ////////////////////////////////////////
                //     ////////////////////////////////////////
                /////////////////
                // function to insert a node at the tail
                //     from the given value


                    void CList::InsertAtTail(int nValue){
                    CNode *pNode = new CNode(nValue);
                    	
                    	// if it is empty


                        	if (this->m_pHead == NULL){
                        		this->m_pHead = pNode;
                        	}


                            	else{
                            		CNode *pCurrent = this->m_pHead; 
                            		
                            		// if there is only one node


                                		if (pCurrent->m_pLink == NULL){
                                			pCurrent->m_pLink = pNode;
                                		}


                                    		else{
                                    			// otherwise we assume it to contain more than 1 node


                                        			while(pCurrent->m_pLink != NULL){
                                        				// keep moving unless we know the link is empty
                                        				if (pCurrent->m_pLink != NULL)
                                        					pCurrent = pCurrent->m_pLink;
                                        			}
                                        			
                                        			// set the link to the new node
                                        			pCurrent->m_pLink = pNode;
                                        		}
                                        	}
                                        	// add 1 to the count
                                        	m_nCount++;
                                    }
                                    ////////////////////////////////////////
                                    //     ////////////////////////////////////////
                                    /////////////////
                                    // bubble sort


                                        void CList::BubbleSort(void){
                                        int nTemp;
                                        	
                                        	// start at the first and sequentially traverse the list
                                        	// each pass starting one node later


                                            	for (CNode *pFirst = this->m_pHead; pFirst; pFirst = pFirst->m_pLink){
                                            		


                                                		for (CNode *pSecond = pFirst->m_pLink; pSecond; pSecond = pSecond->m_pLink){
                                                			
                                                			// if we find a node out of place with the following node


                                                    			if (pFirst->m_nValue > pSecond->m_nValue){
                                                    				// swap em... this will sort increasing values
                                                    				nTemp = pFirst->m_nValue;
                                                    				pFirst->m_nValue = pSecond->m_nValue;
                                                    				pSecond->m_nValue = nTemp;
                                                    			}
                                                    		}
                                                    	}
                                                }
                                                ////////////////////////////////////////
                                                //     ////////////////////////////////////////
                                                /////////////////
                                                // selection sort


                                                    void CList::SelectionSort(void){
                                                    CNode *pFirst = this->m_pHead;
                                                    CNode *pSecond = this->m_pHead;
                                                    CNode *pSmallest = this->m_pHead;
                                                    int nSmallest, nSwap;
                                                    	
                                                    	// set the smallest value to the first element...
                                                    	// since it's the first one we've seen, it has to be the smallest
                                                    	nSmallest = this->m_pHead->m_nValue;
                                                    	
                                                    	// start passing and comparing


                                                        	while (pSecond->m_pLink != NULL){
                                                        		// pass to compare two nodes to find the greatest value


                                                            		while (pFirst->m_pLink != NULL){


                                                                			if (nSmallest > pFirst->m_pLink->m_nValue){
                                                                				nSmallest = pFirst->m_pLink->m_nValue;
                                                                				pSmallest = pFirst->m_pLink;
                                                                			}
                                                                			// continue traversing the list
                                                                			pFirst = pFirst->m_pLink;
                                                                		}
                                                                		// swap the values between the current and the smallest
                                                                		nSwap = pSecond->m_nValue;
                                                                		pSecond->m_nValue = pSmallest->m_nValue;
                                                                		pSmallest->m_nValue = nSwap;
                                                                		
                                                                		// reinitialize the starting point for the next pass