雙向循環(huán)鏈表list

1、list是雙向循環(huán)鏈表，每一個元素都知道前面一個元素和后面一個元素。在STL中，list和vector 一樣，是兩個常被使用的容器。和vector不一樣的是，list不支持對元素的任意存取。list中提供的成員函數(shù)與vector類似，不過list提供對表首元素 的操作 push_front、pop_front，這是 vector不具備的。禾口 vector另一點不同的是， list的迭代器不會存在失效的情況，他不像 vector會保留備份空間，在超過容量額 度時重新全部分配內(nèi)存，導致迭代器失效；list沒有備份空間的概念，出入一個元素 就申請一個元素的空間，所以它的迭代器不會失效。還是舉C+之

2、vector中的例子：int data6=3,5,7,9,2,4;list lidata(data, data+6);lidata.push_back(6);list初始化時，申請的空間大小為 6，存放下了 data中的6個元素，當向lidata插 入第7個元素“6”，list申請新的節(jié)點單元，插入到list鏈表中，數(shù)據(jù)存放結(jié)構(gòu)如圖 1所示：3H57W924-6插入節(jié)點6拆之后的list圖1 list的存儲結(jié)構(gòu)list每次增加一個元素，不存在重新申請內(nèi)存的情況，它的成本是恒定的。而 vector每當增加關(guān)鍵元素的時候，都需要重新申請新的更大的內(nèi)存空間，會調(diào)用元 素的自身的復制構(gòu)造函數(shù)，存在構(gòu)造

3、成本。在銷毀舊內(nèi)存的時候，會調(diào)用析構(gòu)函數(shù), 存在析構(gòu)成本。所以在存儲復雜類型和大量元素的情況下，list比vector更有優(yōu)勢！List是一個雙向鏈表,雙鏈表既可以向前又向后鏈接他的元素。List將元素按順序儲存在鏈表中.與向量(vector)相比,它允許快速的插 入和刪除，但是隨機訪問卻比較慢。assign()給 list 賦值back()返回最后一個元素begin()返回指向第一個元素的迭代器clear()刪除所有元素empty() 如果list是空的則返回trueen d()返回末尾的迭代器erase()刪除一個元素fron t()返回第一個元素get_allocator() 返回 li

4、st 的配置器insert()插入一個元素到list中max_size() 返回list能容納的最大元素數(shù)量merge()合并兩個listpop_back()刪除最后一個元素pop_fro nt()刪除第一個元素push_back()在list的末尾添加一個元素push_front()在list的頭部添加一個元素rbegi n()返回指向第一個元素的逆向迭代器remove() 從list刪除元素remove_if() 按指定條件刪除元素rend()指向list末尾的逆向迭代器 resize。 改變list的大小reverse。把list的元素倒轉(zhuǎn)size()返回list中的元素個數(shù) sort(

5、)給 list 排序 splice()合并兩個listswap()交換兩個listunique() 刪除list中重復的元素List使用實例1#in elude #in clude #in clude #i nclude using n amespace std;創(chuàng)建一個list容器的實例LISTINT typedef list LISTINT;創(chuàng)建一個list容器的實例LISTCHAR typedef list LISTCHAR;int main (i nt argc, char *argv)/用list容器處理整型數(shù)據(jù)/用LISTINT創(chuàng)建一個名為listOne的list對象LISTINT

6、 list One;/聲明i為迭代器LISTINT:iterator i;從前面向listOne容器中添加數(shù)據(jù)listO ne.push_fro nt (2);listO ne.push_fro nt (1);從后面向listOne容器中添加數(shù)據(jù)list On e.push_back (3);listO ne.push_back (4);從前向后顯示listOne中的數(shù)據(jù)coutlist On e.beg in()- list On e.e nd():e ndl;for (i = list On e.begi n(); i 匸 list On e.e nd(); +i) cout *i ;co

7、ut en dl;從后向后顯示listOne中的數(shù)據(jù)LISTINT:reverse_iterator ir;coutlistOne.rbegin()-list On e.re nd():ve ndl; for (ir =list On e.rbeg in (); ir!=list On e.re nd();ir+) cout *ir ;cout en dl;使用STL的accumulate(累加)算法int result = accumulate(list On e.beg in(), list On e.e nd(),0); coutSum二vvresultvve ndl;coute ndl

