练手系列(链表)

长平狐 发布于 2013/03/12 13:02
阅读 39
收藏 0

简单的单向链表的实现,主要功能包括:链表反转 元素获取 链表合并。

LinkList.h
1 #ifndef _HEADER_LINKLIST_CLASS 2 #define _HEADER_LINKLIST_CLASS 3 #include <iostream> 4 using namespace std; 5 6 typedef struct _ListNode 7 { 8 int data; 9 _ListNode * pnext; 10 11 }ListNode,* pListNode; 12 class LinkList 13 { 14 public : 15 LinkList(); 16 LinkList( int n); 17 LinkList(LinkList & list); 18 ~ LinkList(); 19 20 void Add( int data); 21 void Del( int npos); // delete the node in postion npos 22 bool Inverse(); // inverse the list 23 bool PurgeItem( int data); // delete the node with const data 24 LinkList* MergeList(LinkList *plist1); // merge the two list of same ascending order 25 void PrintAllItem(); // print all element in list 26 int GetSize() { return nsize;} // return the size of list 27 bool GetElement( int &data, int npos); // get the value in the postion of npos in list 28 private : 29 int nsize; 30 pListNode phead; 31 }; 32 #endif

 

LinkList.cpp
1 #include " Linklist.h " 2 3 LinkList::LinkList() 4 { 5 phead = NULL; 6 nsize = 0 ; 7 } 8 LinkList::LinkList( int n) 9 { 10 int i; 11 pListNode p; 12 pListNode ptemp; 13 nsize = n; 14 phead = NULL; 15 if (n> 0 ) 16 { 17 phead = new ListNode; 18 phead->pnext = NULL; 19 phead->data = 0 ; 20 p = phead; 21 } 22 for (i= 0; i<n- 1; i++ ) 23 { 24 ptemp = new ListNode; 25 ptemp->data = 0 ; 26 ptemp->pnext = NULL; 27 p->pnext = ptemp; 28 p = ptemp; 29 } 30 } 31 LinkList::LinkList(LinkList & list) 32 { 33 int i; 34 pListNode plast; 35 pListNode ptemp; 36 pListNode psrc = list.phead; 37 phead = NULL; 38 nsize = list.nsize; 39 // deeply copy 40 for (i= 0; i<nsize; i++ ) 41 { 42 ptemp = new ListNode; 43 ptemp->data = psrc-> data; 44 ptemp->pnext = NULL; 45 if(phead == NULL) 46 { 47 phead = ptemp; 48 plast = ptemp; 49 } 50 else 51 { 52 plast->pnext = ptemp; 53 } 54 psrc = psrc-> pnext; 55 } 56 } 57 58 LinkList::~ LinkList() 59 { 60 pListNode p = phead; 61 while (nsize) 62 { 63 Del(nsize- 1 ); 64 } 65 } 66 67 void LinkList::Add( int data) 68 { 69 pListNode ptemp1; 70 pListNode ptemp2; 71 if (phead == NULL) 72 { 73 ptemp1 = new ListNode; 74 phead = ptemp1; 75 phead->data = data; 76 phead->pnext = NULL; 77 nsize++ ; 78 } 79 else 80 { 81 ptemp1 = phead; 82 while(ptemp1->pnext != NULL) 83 { 84 ptemp1 = ptemp1-> pnext; 85 } 86 ptemp2 = new ListNode; 87 ptemp2->data = data; 88 ptemp2->pnext = NULL; 89 ptemp1->pnext = ptemp2; 90 nsize++ ; 91 } 92 } 93 void LinkList::Del( int npos) 94 { 95 int ncount= 0 ; 96 pListNode ptemp = phead; 97 pListNode plast; 98 if (npos< 0 || npos > nsize) 99 return ; 100 while (ptemp != NULL) 101 { 102 if (ncount == npos && ncount== 0 ) 103 { 104 // delete the head 105 phead = phead-> pnext; 106 delete ptemp; 107 ptemp = phead; 108 nsize-- ; 109 } 110 else if (ncount == npos) 111 { 112 plast->pnext = ptemp-> pnext; 113 delete ptemp; 114 ptemp = plast-> pnext; 115 nsize-- ; 116 continue ; 117 } 118 else 119 { 120 plast = ptemp; 121 ptemp = ptemp-> pnext; 122 } 123 ncount++ ; 124 } 125 } 126 bool LinkList::Inverse() 127 { 128 if (phead == NULL) 129 return false ; 130 pListNode pdown=NULL,pcurrent= phead,ptemp1,ptemp2; 131 while (pcurrent->pnext != NULL) 132 { 133 ptemp1 = pcurrent; 134 ptemp2 = pdown; 135 pcurrent = pcurrent-> pnext; 136 pdown = ptemp1; 137 pdown->pnext = ptemp2; 138 } 139 phead = pcurrent; 140 phead->pnext = pdown; 141 return true ; 142 } 143 bool LinkList::PurgeItem( int data) 144 { 145 pListNode p = phead; 146 pListNode plast; 147 while (p != NULL) 148 { 149 if(p->data == data && p== phead) 150 { 151 delete p; 152 phead = p-> pnext; 153 nsize-- ; 154 return true ; 155 } 156 else if(p->data == data) 157 { 158 plast->pnext = p-> pnext; 159 delete p; 160 nsize-- ; 161 return true ; 162 } 163 else 164 { 165 plast = p; 166 p = p-> pnext; 167 } 168 } 169 return false ; 170 } 171 /* *************************************************** 172 /****condition:the two list has sorted by some rule 173 *************************************************** */ 174 LinkList* LinkList::MergeList(LinkList * plist1) 175 { 176 LinkList *plistnew = NULL; 177 ListNode *ptemp1 = NULL; 178 ListNode *ptemp2 = NULL; 179 ListNode *ptemp3 = NULL; 180 int i; 181 if (plist1 == NULL) 182 { 183 plistnew = new LinkList(nsize); 184 ptemp1 = plistnew-> phead; 185 ptemp2 = phead; 186 if (ptemp1== NULL) 187 return NULL; 188 for (i= 0; i<nsize; i++ ) 189 { 190 ptemp1->data = ptemp2-> data; 191 ptemp1=ptemp1-> pnext; 192 ptemp2=ptemp2-> pnext; 193 } 194 } 195 else 196 { 197 plistnew = new LinkList(nsize+plist1-> nsize); 198 ptemp1 = plistnew-> phead; 199 ptemp2 = phead; 200 ptemp3 = plist1-> phead; 201 while (ptemp2 != NULL && ptemp3 != NULL) 202 { 203 if (ptemp2->data < ptemp3-> data) 204 { 205 ptemp1->data = ptemp2-> data; 206 ptemp2 = ptemp2-> pnext; 207 } 208 else 209 { 210 ptemp1->data = ptemp3-> data; 211 ptemp3 = ptemp3-> pnext; 212 } 213 ptemp1 = ptemp1-> pnext; 214 } 215 216 while(ptemp2 != NULL) 217 { 218 ptemp1->data = ptemp2-> data; 219 ptemp2 = ptemp2-> pnext; 220 ptemp1=ptemp1-> pnext; 221 } 222 while(ptemp3 != NULL) 223 { 224 ptemp1->data = ptemp3-> data; 225 ptemp3 = ptemp3-> pnext; 226 ptemp1=ptemp1-> pnext; 227 } 228 } 229 return plistnew; 230 } 231 232 void LinkList::PrintAllItem() 233 { 234 pListNode p = phead; 235 if (p == NULL) 236 return ; 237 printf( " All the data in list is:\n " ); 238 while(p!= NULL) 239 { 240 printf( " %d ",p-> data); 241 p = p-> pnext; 242 } 243 printf( " \nending\n " ); 244 } 245 bool LinkList::GetElement( int &data, int npos) 246 { 247 int ntemp = 0 ; 248 int ncount = 0 ; 249 pListNode p = phead; 250 if (npos< 0 || npos>= nsize) 251 return false ; 252 while (p != NULL) 253 { 254 if (ncount == npos) 255 { 256 data = p-> data; 257 return true ; 258 } 259 ncount++ ; 260 p = p-> pnext; 261 } 262 return false ; 263 }

