linked3.txt

链表的bubble

                                                                		pFirst = pSecond = pSecond->m_pLink;
                                                                		nSmallest = pSecond->m_nValue;
                                                                		pSmallest = pSecond;
                                                                	}
                                                            }
                                                            ////////////////////////////////////////
                                                            //     ////////////////////////////////////////
                                                            /////////////////
                                                            // insertion sort


                                                                void CList::InsertSort(void){
                                                                CNode *pFirst, *pSecond;
                                                                int nSwap;
                                                                bool bSwapped;
                                                                	bSwapped = false;
                                                                		
                                                                	nSwap = 0;
                                                                	 
                                                                	pSecond = this->m_pHead->m_pLink;
                                                                	


                                                                    	for (int i = 0; i < this->m_nCount; i++){
                                                                    		


                                                                        		while(pSecond != NULL){
                                                                        			bSwapped = false;
                                                                        			pFirst = this->m_pHead;
                                                                        			


                                                                            			while((pFirst != pSecond) && (bSwapped==false)){


                                                                                				if (pFirst->m_nValue > pSecond->m_nValue){
                                                                                					nSwap = pFirst->m_nValue;
                                                                                					pFirst->m_nValue = pSecond->m_nValue;
                                                                                					pSecond->m_nValue = nSwap;
                                                                                					bSwapped = true;
                                                                                				}
                                                                                				pFirst = pFirst->m_pLink; 
                                                                                			}
                                                                                			


                                                                                    			if ((pFirst->m_nValue > pSecond->m_nValue) && (bSwapped == false)){
                                                                                    				nSwap = pFirst->m_nValue;
                                                                                    				pFirst->m_nValue = pSecond->m_nValue;
                                                                                    				pSecond->m_nValue = nSwap;
                                                                                    			}
                                                                                    			pSecond = pSecond->m_pLink;
                                                                                    		}
                                                                                    		pSecond = this->m_pHead->m_pLink; 
                                                                                    	}
                                                                                }
                                                                                ////////////////////////////////////////
                                                                                //     ////////////////////////////////////////
                                                                                /////////////////
                                                                                // function to display the current list 
                                                                                //     (ie [ x,x,x,x,x ])


                                                                                    void CList::DisplayList(void){
                                                                                    CNode *pCurrent = this->m_pHead;
                                                                                    	
                                                                                    	printf("Current List=[ ");
                                                                                    	


                                                                                        	for (pCurrent; pCurrent; pCurrent = pCurrent->m_pLink){


                                                                                            		if (pCurrent->m_pLink != NULL){
                                                                                            			printf("%i,",pCurrent->m_nValue);
                                                                                            		}


                                                                                                		else{
                                                                                                			printf("%i", pCurrent->m_nValue); 
                                                                                                		}
                                                                                                	}
                                                                                                	printf(" ]\n");
                                                                                            }


                                                                                                CNode *CList::getTail(void){
                                                                                                	
                                                                                                	for (CNode *pFirst = this->m_pHead; pFirst->m_pLink; pFirst = pFirst->m_pLink); 
                                                                                                	return pFirst;
                                                                                            }
                                                                                            ////////////////////////////////////////
                                                                                            //     ////////////////////////////////////////
                                                                                            /////////////////
                                                                                            ////////////////////////////////////////
                                                                                            //     ////////////////////////////////////////
                                                                                            /////////////////
                                                                                            // private test function definitions
                                                                                            ////////////////////////////////////////
                                                                                            //     ////////////////////////////////////////
                                                                                            /////////////////
                                                                                            ////////////////////////////////////////
                                                                                            //     ////////////////////////////////////////
                                                                                            /////////////////


                                                                                                void TestDefaultConstructor(void){
                                                                                                CList *pList = new CList;
                                                                                                	
                                                                                                	printf("Default constructor\nUsing 10 blank nodes\nInserting i from 1 to 10 generates...\n");
                                                                                                	for (int nIndex = 1; nIndex < 11; nIndex++)
                                                                                                		pList->InsertAtTail(nIndex); 
                                                                                                	
                                                                                                	pList->DisplayList();
                                                                                                	printf("\n\n");
                                                                                            }


                                                                                                void TestIntegerConstructor(int nNumNodes){
                                                                                                CList *pList = new CList(nNumNodes);
                                                                                                	
                                                                                                	printf("Integer constructor\nUsing %X blank nodes generates...\n");
                                                                                                	
                                                                                                	pList->DisplayList();
                                                                                                	printf("\n\n");
                                                                                            }


                                                                                                void TestRandomConstructor(const char *szOption, int nListLength){
                                                                                                CList *pList = new CList(szOption, nListLength);
                                                                                                	
                                                                                                	printf("Random construtor\nUsing %i randomly valued nodes generates...\n", nListLength);
                                                                                                	
                                                                                                	pList->DisplayList();
                                                                                                		
                                                                                                	printf("\n\n");
                                                                                            }


                                                                                                void TestSort(const char *szOption, int nListLength,int nSortOption){
                                                                                                CList *pList = new CList(szOption, nListLength);
                                                                                                	
                                                                                                	printf("Random construtor\nUsing %i randomly valued nodes generates...\n", nListLength);
                                                                                                	
                                                                                                	pList->DisplayList();
                                                                                                	


                                                                                                    	switch(nSortOption){
                                                                                                    		case 1:
                                                                                                    			printf("After sorting the bubble sort generates...\n");
                                                                                                    			pList->BubbleSort();
                                                                                                    			pList->DisplayList(); 
                                                                                                    			break;
                                                                                                    		case 2:
                                                                                                    			printf("After sorting the selection sort generates...\n");
                                                                                                    			pList->SelectionSort(); 
                                                                                                    	 		pList->DisplayList(); 
                                                                                                    			break;
                                                                                                    		case 3:
                                                                                                    			printf("After sorting the insertion sort generates...\n");
                                                                                                    			pList->InsertSort(); 
                                                                                                    	 		pList->DisplayList(); 
                                                                                                    			break;
                                                                                                    	}
                                                                                                    	printf("\n\n");
                                                                                                }
                                                                                                ////////////////////////////////////////
                                                                                                //     ////////////////////////////////////////
                                                                                                /////////////////
                                                                                                ////////////////////////////////////////
                                                                                                //     ////////////////////////////////////////
                                                                                                /////////////////
                                                                                                // main entry point for application
                                                                                                ////////////////////////////////////////
                                                                                                //     ////////////////////////////////////////
                                                                                                /////////////////
                                                                                                ////////////////////////////////////////
                                                                                                //     ////////////////////////////////////////
                                                                                                /////////////////


                                                                                                    int main(void){
                                                                                                    	
                                                                                                    	// initialize the random number generator
                                                                                                    	// set it to the current time by casting the current time to an usigned int
                                                                                                    	srand((int)time(NULL));
                                                                                                    	TestDefaultConstructor();
                                                                                                    	TestIntegerConstructor(8);
                                                                                                    	TestRandomConstructor("R", 7);
                                                                                                    	
                                                                                                    	// bubble sort
                                                                                                    	TestSort("R", 6, 1);
                                                                                                    	
                                                                                                    	// selection sort
                                                                                                    	TestSort("R", 8, 2);
                                                                                                    // insertion sort
                                                                                                    	TestSort("R",9, 3);
                                                                                                    	
                                                                                                    	return 0;
                                                                                                }