顺序表的插入学习教案

《顺序表的插入学习教案》由会员分享，可在线阅读，更多相关《顺序表的插入学习教案（87页珍藏版）》请在装配图网上搜索。

1、会计学1顺序顺序(shnx)表的插入表的插入第一页，共87页。a1a2a3a4a5a62第2页/共87页第二页，共87页。时时 0 0, ,) )( (时时 0 0, ,) )( (iliLOCiiLOC1LOC ( i ) = LOC ( i - -1 ) + l =+ i*l3第3页/共87页第三页，共87页。4第4页/共87页第四页，共87页。525 s 3.3 62 74 t 1.0 6 第5页/共87页第五页，共87页。6第6页/共87页第六页，共87页。7第7页/共87页第七页，共87页。8第8页/共87页第八页，共87页。9第9页/共87页第九页，共87页。10第10页/共87页

2、第十页，共87页。 x = 48 x = 5011第11页/共87页第十一页，共87页。212)(11)2(111=1nnnnnninACNni (假设表的长度为假设表的长度为n,即即n = last + 1)12niiic*pACN1=第12页/共87页第十二页，共87页。13第13页/共87页第十三页，共87页。14第14页/共87页第十四页，共87页。在表中第在表中第 i 个位置插入，从个位置插入，从datai-1 到到data last 成块后移，移动成块后移，移动n-1-(i-1)+1 = n-i+1项项 (假设表的长度为假设表的长度为n,即即n = last + 1)221)(1)

3、(1 0)1(111)(11=11nnnnnninnniAMN15第15页/共87页第十五页，共87页。16第16页/共87页第十六页，共87页。17第17页/共87页第十七页，共87页。删除第删除第 i 个表项，需将第个表项，需将第 i+1 项到第项到第 last+1项全部前移，需前移的项数为项全部前移，需前移的项数为 n-(i+1)+1 = n-i (假设表的长度为假设表的长度为n,即即n = last + 1)ninnnninn12121)(1)(1=AMN18第18页/共87页第十八页，共87页。void Union ( SeqList & LA, SeqList & LB ) int

4、 n = LA.Length ( ); int m = LB.Length ( ); int x; for ( int i = 1; i = m; i+ ) LB.getData(i, x); /在在LB中取一元素中取一元素 int k = LA.Search (x); /在在LA中搜中搜索索(su su)它它 if ( k = 0 ) /若未找到插入它若未找到插入它 LA.Insert (n, x); n+; 19第19页/共87页第十九页，共87页。 void Intersection ( SeqList & LA, SeqList & LB ) int n = LA.Length ( )

5、; int m = LB.Length ( ); int i = 1; int x; while ( i link = current-link; current-link = newNode;firstnewNodefirstnewNode插入firstnewNode0firstnewNode0插入currentcurrentcurrentcurrent39第39页/共87页第三十九页，共87页。 del = current-link; current-link = del-link; delete del; ( (非空表）非空表）( (空表）空表）firstfirstfirst0first

6、0currentdelcurrentdel40第40页/共87页第四十页，共87页。41第41页/共87页第四十一页，共87页。42第42页/共87页第四十二页，共87页。43第43页/共87页第四十三页，共87页。44第44页/共87页第四十四页，共87页。45第45页/共87页第四十五页，共87页。46第46页/共87页第四十六页，共87页。搜索搜索(su su)不成功不成功循环循环(xnhun)链表的链表的搜索算法搜索算法搜索搜索(su su)25搜索成功搜索成功搜索搜索15first31481557 current current currentfirst31481557 curren

7、t current current currentcurrent47第47页/共87页第四十七页，共87页。循环(xnhun)链表的搜索算法template CircListNode * CircList:Search( E x ) /在链表中从头搜索在链表中从头搜索(su su)其数据值为其数据值为 x 的结点的结点 current = first-link; while ( current != first & current-data != x ) current = current-link; return current;48第48页/共87页第四十八页，共87页。49第49页/共8

8、7页第四十九页，共87页。50第50页/共87页第五十页，共87页。51第51页/共87页第五十一页，共87页。 l lL Li in nk k( (左左左左 链链链链 指指指指 针针针针 ) ) d da at ta a( (数数数数 据据据据 ) ) r rL Li in nk k( (右右右右 链链链链 指指指指 针针针针 ) )52第52页/共87页第五十二页，共87页。53第53页/共87页第五十三页，共87页。54第54页/共87页第五十四页，共87页。55第55页/共87页第五十五页，共87页。56第56页/共87页第五十六页，共87页。搜索成功搜索成功搜索不成功搜索不成功fir

9、stfirst3131484815155757搜索搜索15 搜索搜索25 57第57页/共87页第五十七页，共87页。58第58页/共87页第五十八页，共87页。双向循环链表的插入双向循环链表的插入(ch r)(ch r)算算法法 ( (非空表非空表) )newNode-rLink = current-rLink; current-rLink = newNode;newNode-rLink-lLink = newNode; newNode-lLink = current;firstfirst31481525currentnewNode31482515current59第59页/共87页第五十九

10、页，共87页。双向循环链表的插入双向循环链表的插入(ch r)(ch r)算法算法 ( (空表空表) )firstcurrentnewNode25firstcurrentnewNode-rLink = current-rLink (newNode-rLink = first); current-rLink = newNode;newNode-rLink -lLink = newNode; ( first-lLink = newNode ) newNode-lLink = current;60第60页/共87页第六十页，共87页。61第61页/共87页第六十一页，共87页。62第62页/共87页

11、第六十二页，共87页。删除删除(shnch)48双向循环双向循环(xnhun)链表的删除链表的删除算法算法firstfirst314815current3115currentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink;63第63页/共87页第六十三页，共87页。64第64页/共87页第六十四页，共87页。iniinnnxaxaxaxaaxP02210 )(A(x) = 1 - 10 x6 + 2x8 +7x1465第65页/共87页第六十五页，共87页。 66a0 a1 a2 an 0 1 2

12、 degree maxDegree- -1coefn第66页/共87页第六十六页，共87页。67第67页/共87页第六十七页，共87页。a0 a1 a2 ai ame0 e1 e2 ei emcoefexp0 1 2 i m68第68页/共87页第六十八页，共87页。初始化：初始化：/ term Polynomial:termArraymaxTerms;/ int Polynomial:free = 0;class Polynomial /多项式定义多项式定义 public: private: int start, finish; /多项式始末多项式始末(shm)位置位置69第69页/共87页

13、第六十九页，共87页。两个多项式存储两个多项式存储(cn ch)的例子的例子 A(x) = 2.0 x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101 两个(lin )多项式存放在termArray中A.start A.finish B.start B.finish freecoefexp1.8 2.0 1.2 51.3 3.7 0 1000 0 50 101 maxTerms70第70页/共87页第七十页，共87页。数据数据(shj(shj)域域指针指针(zhzh(zhzhn)n)域域A(x) = 1 - 10 x6 + 2x8 +7x1471第71页/共87页

14、第七十一页，共87页。72第72页/共87页第七十二页，共87页。73第73页/共87页第七十三页，共87页。74第74页/共87页第七十四页，共87页。75第75页/共87页第七十五页，共87页。76第76页/共87页第七十六页，共87页。AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 1477第77页/共87页第七十七页，共87页。AH.firstBH.first CH.first1 0-1 4-3 63 6-9 107 128 14papcpb 78第78页/共87页第七十八页，共87页。AH.

15、first CH.first 1 01 0-1 4-3 63 6-9 107 128 14papbpcBH.first79第79页/共87页第七十九页，共87页。AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.first80第80页/共87页第八十页，共87页。AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.firsttmp = -3+3 = 081第81页/共87页第八十一页，共87页。AH.first CH.first1 01 0-1 4-1

16、4-3 63 6-9 107 128 14papc-9 10pbBH.first 82第82页/共87页第八十二页，共87页。AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first7 12 83第83页/共87页第八十三页，共87页。AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first7 128 14 p84第84页/共87页第八十四页，共87页。n为数组中每一个元素附加一个链接指针，就形成静态为数组中每一个元素附加一个链

17、接指针，就形成静态链表结构。链表结构。n静态链表每个结点由两个数据成员构成：静态链表每个结点由两个数据成员构成：datadata域存储域存储数据，数据，linklink域存放链接指针。域存放链接指针。n处理处理(chl)(chl)时可以不改变各元素的物理位置，只要时可以不改变各元素的物理位置，只要重新链接就能改变这些元素的逻辑顺序。重新链接就能改变这些元素的逻辑顺序。n它是利用数组定义的，在整个运算过程中存储空间的它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。大小不会变化。85第85页/共87页第八十五页，共87页。86012345dataa3a4a1a5a2link3245-1(0)1a1a2a3a4a5first第86页/共87页第八十六页，共87页。感谢您的观看感谢您的观看(gunkn)！第87页/共87页第八十七页，共87页。