posts - 195, comments - 34, trackbacks - 0, articles - 1
          


          		
	
          
	
          
		
			
		
		
			
          
				
					
	
          
		
          
			
          
				CSingleList的類實現，可以豐富起來
			
          
 			Posted on 2010-04-16 10:30 小強摩羯座 閱讀(183) 評論(0)  編輯  收藏  所屬分類: C++ &VC 
			
			


		
          
		
            1
          
            2
          
            3// realize a SingleList class
          
            4/*
          
            5實現方法
          
            6add()
          
            7add2Head(dd);
          
            8del
          
            9lastN
          
           10length();
          
           11reverse();//實現單鏈表反轉
          
           12*/
          
           13#include<iostream>
          
           14#include<cassert>
          
           15#include<typeinfo>
          
           16
          
           17using namespace std;
          
           18
          
           19#define  DataType int
          
           20
          
           21class CSingleList
          
           22{
          
           23private:
          
           24    typedef struct Node
          
           25    {
          
           26        DataType data;
          
           27        Node * next;
          
           28    }          ;
          
           29    Node* pHead;
          
           30
          
           31public:
          
           32    CSingleList()
          
           33    {
          
           34        pHead = NULL;
          
           35    }
          
           36    CSingleList& add(DataType data)
          
           37    {
          
           38        if ( pHead == NULL)
          
           39        {
          
           40            pHead = new Node;
          
           41            pHead->data = data;
          
           42        }
          
           43        else
          
           44        {
          
           45            Node* p = pHead;
          
           46            while (p->next != NULL )
          
           47            {
          
           48                p = p->next;
          
           49            }
          
           50            Node* q = new Node;
          
           51            q->data = data;
          
           52            q->next = NULL;
          
           53            p->next = q;
          
           54        }
          
           55        return *this;
          
           56    }
          
           57    CSingleList& add2Head(DataType data)
          
           58    {
          
           59        if ( pHead == NULL)
          
           60        {
          
           61            pHead = new Node;
          
           62            assert(pHead);
          
           63            pHead->data = data;
          
           64            pHead->next = NULL;
          
           65        }
          
           66        else
          
           67        {
          
           68            Node* q = new Node;
          
           69            assert(q);
          
           70            q->data = data;
          
           71            q->next = pHead;
          
           72            pHead = q;
          
           73        }
          
           74        return *this;
          
           75    }
          
           76    void print(const char* note=" ")
          
           77    {
          
           78        Node* p = pHead;
          
           79
          
           80        cout<<"---------- "<<note<<" ---------"<<endl;
          
           81        while (p != NULL && p->next!= NULL)
          
           82        {
          
           83            cout<<p->data<<", ";
          
           84            p = p->next;
          
           85        }
          
           86        cout<<p->data<<endl;;
          
           87    }
          
           88    int length()
          
           89    {
          
           90        int n = 0;
          
           91        Node* p = pHead;
          
           92        while ( p != NULL)
          
           93        {
          
           94            n++;
          
           95            p = p->next;
          
           96        }
          
           97        return n;
          
           98    }
          
           99
          
          100    CSingleList& del(DataType data)
          
          101    {
          
          102        if ( pHead == NULL) return *this;
          
          103        //數據在在頭結點
          
          104        if (pHead->data == data)
          
          105        {
          
          106            delete pHead;
          
          107            pHead = NULL;
          
          108            return *this;
          
          109        }
          
          110        Node *p, *q;
          
          111        p = pHead;
          
          112        q = p->next;
          
          113        while ( q != NULL)
          
          114        {
          
          115            if (q -> data == data)
          
          116                break;
          
          117            p = q;
          
          118            q = q->next;
          
          119        }
          
          120        //point to the q's next
          
          121        p->next = q->next;
          
          122        delete q;
          
          123
          
          124        return *this;
          
          125    }
          
          126
          
          127    CSingleList& reverse()
          
          128    {
          
          129        Node *p1, *p2, *p3;
          
          130        //如果長度小于2不用反轉
          
          131        if ( pHead == NULL || pHead->next== NULL)
          
          132            return *this;
          
          133
          
          134        p1 = pHead;
          
          135        p2 = pHead->next;
          
          136        while (p2 != NULL)
          
          137        {
          
          138            p3 = p2->next;
          
          139            p2->next = p1;
          
          140            p1 = p2;
          
          141            p2 = p3;
          
          142        }
          
          143        pHead->next = NULL;
          
          144        pHead = p1;
          
          145        return *this;
          
          146    }
          
          147    //得到鏈表中的倒數第N個
          
          148    DataType getLastN(int lastN)
          
          149    {
          
          150        reverse();
          
          151        Node *p = pHead;
          
          152        for (int i = 1; i < lastN;i++)
          
          153        {
          
          154            if (p == NULL) return -1;
          
          155            p = p->next;
          
          156        }
          
          157        reverse();
          
          158        if (p != NULL) return p->data;
          
          159        return -1;
          
          160    }
          
          161    //using 2 pointer to speed
          
          162    DataType getLastN2(int lastN)
          
          163    {
          
          164        Node *p = pHead;
          
          165        for (int i = 1; i < lastN;i++)
          
          166        {
          
          167            if (p == NULL) return -1;
          
          168            p = p->next;
          
          169        }
          
          170
          
          171        if (p != NULL)
          
          172        {
          
          173            Node* q = pHead;
          
          174            while ( p->next != NULL)
          
          175            {
          
          176                q = q ->next;
          
          177                p = p ->next;
          
          178            }
          
          179            return q->data;
          
          180        }
          
          181        return -1;
          
          182    }
          
          183    //for singleList, /使用選擇排序吧
          
          184    CSingleList& selectSort()
          
          185    {
          
          186        if ( pHead == NULL) return *this;
          
          187        for ( Node* p = pHead;p != NULL;p = p->next)
          
          188        {   
          
          189            Node* minNode = p;
          
          190            for (Node* q = p->next;  q!= NULL; q = q->next)
          
          191            {
          
          192                if ( q ->data < minNode->data)
          
          193                {
          
          194                    minNode = q;
          
          195                }
          
          196            }
          
          197            cout<<"min = "<<minNode->data<<endl;
          
          198            swap( minNode->data, p->data);
          
          199        }
          
          200        return *this;
          
          201    }
          
          202    CSingleList& insertSort()
          
          203    {
          
          204        if( pHead == NULL) return *this;
          
          205        
          
          206        for(Node* p = pHead->next; p!= NULL;p = p->next)
          
          207        {
          
          208            if( p->data > pHead->data)// 
          
          209            {
          
          210                DataType tmp = pHead->data;
          
          211                for(Node *q = pHead; q != p;q = q->next)
          
          212                {
          
          213                    
          
          214                }           
          
          215            }           
          
          216        }           
          
          217    }           
          
          218}          ;
          
          219void swap(DataType& a, DataType& b)
          
          220{
          
          221    a = a + b - ( b = a);
          
          222}
          
          223
          
          224
          
          225int main()
          
          226{
          
          227    CSingleList myList1;
          
          228    myList1.add(3).add(5).add(34).add(24334).add2Head(88);
          
          229
          
          230    myList1.print();
          
          231
          
          232    cout<< myList1.length()<<endl;
          
          233
          
          234    myList1.del(5).del(34);
          
          235
          
          236    myList1.print();
          
          237
          
          238    myList1.reverse();
          
          239    myList1.print();
          
          240    myList1.add(233).add(256);
          
          241    myList1.print();
          
          242
          
          243    cout<<" last 2 :"<< myList1.getLastN2(2);
          
          244
          
          245
          
          246    myList1.selectSort();
          
          247    myList1.print("afte sort");
          
          248
          
          249    return 0;
          
          250}


          



          
                                
                                
                                
          
	
          


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			

		
	
          

          


    







          
        
	




主站蜘蛛池模板：
定州市|
吐鲁番市|
淳安县|
临安市|
辛集市|
乐安县|
扬中市|
丘北县|
田林县|
福安市|
杭锦后旗|
云南省|
兴仁县|
嵊泗县|
青龙|
广南县|
甘南县|
漾濞|
七台河市|
乐至县|
庆安县|
治县。|
喀什市|
绩溪县|
三台县|
哈巴河县|
海门市|
雷州市|
呼图壁县|
保德县|
梅河口市|
葫芦岛市|
沈丘县|
当涂县|
临沭县|
道孚县|
连江县|
莎车县|
华蓥市|
淮北市|
宁强县|