福州大学：数据结构：数据结构03

? 单链表
? 循环链表
? 多项式及其相加
? 双向链表
? 稀疏矩阵
单链表 (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]结点
稀疏矩阵的正交链表表示的示例