清华大学：C++数据结构（殷人昆）：ds03

? 单链表
循环链表
多项式及其相加
双向链表
稀疏矩阵单链表 (Singly Linked List)
特点
每个元素 (表项 )由结点 (Node)构成。
线性结构
结点可以连续，可以不连续存储
结点的逻辑顺序与物理顺序可以不一致
表可扩充
data link
a0 a1 a2 a3 a4?first
单链表的存储映像
free (a) 可利用存储空间
a0 a2 a1 a3?
freefirst
(b) 经过一段运行后的单链表结构单链表的类定义
多个类表达一个概念 (单链表 )。
链表结点 (ListNode)类
链表 (List)类
链表游标 (Iterator)类
定义方式
复合方式
嵌套方式
继承方式
class List; //链表类定义（复合方式）
class ListNode { //链表结点类
friend class List; //链表类为其友元类
private:
int data; //结点数据,整型
ListNode * link; //结点指针
};
class List { //链表类
private:
ListNode *first,*last; //表头指针
};
class List { //链表类定义 (嵌套方式 )
private:
class ListNode { //嵌套链表结点类
public:
int data;
ListNode *link;
};
ListNode *first,*last; //表头指针
public:
//链表操作 ………
};
链表类和链表结点类定义 (继承方式 )
class ListNode { //链表结点类
protected:
int data;
ListNode * link;
};
class List,public class ListNode {
//链表类,继承链表结点类的数据和操作
private:
ListNode *first,*last; //表头指针
};
单链表中的插入与删除
插入
第一种情况：在第一个结点前插入
newnode->link = first ;
first = newnode;
（ 插入前 ） （ 插入后 ）
first
newnode newnode
first
(插入前 ) (插入后 )
第二种情况：在链表中间插入
newnode->link = p->link;
p->link = newnode；
newnode
p
newnode
p
第三种情况：在链表末尾插入
newnode->link = p->link;
p->link = newnode；
(插入前 ) (插入后 )
newnode newnode
p p
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);
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;
}
删除
第一种情况,删除表中第一个元素
第二种情况,删除表中或表尾元素在单链表中删除含 ai的结点


