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

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

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

2 一、单链表

3 线性表的链式表示 顺序表的优点是可以随机选取表中元素 缺点是插入删除操作复杂。 用指针将互不相连的内存结点串成的 线性表叫线性链表。
结点 node 由一个数据元素域，一个或几个 指针域组成。单链表的结点只有一个指针域。

4 几个结点，前一个结点的指针，指向后一个结点，就连接成一个线性链表。
线性链表的优点则是插入，删除快捷，缺点是选取复杂。

5 #include <stdlib.h〉 #include <iostream.h>
1. 结点类的定义 #include <stdlib.h〉 #include <iostream.h> template <class T> class Node { Node<T> *next; //next 是下一个结点的地址 public: T data; // the data is public Node(const T& item, Node<T>* ptrnext=NULL); // list modification methods void InsertAfter(Node<T> *p); Node<T> * DeleteAfter(void); // obtain the address of the next node Node<T> *NextNode(void) const; };

6 // constructor. initialize data and // pointer members
template <class T> Node<T>::Node(const T& item, Node<T>* ptrnext) : data(item), next(ptrnext)） { }

7 // return value of private member next
template <class T> Node<T>* Node<T>::NextNode(void) const { return next; }

8 // insert a node p after the current one
template <class T> void Node<T>::InsertAfter(Node<T> *p) { // p points to successor of the current // node, and current node points to p. p->next = next; next = p; }

9 // delete the node following current and return its address
template <class T> Node<T>* Node<T>::DeleteAfter(void) { // save address of node to be deleted Node<T>* tempPtr = next; // if there isn't 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; }

10 { Node<char>*a,*b,*c; a=new Node<char>('a');
2．人工建立一个链表 void main(void) { Node<char>*a,*b,*c; a=new Node<char>('a'); b=new Node<char>('b'); c=new Node<char>('c'); Node<char>*head,*p; head=new Node<char>(' '); p=head; head->InsertAfter(a); head->InsertAfter(b); head->InsertAfter(c); while(p!=NULL) { cout << p->data<<" "; p=p->NextNode( ); } } 测试结果：打印 c b a

11 template <class T> { Node<T> *newNode;
3. 定义线性链表的一些操作 #include "node.h" // allocate a node with data member item and pointer nextPtr template <class T> Node<T>*GetNode(constT&item,Node<T>*nextPtr = NULL) { Node<T> *newNode; // allocate memory while passing item and NextPtr to // constructor. terminate program if allocation fails newNode = new Node<T>(item, nextPtr); if (newNode == NULL) { cerr << "Memory allocation failure!" << endl; exit(1); } return newNode; }

12 enum AppendNewline {noNewline, addNewline};
template <class T> // print a linked list void PrintList (Node<T> *head, AppendNewline addnl = noNewline ) { // currPtr chains through the list, starting at head Node<T> *currPtr = head; // print the current node's data until end of list while(currPtr != NULL) { // output newline if addl == addNewline if(addnl == addNewline) cout << currPtr->data << endl; else cout << currPtr->data << " "; // move to next node currPtr = currPtr->NextNode( ); } }

13 // find an item in a linked list head; return TRUE and
// value of previous pointer if found; otherwise return FALSE template <class T> int Find(Node<T> *head, T& item, Node<T>* &prevPtr) { Node<T> *currPtr = head; // begin traversal at first node prevPtr = NULL; // cycle through the list until end of list while(currPtr != NULL) { if (currPtr->data == item) {item = currPtr->data; return 1;} prevPtr = currPtr; currPtr = currPtr->NextNode( );} return 0; // failed to locate item }

14 // insert item at the front of list
template <class T> void InsertFront(Node<T>* & head, T item) { // allocate new node so it points to original list head // update the list head head = GetNode(item,head); }

15 // find rear of the list and append item
template <class T> void InsertRear(Node<T>* & head, const T& item) { Node<T> *newNode, *currPtr = head; if (currPtr == NULL) // if list is empty, insert item at the front InsertFront(head,item); else { // find the node whose pointer is NULL while(currPtr->NextNode( ) != NULL) currPtr = currPtr->NextNode( ); // allocate node and insert at rear (after currPtr) newNode = GetNode(item); currPtr->InsertAfter(newNode); }

16 // delete the first node of the list
template <class T> void DeleteFront(Node<T>* & head) { // save the address of node to be deleted Node<T> *p = head; // make sure list is not empty if (head != NULL) { // move head to second node and delete original head = head->NextNode( ); delete p; }

17 // delete the first occurrence of key in the list
template <class T> void Delete (Node<T>* & head, T key) { Node<T> *currPtr = head, *prevPtr = NULL; if (currPtr == NULL) return; while (currPtr != NULL && currPtr->data != key) { prevPtr = currPtr; currPtr = currPtr->NextNode( ); } if (currPtr != NULL) { if(prevPtr == NULL) head = head->NextNode(); else prevPtr->DeleteAfter(); delete currPtr; } }

18 // insert item into the ordered list
template <class T> void InsertOrder(Node<T>* & head, T item) { Node<T> *currPtr, *prevPtr, *newNode; prevPtr = NULL; currPtr = head; while (currPtr != NULL) { if (item < currPtr->data) break; prevPtr = currPtr; currPtr = currPtr->NextNode( ); } if (prevPtr == NULL) InsertFront(head,item); else { newNode = GetNode(item); prevPtr->InsertAfter(newNode); } }

19 // delete all the nodes in the linked list
template <class T> void ClearList(Node<T> * &head) { Node<T> *currPtr, *nextPtr; currPtr = head; while(currPtr != NULL) { nextPtr = currPtr->NextNode( ); delete currPtr; currPtr = nextPtr; } head = NULL; }

20 链表插入排序 #include <iostream.h> #pragma hdrstop #include "node.h"
#include "nodelib.h"

21 template <class T> void LinkSort(T a[], int n)
{ Node<T> *ordlist = NULL, *currPtr; int i; for (i=0;i < n;i++) InsertOrder(ordlist, a[i]); currPtr = ordlist; i = 0; while(currPtr != NULL) { a[i++] = currPtr->data; currPtr = currPtr->NextNode( ); } ClearList(ordlist); }

22 // scan the array and print its elements
void PrintArray(int a[], int n) { for(int i=0;i < n;i++) cout << a[i] << " "; }

23 /*void main(void) { // initialized array with 10 integer values
int A[10] = {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

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

25 表示链表的三个类的模板定义 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; };

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

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

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

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

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

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

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

33 静态链表结构

34 静态链表定义 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; //当前可分配空间首地址

35 将链表空间初始化 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; //链表收尾 }

36 在静态链表中查找具有给定值的结点 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; }

37 在静态链表的表尾追加一个新结点 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; }

38 在静态链表中查找第 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; }

39 在静态链表第 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; }

40 在静态链表中释放第 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; }

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

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

43 循环链表类的定义 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; //链接指针 }

44 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 );

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

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

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

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

49 例如 n = 8 m = 3

50 约瑟夫问题的解法 #include <iostream.h> #include “CircList.h”
Template<Type> void CircList<Type> :: 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 ( ); //删去 }

51 } 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); //解决约瑟夫问题

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

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

54 多项式(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 &); //加法

55 多项式链表的相加 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 

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

57 friend Polynomial& operator +
( Polynomial& bh ) { //两个带头结点的按升幂排列的多项式相加， //返回结果多项式链表的表头指针，结果不 //另外占用存储, 覆盖ah和bh链表 ListNode<Term> *pa, *pb, *pc, *p; Term a, b; pc = poly.first; //结果存放指针 p = bh.poly.first; pa = poly.first->link; //多项式检测指针 pb = bh.poly.first->link; //多项式检测指针 delete p; //删去bh的表头结点

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

59 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 = pa;

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

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

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

63 双向循环链表类的定义 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=0, DblNode<Type> * left, DblNode<Type> * right ) : data (value), lLink (left), rLink (right) { }

64 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; } //修改左链指针值

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

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

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

68 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; }

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

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

71 双向循环链表的插入算法 (非空表) 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;

72 双向循环链表的插入算法 (空表) 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 )

73 template <class Type> void DblList<Type> ::
Insert ( const Type & value ) { if ( first->rlink == 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;

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

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

76 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; //删去 }

77 其他双向循环链表的公共操作 template <class Type>
int DblList<Type> :: First ( ) { if ( !IsEmpty ( ) ) { current = first->rLink; return 1; } current = first; return 0; }

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

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

80 稀疏矩阵的结点 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]结点

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

82 稀疏矩阵的链表表示的类定义 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; //结点类型

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

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

85 用正交链表表示的稀疏矩阵的建立 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;

86 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; //输入非零元素的三元组

87 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]; //闭合最后一行

88 //闭合各列链表 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; }

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

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