? 单链表
循环链表
多项式及其相加
双向链表
稀疏矩阵单链表 (Singly Linked List)
特点
每个元素 (表项 )由结点 (Node)构成。
线性结构
结点可以不连续存储
表可扩充
data link
a0 a1 a2 a3 a4?first
单链表的存储映像
free (a) 可利用存储空间
a0 a2 a1 a3?
freefirst
(b) 经过一段运行后的单链表结构单链表的类定义
多个类表达一个概念 (单链表 )。
链表结点 (ListNode)类
链表 (List)类
定义方式
复合方式
嵌套方式
继承方式
class List; //链表类定义（复合方式）
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; //表头指针
public:
//链表操作 ………
};
链表类和链表结点类定义 (继承方式 )
class ListNode { //链表结点类
protected:
int data;
ListNode * link;
};
class List,public class ListNode {
//链表类,继承链表结点类的数据和操作
private:
ListNode *first,*current; //表头指针
};
单链表中的插入与删除
插入
第一种情况：在第一个结点前插入
newnode->link = first ;
first = newnode;
（插入前） （插入后）
first
newnode newnode
first
(插入前 ) (插入后 )
第二种情况：在链表中间插入
newnode->link = current->link;
current->link = newnode；
newnode
current
newnode
current
第三种情况：在链表末尾插入
newnode->link = current->link;
current->link = newnode；
(插入前 ) (插入后 )
newnode newnode
current current
int List,,Insert ( int x,int i ) {
//在链表第 i 个结点处插入新元素 x
ListNode * p = current; current = first;
for ( k = 0; k < i -1; k++ ) //找第 i-1个结点
if ( current == NULL ) break;
else current = current->link;
if ( current == NULL && first != NULL ) {
cout <<,无效的插入位置 !\n”;
current = p;
return 0;
}
ListNode *newnode = //创建新结点
new ListNode(x,NULL);
if ( first == NULL || i == 0 ) { //插在表前
newnode->link = first;
first = current = newnode;
}
else { //插在表中或末尾
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 ( int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q; int k = 0;
if ( i == 0 ) //删除表中第 1 个结点
{ q = first; current = first = first->link; }
else {
p = current; current = first;
//找第 i-1个结点
for ( k = 0; k < i-1; k++ )
if ( current == NULL ) break;
else current = current->link;
if ( current == NULL ||
current->link == NULL ) {
cout <<,无效的删除位置 !\n”;
current = p; return 0;
}
else { //删除表中或表尾元素
q = current->link; //重新链接
current = current->link = q->link;
}
Type x = q->data; delete q; //删除 q
return x; //返回第 i 个结点的值
}
带表头结点的单链表
表头结点位于表的最前端，本身不带数据,仅标志表头 。
设置表头结点的目的是 统一空表与非空表的操作,简化链表操作的实现 。
非空表 空表
0ana1first first 0
在带表头结点的单链表第一个结点前插入新结点
newnode->link = p->link; 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;
从带表头结点的单链表中删除第一个结点
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,*current;
//链表的表头指针和当前元素指针
public:
List ( Type& value ) { first = current
= 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 Insert ( Type value );
//将 value插在当前位置后并成为当前元素
Type * Remove ( );
//将链表当前元素删去,填补者为当前元素
ListNode<Type> * Firster ( )
{ current = first; return first; }
//当前指针置于表头,返回表头结点地址
Type * First ( ); //第一个结点为当前结点
Type * Next ( ); //下一个结点为当前结点
int NotNull ( ) { return current != NULL; }
int NextNotNull ( ) { return current != NULL
&& current->link != NULL; }
};
链表结点部分操作的实现
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; //释放它
}
current = 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的结点
current = first->link;
//当前指针 current 指示第一个结点
while ( current != NULL )
if ( current->data == value ) break;
else current = current->link;
return current;
}
template <class Type>
ListNode<Type>* List<Type>,:
Locate ( int i ) {
//定位函数。返回表中第 i 个元素的地址
//若 i < -1或 i 超出，则返回 NULL
if ( i < -1 ) return NULL; // i 值不合理
if ( i ==-1 ) //返回表头结点地址
{ current = first; return first; }
ListNode<Type> * p = first->link;
int k = 0;
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( p != NULL ) current = p;
return p; //返回第 i 个结点地址或 NULL
}
template <class Type>
Type * List<Type>,,GetData ( ) {
//取出链表中当前元素的值
if ( current == NULL ) return NULL; //空表
else return & current->data;
}
template <class Type>
int List<Type>,,Insert ( Type value ) {
//将新元素 value插入在链表中当前结点后
if ( current == NULL ) return 0;
ListNode<Type> *newnode =
GetNode ( value,current->link );
current = current->link = newnode;
return 1; //插入成功，函数返回 1
}
template <class Type>
Type * List<Type>,,Remove ( ) {
//将链表当前元素删去,函数返回该元素
if ( current == first ) return NULL; //空表
ListNode<Type> * p = first;
while ( p->link != current ) p = p->link;
//寻找当前元素的前驱元素结点
p->link = current->link; //摘下被删结点
Type val = current->data;
delete current; current = p->link;
//释放,重置当前元素指针
return &val;
}
template <class Type>
Type * List<Type>,,First ( ) {
//返回表中第一个结点的值的指针,若为空
//表则返回 NULL
if ( first->link != NULL ) {
current = first->link;
return &current->data;
}
else { current = NULL; return NULL; }
}
template <class Type>
Type *List<Type>,,Next ( ) {
//返回表中当前元素的下一个元素的值的
//指针,若无下一元素则返回 NULL
if ( current != NULL &&
current->link != NULL ) {
current = current->link;
return &current->data;
}
else return NULL;
}
【 例 】 单链表 求和函数
int sum ( const List<int> ls ) {
if ( ls.nextNotNull ( ) == NULL )
return 0; //空链表
int retvalue = * ls.First ( );
//取得第一个元素的值
while ( ls.nextNotNull ( ) )
retvalue += * ls.Next ( );
//看有下一个结点存在,累加
return retvalue;
}
静态链表结构循环链表 (Circular List)
循环链表是单链表的变形。
循环链表最后一个结点的 link 指针不为 NULL，而是指向了表的前端。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是,只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
循环链表的示例
带表头结点的循环链表
a0 a1 a2 an-1first
an-1first a1a
0
first
(空表 )
(非空表 )
搜索成功搜索不成功循环链表的搜索算法
first
first
31
31
48
48
15
15
57
57
搜索 15
搜索 25

current current current
current current current currentcurrent
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
分配前的 可利用空间表分配后的 可利用空间表和新结点
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。按升幂排列
class Polynomial {
public,
Polynomial ( ); //构造函数
int operator ! ( ); //判是否零多项式
float Coef ( int e);
int LeadExp ( ); //返回最大指数
Polynomial Add (Polynomial poly);
Polynomial Mult (Polynomial poly);
float Eval ( float x); //求值
}
多项式 (Polynomial)的抽象数据类型多项式的存储表示第一种,private,
(静态数 int degree;
组表示 ) float coef [maxDegree+1];
Pn(x)可以表示为,
pl.degree = n
pl.coef[i] = ci,0? i? n
0 1 2 degree maxDgree
c0 c1 c2 cn…… ……coef
第二种,private:
(动态数 int degree;
组表示 ) float *coef;
构造函数 Polynomial ( int sz ) {
degree = sz;
coef = new float [degree + 1];
}
以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如
P101(x) = 3 + 5x50 - 14x101,不经济。
在多项式的链表表示中每个结点三个数据成员：
优点是：
多项式的项数可以动态地增长，
不存在存储溢出问题。
插入、删除方便，不移动元素。
第三种,多项式的链表表示
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
head row col
a[i][j]
False i j
(c) 建立 a[i][j]结点稀疏矩阵的正交链表表示的示例