第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.

Presentation on theme: "第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵."— Presentation transcript:

1 第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵

2 单链表 (Singly Linked List)
特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以连续，可以不连续存储 结点的逻辑顺序与物理顺序可以不一致 表可扩充 data link a0 a1 a2 a3 a4 first 

3 单链表的存储映像 (a) 可利用存储空间 free a0 a2 a1 a3  free first (b) 经过一段运行后的单链表结构

4 单链表的类定义 多个类表达一个概念(单链表)。 链表结点(ListNode)类 链表(List)类 链表游标(Iterator)类 定义方式
复合方式 嵌套方式 继承方式

5 class ListNode { //链表结点类 friend class List; //链表类为其友元类 private:
int data; //结点数据, 整型 ListNode * link; //结点指针 }; class List { //链表类 ListNode *first , *last; //表头指针

6 class List { //链表类定义(嵌套方式)
private: class ListNode { //嵌套链表结点类 public: int data; ListNode *link; }; ListNode *first , *last; //表头指针 //链表操作………

7 链表类和链表结点类定义(继承方式) class ListNode { //链表结点类 protected: int data; ListNode * link; }; class List : public class ListNode { //链表类, 继承链表结点类的数据和操作 private: ListNode *first , *last; //表头指针

8 newnode->link = first ;
单链表中的插入与删除 插入 第一种情况：在第一个结点前插入 newnode->link = first ; first = newnode; newnode newnode first first （插入前） （插入后）

9 newnode->link = p->link;
第二种情况：在链表中间插入 newnode->link = p->link; p->link = newnode； newnode newnode p p (插入前) (插入后)

10 newnode->link = p->link;
第三种情况：在链表末尾插入 newnode->link = p->link; p->link = newnode； newnode newnode  p p  (插入前) (插入后)

11 int List :: Insert ( int x, int i ) {
//在链表第 i 个结点处插入新元素 x ListNode * p = first; for ( k = 0; k < i -1; k++ ) //找第 i-1个结点 if ( p == NULL ) break; else p = p->link; if ( p == NULL && first != NULL ) { cout << “无效的插入位置!\n”; return 0; } ListNode *newnode = //创建新结点 new ListNode(x, NULL);

12 if ( first == NULL || i == 0 ) { //插在表前
newnode->link = first; if ( first == NULL ) last = newnode; first = newnode; } else { //插在表中或末尾 newnode->link = p->link; if ( p->link == NULL ) last = newnode; p ->link = newnode; return 1;

13 删除     在单链表中删除含ai的结点 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素 ai-1 ai
删除前  ai-1 ai ai+1  p q 删除后 在单链表中删除含ai的结点

14 int List :: Remove ( int i ) {
ListNode *p, *q; if ( i == 0 ) //删除表中第 1 个结点 { q = first; p = first = first->link; } else { p = first; int k = 0; //找第 i-1个结点 while ( p != NULL && k < i-1 ) { p = p->link; k++; } if ( p == NULL || p->link == NULL ) { cout << “无效的删除位置!\n”; return 0; }

15 else { //删除表中或表尾元素 q = p->link; //重新链接 p->link = q->link; } if ( q == last ) last = p; //可能修改last Type x = q->data; delete q; //删除q return x; //返回第 i 个结点的值

16 带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。
first a1 an first 非空表 空表

17 newnode->link = p->link;
在带表头结点的单链表第一个结点前插入新结点 first first p 插入 p newnode newnode first first 插入 p p newnode newnode newnode->link = p->link; if ( p->link == NULL ) last = newnode; p->link = newnode;

18 从带表头结点的单链表中删除第一个结点 q = p->link; p q p->link = q->link;
first (非空表） first p q q = p->link; p->link = q->link; delete q; if ( p->link == NULL ) last = p; first first p q (空表）

19 单链表的模板类 类模板将类的数据成员和成员函数设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中，增加了表头结点。

20 用模板定义的单链表类 template <class Type> class List;
template <class Type> class ListNode { friend class List<Type>; Type data; //结点数据 ListNode<Type> *link; //结点链接指针 public: ListNode ( ) : link (NULL) { } //构造函数 ListNode ( Type& item ) : data (item), link (NULL) { }

21 ListNode<Type> * getNode ( Type& item,
ListNode<Type> *next = NULL ) ; //以item和next建立一个新结点 ListNode<Type> * getLink( ) { return link; } //取得结点的下一结点地址 Type getData ( ) { return data; } //取得结点中的数据 void setLink ( ListNode<Type> * next ) { link = next; } //修改结点的link指针

22 void setData ( Type value ) { data = value; }
}; template <class Type> class List { //链表类 private: ListNode<Type> *first, *last; //链表的表头指针和表尾指针 public: List ( Type& value ) { last = first = new ListNode<Type> ( value ); }

23 ~List ( ) { MakeEmpty ( ); delete first; }
void MakeEmpty ( ); //将链表置为空表 int Length ( ) const; //计算链表的长度 ListNode<Type> * Find ( Type value ); //搜索含数据value的元素并成为当前元素 ListNode<Type> * Locate( int i ); //搜索第 i 个元素的地址并置为当前元素 Type * GetData ( int i ); //取出表中第 i 个元素的值 int Insert ( Type value, int i ); //将value插在表中第 i 个元素后

24 Type * Remove ( int i ); //将链表中第 i 个元素删去 };

25 链表结点部分操作的实现 template <class Type>
ListNode<Type> *ListNode<Type> :: GetNode ( Type& item, ListNode <Type> * next = NULL ) { //建立新结点, 函数返回新结点地址。 ListNode<Type> *newnode = new ListNode<Type> ( item ); newnode->link = next; return newnode; }

26 链表类部分操作的实现 template <class Type>
void List <Type> :: MakeEmpty ( ) { //删去链表中除表头结点外的所有其他结点 ListNode<Type> *q; while ( first->link != NULL ) { q = first->link; first->link = q->link; //将表头结点后第一个结点从链中摘下 delete q; //释放它 } last = first; //修改表尾指针

27 first a0 a1 a2 q first a1 a2 q first a2 q first current

28 template <class Type>
int List<Type> :: Length ( ) const { //求单链表的长度 ListNode<Type> *p = first->link; //检测指针 p 指示第一个结点 int count = 0; while ( p != NULL ) { //逐个结点检测 p = p->link; count++; } return count;

29 first a0 a1 a2 c = 0 p first a0 a1 a2 c = 1 p first a0 a1 a2 c = 2 p first a0 a1 a2 c = 3 p

30 template <class Type> ListNode<Type> *
List <Type> :: Find ( Type value ) { //在链表中从头搜索其数据值为value的结点 ListNode<Type> * p = first->link; //检测指针 p 指示第一个结点 while ( p != NULL ) if ( p->data == value ) break; else p = p->link; return p; // p 在搜索成功时返回找到的结点地址 // p 在搜索不成功时返回空值 }

31 template <class Type> ListNode<Type> *
List<Type> :: Locate ( int i ) { //定位函数。返回表中第 i 个元素的地址 //若 i < -1或 i 超出，则返回NULL if ( i < -1 ) return NULL; // i 值不合理 if ( i == -1 ) return first; //返回表头地址 ListNode<Type> * p = first->link; int k = 0; while ( p != NULL && k < i ) { p = p->link; k++; } //找第 i 个结点 return p; //返回第 i 个结点地址或NULL }

32 template <class Type>
Type * List<Type> :: GetData ( int i ) { //取出链表中当前元素的值 ListNode<Type> *p = Locate ( i ); // p 指向链表第 i 个结点 if ( p == NULL || p == first ) return NULL; else return & p->data; }

33 template <class Type>
int List<Type> :: Insert ( Type value, int i ) { //将新元素value插入在链表第 i 个结点处 ListNode<Type> *p = Locate ( i-1 ); // p 指向链表第 i-1个结点 if ( p == NULL ) return 0; ListNode<Type> *newnode = //创建结点 GetNode ( value, p->link ); if ( p->link == NULL ) last = newnode; p->link = newnode; //重新链接 return 1; //插入成功，函数返回1 }

34 template <class Type>
Type * List<Type> :: Remove ( int i ) { //将链表第 i 个元素删去, 函数返回该元素 ListNode<Type> *p = Locate (i-1), *q; if ( p == NULL || p->link == NULL ) return NULL; q = p->link; p->link = q->link; //重新链接 Type * value = new Type ( q->data ); if ( q == last ) last = p; delete q; return value; }

35 前插法建立单链表 从一个空表开始，重复读入数据： 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端
直到读入结束符为止。 first first newnode newnode

36 template <class Type>
void List <Type> :: createListF ( ) { char ch; ListNode<Type> *s; first = new ListNode<Type>; //建立表头结点 first->link = NULL; cin >> ch; while ( ch != ‘\n’ ) { s = GetNode ( ch, first->link ); if (first->link == NULL ) last = s; //建立新结点 first->link = s; //插入到表前端 cin >> ch; }

37 后插法建立单链表 每次将新结点加在插到链表的表尾； 设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面；
first r r newnode newnode r r

38 template <class Type>
void List <Type> :: createListR ( ) { char ch; first = new ListNode<Type>; //建立表头结点 ListNode<Type> *s, *r = first; // r指向表尾 cin >> ch; while ( ch != ‘\n’ ) { s = new ListNode<Type>(ch);//建立新结点 r ->link = s; r = s; //插入到表末端 } r ->link = NULL; last = r; //表收尾

39 链表的游标类 (Iterator) 游标类主要用于单链表的搜索。 游标类的定义原则：
Iterator类是List类和ListNode类的友元类。 Iterator对象引用已有的List类对象。 Iterator类有一数据成员current，记录对单链表最近处理到哪一个结点。 Iterator类提供若干测试和搜索操作

40 表示链表的三个类的模板定义 enum Boolean { False, True };
template <class Type> class List; template <class Type> class ListIterator; template <class Type> class ListNode { //表结点 friend class List <Type>; friend class ListIterator <Type>; public: ……… private: Type data; ListNode<Type> *link; };

41 template <class Type> class List { //链表类
public: ……… private: ListNode<Type> *first, *last; }; template <class Type> class ListIterator { const List<Type> & list; //引用已有链表 ListNode<Type> *current; //当前结点指针public:

42 ListIterator ( const List<Type> & l )
: list ( l ), current ( l.first ) { } //构造函数: 引用链表 l, 表头为当前结点 ListNode<Type> * Firster ( ) { current = first; return first; } //当前指针置于表头, 返回表头结点地址 Boolean NotNull ( ); //检查当前指针空否 Boolean NextNotNull ( ); //检查链表中下一结点是否非空 ListNode <Type> *First ( ); //返回第一个结点 ListNode <Type> *Next ( ); //返回链表当前结点的下一个结点的地址 }

43 链表的游标类成员函数的实现 template <class Type>
Boolean ListIterator<Type> :: NotNull ( ) { //检查链表中当前元素是否非空 if ( current != NULL ) return True; else return False; } current current 情况 1 返回True 情况 2 返回False

44 template <class Type>
Boolean ListIterator<Type> :: NextNotNull ( ) { //检查链表中下一元素是否非空 if ( current != NULL && current->link != NULL ) return True; else return False; } current current 情况 1 返回True 情况 2 返回False

45 template <class Type>
ListNode<Type>* ListIterator<Type> :: First ( ) { //返回链表中第一个结点的地址 if ( list.first->link != NULL ) { current = list.first->link; return &current->data; } else { current = NULL; return NULL; } 约定链表中 没有表头结点 list.first current

46 template <class Type>
ListNode<Type>* ListIterator<Type> :: Next ( ) { //返回链表中当前结点的下一个结点的地址 if ( current != NULL && current->link != NULL ) { current = current->link; return & current->data; } else { current = NULL; return NULL; } current current

47 利用游标类 (iterator) 计算元素的和
int sum ( const List<int> &L ) { ListIterator<int> li (L); //定义游标对象, current 指向 li.first if ( ! li.NotNull ( ) ) return 0; //链表为空时返回0 int retval = li.First( )->data; //第一个元素 while ( li.nextNotNull ( ) ) //链表未扫描完 retval += li.Next( )->data; //累加 return retval; }

48 静态链表结构

49 静态链表定义 const int MaxSize = 100; //静态链表大小
template <class Type> class StaticList; template <class Type> class SListNode { friend class StaticList<Type>; Type data; //结点数据 int link; //结点链接指针 } template <class Type> class StaticList { SListNode<Type> Nodes[MaxSize]; int newptr; //当前可分配空间首地址

50 将链表空间初始化 template <class Type>
void StaticList<Type> :: InitList ( ) { Nodes[0].link = -1; newptr = 1; //当前可分配空间从 1 开始建 //立带表头结点的空链表 for ( int i = 1; i < MaxSize-1; i++ ) Nodes[i].link = i+1; //构成空闲链接表 Nodes[MaxSize-1].link = -1; //链表收尾 }

51 在静态链表中查找具有给定值的结点 template <class Type> int StaticList<Type> :: Find ( Type x ) { int p = Nodes[0].link; //指针 p 指向链表第一个结点 while ( p != -1 ) if ( Nodes[p].data != x) p = Nodes[p].link; else break; //逐个结点检测查找具有给定值的结点 return p; }

52 在静态链表的表尾追加一个新结点 template <class Type> int StaticList<Type> :: Append ( Type x ) { if ( newptr == -1 ) return 0; //追加失败 int q = newptr; //分配结点 newptr = Nodes[newptr].link; Nodes[q].data = x; Nodes[q].link = -1; int p = 0; //查找表尾 while ( Nodes[p].link != -1 ) p = Nodes[p].link; Nodes[p].link = q; //追加 return 1; }

53 在静态链表中查找第 i 个结点 template <class Type> int StaticList<Type> :: Locate ( int i ) { if ( i < 0 ) return -1; //参数不合理 if ( i == 0 ) return 0; int j = 0, p = Nodes[0].link; while ( p != -1 && j < i ) { p = Nodes[p].link; j++; } //循链查找第 i 号结点 return p; }

54 在静态链表第 i 个结点处插入一个新结点 template <class Type> int StaticList<Type> :: Insert ( int i, Type x ) { int p = Locate ( i-1 ); if ( p == -1 ) return 0; //找不到结点 int q = newptr; //分配结点 newptr = Nodes[newptr].link; Nodes[q].data = x; Nodes[q].link = Nodes[p].link; //链入 Nodes[p].link = q; return 1; }

55 在静态链表中释放第 i 个结点 template <class Type> int StaticList<Type> :: Remove ( int i ) { int p = Locate ( i-1 ); if ( p == -1 ) return 0; //找不到结点 int q = Nodes[p].link; //第 i 号结点 Nodes[p].link = Nodes[q].link; Nodes[q].link = newptr; //释放 newptr = q; return 1; }

56 循环链表 (Circular List) 循环链表是单链表的变形。
循环链表的最后一个结点的 link 指针不为 NULL，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。

57 循环链表的示例 带表头结点的循环链表 first a0 a1 a2 an-1 first a0 a1 an-1 (非空表) first
(空表)

58 循环链表类的定义 template <class Type> class CircList;
template <class Type> class CircListNode { friend class CircList <Type>; public: CircListNode ( Type d = 0, CircListNode<Type> *next = NULL ) : data ( d ), link ( next ) { } //构造函数private: Type data; //结点数据 CircListNode<Type> *link; //链接指针 }

59 template <class Type> class CircList {
private: CircListNode<Type> *first, *current, *last; //链表的表头指针、当前指针和表尾指针 public: CircList ( Type value ); ~CircList ( ); int Length ( ) const; Boolean IsEmpty ( ) { return first->link == first; } Boolean Find ( const Type & value );

60 Type getData ( ) const; void Firster ( ) { current = first; } Boolean First ( ); Boolean Next ( ); Boolean Prior ( ); void Insert ( const Type & value ); void Remove ( ); };

61 循环链表的搜索算法 搜索成功 搜索不成功   搜索15     搜索25 first 31 48 15 57  current

62 循环链表的搜索算法 template <class Type>
CircListNode<Type> * CircList<Type> :: Find ( Type value ) { //在链表中从头搜索其数据值为value的结点 CircListNode<Type> * p = first->link; //检测指针 p 指示第一个结点 while ( p != first && p->data != value ) p = p->link; return p; }

63 利用可利用空间表回收循环链表 if ( first != NULL ) {
CircListNode<Type> *second = first->link; first->link = av; av = second; first = NULL; } 回收前 first av 回收后 av first

64 从可利用空间表分配结点 if ( av == NULL ) newnode = new CircListNode<Type>;
else { newnode = av; av = av->link; } 分配前的可利用空间表 av newnode 分配后的可利用空间表和新结点 av

65 用循环链表求解约瑟夫问题 约瑟夫问题的提法 n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数, 报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。

66 例如 n = 8 m = 3

67 约瑟夫问题的解法 #include <iostream.h> #include “CircList.h”
Template<Type> void CircList<Type> :: Josephus ( int n, int m ) { Firster ( ); 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 ( ); //删去 }

68 } void main ( ) { CircList<int> clist; int n, m; cout << “输入游戏者人数和报数间隔 : ”; cin >> n >> m; for ( int i = 1; i <= n; i++ ) clist.insert (i); //形成约瑟夫环 clist.Josephus (n, m); //解决约瑟夫问题

69 多项式 (Polynomial) n 阶多项式 Pn(x) 有 n+1 项。 系数 c0, c1, c2, …, cn

70 多项式的链表表示 在多项式的链表表示中每个结点三个数据成员： 优点是： 多项式的项数可以动态地增长，不存在存储溢出问题。
插入、删除方便，不移动元素。 Data  Term coef exp link

71 多项式(polynomial)类的链表定义
struct Term { //多项式结点定义 float coef; //系数 int exp; //指数 Term ( float c, int e ) { coef = c; exp = e; } }; class Polynomial { //多项式类的定义 List<Term> poly; //构造函数 friend Polynomial & operator + ( Polynomial &, Polynomial &); //加法

72 多项式链表的相加 AH = 1 - 3x6 + 7x12 BH = - x4 + 3x6 - 9x10 + 8x14 1 0 -3 6
AH.first 1 0 -3 6 7 12  -1 4 3 6 -9 10 8 14  BH.first 1 0 -1 4 -9 10 CH.first 7 12 8 14 

73 两个多项式的相加算法 扫描两个多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到结果多项式。 若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。

74 pa pc AH.first 1 0 -3 6 7 12  -1 4 3 6 -9 10 8 14  p pb BH.first CH.first 1 0 -1 4 -9 10 7 12 8 14 

75 pa pc AH.first 1 0 -3 6 7 12  -1 4 3 6 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

76 pa AH.first 1 0 -3 6 7 12  pc -1 4 3 6 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

77 pa AH.first 1 0 -3 6 7 12  pc -1 4 3 6 -9 10 8 14  p pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

78 pa AH.first 1 0 0 6 7 12  pc p -1 4 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

79 pa AH.first 1 0 7 12  pc -1 4 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

80 pa AH.first 1 0 7 12  pc -1 4 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

81  pc pa == AH.first 1 0 7 12  -1 4 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

82  pc pa == AH.first 1 0 7 12 -1 4 -9 10 8 14  pb CH.first 1 0 -1 4 -9 10 7 12 8 14 

83 friend Polynomial& operator +
( Polynomial& ah, Polynomial& bh ) { //两个带头结点的按升幂排列的多项式相加， //返回结果多项式链表的表头指针，结果不 //另外占用存储, 覆盖ah和bh链表 ListNode<Term> *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的表头结点

84 while ( pa != NULL && pb != NULL ) {
a = pa->data; b = pb->data; switch ( compare ( a.exp, b.exp ) ) { case '==' : //pa->exp == pb->exp a.coef = a.coef + b.coef; //系数相加 p = pb; pb = pb->link; delete p; //删去原pb所指结点 if ( abs(a.coef ) < ) { p = pa; pa = pa->link; delete p; } //相加为零, 该项不要 else { //相加不为零, 加入ch链 pa->data = a; pc->link = pa;

85 pc = pa; pa = pa->link;
} break; case '>' : //pa->exp > pb->exp pc->link = pb; pc = pb; pb = pb->link; case '<' : //pa->exp < pb->exp pc->link;

86 if ( pa->link ) pc->link = pa;
else pc->link = pb; //剩余部分链入ch链 return ah; }

87 双向链表 (Doubly Linked List)
双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构： 双向链表通常采用带表头结点的循环链表形式。 lLink data rLink 前驱方向   后继方向

88 结点指向 p == p->lLink->rLink == p->rLink->lLink
first first 非空表 空表 结点指向 p == p->lLink->rLink == p->rLink->lLink rLink lLink p->lLink p p->rLink

89 双向循环链表类的定义 template <class Type> class DblList;
template <class Type> class DblNode { friend class DblList<Type>; private: Type data; //数据 DblNode<Type> * lLink, * rLink; //指针 public: DblNode (Type value, DblNode<Type> * left, DblNode<Type> * right ) : data (value), lLink (left), rLink (right) { }

90 DblNode ( Type value ) : data (value),
lLink (NULL), rLink (NULL) { } DblNode<Type> * getLeftLink ( ) { return llink; } //取得左链指针值 DblNode<Type> * getRightLink ( ) { return rlink; } //取得右链指针值 Type getData ( ) { return data; } void setLeftLink ( DblNode<Type>*Left ) { llink = Left; } //修改左链指针值 void setRightLink ( DblNode<Type>*Right ) { rlink = Right; } //修改左链指针值

91 void setData ( Type value ) { data = value; }
}; template <class Type> class DblList { private: DblNode<Type> * first, * current; public: DblLIst ( Type uniqueVal ); //构造函数 ~DblList ( ); //析构函数 int Length ( ) const; //计算长度 int IsEmpty ( ) //判链表空否 { return first->rlink == first; }

92 int Find ( const Type& target );
void Firster ( ) { current = first; } //当前指针置于表头结点。 int First ( ) ; //当前指针置于第一个结点 int Next ( ); //当前指针置于后继结点 int Prior ( ); //当前指针置于前驱结点 void Insert ( const Type& value ); //插入一个包含有值value的新结点 void Remove ( ); //删除当前结点 };

93 template <class Type> DblList<Type> :: DblLIst ( Type uniqueVal ) {
//构造函数: 建立双向循环链表的表头结点 first = current = new DblNode<Type> ( uniqueVal ); if (first == NULL ) { cerr << “存储分配错!\”; exit(1); } first->rLink = first->lLink = first; //表头结点的链指针指向自己 }

94 template <class Type>
int DblList<Type> :: Length ( ) const { //计算带表头结点的双向循环链表的长度 DblNode<Type> * p = first->rLink; int count = 0; while ( p != first ) { p = p->rLink; count++; } return count; }

95 双向循环链表的搜索算法 搜索成功 搜索不成功   搜索15     搜索25 first 31 48 15 57  first

96 template <class Type> int DblList<Type> ::
Find ( const Type& target ) { //在双向循环链表中搜索含target的结点, 若 //找到, 则返回1, 同时current指针指向该结点, //否则函数返回0。 DblNode<Type> * current = first->rLink; while ( current != first && current->data != target ) current = current->rLink; if ( current != first ) return 1; else return 0; }

97 双向循环链表的插入算法 (非空表) current 后插入25 current newnode->lLink = current;
first 31 48 15 后插入25 current first 31 48 25 15 current newnode->lLink = current; newnode->rLink = current->rLink; current->rLink = newnode; current = current->rLink; current->rLink->lLink = current;

98 双向循环链表的插入算法 (空表) current 后插入25 current newnode->lLink = current;
first first 25 current 后插入25 current newnode->lLink = current; newnode->rLink = current->rLink; ( = first ) current->rLink = newnode; current = current->rLink; current->rLink->lLink = current; ( first >lLink = current )

99 template <class Type> void DblList<Type> ::
Insert ( const Type & value ) { if ( current == first ) //空表情形 current = first->rLink = new DblNode<Type> ( value, first, first ); else { //非空表情形 current->rLink = new DblNode<Type> ( value, current, current->rLink ); current = current->rLink; } current->rLink->lLink = current;

100 双向循环链表的删除算法 非空表 删除48 current current
first 31 48 15 删除48 current first 31 15 current current->rLink->lLink = current->lLink; current->lLink->rLink = current->rLink;

101 双向循环链表的删除算法 删除31 current current
first first 31 删除31 current current current->rLink->lLink = current->lLink; current->lLink->rLink = current->rLink;

102 template <class Type>
void DblList<Type> :: Remove ( ) { if ( current != first ) { DblNode *temp = current; //被删结点 current = current->rLink; //当前指针进到下一结点 current->lLink = temp->lLink; //将被删结点从链中摘下 temp->lLink->rLink = current; delete temp; //删去 }

103 其他双向循环链表的公共操作 template <class Type>
DblList<Type> :: DblLIst ( Type uniqueVal ) { //双向循环链表的构造函数, 创建表头结点 first = new DblNode<Type> ( uniqueVal ); first→rLink = first→lLink = first; } int DblList<Type> :: Length ( ) const { //求双向循环链表的长度(不计表头结点)

104 DblNode<Type> * p = first->rLink;
int count = 0; while ( p != first ) { p = p->rLink; count++; } return count; } template <class Type> int DblList<Type> :: First ( ) { if ( !IsEmpty ( ) ) { current = first->rLink; return 1; } current = first; return 0;

105 template <class Type>
int DblList<Type> :: Next ( ) { if ( current->rLink == first ) //最后结点 { current = first ->rLink; return 0; } current = current->rLink; return 1; } int DblList<Type> :: Prior ( ) { if ( current->lLink == first ) //第一个结点 { current = first ->lLink; return 0; } current = current->lLink; return 1;

106 稀疏矩阵 在矩阵操作(+、-、*、/)时矩阵非零元素会发生动态变化，用稀疏矩阵的链接表示可适应这种情况。
稀疏矩阵的链接表示采用正交链表：行链表与列链表十字交叉。 行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，第几列。

107 稀疏矩阵的结点 head next head row col down right down value right False i j
(a) 表头结点 (b) 非零元素结点 False i j a[i][j] (c) 建立a[i][j]结点

108 稀疏矩阵的正交链表表示的示例

109 稀疏矩阵的链表表示的类定义 enum Boolean { False, True };
struct Triple { int row, col; float value; }; class Matrix; class MatrixNode { //矩阵结点定义 friend class Matrix; friend istream &operator >> ( istream &, Matrix & ); //矩阵输入重载函数 private: MatrixNode *down, *right; //列/行链指针 Boolean head; //结点类型

110 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;

111 typedef MatrixNode *MatrixNodePtr;
//一个指针数组, 用于建立稀疏矩阵 class Matrix { friend istream& operator >> ( istream &, Matrix & ); //矩阵输入 public: ~Matrix ( ); //析构函数 private: MatrixNode *headnode; //稀疏矩阵的表头 };

112 用正交链表表示的稀疏矩阵的建立 istream & operator
>> ( istream & is, Matrix & matrix ) { Triple s; int p; is >> s.row >> s.col >> s.value; //输入矩阵的行数, 列数和非零元素个数 if ( s.row > s.col ) p = s.row; else p = s.col; //取行、列数大者 matrix.headnode = //整个矩阵表头结点 new MatrixNode ( False, &s ); if ( !p ) { //零矩阵时 matrix.headnode->right = matrix.headnode;

113 return is; } MatrixNodePtr *H = new MatrixNodePtr ( p );
//建立表头指针数组, 指向各链表的表头 for ( int i = 0; i < p; i++ ) H[i] = new MatrixNode ( True, 0 ); int CurrentRow = 0; MatrixNode *last = H[0]; //当前行最后结点 for ( i = 0; i < s.value; i++ ) { //建立矩阵 Triple t; is >> t.row >> t.col >> t.value; //输入非零元素的三元组

114 if ( t.row > CurrentRow ) {
//如果行号大于当前行,闭合当前行 last->right = H[CurrentRow]; CurrentRow = t.row; last = H[CurrentRow]; } last = last->right = //链入当前行 new MatrixNode ( False, &t ); H[t.col]->next = H[t.col]->next->down = last; //链入列链表 last->right = H[CurrentRow]; //闭合最后一行

115 //闭合各列链表 for ( i = 0; i < s.col; i++ ) H[i]->next->down = H[i]; //链接所有表头结点 for ( i = 0; i < p-1; i++ ) H[i]->next =H[i+1]; H[p-1]->next = matrix.headnode; matrix.headnode->right = H[0]; delete [ ] H; return is; }

116 稀疏矩阵的删除 为执行稀疏矩阵的删除，需要使用可利用空间表来管理回收的空间。
可利用空间表是单链表结构，只允许在表头插入或删除，其表头指针为av。 使用可利用空间表，可以高效地回收循环链表。 如果需要建立新的稀疏矩阵，还可以从可利用空间表中分配结点。

117 用正交链表表示的稀疏矩阵的删除 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;