linked3.txt

链表的bubble

//**************************************
//     
// Name: Linked List with bubble, select
//     ion, and insertion sort member functions
//     
// Description:This is an excellent demo
//     nstation of a single linked list of inte
//     gers. The source shows how to implement 
//     two classes, one for the list, and one f
//     or the nodes. Each class uses pointers a
//     nd shows how to also use the Friend oper
//     ator to give the list class access to th
//     e private node class's attributes. There
//     are several member functions included in
//     the list class. All are completely funct
//     ional. They are a bubbleSort, selectionS
//     ort, and insertionSort method. The code 
//     is fairly commented and I've used Hungar
//     ian notation for all variables. That is 
//     also an excellent habit to get into, it 
//     may look strange and confusing at first,
//     but after a small introductory period, y
//     our coding will only grow stronger as a 
//     result!
// By: Mark Belles
//
// Assumes:Pointers, pointers, and more 
//     pointers! The arrow "->" notation is 
//     used via a pointer to an object, where t
//     he dot "." notation is used explicitly f
//     rom an instanced object. 
Example: Pointer notation
CList *pList;
pList->bubbleSort()
Example: Object notation
CList oList;
oList.bubbleSort()
Also, some notes on the variables names. this source is consistent with the Hungarian notation I learned. There are a few variations, but this is how I learned how to do it, so don't worry, it's not the only way!!! :) 
g_ (global variable prefix)
m_ (private variable prefix)
n (int)
sz (char*)
sv (char)
l (long)
d (double)
b (bool)
example, g_bIsSorted or m_nNumNodes
The first is a global boolean called IsSorted, the second is a private integer called NumNodes. this method of naming is extremely handy as you can determine the scope and type of each variable simply by seeing the name!!! Have fun!
//
// Side Effects:No side effects, complet
//     e code, so just compile and run!
//
//This code is copyrighted and has// limited warranties.Please see http://
//     www.1CPlusPlusStreet.com/xq/ASP/txtCodeI
//     d.842/lngWId.3/qx/vb/scripts/ShowCode.ht
//     m//for details.//**************************************
//     

////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// Author: Mark Belles
// E-mail: [e-mail]
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
#include <iostream.h>
#include <stdio.h>
#include <cstdlib>
//#include <windows.h> // this is 
//     required for the msgbox function
#include <string.h>
#include <ctime>
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// function prototypes
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
void TestDefaultConstructor(void);
void TestIntegerConstructor(int nNumNodes);
void TestRandomConstructor(const char *szOption, int nListLength);
void TestSort(const char *szOption, int nListLength,int nSortOption);
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// CNode Definition
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////


    class CNode{
    public:
    	friend class CList;
    	CNode();
    	CNode(int nValue);
    	CNode(CNode &node);
    	~CNode();
    	CNode *getLink(void);
    private:
    	int m_nValue;
    	CNode *m_pLink;
};
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// empty constructor


    CNode::CNode(){
    	this->m_nValue = 0;
    	this->m_pLink = NULL;
}
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// integer constructor


    CNode::CNode(int nValue){
    	this->m_nValue = nValue;
    	this->m_pLink = NULL;
}
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// copy constructor


    CNode::CNode(CNode &node){
    	this->m_nValue = node.m_nValue;
    	this->m_pLink = node.m_pLink; 
}


    CNode *CNode::getLink(void){
    	return this->m_pLink;
}
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// CList Definition
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////


    class CList{
    public:
    	CList(void);
    	CList(int nNumberOfNodes);
    	CList(const char *szOption, int nListLength);
    	~CList(void);
    	int getCount(void);
    	CNode *getHead(void);
    	void InsertAtHead(int nValue);
    	void InsertAtTail(int nValue);
    	void DisplayList(void);
    	void BubbleSort(void);
    	void SelectionSort(void);
    	void InsertSort(void);
    	CNode *getTail(void);
    private:
    	int m_nCount;
    	CNode *m_pHead;
};
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// empty constructor


    CList::CList(void){
    	this->m_nCount = 0;
    	this->m_pHead = NULL;
}
////////////////////////////////////////
//     ////////////////////////////////////////
/////////////////
// create a list nNumberOfNodes long wit