数据结构第03章 (清华 殷人昆版).pptx

《数据结构第03章 (清华 殷人昆版).pptx》由会员分享，可在线阅读，更多相关《数据结构第03章 (清华 殷人昆版).pptx（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单链表单链表(Singly Linked List)n n特点特点uu 每个元素每个元素(表项表项)由结点由结点(Node)构成。构成。uu 线性结构线性结构uu 结点可以不连续存储结点可以不连续存储uu 表可扩充表可扩充data linka0a1a2a3a4 first第1页/共86页单链表的存储映像单链表的存储映像free(a)可利用存储空间可利用存储空间a0a2a1a3 freefirst(b)经过一段运行后的单链表结构经过一段运行后的单链表结构第2页/共86页单链表的类定单链表的类定义义n n多个类表达一个概念多个类表达一个概念(单链表单链表)。uu 链表结点链表结点(ListNode

2、)类类uu 链表链表(List)类类n n定义方式定义方式uu 复合方式复合方式uu 嵌套方式嵌套方式uu 继承方式继承方式第3页/共86页 class List;/链表类定义（复合方式）class ListNode /链表结点类 friend class List;/链表类为其友元类 private:int data;/结点数据,整型 ListNode*link;/结点指针;class List /链表类 private:ListNode*first,*current;/表头指针;第4页/共86页class List /链表类定义(嵌套方式)private:class ListNode /嵌

3、套链表结点类 public:int data;ListNode*link;ListNode*first,*current;/表头指针public:/链表操作;第5页/共86页链表类和链表结点类定义链表类和链表结点类定义(继承方式继承方式)class ListNode /链表结点类protected:int data;ListNode*link;class List:public class ListNode /链表类,继承链表结点类的数据和操作 private:ListNode*first,*current;/表头指针;第6页/共86页单链表中的插入与删除单链表中的插入与删除n n插入uu 第

4、一种情况：在第一个结点前插入第一种情况：在第一个结点前插入 newnode-link=first;first=newnode;（插入前）（插入后）firstnewnodenewnodefirst第7页/共86页 (插入前插入前)()(插入后插入后)uu 第二种情况：在链表中间插入第二种情况：在链表中间插入 newnode-link=current-link;current-link=newnode；newnodecurrentnewnodecurrent第8页/共86页uu 第三种情况：在链表末尾插入第三种情况：在链表末尾插入 newnode-link=current-link;current