ai-1
ai-1
ai
ai
ai+1
ai+1
p q
删除前删除后
int List,,Remove ( int i ) {
//在链表中删除第 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;
}
else { //删除表中或表尾元素
q = p->link; //重新链接
p->link = q->link;
}
if ( q == last ) last = p; //可能修改 last
Type x = q->data;
delete q; //删除 q
return x; //返回第 i 个结点的值
}
带表头结点的单链表
表头结点位于表的最前端，本身不带数据,仅标志表头 。
设置表头结点的目的是 统一空表与非空表的操作,简化链表操作的实现 。
非空表 空表
0ana1first first 0
在带表头结点的单链表第一个结点前插入新结点
newnode->link = p->link;
if ( p->link == NULL ) last = newnode;
p->link = newnode;
first
newnode
first
newnode
插入
first
newnode
0 first
newnode 0
插入
p p
p p
q = p->link;
p->link = q->link;
delete q;
if ( p->link == NULL )
last = p;
从带表头结点的单链表中删除第一个结点
first
first
(非空表）
first
0first
(空表）
0
p q
p q
单链表的模板类
类模板将类的数据成员和成员函数设计得更完整、更灵活。
类模板更易于复用。
在单链表的类模板定义中，增加了表头结点 。
用模板定义的单链表类
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) { }
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指针
void setData ( Type value ) { data = value; }
//修改结点的 data值
};
template <class Type> class List { //链表类
private:
ListNode<Type> *first,*last;
//链表的表头指针和表尾指针
public:
List ( Type& value ) { last = first
= new ListNode<Type> ( value ); }
~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 个元素后
Type * Remove ( int i );
//将链表中第 i 个元素删去
};
链表结点部分操作的实现
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;
}
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; //修改表尾指针
}
链表类部分操作的实现
first
q
first
first
q
q
first
a0 a1
a1
a2
a2
a2
current
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;
}
first
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 <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 在搜索不成功时返回空值
}
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
}
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;
}
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
}
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;
}
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
newnode
first
newnode
0
0
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;
}
}
后插法建立单链表
每次将新结点加在插到链表的表尾；
设置一个尾指针 r，总是指向表中最后一个结点，新结点插在它的后面；
尾指针 r 初始时置为指向表头结点地址。
0
0newnode
first
newnode
0
0
r
r
r
r
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; //插入到表末端
cin >> ch;
}
r ->link = NULL; last = r; //表收尾
}
链表的游标类 (Iterator)
游标类主要用于单链表的搜索。
游标类的定义原则：
Iterator类是 List类和 ListNode类的友元类。
Iterator对象引用已有的 List类对象。
Iterator类有一数据成员 current，记录对单链表最近处理到哪一个结点。
Iterator类提供若干测试和搜索操作表示链表的三个类的模板定义
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;
};
template <class Type> class List { //链表类
public:
………
private:
ListNode<Type> *first,*last;
};
template <class Type> class ListIterator {
private:
const List<Type> & list; //引用已有链表
ListNode<Type> *current; //当前结点指针
public:
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 ( );
//返回链表当前结点的下一个结点的地址
}
链表的游标类成员函数的实现
template <class Type>
Boolean ListIterator<Type>,,NotNull ( ) {
//检查链表中当前元素是否非空
if ( current != NULL ) return True;
else return False;
}
current current
情况 1 返回 True 情况 2 返回 False
template <class Type>
Boolean ListIterator<Type>,,NextNotNull ( ) {
//检查链表中下一元素是否非空
if ( current != NULL &&
current->link != NULL ) return True;
else return False;
}
current current
情况 1 返回 True 情况 2 返回 False
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
约定链表中没有表头结点
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
利用游标类 (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;
}
静态链表结构静态链表定义
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; //当前可分配空间首地址
}
将链表空间初始化
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; //链表收尾
}
在静态链表中查找具有给定值的结点
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;
}
在静态链表的表尾追加一个新结点
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;
}
在静态链表中查找 第 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;
}
在静态链表 第 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;
}
在静态链表中释放 第 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;
}
循环链表 (Circular List)
循环链表是单链表的变形。
循环链表的最后一个结点的 link 指针不为
NULL，而是指向了表的前端。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是,只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
循环链表的示例
带表头结点的循环链表
a0 a1 a2 an-1first
an-1first a1a
0
first
(空表 )
(非空表 )
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; //链接指针
}
循环链表类的定义
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 );
Type getData ( ) const;
void Firster ( ) { current = first; }
Boolean First ( );
Boolean Next ( );
Boolean Prior ( );
void Insert ( const Type & value );
void Remove ( );
};
搜索成功搜索不成功循环链表的搜索算法
first
first
31
31
48
48
15
15
57
57
搜索 15
搜索 25

current current current
current current current currentcurrent
循环链表的搜索算法
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;
}
if ( first != NULL ) {
CircListNode<Type> *second = first->link;
first->link = av; av = second;
first = NULL;
}
利用可利用空间表回收循环链表
first av
first av
回收前回收后
if ( av == NULL )
newnode = new CircListNode<Type>;
else { newnode = av; av = av->link; }
从可利用空间表分配结点
av
newnode
av
分配前的 可利用空间表分配后的 可利用空间表和新结点用循环链表求解约瑟夫问题
约瑟夫问题的提法
n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数,
报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，
报到第 m 个人，再令其出列,…,
如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 8 m = 3
约瑟夫问题的解法
#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 ( ); //删去
}
}
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);
//解决约瑟夫问题
}
i
n
0i
i
n
n
2
210n
xc
xc xcxcc( x )P

