数据结构陈慧南学习教案

1、会计学1数据结构数据结构(sh j ji u)陈慧南陈慧南 第一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第1页/共70页第二页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 2.1 线性表ADT2.2 线性表的顺序表示2.3 线性表的链接(lin ji)表示2.4 多项式的算术运算 第2页/共70页第三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第3页/共70页第四页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 表长可以(ky)改变。第4页/共70页第五页，共70页。南京(nn j

2、n)邮电大学计算机学院陈慧南 2006年9月 第5页/共70页第六页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第6页/共70页第七页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第7页/共70页第八页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第8页/共70页第九页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 a0 a1 ai an-1 0 1 i n-1 maxLength-1第9页/共70页第十页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第10页/共7

3、0页第十一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 SingleListLinearListSeqList第11页/共70页第十二页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 private:/私有数据 int maxLength;/顺序表的最大长度(chngd) T *elements;/动态一维数组的指针; 第12页/共70页第十三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第13页/共70页第十四页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第14页/共70页第十五页，共

4、70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 x=elementsi; 渐近时间复杂度：O(1) a0 a1 ai an-1 0 1 i n-1 maxLength-1第15页/共70页第十六页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool SeqList:Find(int i,T& x) const /O(1) if (in1) /对i进行越界检查 coutOut of Boundsendl; return false; x=elementsi; /通过引用参数x返回下标(xi bio)为i的元素 return true

5、;第16页/共70页第十七页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第17页/共70页第十八页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第18页/共70页第十九页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool SeqList:Insert(int i,T x)/在元素ai之后插入x if (in-1) /越界检查 coutOut Of Boundsendl; return false; if (n=maxLength)/上溢出检查 coutOverFlowi;j-) elements

6、j+1=elementsj; elementsi+1=x;n+; return true;第19页/共70页第二十页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第20页/共70页第二十一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第21页/共70页第二十二页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 template bool SeqList:Delete(int i) /删除元素ai if (!n) /下溢出检查 coutUnderFlowendl; return false; if (in-1) cout

7、Out Of Boundsendl; return false; /从前(cngqin)往后逐个前移元素 for (int j=i+1;jn;j+) elementsj-1=elementsj; n-; return true;第22页/共70页第二十三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 void main() int x=10; SeqList r(4); r.Insert(-1,x); r.Insert(-1,x); r.Output(cout); /? 请复习C+，理解(lji)这一函数第23页/共70页第二十四页，共70页。南京(nn jn)邮电大

8、学计算机学院陈慧南 2006年9月 第24页/共70页第二十五页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第25页/共70页第二十六页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 element linka0a1a2an-1first非空单链表first空单链表 = NULL指针变量的存储单元 红色为结点的指针域 第26页/共70页第二十七页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第27页/共70页第二十八页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 element link第2

9、8页/共70页第二十九页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 template class SingleList:public public: SingleList() first=NULL; n=0; SingleList(); bool Find(int i,T& x) const; int Search(T x) const; bool Insert(int i,T x); bool Delete(int i); 第29页/共70页第三十页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 .private: ; 顺序(shnx)表类

10、SeqList、单链表类SingleList是抽象线性表类LinearList类的派生类。SingleListLinearListSeqListNodefriend第30页/共70页第三十一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 构造函数(hnsh) SingleList() first=NULL; n=0; 析构函数(hnsh) template SingleList: SingleList() Node *p; while (first) p=first-link; delete first; first=p; 第31页/共70页第三十二页，共70页。南京

