单链表链表的游标类静态链表 循环链表多项式及其相加双向链

1、单链表 链表的游标类 静态链表 循环链表 多项式及其相加 双向链表 稀疏矩阵,第三章 链表,单链表 (Singly Linked List),特点 每个元素(表项)由结点(Node)构成。 线性结构。 结点之间可以连续，可以不连续存储; 结点的逻辑顺序与物理顺序可以不一致; 表可扩充。,单链表的存储映像,free,(a) 可利用存储空间,a0,a2,a1,a3,free,first,(b) 经过一段运行后的单链表结构,单链表的类定义,多个类表达一个概念(单链表)。 链表结点(ListNode)类； 链表(List)类。 定义方式： 复合方式； 嵌套方式； 继承方式。,class List; /

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

3、表头指针 public: /链表操作 ;,链表类和链表结点类定义(继承方式) class ListNode /链表结点类 protected: int data; ListNode * link; ; class List : public class ListNode /链表类, 继承链表结点类的数据和操作 private: ListNode *first , *current; /表头指针 ;,在复合方式中，链表结点类中声明链表类是它的友元类，这样可以“奉献”它的私有成员给链表类。这种方式灵活。 在嵌套方式中，链表结点类是链表类的私有成员，这样限制了链表结点类的应用范围。 在继承方式中，链

4、表类声明为链表结点类的派生类，这在实现上是可行的。但在逻辑上是有问题的，如 三角形 is 多边形（继承关系） 链表 is 链表结点（显然概念有误）,单链表中的插入与删除,插入 第一种情况：在链表最前端插入 newnode-link = first ; first = newnode;,（插入前） （插入后）,(插入前) (插入后),第二种情况：在链表中间插入 newnode-link = current-link; current-link = newnode；,第三种情况：在链表末尾插入 newnode-link = current-link; current-link = newnode；