测试:

test
1 #include " Linklist.h " 2 #include <iostream> 3 using namespace std; 4 5 int main( int argc, char * argv[]) 6 { 7 LinkList list1,list2; 8 LinkList * pResult; 9 int data; 10 int ncount = 5 ; 11 cout<< " please input the five element of list1 "<< endl; 12 while(ncount-- ) 13 { 14 scanf( " %d ",& data); 15 list1.Add(data); 16 } 17 printf( " Size of list1 is:%d\n " ,list1.GetSize()); 18 list1.PrintAllItem(); 19 list1.Inverse(); 20 printf( " /************Inverse the list************/\n " ); 21 list1.PrintAllItem(); 22 printf( " /*********get the element in postion 2***/\n " ); 23 list1.GetElement(data, 2 ); 24 printf( " The element is:%d\n " ,data); 25 printf( " /****del the first node wiht data 3******/\n " ); 26 list1.PurgeItem(data); 27 list1.PrintAllItem(); 28 29 ncount = 5 ; 30 cout<< " please input the five element of list2 "<< endl; 31 while (ncount-- ) 32 { 33 scanf( " %d ",& data); 34 list2.Add(data); 35 } 36 list2.PrintAllItem(); 37 pResult = list1.MergeList(& list2); 38 // pResult = list1.MergeList(0); 39 printf( " /********Merge the two list**************/\n " ); 40 pResult-> PrintAllItem(); 41 42 if (pResult != NULL) 43 { 44 delete pResult; 45 pResult = NULL; 46 } 47 return 0 ; 48 }

结果:


原文链接:http://www.cnblogs.com/wb-DarkHorse/archive/2012/10/20/2732226.html
加载中
返回顶部
顶部