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

CSingleList的类实现，可以丰富起来

Posted on 2010-04-16 10:30 小强摩羯座 阅读(177) 评论(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}



只有注册用户登录后才能发表评论。
网站导航: