表的插入和刪除,表的應(yīng)用實(shí)例

1、算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu) 表表list的插入和刪除的插入和刪除表的應(yīng)用實(shí)例表的應(yīng)用實(shí)例 表的插入和刪除表的插入和刪除n 表的最突出的特點(diǎn)就是可以高效的插入和刪除。表的最突出的特點(diǎn)就是可以高效的插入和刪除。n n 插入操作：插入操作： n iterator insert (iterator pos, const T&value)n 在在pos前前插入插入一個(gè)值為一個(gè)值為value的元素，的元素，返回返回指向指向value值所在位置的值所在位置的迭代器迭代器，不影響現(xiàn)在的迭代器，不影響現(xiàn)在的迭代器pos 例如：在例如：在iter位置前插入位置前插入4 插入之后，返回指向新元素插入之后，

2、返回指向新元素4的迭的迭代器代器newIter，原原iter不變不變 例例 : 復(fù)制表中的每個(gè)元素作為相鄰元素復(fù)制表中的每個(gè)元素作為相鄰元素n template n void doubleData ( list& aList)nn typename list:iterator p = aList.begin();n while(p!=aList.end()n n aList.insert(p, *p);n p+;n n如果寫成如果寫成 p=aList.insert(p, *p); p指向哪里？指向哪里？ 刪除表中的元素刪除表中的元素nvoid erase(iterater pos)n

3、刪除刪除pos指向的表元素，刪除后指向的表元素，刪除后 pos迭代迭代器不指向什么元素了器不指向什么元素了，pos失效了失效了,如果還如果還要使用要使用pos，要重新初始化，要重新初始化 例如例如 從表中刪除從表中刪除7 刪除前，刪除前，iter先指向了先指向了7erase(iter)之后之后 ，7刪除了，同刪除了，同時(shí)時(shí) iter迭代器失效了迭代器失效了！ 為了使為了使刪除刪除操作執(zhí)行之后，操作執(zhí)行之后，迭代迭代器能指向下一個(gè)元素器能指向下一個(gè)元素n可以在可以在erase調(diào)用中使用調(diào)用中使用+運(yùn)算運(yùn)算n即即 erase(iter+);n Iter例：刪除表中小于目標(biāo)值的元素例：刪除表中小于目

4、標(biāo)值的元素ntemplate nvoid eraseSmallValues ( list& aList, const T& target)n n typename list:iterator iter= alist.begin();n while(iter!=aList.end()n n if(*iter target)n aList.erase( iter+ ); n elsen iter+;n n 刪除表中一段元素刪除表中一段元素n void erase( iterator first, iterator last)建立一個(gè)有序表建立一個(gè)有序表n表中數(shù)據(jù)已有序，插入元素后仍

5、有序表中數(shù)據(jù)已有序，插入元素后仍有序n template nvoid insertOrder (list& orderedList, const T& item)n例如在下表中插入例如在下表中插入50、70、90 insertOrder算法算法n 掃描表掃描表n 為新數(shù)據(jù)確定正確的位置為新數(shù)據(jù)確定正確的位置currn 然后在然后在curr之前插入它之前插入它插入插入50n 表中第一個(gè)元素是表中第一個(gè)元素是60，6050， 所以所以curr就是就是60所在的位置，所在的位置， 把把50插入到插入到60的前面的前面即可即可插入插入70n 從表中第一個(gè)元素開始與從表中第一個(gè)元素開始與

6、70比較，比較，發(fā)現(xiàn)發(fā)現(xiàn)74大于大于70，所以，所以curr就是就是74所在的位置，所在的位置， 把把70插入到插入到74的前面即可的前面即可插入插入90n 從表中第一個(gè)元素開始與從表中第一個(gè)元素開始與90比較，比較，所有的所有的元素都小于元素都小于90，所以，所以curr是表的是表的end()位置位置，把把90插入到插入到end()之前即可之前即可 insertOrder的實(shí)現(xiàn)的實(shí)現(xiàn)n 在在 d_listl.h可以找到可以找到ntemplate nvoid insertOrder(list& orderedList, const T& item)nn typename lis

7、t:iterator curr = orderedList.begin(),n stop = orderedList.end();n while (curr != stop) & (*curr item)n curr+;n orderedList.insert(curr, item);n 刪除表中多余的重復(fù)元素刪除表中多余的重復(fù)元素n template n void removeDuplicates (list& aList)n需要兩個(gè)迭代器需要兩個(gè)迭代器n 一個(gè)是一個(gè)是curr迭代器迭代器，用來掃描表，每個(gè)，用來掃描表，每個(gè)curr指向的值作為指向的值作為目標(biāo)值目標(biāo)值n另一個(gè)

8、迭代器是另一個(gè)迭代器是 p指向指向curr的相鄰值的相鄰值n 如果如果 *p = *curr 則則erase (p+)n 否則否則p+ ntemplate nvoid removeDuplicates(list& aList)nn T currValue;n list:iterator curr, p;n curr = aList.begin();n while(curr != aList.end()n n currValue = *curr;n p = curr;n p+;n while( p != aList.end() )n if (*p = currValue) aList.e

9、rase(p+);n elsen p+;n curr+;n n沒有重復(fù)項(xiàng)的有序表沒有重復(fù)項(xiàng)的有序表n建立了有序表之后，刪除重復(fù)就得到?jīng)]有建立了有序表之后，刪除重復(fù)就得到?jīng)]有重復(fù)項(xiàng)的有序表重復(fù)項(xiàng)的有序表 合并合并(拼接拼接splice)表表n在表指定位置在表指定位置pos前拼接另一個(gè)表前拼接另一個(gè)表ntemplate nvoid splice (list& dest, n typename list:iterator pos,n const list& source); 解決開始提出的問題解決開始提出的問題n 1 學(xué)生信息管理學(xué)生信息管理n 順序?qū)W生表順序?qū)W生表seqStuLis

10、tn 見工程見工程 studentVector 參考教材例（參考教材例（C語言版的）語言版的）nstruct stud /默認(rèn)的都是默認(rèn)的都是publicn string number;n string name;n bool leaveSchool;n /構(gòu)造函數(shù)構(gòu)造函數(shù)n stud (string no=, string na=, bool ls=false):n number(no),name(na),leaveSchool(ls) ;n; nclass stulistnnpublic:n stulist()size=0;n void insertstu(stud s); /append

11、 studn int deletestu(int i); /set stus leaveschool is falsen void createlist(stud s,int sz);/make vector by using stud array;n void printlist();nprivate:n vector slist;n int size;n ; 測試測試nint main()nn stulist slist1;n stud s2=stud(00001,aaaaa,true),stud(00002,bbbbb,true);n stud t(00003,ccccc,true);n

12、 slist1.createlist(s,2);n slist1.insertstu(t);n slist1.printlist();n slist1.deletestu(2);n slist1.printlist();n return 0;n 多項(xiàng)式運(yùn)算多項(xiàng)式運(yùn)算n 只用系數(shù)描述多項(xiàng)式時(shí)，如果多項(xiàng)式的項(xiàng)只用系數(shù)描述多項(xiàng)式時(shí)，如果多項(xiàng)式的項(xiàng)不規(guī)則時(shí)就難以表達(dá)不規(guī)則時(shí)就難以表達(dá)n p(x) = 3x2 +2x150+5x200n 這樣的表示這樣的表示 P = (p0, p1, ，pn)？結(jié)果是什么？n 如果不僅使用系數(shù)，還包括指數(shù)n 就可以建立表 (3,2),(2,150),(5,200) n

13、多項(xiàng)式表具有不規(guī)則性，用鏈?zhǔn)酱鎯?chǔ)比較方便 多項(xiàng)式項(xiàng)的定義多項(xiàng)式項(xiàng)的定義nstruct polyItemn double coef;n int expn;n polyItem() expn=-1; n polyItem (double cf, int en);n;npolyItem:polyItem(double cf, int en)nn coef=cf;n expn=en;n 多項(xiàng)式表多項(xiàng)式表nclass polynomialnpublic:n polynomial() ;n polynomial(const polynomial &copy);n polynomial(const

14、list &copyList);n polynomial() ;n int length(); bool isZero() const;n void setZero() ; void display();n void insertItem(const polyItem &item);n polynomial operator+(const polynomial &p) const;n polynomial operator-(const polynomial &p) const;n polynomial &operator=(const list &am

15、p;copyList);n polynomial &operator=(const polynomial &copy);nprivate:n list polyList;n;n詳細(xì)代碼見詳細(xì)代碼見polylist工程工程大整數(shù)問題大整數(shù)問題nclass CLargeIntnnprivate:n list num;npublic:n CLargeInt& Multi10Power(unsigned int exponent);/ 乘乘10的階冪的階冪10exponentn CLargeInt operator *(unsigned int digit); / 乘法運(yùn)算符重

16、載乘法運(yùn)算符重載(乘以乘以1位數(shù)位數(shù))n CLargeInt(unsigned int n);/ 構(gòu)造函數(shù)構(gòu)造函數(shù)n CLargeInt &operator =(const CLargeInt &copy);/ 賦值運(yùn)算符重載賦值運(yùn)算符重載n unsigned int size()return num.size();n CLargeInt operator +(const CLargeInt &b);/ 加法運(yùn)算符加法運(yùn)算符+重載重載n CLargeInt operator *(CLargeInt &b);/ 乘法運(yùn)算符乘法運(yùn)算符*重載重載friend ostr

17、eam &operator num.push_front(r);/ 插入到雙向鏈表中插入到雙向鏈表中nq = q / 10;/ 進(jìn)一步求高位進(jìn)一步求高位nnnCLargeInt CLargeInt:operator+( const CLargeInt &b)n/ 操作結(jié)果：加法運(yùn)算符操作結(jié)果：加法運(yùn)算符+重載重載nnCLargeInt c(0);nunsigned int carry = 0;/ 進(jìn)位進(jìn)位nlist lb;n lb=b.num;nlist:reverse_iterator ria=num.rbegin();nlist:reverse_iterator rib=l

18、b.rbegin();nfor(;ria!=num.rend()&rib!=lb.rend();ria+,rib+)n n c.num.push_front(*ria)+(*rib)+carry)%10);n carry=(*ria)+(*rib)+carry)/10;n n while(ria!=num.rend()n n c.num.push_front(*ria)+carry)%10);n carry=(*ria)+carry)/10;n ria+;n n while(rib!=lb.rend()n n c.num.push_front(*rib)+carry)%10);n ca

19、rry=(*rib)+carry)/10;n rib+;n n if(carry!=0)n c.num.push_front(carry);n return c;nn 詳細(xì)代碼見工程詳細(xì)代碼見工程biginteger約瑟夫環(huán)問題約瑟夫環(huán)問題n有有n個(gè)人圍成一圈，（假設(shè)他們的編號(hào)沿順時(shí)針方向依次個(gè)人圍成一圈，（假設(shè)他們的編號(hào)沿順時(shí)針方向依次為為1到到n），而后從），而后從1號(hào)人員開始報(bào)數(shù)（沿順時(shí)針方向），號(hào)人員開始報(bào)數(shù)（沿順時(shí)針方向），數(shù)到數(shù)到3者者被被“淘汰出局淘汰出局”；然后從下一個(gè)人重新從；然后從下一個(gè)人重新從1開始報(bào)開始報(bào)數(shù)，數(shù)到數(shù)，數(shù)到3后，淘汰第二個(gè)人；依此類推，直到最后剩下后，淘汰

20、第二個(gè)人；依此類推，直到最后剩下二人為止。這個(gè)問題當(dāng)二人為止。這個(gè)問題當(dāng)n=41時(shí)便是約瑟夫環(huán)那個(gè)歷史故事。時(shí)便是約瑟夫環(huán)那個(gè)歷史故事。寫一個(gè)程序，依次輸出被寫一個(gè)程序，依次輸出被“淘汰淘汰”的人和最后留下的人的的人和最后留下的人的編號(hào)，要求用鏈表來實(shí)現(xiàn)。編號(hào)，要求用鏈表來實(shí)現(xiàn)。n輸入樣例：輸入樣例：n41n輸出樣例：輸出樣例：n3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35n16 31 實(shí)例研究：畢業(yè)生表實(shí)例研究：畢業(yè)生表n問

21、題描述：問題描述：n 某高校的畢業(yè)生有文學(xué)學(xué)士，理學(xué)學(xué)士，教務(wù)某高校的畢業(yè)生有文學(xué)學(xué)士，理學(xué)學(xué)士，教務(wù)主任要確定哪些畢業(yè)生能夠畢業(yè)，報(bào)送給校長，主任要確定哪些畢業(yè)生能夠畢業(yè)，報(bào)送給校長，校長要從教務(wù)主任的文件中去掉那些不能參加典校長要從教務(wù)主任的文件中去掉那些不能參加典禮的學(xué)生，生成一張按字母序排序的名字表，且禮的學(xué)生，生成一張按字母序排序的名字表，且理學(xué)學(xué)士的學(xué)生在前，校長在典禮的時(shí)候按名單理學(xué)學(xué)士的學(xué)生在前，校長在典禮的時(shí)候按名單頒發(fā)證書。頒發(fā)證書。n分析：分析：n 每個(gè)合格學(xué)生的信息包括：名字、學(xué)位類型每個(gè)合格學(xué)生的信息包括：名字、學(xué)位類型（文還是理）（文還是理） 建立一個(gè)畢業(yè)生類建立一

22、個(gè)畢業(yè)生類，存儲(chǔ)在，存儲(chǔ)在文件文件中中n 不能參加畢業(yè)典禮的學(xué)生存儲(chǔ)在不能參加畢業(yè)典禮的學(xué)生存儲(chǔ)在另一個(gè)文件中另一個(gè)文件中n 最后生成在典禮上頒發(fā)證書的學(xué)生名單最后生成在典禮上頒發(fā)證書的學(xué)生名單 nclass graduatennpublic:graduate()string getDegree() const return degree; friend bool operator= (const graduate& lhs, const graduate& rhs)n return = ;friend bool operator (const

23、 graduate& lhs, const graduate& rhs)n return (istream& istr, graduate& grad)nn getline(istr, ,t);n getline(istr, grad.degree,n);n return istr;friend ostream& operator (ostream& ostr, const graduate& grad)nn ostr.setf(ios:left, ios:adjustfield); n ostr se

24、tw(20) grad.degree; n ostr.setf(ios:right, ios:adjustfield);n return ostr;nprivate:nstring name;nstring degree;n;畢業(yè)生類畢業(yè)生類 n nPeterson, BradleyBA /Bachelor of Arts nFrazer, ThomasBAnHarnes, BaileyBAnKilmer, WilliamBAnBarnes, NancyBS /Bachelor of Science nMiller, SaraBSnNeeson, RebeccaBSnBailey, Julie BSnNelson, HaroldBSnODell, JackBAnJohnson, ShannonBSnnFFrazer, ThomasBAnJohnson, ShannonBSnBarnes, NancyBS 從合格學(xué)生表中刪除一個(gè)不參加典禮的學(xué)生從合格學(xué)生表中刪除一個(gè)不參加典禮的學(xué)生nvoid removeGraduate(list& gradList, const graduate& grad)nnlist:iterator iter =nseqSearch