多项式 (Polynomial)
n 阶多项式 Pn(x) 有 n+1 项 。
系数 c0,c1,c2,…,cn
指数 0,1,2,…,n。按升幂排列
在多项式的链表表示中每个结点三个数据成员：
优点是：
多项式的项数可以动态地增长，不存在存储溢出问题。
插入、删除方便，不移动元素。
多项式的链表表示
coef exp linkData? Term
多项式 (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 &); //加法
};
多项式链表的相加
AH = 1 - 3x6 + 7x12
BH = - 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，则将结果加到结果多项式。
若当前被检测项 指数不等,将指数小者加到结果多项式。
若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
AH.first
BH.first
CH.first
1 0
1 0
-1 4
-1 4
-3 6
3 6 -9 10
7 12
7 12
8 14
8 14
pa
p
pc
-9 10
pb
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
-3 6
3 6 -9 10
7 12
7 12
8 14
8 14
pa
pb
pc
-9 10
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
-3 6
3 6 -9 10
7 12
7 12
8 14
8 14
pa
pb
pc
-9 10
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
-3 6
3 6 -9 10
7 12
7 12
8 14
8 14
pa
p
pc
-9 10
pb
0
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
0 6
-9 10
7 12
7 12
8 14
8 14
pa
ppc
-9 10
pb
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
-9 10
7 12
7 12
8 14
8 14
pa
pc
-9 10
pb
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
-9 10
7 12
7 12
8 14
8 14
pa
pc
-9 10
pb
AH.first?
CH.first
1 0
1 0
-1 4
-1 4
-9 10
7 12
7 12
8 14
8 14
pa == pc
-9 10
pb
AH.first
CH.first
1 0
1 0
-1 4
-1 4
-9 10
7 12
7 12
8 14
8 14
pa == pc
-9 10
pb
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的表头结点
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 ) < 0.0001) {
p = pa; pa = pa->link; delete p;
} //相加为零,该项不要
else { //相加不为零,加入 ch链
pa->data = a; pc->link = pa;
pc = pa; pa = pa->link;
}
break;
case '>',//pa->exp > pb->exp
pc->link = pb; pc = pb;
pb = pb->link;
break;
case '<',//pa->exp < pb->exp
pc->link;
pc = pa; pa = pa->link;
}
}
if ( pa->link ) 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->rLinkp
lLinkrLink
first first
双向循环链表类的定义
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) { }
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; } //修改左链指针值
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; }
int Find ( const Type& target );
void Firster ( ) { current = first; }
//当前指针置于表头结点 。
int First ( ) ; //当前指针置于第一个结点
int Next ( ); //当前指针置于后继结点
int Prior ( ); //当前指针置于前驱结点
void Insert ( const Type& value );
//插入一个包含有值 value的新结点
void Remove ( );
//删除当前结点
};
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;
//表头结点的链指针指向自己
}
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;
}
搜索成功搜索不成功双向循环链表的搜索算法
first
first
31
31
48
48
15
15
57
57
搜索 15
搜索 25
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;
}
双向循环链表的插入算法 (非空表 )
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
后插入 25current 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 <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;
}
删除 48
双向循环链表的删除算法
first
first
非空表31 48 15
current
31 15
current
current->rLink->lLink = current->lLink;
current->lLink->rLink = current->rLink;
删除 31
双向循环链表的删除算法
first first31
current current
current->rLink->lLink = current->lLink;
current->lLink->rLink = current->rLink;
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; //删去
}
}
其他双向循环链表的公共操作
template <class Type>
DblList<Type>,,DblLIst ( Type uniqueVal ) {
//双向循环链表的构造函数,创建表头结点
first = new DblNode<Type> ( uniqueVal );
first→rLink = first→lLink = first ;
}
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;
}
template <class Type>
int DblList<Type>,,First ( ) {
if ( !IsEmpty ( ) )
{ current = first->rLink; return 1; }
current = first; return 0;
}
template <class Type>
int DblList<Type>,,Next ( ) {
if ( current->rLink == first ) //最后结点
{ current = first ->rLink; return 0; }
current = current->rLink; return 1;
}
template <class Type>
int DblList<Type>,,Prior ( ) {
if ( current->lLink == first ) //第一个结点
{ current = first ->lLink; return 0; }
current = current->lLink; return 1;
}
稀疏矩阵
在矩阵操作 (+,-,*,/)时矩阵非零元素会发生动态变化，用 稀疏矩阵的链接表示 可适应这种情况。
稀疏矩阵的链接表示采用正交链表：
行链表 与 列链表 十字交叉。
行链表与列链表都是 带表头结点的循环链表 。用表头结点表征是第几行，
第几列。
稀疏矩阵的结点
head
down
next
right
(a) 表头结点 (b) 非零元素结点
rightvaluedown
row col
a[i][j]
False i j
(c) 建立 a[i][j]结点
head
稀疏矩阵的正交链表表示的示例稀疏矩阵的链表表示的类定义
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; //结点类型
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& operator >> ( istream &,
Matrix & ); //矩阵输入
public:
~Matrix ( ); //析构函数
private:
MatrixNode *headnode; //稀疏矩阵的表头
};
用正交链表表示的稀疏矩阵的建立
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;
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;
//输入非零元素的三元组
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]; //闭合最后一行
//闭合各列链表
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;
}
稀疏矩阵的删除
为执行稀疏矩阵的删除，需要使用可利用空间表来管理回收的空间。
可利用空间表是单链表结构，只允许在表头插入或删除，其表头指针为 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;
}