5、-link=newnode；(插入前插入前)()(插入后插入后)newnodenewnodecurrentcurrent 第9页/共86页int List:Insert(int x,int i)/在链表第 i 个结点处插入新元素 x ListNode*p=current;current=first;for(k=0;k link;if(current=NULL&first!=NULL)cout link=first;first=current=newnode;else /插在表中或末尾 newnode-link=current-link;current=current-link=newnode;

6、return 1;第11页/共86页n n删除uu第一种情况第一种情况:删除表中第一个元素删除表中第一个元素uu第二种情况第二种情况:删除表中或表尾元素删除表中或表尾元素在单链表中删除含在单链表中删除含ai的结点的结点ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后第12页/共86页int List:Remove(int i)/在链表中删除第 i 个结点 ListNode*p,*q;int k=0;if(i=0)/删除表中第 1 个结点 q=first;current=first=first-link;else p=current;current=first;/找第 i-1

7、个结点 for(k=0;k link;第13页/共86页 if(current=NULL|current-link=NULL)cout link;/重新链接 current=current-link=q-link;Type x=q-data;delete q;/删除q return x;/返回第 i 个结点的值第14页/共86页带表头结点的单链带表头结点的单链表表n n表头结点位于表的最前端，本身不表头结点位于表的最前端，本身不带数据，带数据，仅标志表头仅标志表头。n n设置表头结点的目的是设置表头结点的目的是统一空表与统一空表与非空表的操作非空表的操作，简化链表操作的实简化链表操作的实现现。

8、非空表非空表 空表空表0ana1firstfirst0第15页/共86页在带表头结点的单链表在带表头结点的单链表 第一个结点前插入新结点第一个结点前插入新结点 newnode-link=p-link;p-link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp第16页/共86页 q=p-link;p-link=q-link;delete q;从带表头结点的单链表中删除第一个结点从带表头结点的单链表中删除第一个结点firstfirst(非空表）非空表）first0first(空表）空表）0pqpq第17页/共8

9、6页单链表的模板单链表的模板类类n n类模板将类的数据成员和成员函类模板将类的数据成员和成员函数设计得更完整、更灵活。数设计得更完整、更灵活。n n类模板更易于复用。类模板更易于复用。n n在单链表的类模板定义中，增加在单链表的类模板定义中，增加了了表头结点表头结点。第18页/共86页 用模板定义的单链表类用模板定义的单链表类template class List;template class ListNode friend class List;Type data;/结点数据 ListNode*link;/结点链接指针public:ListNode():link(NULL)/构造函数 Lis

10、tNode(Type&item):data(item),link(NULL)第19页/共86页 ListNode*getNode(Type&item,ListNode*next=NULL);/以item和next建立一个新结点 ListNode*getLink()return link;/取得结点的下一结点地址 Type getData()return data;/取得结点中的数据 void setLink(ListNode*next)link=next;/修改结点的link指针第20页/共86页 void setData(Type value)data=value;/修改结点的data值;t

11、emplate class List /链表类private:ListNode*first,*current;/链表的表头指针和当前元素指针public:List(Type&value)first=current =new ListNode(value);第21页/共86页 List()MakeEmpty();delete first;void MakeEmpty();/将链表置为空表 int Length()const;/计算链表的长度 ListNode*Find(Type value);/搜索含数据value的元素并成为当前元素 ListNode*Locate(int i);/搜索第 i

12、个元素的地址并置为当前元素 Type*GetData();/取出表中当前元素的值 int Insert(Type value);/将value插在当前位置后并成为当前元素第22页/共86页 Type*Remove();/将链表当前元素删去,填补者为当前元素 ListNode*Firster()current=first;return first;/当前指针置于表头,返回表头结点地址 Type*First();/第一个结点为当前结点 Type*Next();/下一个结点为当前结点 int NotNull()return current!=NULL;int NextNotNull()return

13、current!=NULL¤t-link!=NULL;第23页/共86页链表结点部分操作的实现链表结点部分操作的实现template ListNode*ListNode:GetNode(Type&item,ListNode *next=NULL)/建立新结点,函数返回新结点地址。ListNode*newnode=new ListNode(item);newnode-link=next;return newnode;第24页/共86页template void List :MakeEmpty()/删去链表中除表头结点外的所有其他结点 ListNode*q;while(first-li

14、nk!=NULL)q=first-link;first-link=q-link;/将表头结点后第一个结点从链中摘下 delete q;/释放它 current=first;/当前指针置于表头结点第25页/共86页firstqfirstfirstqqfirsta0a1a1a2a2a2current第26页/共86页template int List:Length()const/求单链表的长度 ListNode*p=first-link;/检测指针 p 指示第一个结点 int count=0;while(p!=NULL)/逐个结点检测 p=p-link;count+;return count;第2

15、7页/共86页firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3第28页/共86页template ListNode*List :Find(Type value)/在链表中从头搜索其数据值为value的结点 current=first-link;/当前指针 current 指示第一个结点 while(current!=NULL)if(current-data=value)break;else current=current-link;return current;第29页/共86页template ListNode*List

16、:Locate(int i)/定位函数。返回表中第 i 个元素的地址/若 i -1或 i 超出，则返回NULL if(i -1)return NULL;/i 值不合理 if(i=-1)/返回表头结点地址 current=first;return first;ListNode*p=first-link;int k=0;第30页/共86页 while(p!=NULL&k link;k+;/找第 i 个结点 if(p!=NULL)current=p;return p;/返回第 i 个结点地址或NULLtemplate Type*List:GetData()/取出链表中当前元素的值 if(curren

17、t=NULL)return NULL;/空表 else return¤t-data;第31页/共86页template int List:Insert(Type value)/将新元素value插入在链表中当前结点后 if(current=NULL)return 0;ListNode*newnode=GetNode(value,current-link);current=current-link=newnode;return 1;/插入成功，函数返回1template Type*List:Remove()第32页/共86页/将链表当前元素删去,函数返回该元素 if(current=

18、first)return NULL;/空表 ListNode*p=first;while(p-link!=current)p=p-link;/寻找当前元素的前驱元素结点 p-link=current-link;/摘下被删结点 Type val=current-data;delete current;current=p-link;/释放,重置当前元素指针 return&val;第33页/共86页template Type*List:First()/返回表中第一个结点的值的指针,若为空/表则返回NULL if(first-link!=NULL)current=first-link;return&c

19、urrent-data;else current=NULL;return NULL;第34页/共86页template Type*List:Next()/返回表中当前元素的下一个元素的值的/指针,若无下一元素则返回NULL if(current!=NULL¤t-link!=NULL)current=current-link;return¤t-data;else return NULL;第35页/共86页【例例例例】单链表单链表单链表单链表求和函数求和函数求和函数求和函数 int sum(const List ls)if(ls.nextNotNull()=NULL)ret

20、urn 0;/空链表 int retvalue=*ls.First();/取得第一个元素的值 while(ls.nextNotNull()retvalue+=*ls.Next();/看有下一个结点存在,累加 return retvalue;第36页/共86页静态链表结构静态链表结构第37页/共86页循环链表循环链表(Circular List)n n循环链表是单链表的变形。循环链表是单链表的变形。n n循环链表最后一个结点的循环链表最后一个结点的 link 指针指针不不 为为NULL，而是指向了表的前端。，而是指向了表的前端。n n为简化操作，在循环链表中往往加入为简化操作，在循环链表中往往加

21、入表头结点。表头结点。n n循环链表的特点是：循环链表的特点是：只要知道表中某只要知道表中某一结点的地址，就可搜寻到所有其他一结点的地址，就可搜寻到所有其他结点的地址。结点的地址。第38页/共86页n n循环链表的示例循环链表的示例n n带表头结点的循环链表带表头结点的循环链表 a0a1a2an-1firstan-1firsta1a0first(空表空表)(非空表非空表)第39页/共86页搜索成功搜索成功搜索不成功搜索不成功循环链表的搜索算法循环链表的搜索算法firstfirst3131484815155757搜索搜索15 搜索搜索25 current current currentcurre

22、nt current current currentcurrent第40页/共86页if(first!=NULL)CircListNode*second=first-link;first-link=av;av=second;first=NULL;利用可利用空间表回收循环链表利用可利用空间表回收循环链表firstavfirstav回收前回收前回收后回收后第41页/共86页if(av=NULL)newnode=new CircListNode;else newnode=av;av=av-link;从可利用空间表分配结点从可利用空间表分配结点avnewnodeav分配前的分配前的可利可利用空间表用空

23、间表分配后的分配后的可可利用空间表利用空间表和新结点和新结点第42页/共86页多项式多项式(Polynomial)n nn 阶多项式阶多项式 Pn(x)有有 n+1 项项。u 系数系数 c0,c1,c2,cnu 指数指数 0,1,2,n。按升幂。按升幂排列排列第43页/共86页class Polynomial public:Polynomial();/构造函数构造函数 int operator!();/判是否零多项式判是否零多项式 float Coef(int e);int LeadExp();/返回最大指数返回最大指数 Polynomial Add(Polynomial poly);Poly

24、nomial Mult(Polynomial poly);float Eval(float x);/求值求值多项式多项式(Polynomial)的抽象数据类型的抽象数据类型第44页/共86页 多项式的存储表示多项式的存储表示第一种：第一种：第一种：第一种：private:(静态数静态数静态数静态数 int degree;组表示组表示组表示组表示)float coef maxDegree+1;P Pn n(x x)可以表示为可以表示为可以表示为可以表示为：pl.degree=n pl.coefi=ci,0 i n0 1 2 degree maxDgreec0c1c2cncoef第45页/共86页

25、第二种：第二种：private:(动态数动态数 int degree;组表示组表示)float*coef;构造函数构造函数 Polynomial(int sz)degree=sz;coef=new float degree+1;以上两种存储表示适用于指数连续排列以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如的多项式。但对于指数不全的多项式如 P101(x)=3+5x50-14x101,不经济。不经济。第46页/共86页n n在多项式的链表表示中每个结点三在多项式的链表表示中每个结点三个数据成员：个数据成员：n n优点是：优点是：uu 多项式的项数可以动态地增长，多项式的项

26、数可以动态地增长，不存在存储溢出问题。不存在存储溢出问题。uu 插入、删除方便，不移动元素。插入、删除方便，不移动元素。第三种第三种：多项式的链表表：多项式的链表表示示coef exp link Data Term第47页/共86页多项式多项式(polynomial)类的链表定义类的链表定义struct Term /多项式结点定义 float coef;/系数 int exp;/指数 Term(float c,int e)coef=c;exp=e;class Polynomial /多项式类的定义 List poly;/构造函数 friend Polynomial&operator+(Poly

27、nomial&,Polynomial&);/加法;第48页/共86页多项式链表的相加多项式链表的相加AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 14第49页/共86页两个多项式的相加算法两个多项式的相加算法n n扫描两个多项式，若都未检测完：扫描两个多项式，若都未检测完：uu 若当前被检测项若当前被检测项指数相等指数相等，系，系数相加。若未变成数相加。若未变成 0，则将结果，则将结果加到结果多项式。加到结果多项式。uu 若当前被检测

28、项若当前被检测项指数不等指数不等，将，将指数小者加到结果多项式。指数小者加到结果多项式。n n若一个多项式已检测完，将另一若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项个多项式剩余部分复制到结果多项式。式。第50页/共86页AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14pappc-9 10pb第51页/共86页AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14papbpc-9 10第52页/共86页AH.first CH.f

29、irst 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14papbpc-9 10第53页/共86页AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 127 128 148 14pappc-9 10pb0第54页/共86页AH.first CH.first 1 01 0-1 4-1 40 6-9 107 127 128 148 14pappc-9 10pb第55页/共86页AH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14papc-9 10pb第56页/共86页A

30、H.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14papc-9 10pb第57页/共86页AH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14pa=pc-9 10pb 第58页/共86页AH.first CH.first 1 01 0-1 4-1 4-9 107 127 128 148 14pa=pc-9 10pb 第59页/共86页friend Polynomial&operator+(Polynomial&ah,Polynomial&bh)/两个带头结点的按升幂排列的多项式相加，/返

31、回结果多项式链表的表头指针，结果不/另外占用存储,覆盖ah和bh链表 ListNode*pa,*pb,*pc,*p;Term a,b;pc=ah.poly.Firster();/结果存放指针 p=bh.poly.Firster();pa=ah.poly.First();/多项式检测指针 pb=bh.poly.First();/多项式检测指针 delete p;/删去bh的表头结点第60页/共86页 while(pa!=NULL&pb!=NULL)/两两比较 a=pa-data;b=pb-data;switch(compare(a.exp,b.exp)case=:/pa-exp=pb-exp a

32、.coef=a.coef+b.coef;/系数相加 p=pb;pb=pb-link;delete p;/删去原pb所指结点 if(abs(a.coef)link;delete p;/相加为零,该项不要第61页/共86页 else /相加不为零,加入ch链 pa-data=a;pc-link=pa;pc=pa;pa=pa-link;break;case :/pa-exp pb-exp pc-link=pb;pc=pb;pb=pb-link;break;case exp exp pc-link=pa;pc=pa;pa=pa-link;第62页/共86页 if(pa-link!=NULL)pc-li

33、nk=pa;else pc-link=pb;/剩余部分链入ch链 return ah;第63页/共86页双向链表双向链表(Doubly Linked List)n n双向链表是指在前驱和后继方向都双向链表是指在前驱和后继方向都能游历能游历(遍历遍历)的线性链表。的线性链表。n n双向链表每个结点结构：双向链表每个结点结构：n n双向链表通常采用带表头结点的循双向链表通常采用带表头结点的循环链表形式。环链表形式。前驱方向前驱方向 后继方向后继方向lLink data rLink第64页/共86页n n结点指向结点指向结点指向结点指向p=pp=p-lLinklLink-rLink=prLink=p

34、-rLinkrLink-lLinklLink非空表非空表 空表空表p-lLinkp-rLinkplLinkrLinkfirstfirst第65页/共86页双向循环链表类的定义双向循环链表类的定义template class DblList;template class DblNode friend class DblList;private:Type data;/数据 DblNode*lLink,*rLink;/指针public:DblNode(Type value,DblNode*left,DblNode*right):data(value),lLink(left),rLink(right)

35、第66页/共86页 DblNode(Type value):data(value),lLink(NULL),rLink(NULL)DblNode*getLeftLink()return llink;/取得左链指针值 DblNode*getRightLink()return rlink;/取得右链指针值 Type getData()return data;void setLeftLink(DblNode*Left)llink=Left;/修改左链指针值 void setRightLink(DblNode*Right)rlink=Right;/修改左链指针值 第67页/共86页 void setD

36、ata(Type value)data=value;template class DblList private:DblNode*first,*current;public:DblLIst(Type uniqueVal);/构造函数 DblList();/析构函数 int Length()const;/计算长度 int IsEmpty()/判链表空否 return first-rlink=first;第68页/共86页 int Find(const Type&target);void Firster()current=first;/当前指针置于表头结点。int First();/当前指针置于第

37、一个结点 int Next();/当前指针置于后继结点 int Prior();/当前指针置于前驱结点 void Insert(const Type&value);/插入一个包含有值value的新结点 void Remove();/删除当前结点;第69页/共86页template DblList:DblLIst(Type uniqueVal)/构造函数:建立双向循环链表的表头结点 first=current=new DblNode(uniqueVal);if(first=NULL)cerr rLink=first-lLink=first;/表头结点的链指针指向自己第70页/共86页templa

38、te int DblList:Length()const/计算带表头结点的双向循环链表的长度 DblNode*p=first-rLink;int count=0;while(p!=first)p=p-rLink;count+;return count;第71页/共86页搜索成功搜索成功搜索不成功搜索不成功双向循环链表的搜索算法双向循环链表的搜索算法firstfirst3131484815155757搜索搜索15 搜索搜索25 第72页/共86页template int DblList:Find(const Type&target)/在双向循环链表中搜索含target的结点,若/找到,则返回1,

39、同时current指针指向该结点,/否则函数返回0。DblNode*current=first-rLink;while(current!=first¤t-data !=target)current=current-rLink;if(current!=first)return 1;else return 0;第73页/共86页双向循环链表的插入算法双向循环链表的插入算法(非空表非空表)firstfirst314815后插入后插入25currentcurrent31482515newnode-lLink=current;newnode-rLink=current-rLink;curre

40、nt-rLink=newnode;current=current-rLink;current-rLink-lLink=current;第74页/共86页双向循环链表的插入算法双向循环链表的插入算法(空表空表)first后插入后插入25currentcurrent25newnode-lLink=current;newnode-rLink=current-rLink;(=first)current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;(first -lLink=current)first第75页/共86页t

41、emplate void DblList:Insert(const Type&value)if(current=first)/空表情形 current=first-rLink=new DblNode(value,first,first);else /非空表情形 current-rLink=new DblNode (value,current,current-rLink);current=current-rLink;current-rLink-lLink=current;第76页/共86页删除删除48双向循环链表的删除算法双向循环链表的删除算法firstfirst非空表非空表314815curr

42、ent3115currentcurrent-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;第77页/共86页删除删除31双向循环链表的删除算法双向循环链表的删除算法firstfirst31currentcurrentcurrent-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;第78页/共86页template void DblList:Remove()if(current!=first)DblNode*temp=current;/被删结点 cur

43、rent=current-rLink;/当前指针进到下一结点 current-lLink=temp-lLink;/将被删结点从链中摘下 temp-lLink-rLink=current;delete temp;/删去 第79页/共86页其他双向循环链表的公共操作其他双向循环链表的公共操作template DblList:DblLIst(Type uniqueVal)/双向循环链表的构造函数,创建表头结点 first=new DblNode(uniqueVal);firstrLink=firstlLink=first;template int DblList:Length()const/求双向循

44、环链表的长度(不计表头结点)第80页/共86页 DblNode*p=first-rLink;int count=0;while(p!=first)p=p-rLink;count+;return count;template int DblList:First()if(!IsEmpty()current=first-rLink;return 1;current=first;return 0;第81页/共86页template int DblList:Next()if(current-rLink=first)/最后结点 current=first-rLink;return 0;current=cu

45、rrent-rLink;return 1;template int DblList:Prior()if(current-lLink=first)/第一个结点 current=first-lLink;return 0;current=current-lLink;return 1;第82页/共86页稀疏矩阵稀疏矩阵n n在矩阵操作在矩阵操作(+、-、*、/)时矩阵非时矩阵非零元素会发生动态变化，用零元素会发生动态变化，用稀疏矩阵稀疏矩阵的链接表示的链接表示可适应这种情况。可适应这种情况。n n稀疏矩阵的链接表示采用正交链表：稀疏矩阵的链接表示采用正交链表：行链表行链表与与列链表列链表十字交叉。十字交叉。n n行链表与列链表都是行链表与列链表都是带表头结点的带表头结点的循环链表循环链表。用表头结点表征是第几行，。用表头结点表征是第几行，第几列。第几列。第83页/共86页稀疏矩阵的结点稀疏矩阵的结点headdownnextright(a)表头结点表头结点 (b)非零元素结点非零元素结点rightvaluedownheadrowcolaijFalseij(c)建立建立aij结点结点 第84页/共86页稀疏矩阵的正交链表表示的示例稀疏矩阵的正交链表表示的示例第85页/共86页谢谢您的观看！第86页/共86页