1
2
第二章 线性表
? 线性表的逻辑结构
? 线性表的顺序存贮结构
? 线性表的链式存储 ----线性链表
? 几种特殊线性链表
? 线性表应用示例
3
§ 2.1 线性表的逻辑结构
? 线性表（ Linear list）,
是数据元素的一个有限序列，在这个序列中,每个元素有
一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元
素可以无前趋，而最后一个元素也可以无后继
? 可记为
L = (a1,a2,…, an)；
ai为数据元素,ai-1称为 ai的 前趋 （ i≥ 1）,ai+1称为 ai 的 后继 （ i≤ n），
i=1,2,…,n.
§ 2.1.1 基本概念
4
§ 2.1.1 基本概念
? 线性表中元素的个数称线性表的 长度, n=0时
称为 空表, 空表长度为 0。
? 按形式化方法，线性表定义为
LL=（ D,S）
D={a1,a2,…,an}
S={r}
r= { <ai-1,ai>｜ ai∈ D,i=2,…,n}。
5
§ 2.1.2 基本操作
? Init(L),初始化操作, 设定一个空的线性表 L,执行该操作后, 线
性表 L就可用于其它操作 。
? Len(L),求长度函数 。 函数值为线性表中元素的个数 。
? Get(L,i),取元素函数 。 函数值为 L中的序号为 i的元素 （ 值或地
址 ） 。
? Set(L,i,x),置值函数 。 将 L中的序号为 i的元素的值置为 x.
? Prior(L,x),求前趋函数 。 函数值为 L中的 x的前趋 。
? Next(L,x),求后继函数 。 函数值为 L中的 x的后继 。
? Locate(L,x),查找函数 。 函数值为 L中的元素 x的序号, 若 x不在 L
中, 则返回特殊标志 。
6
§ 2.1.2 基本操作
? Insert (L,i,x),插入操作 。 将元素 x插入到 L中的第 i个元素之前,
使原第 i个元素及其后的各元素的序号分别增 1。
? Deletel (L,i),删除操作 。 将 L中的第 i个元素删除掉, 使 L 中的元
素个数减 1,原第 i个元素之后的元素的序号分别减 1。
? Empty (L),判定函数 。 若 L为空表, 函数值为, 真,, 否则为
,假, 。
? Clear (L),置空操作 。 使 L成为空表 。
7
§ 2.1.2 基本操作
? Copy (L1,L2),复制操作 。 生成一个名为 L2的与 L1完全相同的线
性表 。
? Sort ( L,key,type),排序操作 。 按线性表中元素的关键字 key的递
增或递减 （ 由 type确定 ） 次序重新排列 L中的元素次序 。
? Merge ( L1,L2,L3 ),合并操作 。 使 L3取 L1和 L2首尾相连的结果
? Split ( L,i,L1,L2),分拆操作 。 使 L1为 L中的前 i个元素 （ 含第 i个 ）
构成的线性表, L2为剩余部分构成的线性表 。
8
§ 2,1.3 异常处理
? 异常 (Exception)：
是指程序运行中，由于运行环境、数据
输入或操作不当而导致程序不能物理地运行的
错误
? 不能通过静程序发现异常（只能估计它的可能
性），而只能通过程序的运行发现
9
§ 1.2.3 异常处理
? 在 C++中，为程序员提供了良好的处理异常的
机制
– try----检测 /捕获异常；
– catch----处理 try所捕获的异常；
– throw----生成一个异常, 交由 try捕获；
10
§ 2.1.3 异常处理
? 首先，设立一个表，存储异常代码和用于说明异常的文字信息
struct TErrMessageRec
{
int no;
char msg [CNST_SizeErrMessage ];
};
class TErrMessageList
{
TErrMessageRec msgList [CNST_MaxNumErrMessage ];
public:
int len;
TErrMessageList()
{
int i = 0;
11
§ 2.1.3 异常处理
/* 0*/ msgList[i].no=i; strcpy(msgList[i].msg,"Unkonwn error"); i++;
/* 1*/ msgList[i].no=i; strcpy(msgList[i].msg,"The parameters Out of range"); i++;
/* 2*/ msgList[i].no=i; strcpy(msgList[i].msg,"The parameters illegal"); i++;
/* 3*/ msgList[i].no=i; strcpy(msgList[i].msg,"The memory space low"); i++;
/* 4*/ msgList[i].no=i; strcpy(msgList[i].msg,"Not found"); i++;
len = i;
};
char *GetMessage(int no)
{
if (no<0 || no >= CNST_MaxNumErrMessage)
return NULL;
return msgList [no].msg;
};
};
全局的出错代码表 errMessageList
extern TErrMessageList errMessageList;
12
§ 2.1.3 异常处理
? 定义一个可用的异常处理类 TExcepComm
class TExcepComm
{
public:
int errNo;
char errMessage[CNST_SizeErrMessage];
TExcepComm (int mErrNo)
{
errNo = mErrNo;
strcpy (errMessage,errMessageList.GetMessage(errNo));
}
};
13
§ 2.1.4 下标选择器
? TIndexSelector是一个字符串形式的下标选择器
IndexSelector,:=IndexScope|(IndexScope "," IndexSelector)
IndexScope,:= INTEGER |( INTEGER? "_" INTEGER?)
INTEGER,:=("-"| "+")? DIGITS
DIGITS,:=DIGIT |( DIGIT DIGITS)
DIGIT,:= 0|1|2|3|4|5|6|7|8|9
14
§ 2.1.4 下标选择器
? 合法的下标选择器
5
1_
_8
_
1,2
1,2_3,-1_-3
3_4,2,7_8,10_
15
§ 2.1.4 下标选择器
? TIndexSelector类的定义
struct TSelectorItem
{
long lower;
long upper;
};
class TIndexSelector
{
TSelectorItem room[CNST_SizeIndexSelector];
int lastVisitedItem;
int LoadFromArray (TSelectorItem *se,int n,long maxIdx);
long Standardize(void);
16
§ 2.1.4 下标选择器
public:
int len;
long maxIndex;
TIndexSelector (char *) {len=0;};
TIndexSelector (TSelectorItem *se,int n,long maxIdx);
int GetFirst(long &lw,long &up);
int GetNext(long &lw,long &up);
long GetEachIndex(long *idxs);
int Get(int idx,long &lw,long &up);
int Set(int idx,long lw,long up);
long GetIndexNum(void);
17
§ 2.1.4 下标选择器
int ResetByFromArray(TSelectorItem *se,int n,long maxIdx);
/*
long GetLower(int idx);
long GetUpper(int idx);
int SetLower(int idx,lw);
int SetUpper(int idx,up);
int Insert(int idx,long lw,long up);
int InsertLower(int idx,long lw);
int InsertUpper(int idx,long up);
int Delete(int idx);
*/
};
18
§ 2.1.5 线性表抽象类
? 线性表抽象类的定义
class TExcepLinearList
{
public:
int errNo;
char errMessage[CNST_SizeErrMessage];
TExcepLinearList(int mErrNo)
{
errNo=mErrNo;
strcpy(errMessage,errMessageList.GetMessage(errNo));
}
};
专用于线性表类的异
常处理类
19
§ 2.1.5 线性表抽象类
? 当检测到异常时, 使用 throw 抛 掷 一 个
TExceptionLinearlist对象, 产生一个该类型的
异常, 形式为：
throw TExceptionLinearlist（ no） ;
20
§ 2.1.5 线性表抽象类
template <class TElem>
class TLinearList0
{
protected:
public:
long len;
virtual TBool IsEmpty ()
{if (len <=0) return True; else return False;}
virtual TElem &Get (long idx) = 0;
virtual TElem *Set (long idx,TElem &elem) = 0;
virtual TElem *Prior (long idx) = 0;
virtual TElem *Next (long idx) = 0;
virtual TElem *GetAddress (long idx)=0;
线性表抽象类
21
§ 2.1.5 线性表抽象类
virtual long CountElem (TElem &elem)=0;
virtual long Locate (TElem &elem,long sn=1) = 0;
virtual long Locate (TElem &elem,long *foundElem) = 0;
virtual long LocateFirst (TElem &elem) = 0;
virtual long LocateNext (TElem &elem) = 0;
virtual TElem *Insert (TElem &elem,long sn=1) = 0;
virtual TElem *Delete (long sn=1)=0;
virtual long Delete (TIndexSelector &sel,TElem *elemDeleted = NULL) = 0;
virtual long DeleteByIndex (long *idxTobeDel,
long numIdx,TElem *elemDeleted=NULL)=0;
};
22
§ 2.2 线性表的顺序存贮结构
? 线性表的顺序存贮
将表中各元素依它们的逻辑次序存贮在一片连续
的存贮区域中，使任意两相邻元素之间的存贮单元个
数相等
? 设线性表为 L=(a1,a2,…,a n)，每个元素占 2个存贮单元，
§ 2.2.1 基本存储方法
a1 a2 a3 … …
图 2.1 线性表的顺序存储
有下列关系成立 Loc ( ai ) =Loc(a1) + ( i -1) * c
23
§ 2.2.2 面向对象描述
? (一 ) 对象结构
? 线性表的顺序存贮结构的存储区域，可用高级
语言中的数组模拟
? 从面向对象观点看，顺序存储的线性表，是一
个对象，其主要数据成员是一维数组
? 一维数组采用动态空间表示
24
§ 2.2.2 面向对象描述
? (一 ) 对象结构
template <class TElem>
class TLinearListSqu, public TLinearList0<TElem>
{
protected:
TElem *room;
long size;
long lastVisited;
TElem buffElem;
long ResizeRoom (long newSize);
long CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2);
25
§ 2.2.2 面向对象描述
? (一 ) 对象结构
public:
TLinearListSqu (void);
TLinearListSqu (long mSize);
~TLinearListSqu (void);
virtual TElem &Get (long idx);
virtual TElem *GetAddress (long idx);
virtual TElem *Set (long idx,TElem &elem);
virtual TElem *Prior (long idx);
virtual TElem *Next (long idx);
virtual long CountElem (TElem &elem);
26
§ 2.2.2 面向对象描述
? (一 ) 对象结构
virtual long Locate (TElem &elem,long sn=1);
virtual long Locate (TElem &elem,long *foundElemIndex);
virtual long LocateFirst (TElem&elem);
virtual long LocateNext (TElem &elem);
virtual TElem *Insert (TElem &elem,long sn=1);
virtual TElem *Delete (long sn=1);
virtual long Delete (TIndexSelector &sel,TElem *elemDeleted=NULL);
virtual long DeleteByIndex (long *idxTobeDel,long numIdx,
TElem *elemDeleted=NULL);
void Print (); //Only for test
};
27
§ 2.2.2 面向对象描述
? (二 )初始化
template <class TElem>
TLinearListSqu< TElem>::TLinearListSqu ( )
{
size = 0;
len = 0;
room = NULL;
}
28
§ 2.2.2 面向对象描述
? (二 )初始化
template <class TElem>
TLinearListSqu< TElem>::TLinearListSqu (long mSize)
{
size=0;
room=NULL;
len=0;
if (mSize<1) throw TExcepLinearList(2);
room = new TElem[mSize];
if (room==NULL) throw TExcepLinearList(3);
size = mSize;
}
29
template <class TElem>
TLinearListSqu< TElem>::~TLinearListSqu(void)
{
if (room != NULL)
delete [] room;
}
§ 2.2.2 面向对象描述
30
§ 2.2.2 面向对象描述
? (三 )元素直接访问
? Get和 Set类函数用于实现按序号（逻辑关系）
访问元素
template <class TElem>
TElem &TLinearListSqu< TElem>::Get (long idx)
{
if (idx<0 || idx>=len)
throw TExcepLinearList(1);
return room[idx];
}
31
§ 2.2.2 面向对象描述
template <class TElem>
TElem *TLinearListSqu< TElem>::GetAddress
(long idx)
{
if (idx<0 || idx>=len)
throw TExcepLinearList(1);
return &room[idx];
}
32
§ 2.2.2 面向对象描述
template <class TElem>
TElem *TLinearListSqu< TElem>::Set (long idx,
TElem &elem)
{
if (idx<0 || idx>=len)
throw TExcepLinearList(1);
room[idx] = elem;
return &room[idx];
}
33
§ 2.2.2 面向对象描述
? (四 )前驱 /后继操作
template <class TElem>
TElem *TLinearListSqu< TElem>::Prior (long idx)
{
if (idx-1<0 || idx-1>=len)
throw TExcepLinearList(1);
return &room[idx-1];
}
34
§ 2.2.2 面向对象描述
? (四 )前驱 /后继操作
template <class TElem>
TElem *TLinearListSqu< TElem>::Next (long idx)
{
if (idx+1<0 || idx+1>=len)
throw TExcepLinearList(1);
return &room[idx+1];
}
35
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (1)
template <class TElem>
long TLinearListSqu< TElem>::Locate (TElem &elem,long sn)
{
long i,k;
k=0;
if (sn>0)
{ for (i=0; i<len; i++)
if (room[i]==elem)
{
k++;
if (k==sn) return i;
}
}
查找值等于 elem的第 sn个元
素，存在时返回其在表中的
序号。由于 sn可能是负值
（表示倒数第 sn个，设最后
一个的 sn为 -1）
36
§ 2.2.2 面向对象描述
? (五 )查找定位操作
else
for (i=len-1; i>=0; i--)
if (room[i]==elem)
{
k++;
if (k==-sn) return i;
}
if (k>0) return i; //"sn" is larger the number of matched element.
//The last is found and its index is returned
else return -1; //Not found
}
37
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (2)
template <class TElem>
long TLinearListSqu< TElem>:,Locate (TElem &elem,long
*foundElemIndex)
{
long i,k;
k=0;
for (i=0; i<len; i++)
if (room[i]==elem) //Assume the TElem support the operator "=="
{
foundElemIndex[k]= i;
k++;
}
return k;
}
求出值为 elem的所有元素的序
号，并存入 foundElemIndex所
指出的一维数组中
38
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (3)
template <class TElem>
long TLinearListSqu< TElem>::LocateFirst (TElem &elem)
{
long i;
for (i=0; i<len; i++)
if (room[i]==elem)
{
lastVisited=i;
return i;
}
return -1; //Not found
}
与 LocateNext配合使用，用于
逐个访问值为 elem的各元素；
查找值为 elem的第一个出现的
元素的序号
39
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (3续 )
template <class TElem>
long TLinearListSqu< TElem>::LocateNext (TElem &elem)
{
long i;
for (i=lastVisited+1; i<len; i++)
if (room[i]==elem)
{
lastVisited=i;
return i;
}
return -1; //Not found
}
查找值为 elem的下一个
出现的元素
记下最近一次调用
LocateFirst/LocateNext所找
到的元素的序号
40
§ 2.2.2 面向对象描述
? (六 )插入操作
template <class TElem>
TElem *TLinearListSqu< TElem>::Insert (TElem &elem,
long sn)
{
long i,k;
int ret=0;
if (sn<0) k=len+sn;
else k=sn-1;
if ( k>len) k=len;
else if (k<0) k=0;
在表中第 sn个元素的前面插
入指定的元素 elem
41
§ 2.2.2 面向对象描述
? (六 )插入操作
if (len>=size)
{
ret=ResizeRoom(size+10);
if (ret<0) throw TExcepLinearList(3);
}
for (i=len-1; i>=k; i--)
room[i+1] = room[i];
room[k]=elem;
len++;
return &room[k];
}
42
§ 2.2.2 面向对象描述
? (六 )插入操作
? 基本插入操作的时间复杂度
– 算法中耗时最大的执行是元素移动的语句
for (i=len-1; i>=k; i--) room[i+1] = room[i];
– 移动元素的次数应为概率平均（数学期望）
f(n) =
ci与算法有关，在这里 ci = (n – i )
假定插入位置是等概率的，则 pi=1/(n+1)，则
f(n) = = =
= =
=O(n)
i
n
i
icp?
?0
i
n
i
icp?
?
?
1
0
??
? ?
1
0 1
n
i
inc ??
?
?? 1
0
)(11 n
i
inn
2
)1(
1
1 ?
?
nn
n 2
n
43
§ 2.2.2 面向对象描述
? (六 )删除操作 (1)
template <class TElem>
TElem *TLinearListSqu< TElem>::Delete (long sn)
{
long i,k;
if (sn<0) k=len+sn;
else k=sn-1;
if (k<0 || k>=len)
throw TExcepLinearList(2);
删除表中第 sn个元素 (sn的含
义同 Locate)，并将其值的地
址返回
44
§ 2.2.2 面向对象描述
? (六 )删除操作
buffElem=room[k];
for (i=k; i<len; i++)
room[i] = room[i+1];
len--;
if (2*len < size)
ResizeRoom(len+long(len/2.0));
return &buffElem;
}
时间复杂度 O(n)
45
§ 2.2.2 面向对象描述
? (六 )删除操作 (2)
template <class TElem>
long TLinearListSqu< TElem>::Delete (TIndexSelector &sel,TElem
*elemDeleted)
{
long i;
long *indexDeleted;
i = sel.GetIndexNum();
indexDeleted = new long[i];
if (indexDeleted==NULL) throw TExcepLinearList(4);
i=sel.GetEachIndex(indexDeleted);
i=DeleteByIndex(indexDeleted,i,elemDeleted);
delete[] indexDeleted;
return i;
}
删除下标选择器 sel所指出的
各元素
时间复杂度 O(n)
46
§ 2.2.2 面向对象描述
? (六 )删除操作 (3)
? 根据下标列举 idxTobeDel进行删除
序号,0 1 2 3 4 5 6 7 8 9, 10 11 12
元素,x x * * x * x x * * x * *
图 - 删除带标记的元素
k=2 k=3
47
§ 2.2.2 面向对象描述
? (六 )删除操作 (3)
template <class TElem>
longTLinearListSqu< TElem>::DeleteByIndex
(long *idxTobeDel,long numIdx,TElem *elemDeleted)
{
long i,k;
k=0;
for (i=0; i<len; i++)
{
if (i==idxTobeDel[k])
{
if (elemDeleted!=NULL)
elemDeleted[k]= room[i];
k++;
}
else room[i-k] =room[i];
}
时间复杂度 O(n)
48
§ 2.2.2 面向对象描述
? (六 )删除操作 (3)
len = len - k;
if (2*len < size)
ResizeRoom(len+long(len/2.0));
return k;
}
49
§ 2.3 线性表的链式存储 ----线性链表
? 连续存贮结构 的讨论
– 优点是存贮利用率高，访问元素的速度快
– 几方面的缺点
? 当进行插入与删除时，需移动元素
? 存贮要求较高，不能利用小块存贮区
? 如果对线性表经常要进行插入删除并需动态扩
充容量，则需采用 链式存贮结构
50
§ 2.3.1 链式存贮方法
? 线性表采用链式存贮结构时称为 线性链表
? 单链表,以后继或前驱地址为链的存储方法
? 具体的存贮映射方法,
– 1、对线性表中每个元素 ai，为它分配一块存贮区
– 2、每个元素的存贮区分为两大部分
– 3．为了能方便地访问链表，设置链表头结点
内容 前驱 /后继地址
51
§ 2.3.1 链式存贮方法
图 - 单链表基本形式
a2 an ^head
len
a1
表头
TLinearLis
tLink
链结点
TLinkNode
52
§ 2.3.2 线性链表的面向对象描述
template <class TElem>
struct TLinkNode
{
TElem info;
TLinkNode *next; //Note,not necessary for
<TElem> to follow TLinkNode here
};
53
§ 2.3.2 线性链表的面向对象描述
template <class TElem>
class TLinearListLink, public TLinearList0<TElem>
{
protected:
TLinkNode<TElem> *head;
TLinkNode<TElem> *lastVisited;
long lastVisitedIndex;
TElem buffElem;
void ReleaseAll();
54
§ 2.3.2 线性链表的面向对象描述
public:
TLinearListLink(void);
~TLinearListLink(void);
virtual TElem &Get(long idx);
virtual TElem *GetAddress(long idx);
virtual TElem *Set(long idx,TElem &elem);
virtual long CountElem(TElem &elem);
virtual TElem *Prior(long idx);
virtual TElem *Next(long idx)
55
§ 2.3.2 线性链表的面向对象描述
virtual long Locate(TElem&elem,long sn=1);
virtual long Locate(TElem&elem,long *foundElemIndex=NULL);
virtual long LocateFirst(TElem&elem);
virtual long LocateNext(TElem&elem);
virtual TElem *Insert(TElem &elem,long sn=1);
virtual TElem *Delete(longsn=1);
virtual long Delete(TIndexSelector &sel,TElem *elemDeleted=NULL);
virtual long DeleteByIndex(long*idxTobeDel,long numIdx,
TElem *elemDeleted=NULL);
void Print(); //Only for test
56
§ 2.3.2 线性链表的面向对象描述
//New functions
virtual TElem &Get(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *GetNode(longidx);
virtual long GetNodeIndex(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *SetNode(TLinkNode<TElem> *pNode,
TElem &elem,TLinkNode<TElem> *pNodeNext);
virtual TLinkNode<TElem> *SetNodeElem(TLinkNode<TElem> *pNode,
TElem &elem);
virtual TLinkNode<TElem> *SetNodeNext(TLinkNode<TElem> *pNode,
TLinkNode<TElem> *pNodeNext);
57
§ 2.3.2 线性链表的面向对象描述
virtual TLinkNode<TElem> *PriorNode(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *NextNode(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *PriorNode(longidx);
virtual TLinkNode<TElem> *NextNode(longidx);
virtual TLinkNode<TElem> *LocateNode(TElem&elem,long sn=1);
virtual long LocateNode(TElem &elem,TLinkNode<TElem>
*foundElemPointer[]);
58
§ 2.3.2 线性链表的面向对象描述
virtual TLinkNode<TElem> *LocateNodeFirst(TElem&elem);
virtual TLinkNode<TElem> *LocateNodeNext(TElem&elem);
virtual TLinkNode<TElem> *InsertAfter (TLinkNode<TElem>
*pNodeTobeInserted,TLinkNode<TElem> *pNodeBase);
virtual TLinkNode<TElem> *Insert(TLinkNode<TElem> *pNodeTobeInserted,
TLinkNode<TElem> *pNodeBase);
virtual TLinkNode<TElem> *DeleteAfter(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *Delete(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *Insert(TLinkNode<TElem> *pNode,long sn=1);
};
59
§ 2.3.3 线性链表的面向对象实现
? (一 )初始化
template <class TElem>
TLinearListLink< TElem>::TLinearListLink()
{
head=NULL;
len=0;
lastVisitedIndex=0;
lastVisited=NULL;
}
60
§ 2.3.3 线性链表的面向对象实现
? (一 )初始化
template <class TElem>
void TLinearListLink< TElem>::ReleaseAll()
{
if (head==NULL) return;
TLinkNode<TElem> *p,*q;
p=head;
while (p!=NULL)
{
q=p;
p=p->next;
delete q;
}
}
61
§ 2.3.3 线性链表的面向对象实现
? (二 )指针类 Get类操作 (1)
template <class TElem>
TElem &TLinearListLink< TElem>::Get(TLinkNode<TElem>
*pNode)
{
if ( pNode==NULL) TExcepLinearList(4);
return pNode->info;
}
? 该函数返回指定结点中的元素内容
62
§ 2.3.3 线性链表的面向对象实现 ? (二 )指针类 Get类操作 (2)
template <class TElem>
long TLinearListLink< TElem>::GetNodeIndex(TLinkNode<TElem>
*pNode)
{
if ( pNode==NULL) TExcepLinearList(4);
TLinkNode<TElem> *p;
long i;
i=0;
p=head;
while (p!=NULL)
{
if (p==pNode) break;
i++;
p=p->next;
}
if ( p==NULL) TExcepLinearList(4);
return i;
}
返回指定结点在表中的序
号
63
§ 2.3.3 线性链表的面向对象实现
? (二 )指针类 Get类操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::GetNode(long idx)
{
TLinkNode<TElem> *p;
long i;
if (idx<0 || idx>=len)
throw TExcepLinearList(2);
if (lastVisited!=NULL && idx >= lastVisitedIndex)
{ p=lastVisited;
i=lastVisitedIndex;
}
函数通过序号求指针，它
返回指定序号 idx所对应的
结点的指针
64
§ 2.3.3 线性链表的面向对象实现 ? (二 )指针类 Get类操作 (3)
else
{
p=head;
i=0;
}
while (p!=NULL)
{
if (i==idx) break;
i++;
p=p->next;
}
if ( p==NULL) TExcepLinearList(0);
lastVisitedIndex=i;
lastVisited=p;
return p;
}
65
§ 2.3.3 线性链表的面向对象实现
? (三 )指针类 Set类操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::SetNode(
TLinkNode<TElem> *pNode,TElem &elem,
TLinkNode<TElem> *pNodeNext)
{
if (pNode==NULL) throw TExcepLinearList(4);
pNode->info = elem;
pNode->next = pNodeNext;
return pNode;
}
用于对给定结
点 (pNode)的
info和 next字段
同时置值
66
§ 2.3.3 线性链表的面向对象实现
? (三 )指针类 Set类操作 (2)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::SetNodeElem(
TLinkNode<TElem> *pNode,TElem &elem)
{
if (pNode==NULL) throw TExcepLinearList(4);
pNode->info = elem;
return pNode;
}
用于只给指定
的结点 (pNode)
置内容 (elem)
67
§ 2.3.3 线性链表的面向对象实现
? (三 )指针类 Set类操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::SetNodeNext
(TLinkNode<TElem> *pNode,TLinkNode<TElem> *pNodeNext)
{
if (pNode==NULL) throw TExcepLinearList(4);
pNode->next = pNodeNext;
return pNode;
}
用于只给指定
的结点 (pNode)
置后继 (next)
68
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink<TElem>:,NextNode
( TLinkNode<TElem> *pNode)
{
if ( pNode->next = = NULL) TExcepLinearList(4);
lastVisited = pNode;
return pNode->next;
}
返回给定结点
(pNode)的后继
结点的指针
69
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (2)
template <class TElem>
TLinkNode <TElem> *TLinearListLink< TElem>,:
PriorNode (TLinkNode<TElem> *pNode)
{
TLinkNode<TElem> *p;
long i;
if (lastVisited != NULL)
if (lastVisited->next = = pNode)
return lastVisited;
i=0;
p=head;
if (pNode = = head)
throw TExcepLinearList (4);
返回给定结点
(pNode)的前驱
结点的指针
70
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (2)
while (p != NULL)
{
if (p->next = = pNode) break;
i++;
p=p->next;
}
if (p==NULL)
throw TExcepLinearList (4);
lastVisited = p;
lastVisitedIndex = i;
return p;
}
71
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
PriorNode(long idx)
{
return GetNode(idx-1); //Throw the same exception as
GetNode if idx is illegal;
}
根据序号求对
应结点的前驱
结点的指针
72
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (4)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
NextNode(long idx)
{
return GetNode(idx+1);
//Throw the same exception as GetNode if idx is illegal;
}
根据序号求对
应结点的后继
结点的指针
73
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::LocateNode(TElem
&elem,long sn)
{
TLinkNode<TElem> *p,*p0;
long k,i;
k=sn;
if (k<0) k=k+len+1;
if (k<0 )
throw TExcepLinearList(2);
p0=NULL;
p=head;
i=0;
返回元素值为
elem的第 sn次
出现的结点的
指针
74
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (1)
while (p!=NULL)
{
if (p->info==elem)
{
i++;
p0=p;
if (k==i) return p;
}
p=p->next;
}
if (p0==NULL) throw TExcepLinearList(3); //Not found
else return p0; //Found,but sn is larger than the index of the last found
element
}
75
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (2)
template <class TElem>
long TLinearListLink< TElem>::LocateNode(TElem &elem,
TLinkNode<TElem> *foundElemPointer[])
{
TLinkNode<TElem> *p;
long i;
p=head;
i=0; 查找值为 elem的所有元素，
将它们的指针依次存储在
foundElemPoint[]中，并返
回所找到的元素的个数
76
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (2)
while (p!=NULL)
{
if (p->info==elem)
{
foundElemPointer[i]=p;
i++;
}
p=p->next;
}
if (i<=0) throw TExcepLinearList(3); //Not found
return i;
}
77
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
LocateNodeFirst(TElem &elem)
{
TLinkNode<TElem> *p;
int k;
p=head;
k=0; 查找值为 elem的第一个出现的结点，并返回其指针
78
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (3)
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited=p;
lastVisitedIndex = k;
break;
}
k++;
p=p->next;
}
if (p==NULL) throw TExcepLinearList(3); //Not found
else return p; //Found
}
79
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (4)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
LocateNodeNext(TElem &elem)
{
TLinkNode<TElem> *p;
long k;
if (lastVisited==NULL) p=head;
else p=lastVisited->next;
查找值为 elem的下一个出现
的结点，并返回其指针
80
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (4)
k=0;
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited=p;
lastVisitedIndex +=k;
break;
}
p=p->next;
k++;
}
if (p==NULL) throw TExcepLinearList(3); //Not found
else return p; //Found
}
81
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
InsertAfter(TLinkNode<TElem> *pNodeTobeInserted,
TLinkNode<TElem> *pNodeBase)
{
if (pNodeTobeInserted==NULL || pNodeBase==NULL)
throw TExcepLinearList(2);
pNodeTobeInserted->next = pNodeBase->next;
pNodeBase->next = pNodeTobeInserted;
len++;
return pNodeTobeInserted;
}
将指针 pNodeTobeInserted
所指结点，插入到指针
pNodeBase所指结点的后面
82
§ 2.3.3 线性链表的面向对象实现
a2 an… …head
len
a1
图 - 单链表插入结点
pNodeTobeInserted
pNodeBase
pNodeTobeInserted->next
= pNodeBase->next;
pNodeBase->next =
pNodeTobeInserted;
83
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (2)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
Insert(TLinkNode<TElem> *pNodeTobeInserted,
TLinkNode<TElem> *pNodeBase)
{
if (pNodeTobeInserted==NULL || pNodeBase==NULL)
throw TExcepLinearList(2);
TLinkNode<TElem> *p;
在 pNodeBase所指结点之前
插入 pNodeTobeInserted所
指结点
84
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (2)
if (pNodeBase==head)
{
pNodeTobeInserted->next = head;
head = pNodeTobeInserted;
}
else
{
p=PriorNode(pNodeBase);
pNodeTobeInserted->next = pNodeBase;
p->next = pNodeTobeInserted;
}
len++;
return pNodeTobeInserted;
}
85
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
Insert(TLinkNode<TElem> *pNode,long sn)
{
long i,k;
if (sn<0) k=len+sn;
else k=sn-1;
if (k>=len)k=len-1;
if (k<0 )
throw TExcepLinearList(2);
将 pNode所指结点插入到第
sn个元素之前
86
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (3)
if (k==0)
{
pNode->next = head;
head = pNode;
len++;
return pNode;
}
else
{
TLinkNode <TElem> *p;
p=GetNode(k-1);
return InsertAfter(pNode,p);
}
}
87
§ 2.3.3 线性链表的面向对象实现
? (七 )指针类删除操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
DeleteAfter(TLinkNode<TElem> *pNode)
{
if (pNode==NULL)
throw TExcepLinearList(2);
TLinkNode<TElem> *p;
p = pNode->next;
pNode->next = p->next;
len--;
return p;
}
删除 pNode所指结点的后继
结点
88
§ 2.3.3 线性链表的面向对象实现
pNode
pNode->next =p
p
图 - 单链表中删除结点
89
§ 2.3.3 线性链表的面向对象实现
? (七 )指针类删除操作 (2)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
Delete(TLinkNode<TElem> *pNode)
{
if (pNode==NULL
throw TExcepLinearList(2);
TLinkNode<TElem> *p;
删除 pNode所指出的结点
90
§ 2.3.3 线性链表的面向对象实现
? (七 )指针类删除操作 (2)
if (pNode==head)
head = pNode->next;
else
{p=PriorNode(pNode);
p->next = pNode->next;
}
len--;
return pNode;
}
91
§ 2.3.3 线性链表的面向对象实现
? (八 )一般的 Get/Set操作 (1)
template <class TElem>
TElem &TLinearListLink< TElem>::Get(long idx)
{
return Get(GetNode(idx));
//Throw the same exception as GetNode if idx is illegal;
}
92
§ 2.3.3 线性链表的面向对象实现
? (八 )一般的 Get/Set操作 (2)
template <class TElem>
TElem *TLinearListLink< TElem>::GetAddress(long idx)
{
TLinkNode<TElem> *p;
p= GetNode(idx);
//Throw the same exception as GetNode if idx is illega;
return &(p->info);
}
93
§ 2.3.3 线性链表的面向对象实现
? (八 )一般的 Get/Set操作 (3)
template <class TElem>
TElem *TLinearListLink< TElem>::Set(long idx,TElem
&elem)
{
TLinkNode<TElem> *p;
p= GetNode(idx);
//Throw the same exception as GetNode if idx is illegal;
p->info = elem;
//Assume that the TElem support operator "="
return &(p->info);
}
94
§ 2.3.3 线性链表的面向对象实现
? (九 )一般的前驱 /后继操作 (1)
template <class TElem>
TElem *TLinearListLink< TElem>::Prior(long idx)
{
TLinkNode<TElem> *p;
p= GetNode(idx-1);
//Throw the same exception as GetNode if idx is illegal;
return &(p->info);
}
95
§ 2.3.3 线性链表的面向对象实现
? (九 )一般的前驱 /后继操作 (2)
template <class TElem>
TElem *TLinearListLink< TElem>::Next(long idx)
{
TLinkNode<TElem> *p;
p= GetNode(idx+1);
//Throw the same exception as GetNode if idx is illegal;
return &(p->info);
}
96
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (1)
template <class TElem>
long TLinearListLink< TElem>::Locate(TElem &elem,long sn)
{
TLinkNode<TElem> *p;
long k,i,j,j0;
k=sn;
if (k<0) k = CountElem(elem)+sn+1;
if (k<0 )
throw TExcepLinearList(2);
97
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (1)
p=head;
i=0; j=0;j0=0;
while (p!=NULL)
{
if (p->info==elem)
{
i++;
j0=j;
if (k==i) break;
}
p=p->next;
j++;
}
if (j0<=0) throw TExcepLinearList(3); //Not found
else return j0; //Found,but sn is larger than the index of the last found element
}
98
§ 2.3.3 线性链表的面向对象实现
?(十 )一般的定位操作 (2)
template <class TElem>
long TLinearListLink< TElem>::Locate(TElem &elem,long
*foundElemIndex)
{
TLinkNode<TElem> *p;
long i,j;
p=head;
i=0; j=0;
99
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (2)
while (p!=NULL)
{
if (p->info==elem)
{
foundElemIndex[i]=j;
i++;
}
j++;
p=p->next;
}
if (i<=0) throw TExcepLinearList(3); //Not found
return i;
}
100
§ 2.3.3 线性链表的面向对象实现
?(十 )一般的定位操作 (3)
template <class TElem>
long TLinearListLink< TElem>::LocateFirst(TElem &elem)
{
TLinkNode<TElem> *p;
int k;
k=0;
p=head;
101
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (3)
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited = p;
lastVisitedIndex =k;
break;
}
k++;
p=p->next;
}
if (p==NULL) return -1; //Not found
else return k; //Found
}
102
§ 2.3.3 线性链表的面向对象实现
?(十 )一般的定位操作 (4)
template <class TElem>
long TLinearListLink< TElem>::LocateNext(TElem &elem)
{
TLinkNode<TElem> *p;
int k;
k=0;
p=lastVisited;
103
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (4)
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited = p;
lastVisitedIndex+=k;
break;
}
k++;
p=p->next;
}
if (p==NULL) return -1; //Not found
else return k; //Found
}
104
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (5)
template <class TElem>
longTLinearListLink< TElem>::CountElem(TElem &elem)
{
TLinkNode<TElem> *p;
long cnt;
cnt=0;
p=head;
while (p!=NULL)
{
if (p->info == elem) cnt++;
p=p->next;
}
return cnt;
}
105
§ 2.3.3 线性链表的面向对象实现
?(十一 )一般的插入 /删除操作 (1)
template <class TElem>
TElem *TLinearListLink< TElem>::Insert(TElem &elem,long sn)
{
TLinkNode<TElem> *p;
p = new TLinkNode<TElem>;
if (p==NULL) throw TExcepLinearList(4);
SetNodeElem(p,elem);
Insert(p,sn);
return &elem;
}
106
§ 2.3.3 线性链表的面向对象实现
?(十一 )一般的插入 /删除操作 (2)
template <class TElem>
TElem *TLinearListLink< TElem>::Delete(long sn)
{
TLinkNode<TElem> *p;
long k;
if (sn<0) k=len+sn;
else k=sn-1;
107
§ 2.3.3 线性链表的面向对象实现
? (十一 )一般的插入 /删除操作 (2)
if (k<1)
{
p = head;
head = head->next;
len--;
}
else
{
p=GetNode(k-1); //throw a exception if "k" is not in range
p=DeleteAfter(p);
}
buffElem = p->info;
delete p;
return &buffElem;
}
108
§ 2.3.3 线性链表的面向对象实现
?(十一 )一般的插入 /删除操作 (3,4)
Delete(TIndexSelector &sel,TElem *elemDeleted)
该操作的实现留作练习。
DeleteByIndex(long *idxTobeDel,long numIdx,TElem
*elemDeleted)
该操作的实现留作练习。
109
§ 2.4 线性表程序清单
? 见书
110
§ 2.5 几种特殊线性链表
? 头结点
在线性链表的第一个结点的前面增设一个特殊的
结点
? 作用
– 存贮一些有关线性表的信息
– 为了算法处理上的方便
? 增设头指针后，链表的头指针指向头结点，而头结点
才指向第一个元素结点
? 空表时仍含有头结点
§ 2.5.1 带头结点的链表
111
§ 2.5.2 循环链表
? 循环线性表
将第 1 个结点视为最后一个结点的后继，将最后
一个结点视为第 1个结点的前趋
? 相应的链表称循环线性链表（简称 循环链表 ）
?
… …
图 -循环链表
112
§ 2.5.2 循环链表
? 使用循环链表的主要目的是使链表中各结点处
于, 平等, 地位
? 循环链表多半带头结点，构成带头结点的循环
链表
? 最后一个结点的特征是，它的 next等于第一个
结点的指针
113
§ 2.5.2 循环链表
? 对不带头结点的循环链表，扫描一般的模式为：
p = head;
if (p!=NULL) //查找链表是否为空
{ while (p->next!=head)
{
… … //访问结点
p = p->next;
}
… … //这里要访问最后一个结点 p;
}
114
§ 2.5.2 循环链表
? 对带头结点的循环链表，扫描一般的模式为：
p = head->next;
while (p!=head) //空链表时, 仍然有一个结点
(head,其不空 ),但它的 next直接
//指向自己, 故此时该循环条件不满足 。
{
//访问结点
p = p->next;
}
115
§ 2.5.3 双向链表
? 双向链表
单向链表的每个结点增设一个指向相应结
点前趋的指针，使其同时包含前驱和后继两个
链
info----存放元素内容；
next----存放该元素的后继的指针 （ 地址 ） ；
prior----存放该元素的前驱的指针 （ 地址 ） ；
prior info next
116
§ 2.5.3 双向链表
? 双链表的插入
在结点 p之前插入结点 q,其程序片段如下 。
(1) q->next=p;
(2) q->prior=p->prior;
(3) p->prior->next=q;
(4) p->prior=q;
(4)(3)
(2) (1)
q
pp->prior p->next
图 -双链表插入
117
§ 2.5.3 双向链表
? 双链表删除
现设删除结点 p所指结点, 程序片段如下 。
(1) p->prior->next=p->next;
(2) p->next->prior=p->prior;
(3) return p;
(2)
(1)
pp->prior p->next
图 - 双链表的删除
118
§ 2.6 线性表应用示例
? 集合结构，一般可用线性表表示
? 可以模仿线性表设置一个集合类
? 只从算法角度介绍一种集合运算
(A-B)∪ (B-A)
的实现
? 将 (A-B)∪ (B-A)的结果存储在 A中,B保持不变
? 实现策略
对Ｂ中每个元素，检查其在 A中是否出现，若是，从Ａ中删除
之，否则将之加到 A中
§ 2.6.1 集合运算
119
long DiDiff(TLinearListSqu<long> &a,TLinearListSqu<long> &b)
{
long i,j,k;
j=0;
for (i=0; i<b.len; i++)
{
k = a.Locate(b.Get(i),1);
if (k >= 0 )
{a.Delete(k+1); j++;}
else a.Insert(b.Get(i),1);
}
return j;
}
120
§ 2.6.2 一元多项式相加
? (一 ) 一元多项式的表示 ── 数据结构
? 一元多项式
Pn(x)=p0+p1x+p2x2+…+p nxn
? 可用一个线性表 P来表示：
P=(p0,p1,…,pn)
其中,pi代表 Pn(x)中的 i次项系数
? Qm(x)是另一个 m次一元多项式
Q=(q0,q1,…,Q m)
? 设 m<n，则两个多项式相加结果 Rn(x)=Pn(x)+Qm(x)仍为一个一元 n
次多项式
R=(p0+q0,p1+q1,…,p m+qm,pm+1,…,p n)
121
§ 2.6.2 一元多项式相加
? (二 )多项式加法实现 —直接操作链表
? 采用带头结点的非循环链表
P5(x)=7+3x-9x3+x5
7 0 3 1 -9 3 1 5 ^
图 - 一个一元 5次多项式的链表表示
122
§ 2.6.2 一元多项式相加
? (二 )多项式加法实现 —直接操作链表
? A(x)+B(x)→A(x) 的实现方法
? 重复进行下列几个步骤
1,若 p→exp<q→exp, p后移一步, q不动 。
2,若 p→exp>q→exp,将 q插入到 A(x)中 p之前, 然后 q向后移一步,
p不动 。
3,若 p→ exp==q→ exp：将 q的系数加到 p的系数上, 若相加结果为 0，
从 A(x)中删除 p,从 B(x)中删除 q,并令 p与 q分别指向下一结点 。
若相加和不为 0,p后移一步, 然后将 q从 B(x)中摘除, 令 p指向
下一结点 。
设两个指针 p和 q，初始时它们分别指向
A(x)与 B(x)中当前未被处理的（未被加
入到和式中的）结点中指数最小者
123
? (二 )多项式加法实现 —直接操作链表
? 算法的伪码
p=A的第一个元素；
q=B的第一个元素；
while (p存在 && q存在 )
{
if (p的指数 < q的指数 )
{ p0 = p; p = p->next; }
else if (p的指数 > q的指数 )
{
将 q插入到 p之前；
令 p0指向插入后的 q,即 p的当前前驱 ;
令 q指向它原所指的下一个结点；
}
else
{
x = p的系数 + q的系数之和；
124
if (x==0)
{
删除 p;
使 p指向它原指结点的下一个；
}
else
{
令 p的系数为 x;
使 p指向它原指结点的下一个；
}
删除 q;
使 q指向它原指结点的下一个；
} // if (p的指数 > q的指数 ) … else
} //while
if (q不为空 ) 将 q挂接在 p之后；
125
? 完整的程序 (假定链表为, 带头结点, )
int PolynomialAdd(TLinearListLink<TPolynomialItem> &a,
TLinearListLink<TPolynomialItem> &b)
{
TLinkNode<TPolynomialItem> *p,*p0,*q,*q0;
float x;
longk;
k=0;
p = a.head->next;
p0 = a.head;
q = b.head->next;
126
while (p!=NULL && q!=NULL)
{
if (p->exp < q->exp)
{ p0 = p; //永远使 p0保持为 p的前驱, 以方便对在 p前插入, 或删除 p
p = p->next;
k++;
}
else
if (p->exp > q->exp )
{
q0 = q; //在下面用 q0操作原 q
q = q->next; //q先行一步
q0->next = p;
p0->next = q0; // 以上两句, 将 q0插入到 p0之后 （ 即 p之前 ）
k++;
}
127
else
{
x = p->coef + q->coef;
if (x==0)
{
p0->next = p->next;
delete p; //以上两句, 将 p从表中删除并将其所指对象释放
p = p0->next; //令 p指向相对于它原指的下一个
} // if (x==0)
else
{
p->coef = x;
p0 = p;
p = p->next; k++;
} // if (x==0) … else …
128
q0 = q;
q = q->next;
delete q0; //将 q所指结点从表中删除并释放, 令 q新指向原所指的下
一个
} // if (p->exp > q->exp ) … else …
} //while
if (q!=NULL) p0->next = q;
While (q!=NULL) {k++; q=q->next; }
b.head->next = NULL; //此时, b中已只剩第一个结点 （ 头 ）, 为其置
空表标志
return k; //返回结果链表中的元素个数
}
129
? 程序运行例子
7 0 3 2 -9 3 1 5 ^
（ a） A(x)= P5(x)=7+3x2-9x3+x5
进入循环前
p
3 1 9 3 1 5 -1 8 ^
（ b） B(x)=3x+9x3+x5-x8
进入循环前
q
130
7 0 3 2 -9 3 1 5 ^
（ c） A(x):第 1次循环后
p后移
p
3 1 9 3 1 5 -1 8 ^
（ d） B(x)：第 1次循环后
q保持不变
q
131
9 3 1 5 -1 8 ^
（ f） B(x)：第 2次循环后
q被插入到 p之前,q新指向下一个
q
7 0 3 2 -9 3 1 5 ^
（ e） A(x):第 2次循环后
q被插入到 p前
p
3 1
132
9 3 1 5 -1 8 ^
（ h） B(x)：第 3次循环后
q保持
q
7 0 3 2 -9 3 1 5 ^
（ g） A(x):第 3次循环后
p后移
p
3 1
133
7 0 3 2 1 5 ^
（ i） A(x):第 4次循环后
p被删除，新指向下一个
p
3 1
9 3 1 5 -1 8 ^
（ j） B(x)：第 4次循环后
q被删除，新指向下一个
q
134
7 0 3 2 2 5 ^
（ k） A(x):第 5次循环后
p与 p合并,p新指向下一个（空）
p
3 1
9 3 1 5 -1 8 ^
（ l） B(x)：第 5次循环后
q合并到 p，然后被删除，新指向下一个
q
135
7 0 3 2 2 5 ^
（ m） A(x):退出循环后
p后面的挂接到了 p的前驱的尾
p0
-1 8 ^3 1
9 3 1 5
（ n） B(x)：退出循环后
q挂到了 p的前驱后面
图 -多项式链表相加
136
? (三 )多项式加法实现 —借助抽象操作
struct TPolynomialItem
{
float coef;
int exp;
operator ==(TPolynomialItem&i1)
{
return (coef == i1.coef && exp==i1.exp);
};
TPolynomialItem& operator =(TPolynomialItem &i1)
{
this->coef = i1.coef;
this->exp = i1.exp;
return i1;
};
} ;
137
? (三 )多项式加法实现 —借助抽象操作
ostream& operator << (ostream& oo,TPolynomialItem &i1)
{
oo<<i1.coef<<","<<i1.exp<<" ";
return oo;
}
138
? (三 )多项式加法实现 —借助抽象操作
? 多项式加法程序
long PolynomialAdd(TLinearListSqu<TPolynomialItem>
&a,TLinearListSqu<TPolynomialItem> &b)
{
long currE1,currE2,k;
TPolynomialItem e1,e2;
k=0;
currE1=0;
currE2=0;
139
while (currE1 <a.len && currE2<b.len)
{
e1=a.Get(currE1);
e2=b.Get(currE2);
if (e1.exp < e2.exp)
{ currE1++; k++; }
else
if (e1.exp > e2.exp)
{ a.Insert(e2,currE1+1);
currE1++;
b.Delete(currE2+1);
k++;
}
140
else
{
e1.coef = e1.coef + e2.coef;
if (e1.coef==0)
a.Delete(currE1+1);
else
{a.Set(currE1,e1);
currE1++;
k++;
}
b.Delete(currE2+1);
}
}
if (currE2 < b.len)
for (int i = currE2+1; i<b.len+1; i++,k++)
a.Insert(*(b.Delete(i)),a.len+1);
return k;
}
141
§ 2.6.3 一元多项式的乘法
? 设 Am(x)与 Bn(x)为两个一元多项式, 设
Am(x) = Bn(x) =
? 则
Am(x)·Bn(x)= Bn(x)
=
? 两个一元多项式相乘, 可以化为多个一元多项式相加
?
?
m
i
e
i
ixa
1
?
?
n
i
p
i ixa
1
?
?
m
i
e
i ixa
1
?
?
m
i
e
ni
ixxBa
1
))((
142
习题
2.1编写程序, 实现在有序表 （ 表中元素按元素关键字大
小排序 ） 中插入一个元素, 使原有序表保持有序 。
分别假定有序表是连续存贮结构和链式存贮结构 。
2.2编定实现合并两个有序表, 使得合并结果仍为有序表
的程序 。 分别假定有序表按顺序方式存贮和链接方
式存贮 。
2.3 完善讲义给出的 TindexSelector类 。
2.4假定用线性表表示集合, 请定义相应的集合类, 实现
集合的各种基本运算 （ 交, 并, 差等 ） 及判别成员,
求子集, 查找元素等操作 。
2.5编写一个通过终端交互建立链表 （ 动态或静态 ） 的程
序, 使得较先输入的结点放在链表较前的位置 。
143
习题 (续 )
2.6写一个单链表倒链程序, 即将单链表中每个结点的
前趋与后继关系颠倒 。
2.7写一个建立双向链表的程序 （ 分别针对动态与静态
两种链表 ） 。
2.8分别针对动态与连续存贮结构, 编写程序实现
Josephus问题：设有 n个人围坐在一个圆桌周围, 从
第 s个人开始扳数, 数到第 m的人就出列, 然后从出
列者的下一个人开始重新按上述方式扳数, 出列,
如此重复, 直到所有的人全部出列好止 。 要求的结
果是, 给出每个人的出列次序 （ 给定 n,对任意合
法的 s与 m） （ 即求一个按出列次序排列的 n个人的
顺序表 。
2.9编写一个一元 n次多项式的化简程序 （ 即将多项式
内的同类项合并, 0系数项去除, 并使各项按指数
升序排列 ） 。
144
习题 (续 )
2.10假定一元 n次多项式用连续存贮结构的线性表表
示 （ 不含 0系数项 ）, 编写两多项式相加的程序 。
2.11写一个实现两一元 n次多项式相乘的程序 。
2.12实现 Delete(TindexSelector &sel)
2.13 在类 TLinearListSqu或 TlinearListLink基础上, 实
现 Copy,Merge,Sort等操作 。
2.14 直接利用 TlinearListLink实现多项式加法 。
2.15 在类 TLinearListSqu或 TlinearListLink基础上, 实
现一个学生基本信息登记表的操作, 包括, 输入,
修改, 打印, 查询, 统计等功能 。
2
第二章 线性表
? 线性表的逻辑结构
? 线性表的顺序存贮结构
? 线性表的链式存储 ----线性链表
? 几种特殊线性链表
? 线性表应用示例
3
§ 2.1 线性表的逻辑结构
? 线性表（ Linear list）,
是数据元素的一个有限序列，在这个序列中,每个元素有
一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元
素可以无前趋，而最后一个元素也可以无后继
? 可记为
L = (a1,a2,…, an)；
ai为数据元素,ai-1称为 ai的 前趋 （ i≥ 1）,ai+1称为 ai 的 后继 （ i≤ n），
i=1,2,…,n.
§ 2.1.1 基本概念
4
§ 2.1.1 基本概念
? 线性表中元素的个数称线性表的 长度, n=0时
称为 空表, 空表长度为 0。
? 按形式化方法，线性表定义为
LL=（ D,S）
D={a1,a2,…,an}
S={r}
r= { <ai-1,ai>｜ ai∈ D,i=2,…,n}。
5
§ 2.1.2 基本操作
? Init(L),初始化操作, 设定一个空的线性表 L,执行该操作后, 线
性表 L就可用于其它操作 。
? Len(L),求长度函数 。 函数值为线性表中元素的个数 。
? Get(L,i),取元素函数 。 函数值为 L中的序号为 i的元素 （ 值或地
址 ） 。
? Set(L,i,x),置值函数 。 将 L中的序号为 i的元素的值置为 x.
? Prior(L,x),求前趋函数 。 函数值为 L中的 x的前趋 。
? Next(L,x),求后继函数 。 函数值为 L中的 x的后继 。
? Locate(L,x),查找函数 。 函数值为 L中的元素 x的序号, 若 x不在 L
中, 则返回特殊标志 。
6
§ 2.1.2 基本操作
? Insert (L,i,x),插入操作 。 将元素 x插入到 L中的第 i个元素之前,
使原第 i个元素及其后的各元素的序号分别增 1。
? Deletel (L,i),删除操作 。 将 L中的第 i个元素删除掉, 使 L 中的元
素个数减 1,原第 i个元素之后的元素的序号分别减 1。
? Empty (L),判定函数 。 若 L为空表, 函数值为, 真,, 否则为
,假, 。
? Clear (L),置空操作 。 使 L成为空表 。
7
§ 2.1.2 基本操作
? Copy (L1,L2),复制操作 。 生成一个名为 L2的与 L1完全相同的线
性表 。
? Sort ( L,key,type),排序操作 。 按线性表中元素的关键字 key的递
增或递减 （ 由 type确定 ） 次序重新排列 L中的元素次序 。
? Merge ( L1,L2,L3 ),合并操作 。 使 L3取 L1和 L2首尾相连的结果
? Split ( L,i,L1,L2),分拆操作 。 使 L1为 L中的前 i个元素 （ 含第 i个 ）
构成的线性表, L2为剩余部分构成的线性表 。
8
§ 2,1.3 异常处理
? 异常 (Exception)：
是指程序运行中，由于运行环境、数据
输入或操作不当而导致程序不能物理地运行的
错误
? 不能通过静程序发现异常（只能估计它的可能
性），而只能通过程序的运行发现
9
§ 1.2.3 异常处理
? 在 C++中，为程序员提供了良好的处理异常的
机制
– try----检测 /捕获异常；
– catch----处理 try所捕获的异常；
– throw----生成一个异常, 交由 try捕获；
10
§ 2.1.3 异常处理
? 首先，设立一个表，存储异常代码和用于说明异常的文字信息
struct TErrMessageRec
{
int no;
char msg [CNST_SizeErrMessage ];
};
class TErrMessageList
{
TErrMessageRec msgList [CNST_MaxNumErrMessage ];
public:
int len;
TErrMessageList()
{
int i = 0;
11
§ 2.1.3 异常处理
/* 0*/ msgList[i].no=i; strcpy(msgList[i].msg,"Unkonwn error"); i++;
/* 1*/ msgList[i].no=i; strcpy(msgList[i].msg,"The parameters Out of range"); i++;
/* 2*/ msgList[i].no=i; strcpy(msgList[i].msg,"The parameters illegal"); i++;
/* 3*/ msgList[i].no=i; strcpy(msgList[i].msg,"The memory space low"); i++;
/* 4*/ msgList[i].no=i; strcpy(msgList[i].msg,"Not found"); i++;
len = i;
};
char *GetMessage(int no)
{
if (no<0 || no >= CNST_MaxNumErrMessage)
return NULL;
return msgList [no].msg;
};
};
全局的出错代码表 errMessageList
extern TErrMessageList errMessageList;
12
§ 2.1.3 异常处理
? 定义一个可用的异常处理类 TExcepComm
class TExcepComm
{
public:
int errNo;
char errMessage[CNST_SizeErrMessage];
TExcepComm (int mErrNo)
{
errNo = mErrNo;
strcpy (errMessage,errMessageList.GetMessage(errNo));
}
};
13
§ 2.1.4 下标选择器
? TIndexSelector是一个字符串形式的下标选择器
IndexSelector,:=IndexScope|(IndexScope "," IndexSelector)
IndexScope,:= INTEGER |( INTEGER? "_" INTEGER?)
INTEGER,:=("-"| "+")? DIGITS
DIGITS,:=DIGIT |( DIGIT DIGITS)
DIGIT,:= 0|1|2|3|4|5|6|7|8|9
14
§ 2.1.4 下标选择器
? 合法的下标选择器
5
1_
_8
_
1,2
1,2_3,-1_-3
3_4,2,7_8,10_
15
§ 2.1.4 下标选择器
? TIndexSelector类的定义
struct TSelectorItem
{
long lower;
long upper;
};
class TIndexSelector
{
TSelectorItem room[CNST_SizeIndexSelector];
int lastVisitedItem;
int LoadFromArray (TSelectorItem *se,int n,long maxIdx);
long Standardize(void);
16
§ 2.1.4 下标选择器
public:
int len;
long maxIndex;
TIndexSelector (char *) {len=0;};
TIndexSelector (TSelectorItem *se,int n,long maxIdx);
int GetFirst(long &lw,long &up);
int GetNext(long &lw,long &up);
long GetEachIndex(long *idxs);
int Get(int idx,long &lw,long &up);
int Set(int idx,long lw,long up);
long GetIndexNum(void);
17
§ 2.1.4 下标选择器
int ResetByFromArray(TSelectorItem *se,int n,long maxIdx);
/*
long GetLower(int idx);
long GetUpper(int idx);
int SetLower(int idx,lw);
int SetUpper(int idx,up);
int Insert(int idx,long lw,long up);
int InsertLower(int idx,long lw);
int InsertUpper(int idx,long up);
int Delete(int idx);
*/
};
18
§ 2.1.5 线性表抽象类
? 线性表抽象类的定义
class TExcepLinearList
{
public:
int errNo;
char errMessage[CNST_SizeErrMessage];
TExcepLinearList(int mErrNo)
{
errNo=mErrNo;
strcpy(errMessage,errMessageList.GetMessage(errNo));
}
};
专用于线性表类的异
常处理类
19
§ 2.1.5 线性表抽象类
? 当检测到异常时, 使用 throw 抛 掷 一 个
TExceptionLinearlist对象, 产生一个该类型的
异常, 形式为：
throw TExceptionLinearlist（ no） ;
20
§ 2.1.5 线性表抽象类
template <class TElem>
class TLinearList0
{
protected:
public:
long len;
virtual TBool IsEmpty ()
{if (len <=0) return True; else return False;}
virtual TElem &Get (long idx) = 0;
virtual TElem *Set (long idx,TElem &elem) = 0;
virtual TElem *Prior (long idx) = 0;
virtual TElem *Next (long idx) = 0;
virtual TElem *GetAddress (long idx)=0;
线性表抽象类
21
§ 2.1.5 线性表抽象类
virtual long CountElem (TElem &elem)=0;
virtual long Locate (TElem &elem,long sn=1) = 0;
virtual long Locate (TElem &elem,long *foundElem) = 0;
virtual long LocateFirst (TElem &elem) = 0;
virtual long LocateNext (TElem &elem) = 0;
virtual TElem *Insert (TElem &elem,long sn=1) = 0;
virtual TElem *Delete (long sn=1)=0;
virtual long Delete (TIndexSelector &sel,TElem *elemDeleted = NULL) = 0;
virtual long DeleteByIndex (long *idxTobeDel,
long numIdx,TElem *elemDeleted=NULL)=0;
};
22
§ 2.2 线性表的顺序存贮结构
? 线性表的顺序存贮
将表中各元素依它们的逻辑次序存贮在一片连续
的存贮区域中，使任意两相邻元素之间的存贮单元个
数相等
? 设线性表为 L=(a1,a2,…,a n)，每个元素占 2个存贮单元，
§ 2.2.1 基本存储方法
a1 a2 a3 … …
图 2.1 线性表的顺序存储
有下列关系成立 Loc ( ai ) =Loc(a1) + ( i -1) * c
23
§ 2.2.2 面向对象描述
? (一 ) 对象结构
? 线性表的顺序存贮结构的存储区域，可用高级
语言中的数组模拟
? 从面向对象观点看，顺序存储的线性表，是一
个对象，其主要数据成员是一维数组
? 一维数组采用动态空间表示
24
§ 2.2.2 面向对象描述
? (一 ) 对象结构
template <class TElem>
class TLinearListSqu, public TLinearList0<TElem>
{
protected:
TElem *room;
long size;
long lastVisited;
TElem buffElem;
long ResizeRoom (long newSize);
long CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2);
25
§ 2.2.2 面向对象描述
? (一 ) 对象结构
public:
TLinearListSqu (void);
TLinearListSqu (long mSize);
~TLinearListSqu (void);
virtual TElem &Get (long idx);
virtual TElem *GetAddress (long idx);
virtual TElem *Set (long idx,TElem &elem);
virtual TElem *Prior (long idx);
virtual TElem *Next (long idx);
virtual long CountElem (TElem &elem);
26
§ 2.2.2 面向对象描述
? (一 ) 对象结构
virtual long Locate (TElem &elem,long sn=1);
virtual long Locate (TElem &elem,long *foundElemIndex);
virtual long LocateFirst (TElem&elem);
virtual long LocateNext (TElem &elem);
virtual TElem *Insert (TElem &elem,long sn=1);
virtual TElem *Delete (long sn=1);
virtual long Delete (TIndexSelector &sel,TElem *elemDeleted=NULL);
virtual long DeleteByIndex (long *idxTobeDel,long numIdx,
TElem *elemDeleted=NULL);
void Print (); //Only for test
};
27
§ 2.2.2 面向对象描述
? (二 )初始化
template <class TElem>
TLinearListSqu< TElem>::TLinearListSqu ( )
{
size = 0;
len = 0;
room = NULL;
}
28
§ 2.2.2 面向对象描述
? (二 )初始化
template <class TElem>
TLinearListSqu< TElem>::TLinearListSqu (long mSize)
{
size=0;
room=NULL;
len=0;
if (mSize<1) throw TExcepLinearList(2);
room = new TElem[mSize];
if (room==NULL) throw TExcepLinearList(3);
size = mSize;
}
29
template <class TElem>
TLinearListSqu< TElem>::~TLinearListSqu(void)
{
if (room != NULL)
delete [] room;
}
§ 2.2.2 面向对象描述
30
§ 2.2.2 面向对象描述
? (三 )元素直接访问
? Get和 Set类函数用于实现按序号（逻辑关系）
访问元素
template <class TElem>
TElem &TLinearListSqu< TElem>::Get (long idx)
{
if (idx<0 || idx>=len)
throw TExcepLinearList(1);
return room[idx];
}
31
§ 2.2.2 面向对象描述
template <class TElem>
TElem *TLinearListSqu< TElem>::GetAddress
(long idx)
{
if (idx<0 || idx>=len)
throw TExcepLinearList(1);
return &room[idx];
}
32
§ 2.2.2 面向对象描述
template <class TElem>
TElem *TLinearListSqu< TElem>::Set (long idx,
TElem &elem)
{
if (idx<0 || idx>=len)
throw TExcepLinearList(1);
room[idx] = elem;
return &room[idx];
}
33
§ 2.2.2 面向对象描述
? (四 )前驱 /后继操作
template <class TElem>
TElem *TLinearListSqu< TElem>::Prior (long idx)
{
if (idx-1<0 || idx-1>=len)
throw TExcepLinearList(1);
return &room[idx-1];
}
34
§ 2.2.2 面向对象描述
? (四 )前驱 /后继操作
template <class TElem>
TElem *TLinearListSqu< TElem>::Next (long idx)
{
if (idx+1<0 || idx+1>=len)
throw TExcepLinearList(1);
return &room[idx+1];
}
35
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (1)
template <class TElem>
long TLinearListSqu< TElem>::Locate (TElem &elem,long sn)
{
long i,k;
k=0;
if (sn>0)
{ for (i=0; i<len; i++)
if (room[i]==elem)
{
k++;
if (k==sn) return i;
}
}
查找值等于 elem的第 sn个元
素，存在时返回其在表中的
序号。由于 sn可能是负值
（表示倒数第 sn个，设最后
一个的 sn为 -1）
36
§ 2.2.2 面向对象描述
? (五 )查找定位操作
else
for (i=len-1; i>=0; i--)
if (room[i]==elem)
{
k++;
if (k==-sn) return i;
}
if (k>0) return i; //"sn" is larger the number of matched element.
//The last is found and its index is returned
else return -1; //Not found
}
37
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (2)
template <class TElem>
long TLinearListSqu< TElem>:,Locate (TElem &elem,long
*foundElemIndex)
{
long i,k;
k=0;
for (i=0; i<len; i++)
if (room[i]==elem) //Assume the TElem support the operator "=="
{
foundElemIndex[k]= i;
k++;
}
return k;
}
求出值为 elem的所有元素的序
号，并存入 foundElemIndex所
指出的一维数组中
38
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (3)
template <class TElem>
long TLinearListSqu< TElem>::LocateFirst (TElem &elem)
{
long i;
for (i=0; i<len; i++)
if (room[i]==elem)
{
lastVisited=i;
return i;
}
return -1; //Not found
}
与 LocateNext配合使用，用于
逐个访问值为 elem的各元素；
查找值为 elem的第一个出现的
元素的序号
39
§ 2.2.2 面向对象描述
? (五 )查找定位操作
? 根据元素内容，求出该元素的位置（序号） (3续 )
template <class TElem>
long TLinearListSqu< TElem>::LocateNext (TElem &elem)
{
long i;
for (i=lastVisited+1; i<len; i++)
if (room[i]==elem)
{
lastVisited=i;
return i;
}
return -1; //Not found
}
查找值为 elem的下一个
出现的元素
记下最近一次调用
LocateFirst/LocateNext所找
到的元素的序号
40
§ 2.2.2 面向对象描述
? (六 )插入操作
template <class TElem>
TElem *TLinearListSqu< TElem>::Insert (TElem &elem,
long sn)
{
long i,k;
int ret=0;
if (sn<0) k=len+sn;
else k=sn-1;
if ( k>len) k=len;
else if (k<0) k=0;
在表中第 sn个元素的前面插
入指定的元素 elem
41
§ 2.2.2 面向对象描述
? (六 )插入操作
if (len>=size)
{
ret=ResizeRoom(size+10);
if (ret<0) throw TExcepLinearList(3);
}
for (i=len-1; i>=k; i--)
room[i+1] = room[i];
room[k]=elem;
len++;
return &room[k];
}
42
§ 2.2.2 面向对象描述
? (六 )插入操作
? 基本插入操作的时间复杂度
– 算法中耗时最大的执行是元素移动的语句
for (i=len-1; i>=k; i--) room[i+1] = room[i];
– 移动元素的次数应为概率平均（数学期望）
f(n) =
ci与算法有关，在这里 ci = (n – i )
假定插入位置是等概率的，则 pi=1/(n+1)，则
f(n) = = =
= =
=O(n)
i
n
i
icp?
?0
i
n
i
icp?
?
?
1
0
??
? ?
1
0 1
n
i
inc ??
?
?? 1
0
)(11 n
i
inn
2
)1(
1
1 ?
?
nn
n 2
n
43
§ 2.2.2 面向对象描述
? (六 )删除操作 (1)
template <class TElem>
TElem *TLinearListSqu< TElem>::Delete (long sn)
{
long i,k;
if (sn<0) k=len+sn;
else k=sn-1;
if (k<0 || k>=len)
throw TExcepLinearList(2);
删除表中第 sn个元素 (sn的含
义同 Locate)，并将其值的地
址返回
44
§ 2.2.2 面向对象描述
? (六 )删除操作
buffElem=room[k];
for (i=k; i<len; i++)
room[i] = room[i+1];
len--;
if (2*len < size)
ResizeRoom(len+long(len/2.0));
return &buffElem;
}
时间复杂度 O(n)
45
§ 2.2.2 面向对象描述
? (六 )删除操作 (2)
template <class TElem>
long TLinearListSqu< TElem>::Delete (TIndexSelector &sel,TElem
*elemDeleted)
{
long i;
long *indexDeleted;
i = sel.GetIndexNum();
indexDeleted = new long[i];
if (indexDeleted==NULL) throw TExcepLinearList(4);
i=sel.GetEachIndex(indexDeleted);
i=DeleteByIndex(indexDeleted,i,elemDeleted);
delete[] indexDeleted;
return i;
}
删除下标选择器 sel所指出的
各元素
时间复杂度 O(n)
46
§ 2.2.2 面向对象描述
? (六 )删除操作 (3)
? 根据下标列举 idxTobeDel进行删除
序号,0 1 2 3 4 5 6 7 8 9, 10 11 12
元素,x x * * x * x x * * x * *
图 - 删除带标记的元素
k=2 k=3
47
§ 2.2.2 面向对象描述
? (六 )删除操作 (3)
template <class TElem>
longTLinearListSqu< TElem>::DeleteByIndex
(long *idxTobeDel,long numIdx,TElem *elemDeleted)
{
long i,k;
k=0;
for (i=0; i<len; i++)
{
if (i==idxTobeDel[k])
{
if (elemDeleted!=NULL)
elemDeleted[k]= room[i];
k++;
}
else room[i-k] =room[i];
}
时间复杂度 O(n)
48
§ 2.2.2 面向对象描述
? (六 )删除操作 (3)
len = len - k;
if (2*len < size)
ResizeRoom(len+long(len/2.0));
return k;
}
49
§ 2.3 线性表的链式存储 ----线性链表
? 连续存贮结构 的讨论
– 优点是存贮利用率高，访问元素的速度快
– 几方面的缺点
? 当进行插入与删除时，需移动元素
? 存贮要求较高，不能利用小块存贮区
? 如果对线性表经常要进行插入删除并需动态扩
充容量，则需采用 链式存贮结构
50
§ 2.3.1 链式存贮方法
? 线性表采用链式存贮结构时称为 线性链表
? 单链表,以后继或前驱地址为链的存储方法
? 具体的存贮映射方法,
– 1、对线性表中每个元素 ai，为它分配一块存贮区
– 2、每个元素的存贮区分为两大部分
– 3．为了能方便地访问链表，设置链表头结点
内容 前驱 /后继地址
51
§ 2.3.1 链式存贮方法
图 - 单链表基本形式
a2 an ^head
len
a1
表头
TLinearLis
tLink
链结点
TLinkNode
52
§ 2.3.2 线性链表的面向对象描述
template <class TElem>
struct TLinkNode
{
TElem info;
TLinkNode *next; //Note,not necessary for
<TElem> to follow TLinkNode here
};
53
§ 2.3.2 线性链表的面向对象描述
template <class TElem>
class TLinearListLink, public TLinearList0<TElem>
{
protected:
TLinkNode<TElem> *head;
TLinkNode<TElem> *lastVisited;
long lastVisitedIndex;
TElem buffElem;
void ReleaseAll();
54
§ 2.3.2 线性链表的面向对象描述
public:
TLinearListLink(void);
~TLinearListLink(void);
virtual TElem &Get(long idx);
virtual TElem *GetAddress(long idx);
virtual TElem *Set(long idx,TElem &elem);
virtual long CountElem(TElem &elem);
virtual TElem *Prior(long idx);
virtual TElem *Next(long idx)
55
§ 2.3.2 线性链表的面向对象描述
virtual long Locate(TElem&elem,long sn=1);
virtual long Locate(TElem&elem,long *foundElemIndex=NULL);
virtual long LocateFirst(TElem&elem);
virtual long LocateNext(TElem&elem);
virtual TElem *Insert(TElem &elem,long sn=1);
virtual TElem *Delete(longsn=1);
virtual long Delete(TIndexSelector &sel,TElem *elemDeleted=NULL);
virtual long DeleteByIndex(long*idxTobeDel,long numIdx,
TElem *elemDeleted=NULL);
void Print(); //Only for test
56
§ 2.3.2 线性链表的面向对象描述
//New functions
virtual TElem &Get(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *GetNode(longidx);
virtual long GetNodeIndex(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *SetNode(TLinkNode<TElem> *pNode,
TElem &elem,TLinkNode<TElem> *pNodeNext);
virtual TLinkNode<TElem> *SetNodeElem(TLinkNode<TElem> *pNode,
TElem &elem);
virtual TLinkNode<TElem> *SetNodeNext(TLinkNode<TElem> *pNode,
TLinkNode<TElem> *pNodeNext);
57
§ 2.3.2 线性链表的面向对象描述
virtual TLinkNode<TElem> *PriorNode(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *NextNode(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *PriorNode(longidx);
virtual TLinkNode<TElem> *NextNode(longidx);
virtual TLinkNode<TElem> *LocateNode(TElem&elem,long sn=1);
virtual long LocateNode(TElem &elem,TLinkNode<TElem>
*foundElemPointer[]);
58
§ 2.3.2 线性链表的面向对象描述
virtual TLinkNode<TElem> *LocateNodeFirst(TElem&elem);
virtual TLinkNode<TElem> *LocateNodeNext(TElem&elem);
virtual TLinkNode<TElem> *InsertAfter (TLinkNode<TElem>
*pNodeTobeInserted,TLinkNode<TElem> *pNodeBase);
virtual TLinkNode<TElem> *Insert(TLinkNode<TElem> *pNodeTobeInserted,
TLinkNode<TElem> *pNodeBase);
virtual TLinkNode<TElem> *DeleteAfter(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *Delete(TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem> *Insert(TLinkNode<TElem> *pNode,long sn=1);
};
59
§ 2.3.3 线性链表的面向对象实现
? (一 )初始化
template <class TElem>
TLinearListLink< TElem>::TLinearListLink()
{
head=NULL;
len=0;
lastVisitedIndex=0;
lastVisited=NULL;
}
60
§ 2.3.3 线性链表的面向对象实现
? (一 )初始化
template <class TElem>
void TLinearListLink< TElem>::ReleaseAll()
{
if (head==NULL) return;
TLinkNode<TElem> *p,*q;
p=head;
while (p!=NULL)
{
q=p;
p=p->next;
delete q;
}
}
61
§ 2.3.3 线性链表的面向对象实现
? (二 )指针类 Get类操作 (1)
template <class TElem>
TElem &TLinearListLink< TElem>::Get(TLinkNode<TElem>
*pNode)
{
if ( pNode==NULL) TExcepLinearList(4);
return pNode->info;
}
? 该函数返回指定结点中的元素内容
62
§ 2.3.3 线性链表的面向对象实现 ? (二 )指针类 Get类操作 (2)
template <class TElem>
long TLinearListLink< TElem>::GetNodeIndex(TLinkNode<TElem>
*pNode)
{
if ( pNode==NULL) TExcepLinearList(4);
TLinkNode<TElem> *p;
long i;
i=0;
p=head;
while (p!=NULL)
{
if (p==pNode) break;
i++;
p=p->next;
}
if ( p==NULL) TExcepLinearList(4);
return i;
}
返回指定结点在表中的序
号
63
§ 2.3.3 线性链表的面向对象实现
? (二 )指针类 Get类操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::GetNode(long idx)
{
TLinkNode<TElem> *p;
long i;
if (idx<0 || idx>=len)
throw TExcepLinearList(2);
if (lastVisited!=NULL && idx >= lastVisitedIndex)
{ p=lastVisited;
i=lastVisitedIndex;
}
函数通过序号求指针，它
返回指定序号 idx所对应的
结点的指针
64
§ 2.3.3 线性链表的面向对象实现 ? (二 )指针类 Get类操作 (3)
else
{
p=head;
i=0;
}
while (p!=NULL)
{
if (i==idx) break;
i++;
p=p->next;
}
if ( p==NULL) TExcepLinearList(0);
lastVisitedIndex=i;
lastVisited=p;
return p;
}
65
§ 2.3.3 线性链表的面向对象实现
? (三 )指针类 Set类操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::SetNode(
TLinkNode<TElem> *pNode,TElem &elem,
TLinkNode<TElem> *pNodeNext)
{
if (pNode==NULL) throw TExcepLinearList(4);
pNode->info = elem;
pNode->next = pNodeNext;
return pNode;
}
用于对给定结
点 (pNode)的
info和 next字段
同时置值
66
§ 2.3.3 线性链表的面向对象实现
? (三 )指针类 Set类操作 (2)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::SetNodeElem(
TLinkNode<TElem> *pNode,TElem &elem)
{
if (pNode==NULL) throw TExcepLinearList(4);
pNode->info = elem;
return pNode;
}
用于只给指定
的结点 (pNode)
置内容 (elem)
67
§ 2.3.3 线性链表的面向对象实现
? (三 )指针类 Set类操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::SetNodeNext
(TLinkNode<TElem> *pNode,TLinkNode<TElem> *pNodeNext)
{
if (pNode==NULL) throw TExcepLinearList(4);
pNode->next = pNodeNext;
return pNode;
}
用于只给指定
的结点 (pNode)
置后继 (next)
68
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink<TElem>:,NextNode
( TLinkNode<TElem> *pNode)
{
if ( pNode->next = = NULL) TExcepLinearList(4);
lastVisited = pNode;
return pNode->next;
}
返回给定结点
(pNode)的后继
结点的指针
69
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (2)
template <class TElem>
TLinkNode <TElem> *TLinearListLink< TElem>,:
PriorNode (TLinkNode<TElem> *pNode)
{
TLinkNode<TElem> *p;
long i;
if (lastVisited != NULL)
if (lastVisited->next = = pNode)
return lastVisited;
i=0;
p=head;
if (pNode = = head)
throw TExcepLinearList (4);
返回给定结点
(pNode)的前驱
结点的指针
70
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (2)
while (p != NULL)
{
if (p->next = = pNode) break;
i++;
p=p->next;
}
if (p==NULL)
throw TExcepLinearList (4);
lastVisited = p;
lastVisitedIndex = i;
return p;
}
71
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
PriorNode(long idx)
{
return GetNode(idx-1); //Throw the same exception as
GetNode if idx is illegal;
}
根据序号求对
应结点的前驱
结点的指针
72
§ 2.3.3 线性链表的面向对象实现
? (四 )链指针类前驱 /后继操作 (4)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
NextNode(long idx)
{
return GetNode(idx+1);
//Throw the same exception as GetNode if idx is illegal;
}
根据序号求对
应结点的后继
结点的指针
73
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::LocateNode(TElem
&elem,long sn)
{
TLinkNode<TElem> *p,*p0;
long k,i;
k=sn;
if (k<0) k=k+len+1;
if (k<0 )
throw TExcepLinearList(2);
p0=NULL;
p=head;
i=0;
返回元素值为
elem的第 sn次
出现的结点的
指针
74
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (1)
while (p!=NULL)
{
if (p->info==elem)
{
i++;
p0=p;
if (k==i) return p;
}
p=p->next;
}
if (p0==NULL) throw TExcepLinearList(3); //Not found
else return p0; //Found,but sn is larger than the index of the last found
element
}
75
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (2)
template <class TElem>
long TLinearListLink< TElem>::LocateNode(TElem &elem,
TLinkNode<TElem> *foundElemPointer[])
{
TLinkNode<TElem> *p;
long i;
p=head;
i=0; 查找值为 elem的所有元素，
将它们的指针依次存储在
foundElemPoint[]中，并返
回所找到的元素的个数
76
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (2)
while (p!=NULL)
{
if (p->info==elem)
{
foundElemPointer[i]=p;
i++;
}
p=p->next;
}
if (i<=0) throw TExcepLinearList(3); //Not found
return i;
}
77
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
LocateNodeFirst(TElem &elem)
{
TLinkNode<TElem> *p;
int k;
p=head;
k=0; 查找值为 elem的第一个出现的结点，并返回其指针
78
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (3)
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited=p;
lastVisitedIndex = k;
break;
}
k++;
p=p->next;
}
if (p==NULL) throw TExcepLinearList(3); //Not found
else return p; //Found
}
79
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (4)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
LocateNodeNext(TElem &elem)
{
TLinkNode<TElem> *p;
long k;
if (lastVisited==NULL) p=head;
else p=lastVisited->next;
查找值为 elem的下一个出现
的结点，并返回其指针
80
§ 2.3.3 线性链表的面向对象实现
? (五 )指针类定位操作 (4)
k=0;
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited=p;
lastVisitedIndex +=k;
break;
}
p=p->next;
k++;
}
if (p==NULL) throw TExcepLinearList(3); //Not found
else return p; //Found
}
81
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
InsertAfter(TLinkNode<TElem> *pNodeTobeInserted,
TLinkNode<TElem> *pNodeBase)
{
if (pNodeTobeInserted==NULL || pNodeBase==NULL)
throw TExcepLinearList(2);
pNodeTobeInserted->next = pNodeBase->next;
pNodeBase->next = pNodeTobeInserted;
len++;
return pNodeTobeInserted;
}
将指针 pNodeTobeInserted
所指结点，插入到指针
pNodeBase所指结点的后面
82
§ 2.3.3 线性链表的面向对象实现
a2 an… …head
len
a1
图 - 单链表插入结点
pNodeTobeInserted
pNodeBase
pNodeTobeInserted->next
= pNodeBase->next;
pNodeBase->next =
pNodeTobeInserted;
83
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (2)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
Insert(TLinkNode<TElem> *pNodeTobeInserted,
TLinkNode<TElem> *pNodeBase)
{
if (pNodeTobeInserted==NULL || pNodeBase==NULL)
throw TExcepLinearList(2);
TLinkNode<TElem> *p;
在 pNodeBase所指结点之前
插入 pNodeTobeInserted所
指结点
84
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (2)
if (pNodeBase==head)
{
pNodeTobeInserted->next = head;
head = pNodeTobeInserted;
}
else
{
p=PriorNode(pNodeBase);
pNodeTobeInserted->next = pNodeBase;
p->next = pNodeTobeInserted;
}
len++;
return pNodeTobeInserted;
}
85
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (3)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
Insert(TLinkNode<TElem> *pNode,long sn)
{
long i,k;
if (sn<0) k=len+sn;
else k=sn-1;
if (k>=len)k=len-1;
if (k<0 )
throw TExcepLinearList(2);
将 pNode所指结点插入到第
sn个元素之前
86
§ 2.3.3 线性链表的面向对象实现
? (六 )指针类插入操作 (3)
if (k==0)
{
pNode->next = head;
head = pNode;
len++;
return pNode;
}
else
{
TLinkNode <TElem> *p;
p=GetNode(k-1);
return InsertAfter(pNode,p);
}
}
87
§ 2.3.3 线性链表的面向对象实现
? (七 )指针类删除操作 (1)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
DeleteAfter(TLinkNode<TElem> *pNode)
{
if (pNode==NULL)
throw TExcepLinearList(2);
TLinkNode<TElem> *p;
p = pNode->next;
pNode->next = p->next;
len--;
return p;
}
删除 pNode所指结点的后继
结点
88
§ 2.3.3 线性链表的面向对象实现
pNode
pNode->next =p
p
图 - 单链表中删除结点
89
§ 2.3.3 线性链表的面向对象实现
? (七 )指针类删除操作 (2)
template <class TElem>
TLinkNode<TElem> *TLinearListLink< TElem>::
Delete(TLinkNode<TElem> *pNode)
{
if (pNode==NULL
throw TExcepLinearList(2);
TLinkNode<TElem> *p;
删除 pNode所指出的结点
90
§ 2.3.3 线性链表的面向对象实现
? (七 )指针类删除操作 (2)
if (pNode==head)
head = pNode->next;
else
{p=PriorNode(pNode);
p->next = pNode->next;
}
len--;
return pNode;
}
91
§ 2.3.3 线性链表的面向对象实现
? (八 )一般的 Get/Set操作 (1)
template <class TElem>
TElem &TLinearListLink< TElem>::Get(long idx)
{
return Get(GetNode(idx));
//Throw the same exception as GetNode if idx is illegal;
}
92
§ 2.3.3 线性链表的面向对象实现
? (八 )一般的 Get/Set操作 (2)
template <class TElem>
TElem *TLinearListLink< TElem>::GetAddress(long idx)
{
TLinkNode<TElem> *p;
p= GetNode(idx);
//Throw the same exception as GetNode if idx is illega;
return &(p->info);
}
93
§ 2.3.3 线性链表的面向对象实现
? (八 )一般的 Get/Set操作 (3)
template <class TElem>
TElem *TLinearListLink< TElem>::Set(long idx,TElem
&elem)
{
TLinkNode<TElem> *p;
p= GetNode(idx);
//Throw the same exception as GetNode if idx is illegal;
p->info = elem;
//Assume that the TElem support operator "="
return &(p->info);
}
94
§ 2.3.3 线性链表的面向对象实现
? (九 )一般的前驱 /后继操作 (1)
template <class TElem>
TElem *TLinearListLink< TElem>::Prior(long idx)
{
TLinkNode<TElem> *p;
p= GetNode(idx-1);
//Throw the same exception as GetNode if idx is illegal;
return &(p->info);
}
95
§ 2.3.3 线性链表的面向对象实现
? (九 )一般的前驱 /后继操作 (2)
template <class TElem>
TElem *TLinearListLink< TElem>::Next(long idx)
{
TLinkNode<TElem> *p;
p= GetNode(idx+1);
//Throw the same exception as GetNode if idx is illegal;
return &(p->info);
}
96
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (1)
template <class TElem>
long TLinearListLink< TElem>::Locate(TElem &elem,long sn)
{
TLinkNode<TElem> *p;
long k,i,j,j0;
k=sn;
if (k<0) k = CountElem(elem)+sn+1;
if (k<0 )
throw TExcepLinearList(2);
97
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (1)
p=head;
i=0; j=0;j0=0;
while (p!=NULL)
{
if (p->info==elem)
{
i++;
j0=j;
if (k==i) break;
}
p=p->next;
j++;
}
if (j0<=0) throw TExcepLinearList(3); //Not found
else return j0; //Found,but sn is larger than the index of the last found element
}
98
§ 2.3.3 线性链表的面向对象实现
?(十 )一般的定位操作 (2)
template <class TElem>
long TLinearListLink< TElem>::Locate(TElem &elem,long
*foundElemIndex)
{
TLinkNode<TElem> *p;
long i,j;
p=head;
i=0; j=0;
99
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (2)
while (p!=NULL)
{
if (p->info==elem)
{
foundElemIndex[i]=j;
i++;
}
j++;
p=p->next;
}
if (i<=0) throw TExcepLinearList(3); //Not found
return i;
}
100
§ 2.3.3 线性链表的面向对象实现
?(十 )一般的定位操作 (3)
template <class TElem>
long TLinearListLink< TElem>::LocateFirst(TElem &elem)
{
TLinkNode<TElem> *p;
int k;
k=0;
p=head;
101
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (3)
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited = p;
lastVisitedIndex =k;
break;
}
k++;
p=p->next;
}
if (p==NULL) return -1; //Not found
else return k; //Found
}
102
§ 2.3.3 线性链表的面向对象实现
?(十 )一般的定位操作 (4)
template <class TElem>
long TLinearListLink< TElem>::LocateNext(TElem &elem)
{
TLinkNode<TElem> *p;
int k;
k=0;
p=lastVisited;
103
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (4)
while (p!=NULL)
{
if (p->info==elem)
{
lastVisited = p;
lastVisitedIndex+=k;
break;
}
k++;
p=p->next;
}
if (p==NULL) return -1; //Not found
else return k; //Found
}
104
§ 2.3.3 线性链表的面向对象实现
? (十 )一般的定位操作 (5)
template <class TElem>
longTLinearListLink< TElem>::CountElem(TElem &elem)
{
TLinkNode<TElem> *p;
long cnt;
cnt=0;
p=head;
while (p!=NULL)
{
if (p->info == elem) cnt++;
p=p->next;
}
return cnt;
}
105
§ 2.3.3 线性链表的面向对象实现
?(十一 )一般的插入 /删除操作 (1)
template <class TElem>
TElem *TLinearListLink< TElem>::Insert(TElem &elem,long sn)
{
TLinkNode<TElem> *p;
p = new TLinkNode<TElem>;
if (p==NULL) throw TExcepLinearList(4);
SetNodeElem(p,elem);
Insert(p,sn);
return &elem;
}
106
§ 2.3.3 线性链表的面向对象实现
?(十一 )一般的插入 /删除操作 (2)
template <class TElem>
TElem *TLinearListLink< TElem>::Delete(long sn)
{
TLinkNode<TElem> *p;
long k;
if (sn<0) k=len+sn;
else k=sn-1;
107
§ 2.3.3 线性链表的面向对象实现
? (十一 )一般的插入 /删除操作 (2)
if (k<1)
{
p = head;
head = head->next;
len--;
}
else
{
p=GetNode(k-1); //throw a exception if "k" is not in range
p=DeleteAfter(p);
}
buffElem = p->info;
delete p;
return &buffElem;
}
108
§ 2.3.3 线性链表的面向对象实现
?(十一 )一般的插入 /删除操作 (3,4)
Delete(TIndexSelector &sel,TElem *elemDeleted)
该操作的实现留作练习。
DeleteByIndex(long *idxTobeDel,long numIdx,TElem
*elemDeleted)
该操作的实现留作练习。
109
§ 2.4 线性表程序清单
? 见书
110
§ 2.5 几种特殊线性链表
? 头结点
在线性链表的第一个结点的前面增设一个特殊的
结点
? 作用
– 存贮一些有关线性表的信息
– 为了算法处理上的方便
? 增设头指针后，链表的头指针指向头结点，而头结点
才指向第一个元素结点
? 空表时仍含有头结点
§ 2.5.1 带头结点的链表
111
§ 2.5.2 循环链表
? 循环线性表
将第 1 个结点视为最后一个结点的后继，将最后
一个结点视为第 1个结点的前趋
? 相应的链表称循环线性链表（简称 循环链表 ）
?
… …
图 -循环链表
112
§ 2.5.2 循环链表
? 使用循环链表的主要目的是使链表中各结点处
于, 平等, 地位
? 循环链表多半带头结点，构成带头结点的循环
链表
? 最后一个结点的特征是，它的 next等于第一个
结点的指针
113
§ 2.5.2 循环链表
? 对不带头结点的循环链表，扫描一般的模式为：
p = head;
if (p!=NULL) //查找链表是否为空
{ while (p->next!=head)
{
… … //访问结点
p = p->next;
}
… … //这里要访问最后一个结点 p;
}
114
§ 2.5.2 循环链表
? 对带头结点的循环链表，扫描一般的模式为：
p = head->next;
while (p!=head) //空链表时, 仍然有一个结点
(head,其不空 ),但它的 next直接
//指向自己, 故此时该循环条件不满足 。
{
//访问结点
p = p->next;
}
115
§ 2.5.3 双向链表
? 双向链表
单向链表的每个结点增设一个指向相应结
点前趋的指针，使其同时包含前驱和后继两个
链
info----存放元素内容；
next----存放该元素的后继的指针 （ 地址 ） ；
prior----存放该元素的前驱的指针 （ 地址 ） ；
prior info next
116
§ 2.5.3 双向链表
? 双链表的插入
在结点 p之前插入结点 q,其程序片段如下 。
(1) q->next=p;
(2) q->prior=p->prior;
(3) p->prior->next=q;
(4) p->prior=q;
(4)(3)
(2) (1)
q
pp->prior p->next
图 -双链表插入
117
§ 2.5.3 双向链表
? 双链表删除
现设删除结点 p所指结点, 程序片段如下 。
(1) p->prior->next=p->next;
(2) p->next->prior=p->prior;
(3) return p;
(2)
(1)
pp->prior p->next
图 - 双链表的删除
118
§ 2.6 线性表应用示例
? 集合结构，一般可用线性表表示
? 可以模仿线性表设置一个集合类
? 只从算法角度介绍一种集合运算
(A-B)∪ (B-A)
的实现
? 将 (A-B)∪ (B-A)的结果存储在 A中,B保持不变
? 实现策略
对Ｂ中每个元素，检查其在 A中是否出现，若是，从Ａ中删除
之，否则将之加到 A中
§ 2.6.1 集合运算
119
long DiDiff(TLinearListSqu<long> &a,TLinearListSqu<long> &b)
{
long i,j,k;
j=0;
for (i=0; i<b.len; i++)
{
k = a.Locate(b.Get(i),1);
if (k >= 0 )
{a.Delete(k+1); j++;}
else a.Insert(b.Get(i),1);
}
return j;
}
120
§ 2.6.2 一元多项式相加
? (一 ) 一元多项式的表示 ── 数据结构
? 一元多项式
Pn(x)=p0+p1x+p2x2+…+p nxn
? 可用一个线性表 P来表示：
P=(p0,p1,…,pn)
其中,pi代表 Pn(x)中的 i次项系数
? Qm(x)是另一个 m次一元多项式
Q=(q0,q1,…,Q m)
? 设 m<n，则两个多项式相加结果 Rn(x)=Pn(x)+Qm(x)仍为一个一元 n
次多项式
R=(p0+q0,p1+q1,…,p m+qm,pm+1,…,p n)
121
§ 2.6.2 一元多项式相加
? (二 )多项式加法实现 —直接操作链表
? 采用带头结点的非循环链表
P5(x)=7+3x-9x3+x5
7 0 3 1 -9 3 1 5 ^
图 - 一个一元 5次多项式的链表表示
122
§ 2.6.2 一元多项式相加
? (二 )多项式加法实现 —直接操作链表
? A(x)+B(x)→A(x) 的实现方法
? 重复进行下列几个步骤
1,若 p→exp<q→exp, p后移一步, q不动 。
2,若 p→exp>q→exp,将 q插入到 A(x)中 p之前, 然后 q向后移一步,
p不动 。
3,若 p→ exp==q→ exp：将 q的系数加到 p的系数上, 若相加结果为 0，
从 A(x)中删除 p,从 B(x)中删除 q,并令 p与 q分别指向下一结点 。
若相加和不为 0,p后移一步, 然后将 q从 B(x)中摘除, 令 p指向
下一结点 。
设两个指针 p和 q，初始时它们分别指向
A(x)与 B(x)中当前未被处理的（未被加
入到和式中的）结点中指数最小者
123
? (二 )多项式加法实现 —直接操作链表
? 算法的伪码
p=A的第一个元素；
q=B的第一个元素；
while (p存在 && q存在 )
{
if (p的指数 < q的指数 )
{ p0 = p; p = p->next; }
else if (p的指数 > q的指数 )
{
将 q插入到 p之前；
令 p0指向插入后的 q,即 p的当前前驱 ;
令 q指向它原所指的下一个结点；
}
else
{
x = p的系数 + q的系数之和；
124
if (x==0)
{
删除 p;
使 p指向它原指结点的下一个；
}
else
{
令 p的系数为 x;
使 p指向它原指结点的下一个；
}
删除 q;
使 q指向它原指结点的下一个；
} // if (p的指数 > q的指数 ) … else
} //while
if (q不为空 ) 将 q挂接在 p之后；
125
? 完整的程序 (假定链表为, 带头结点, )
int PolynomialAdd(TLinearListLink<TPolynomialItem> &a,
TLinearListLink<TPolynomialItem> &b)
{
TLinkNode<TPolynomialItem> *p,*p0,*q,*q0;
float x;
longk;
k=0;
p = a.head->next;
p0 = a.head;
q = b.head->next;
126
while (p!=NULL && q!=NULL)
{
if (p->exp < q->exp)
{ p0 = p; //永远使 p0保持为 p的前驱, 以方便对在 p前插入, 或删除 p
p = p->next;
k++;
}
else
if (p->exp > q->exp )
{
q0 = q; //在下面用 q0操作原 q
q = q->next; //q先行一步
q0->next = p;
p0->next = q0; // 以上两句, 将 q0插入到 p0之后 （ 即 p之前 ）
k++;
}
127
else
{
x = p->coef + q->coef;
if (x==0)
{
p0->next = p->next;
delete p; //以上两句, 将 p从表中删除并将其所指对象释放
p = p0->next; //令 p指向相对于它原指的下一个
} // if (x==0)
else
{
p->coef = x;
p0 = p;
p = p->next; k++;
} // if (x==0) … else …
128
q0 = q;
q = q->next;
delete q0; //将 q所指结点从表中删除并释放, 令 q新指向原所指的下
一个
} // if (p->exp > q->exp ) … else …
} //while
if (q!=NULL) p0->next = q;
While (q!=NULL) {k++; q=q->next; }
b.head->next = NULL; //此时, b中已只剩第一个结点 （ 头 ）, 为其置
空表标志
return k; //返回结果链表中的元素个数
}
129
? 程序运行例子
7 0 3 2 -9 3 1 5 ^
（ a） A(x)= P5(x)=7+3x2-9x3+x5
进入循环前
p
3 1 9 3 1 5 -1 8 ^
（ b） B(x)=3x+9x3+x5-x8
进入循环前
q
130
7 0 3 2 -9 3 1 5 ^
（ c） A(x):第 1次循环后
p后移
p
3 1 9 3 1 5 -1 8 ^
（ d） B(x)：第 1次循环后
q保持不变
q
131
9 3 1 5 -1 8 ^
（ f） B(x)：第 2次循环后
q被插入到 p之前,q新指向下一个
q
7 0 3 2 -9 3 1 5 ^
（ e） A(x):第 2次循环后
q被插入到 p前
p
3 1
132
9 3 1 5 -1 8 ^
（ h） B(x)：第 3次循环后
q保持
q
7 0 3 2 -9 3 1 5 ^
（ g） A(x):第 3次循环后
p后移
p
3 1
133
7 0 3 2 1 5 ^
（ i） A(x):第 4次循环后
p被删除，新指向下一个
p
3 1
9 3 1 5 -1 8 ^
（ j） B(x)：第 4次循环后
q被删除，新指向下一个
q
134
7 0 3 2 2 5 ^
（ k） A(x):第 5次循环后
p与 p合并,p新指向下一个（空）
p
3 1
9 3 1 5 -1 8 ^
（ l） B(x)：第 5次循环后
q合并到 p，然后被删除，新指向下一个
q
135
7 0 3 2 2 5 ^
（ m） A(x):退出循环后
p后面的挂接到了 p的前驱的尾
p0
-1 8 ^3 1
9 3 1 5
（ n） B(x)：退出循环后
q挂到了 p的前驱后面
图 -多项式链表相加
136
? (三 )多项式加法实现 —借助抽象操作
struct TPolynomialItem
{
float coef;
int exp;
operator ==(TPolynomialItem&i1)
{
return (coef == i1.coef && exp==i1.exp);
};
TPolynomialItem& operator =(TPolynomialItem &i1)
{
this->coef = i1.coef;
this->exp = i1.exp;
return i1;
};
} ;
137
? (三 )多项式加法实现 —借助抽象操作
ostream& operator << (ostream& oo,TPolynomialItem &i1)
{
oo<<i1.coef<<","<<i1.exp<<" ";
return oo;
}
138
? (三 )多项式加法实现 —借助抽象操作
? 多项式加法程序
long PolynomialAdd(TLinearListSqu<TPolynomialItem>
&a,TLinearListSqu<TPolynomialItem> &b)
{
long currE1,currE2,k;
TPolynomialItem e1,e2;
k=0;
currE1=0;
currE2=0;
139
while (currE1 <a.len && currE2<b.len)
{
e1=a.Get(currE1);
e2=b.Get(currE2);
if (e1.exp < e2.exp)
{ currE1++; k++; }
else
if (e1.exp > e2.exp)
{ a.Insert(e2,currE1+1);
currE1++;
b.Delete(currE2+1);
k++;
}
140
else
{
e1.coef = e1.coef + e2.coef;
if (e1.coef==0)
a.Delete(currE1+1);
else
{a.Set(currE1,e1);
currE1++;
k++;
}
b.Delete(currE2+1);
}
}
if (currE2 < b.len)
for (int i = currE2+1; i<b.len+1; i++,k++)
a.Insert(*(b.Delete(i)),a.len+1);
return k;
}
141
§ 2.6.3 一元多项式的乘法
? 设 Am(x)与 Bn(x)为两个一元多项式, 设
Am(x) = Bn(x) =
? 则
Am(x)·Bn(x)= Bn(x)
=
? 两个一元多项式相乘, 可以化为多个一元多项式相加
?
?
m
i
e
i
ixa
1
?
?
n
i
p
i ixa
1
?
?
m
i
e
i ixa
1
?
?
m
i
e
ni
ixxBa
1
))((
142
习题
2.1编写程序, 实现在有序表 （ 表中元素按元素关键字大
小排序 ） 中插入一个元素, 使原有序表保持有序 。
分别假定有序表是连续存贮结构和链式存贮结构 。
2.2编定实现合并两个有序表, 使得合并结果仍为有序表
的程序 。 分别假定有序表按顺序方式存贮和链接方
式存贮 。
2.3 完善讲义给出的 TindexSelector类 。
2.4假定用线性表表示集合, 请定义相应的集合类, 实现
集合的各种基本运算 （ 交, 并, 差等 ） 及判别成员,
求子集, 查找元素等操作 。
2.5编写一个通过终端交互建立链表 （ 动态或静态 ） 的程
序, 使得较先输入的结点放在链表较前的位置 。
143
习题 (续 )
2.6写一个单链表倒链程序, 即将单链表中每个结点的
前趋与后继关系颠倒 。
2.7写一个建立双向链表的程序 （ 分别针对动态与静态
两种链表 ） 。
2.8分别针对动态与连续存贮结构, 编写程序实现
Josephus问题：设有 n个人围坐在一个圆桌周围, 从
第 s个人开始扳数, 数到第 m的人就出列, 然后从出
列者的下一个人开始重新按上述方式扳数, 出列,
如此重复, 直到所有的人全部出列好止 。 要求的结
果是, 给出每个人的出列次序 （ 给定 n,对任意合
法的 s与 m） （ 即求一个按出列次序排列的 n个人的
顺序表 。
2.9编写一个一元 n次多项式的化简程序 （ 即将多项式
内的同类项合并, 0系数项去除, 并使各项按指数
升序排列 ） 。
144
习题 (续 )
2.10假定一元 n次多项式用连续存贮结构的线性表表
示 （ 不含 0系数项 ）, 编写两多项式相加的程序 。
2.11写一个实现两一元 n次多项式相乘的程序 。
2.12实现 Delete(TindexSelector &sel)
2.13 在类 TLinearListSqu或 TlinearListLink基础上, 实
现 Copy,Merge,Sort等操作 。
2.14 直接利用 TlinearListLink实现多项式加法 。
2.15 在类 TLinearListSqu或 TlinearListLink基础上, 实
现一个学生基本信息登记表的操作, 包括, 输入,
修改, 打印, 查询, 统计等功能 。
