线性表课件学习培训课件.ppt

1、1线性表线性表顺序表顺序表 单链表单链表循环链表循环链表双向链表双向链表多项式多项式线性表的物理实现单链表的变化形式 链表的应用2,3a1a2a3a4a5a64时时 0 0,)(时时 0 0,)(iliLOCiiLOC1LOC(i)=LOC(i-1)+l=+i*l5625 s 3.3 62 74 t 1.0 6 7顺序表(SeqList)类的定义#include /定义在“seqList.h”中#include#include“linearList.hconst int defaultSize=100;template class SeqList:public LinearList prote

2、cted:E*data;/存放数组 int maxSize;/最大可容纳表项的项数 int last;/当前已存表项的最后位置 void reSize(int newSize);/改变数组空间大小8 public:SeqList(int sz=defaultSize);/构造函数 SeqList(SeqList&L);/复制构造函数 SeqList()delete data;/析构函数 int Size()const return maxSize;/求表最大容量 int Length()const return last+1;/计算表长度 int Search(E&x)const;/搜索x在表

3、中位置，函数返回表项序号 int Locate(int i)const;/定位第 i 个表项，函数返回表项序号 bool getData(int i,E&x)const;/取第i个表项的值 bool Insert(int i,E x);/插入 bool Remove(int i,E&x);/删除;9顺序表的构造函数#include /操作“exit”存放在此#include“seqList.h”/操作实现放在“seqList.cpp”template SeqList:SeqList(int sz)if(sz 0)maxSize=sz;last=-1;data=new EmaxSize;/创建表

4、存储数组 if(data=NULL)/动态分配失败 cerr 存储分配错误！endl;exit(1);10template SeqList:SeqList(SeqList&L)maxSize=L.Size();last=L.Length()-1;E value;data=new EmaxSize;/创建存储数组 if(data=NULL)/动态分配失败 cerr 存储分配错误！endl;exit(1);for(int i=1;i=last+1;i+)/传送各个表项L.getData(i,value);datai-1=value;复制构造函数11顺序表的搜索算法template int SeqL

5、ist:Search(E&x)const/在表中顺序搜索与给定值 x 匹配的表项，找到则/函数返回该表项是第几个元素，否则函数返回0 for(int i=0;i=last;i+)/顺序搜索 if(datai=x)return i+1;/表项序号和表项位置差1 return 0;/搜索失败;12 x=48 x=5013212)(11)2(111=1nnnnnninACNni (假设表的长度为假设表的长度为n,即即n=last+1)niiic*pACN1=1415表项的插入算法template bool SeqList:Insert(int i,E x)/将新元素x插入到表中第i(1ilast+2

6、)个表项位/置。if(last=maxSize-1)return false;/表满 if(i last+2)return false;/参数i不合理 for(int j=last;j=i-1;j-)/依次后移 dataj+1=dataj;datai-1=x;/插入(第 i 表项在datai-1处)last+;return true;/插入成功;16在表中第在表中第 i 个位置插入，从个位置插入，从datai-1 到到data last 成块后移，成块后移，移动移动n-1-(i-1)+1=n-i+1项项(假设表的长度为假设表的长度为n,即即n=last+1)221)(1)(1 0)1(111)

