675单链表 循环链表多项式及其相加双向链表稀疏矩阵.ppt

单链表 循环链表多项式及其相加双向链表稀疏矩阵,第三章 链表,一、单链表,线性表的链式表示,顺序表的优点是可以随机选取表中元素缺点是插入删除操作复杂。用指针将互不相连的内存结点串成的线性表叫线性链表。结点 node 由一个数据元素域，一个或几个指针域组成。单链表的结点只有一个指针域。,几个结点，前一个结点的指针，指向后一个结点，就连接成一个线性链表。,线性链表的优点则是插入，删除快捷，缺点是选取复杂。,#include template class Node Node*next;/next 是下一个结点的地址 public:T data;/the data is public Node(const T,1.结点类的定义,/constructor.initialize data and/pointer members,template Node:Node(const T&item,Node*ptrnext):data(item),next(ptrnext)）,/return value of private member next,template Node*Node:NextNode(void)const return next;,/insert a node p after the current one,template void Node:InsertAfter(Node*p)/p points to successor of the current/node,and current node points to p.p-next=next;next=p;,/delete the node following current and return its address,template Node*Node:DeleteAfter(void)/save address of node to be deleted Node*tempPtr=next;/if there isnt a successor,return NULL if(next=NULL)return NULL;/current node points to successor of tempPtr.next=tempPtr-next;/return the pointer to the unlinked node return tempPtr;,2人工建立一个链表,void main(void)Node*a,*b,*c;a=new Node(a);b=new Node(b);c=new Node(c);Node*head,*p;head=new Node();p=head;head-InsertAfter(a);head-InsertAfter(b);head-InsertAfter(c);while(p!=NULL)cout dataNextNode();测试结果：打印 c b a,3.定义线性链表的一些操作,#include node.h/allocate a node with data member item and pointer nextPtrtemplate Node*GetNode(constT,enum AppendNewline noNewline,addNewline;,template/print a linked listvoid PrintList(Node*head,AppendNewline addnl=noNewline)/currPtr chains through the list,starting at head Node*currPtr=head;/print the current nodes data until end of list while(currPtr!=NULL)/output newline if addl=addNewline if(addnl=addNewline)cout data data NextNode();,/find an item in a linked list head;return TRUE and,/value of previous pointer if found;otherwise return FALSEtemplate int Find(Node*head,T/failed to locate item,/insert item at the front of list,template void InsertFront(Node*,/find rear of the list and append item,template void InsertRear(Node*,/delete the first node of the list,template void DeleteFront(Node*,/delete the first occurrence of key in the list,template void Delete(Node*,/insert item into the ordered list,template void InsertOrder(Node*,/delete all the nodes in the linked list,template void ClearList(Node*,链表插入排序,#include#pragma hdrstop#include node.h#include nodelib.h,template void LinkSort(T a,int n),Node*ordlist=NULL,*currPtr;int i;for(i=0;i data;currPtr=currPtr-NextNode();ClearList(ordlist);,/scan the array and print its elements,void PrintArray(int a,int n)for(int i=0;i n;i+)cout ai;,/*void main(void),/initialized array with 10 integer values int A10=82,65,74,95,60,28,5,3,33,55;LinkSort(A,10);/sort the array cout Sorted array:;PrintArray(A,10);/print the array cout endl;*/#endif/NODE_LIBRARY,链表的游标类(Iterator),游标类主要用于单链表的搜索。游标类的定义原则：Iterator类是List类和ListNode类的友元类。Iterator对象引用已有的List类对象。Iterator类有一数据成员current，记录对单链表最近处理到哪一个结点。Iterator类提供若干测试和搜索操作,表示链表的三个类的模板定义 enum Boolean False,True;template class List;template class ListIterator;template class ListNode/表结点friend class List;friend class ListIterator;public:private:Type data;ListNode*link;,template class List/链表类public:private:ListNode*first,*last;template class ListIterator private:const List/当前结点指针public:,ListNode*listfirst;?,ListIterator(const List/返回链表当前结点的下一个结点的地址,链表的游标类成员函数的实现template Boolean ListIterator:NotNull()/检查链表中当前元素是否非空 if(current!=NULL)return True;else return False;,current,current,情况 1 返回True 情况 2 返回False,template Boolean ListIterator:NextNotNull()/检查链表中下一元素是否非空 if(current!=NULL,current,current,情况 1 返回True 情况 2 返回False,template ListNode*ListIterator:First()/返回链表中第一个结点的地址 if(list.first-link!=NULL)current=list.first-link;return current;else current=NULL;return NULL;,list.first,current,链表中有表头结点,current,template ListNode*ListIterator:Next()/返回链表中当前结点的下一个结点的地址 if(current!=NULL,current,利用游标类(iterator)计算元素的和int sum(const List,静态链表结构,静态链表定义,const int MaxSize=100;/静态链表大小template class StaticList;template class SListNode friend class StaticList;Type data;/结点数据 int link;/结点链接指针template class StaticList SListNode NodesMaxSize;int newptr;/当前可分配空间首地址,将链表空间初始化,template void StaticList:InitList()Nodes0.link=-1;newptr=1;/当前可分配空间从 1 开始建/立带表头结点的空链表 for(int i=1;i MaxSize-1;i+)Nodesi.link=i+1;/构成空闲链接表 NodesMaxSize-1.link=-1;/链表收尾,在静态链表中查找具有给定值的结点,template int StaticList:Find(Type x)int p=Nodes0.link;/指针 p 指向链表第一个结点 while(p!=-1)if(Nodesp.data!=x)p=Nodesp.link;else break;/逐个结点检测查找具有给定值的结点 return p;,在静态链表的表尾追加一个新结点,template int StaticList:Append(Type x)if(newptr=-1)return 0;/追加失败 int q=newptr;/分配结点 newptr=Nodesnewptr.link;Nodesq.data=x;Nodesq.link=-1;int p=0;/查找表尾 while(Nodesp.link!=-1)p=Nodesp.link;Nodesp.link=q;/追加 return 1;,在静态链表中查找第 i 个结点,template int StaticList:Locate(int i)if(i 0)return-1;/参数不合理 if(i=0)return 0;int j=0,p=Nodes0.link;while(p!=-1,在静态链表第 i 个结点处插入一个新结点,template int StaticList:Insert(int i,Type x)int p=Locate(i-1);if(p=-1)return 0;/找不到结点 int q=newptr;/分配结点 newptr=Nodesnewptr.link;Nodesq.data=x;Nodesq.link=Nodesp.link;/链入 Nodesp.link=q;return 1;,在静态链表中释放第 i 个结点,template int StaticList:Remove(int i)int p=Locate(i-1);if(p=-1)return 0;/找不到结点 int q=Nodesp.link;/第 i 号结点 Nodesp.link=Nodesq.link;Nodesq.link=newptr;/释放 newptr=q;return 1;,二、循环链表(Circular List),循环链表是单链表的变形。循环链表的最后一个结点的 link 指针不为 NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。,循环链表的示例带表头结点的循环链表,a0,a1,a2,an-1,first,an-1,first,a1,a0,first,(空表),(非空表),template class CircList;template class CircListNode friend class CircList;public:CircListNode(Type d=0,CircListNode*next=NULL):data(d),link(next)/构造函数private:Type data;/结点数据 CircListNode*link;/链接指针,循环链表类的定义,template class CircList private:CircListNode*first,*current,*last;/链表的表头指针、当前指针和表尾指针public:CircList(Type value);CircList();int Length()const;Boolean IsEmpty()return first-link=first;Boolean Find(const Type,Type getData()const;void Firster()current=first;Boolean First();Boolean Next();Boolean Prior();void Insert(const Type,搜索成功,搜索不成功,循环链表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,current,current,current,current,current,current,current,current,循环链表的搜索算法,template CircListNode*CircList:Find(Type value)/在链表中从头搜索其数据值为value的结点 current=first-link;/检测指针 current 指示第一个结点 while(current!=first,用循环链表求解约瑟夫问题,约瑟夫问题的提法 n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数,报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。,例如 n=8 m=3,约瑟夫问题的解法#include#include“CircList.h”Template void CircList:Josephus(int n,int m)First();for(int i=0;i n-1;i+)/执行n-1次 for(int j=0;j m-1;j+)Next();cout“出列的人是”getData()endl;/数m-1个人 Remove();/删去,void main()CircList clist;int n,m;cout n m;for(int i=1;i=n;i+)clist.insert(i);/形成约瑟夫环 clist.Josephus(n,m);/解决约瑟夫问题,三、多项式(Polynomial),n 阶多项式 Pn(x)有 n+1 项。系数 c0,c1,c2,cn 指数 0,1,2,n。按升幂排列,在多项式的链表表示中每个结点三个数据成员：优点是：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。,多项式的链表表示,coef exp link,Data Term,多项式(polynomial)类的链表定义struct Term/多项式结点定义 float coef;/系数 int exp;/指数 Term(float c,int e)coef=c;exp=e;class Polynomial/多项式类的定义 List poly;/构造函数 friend Polynomial,多项式链表的相加,AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14,AH.first,BH.first,CH.first,1 0,1 0,-1 4,-1 4,-3 6,3 6,-9 10,-9 10,7 12,7 12,8 14,8 14,两个多项式的相加算法,扫描两个多项式，若都未检测完：若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。若当前被检测项指数不等，将指数小者加到结果多项式。若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。,friend Polynomial/删去bh的表头结点,while(pa!=NULL,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;,if(pa-link)pc-link=pa;else pc-link=pb;/剩余部分链入ch链 return this;,四、双向链表(Doubly Linked List),双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。双向链表每个结点结构：双向链表通常采用带表头结点的循环链表形式。,前驱方向 后继方向,lLink data rLink,结点指向p=p-lLink-rLink=p-rLink-lLink,非空表 空表,p-lLink,p-rLink,p,lLink,rLink,first,first,双向循环链表类的定义template class DblList;template class DblNode friend class DblList;private:Type data;/数据 DblNode*lLink,*rLink;/指针public:DblNode(Type value=0,DblNode*left,DblNode*right):data(value),lLink(left),rLink(right),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;/修改左链指针值,void setData(Type value)data=value;template class DblList private:DblNode*first,*current;public:DblLIst();/构造函数 DblList();/析构函数 int Length()const;/计算长度 int IsEmpty()/判链表空否 return first-rlink=first;,int Find(const Type,template DblList:DblList()/构造函数:建立双向循环链表的表头结点 first=current=new DblNode();if(first=NULL)cerr rLink=first-lLink=first;/表头结点的链指针指向自己,template int DblList:Length()const/计算带表头结点的双向循环链表的长度 DblNode*p=first-rLink;int count=0;while(p!=first)p=p-rLink;count+;return count;,搜索成功,搜索不成功,双向循环链表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,template int DblList:Find(const Type,双向循环链表的插入算法(非空表),first,first,31,48,15,后插入25,current,current,31,48,25,15,newnode-lLink=current;newnode-rLink=current-rLink;current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;,双向循环链表的插入算法(空表),first,后插入25,current,current,25,newnode-lLink=current;newnode-rLink=current-rLink;(=first)current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;(first-lLink=current),first,template void DblList:Insert(const Type,删除48,双向循环链表的删除算法,first,first,非空表,31,48,15,current,31,15,current,current-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;,删除31,双向循环链表的删除算法,first,first,31,current,current,current-rLink-lLink=current-lLink;current-lLink-rLink=current-rLink;,template void DblList:Remove()if(current!=first)DblNode*temp=current;/被删结点 current=current-rLink;/当前指针进到下一结点 current-lLink=temp-lLink;/将被删结点从链中摘下 temp-lLink-rLink=current;delete temp;/删去,template int DblList:First()if(!IsEmpty()current=first-rLink;return 1;current=first;return 0;,其他双向循环链表的公共操作,template int DblList:Next()if(current-rLink=first)/最后结点 current=first-rLink;return 0;current=current-rLink;return 1;template int DblList:Prior()if(current-lLink=first)/第一个结点 current=first-lLink;return 0;current=current-lLink;return 1;,五、稀疏矩阵,在矩阵操作(+、-、*、/)时矩阵非零元素会发生动态变化，用稀疏矩阵的链接表示可适应这种情况。稀疏矩阵的链接表示采用正交链表：行链表与列链表十字交叉。行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，第几列。,稀疏矩阵的结点,head,down,next,right,(a)表头结点(b)非零元素结点,right,value,down,row,col,aij,False,i,j,(c)建立aij结点,head,稀疏矩阵的正交链表表示的示例,稀疏矩阵的链表表示的类定义enum Boolean False,True;struct Triple int row,col;float value;class Matrix;class MatrixNode/矩阵结点定义friend class Matrix;friend istream/结点类型,Union Triple triple;MatrixNode*next;/矩阵元素结点(False)或链头结点(True)MatrixNode(Boolean,Triple*);/结点构造函数MatrixNode:MatrixNode(Boolean b,Triple*t)/矩阵结点构造函数 head=b;/结点类型 if(b)right=next=this;else triple=*t;,typedef MatrixNode*MatrixNodePtr;/一个指针数组,用于建立稀疏矩阵class Matrix friend istream,用正交链表表示的稀疏矩阵的建立istream,return is;MatrixNodePtr*H=new MatrixNodePtr(p);/建立表头指针数组,指向各链表的表头 for(int i=0;i t.row t.col t.value;/输入非零元素的三元组,if(t.row CurrentRow)/如果行号大于当前行,闭合当前行 last-right=HCurrentRow;CurrentRow=t.row;last=HCurrentRow;last=last-right=/链入当前行 new MatrixNode(False,/闭合最后一行,/闭合各列链表 for(i=0;i next-down=Hi;/链接所有表头结点 for(i=0;i next=Hi+1;Hp-1-next=matrix.headnode;matrix.headnode-right=H0;delete H;return is;,稀疏矩阵的删除,为执行稀疏矩阵的删除，需要使用可利用空间表来管理回收的空间。可利用空间表是单链表结构，只允许在表头插入或删除，其表头指针为av。使用可利用空间表，可以高效地回收循环链表。如果需要建立新的稀疏矩阵，还可以从可利用空间表中分配结点。,用正交链表表示的稀疏矩阵的删除Matrix:Matrix()if(headnode=NULL)return;MatrixNode*x=headnode-right,*y;headnode-right=av;av=headnode;while(x!=headnode)y=x-right;x-right=av;av=y;x=x-next;headnode=NULL;,