5、,(插入前) (插入后),int List : Insert ( int x, int i ) /在链表第 i ( 0) 号结点处插入新元素 x ListNode * p = current; current = first; for ( k = 0; k link; if ( current = NULL ,ListNode *newnode = /创建新结点 new ListNode(x, NULL); if ( first = NULL | i = 0 ) /插在表前 newnode-link = first; first = current = newnode; else /插在表中或

6、末尾 newnode-link = current-link; current = current-link = newnode; return 1; ,删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素,在单链表中删除含ai的结点,ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,删除前,删除后,int List : Remove ( Type ,if ( current = NULL | current-link = NULL ) cout link; /重新链接 current = current-link = q-link; x = q-data; de

7、lete q; /删除q return 1; ,带表头结点的单链表,表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。,非空表 空表,在带表头结点的单链表最前端插入新结点,newnode-link = p-link; p-link = newnode;,q = p-link; p-link = q-link; delete q;,从带表头结点的单链表中删除最前端的结点,(非空表）,(空表）,单链表的模板类,类模板将类的数据成员和成员函数设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中，增加了表头结点。,用模板定

8、义的单链表类,template class List; template class ListNode friend class List; Type data; /结点数据 ListNode *link; /结点链接指针 public: ListNode ( ) : link (NULL) /构造函数 ListNode ( Type item ) : data (item), link (NULL) ,ListNode (Type item, ListNode *next) : data (item), link (next) /以item和next建立一个新结点 ListNode * ge

9、tLink( ) return link; /取得结点的下一结点地址 Type getData ( ) return data; /取得结点中的数据 void setLink ( ListNode * next ) link = next; /修改结点的link指针 void setData ( Type value ) data = value; /修改结点的data值,; template class List /链表类 private: ListNode *first, *current; /链表的表头指针和当前元素指针 public: List ( Type value ) curre

10、nt = first = new ListNode ( value ); List ( List /析构函数,void MakeEmpty ( ); /将链表置为空表 int Length ( ) const; /计算链表的长度 ListNode * Find ( Type value ); /搜索含数据value的元素并成为当前元素 ListNode * Locate( int i ); /搜索第 i 号元素的地址并置为当前元素 int GetData ( Type /将链表当前元素删去, 填补者为当前元素,ListNode * Firster ( ) current = first; re

11、turn first; /当前指针置于表头, 返回表头结点地址 ListNode * First ( ) current = first-link; return current; /第一个结点为当前结点 ListNode * Next ( ); /下一个结点为当前结点 int NotNull ( ) return current != NULL; int NextNotNull ( ) return current != NULL ,template void List : MakeEmpty ( ) /删去链表中除表头结点外的所有其他结点 ListNode *q; while ( firs

12、t-link != NULL ) q = first-link; first-link = q-link; /将表头结点后第一号结点从链中摘下 delete q; /释放它 current = first; /当前指针置于表头结点 ,链表类部分操作的实现,template int List : Length ( ) const /求单链表的长度 ListNode *p = first-link; /检测指针 p 指示第一号结点 int count = 0; while ( p != NULL ) /逐个结点检测 p = p-link; count+; return count; ,first,

13、p,a0,a1,a2,c = 0,first,p,a0,a1,a2,c = 1,first,p,a0,a1,a2,c = 2,first,p,a0,a1,a2,c = 3,template ListNode * List : Find ( Type value ) /在链表中从头搜索其数据值为value的结点 current = first-link; /当前指针 current 指示第一号结点 while ( current != NULL ) if ( current-data = value ) break; else current = current-link; return cur

14、rent; /搜索失败时current = NULL,template ListNode * List : Locate ( int i ) /定位函数：返回表中第 i 号元素的地址, /i = 0为寻找表头结点的地址 if ( i link; k+; /找第 i 号结点 return current; /返回第 i 号结点地址或NULL /定位失败时current = NULL,template int List : GetData ( Type ,template int List : Insert ( Type value ) /将新元素value插入在链表中当前结点后 if ( cur

15、rent = NULL ) return 0; ListNode *newnode = /创建结点 new ListNode (value); newnode-link = current-link; current-link = newnode; current = newnode; return 1; /插入成功，函数返回1 ,template int List : Remove ( Type ,前插法建立单链表,从一个空表开始，重复读入数据： 生成新结点； 将读入数据存放到新结点的数据域中； 将该新结点插入到链表的前端。 直到读入结束符为止。,template void List : c

16、reateListF(Type endTag) Type val; ListNode *node; first = new ListNode; /表头结点 cin val; while ( val != endTag ) node = new ListNode(val); node-link = first-link; first-link = node; /插入到表前端 cin val; current = first; ,后插法建立单链表,每次将新结点加在插到链表的表尾； 设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面； 尾指针 last 初始时置为指向表头结点地址。,t

17、emplate void List : createListR(Type endTag) Type val; ListNode *node, *last; first = new ListNode; /表头结点 cin val; current = last = first; while ( val != endTag ) /last指向表尾 node = new ListNode(val); last-link = node; last = node; cin val; /插入到表末端 last-link = NULL; /表收尾 ,链表的游标类 (Iterator),游标类主要用于单链表的

18、搜索。 游标类的定义原则： 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 ;

19、public: private: Type data; ListNode *link; ;,template class List /链表类 public: private: ListNode *first, *last; ; template class ListIterator private: const List /当前结点指针public:,ListIterator ( const List /返回链表当前结点的下一个结点的地址 ,链表的游标类成员函数的实现 template Boolean ListIterator : NotNull ( ) /检查链表中当前元素是否非空 if (

20、 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 !

21、= NULL ) current = list.first-link; return ,list.first,current,约定链表中 没有表头结点,template ListNode* ListIterator : Next ( ) /返回链表中当前结点的下一个结点的地址 if ( current != NULL ,current,current,利用游标类 (iterator) 计算元素的和 int sum ( const List ,静态链表结构,静态链表定义,const int MaxSize = 100; /静态链表大小 template class StaticList; tem

22、plate class SListNode friend class StaticList; Type data; /结点数据 int link; /结点链接指针 template class StaticList SListNode elemMaxSize; int avil; /当前可分配空间首地址 ,将链表空间初始化,template void StaticList : InitList ( ) elem0.link = -1; avil = 1; /当前可分配空间从 1 开始建 /立带表头结点的空链表 for ( int i = 1; i link; return current; C

23、ircListNode * Next ( ) current = current-link; return current; CircListNode * Prior ( ); int Insert ( Type value ); int Remove ( Type,搜索成功,搜索不成功,循环链表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,current,current,current,current,current,current,current,current,循环链表的搜索算法,template CircListNode * C

24、ircList : Find ( Type value ) /在链表中从头搜索其数据值为value的结点 current = first-link; while ( current != first ,if ( first != NULL ) CircListNode *second = first-link; first-link = av; av = second; first = NULL; ,利用可利用空间表回收循环链表,first,av,first,av,回收前,回收后,second,if ( av = NULL ) newnode = new CircListNode; else

25、newnode = av; av = av-link; ,从可利用空间表分配结点,av,newnode,av,分配前的可利用空间表,分配后的可利用空间表和新结点,带尾指针的循环链表,rear,31,48,15,57,22,如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。 在表尾插入，时间复杂性 O(1) 在表尾删除，时间复杂性 O(n) 在表头插入，相当于在表尾插入 在表头删除，时间复杂性 O(1),将循环链表链入单链表链头,用循环链表求解约瑟夫问题,约瑟夫问题的提法 n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数, 报到第 m 个人，令其出列。然后

26、再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。,例如 n = 8 m = 3,约瑟夫问题的解法 #include #include “CircList.h” Template void Josephus (CircList /数m-1个人,cout clist; int n, m; cout n m; /形成约瑟夫环 for ( int i = 1; i link; break; case : /pa-exp pb-exp pc-link = pb; pc = pb; pb = pb-link; break; cas

27、e exp exp pc-link = pa; pc = pa; pa = pa-link; ,if ( pa != NULL ) pc-link = pa; else pc-link = pb; /剩余部分链入ch链 return ah; ,双向链表 (Doubly Linked List),双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构： 双向链表通常采用带表头结点的循环链表形式。,前驱方向 后继方向,lLink data rLink,结点指向 p = p-lLink-rLink = p-rLink-lLink,非空表 空表,p-lLink,p-rLink,

28、p,lLink,rLink,first,first,双向循环链表类的定义 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) ,DblNode ( Type value ) : data (v

29、alue), lLink (NULL), rLink (NULL) DblNode ( ) : data(0), 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*Righ

30、t ) rlink = Right; /修改右链指针值 void setData ( Type value ) data = value; ; template class DblList private: DblNode * first, * current; public: DblList ( Type uniqueVal ); /构造函数 DblList ( DblList /复制构造函数,DblList ( ); /析构函数 int Length ( ) const; /计算长度 int IsEmpty ( ) /判链表空否 return first-rlink = first; Db

31、lListNode * Find ( Type value ); /搜索链表中含value的结点 DblListNode * Firster ( ) current = first; return current; /当前指针置于表头结点 DblListNode * First ( ); /当前指针置于第一个结点,DblListNode * Next ( ); /当前指针置于后继结点 DblListNode * Prior ( ); /当前指针置于前驱结点 int Insert ( Type value ); /插入一个包含有值value的新结点 int Remove ( Type,templ

32、ate DblList : DblLIst ( Type uniqueVal ) /构造函数: 建立双向循环链表的表头结点 first = current = new DblNode ( uniqueVal ); 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; coun

33、t+; return count; /按前驱方向计算只需左、右互换即可,搜索成功,搜索不成功,双向循环链表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,template DblListNode * DblList : Find ( Type value ) /在双向循环链表中搜索含value的结点, 若 /找到, 则返回1, 同时current指针指向该结点, /否则函数返回0。 current = first-rLink; while ( current != first ,双向循环链表的插入算法 (非空表),first,first,

34、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 ) curr

35、ent-rLink = newnode; current = current-rLink; current-rLink-lLink = current; ( first -lLink = current ),first,template int DblList : Insert ( Type value ) if ( first-rlink = first ) /空表情形 current = first-rLink = new DblNode ( value, first, first ); else /非空表情形 current-rLink = new DblNode ( value, cu

36、rrent, current-rLink ); current = current-rLink; current-rLink-lLink = current; return 1; ,template DblList : DblLIst ( DblList,while ( p != RL-first ) /逐个结点复制 last-rLink = new DblNode ( p-data, last, last-rLink ); if ( last-rLink = NULL ) /分配新结点 cerr rLink; last-rLink-lLink = last; /链结完成 if ( RL-cu

37、rrent = p ) current = last; p = p-rLink; ,删除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

38、;,template int DblList : Remove ( Type ,template DbistNode * DblList : First ( ) if ( first-rLink = first ) current = first; else current = first-rLink; return current; template DbistNode * DblList : Next ( ) if ( current-rLink = first ) /最后结点 current = first -rLink; else current = current-rLink;,re

39、turn current; template DbistNode * DblList : Prior ( ) if ( current-lLink = first ) /第一个结点 current = first-lLink; else current = current-lLink; return current; ,稀疏矩阵,在矩阵操作(+、-、*、/)时矩阵非零元素会发生动态变化，用稀疏矩阵的链接表示可适应这种情况。 稀疏矩阵的链接表示采用正交链表：行链表与列链表十字交叉。 行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，第几列。,稀疏矩阵的结点,head,down,next,right,(a) 表头结点 (b) 非零元素结点,right,value,down,row,col,aij,False,i,j,(c) 建立aij结点,head,稀疏矩阵的正交链表表示的示例,稀疏矩阵的链表表示的类定义 enum Boolean False,