7、(11=11nnnnnninnniAMN1718表项的删除算法template bool SeqList:Remove(int i,E&x)/从表中删除第 i(1ilast+1)个表项，通过引用型/参数 x 返回被删元素。if(last=-1)return false;/表空 if(i last+1)return false;/参数i不合理 x=datai-1;for(int j=i;j=last;j+)/依次前移，填补 dataj-1=dataj;last-;return true;19删除第删除第 i 个表项，需将第个表项，需将第 i+1 项到第项到第 last+1项全部前移，需前项全部前

8、移，需前移的项数为移的项数为 n-(i+1)+1=n-i (假设表的长度为假设表的长度为n,即即n=last+1)ninnnninn12121)(1)(1=AMN20void Union(SeqList&LA,SeqList&LB)int 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中搜索它中搜索它 if(k=0)/若未找到插入它若未找到插入它 n+;LA.Insert(n,x);21 void Intersect

9、ion(SeqList&LA,SeqList&LB)int n=LA.Length();int m=LB.Length();int i=1;int x;while(i link=first;first=newNode;firstnewNodenewNodefirst32u 第二种情况：在链表中间插入第二种情况：在链表中间插入 newNode-link=current-link;current-link=newNode；newNodecurrentnewNodecurrent33第三种情况：在链表末尾插入第三种情况：在链表末尾插入 newNode-link=current-link;curren

10、t-link=newNode；newNodenewNodecurrentcurrent 34单链表的插入算法bool List:Insert(int i,int x)/将新元素 x 插入到第 i 个结点之后。i 从1开始，/i=0 表示插入到首元结点之前。if(first=NULL|i=0)/空表或首元结点前 LinkNode*newNode=new LinkNode(x);/建立一个新结点 newNode-link=first;first=newNode;/新结点成为首元结点 else /否则，寻找插入位置 LinkNode*current=first;int k=1;35 while(k

11、link;k+;if(current=NULL&first!=NULL)/链短 cerr link=current-link;current-link=newNode;return true;3637单链表的删除算法bool List:Remove(int i,int&x)/将链表中的第 i 个元素删去,i 从1开始。LinkNode*del;/暂存删除结点指针if(i link;else LinkNode*current=first;k=1;/找i-1号结点 while(k link;k+;if(current=NULL|current-link=NULL)cout link;/删中间/尾结

12、点 current-link=del-link;x=del-data;delete del;/取出被删结点数据 return true;实现单链表的插入和删除算法，不需要移动元实现单链表的插入和删除算法，不需要移动元素，只需修改结点指针，比顺序表方便。素，只需修改结点指针，比顺序表方便。情况复杂，要专门讨论空表和在表头插入的特情况复杂，要专门讨论空表和在表头插入的特殊情形。殊情形。寻找插入或删除位置只能沿着链顺序检测。寻找插入或删除位置只能沿着链顺序检测。390ana1firstfirst040 newNode-link=current-link;current-link=newNode;fi

13、rstnewNodefirstnewNode插入firstnewNode0firstnewNode0插入currentcurrentcurrentcurrent41 del=current-link;current-link=del-link;delete del;(非空表）非空表）(空表）空表）firstfirstfirst0first0currentdelcurrentdel42434445template struct CircLinkNode/链表结点类定义 E data;CircLinkNode*link;CircLinkNode(CircLinkNode*next=NULL)lin

14、k=next;CircLinkNode(E x,CircLinkNode*next=NULL)data=x;link=next;bool Operator=(CircLinkNode&node)return data=node.data;bool Operator!=(CircLinkNode&node)return data!=node.data;循环链表类的定义46template /链表类定义class CircList:public LinearList private:CircLinkNode*first,*last;/头指针,尾指针public:CircList(const E x

15、);/构造函数CircList(CircList&L);/复制构造函数CircList();/析构函数 int Length()const;/计算链表长度bool IsEmpty()return first-link=first;/判表空否CircLinkNode*getHead()const;/返回表头结点地址47 void setHead(CircLinkNode*p);/设置表头结点地址 CircLinkNode*Search(E x);/搜索CircLinkNode*Locate(int i);/定位 E*getData(int i);/提取 void setData(int i,E

16、x);/修改bool Insert(int i,E x);/插入 bool Remove(int i,E&x);/删除;循环链表与单链表的操作实现，最主要的不同就循环链表与单链表的操作实现，最主要的不同就是扫描到链尾，遇到的不是是扫描到链尾，遇到的不是NULL，而是表头。，而是表头。48搜索不成功搜索不成功循环链表的搜索算法循环链表的搜索算法搜索搜索25搜索成功搜索成功搜索搜索15first31481557 current current currentfirst31481557 current current current currentcurrent49循环链表的搜索算法template

17、 CircListNode*CircList:Search(E x)/在链表中从头搜索其数据值为 x 的结点 current=first-link;while(current!=first¤t-data!=x)current=current-link;return current;5051求解Josephus问题的算法#include#include“CircList.h”template void Josephus(CircList&Js,int n,int m)CircLinkNode*p=Js.getHead(),*pre=NULL;int i,j;for(i=0;i n-1

18、;i+)/执行n-1次 for(j=1;j link;cout “出列的人是”data link=p-link;delete p;/删去 p=pre-link;void main()CircList clist;int i,n,m;cout n m;for(i=1;i=n;i+)clist.insert(i,i);/约瑟夫环 Josephus(clist,n,m);/解决约瑟夫问题 53 l lL Li in nk k(左左左左 链链链链 指指指指 针针针针)d da at ta a(数数数数 据据据据)r rL Li in nk k(右右右右 链链链链 指指指指 针针针针)54 55temp

19、late struct DblNode/链表结点类定义 E data;/链表结点数据 DblNode*lLink,*rLink;/前驱、后继指针 DblNode(DblNode*l=NULL,DblNode*r=NULL)lLink=l;rLink=r;/构造函数 DblNode(E value,DblNode*l=NULL,DblNode*r=NULL)data=value;lLink=l;rLink=r;/构造函数;56template class DblList/链表类定义 public:DblList(E uniqueVal)/构造函数 first=new DblNode(unique

20、Val);first-rLink=first-lLink=first;DblNode*getFirst()const return first;void setFirst(DblNode*ptr)first=ptr;DblNode*Search(E x,int d);/在链表中按d指示方向寻找等于给定值x的结点,/d=0按前驱方向,d0按后继方向57 DblNode*Locate(int i,int d);/在链表中定位序号为i(0)的结点,d=0按前驱方 /向,d0按后继方向 bool Insert(int i,E x,int d);/在第i个结点后插入一个包含有值x的新结点,d=0 /按前

21、驱方向,d0按后继方向 bool Remove(int i,E&x,int d);/删除第i个结点 bool IsEmpty()return first-rlink=first;/判双链表空否 private:DblNode*first;/表头指针;58搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 59双向循环链表的搜索算法template DblNode*DblList:Search(E x,int d)/在双向循环链表中寻找其值等于x的结点。DblNode*current=(d=0)?first-lLink:first-

22、rLink;/按d确定搜索方向while(current!=first¤t-data!=x)current=(d=0)?current-lLink:current-rLink;if(current!=first)return current;/搜索成功else return NULL;/搜索失败;60双向循环链表的插入算法双向循环链表的插入算法 (非空表非空表)newNode-rLink=current-rLink;current-rLink=newNode;newNode-rLink-lLink=newNode;newNode-lLink=current;firstfirst31

23、481525currentnewNode31482515current61双向循环链表的插入算法双向循环链表的插入算法 (空表空表)first25currentnewNode25firstcurrentnewNode-rLink=current-rLink (newNode-rLink=first);current-rLink=newNode;newNode-rLink-lLink=newNode;(first-lLink=newNode)newNode-lLink=current;62双向循环链表的插入算法template bool DblList:Insert(int i,E x,int

24、d)/建立一个包含有值x的新结点,并将其按 d 指定的/方向插入到第i个结点之后。DblNode*current=Locate(i,d);/按d指示方向查找第i个结点 if(current=NULL)return false;/插入失败 DblNode*newNd=new DblNode(x);if(d=0)/前驱方向:插在第i个结点左侧newNd-lLink=current-lLink;/链入lLink链 current-lLink=newNd;63 newNd-lLink-rLink=newNd;/链入rLink链 newNd-rLink=current;else /后继方向:插在第i个结

25、点后面 newNd-rLink=current-rLink;/链入rLink链 current-rLink=newNd;newNd-rLink-lLink=newNd;/链入lLink链 newNd-lLink=current;return true;/插入成功;64删除删除48双向循环链表的删除算法双向循环链表的删除算法firstfirst314815current3115currentcurrent-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;65双向循环链表的删除算法template bool DblList:R

26、emove(int i,E&x,int d)/在双向循环链表中按d所指方向删除第i个结点。DblNode*current=Locate(i,d);if(current=NULL)return false;/删除失败current-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;/从lLink链和rLink链中摘下 x=current-data;delete current;/删除 return true;/删除成功;66iniinnnxaxaxaxaaxP02210 )(Pn(x)。u u A(x)=1-10 x6+2x8

27、+7x1467 (静态数组表示静态数组表示)private:int degree;float coef maxDegree+1;可以表示为可以表示为：pl.degree=n pl.coefi=ai,0 i na0 a1 a2 an 0 1 2 degree maxDegree-1coefn68(动态数组表示动态数组表示)private:int degree;float*coef;Polynomial:Polynomial(int sz)maxDegree=sz;coef=new float maxDegree+1;69：struct term /多项式的项定义 float coef;/系数 i

28、nt exp;/指数;static term termArraymaxTerms;/项数组 static int free,maxTerms;/当前空闲位置指针a0 a1 a2 ai ame0 e1 e2 ei emcoefexp0 1 2 i m70初始化：初始化：/term Polynomial:termArraymaxTerms;/int Polynomial:free=0;class Polynomial /多项式定义 public:private:int start,finish;/多项式始末位置71两个多项式存储的例子两个多项式存储的例子 A(x)=2.0 x1000+1.8 B(

29、x)=1.2+51.3x50+3.7x101 两个多项式存放在两个多项式存放在termArray中中A.start A.finish B.start B.finish freecoefexp1.8 2.0 1.2 51.3 3.7 0 1000 0 50 101 maxTerms72数据域数据域指针域指针域A(x)=1-10 x6+2x8+7x1473 多项式顺序存储表示的缺点多项式顺序存储表示的缺点 插入和删除时项数可能有较大变化，因此要插入和删除时项数可能有较大变化，因此要移动大量数据移动大量数据 不利于多个多项式的同时处理不利于多个多项式的同时处理 多项式链表存储表示的优点多项式链表存储

30、表示的优点 多项式的项数可以动态地增长，不存在存储多项式的项数可以动态地增长，不存在存储溢出问题。溢出问题。插入、删除方便，不移动元素插入、删除方便，不移动元素74struct Term /多项式结点定义 float coef;/系数 int exp;/指数 Term*link;/链接指针 Term(float c,int e,Term*next=NULL)coef=c;exp=e;link=next;Term*InsertAfter(float c,int e);friend ostream&operator (ostream&,const Term&);75class Polynomial

31、/多项式类的定义public:Polynomal()first=new Term(0,-1);/构造函数Polynomal(Polynomal&R);/复制构造函数int maxOrder();/计算最大阶数private:Term*first;friend ostream&operator (istream&,Polynomal&);76 friend void Add(Polynomial&A,Polynomial&B,Polynomial&C);friend void Mul(Polynomial&A,Polynomial&B,Polynomial&C);77两个多项式的相加算法设两个多

32、项式都带表头结点，检测指针设两个多项式都带表头结点，检测指针pa和和pb分分别指示两个链表当前检测结点，并设结果多项式的别指示两个链表当前检测结点，并设结果多项式的链表为链表为C，存放指针为，存放指针为pc，初始位置在，初始位置在C的表头结的表头结点。点。当当pa和和pb没有检测完各自的链表时，比较当前检没有检测完各自的链表时，比较当前检测结点的指数域：测结点的指数域：指数不等：小者加入指数不等：小者加入C链，相应检测指针链，相应检测指针pa或者或者pb进进1；指数相等：对应项系数相加。若相加结果不为指数相等：对应项系数相加。若相加结果不为零，则结果加入零，则结果加入C链，链，pa与与pb进进

33、1。当当pa或或pb指针中有一个为指针中有一个为NULL，则把另一个链，则把另一个链表的剩余部分加入到表的剩余部分加入到C链。链。78AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 14多项式链表的相加AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14CH=1-x4-9x10+7x12+8x1479AH.firstBH.first CH.first1 0-1 4-3 63 6-9 107 128 14papcpb 80AH.first CH.first 1 01 0-1 4-3 63

34、6-9 107 128 14papbpcBH.first81AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.first82AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.firsttmp=-3+3=083AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first 84AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14

35、papc-9 10pbBH.first7 12 85AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first7 128 14 p86n为数组中每一个元素附加一个链接指针，就形成静为数组中每一个元素附加一个链接指针，就形成静态链表结构。态链表结构。n静态链表每个结点由两个数据成员构成：静态链表每个结点由两个数据成员构成：datadata域存域存储数据，储数据，linklink域存放链接指针。域存放链接指针。n处理时可以处理时可以不改变各元素的物理位置不改变各元素的物理位置，只要，只要重新链重新链接接就能改变这些元素的逻辑顺序。就能改变这些元素的逻辑顺序。n它是利用数组定义的，在整个运算过程中存储空间它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。的大小不会变化。87静态链表的结构0号是表头结点，号是表头结点，link给出首元结点地址。给出首元结点地址。循环链表收尾时循环链表收尾时link=0，回到表头结点。如果不是，回到表头结点。如果不是循环链表，收尾结点指针循环链表，收尾结点指针link=-1。link指针是数组下标，因此是整数。指针是数组下标，因此是整数。012345dataa3a4a1a5a2link3245-1(0)1a1a2a3a4a5first