哈尔滨手机网站建设价格,邢台seo技术,最好的ui设计培训,app设计理念c List(双向链表)List(双向链表)介绍: List是一个线性链表结构#xff0c;它的数据由若干个节点构成#xff0c;每一个节点都包括一个信息块#xff08;即实际存储的数据#xff09;、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩#x… c List(双向链表)List(双向链表)介绍: List是一个线性链表结构它的数据由若干个节点构成每一个节点都包括一个信息块即实际存储的数据、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩这是因为它存储在非连续的内存空间中并且由指针将有序的元素链接起来。 由于其结构的原因list 随机检索的性能非常的不好因为它不像vector 那样直接找到元素的地址而是要从头一个一个的顺序查找这样目标元素越靠后它的检索时间就越长。检索时间与目标元素的位置成正比。 虽然随机检索的速度不够快但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置插入或删除一个元素仅对最多三个元素有所影响不像vector 会对操作点之后的所有元素的存储地址都有所影响这一点是vector 不可比拟的。 List 的特点 (1) 不使用连续的内存空间这样可以随意地进行动态操作 (2) 可以在内部任何位置快速地插入或删除当然也可以在两端进行push和pop 。 (3) 不能进行内部的随机访问即不支持[ ] 操作符和vector.at() Lists将元素按顺序储存在链表中与向量(vectors)相比它允许快速的插入和删除但是随机访问却比较慢. 1.assign() 给list赋值 语法: void assign( input_iterator start, input_iterator end ); //以迭代器start和end指示的范围为list赋值 void assign( size_type num, const TYPE val ); //赋值num个以val为值的元素。 2.back() 返回最后一个元素的引用 3.begin() 返回指向第一个元素的迭代器 4.clear() 删除所有元素 5.empty() 如果list是空的则返回true 6.end() 返回末尾的迭代器 7.erase() 删除一个元素 语法 iterator erase( iterator loc );//删除loc处的元素 iterator erase( iterator start, iterator end ); //删除start和end之间的元素 8.front() 返回第一个元素的引用 9.get_allocator() 返回list的配置器 10.insert() 插入一个元素到list中 语法 iterator insert( iterator loc, const TYPE val ); //在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器, void insert( iterator loc, size_type num, const TYPE val ); //定位置loc前插入num个值为val的元素 void insert( iterator loc, input_iterator start, input_iterator end ); //在指定位置loc前插入区间[start, end)的所有元素 11.max_size() 返回list能容纳的最大元素数量 12.merge() 合并两个list 语法: void merge( list lst );//把自己和lst链表连接在一起 void merge( list lst, Comp compfunction ); //指定compfunction则将指定函数作为比较的依据。 13.pop_back() 删除最后一个元素 14.pop_front() 删除第一个元素 15.push_back() 在list的末尾添加一个元素 16.push_front() 在list的头部添加一个元素 17.rbegin() 返回指向第一个元素的逆向迭代器 18.remove() 从list删除元素 语法: void remove( const TYPE val ); //删除链表中所有值为val的元素 19.remove_if() 按指定条件删除元素 20.rend() 指向list末尾的逆向迭代器 21.resize() 改变list的大小 语法: void resize( size_type num, TYPE val ); //把list的大小改变到num。被加入的多余的元素都被赋值为val22. 22.reverse() 把list的元素倒转 23.size() 返回list中的元素个数 24.sort() 给list排序 语法: void sort();//为链表排序默认是升序 void sort( Comp compfunction );//采用指定函数compfunction来判定两个元素的大小。 25.splice() 合并两个list 语法: void splice( iterator pos, list lst );//把lst连接到pos的位置 void splice( iterator pos, list lst, iterator del );//插入lst中del所指元素到现链表的pos上 void splice( iterator pos, list lst, iterator start, iterator end );//用start和end指定范围。 26.swap() 交换两个list 语法 void swap( list lst );// 交换lst和现链表中的元素 27.unique() 删除list中重复的元素 语法: void unique();//删除链表中所有重复的元素 void unique( BinPred pr );// 指定pr则使用pr来判定是否删除。 以下转自http://www.cnblogs.com/fangyukuan/archive/2010/09/21/1832364.html 例子 1 // ------------------------------------------------------------------------- 2 // 文件名 : list1.cpp 3 // 创建者 : 方煜宽 4 // 邮箱 fangyukuangmail.com 5 // 创建时间 : 2010-9-19 15:58 6 // 功能描述 : STL中的list就是一双向链表可高效地进行插入删除元素。 7 // 8 // ------------------------------------------------------------------------- 9 #include stdafx.h 10 #include iostream 11 #include list 12 using namespace std; 13 14 listint g_list1; 15 listint g_list2; 16 17 // 18 19 // 初始化全局链表 20 void InitList() 21 { 22 // push_back()增加一元素到链表尾 23 g_list1.push_back(1); 24 g_list1.push_back(2); 25 g_list1.push_back(3); 26 27 // push_front()增加一元素到链表头 28 g_list2.push_front(6); 29 g_list2.push_front(5); 30 g_list2.push_front(4); 31 } 32 33 // 输出一个链表 34 void ShowList(listint listTemp) 35 { 36 // size()返回链表中元素个数 37 cout listTemp.size() endl; 38 39 for (listint::iterator it listTemp.begin(); it ! listTemp.end(); it) 40 { 41 cout *it ; 42 } 43 cout endl; 44 } 45 46 // 47 48 // 构造函数空链表 49 void constructor_test0() 50 { 51 listint listTemp; 52 cout listTemp.size() endl; 53 } 54 55 // 构造函数建一个含三个默认值是0的元素的链表 56 void constructor_test1() 57 { 58 listint listTemp(3); 59 ShowList(listTemp); 60 } 61 62 // 构造函数建一个含五个元素的链表值都是1 63 void constructor_test2() 64 { 65 listint listTemp(5, 1); 66 ShowList(listTemp); 67 } 68 69 // 构造函数建一个g_list1的copy链表 70 void constructor_test3() 71 { 72 listint listTemp(g_list1); 73 ShowList(listTemp); 74 } 75 76 // 构造函数listTemp含g_list1一个区域的元素[_First, _Last) 77 void constructor_test4() 78 { 79 listint listTemp(g_list1.begin(), g_list1.end()); 80 ShowList(listTemp); 81 } 82 83 // assign()分配值有两个重载 84 // template class InputIterator 85 // void assign ( InputIterator first, InputIterator last ); 86 // void assign ( size_type n, const T u ); 87 void assign_test() 88 { 89 listint listTemp(5, 1); 90 ShowList(listTemp); 91 92 listTemp.assign(4, 3); 93 ShowList(listTemp); 94 95 listTemp.assign(g_list1.begin(), g_list1.end()); 96 ShowList(listTemp); 97 } 98 99 // operator 100 void operator_equality_test() 101 { 102 g_list1 g_list2; 103 ShowList(g_list1); 104 ShowList(g_list2); 105 } 106 107 // front()返回第一个元素的引用 108 void front_test7() 109 { 110 cout g_list1.front() endl; 111 } 112 113 // back()返回最后一元素的引用 114 void back_test() 115 { 116 cout g_list1.back() endl; 117 } 118 119 // begin()返回第一个元素的指针(iterator) 120 void begin_test() 121 { 122 listint::iterator it1 g_list1.begin(); 123 cout *it1 endl; 124 125 listint::const_iterator it2 g_list1.begin(); 126 it2; 127 // (*it2); // *it2 为const 不用修改 128 cout *it2 endl; 129 130 } 131 132 // end()返回 [最后一个元素的下一位置的指针] (list为空时end() begin()) 133 void end_test() 134 { 135 listint::iterator it g_list1.end(); // 注意是最后一个元素的下一位置的指针 136 --it; 137 cout *it endl; 138 } 139 140 // rbegin()返回链表最后一元素的后向指针 141 void rbegin_test() 142 { 143 listint::reverse_iterator it g_list1.rbegin(); 144 for (; it ! g_list1.rend(); it) 145 { 146 cout *it ; 147 } 148 cout endl; 149 } 150 151 // rend()返回链表第一元素的下一位置的后向指针 152 void rend_test() 153 { 154 listint::reverse_iterator it g_list1.rend(); 155 --it; 156 cout *it endl; 157 } 158 159 // push_back()增加一元素到链表尾 160 void push_back_test() 161 { 162 ShowList(g_list1); 163 g_list1.push_back(4); 164 ShowList(g_list1); 165 } 166 167 // push_front()增加一元素到链表头 168 void push_front_test() 169 { 170 ShowList(g_list1); 171 g_list1.push_front(4); 172 ShowList(g_list1); 173 } 174 175 // pop_back()删除链表尾的一个元素 176 void pop_back_test() 177 { 178 ShowList(g_list1); 179 cout endl; 180 181 g_list1.pop_back(); 182 ShowList(g_list1); 183 184 } 185 186 // pop_front()删除链表头的一元素 187 void pop_front_test() 188 { 189 ShowList(g_list1); 190 cout endl; 191 192 g_list1.pop_front(); 193 ShowList(g_list1); 194 } 195 196 // clear()删除所有元素 197 void clear_test() 198 { 199 ShowList(g_list1); 200 g_list1.clear(); 201 ShowList(g_list1); 202 } 203 204 // erase()删除一个元素或一个区域的元素(两个重载函数) 205 void erase_test() 206 { 207 ShowList(g_list1); 208 g_list1.erase(g_list1.begin()); 209 ShowList(g_list1); 210 211 cout endl; 212 213 ShowList(g_list2); 214 g_list2.erase(g_list2.begin(), g_list2.end()); 215 ShowList(g_list2); 216 } 217 218 // remove()删除链表中匹配值的元素(匹配元素全部删除) 219 void remove_test() 220 { 221 ShowList(g_list1); 222 g_list1.push_back(1); 223 ShowList(g_list1); 224 225 g_list1.remove(1); 226 ShowList(g_list1); 227 } 228 229 bool myFun(const int value) { return (value 2); } 230 // remove_if()删除条件满足的元素(会遍历一次链表) 231 void remove_if_test() 232 { 233 ShowList(g_list1); 234 g_list1.remove_if(myFun); 235 ShowList(g_list1); 236 } 237 238 239 // empty()判断是否链表为空 240 void empty_test() 241 { 242 listint listTemp; 243 if (listTemp.empty()) 244 cout listTemp为空 endl; 245 else 246 cout listTemp不为空 endl; 247 } 248 249 250 // max_size()返回链表最大可能长度:1073741823 251 void max_size_test() 252 { 253 listint::size_type nMax g_list1.max_size(); 254 cout nMax endl; 255 } 256 257 258 // resize()重新定义链表长度(两重载函数) 259 void resize_test() 260 { 261 ShowList(g_list1); 262 g_list1.resize(9); // 用默认值填补 263 ShowList(g_list1); 264 cout endl; 265 266 ShowList(g_list2); 267 g_list2.resize(9, 51); // 用指定值填补 268 ShowList(g_list2); 269 } 270 271 // reverse()反转链表 272 void reverse_test() 273 { 274 ShowList(g_list1); 275 g_list1.reverse(); 276 ShowList(g_list1); 277 } 278 279 280 // sort()对链表排序默认升序(两个重载函数) 281 void sort_test() 282 { 283 listint listTemp; 284 listTemp.push_back(9); 285 listTemp.push_back(3); 286 listTemp.push_back(5); 287 listTemp.push_back(1); 288 listTemp.push_back(4); 289 listTemp.push_back(3); 290 291 ShowList(listTemp); 292 listTemp.sort(); 293 ShowList(listTemp); 294 295 listTemp.sort(greaterint()); 296 ShowList(listTemp); 297 } 298 299 // merge()合并两个升序序链表并使之成为另一个升序. 300 void merge_test1() 301 { 302 listint listTemp2; 303 listTemp2.push_back(3); 304 listTemp2.push_back(4); 305 306 listint listTemp3; 307 listTemp3.push_back(9); 308 listTemp3.push_back(10); 309 310 ShowList(listTemp2); 311 cout endl; 312 ShowList(listTemp3); 313 cout endl; 314 315 listTemp2.merge(listTemp3); 316 ShowList(listTemp2); 317 } 318 319 320 bool myCmp (int first, int second) 321 { return ( int(first)int(second) ); } 322 323 // merge()合并两个降序链表并使之成为另一个降序. 324 void merge_test2() 325 { 326 listint listTemp2; 327 listTemp2.push_back(4); 328 listTemp2.push_back(3); 329 330 listint listTemp3; 331 listTemp3.push_back(10); 332 listTemp3.push_back(9); 333 334 ShowList(listTemp2); 335 cout endl; 336 ShowList(listTemp3); 337 cout endl; 338 339 // listTemp2.merge(listTemp3, greaterint()); // 第二个参数可以是自己定义的函数如下 340 listTemp2.merge(listTemp3, myCmp); 341 ShowList(listTemp2); 342 } 343 344 // splice()对两个链表进行结合(三个重载函数),结合后第二个链表清空 345 // void splice ( iterator position, listT,Allocator x ); 346 // void splice ( iterator position, listT,Allocator x, iterator i ); 347 // void splice ( iterator position, listT,Allocator x, iterator first, iterator last ); 348 void splice_test() 349 { 350 listint listTemp1(g_list1); 351 listint listTemp2(g_list2); 352 353 ShowList(listTemp1); 354 ShowList(listTemp2); 355 cout endl; 356 357 // 358 listTemp1.splice(listTemp1.begin(), listTemp2); 359 ShowList(listTemp1); 360 ShowList(listTemp2); 361 362 // 363 listTemp1.assign(g_list1.begin(), g_list1.end()); 364 listTemp2.assign(g_list2.begin(), g_list2.end()); 365 listTemp1.splice(listTemp1.begin(), listTemp2, listTemp2.begin()); 366 ShowList(listTemp1); 367 ShowList(listTemp2); 368 369 // 370 listTemp1.assign(g_list1.begin(), g_list1.end()); 371 listTemp2.assign(g_list2.begin(), g_list2.end()); 372 listTemp1.splice(listTemp1.begin(), listTemp2, listTemp2.begin(), listTemp2.end()); 373 ShowList(listTemp1); 374 ShowList(listTemp2); 375 376 } 377 378 // insert()在指定位置插入一个或多个元素(三个重载函数) 379 // iterator insert ( iterator position, const T x ); 380 // void insert ( iterator position, size_type n, const T x ); 381 // template class InputIterator 382 // void insert ( iterator position, InputIterator first, InputIterator last ); 383 void insert_test() 384 { 385 listint listTemp1(g_list1); 386 ShowList(listTemp1); 387 listTemp1.insert(listTemp1.begin(), 51); 388 ShowList(listTemp1); 389 cout endl; 390 391 listint listTemp2(g_list1); 392 ShowList(listTemp2); 393 listTemp2.insert(listTemp2.begin(), 9, 51); 394 ShowList(listTemp2); 395 cout endl; 396 397 listint listTemp3(g_list1); 398 ShowList(listTemp3); 399 listTemp3.insert(listTemp3.begin(), g_list2.begin(), g_list2.end()); 400 ShowList(listTemp3); 401 402 } 403 404 // swap()交换两个链表(两个重载) 405 void swap_test() 406 { 407 ShowList(g_list1); 408 ShowList(g_list2); 409 cout endl; 410 411 g_list1.swap(g_list2); 412 ShowList(g_list1); 413 ShowList(g_list2); 414 } 415 416 bool same_integral_part (double first, double second) 417 { return ( int(first)int(second) ); } 418 419 // unique()删除相邻重复元素 420 void unique_test() 421 { 422 listint listTemp; 423 listTemp.push_back(1); 424 listTemp.push_back(1); 425 listTemp.push_back(4); 426 listTemp.push_back(3); 427 listTemp.push_back(5); 428 listTemp.push_back(1); 429 listint listTemp2(listTemp); 430 431 ShowList(listTemp); 432 listTemp.unique(); // 不会删除不相邻的相同元素 433 ShowList(listTemp); 434 cout endl; 435 436 listTemp.sort(); 437 ShowList(listTemp); 438 listTemp.unique(); 439 ShowList(listTemp); 440 cout endl; 441 442 listTemp2.sort(); 443 ShowList(listTemp2); 444 listTemp2.unique(same_integral_part); 445 ShowList(listTemp2); 446 447 } 448 449 // 主函数下面要测试哪个就把那个注释去掉即可 450 int _tmain(int argc, _TCHAR* argv[]) 451 { 452 InitList(); 453 // ShowList(g_list1); 454 // ShowList(g_list2); 455 456 // constructor_test0(); 457 // constructor_test1(); 458 // constructor_test2(); 459 // constructor_test3(); 460 // constructor_test4(); 461 // assign_test(); 462 // operator_equality_test(); 463 // front_test7(); 464 // back_test(); 465 // begin_test(); 466 // end_test(); 467 // rbegin_test(); 468 // rend_test(); 469 // push_back_test(); 470 // push_front_test(); 471 // pop_back_test(); 472 // pop_front_test(); 473 // clear_test(); 474 // erase_test(); 475 // remove_test(); 476 // remove_if_test(); 477 // empty_test(); 478 // max_size_test(); 479 // resize_test(); 480 // reverse_test(); 481 // sort_test(); 482 // merge_test1(); 483 // merge_test2(); 484 // splice_test(); 485 // insert_test(); 486 // swap_test(); 487 // unique_test(); 488 return 0; 489 }
