数据结构 课件 链表应用与变形.ppt

链表应用与变形数据结构电子教案数据结构电子教案1第二章第二章 线性表线性表n多项式多项式n循环链表循环链表n双向链表双向链表2 2单链表的应用n多项式存储3 3多项式多项式 (Polynomial)n nn阶多项式阶多项式 Pn(x)有有 n+1 项项。u 系数系数 a0,a1,a2,anu 指数指数 0,1,2,n。按升幂排列按升幂排列4 4第三种第三种：struct term /多项式的项定义 float coef;/系数 int exp;/指数;static term termArraymaxTerms;/项数组 static int free,maxTerms;/当前空闲位置指针a0 a1 a2 ai ame0 e1 e2 ei emcoefexp0 1 2 i m5 5两个多项式存储的例子两个多项式存储的例子 A(x)=2.0 x1000+1.8 B(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 maxTerms6 6n多项式顺序存储表示的缺点多项式顺序存储表示的缺点u插入和删除时项数可能有较大变化，因此插入和删除时项数可能有较大变化，因此要移动大量数据要移动大量数据u不利于多个多项式的同时处理不利于多个多项式的同时处理n采用多项式的链表表示可以克服这类困难：采用多项式的链表表示可以克服这类困难：u多项式的项数可以动态地增长，不存在存多项式的项数可以动态地增长，不存在存储溢出问题。储溢出问题。u插入、删除方便，不移动元素插入、删除方便，不移动元素。多项式的链表存储表示多项式的链表存储表示7 7n在多项式的链表表示中，每个结点三个数据在多项式的链表表示中，每个结点三个数据成员：成员：n通过链接指针，可以将多项式各项按指数递通过链接指针，可以将多项式各项按指数递增的顺序链接成一个单链表。增的顺序链接成一个单链表。n在此结构上，新项的加入和废项的删除执行在此结构上，新项的加入和废项的删除执行简单的链表插入和删除操作即可解决。简单的链表插入和删除操作即可解决。多项式的链表结构多项式的链表结构coef exp link Data Term8 8多项式表示法14328100a.poly.first148-3101060b.poly.first9 9多项式类定义struct Term/all members of Terms are public by defaultintcoef;/coefficientintexp;/exponentTerm Set(int c,int e)coef=c;exp=e;return*this;classPolynomialprivate:Chain poly;1010两个多项式的相加算法两个多项式的相加算法设两个多项式都带表头结点，检测指针设两个多项式都带表头结点，检测指针pa和和pb分别指示两个链表当前检测结点，并设结分别指示两个链表当前检测结点，并设结果多项式的表头指针为果多项式的表头指针为C，存放指针为存放指针为pc，初始位置在初始位置在C的表头结点。的表头结点。当当pa和和pb没有检测完各自的链表时，比较当没有检测完各自的链表时，比较当前检测结点的指数域：前检测结点的指数域：指数不等：小者加入指数不等：小者加入C链，相应检测指针链，相应检测指针pa或者或者pb进进1；指数相等：对应项系数相加。若相加结果指数相等：对应项系数相加。若相加结果不为零，则结果加入不为零，则结果加入C链，链，pa与与pb进进1。11 11CH.poly.firstAH.poly.firstBH.poly.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+8x141212AH.firstBH.first CH.first1 0-1 4-3 63 6-9 107 128 14papcpb 1313AH.first CH.first 1 01 0-1 4-3 63 6-9 107 128 14papbpcBH.first1414AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.first1515AH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 107 128 14papbpcBH.firsttmp=-3+3=01616AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first 1717AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first7 12 1818AH.first CH.first1 01 0-1 4-1 4-3 63 6-9 107 128 14papc-9 10pbBH.first7 128 14 p1919当当pa或或pb指针中有一个为指针中有一个为NULL，则把另一则把另一个链表的剩余部分加入到个链表的剩余部分加入到C链。链。void Add(Polynomal&A,Polynomal&B,Polynomal&C)/友元函数：两个带表头结点的按升幂排列的/多项式链表的头指针分别是 A.first 和 B.first,/返回的是结果多项式链表 C.Term*pa,*pb,*pc,*p,temp;float sum;pc=C.poly.first;/结果链尾指针 pa=A.poly.first-link;/A链检测指针 pb=B.poly.first-link;/B链检测指针 while(pa!=NULL&pb!=NULL)2020 if(pa-exp=pb-exp)/对应项指数相等 sum=pa-coef+pb-coef;if(fabs(sum)0.001)temp.set(sum,pa-exp);pc=C.poly.InsertAfter(temp);pa=pa-link;pb=pb-link;else if(pa-exp exp)/pa指数小 temp.set(pa-coef,pa-exp);pc=C.poly.InsertAfter(temp);pa=pa-link;else /pb指数小temp.set(pb-coef,pb-exp)pc=C.poly.InsertAfter(temp);pb=pb-link;2121 p=(pa!=NULL)?pa:pb;/p指示剩余链 while(p!=NULL)temp.set(p-coef,p-exp);pc=C.poly.InsertAfter(temp);p=p-link;2222template struct CircLinkNode/链表结点类定义 T data;CircLinkNode*link;CircLinkNode(CircLinkNode*next=NULL)link=next;CircLinkNode(T d,CircLinkNode*next=NULL)data=d;link=next;bool Operator=(T x)return data=x;bool Operator!=(T x)return data!=x;带表头结点的循环链表类的定义带表头结点的循环链表类的定义2323template /链表类定义class CircList private:CircLinkNode*first,*last;/头指针,尾指针public:CircList(const T x);/构造函数CircList(CircList&L);/复制构造函数CircList();/析构函数 int Length()const;/计算链表长度bool IsEmpty()return first-link=first;/判表空否CircLinkNode*getHead()const;/返回表头结点地址2424 void setHead(CircLinkNode*p);/设置表头结点地址 CircLinkNode*Search(T x);/搜索CircLinkNode*Locate(int i);/定位 T*getData(int i);/提取 void setData(int i,Tx);/修改bool Insert(int i,T x);/插入 bool Remove(int i,T&x);/删除;n循环链表与单链表的操作实现，最主要的不同就循环链表与单链表的操作实现，最主要的不同就是扫描到链尾，遇到的不是是扫描到链尾，遇到的不是NULL，而是表头。，而是表头。2525搜索不成功搜索不成功循环链表的搜索算法循环链表的搜索算法搜索搜索25搜索成功搜索成功搜索搜索15first31481557 current current currentfirst31481557 current current current currentcurrent2626循环链表的搜索算法循环链表的搜索算法template CircListNode*CircList:Search(T x)/在链表中从头搜索其数据值为 x 的结点 current=first-link;while(current!=first&current-data!=x)current=current-link;return current;2727带尾指针的循环链表带尾指针的循环链表last3148155722n n如果插入与删除仅在链表的两端发生，可如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。采用带表尾指针的循环链表结构。在表尾插入，时间复杂性在表尾插入，时间复杂性 O(1)在表尾删除，时间复杂性在表尾删除，时间复杂性 O(n)在表头插入，相当于在表尾插入在表头插入，相当于在表尾插入在表头删除，时间复杂性在表头删除，时间复杂性 O(1)2828带尾指针的单循链表代码见课本2929可用空间链表（见课本）n又叫 空闲链表n课本用单循链表实现3030双向链表(Doubly Linked List)n双向链表是指在前驱和后继方向都能游历双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。（遍历）的线性链表。n双向链表每个结点结构：双向链表每个结点结构：n双向链表通常采用带表头结点的循环链表形双向链表通常采用带表头结点的循环链表形式。式。前驱方向前驱方向 后继方向后继方向lLink data rLink3131n n结点指向结点指向结点指向结点指向p=pp=p-lLinklLink-rLinkrLink=p=p-rLinkrLink-lLinklLink非空表非空表 空表空表p-lLinkp-rLinkplLinkrLinkfirstfirst3232双向循环链表类的定义双向循环链表类的定义template struct DblNode/链表结点类定义T data;/链表结点数据DblNode*lLink,*rLink;/前驱、后继指针DblNode(DblNode*l=NULL,DblNode*r=NULL)lLink=l;rLink=r;/构造函数DblNode(T value,DblNode*l=NULL,DblNode*r=NULL)data=value;lLink=l;rLink=r;/构造函数;3333template class DblList/链表类定义public:DblList(T uniqueVal)/构造函数 first=new DblNode(uniqueVal);first-rLink=first-lLink=first;DblNode*getFirst()const return first;void setFirst(DblNode*ptr)first=ptr;DblNode*Search(T x,int d);/在链表中按d指示方向寻找等于给定值x的结点,/d=0按前驱方向,d0按后继方向3434DblNode*Locate(int i);/在链表中定位序号为i(0)的结点,bool Insert(int i,T x);/在第i个结点后插入一个包含有值x的新结点bool Remove(int i,T&x);/删除第i个结点bool IsEmpty()return first-rlink=first;/判双链表空否private:DblNode*first;/表头指针;3535双向循环链表的搜索算法双向循环链表的搜索算法搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 3636双向循环链表的搜索算法双向循环链表的搜索算法template DblNode*DblList:Search(T x)/在双向循环链表中寻找其值等于x的结点。DblNode*current=first-rLink;while(current!=first&current-data!=x)current=current-rLink;if(current!=first)return current;/搜索成功else return NULL;/搜索失败;3737双向循环链表的插入算法双向循环链表的插入算法 (非空表非空表)newNode-rLink=current-rLink;current-rLink=newNode;newNode-rLink-lLink=newNode;newNode-lLink=current;firstfirst314815后插入后插入后插入后插入25currentnewNode31482515current3838双向循环链表的插入算法双向循环链表的插入算法 (空表空表)first后插入后插入25currentnewNode25firstcurrentnewNode-rLink=current-rLink (newNode-rLink=first);current-rLink=newNode;newNode-rLink-lLink=newNode;(first-lLink=newNode)newNode-lLink=current;3939双向循环链表的插入算法双向循环链表的插入算法template bool DblList:Insert(int i,T x)/建立一个包含有值x的新结点,并将其插入到第i个结点之后。DblNode*current=Locate(i);/按d指示方向查找第i个结点 if(current=NULL)return false;/插入失败 DblNode*newNd=new DblNode(x);4040 newNd-rLink=current-rLink;/链入rLink链 current-rLink=newNd;newNd-rLink-lLink=newNd;/链入lLink链 newNd-lLink=current;return true;/插入成功;4141删除删除48双向循环链表的删除算法双向循环链表的删除算法firstfirst非空表非空表314815current3115currentcurrent-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;4242双向循环链表的删除算法双向循环链表的删除算法template bool DblList:Remove(int i,T&x)/在双向循环链表中按d所指方向删除第i个结点。DblNode*current=Locate(i);if(current=NULL)return false;/删除失败current-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;/从lLink链和rLink链中摘下 x=current-data;delete current;/删除 return true;/删除成功;4343静态链表静态链表n为数组中每一个元素附加一个链接指针，就为数组中每一个元素附加一个链接指针，就形成静态链表结构。形成静态链表结构。n处理时中可以处理时中可以不改变各元素的物理位置不改变各元素的物理位置，只，只要要重新链接重新链接就能改变这些元素的逻辑顺序。就能改变这些元素的逻辑顺序。n它是利用数组定义的，在整个运算过程中存它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。储空间的大小不会变化。n静态链表每个结点由两个数据成员构成：静态链表每个结点由两个数据成员构成：data域存储数据，域存储数据，link域存放链接指针。域存放链接指针。n所有结点形成一个结点数组，所有结点形成一个结点数组，4444静态链表的结构静态链表的结构n0号是表头结点，号是表头结点，link给出首元结点地址。给出首元结点地址。n循环链表收尾时循环链表收尾时link=0，回到表头结点。如果，回到表头结点。如果不是循环链表，收尾结点指针不是循环链表，收尾结点指针link=-1。nlink指针是数组下标，因此是整数。指针是数组下标，因此是整数。a1a2a3a4a5first012345dataa3a4a1a5a2link3245-1(0)14545