11、(nn jn)邮电大学计算机学院陈慧南 2006年9月 第32页/共70页第三十三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool SingleList:Find(int i,T& x)const /在(a0,a1,.,an1)中找下标为i的元素ai if (in1) /对i进行(jnxng)越界检查 cout Out Of Bounds; return false; Node *p=first; for (int j=0; jlink; x=p-element; return true;第33页/共70页第三十四页，共70页。南京(nn jn

12、)邮电大学计算机学院陈慧南 2006年9月 第34页/共70页第三十五页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第35页/共70页第三十六页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool SingleList:Insert(int i,T x) if (in1) cout Out Of Bounds; return false; Node * q=new Node;q-element=x; Node *p=first;/ 找ai元素所在(suzi)的结点p for (int j=0; jlink;firsta0a

13、1a2an-1非空单链表first空单链表pppi=2第36页/共70页第三十七页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 if(i1) q-link=p-link;/新结点q插在p之后 p-link=q; else q-link=first; /新结点q插在头结点之前 first=q; n+; return true; / 删除结点p是指删除指针变量(binling)p所指示的结点*p。第37页/共70页第三十八页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第38页/共70页第三十九页，共70页。南京(nn jn)邮电大学计算机学院陈

14、慧南 2006年9月 第39页/共70页第四十页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool SingleList:Delete(int i) if ( !n ) coutUnderFlowendl; return false; if ( in-1 ) cout Out Of Boundsendl; return false； Node *p=first,*q=first; for (int j=0; jlink;第40页/共70页第四十一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 if (i=0) first=

15、first-link;/ 删除(shnch)头结点 else p=q-link; q-link=p-link; delete p; n-; return true;第41页/共70页第四十二页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第42页/共70页第四十三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 请区分“表头(bio tu)结点”和“头结点” 第43页/共70页第四十四页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templateHeaderList: HeaderList() Node *first

16、=new Node; first-link=NULL; n=0; 第44页/共70页第四十五页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool HeaderList:Insert(int i, T x) if (in1) cout Out Of Boundsendl; return false; Node *p=first; for (int j=0; jlink; Node * q=new Node; q-element=x; q-link=p-link; p-link=q; n+;return true;第45页/共70页第四十六页，共70页

17、。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 templatebool HeaderList:Delete(int i) if ( !n ) coutUnderFlowendl; return false; if ( in1 ) cout Out Of Boundsendl; return false; Node *q=first, *p; for (int j=0; jlink; p=q-link; q-link=p-link; delete p; n-; return true;第46页/共70页第四十七页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9

18、月 第47页/共70页第四十八页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第48页/共70页第四十九页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第49页/共70页第五十页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第50页/共70页第五十一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 删除操作的核心步骤(bzhu)如下：（1）p-lLink-rLink=p-rLink; p-rLink-lLink=p-lLink;（2）delete p;第51页/共70页第五十二页，共70页。南

19、京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第52页/共70页第五十三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 多项式的逻辑结构：视为线性表 p(x)=3x14-8x8+6x2+2 数据元素 (coef,exp) 表示(biosh)多项式项 coefxexp ，coef是该项的系数，exp是变元x的指数。第53页/共70页第五十四页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第54页/共70页第五十五页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第55页/共70页第五十六页，共70页。南京(n

20、n jn)邮电大学计算机学院陈慧南 2006年9月 项结点类 Term* InsertAfter（int c,int e） 构造一个(y )新项（c,e）结点，插在*this项之后，函数返回新项结点的地址。第56页/共70页第五十七页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第57页/共70页第五十八页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 Term:Term(int c,int e):coef(c),exp(e) link=0;Term:Term(int c,int e,Term *nxt):coef(c),exp(e) link

21、=nxt; Term:Term(int c,int e) coef=c;exp=e; link=0;第58页/共70页第五十九页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第59页/共70页第六十页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第60页/共70页第六十一页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第61页/共70页第六十二页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 private: Term* theList;/单循环链表的表头(bio tu)指针 friend o

22、stream & operator (istream&, Polynominal &); friend Polynominal& operator +(Polynominal &, Polynominal &);第62页/共70页第六十三页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第63页/共70页第六十四页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 第64页/共70页第六十五页，共70页。南京(nn jn)邮电大学计算机学院陈慧南 2006年9月 输出(shch)多项式void Polynominal:Output(ostream& out)const bool start=true; Term *p=theList-link; outThe polynom