8、;/用list容器處理字符型數(shù)據(jù)/用LISTCHAR創(chuàng)建一個名為list One的list對象LISTCHAR listTwo;/聲明i為迭代器LISTCHAR:iterator j;/從前面向listTwo容器中添加數(shù)據(jù)listTwo.push_fro nt (A);listTwo.push_fro nt (B);/從后面向listTwo容器中添加數(shù)據(jù) listTwo.push_back (x); listTwo.push_back (y);從前向后顯示listTwo中的數(shù)據(jù)coutlistTwo.begin()-listTwo.e nd():ve ndl;for (j = listTwo.

9、begin(); j != listTwo.end(); +j)cout char(*j) ;cout en dl;使用STL的max_element算法求listTwo中的最大元素并顯示 j=max_eleme nt(listTwo.begi n( ),listTwo.e nd();cout The maximum eleme nt in listTwo is: vchar(*j)ve ndl;return 0;List使用實例2list: Lin ked list of variables, struct or objects. In sert/remove any where.Two e

10、xamples are give n:1. The first STL example is for data type int2. The sec ond for a list of class in sta nces.They are used to show a simple example and a more complex real world applicati on.1. Lets start with a simple example of a program using STL for a linked list:/ Simple example uses type int

11、#in clude #in clude using n amespace std;int mai n()list L;L.push_back(O);L.push_fro nt(0);L.i nsert(+L.beg in( ),2);/In sert a new eleme nt at the end/Insert a new eleme nt at the beg inning/ Insert 2 before position of first argument/ (Place before sec ond argume nt)L.push_back(5);L.push_back(6);l

12、ist :iterator i;for(i=L.begin(); i != L.end(); +i) cout *i ;cout en dl;return 0;Compile: g+ example1.cppRun: ./a.outOutput: 0 2 0 5 62. The STL tutorials and texts seem to give simple examples which do notapply to the real world. The following example is for a doubly linked list.Since we are using a

13、 class and we are not using defined built-in C+types we have in cluded the followi ng:* To make this example more complete, a copy con structor has bee nin cluded although the compiler will gen erate a member-wise one automatically if needed. This has the same functionality as the assignment operato

14、r (=). The assig nment (=) operator must be specified so that sort routi nes can assig n a new order to the members of the list. The less than () operator must be specified so that sort routines candetermine if one class instance is less than another. The equals to (=) operator must be specified so

15、that sort routines candetermine if one class instance is equals to another./ Stan dard Template Library example using a class.#in clude #in clude using n amespace std;/ The List STL template requires overloading operators =, = and .vc2005調(diào)試沒有錯(紅色字體部分可去掉)、可用vc6.0卻報錯了 “ operator is ambiguous ” (vc6.0的

16、加上紅色字體部分)class AAA;ostream &operator(ostream &output, const AAA &aaa);class AAAfrie nd ostream &operator(ostream &, const AAA &);public:int x;int y;float 乙AAA();AAA(co nst AAA &);AAA()；AAA & operator=(co nst AAA &rhs);int operator=(c onst AAA &rhs) con st;int operator(c onst AAA &rhs) con st;；AAA:AA

17、A()/ Con structorx = 0;y = 0;z = 0;AAA:AAA(c onst AAA © in)/ Copy con structor to han die pass by value.x = copy in.x;y = copyi n.y;z = copy in.z;ostream &operator(ostream &output, const AAA &aaa)output aaa.x aaa.y aaa.z x = rhs.x;this-y = rhs.y;this-z = rhs. z;return *this;int AAA:operator=(c o

18、nst AAA &rhs) constif( this-x != rhs.x) return 0;if( this-y != rhs.y) return 0;if( this-z != rhs.z) return 0;return 1;/ This function is required for built-in STL list functions like sortint AAA:operatorx = rhs.x & this-y = rhs.y & this-z x = rhs.x & this-y x rhs.x ) return 1;return 0;int mai n()list L;AAA Ablob ;Ablob.x=7;Ablob.y=2;Ablob.z=4.2355;L.push_back(Ablob); /In sert a new eleme