list容器的C++代码实现

2023-08-20 18:14:52

  1. #include <iostream>
  2. using namespace std;
  3. template  <class T>
  4. class mylist;//前置声明
  5. template <class T>
  6. class node
  7. {
  8. friend class mylist<T>;//友元
  9. template <class T1>
  10. friend ostream& operator <<(ostream & out , node<T1> _node);
  11. public:
  12. node(T _data)
  13. {
  14. data = _data;
  15. next = NULL;
  16. prev = NULL;
  17. }
  18. private:
  19. T data;
  20. node<T> *next;//指向下一个节点
  21. node<T> *prev;//指向前一个节点
  22. };
  23. //输出符号 << 的重载
  24. template <class T>
  25. ostream& operator <<(ostream & out , node<T> _node)
  26. {
  27. out<<_node.data<<'\t';
  28. return out;
  29. }
  30. /*类名:mylist*/
  31. template<class T>
  32. class mylist
  33. {
  34. public:
  35. typedef bool (*Unperd)(T value);
  36. typedef bool (*BinPred)(T value);
  37. typedef bool (*Comp)(T a,T b);//排序的函数指针
  38. /*类名:iterator
  39. 作用:迭代器
  40. */
  41. class iterator
  42. {
  43. public:
  44. iterator()
  45. {
  46. ptr = NULL;
  47. }
  48. iterator(node<T>* _ptr)
  49. {
  50. ptr = _ptr;
  51. }
  52. /*符号 = 重载*/
  53. void operator =(iterator it)
  54. {
  55. this->ptr = it.ptr;
  56. }
  57. /*符号 != 重载*/
  58. bool operator !=(iterator it)
  59. {
  60. return this->ptr != it.ptr;
  61. }
  62. /*符号 == 重载*/
  63. bool operator == (iterator it)
  64. {
  65. return this->ptr == it.ptr;
  66. }
  67. /*符号 ++ 重载*/
  68. iterator operator ++(int i)//这里的 int i 是无意义的只是区别前++
  69. {
  70. iterator tmp;//中间迭代器变量tmp
  71. tmp = *this;
  72. this->ptr = this->ptr->next;
  73. return tmp;
  74. }
  75. /*符号 * 重载*/
  76. node<T> operator *()
  77. {
  78. return *(this->ptr);
  79. }
  80. private:
  81. node<T> *ptr;
  82. };
  83. /*反向迭代器*/
  84. //反向迭代器就是++的重载不一样,其他是一样的
  85. class reserve_iterator
  86. {
  87. public:
  88. reserve_iterator()
  89. {
  90. ptr = NULL;
  91. }
  92. reserve_iterator(node<T>* _ptr)
  93. {
  94. ptr = _ptr;
  95. }
  96. void operator =(reserve_iterator it)
  97. {
  98. this->ptr = it.ptr;
  99. }
  100. bool operator !=(reserve_iterator it)
  101. {
  102. return this->ptr != it.ptr;
  103. }
  104. bool operator == (reserve_iterator it)
  105. {
  106. return this->ptr == it.ptr;
  107. }
  108. reserve_iterator operator ++(int i)
  109. {
  110. reserve_iterator tmp;
  111. tmp = *this;
  112. this->ptr = this->ptr->prev;
  113. return tmp;
  114. }
  115. node<T> operator *()
  116. {
  117. return *(this->ptr);
  118. }
  119. private:
  120. node<T> *ptr;
  121. };
  122. /*无参缺省构造*/
  123. mylist()
  124. {
  125. head = NULL;
  126. curr = NULL;
  127. }
  128. /*list(int num,T value)
  129. 函数名:mylist
  130. 作用:创造一个list容器里面初始就有num个value值
  131. 参数:int num,T value
  132. 返回值:无
  133. */
  134. mylist(int num,T value)
  135. {
  136. head = new node<T>(value);
  137. curr = head;
  138. int i;
  139. node<T>* newnode = NULL;
  140. for (i = 0; i < num;i++)
  141. {
  142. newnode = new node<T>(value);
  143. curr->next = newnode;
  144. newnode->prev = curr;
  145. curr = newnode;
  146. newnode = NULL;
  147. }
  148. curr->next = head;//构成循环
  149. head->prev = curr;
  150. }
  151. /*list<T>(list)
  152. 函数名:mylist
  153. 作用:创造一个list容器里面拷贝另一个list容器的所有内容
  154. 参数:mylist & list
  155. 返回值:无
  156. */
  157. mylist(mylist & list)
  158. {
  159. node<T>* point = list.head->next;
  160. this->head = new node<T>(point->data);
  161. this->curr = this->head;
  162. node<T> * newnode = NULL;
  163. while (point != list.head)
  164. {
  165. newnode = new node<T>(point->data);
  166. this->curr->next = newnode;
  167. newnode->prev = this->curr;
  168. this->curr = newnode;
  169. newnode = NULL;
  170. point = point->next;
  171. }
  172. this->curr->next = this->head;
  173. this->head->prev = this->curr;
  174. }
  175. /*list<T>(list.begin(),list.end())
  176. 函数名:mylist
  177. 作用:创造一个list容器里面拷贝另一个list容器的所有内容
  178. 参数:mylist & list
  179. 返回值:无
  180. */
  181. mylist(iterator start,iterator end)
  182. {
  183. iterator point = start;
  184. head = new node<T>(*point);
  185. curr = head;
  186. node<T> * newnode = NULL;
  187. while (point != end)
  188. {
  189. newnode = new node<T>(*point);
  190. curr->next = newnode;
  191. newnode->prev = curr;
  192. curr = newnode;
  193. newnode = NULL;
  194. point++;
  195. }
  196. curr->next = head;
  197. head->prev = curr;
  198. }
  199. /*void assign( input_iterator start, input_iterator end );
  200. assign()函数以迭代器start和end指示的范围为list赋值*/
  201. void assign(iterator start,iterator end)
  202. {
  203. iterator point = start;
  204. if (NULL == head)
  205. {
  206. this->head = new node<T>(*point);
  207. curr = head;
  208. }
  209. else
  210. {
  211. curr = head->prev;
  212. }
  213. node<T> * newnode = NULL;
  214. while (point != end)
  215. {
  216. newnode = new node<T>(*point);
  217. curr->next = newnode;
  218. newnode->prev = curr;
  219. curr = newnode;
  220. newnode = NULL;
  221. point++;
  222. }
  223. curr->next = head;
  224. head->prev = curr;
  225. }
  226. /*void assign( size_type num, const TYPE &val );*/
  227. void assign(int num,const T & value)
  228. {
  229. if (NULL == head)
  230. {
  231. head = new node<T>(value);
  232. curr = head;
  233. }
  234. else
  235. {
  236. curr = head->prev;
  237. }
  238. int i;
  239. node<T>* newnode = NULL;
  240. for (i = 0; i < num;i++)
  241. {
  242. newnode = new node<T>(value);
  243. curr->next = newnode;
  244. newnode->prev = curr;
  245. curr = newnode;
  246. newnode = NULL;
  247. }
  248. curr->next = head;
  249. head->prev = curr;
  250. }
  251. /*back()函数返回一个引用，指向list的最后一个元素*/
  252. T& back()
  253. {
  254. return head->prev->data;
  255. }
  256. /*clear()函数删除list的所有元素*/
  257. void clear()
  258. {
  259. curr = head->next;
  260. head->next = NULL;
  261. node<T>* tmp;
  262. while (curr != head)
  263. {
  264. tmp = curr;
  265. curr = curr->next;
  266. head->next = curr;
  267. if (NULL != curr)
  268. {
  269. curr->prev = head;
  270. }
  271. free(tmp);
  272. tmp = NULL;
  273. }
  274. }
  275. /*empty()函数返回真(true)如果链表为空，否则返回假*/
  276. bool empty()
  277. {
  278. if (head->next == head)
  279. return true;
  280. return false;
  281. }
  282. /*起始位置*/
  283. iterator begin()
  284. {
  285. return  iterator(head->next);
  286. }
  287. /*末尾的下一个*/
  288. iterator end()
  289. {
  290. return  iterator(head);
  291. }
  292. /*rbegin()函数返回一个逆向迭代器，指向链表的末尾。*/
  293. reserve_iterator rebegin()
  294. {
  295. return reserve_iterator(head->prev);
  296. }
  297. /*rend()函数迭代器指向链表的头部。*/
  298. reserve_iterator rend()
  299. {
  300. return reserve_iterator(head);
  301. }
  302. /*find查找指定元素的第一个位置没找到则返回NULL*/
  303. iterator find(const T &value)
  304. {
  305. curr = head->next;
  306. int flag = 0;
  307. while (curr != head)
  308. {
  309. if (curr->data == value)
  310. {
  311. flag = 1;
  312. return iterator(curr);
  313. break;
  314. }
  315. curr = curr->next;
  316. }
  317. if (flag == 0)
  318. {
  319. return iterator();
  320. }
  321. }
  322. /*erase()函数删除以pos指示位置的元素
  323. iterator erase( iterator pos );*/
  324. iterator erase(iterator pos)
  325. {
  326. node<T>* tmp = head;
  327. curr = head->next;
  328. while (curr != head)
  329. {
  330. if (iterator(curr) == pos)
  331. {
  332. tmp->next = curr->next;
  333. curr->next->prev = tmp;
  334. return iterator(curr->next);
  335. free(curr);
  336. curr = NULL;
  337. break;
  338. }
  339. else
  340. {
  341. tmp = curr;
  342. }
  343. curr = curr->next;
  344. }
  345. }
  346. /* iterator erase( iterator start, iterator end );
  347. 删除start和end之间的元素。 返回值是一个迭代器，
  348. 指向最后一个被删除元素的下一个元素*/
  349. iterator erase(iterator start,iterator end)
  350. {
  351. node<T>* tmp = head;
  352. curr = head->next;
  353. while (curr != head)
  354. {
  355. if (iterator(tmp) == start)
  356. {
  357. while (iterator(curr) != end)
  358. {
  359. tmp->next = curr->next;
  360. curr->next->prev = tmp;
  361. free(curr);
  362. curr = NULL;
  363. curr = tmp->next;
  364. }
  365. return iterator(curr);
  366. break;
  367. }
  368. else
  369. {
  370. tmp = curr;
  371. }
  372. curr = curr->next;
  373. }
  374. }
  375. /*front()函数返回一个引用，指向链表的第一个元素。*/
  376. T & front()
  377. {
  378. return head->next->data;
  379. }
  380. /*  iterator insert( iterator pos, const TYPE &val );*/
  381. iterator insert(iterator pos,const T& value)
  382. {
  383. node<T>* newnode = new node<T>(value);
  384. curr = head->next;
  385. while (curr != head)
  386. {
  387. if (iterator(head) == pos)
  388. {
  389. head->prev->prev->next = newnode;
  390. newnode->prev = head->prev->prev;
  391. head->prev->prev = newnode;
  392. newnode->next = head->prev;
  393. return iterator(head->prev);
  394. break;
  395. }
  396. if (iterator(curr) == pos)
  397. {
  398. curr->prev->next = newnode;
  399. newnode->prev = curr->prev;
  400. curr->prev = newnode;
  401. newnode->next = curr;
  402. break;
  403. }
  404. curr = curr->next;
  405. }
  406. }
  407. /*  void insert( iterator pos, size_type num, const TYPE &val );*/
  408. void insert(iterator pos,int num,const T &value)
  409. {
  410. node<T>* newnode;
  411. curr = head->next;
  412. node<T>* tmp = head;
  413. if (iterator(head) == pos)
  414. {
  415. tmp = head->prev->prev;
  416. curr = head->prev;
  417. while (0 != num)
  418. {
  419. newnode = new node<T>(value);
  420. tmp->next = newnode;
  421. newnode->prev = tmp;
  422. tmp = newnode;
  423. newnode = NULL;
  424. num--;
  425. }
  426. tmp->next = curr;
  427. curr->prev = tmp;
  428. }
  429. else
  430. {
  431. while (curr != head)
  432. {
  433. if (iterator(curr) == pos)
  434. {
  435. while (0 != num)
  436. {
  437. newnode = new node<T>(value);
  438. tmp->next = newnode;
  439. newnode->prev = tmp;
  440. tmp = newnode;
  441. newnode = NULL;
  442. num--;
  443. }
  444. tmp->next = curr;
  445. curr->prev = tmp;
  446. break;
  447. }
  448. else
  449. {
  450. tmp =curr;
  451. }
  452. curr = curr->next;
  453. }
  454. }
  455. }
  456. /*pop_back()函数删除链表的最后一个元素。*/
  457. void pop_back()
  458. {
  459. curr = head->prev;
  460. node<T>* tmp = head->prev->prev;
  461. tmp->next = head;
  462. head->prev = tmp;
  463. free(curr);
  464. curr = NULL;
  465. }
  466. /*pop_front()函数删除链表的第一个元素。*/
  467. void pop_front()
  468. {
  469. curr = head->next;
  470. node<T>* tmp = head->next->next;
  471. head->next = tmp;
  472. tmp->prev = head;
  473. free(curr);
  474. curr = NULL;
  475. }
  476. /* push_back()将val连接到链表的最后*/
  477. void push_back(const T& value)
  478. {
  479. node<T>* newnode = new node<T>(value) ;
  480. if (head == NULL)
  481. {
  482. head = new node<T>(value);
  483. curr = head;
  484. }
  485. else
  486. {
  487. curr = head->prev;
  488. }
  489. curr->next = newnode;
  490. newnode->prev = curr;
  491. curr = newnode;
  492. newnode = NULL;
  493. curr->next = head;
  494. head->prev = curr;
  495. }
  496. /*push_front函数将val连接到链表的头部。*/
  497. void push_front(const T& value)
  498. {
  499. node<T>* newnode = new node<T>(value) ;
  500. if (head == NULL)
  501. {
  502. head = new node<T>(value);
  503. curr = head;
  504. curr->next = newnode;
  505. newnode->next = curr;
  506. curr = newnode;
  507. newnode = NULL;
  508. curr->next = head;
  509. head->prev = curr;
  510. }
  511. else
  512. {
  513. curr = head;
  514. newnode->next = curr->next;
  515. curr->next = newnode;
  516. curr = newnode;
  517. newnode = NULL;
  518. curr->prev = head;
  519. curr->next->prev = curr;
  520. }
  521. }
  522. /*remove()函数删除链表中所有值为val的元素*/
  523. void remove(const T & value)
  524. {
  525. node<T>* tmp = head;
  526. curr = head->next;
  527. while (curr != head)
  528. {
  529. if (curr->data == value)
  530. {
  531. tmp->next = curr->next;
  532. curr->next->prev = tmp;
  533. free(curr);
  534. curr = NULL;
  535. curr = tmp;
  536. }
  537. else
  538. {
  539. tmp = curr;
  540. }
  541. curr = curr->next;
  542. }
  543. }
  544. /*remove_if()以一元谓词pr为判断元素的依据，遍历整个链表
  545. 如果pr返回true则删除该元素。*/
  546. void remove_if(Unperd pr)
  547. {
  548. node<T>* tmp = head;
  549. curr = head->next;
  550. while (curr != head)
  551. {
  552. if (pr(curr->data))
  553. {
  554. tmp->next = curr->next;
  555. curr->next->prev = tmp;
  556. free(curr);
  557. curr = NULL;
  558. curr = tmp;
  559. }
  560. else
  561. {
  562. tmp = curr;
  563. }
  564. curr = curr->next;
  565. }
  566. }
  567. /*resize()函数把list的大小改变到num。被加入的多余的元素都被赋值为val*/
  568. void resize(int num,T value)
  569. {
  570. int record = 0;
  571. curr = head->next;
  572. iterator point;
  573. while (curr != head)
  574. {
  575. ++record;
  576. if (record == num)
  577. {
  578. point = iterator(curr);
  579. }
  580. curr = curr->next;
  581. }
  582. if (record < num)
  583. {
  584. while (record != num)
  585. {
  586. node<T>* newnode = new node<T>(value);
  587. curr = head->prev;
  588. curr->next = newnode;
  589. newnode->prev = curr;
  590. curr = newnode;
  591. newnode = NULL;
  592. curr->next = head;
  593. head->prev = curr;
  594. record++;
  595. }
  596. }
  597. if (record > num)
  598. {
  599. erase(point,iterator(head));
  600. }
  601. }
  602. /*reverse()函数把list所有元素倒转。*/
  603. void reverse()
  604. {
  605. mylist<T> list(*this);
  606. node<T>* tmp = list.head->prev;
  607. this->curr = this->head->next;
  608. while (this->curr != this->head)
  609. {
  610. this->curr->data = tmp->data;
  611. tmp = tmp->prev;
  612. this->curr = this->curr->next;
  613. }
  614. }
  615. /*size()函数返回list中元素的数量。*/
  616. int size()
  617. {
  618. curr = head->next;
  619. int num = 0;
  620. while (curr != head)
  621. {
  622. num++;
  623. curr = curr->next;
  624. }
  625. return num;
  626. }
  627. /*sort()函数为链表排序，默认是升序*/
  628. void sort()
  629. {
  630. curr = head->next;
  631. node<T>* tmp;
  632. tmp =  head->next->next;
  633. int temp = 0;
  634. int n = size();
  635. int i = 0;
  636. int flag = 0;
  637. while (tmp != head)
  638. {
  639. if (curr->data > tmp->data)
  640. {
  641. flag = 1;
  642. temp = tmp->data;
  643. tmp->data = curr->data;
  644. curr->data = temp;
  645. }
  646. i++;
  647. curr = curr->next;
  648. tmp = tmp->next;
  649. if ((i == n-1)&&(flag == 1))
  650. {
  651. flag = 0;
  652. i = 0;
  653. curr = head->next;
  654. tmp = head->next->next;
  655. }
  656. }
  657. }
  658. /* void sort( Comp compfunction );
  659. 如果指定compfunction的话，就采用指定函数来判定两个元素的大小*/
  660. void sort(Comp compfunction)
  661. {
  662. curr = head->next;
  663. node<T>* tmp;
  664. tmp =  head->next->next;
  665. int temp = 0;
  666. int n = size();
  667. int i = 0;
  668. int flag = 0;
  669. while (tmp != head)
  670. {
  671. if (compfunction(curr->data,tmp->data))
  672. {
  673. flag = 1;
  674. temp = tmp->data;
  675. tmp->data = curr->data;
  676. curr->data = temp;
  677. }
  678. i++;
  679. curr = curr->next;
  680. tmp = tmp->next;
  681. if ((i == n-1)&&(flag == 1))
  682. {
  683. flag = 0;
  684. i = 0;
  685. curr = head->next;
  686. tmp = head->next->next;
  687. }
  688. }
  689. }
  690. /*void splice( iterator pos, list &lst );splice()函数把lst连接到pos的位置*/
  691. void splice(iterator pos,mylist & list)
  692. {
  693. this->curr = this->head->next;
  694. node<T>* tmp = this->head;
  695. while (this->curr != this->head)
  696. {
  697. if (iterator(this->curr) == pos)
  698. {
  699. tmp->next = list.head->next;
  700. list.head->prev->next = this->curr->next;
  701. this->curr->next->prev = list.head->prev;
  702. list.head->prev = tmp;
  703. free(this->curr);
  704. this->curr = NULL;
  705. free(list.head);
  706. list.head = NULL;
  707. break;
  708. }
  709. else
  710. {
  711. tmp = this->curr;
  712. }
  713. this->curr = this->curr->next;
  714. }
  715. }
  716. /* void splice( iterator pos, list &lst, iterator del );*/
  717. void splice(iterator pos,mylist & list,iterator del)
  718. {
  719. this->curr = this->head->next;
  720. list.curr = list.head->next;
  721. node<T>* tmp = list.head;
  722. while (this->curr != this->head)
  723. {
  724. if (iterator(this->curr) == pos)
  725. {
  726. while (list.curr != list.head)
  727. {
  728. if (iterator(list.curr) == del)
  729. {
  730. this->curr->data = list.curr->data;
  731. tmp->next = list.curr->next;
  732. curr->next->prev = tmp;
  733. free(list.curr);
  734. list.curr;
  735. break;
  736. }
  737. else
  738. {
  739. tmp = list.curr;
  740. }
  741. list.curr = list.curr->next;
  742. }
  743. break;
  744. }
  745. this->curr = this->curr->next;
  746. }
  747. }
  748. /* void splice( iterator pos, list &lst, iterator start, iterator end );*/
  749. void splice(iterator pos,mylist & list,iterator start,iterator end)
  750. {
  751. list.curr = list.head;
  752. node<T>* point = list.head;
  753. node<T>* point1 = list.head;
  754. iterator it = this->erase(pos);
  755. while (iterator(list.curr) != start)
  756. {
  757. list.curr = list.curr->next;
  758. }
  759. point = list.curr->prev;
  760. while(iterator(list.curr->prev) != end)
  761. {
  762. this->insert(it,list.curr->data);
  763. list.curr = list.curr->next;
  764. }
  765. point1 = list.curr;
  766. list.erase(point,point1);
  767. }
  768. /*swap()函数交换lst和现链表中的元素*/
  769. void swap(mylist & list)
  770. {
  771. int flag1 = 0;//记录交换时那个链表过长需要删除
  772. int flag2 = 0;//这里其实只要一个标志  但是为了方便故设置两个
  773. mylist<T> tmp(list);
  774. list.curr = list.head->next;
  775. this->curr = this->head->next;
  776. while (this->curr != this->head)
  777. {
  778. if (list.curr != list.head)
  779. {
  780. list.curr->data =  this->curr->data;
  781. list.curr = list.curr->next;
  782. }
  783. else
  784. {
  785. flag1 = 1;
  786. list.push_back(this->curr->data);
  787. }
  788. this->curr = this->curr->next;
  789. }
  790. if ((list.curr != list.head)&& (flag1 == 0))
  791. {
  792. list.erase(iterator(list.curr->prev),iterator(list.head));
  793. }
  794. tmp.curr = tmp.head->next;
  795. this->curr = this->head->next;
  796. while (tmp.curr != tmp.head)
  797. {
  798. if (this->curr != this->head)
  799. {
  800. this->curr->data =  tmp.curr->data;
  801. this->curr = this->curr->next;
  802. }
  803. else
  804. {
  805. flag2 = 1;
  806. this->push_back(tmp.curr->data);
  807. }
  808. tmp.curr = tmp.curr->next;
  809. }
  810. if ((this->curr != this->head)&& (flag2 == 0))
  811. {
  812. this->erase(iterator(this->curr->prev),iterator(this->head));
  813. }
  814. }
  815. /* void unique();unique()函数删除链表中所有重复的元素。*/
  816. void unique()
  817. {
  818. curr = head->next->next;
  819. node<T>* tmp = head->next;
  820. while (curr != head)
  821. {
  822. if (tmp->data == curr->data)
  823. {
  824. tmp->next = curr->next;
  825. curr->next->prev = tmp;
  826. free(curr);
  827. curr = NULL;
  828. curr = tmp->next;
  829. }
  830. tmp = tmp->next;
  831. curr = curr->next;
  832. }
  833. }
  834. /* void unique( BinPred pr );
  835. 指定pr，则使用pr来判定是否删除*/
  836. void unique(BinPred pr)
  837. {
  838. curr = head->next->next;
  839. node<T>* tmp = head->next;
  840. while (curr != head)
  841. {
  842. if ((tmp->data == curr->data)&&pr(curr->data))
  843. {
  844. tmp->next = curr->next;
  845. curr->next->prev = tmp;
  846. free(curr);
  847. curr = NULL;
  848. curr = tmp->next;
  849. }
  850. tmp = tmp->next;
  851. curr = curr->next;
  852. }
  853. }
  854. private:
  855. node<T> *head;
  856. node<T> *curr;
  857. };
  858. template <class T>
  859. bool dis_tinet( T value)
  860. {
  861. if (9 == value)
  862. return true;
  863. return false;
  864. }
  865. template <class T>
  866. bool sortfunction(T a,T b)
  867. {
  868. if (a < b)
  869. return true;
  870. return false;
  871. }
  872. template <class T>
  873. bool unique_t( T value)
  874. {
  875. if (8 == value)
  876. return true;
  877. return false;
  878. }
上一篇：Java、C#双语版HttpHelper类


下一篇：WinForm利用AForge.NET调用电脑摄像头进行拍照和视频