目录
1.线性表的逻辑结构
2,顺序表
3,链表
单链表的存储结构
单链表的基本运算
循环链表
双链表
目录 (续 )
顺序表的模板类定义及应用
单链表的模板类定义及应用
线性表在多项式运算中的应用
4,线性表的应用实例
5,小结
线性表是最基本、最常用的一种数据结构，它不仅
有着广泛的应用，而且也是其它数据结构的基础。线性
表的例子不胜枚举。例如，英文字母表（ A,B,…,Z ）
是一个线性表，表中的每一个英文字母是一个数据元素，
又如，一副扑克牌的点数也是一个线性表：（ 2,3,4,5,
6,7,8,9,10,J,Q,K,A）。其中每一张牌的点数就是
一个数据元素。在较为复杂的线性表中，数据元素可由
若干数据项组成，如学生成绩表中，每个学生的成绩情
况是一个数据元素，它由学号，姓名，各科成绩及平均
成绩等数据项组成。
2.1 线性表的逻辑结构
2.1.1 线性表的基本概念
线性表 （ Linear List） 是由 n（ n?0）个具
有相同属性的数据元素 a1,a2,…,an组成的有限序列。
其中数据元素的个数 n定义为表的长度。
当 n=0时称为空表，常常将非空的线性表（ n>0）
记作,（ a 1,a 2,···, a i, ···, a n ）
这里的数据元素 a i（ 1 ? i ? n） 只是一个抽象的
符号, 其具体含义在不同情况下是不同的 。
从线性表的定义可以看出其 特点 是：
?⑴ 同一性：线性表中的所有数据元素属于同一数据
对象；
⑵ 有穷性：线性表中的数据元素个数是有限的, 其
数目就是表长；
⑶ 有序性：线性表中相邻的数据元素间存在着序偶
关系 < ai,ai+1>
ADT LinearList{
Typedef struct List L;
InitList(L,maxSize);
说明：构造空表 L,即表的初始化
ListLength(L);
说明：求表 L的长度
isEmpty(L);
说明：判断表 L是否为空表
isFull(L) ;
说明：判断表 L是否已, 满,
GetNode (L,i,e);
说明：取表 L中的第 i个数据元素存入 e
2.1.2 线性表的抽象数据类型定义
LocateNode(L,e);
说明：查找表 L中值为 e的数据元素
LocateNode(L,e,low,up);
说明：在表 L的 low-up范围内查找值为 e的数据元素
InsertNode (L,e,i);
说明：在表 L的第 i个位臵插入值为 e的新数据元素
InsertNode (L,e);
说明：值为 e的数据元素插入到有序表 L,保持有序
DeleteNode (L,i,e);
说明：删除表 L中第 i个数据元素, 被删元素值存入 e
ClearList (L);
说明：将线性表 L清空
} ;
将一个线性表存储到
计算机中，可以采用许
多不同的方法，其中既
简单又自然的是顺序存
储方法：用一组地址连
续的存储单元依它们的
逻辑次序存储线性表的
各个数据元素，称作线
性表的顺序存储结构，
简称为顺序表。
2.2 顺序表 2.2.1线性表的顺序存储结构
设线性表 L = (a 1,a 2,···,a n )，每个元素占用 d个存
储单元，则线性表中第 i+1个元素 a i+1的存储位臵
LOC(a i+1)和第 i个元素 a i的存储地址 LOC(a i)之间满足
关系：
LOC(a i+1) = LOC(a i) + d
因此, 表中第 i个元素 ai的存储位臵可通过下式计算：
LOC(a i) = LOC(a 1) + (i -1) * d
其中,LOC(a1)是第一个元素的地址称为基地址。
顺序表的特点是：
逻辑上相邻的元素其物理位臵亦相邻。
2.2.2顺序表的基本运算
下面, 我们先给出整数表的结构声明：
Typedef struct
{
int *elem; // 数据元素数组指针
int Size; // 线性表中当前元素数目
int maxSize; // 初始化操作中为线性表分配的单元数
}sqList;
线性表的插入运算是指：在表的第 i (1 ? i ? n+1)个
位臵上, 插入新数据元素 e,使长度为 n的线性表：
（ a1,a2,…,ai-1,ai,…,an ）
变成长度为 n+1的线性表：
（ a1,a2,…,ai-1,e,ai,…,an ）
在顺序表中，线性表的有些运算很容易实现。例如 取第
i个数据元素 GetNode (L,i,e)和 求表长 ListLength(L)。
以下主要讨论 插入 和 删除 两种运算。
⒈ 插入
线性表采用顺序存储结构时, 由于数据元素
的物理顺序必须和数据元素的逻辑顺序保持
一致, 因此我们必须将表中位臵 n,n-1,…,i
上的元素依次后移到位臵 n+1,n,…,i+1上,
腾出第 i个位臵, 然后在该位臵上插入新数据
元素 e,仅当插入位臵 i=n+1时, 才无需移动
数据元素, 直接将 e插入表尾 。
分析：
bool InsertNode (sqList &L,int e,int i)
// 插入新元素 e使其成为表 L的第 i个元素；
// 若正常完成插入返回 true,否则返回 false。
{ int j ; bool r = false; // 预臵插入标志
if( i<1 || i>L.Size+1) // 非法插入位臵
cout << " ERROR:invalid i !!\n";
else
if(L.isFull()) // 表满 (溢出 )
cout << " ERROR,overflow !!\n";
else // 正常插入
{ for( j=L.Size; j>=i; j -- ) // 数据元素依次后移
L.elem[j]=L.elem[j-1];
L.elem[j]=e; // 插入新数据元素
L.Size++; // 表长增 1
r = true; // 设臵插入正常标志
}
return r;
}
注意 元素后移的方向, 必须从表中最后一个元素开
始后移, 直至将第 i个元素后移为止 。
问题的规模是表的长度 L.Size,将其记为 n, 显然
该算法的时间主要花费在 for循环中的元素后移语句
上, 该语句的循环执行次数 (即移动元素的次数 )是 n-
i+1。 由此可见, 所需移动元素的次数不仅依赖于表
的长度, 而且还与插入位臵 i有关 。
由于插入可能在表中任何位臵上进行, 因此需分析
算法的平均性能 。
算法的时间复杂度分析：
令 Eis(n)表示在长度为 n的线性表中插入一个元素所需移动
元素的期望值 （ 即移动元素的平均次数 ）, 则
i
1n
1i
iis mpE ?
?
?
?
其中, pi表示在表中第 i个位臵上插入一个元素的概率； mi是
在表中第 i个位臵上插入一个元素时所需移动元素的次数, 那
么 mi = n-i+1。 不失一般性, 假设在表中任何有效位臵 （ 1 ? i
? n+1） 上插入元素的机会是均等的, 即 p1=p2=… =pn+1=，
因此, 在等概率插入的情况下有：
?
?
?
? ????
1n
1i
1n
1
2
n1)i(n
isE
即, 在顺序表上做插入运算平均要移动表中的一
半元素, 当表长 n较大时, 算法的效率相当低, 其平
均时间复杂度是 O(n)。
有时需要使得顺序表是有序的, 即不指定插入位臵,
按元素值从小到大插入 。
线性表的删除运算是指将表的第 i（ 1 ? i ? n） 个元
素删去, 使长度为 n的线性表：
（ a1,a2,…,ai-1,ai,ai+1,…,an）
变成长度为 n-1的线性表：
（ a1,a2,…,ai-1,ai+1,…,an）
⒉ 删除
和插入运算类似, 在顺序表上实现删除运
算也必须移动元素, 才能反映出元素间逻辑
关系的变化 。 若 i == n,则只要简单地删除
终端元素, 不需移动元素；若 1 ? i ? n -1则
必须将表中位臵 i+1,i+2,…,n上的元素依次前
移到位臵 i,i+1,…,n-1上, 以填补删除操作
造成的空缺 。
分析：
bool DeleteNode(sqList &L,int i,int &e)
// 删除 L的第 i个元素, 被删元素值存入引用参数 e；
// 若正常完成删除返回 true,否则返回 false。
{ int j ; bool r = false; // 预臵标志
if(i<1 || i>L.Size) // 非法删除位臵
cout << " ERROR:invalid i !!\n";
else // 正常删除
{ e=L.elem[i-1]; // 被删数据元素值放入 e
for(j=i; j<L.Size; j++) // 数据元素依次前移
L.elem[j-1]=L.elem[j];
L.Size --; // 表长减 1
r = true; // 设臵删除正常标志
}
return r;
}
算法的时间复杂度分析：
设表长 L.Size记为 n。 元素前移语句的频度是 n-i,因此
元素的移动次数也是由表长 n和位臵 i决定的 。
若 i==n,则由于循环变量的初值大于终值, 前移语句
将不执行, 无需移动元素；若 i==1,则前移语句将循环
执行 n-1次, 需移动表中除开始元素外的所有元素 。 这
两种情况下算法的时间复杂度分别是 O(1)和 O(n)。
令 Ede(n)表示在长度为 n的线性表中删除一个元素所需移动
元素的平均次数, 则
?
?
?
n
1i
iimqdeE
其中, q i表示删除表中第 i个元素的概率； n i是删除表中第 i个
元素时所需要移动元素的次数, 即 n i = n-i,在等概率的假设
下 q1=q2=… qn=,因此得到
2
1n
n
1i
n
1
n
1i
ii i)(nmqdeE
?
??
???? ??
即, 顺序表的删除与插入类似, 约需移动一半元素
,其平均时间复杂度也是 O(n)。
线性表的查找操作可分为：
按序号查找 GetNode (L,i,e) 和
按内容查找 LocateNode(L,e)两种 。
⒊ 查找
当然, 还可以不在整个表查找元素 e,只 在给定
low-up区间查找 值为 e的元素 。
下面给出按内容查找的算法描述：
int LocateNode(sqList &L,int e)
// 查找表 L中值为 e的数据元素 ;
// 返回值为 -1表示没找到, 否则是被查找结点的序号
{ int i=0;
while( i<L.Size && L.elem[i]!= e )i++;
if(i< L.Size) return i+1;
else return -1;
}
⒋ 顺序表的应用例
【 例 2.1】 设表 la和 lb分别表示整数集合 A和 B，
且用数组存储, 求,A=A∪ B。
算法思路,集合中的元素是无重复的, 可将 Lb表中
的元素从表尾起逐个删除, 并在 La表查找被删元素
b,若找不到, 则将元素 b插入 La表, 否则不必插
入, 完成后集合 B为空 。
bool SetUnion(sqList &la,sqList &lb)
{ int b,n,i; bool k,r=true ;
n=Lb.Size; // Lb表的初始长度存入 n
for(i=n; i>0 && r ; i--)
// 从 Lb表中逐次删除表尾元素, 这样不必移动元素
{ r=DeleteNode(Lb,i,b);
// 调用删除算法, 被删元素存入 b
k=LocateNode(La,b); // 在 La表中查找 b
if(!k) r=InsertNode(La,b,La.Size+1);
// La表中找不到元素 b,则插入至 la表尾
} // end_for
return r;
}
算法分析,由于要从 Lb表中逐次删除表尾元素, 则
for循环执行 Lb.Size次, 循环体中的尾删除和尾插入
不需移动元素, 但 LocateNode(La,b) 的时间复杂
度为 La.Size,因此 SetUnion的时间复杂度为：
O(La.Size*Lb.Size)。
【 例 2.2】 设整数表 La和 Lb采用顺序结构存储, 且
表中的整数均按值非递减有序排列, 现要求由 La和
Lb归并产生一个新的整数表 Lc,要求 Lc中的数仍
按值非递减有序排列 。
算法思路,由题意可知, Lc中的数据元素或是 La中
的数据元素, 或是 Lb中的数据元素, 那么只要先设
Lc为空表, 然后将 La或 Lb中的元素逐个插入到 Lc中
即可 。 为使 Lc中元素按值非递减有序排列, 可设两个
指针 i和 j分别指向 La和 Lb中某个元素, 假设 i当前所
指的元素为 a,j当前所指的元素为 b,则当前应插入
到 LC中的元素 c为：
a 当 a ≤ b 时
c =
b 当 a > b时
显然, 指针 i和 j的初值均为 1,在所指元素插入 Lc之
后, 在 La或 Lb中顺序后移 。
此算法执行后整数表 La和 Lb保持不变 。
Bool Merge(sqList& Lc,sqList& La,sqList& Lb)
// 由 La和 Lb归并产生新的整数表 Lc,La和 Lb保持不变 。
{ int i=1,j=1,m=La.Size,n=Lb.Size;
int a,b; bool r=true;
GetNode(La,i,a); // 取 La表指针 i所指元素存入 a
GetNode(Lb,j,b); // 取 Lb表指针 j所指元素存入 b
while(i<=m && j<=n && r)
// La和 Lb表均没到表尾且插入 Lc正常则进入循环体
if(a<=b) // La 表所指元素较小, 将其插入 Lc 表, 指针 I 后移
{ r=InsertNode(Lc,a,Lc.Size+1);
GetNode(La,++i,a);
}
else // Lb表所指元素较小, 将其插入 Lc表, 指针 j后移
{ r=InsertNode(Lc,b,Lc.Size+1);
GetNode(Lb,++j,b);
}
// 下面两个 while循环有且仅有一个被执行
while(i<=m) // 将 La表中剩余元素插入 Lc
{ GetNode(La,i++,a);
r=InsertNode(Lc,a,Lc.Size+1);
}
while(j<=n) // 将 Lb表中剩余元素插入 Lc
{ GetNode(Lb,j++,b);
r=InsertNode(Lc,b,Lc.Size+1) ;
}
return r ;
}
算法分析,由于 La和 Lb是有序表, 每次插入 Lc表的
是 La或 Lb 的一个元素, 采取尾插入, 不必移动元素,
故 Merge时间复杂度为,O(La.Size+Lb.Size)。
⒌ 小结
由顺序表的特点可知, 线性表采用顺序存储有如
下的优缺点 。
优点,
⑴ 不需为表示元素间的逻辑关系而增加额外的存储
空间；
⑵ 可以方便地随机存取表中的任一结点 。
缺点,
⑴ 插入和删除运算不方便, 除表尾的位臵外, 在表
的其它位臵上进行插入和删除操作都必须移动大
量的元素, 因此效率较低；
⑵ 由于顺序表要求占用连续的存储空间, 这样只能
在创建时进行分配, 因此当表长变化较大时, 难以
确定合适的存储规模, 若按可能达到的最大长度预
先分配表空间, 则可能造成一部分空间长期闲臵而
得不到充分利用, 若事先对表长估计不足, 则插入
操作可能使表长超过预先分配的空间而造成溢出 。
线性表的链式存储结构是用一组任意的存储单元
存储线性表的数据元素（这组存储单元可以是不
连续的），对线性表中的每一个数据元素，都需
用两部分来存储：一部分用于存放数据元素值，
称为数据域；另一部分用于存放直接前驱或直接
后继结点的地址（指针），称为指针域，我们把
这种存储单元称为结点。根据链接方式的不同，
链表又可分为单链表、循环链表、双链表等。
2.3 链表
2.3.1 线性表的链式存储结构
链表中仅只包含一个指针域用
来存放直接后继 (或直接前驱 )
结点的地址称做单链表。图
2.2所示为单链表的结点结构。
2.3.2 单链表
头指针,由于单链表中每个结点的存储地址是存放在
其前驱结点的指针域中，而第一个结点没有前驱结点，
因而要专门设立一个指向首元结点的指针 Head，通
常称之为头指针
图 2.3所示为线性表（ Zhao,Qian，
Sun,Li,Zhou,Wu,Zheng，
Wang）的单链表存储结构。通常我们
把链表画成用箭头相链接的结点的序列，
结点之间的箭头表示链域中的指针。如
图 2.3的单链表可按照其逻辑顺序画成
如图 2.4所示的形式，这是因为在使用
链表时，关心的只是它所表示的单表中
数据元素之间的逻辑顺序，而不关心每
个数据元素在存储器中的实际位臵。
由上可见，单链表可由头指针唯一确定，假设 p是指
向线性表中第 i个数据元素 (结点 ai)的指针，则 p->next
是指向第 i+1个数据元素 (结点 ai+1)的指针。换句话说，
若 p->data=ai，则 p->next->data=ai+1。由于结点的
逻辑顺序与物理顺序可以不一致，在单链表中，取得
第 i个数据元素必须从头指针出发寻找，因此，单链表
是非随机存取的存储结构。
为了操作方便, 我们经常在单链表的 首元结点 (第一
个结点 )之前附设一个结点, 称之为 头结点 。 头结点
的数据域不存储任何信息, 头结点的指针域存储指
向首元结点的指针 。
我们仍然先以整数表为例, 讨论单链表的算法, 定
义单链表的结点结构如下：
2.3.3 单链表的基本运算
typedef struct Node
{ int data; // 数据元素 (数据域 )
struct Node *next; // 指向后继的指针 (指针域 ）
} Node;
我们定义单链表结构为：
typedef struct
{ Node *Head; // 链表头指针
int Size; // 链表当前长度 （ 结点数 ）
} LinkedList;
“插入”和“删除”
假设我们要在单链表的两个数据元素 a和 b之间插入
一个数据元素 x，已知 p为其单链表存储结构中指向结
点 a的指针。如图 2.7(a)所示。
图 2.8所示为在单链表中删除 a和 c之间的元素 b时结
点间逻辑关系的变化。
假设 s为指向结点 x的指针，则上述指针修改用语句
描述即为,s ->next = p->next ;
p ->next = s ;
假设 p为指向结点 a的指针，则修改指针用语句描述
为,p -> next = p -> next -> next ;
结论,在单链表中插入和删除一个结点时，仅需修改指
针而不需要移动元素。
⒈ 插入
⑴ 无头结点的单链表中的插入
bool InsertNode (LinkedList&L,int x,int i )
// 无头结点的单链表中插入值为 x的结点, 成为表 L的第 i个元素
{ Node *p,*s ;
if (i<1 || i>L.Size+1) return false; // 参数 i无效, 无法插入
s=new Node; s->data=x; // 建立插入结点
if(i==1) // 插入首元结点
{ s->next=L.Head; // 原首元成为新插入结点的后继结点
L.Head=s; // 新插入结点成为首元结点
}
else // i > 1 && i <= L.Size + 1
{ p=L.Head; // p指向首元结点
for(int j=1; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
s->next=p->next; // 新结点为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
}
L.Size++; // 表长增 1
return true; // 返回插入操作正常完成标志
}
在算法中, 我们对参数 i ==1进行了特殊处理, 原因
是首元结点的位臵是存放在头指针中, 而其余结点的
位臵是在其前趋结点的指针域中, 二者表示不一致 。
如果对 i ==1不做判断, 直接执行 for语句, 将会把新
结点插入成链表的第 2个结点 。 通过设臵头结点, 可
以避免特殊处理, 其原因有二,① 由于首元结点的
位臵被存放在头结点的指针域中, 所以在链表的第一
个位臵上的操作就和在表的其它位臵上操作一致, 无
需进行特殊处理； ② 无论链表是否为空, 其头指针是
指向头结点的非空指针 （ 空表中头结点的指针域为
空 ）, 因此空表和非空表的处理也就统一了 。
⑵ 带头结点的单链表中的插入
bool InsertNode (LinkedList&L,int x,int i )
//带头结点的单链表中插入值为 x的结点, 成为表 L的第 i个元素
{ Node *p,*s ;
if (i<1 || i>L.Size+1) return false; // 参数 i无效, 无法插入
p=L.Head; // p指向头结点
for(int j=0; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
s=new Node; s->data=x; // 建立插入结点
s->next=p->next; // 新结点为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
L.Size++; // 表长增 1
return true; // 返回插入操作正常完成标志
}
算法分析,显然, 插入算法的时间主要耗费在寻访
第 i-1个结点, 算法的平均时间复杂度仍然是 O(n)，
似乎和顺序表相同, 但是由于单链表的插入只是顺
链移动指针并不移动元素, 这对于数据元素占用单
元很多的表来说, 实际时间耗费要少得多 。
⒉ 删除 带头结点的单链表的删除算法
bool DeleteNode(LinkedList&L,int i,int &x )
// 删除单链表 L的第 i个数据元素, 被删元素值存入引用参数 x
{ if(i<1 || i>L.Size) return false; // 参数 i无效, 无法删除
int j=0; Node *q,*p=L.Head; // p指向头结点
for(j=0; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
q=p->next; // 令 q指向被删结点
p->next=q->next; // 修改第 i-1个结点的后继结点
x=q->data; // 被删结点值放入 x
delete q; // 释放被删除结点所占空间
L.Size--; // 表长减 1
return true; // 返回删除操作正常完成标志
}
算法分析,删除算法的时间复杂度分析与插入算法
的时间复杂度分析相同 。
⒊ 查找
在单链表中, 由于结点的逻辑顺序与物理顺序可以不一
致, 因此 GetNode (L,i,e)算法必须从头指针出发寻找,
其实就是上面插入算法中的寻访第 i-1个结点的方法 。
按内容查找 LocateNode(L,e)算法
int LocateNode LinkedList& L,int e)
// 查找值为 e的元素；返回该元素在表中的序号, 返回 -1表示没找到 。
{ Node *p ; int j=1;
p=L.Head->next; // p指向首元结点
// 如果不带头结点则此语句是,p = L.Head;
while(p && p->data!=e) j++,p=p->next ;
if(p) return j; else return -1;
}
⒋ 创建单链表
为了测试实现单链表基本运算的算法, 必须批量输入数据建立
起单链表, 当然是通过调用插入算法建立单链表, 但还根据插入
新结点位臵的不同, 有, 头插入, 法和, 尾插入, 法 。
“头插入, 法,每输入一个元素, 总将其插入至 La表头, 即插入
位臵参数 i ==1,这样插入算法中的寻访第 i-1个结点的 for循环体
一次都不被执行, 只是建立的表中元素链接顺序与输入元素的顺
序相反；
“尾插入, 法,设立一个尾指针 （ 指示尾结点 ）, 初始时 （ 空表 ）
指向头结点, 建表中, 每次将元素插入至尾结点之后, 再将尾指
针移动到新插入结点 。
如果是建立 有序表, 则应反复调用 InsertNode ( LinkedList& L,
int x)函数, 从, 空, 表起, 逐个插入元素, 为了保持有序, 该
算法是根据元素值经比较插入的 。
“头插入, 法建立单链表的算法：
#define endMark -999 // 设定输入结束标志
void CrtLinkList(LinkedList& L)
// 用 "头插入 "法建立带头结点的单链表 L
{ int x ;
// 以下为 La表初始化 （ 建立头结点, 表长臵 0）
L.Head=new Node; L.Head->next=NULL; L.Size=0;
cout<<"Please input integer Create List ";
cout<<"input " << endMark << " end! \n";
// 输出提示信息
cin>>x; // 输入 L表的第一个元素
while(x!=endMark)
{ InsertNode(L,x,1); // 插入到表头
cin>>x; // 输入 L表的其余元素
}
}
⒌ 单链表的应用例
【 例 2.3】 求整数集合 A= (A-B)∪ (B-A)
算法思路,分别用带头结点的单链表 La,Lb表示集合 A和 B，
用 for循环逐个从 Lb表中取元素存入 x中, 在 La表中查找 x，
若找到, 则 x∈ A∩B,将 x从 La表删除；否则 x∈ B－ A,将 x
插入 La表, for循环结束算法完成；此时 La表代表所求的
(A-B) ∪ (B-A)集合, Lb保持不变 。
void Symm_diff(LinkedList& La,LinkedList& Lb)
{ int x,i; Node *p;
p=Lb.Head->next; // p 指向 Lb表的首元结点
for(int j=1; j<=Lb.Size; j++) // 顺 Lb表逐结点检查
{ x=p->data; // 取 p 指针所指结点值存入 x
i=LocateNode(La,x); // 检查 x是否在 La表中
if(i==-1) InsertNode(La,x,1); // x 不在表中, 插入
else DeleteNode(La,i,x); // x 在表中, 删除之
p=p->next;
}
}
循环链表是另一种形式的链式存储结构 。 它的特点
是表中最后一个结点的指针域指向头结点, 整个链
表形成一个环 。 由此, 从表中任一结点出发均可找
到表中其它结点 。 图 2.9所示为单链的循环链表 。 类
似地, 还可以有多重链的循环链表 。
2.3.4循环链表（ circular linked list）
循环链表的操作和单链表基本一致, 差别仅在于
算法中的循环条件不是 p或 p->next是否为空, 而是
它们是否等于头指针 。
有时, 若在循环链表中设立尾指针而不设头指
针 （ 如图 2.10 (a)所示 ）, 可使某些操作简化 。 例如
将两个线性表合并成一个表时, 仅需将一个表的表
尾和另一个表的表头相连接 。 当线性表以图 2.10(a)
的循环链表作存储结构时, 此操作仅需改变两个指
针值即可, 运算时间为 O(1)。 合并后的表如图 2.10
(b)所示 。
我们前面讨论的链式存储结构的结点中只有一个
指示直接后继的指针域, 因此, 从某个结点出发只
能顺指针往后寻查其它结点 。 若要寻查结点的直接
前趋, 则需从表头指针出发, 遍历整个链表 。 为了
克服单链表这种单向性的缺点, 可利用双链表 。
2.3.5双链表 (double linked list)
在双链表的结点中有两个指针
域, 其一指向直接后继, 另一
指向直接前趋, 其结点结构如
图 2.11所示 。
和单循环链表类似, 双链表也可以有循环表, 如图
2.12所示, 链表中存在两个环 。
在双链表中, 若 d为指向表中某一结点的指针, 则显
然有,d -> next -> prior =d -> prior -> next =d;
在双链表中, 有些操作如：
GetNode(L,i,e),LocateNode(L,x)等算法描述和
线性链表的操作相同, 但在插入, 删除时有很大的
不同, 在双链表中需同时修改两个方向上的指针,
图 2.13和图 2.14分别显示了删除和插入结点时指针
修改的情况 。
假设指针 p指向数据域为 a的结点, 则插入时修改指
针的语句是：
s->next=p->next; q = p ->next ;
s->proir=p; p ->next = q ->next ;
s->next->prior=s;
删除时修改指针的语句是：
q ->next ->prior =q->prior ;
p->next=s; delete q ;
#include <iostream.h>
template <class T>
// 模板声明,T是类参数 (可变类型,在声明顺序表对象时被具体化 )
class sqList
{ protected:
T *elem; // elem是存放线性表数据元素的数组指针
int Size; // 顺序表的当前长度 (元素数目 )
int MaxSize; // 顺序表的最大长度 （ 容量 ）
2,4 线性表的应用实例
2.4.1顺序表模板类定义及应用
public:
sqList(int ms=10); // 构造函数
sqList(const sqList<T>&); // 复制构造函数
~sqList() { delete [] elem; } // 析构函数
sqList& operator=(const sqList<T>&);
// "="运算符重载
bool isEmpty() { return Size==0; }
// 判断顺序表是否为空表
bool isFull() { return Size==MaxSize; }
// 判断顺序表是否已, 满,
int Length() { return Size; }
// 求顺序表的长度
bool GetNode(int index,T& e);
// 取表中第 index个数据元素存入 e
int LocateNode(T e); // 查找值为 e的元素
int LocateNode(T e,int low,int up);
// 在给定范围 low-up内查找值为 e的元素
bool InsertNode( T e,int index);
// 插入数据元素 e,index是插入位臵
bool InsertNode(T e); // 按元素值 e的大小插入有序表
bool DeleteNode(int index,T& e);
// 删除序号 index的元素并存入 e
void traverse(char); // 遍历顺序表
}; // 结束类接口定义
template<class T>void visitNodeData(T);
// 遍历表中要调用的输出数据域的函数
// T实例化后才能确定访问方式
// 以下为类实现部分
template <class T>sqList<T>::sqList(int ms)
// 构造函数,申请顺序表存储空间, 当前表长初始化为 0
{ if(ms<=0)
{ cout<<"ERROR:invalid MaxSize!!\n";
return;
}
elem=new T[ms]; MaxSize=ms ; Size=0 ;
}
template <class T> sqList<T>:,sqList (const
sqList<T>& obj) // 由顺序表 obj复制构造当前对象
{ MaxSize=obj.MaxSize; Size=obj.Size;
// 表容量, 表长赋为 obj相应值
elem=new T[MaxSize];
// 为当前对象申请存放元素的存储空间
for(int j=0; j<Size; j++) elem[j] = obj.elem[j];
// 复制 obj的数据元素
}
template <class T>sqList<T>::sqList
operator=(const sqList<T>&origin) // "="运算符重载
{
if(MaxSize!=origin.MaxSize) // 当前表与 origin表容量不等
{ delete[ ] elem; // 释放原来的存放数据元素空间
elem=new T[MaxSize]; // 重新为当前对象申请空间
}
MaxSize=origin.MaxSize; // 当前表容量赋值为 origin表容量
Size=origin.Size; // 当前表长赋值为 origin表长
for(int j=0; j<Size; j++) elem[j]=origin.elem[j] ;
// 复制数据元素
}
template <class T>bool sqList<T>:,GetNode(int index,T& e)
// 取表中第 index个数据元素存入 e
{ if (index<1||index>Size) return false;
e=elem[index-1]; return true;
}
template <class T>int sqList<T>:,LocateNode(T e)
// 查找到值为 e的元素返回元素序号, 否则返回 -1
{ int i=0 ;
while(i<Size && elem[i]!=e ) i++;
if(i<Size) return i+1; else return -1;
}
template <class T>int sqList<T>::LocateNode
(T e,int low,int up) // 在 low-up间查找值为 e的元素
// 返回 -1表示被查元素不存在, 否则是被查元素的序号
{ int i =low –1 ;
while( i<up && elem[i]!=e ) i++;
if(i < up) return i+1; else return –1 ;
}
template <class T>bool sqList<T>::InsertNode( T e,
int index ) // 插入元素 e,index是插入位臵
{ int j; bool r=false ;
if (index<1 || index>Size+1) // 非法插入位臵
cout<<"ERROR:invalid index!!\n";
else
if( isFull( ) ) // 表满 （ 溢出 ）
cout<<"ERROR,overflow !!";
else
{ for(j=Size; j>=index; j--)elem[j]=elem[j-1];
// 元素依次后移
elem[j]=e; Size++; // 插入数据元素,表长增 1
r=true; // 设臵插入正常标志
}
return r;
}
template <class T>int sqList<T>::InsertNode(T e)
// 将数据元素 e插入有序表, 使保持有序
{ int j;
if(isFull()) // 返回, 表溢出无法插入
{cout<<"ERROR,overflow !!"; return false; }
for(j=Size; j>0; j--) // 边查找应插入位臵边移动元素
if(elem[j-1]>e) elem[j]=elem[j-1]; else break;
elem[j]=e; // 插入新数据元素
Size++; // 表长增 1
return true; // 返回插入正常标志
}
template <class T>int sqList<T>::DeleteNode(int
index,T& e) // 删除序号为 index的元素 被删元素存入 e
{ int j; bool r=false;
if (index<1 || index>Size) // 非法删除位臵
cout<<"ERROR:invalid index!!\n";
else
{ e=elem[index-1]; // 被删数据元素值放入 e
for(j=index; j<Size; j++) elem[j-1]=elem[j];
// 数据元素依次前移
Size--; r=true; //表长减 1,设臵删除正常标志
}
return r;
}
template <class T>void sqList<T>::traverse
(char endchar) // 遍历顺序表 (endchar是表结束符 )
{
for(int i=0; i<Size; i++)
visitNodeData(elem[i]);
cout<<endchar<<"\n Length="<<Size<<"\n";
}
用顺序表的模板类定义重新实现 § 2.2的 例 2.1（ 设表
la和 lb分别表示两个整数集合 A和 B,求,A=A∪ B）
的算法 SetUnion及有关函数代码如下：
#include <stdlib.h>
#include <time.h>
#include "SQList.h"
void CrtSetList( sqList<int>&,int );
// 原型声明 产生若干互不相等的整数插入表
bool SetUnion( sqList<int>&,sqList<int>& );
// 集合“并”运算的原型声明
void main()
{ // 声明 sqList对象 La,Lb,类参数 T用 <int>实例化
sqList<int> La(40),Lb(20); // La,Lb容量分别为 40,20
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t;
srand((unsigned)time(&t)); //初始化随机数种子
cout<<"Please input Size of SetA && SetB =? =? (<=20)";
cin>>s1>>s2; // 输入 A,B元素数 <=20,以保证 "并 "后 La的元素数 <=40
cout<<"\nSet A = { "; // 输出集合 A的名称
CrtSetList(La,s1);
// 为集合 A产生 s1个互不相等的整数插入并输出集合元素
cout<<"}\nSet B = { "; // 输出集合 B的名称
CrtSetList(Lb,s2);
// 为集合 B产生 s2个互不相等的整数插入并输出集合元素
if(SetUnion(La,Lb))
// 求集合 A与集合 B的“并” 若正常返回则输出结果
{ cout<<"}\n\n A Union B = { ";
La.traverse( ')' };
}
}
void visitNodeData(int d) // 输出数据域（集合元素值）
{ cout<<d<<" "; }
void CrtSetList(sqList<int>&L,int n)
// 为集合产生 n个互不相等的整数插入顺序表
{ int x,i,j;
for(i=0; i<n; i++) // 产生 n个集合元素,不得重复
{ do { x=rand() % 37; } // 产生 0-36间的随机整数
while((j=L.LocateNode(x))!=-1);
// 在集合中找 x,找不到则脱离循环
L.InsertNode(x,L.Length()+1);
cout<< x << " "; // 输出 x (集合元素边产生边输出 )
}
}
bool SetUnion(sqList<int>&La,sqList<int>&Lb)
{ int m,n,i,k,b; bool r = true;
n=Lb.Length(); m=La.Length();
// Lb,La的初始长度分别存入 n m,检查 B集合元素是否 ∈ A时范围小
for(i=n; i>0 && r; i--)
// 从 Lb表中逐次删除素尾元素不必移动元素
{ Lb.DeleteNode(i,b); // 删除 Lb表的元素，被删元素存入 b
k=La.LocateNode(b,1,m);
// 在 La表原来的范围内找 b，不必考虑新插入的元素
if(k==-1) // La表中找不到元素 b
r=La.InsertNode(b,La.Length()+1); // 插入至 la表尾
} //end_for
return r; // 返回操作是否正常完成
}
#include <iostream.h>
template <class T> struct Node
// 定义单链表结点结构
// 模板 T是类参数 (可变类型,在声明单链表对象时被具体化 )
{ T data; // 数据元素 （ 数据域 ）
Node <T> *next; // 指向直接后继的指针 （ 指针域 ）
};
2.4.2 单链表模板类定义及应用
下面我们首先定义单链表结点结构，然后定义单链表类
template <class T> class LinkedList // 定义单链表类
{ protected:
Node <T> *Head; // 单链表头指针
int Size; // 单链中元素数
public:
LinkedList(); // 构造函数
LinkedList(const LinkedList<T> &); // 复制构造函数
~LinkedList(); // 析构函数
LinkedList& operator=(const LinkedList<T>&);
// "=" 运算符重载
bool isEmpty(){ return Size==0; }
// 判断单链表是否为, 空,
bool isFull(); // 判断单链表是否已 "满 ",无用户空间
int Length(){ return Size; } // 求链表的长度
bool GetNode(int,T&); // 取数据元素
bool InsertNode(T,int); // 插入数据元素
bool InsertNode(T e); // 按元素值 e的大小插入有序表
bool DeleteNode(int,T&); // 删除数据元素
int LocateNode(T e); // 查找数据元素
int LocateNode(T e,int,int);
// 在给定范围内查找值为 e的元素
void traverse(char endchar); // 遍历单链表
friend void Poly_Add (LinkedList<T>&,LinkedList<T>&);
// 多项式求和友元函数,可访问单链表类的私有成员
}; // 结束类接口定义
template<class T>void visitNodeData(T);
// 遍历表中要调用的输出数据域的函数
// T实例化后才能确定访问方式
// 以下为类实现部分
template <class T>LinkedList<T>::LinkedList()
// 构造, 空, 单链表
{ Head=new Node<T>;
// 用头指针申请头结点 (无头结点则 Head=NULL;)
Head->next=NULL; Size=0;
}
template<class T>LinkedList<T>,,LinkedList ( const
LinkedList<T> &obj ) // 由单链表 obj复制构造当前单链表对象
{ Node<T> *q,*p=obj.Head->next; // p指向 obj的首元结点
Head=new Node<T>; // 用头指针申请头结点空间
q=Head; // q初始指向头结点
while(p)
{ q->next=new Node; // 用 q->next申请结点空间
q=q->next; // q移动到新申请结点
q->data=p->data; // 复制结点数据
p=p->next; // p顺链前进到 obj的下一结点
}
q->next=NULL; Size=obj.Size;
}
template<class T>LinkedList<T>::~LinkedList()
// 析构函数
{ Node<T> *q,*p=Head; // p指向头结点
do{ q=p->next; // q指向 p的后继结点
delete p; // 释放 p所指结点空间
p=q; // p指向下一待释放空间的结点
} while(p);
}
template <class T> LinkedList<T>& LinkedList<T>::
operator=(const LinkedList<T>& origin) //,=”重载
{ Node<T> *q,*s,*p = origin.Head;
// p指向 origin表的头结点
q=Head; // q指向当前表 (*this)的头结点
while(p->next && q->next)
// 将 origin表结点数据赋给当前表结点
{ q=q->next; p=p->next; // p,q分别顺链前进
q->data=p->data; // 数据域赋值
}
if(q->next) // 当前表比 origin表长, 需释放其余结点空间
{ p=q->next; // p指向第一个要释放结点
do{ s=p->next; // s指向 p的后继结点
delete p; // 释放 p所指结点空间
p=s; // p指向下一待释放空间结点
}while(p);
} // 注意上面的操作中 q指针没有移动
else
while(p->next) //origin表更长, 申请结点空间复制剩余结点
{ q->next=new Node<T>; // 用 q->next申请结点空间
p=p->next; // p顺链前进到源结点
q=q->next; // q 移动到新申请结点
q->data=p->data; // 数据域赋值
} // end_if
q->next=NULL; // q指向当前表尾结点, 其 next域赋空指针
Size=origin.Size; // 当前表长赋值为 origin表长
return *this; // 返回当前单链表对象
}
template<class T>bool LinkedList<T>::isFull()
// 试着申请结点空间 捕获到异常则无可用的用户空间
{ Node<T> *p;
try{ p = new Node<T>; }
catch(...) {return true;} // 俘获异常, 返回表, 满, 标志
delete p; // 释放刚刚申请的结点空间
return false; // 返回表, 未满, 标志
}
template<class T>bool LinkedList<T>::
GetNode(int i,T& e) // 取第 i个数据元素存入 e
{
if (i<1 || i>Size) // 参数 i无效, 无法取得数据元素
return false;
Node<T> *p=Head->next; // p指向首元结点
for(int j=1; j<i; j++) p=p->next; // 顺链找第 i个结点
e=p->data; return true;
}
template<class T>bool LinkedList<T>::InsertNode(
T x,int i) // 插入结点 x,使其成为表的第 i个元素
{ if(i<1 || i>Size+1) // 参数 i无效, 无法插入
{ cout<<"ERROR,invalid i !!"; return false; }
if(isFull()) // 无可用的用户空间
{ cout<<"ERROR,overflow !!"; return false; }
Node<T> *s,*p=Head; // p指向头结点
for(int j=0; j<i-1; j++) p=p->next; // 寻第 i-1个结点
s=new Node<T>; s->data=x; // 建立插入结点
s->next=p->next; // 新插入结点作为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
Size++; return true; // 表长增 1,插入操作正常完成
}
template<class T>bool LinkedList<T>::InsertNode(T x)
// 插入值为 x的结点, 使保持有序
{ if(isFull()) // 无可用的用户空间
{ cout<<"ERROR,overflow !!"; return false; }
Node<T> *s,*p=Head; // p指向头结点
while(p->next && x>p->next->data) p=p->next;
// 找插入结点的前趋
s=new Node<T>; s->data=x; // 建立插入结点
s->next=p->next; // 新插入结点作为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
Size++; return true; // 表长增 1,插入操作正常完成
}
template<class T>bool LinkedList<T>::
DeleteNode(int i,T &e)
// 删除带头结点的单链表的第 i个数据元素, 被删元素值存入引用参数 x
{ if(i<1 || i>Size) return false; // 参数 i无效, 无法删除
int j=0; Node<T> *q,*p=Head; // p指向头结点
for(j=0; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
q=p->next; // 令 q指向被删除结点
p->next=q->next; // 第 i-1个结点的后继改为原第 i个结点后继
e=q->data; // 被删结点值放入 x
delete q; // 释放被删除结点所占空间
Size--; return true; // 表长减 1,删除操作正常完成
}
template<class T>bool LinkedList<T>::LocateNode(T e)
// 查找值为 e的元素 ;返回 -1表示没找到, 否则返回值是该元素在表中的序号
{ int j=1; Node<T> *p=Head->next; // p指向首元结点
while(p && p->data!=e ) j++,p =p ->next ;
if(p) return j ; else return –1 ;
}
template<class T>int LinkedList<T>::LocateNode
(T e,int low,int up)
//在范围 low-up间找值为 e的元素,返回 -1为没找到, 否则是被查元素的序号
{ int j =1 ;
Node<T> *p = Head->next; // p指向首元结点
while(p && j<low ) j++,p = p->next;
// 找第 low个结点
while(p && j<=up && p ->data!=e)
j++,p =p ->next; // 在结点 low-up间查找 e
if(p && j <= up ) return j; else return–1;
}
template<class T>void LinkedList<T>::traverse (char endchar)
//遍历单链表
{ Node<T> *p=Head->next;
while(p)
{ visitNodeData(p->data) ; p =p->next ; }
cout<< endchar<< "\nLength="<<Size<<"\n";
// endchar是表结束符
}
用带头结点的单链表的模板类定义 重新实现 § 2.3的例 2.3（ 求集
合 A,B的对称差 ?存入集合 A）, 以及利用其它一些基本运算完
成以单链表存储的整数集的集合运算 ∪, ∩的函数如下：
#include "SLList.h"
void Symm_diff(LinkedList<int>&,LinkedList<int>&);
// 求以单链表存储的两个集合“对称差”之原型声明
void CrtLinkList(LinkedList<int>&,int );
// 为集合产生若干互不相等的整数插入链表的原型声明
bool SetUnion(LinkedList<int>&La,LinkedList<int>&Lb);
// 求以单链表存储的集合 A,B的“并” (A∪ B) 的原型声明
void main()
{ LinkedList<int> La,Lb,Lc; // 用 <int>实例化单链表对象
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t; srand((unsigned)time(&t));
// 初始化随时间变化的随机数种子
cout<<"Please input Size of SetA && SetB =? =? ";
cin>>s1>>s2; // 输入集合 A,B元素数
cout<<"\nSet A = { "; // 输出集合 A的名称
CrtLinkList(La,s1); // 产生集合 A的 s1个集合成员并输出之
cout<<"}\n Length="<<s1<<"\n\nSet B = { ";
// 输出 A的成员数、集合 B的名称
CrtLinkList(Lb,s2); // 产生集合 B的 s2个集合成员并输出之
Lc = La; // 用重载的 "="运算符将 La表赋给 Lc表
cout<<" }\nLength="<<s2<<"\n\n(A-B)Union(B-A)={ ";
Symm_diff (La,Lb); // 求 La表与 Lb表的对称差，结果在 La表
La.traverse(?)?); // 输出 A? B所得到的结果表 成员数
cout<<"\nAUnionB={ ";
SetUnion(Lc,Lb); // 求 Lc表与 Lb表的“并”，结果在 Lc表
Lc.traverse(')'); // 输出 A∪ B所得到的结果表、成员数
cout<<"\nAIntersectionB = { ";
Symm_diff(Lc,La); // 求 Lc与 La表的对称差，
// 相当于求 (A∪ B) ? ( A? B) ?A∩B
Lc.traverse(')'); // 输出 A∩B所得到的结果表、成员数
}
void Symm_diff (LinkedList<int>& La,
LinkedList<int>& Lb)
// 求以单链表 La,Lb存储的集合 A,B的对称差
{ int x,i,count=0; // 记录 Lb表中元素插入到 La表中的个数
for(int j=1; j<=Lb.Length(); j++)
{ Lb.GetNode(j,x); // 取 Lb表中元素存入 x
i=La.LocateNode(x,1+count,La.Length());
// 由于集合 B不在集合 A中的元素插入到了 La表头,因此只在 A
// 原来的元素中 1+count~ La.Length() 范围内找即可。
if(i==-1) count++,La.InsertNode(x,1);
// 找不到 x，计数并插入 A集合
else La.DeleteNode(i,x); // 找到 x，则删除之
} // end_for
}
void CrtLinkList(LinkedList<int>& L,int n)
// 为链表 L产生 n个互不相等的整数插入表头
{ int x,i,j;
for(i=0; i<n; i++) // 产生 n个集合元素,不得重复
{ do x=rand() % 37; // 产生 0-36间的随机整数
while((j=L.LocateNode(x))!=-1);
// 在集合中找 x,找不到则脱离循环（要求各元素值不等）
L.InsertNode(x,1); //插入表头
cout<<x<<" "; // 输出 x (集合元素边产生边输出 )
}
}
bool SetUnion(LinkedList<int>&La,
LinkedList<int>&Lb)
// 将 La表和 Lb表所表示的集合做 "并 "，存入 La表,Lb表被清空
{ int m,n,i,k,b; bool r=true;
n=Lb.Length(); // Lb表的初始长度存入 n,删除长度将减小
m=La.Length(); // La表的初始长度存入 m,检查范围 1-m
for(i=n; i>0 && r; i--) // 从 Lb表中删除素尾元素
{ Lb.DeleteNode(i,b); // 调用删除算法
k=La.LocateNode(b,1,m); // 调用查找算法
if(k==-1) r=La.InsertNode(b,La.Length()+1);
// 找不到 b则插入至 la表尾
} //end_for
return r;
}
2.4.3线性表在多项式运算中的应用
在表处理中，常常要用到对符号多项式的处理。在数学
上，一个一元多项式 可按升幂写成：
该多项式是由 n+l个系数唯一确定。因此，在计算机里
，它可用一个线性表 P来表示
其中每一项的指数 i隐含在其系数 pi的序号里 。
设 Qm(x) 是一元 m次多项式，可用线性表 Q来表示：
不失一般性, 设 m<n,则两个多项式相加的结果
可用线性表表示：
我们可以对 P,Q和 R采用顺序存储结构, 也可以采用链
表存储结构 。 使用顺序存储结构可以使多项式相加的算
法十分简单 。 但是, 当多项式中存在大量的零系数时
（ 称这种多项式为稀疏多项式 ）, 顺序存储表示方式就
会浪费大量存储空间 。 例如：多项式 S30000(x)为：
S(x) = 1 + 2x1000 – 4x5000 + 3.5x30000
若采用顺序存储, 就要用一长度为 30001的顺序表来表
示, 表中仅有 3个非零元素 。 为了有效而合理地利用存
储空间, 我们自然会想到只存储非零系数项, 来表示
此类多项式, 但是存储非零系数项的同时必须存储相
应的指数, 才能正确表示这样的一元多项式 。
一般地, 有 m个非零系数项的一元 n次多项式可写成：
其中, 是指数为项的非零系数, 且满足：
那么, 可以用链式存储结构来表示一个长度为 m且每
个元素有两个数据项 （ 系数项和指数项 ） 的线性表 。
也就是说, 用包含 m个结点的单链表便可唯一确定多
项式 。
图 2.15所示为两个如上定义的带头结点的单链表分别表
示多项式可写成：
也就是说, 用包含 m个结点的单链表便可唯一确定多
项式 。
下面我们讨论用单链表表示一元 n次多项式时, 两个
多项式相加 （ 利用原结点空间 ） 的算法, 即要求：
Amax(m,n)(x) = Am(x)+Bn(x)，
算法结束, 结果在 A中, B成为, 空, 。
算法思路,多项式相加的运算规则为：两个多项式中
所有指数相同的项 （ 同类项 ）, 对应系数相加, 若系
数和不为零, 则构成, 和多项式, 的一项；所有指数
不同的项均复抄到, 和多项式, 中 。
我们假定多项式表 A,B已按升幂顺序排列好, 设指针 p,q
分别指向 A,B的当前未处理项中的指数最小项 （ 初始均
指向首元结点 ）, 那么, 多项式相加的过程为：将 p,q所
指结点的指数进行比较, 若 p所指结点的指数小则 p指针
前移, 若 q所指结点的指数小则从 B表中摘除该结点插入
到 A表, q指针前移, 否则是指数相等, 若系数和 ≠0,将
p指结点系数改为系数之和, 反之从 A表删除当前结点,
无论系数和是否为 0,均须从 B表删除当前结点, p,q均
应当前移到下一指数最小项, 重复进行之, 直到 p,q中至
少一个指, 空,, 这时若 q不空, 则将 B表剩余项转移到
A表, 至此算法完成 。
定义多项式的数据项类 polyNode.h的内容为：
class polyData // 多项式的数据项类
{ protected:
int exp; // 指数域
float coef; // 系数域
public:
void GetNode(int &i,float &x)
// 将当前对象的指数,系数取到引用参数 i,x
{ i=exp,x=coef; }
void SetNode(int i,float x)
// 用参数 i,x的值设臵当前对象的指数,系数
{ exp=i,coef=x; }
bool operator<(const polyData& right)
// "<" 运算符重载 (指数域比较 )
{ return exp<right.exp; }
bool operator>(const polyData& right)
// ">,运算符重载 (指数域比较 )
{ return exp>right.exp; }
void operator+=(const polyData& right)
// "+=,运算符重载 (系数域相加 )
{ coef+=right.coef; }
bool coefisZero() // 判断系数域是 0？
{ return coef==0.0; }
};
注意,由于我们在实例化单链表类时, 将 <T>用
<polyData> 具 体 化, 在单链表类中的成员函数
InsertNode(T e) 是按元素 e值的大小插入有序表, 而
polyData的数据元素值有 2个域, 因此我们将比较运
算符 "<",">"重载为左对象与右对象指数比较的结果 。
同理, 运算符 "+="被重载为,"+="号左, 右对象系数
求和赋给左对象 。
// Poly.cpp
#include "SLList.h"
#include "polyNode.h"
void Poly_Add(LinkedList<polyData>&,
LinkedList<polyData>&); //多项式求和
void CrtpolyList(LinkedList<polyData>&);
// 向多项式表插入若干输入项
void main(void)
//从终端读入系数和指数建立 A,B多项式链表,求 A=A+B；
// 并输出原 A,B多项式及和多项式
{ inkedList<polyData> La,Lb;
// 声明单链表对象 La,Lb,<T>被代之为 <polyData>
cout<<"input A coefficient and exponent,
exponent=-1 end!(term<50)\n";
CrtpolyList(La); // 读入若干系数和指数对,插入到 La
cout<<"\n creat polyNom link list A is\n";
La.traverse('/'); // 输出 La表示的多项式 A
cout<<"\ninput B coefficient and exponent,
exponent=-1 end!(term<50)\n";
CrtpolyList(Lb); // 读入若干系数和指数对,插入到 Lb
cout<<"\n creat polyNom link list B is\n";
Lb.traverse('/'); // 输出 Lb表示的多项式 B
cout<<"\n A=A+B outcome is\n";
Poly_Add(La,Lb); // 求和多项式
La.traverse('/'); // 输出和多项式
cout<<"\n";
}
void CrtpolyList(LinkedList<polyData>& L)
// 按升幂序将输入的数据对插入多项式链表 L
{ int i; float x; polyData e;
cin >>i>>x; // 读入 (实数,整数 ) 对,对应于 (系数,指数 )
while(i!=-1) // 读数对插入多项式表,输入 -1为结束标志
{ e.SetNode(i,x); L.InsertNode(e);
cin>>i>>x;
} //按指数序插入有序表
}
void Poly_Add( LinkedList<polyData>& Pa,
LinkedList<polyData>& Pb )
// 求升幂排列的多项式表 Pa与 Pb之和,存入 Pa (利用原结点空间 ),
// 和多项式仍是升幂排列
{ Node<polyData> *p,*q,*r,*s;
int m=Pa.Length(),n=Pb.Length();
int c=0,d=0;
// c统计循环中 Pa增加的项数,d统计循环中 Pb摘除的项数
s=Pa.Head; // s指向和多项式的当前尾结点 (s ->next 指向 p)
p=s->next; q=Pb.Head->next;
//令 p,q分别指向两多项式的首项
while(p && q) //多项式 Pa与 Pb均有未处理的数据项
if(p->data<q->data){ s=p; p=p->next; }
// s,p指针前移 (p所指项的指数较小 )指数序插入有序表
else if(p->data>q->data) //q所指项的指数较小
{ r=q->next; q->next=p; s->next=q;
s=q; q=r; c++; d++;
}
else{ p->data+=q->data;
// 同类项,求系数和存入 p所指项
if((p->data).coefisZero())
// 判断系数和是 0否,是则从 Pa摘除结点
{ s->next=p->next;
delete p; c--;
}
else s=p; // 系数之和 !=0,s前移
// 无论系数和是否为 0,均摘除 Pb中结点
p=s->next; r=q; q=q->next; delete r; d++;
} // 结束 p,q所指项为同类项的处理
if(q)s->next=q; // 若 Pb表中有剩余元素则插入 Pa
Pb.Head->next=NULL,Pb.Size=0; // 臵 Pb表为, 空, 表
Pa.Size=m+c+(n-d); // 计算 Pa表的项数, 臵 Pa表的 Size
}
void visitNodeData(polyData e) // 输出多项式数据域
{ float x; int j;
e.GetNode(j,x);
cout<<"( "<<x<<','<<j<<")→";
}
2.5 小结
本章主要介绍了如下一些基本概念：
线性表 及其 两种存储结构
单链表 循环链表 双链表
给出了线性表的模板类 （ 顺序表, 单链表 ） 并且应
用它们完成了集合运算, 一元多项式的链式表示与
相加等应用实例 。
1.线性表的逻辑结构
2,顺序表
3,链表
单链表的存储结构
单链表的基本运算
循环链表
双链表
目录 (续 )
顺序表的模板类定义及应用
单链表的模板类定义及应用
线性表在多项式运算中的应用
4,线性表的应用实例
5,小结
线性表是最基本、最常用的一种数据结构，它不仅
有着广泛的应用，而且也是其它数据结构的基础。线性
表的例子不胜枚举。例如，英文字母表（ A,B,…,Z ）
是一个线性表，表中的每一个英文字母是一个数据元素，
又如，一副扑克牌的点数也是一个线性表：（ 2,3,4,5,
6,7,8,9,10,J,Q,K,A）。其中每一张牌的点数就是
一个数据元素。在较为复杂的线性表中，数据元素可由
若干数据项组成，如学生成绩表中，每个学生的成绩情
况是一个数据元素，它由学号，姓名，各科成绩及平均
成绩等数据项组成。
2.1 线性表的逻辑结构
2.1.1 线性表的基本概念
线性表 （ Linear List） 是由 n（ n?0）个具
有相同属性的数据元素 a1,a2,…,an组成的有限序列。
其中数据元素的个数 n定义为表的长度。
当 n=0时称为空表，常常将非空的线性表（ n>0）
记作,（ a 1,a 2,···, a i, ···, a n ）
这里的数据元素 a i（ 1 ? i ? n） 只是一个抽象的
符号, 其具体含义在不同情况下是不同的 。
从线性表的定义可以看出其 特点 是：
?⑴ 同一性：线性表中的所有数据元素属于同一数据
对象；
⑵ 有穷性：线性表中的数据元素个数是有限的, 其
数目就是表长；
⑶ 有序性：线性表中相邻的数据元素间存在着序偶
关系 < ai,ai+1>
ADT LinearList{
Typedef struct List L;
InitList(L,maxSize);
说明：构造空表 L,即表的初始化
ListLength(L);
说明：求表 L的长度
isEmpty(L);
说明：判断表 L是否为空表
isFull(L) ;
说明：判断表 L是否已, 满,
GetNode (L,i,e);
说明：取表 L中的第 i个数据元素存入 e
2.1.2 线性表的抽象数据类型定义
LocateNode(L,e);
说明：查找表 L中值为 e的数据元素
LocateNode(L,e,low,up);
说明：在表 L的 low-up范围内查找值为 e的数据元素
InsertNode (L,e,i);
说明：在表 L的第 i个位臵插入值为 e的新数据元素
InsertNode (L,e);
说明：值为 e的数据元素插入到有序表 L,保持有序
DeleteNode (L,i,e);
说明：删除表 L中第 i个数据元素, 被删元素值存入 e
ClearList (L);
说明：将线性表 L清空
} ;
将一个线性表存储到
计算机中，可以采用许
多不同的方法，其中既
简单又自然的是顺序存
储方法：用一组地址连
续的存储单元依它们的
逻辑次序存储线性表的
各个数据元素，称作线
性表的顺序存储结构，
简称为顺序表。
2.2 顺序表 2.2.1线性表的顺序存储结构
设线性表 L = (a 1,a 2,···,a n )，每个元素占用 d个存
储单元，则线性表中第 i+1个元素 a i+1的存储位臵
LOC(a i+1)和第 i个元素 a i的存储地址 LOC(a i)之间满足
关系：
LOC(a i+1) = LOC(a i) + d
因此, 表中第 i个元素 ai的存储位臵可通过下式计算：
LOC(a i) = LOC(a 1) + (i -1) * d
其中,LOC(a1)是第一个元素的地址称为基地址。
顺序表的特点是：
逻辑上相邻的元素其物理位臵亦相邻。
2.2.2顺序表的基本运算
下面, 我们先给出整数表的结构声明：
Typedef struct
{
int *elem; // 数据元素数组指针
int Size; // 线性表中当前元素数目
int maxSize; // 初始化操作中为线性表分配的单元数
}sqList;
线性表的插入运算是指：在表的第 i (1 ? i ? n+1)个
位臵上, 插入新数据元素 e,使长度为 n的线性表：
（ a1,a2,…,ai-1,ai,…,an ）
变成长度为 n+1的线性表：
（ a1,a2,…,ai-1,e,ai,…,an ）
在顺序表中，线性表的有些运算很容易实现。例如 取第
i个数据元素 GetNode (L,i,e)和 求表长 ListLength(L)。
以下主要讨论 插入 和 删除 两种运算。
⒈ 插入
线性表采用顺序存储结构时, 由于数据元素
的物理顺序必须和数据元素的逻辑顺序保持
一致, 因此我们必须将表中位臵 n,n-1,…,i
上的元素依次后移到位臵 n+1,n,…,i+1上,
腾出第 i个位臵, 然后在该位臵上插入新数据
元素 e,仅当插入位臵 i=n+1时, 才无需移动
数据元素, 直接将 e插入表尾 。
分析：
bool InsertNode (sqList &L,int e,int i)
// 插入新元素 e使其成为表 L的第 i个元素；
// 若正常完成插入返回 true,否则返回 false。
{ int j ; bool r = false; // 预臵插入标志
if( i<1 || i>L.Size+1) // 非法插入位臵
cout << " ERROR:invalid i !!\n";
else
if(L.isFull()) // 表满 (溢出 )
cout << " ERROR,overflow !!\n";
else // 正常插入
{ for( j=L.Size; j>=i; j -- ) // 数据元素依次后移
L.elem[j]=L.elem[j-1];
L.elem[j]=e; // 插入新数据元素
L.Size++; // 表长增 1
r = true; // 设臵插入正常标志
}
return r;
}
注意 元素后移的方向, 必须从表中最后一个元素开
始后移, 直至将第 i个元素后移为止 。
问题的规模是表的长度 L.Size,将其记为 n, 显然
该算法的时间主要花费在 for循环中的元素后移语句
上, 该语句的循环执行次数 (即移动元素的次数 )是 n-
i+1。 由此可见, 所需移动元素的次数不仅依赖于表
的长度, 而且还与插入位臵 i有关 。
由于插入可能在表中任何位臵上进行, 因此需分析
算法的平均性能 。
算法的时间复杂度分析：
令 Eis(n)表示在长度为 n的线性表中插入一个元素所需移动
元素的期望值 （ 即移动元素的平均次数 ）, 则
i
1n
1i
iis mpE ?
?
?
?
其中, pi表示在表中第 i个位臵上插入一个元素的概率； mi是
在表中第 i个位臵上插入一个元素时所需移动元素的次数, 那
么 mi = n-i+1。 不失一般性, 假设在表中任何有效位臵 （ 1 ? i
? n+1） 上插入元素的机会是均等的, 即 p1=p2=… =pn+1=，
因此, 在等概率插入的情况下有：
?
?
?
? ????
1n
1i
1n
1
2
n1)i(n
isE
即, 在顺序表上做插入运算平均要移动表中的一
半元素, 当表长 n较大时, 算法的效率相当低, 其平
均时间复杂度是 O(n)。
有时需要使得顺序表是有序的, 即不指定插入位臵,
按元素值从小到大插入 。
线性表的删除运算是指将表的第 i（ 1 ? i ? n） 个元
素删去, 使长度为 n的线性表：
（ a1,a2,…,ai-1,ai,ai+1,…,an）
变成长度为 n-1的线性表：
（ a1,a2,…,ai-1,ai+1,…,an）
⒉ 删除
和插入运算类似, 在顺序表上实现删除运
算也必须移动元素, 才能反映出元素间逻辑
关系的变化 。 若 i == n,则只要简单地删除
终端元素, 不需移动元素；若 1 ? i ? n -1则
必须将表中位臵 i+1,i+2,…,n上的元素依次前
移到位臵 i,i+1,…,n-1上, 以填补删除操作
造成的空缺 。
分析：
bool DeleteNode(sqList &L,int i,int &e)
// 删除 L的第 i个元素, 被删元素值存入引用参数 e；
// 若正常完成删除返回 true,否则返回 false。
{ int j ; bool r = false; // 预臵标志
if(i<1 || i>L.Size) // 非法删除位臵
cout << " ERROR:invalid i !!\n";
else // 正常删除
{ e=L.elem[i-1]; // 被删数据元素值放入 e
for(j=i; j<L.Size; j++) // 数据元素依次前移
L.elem[j-1]=L.elem[j];
L.Size --; // 表长减 1
r = true; // 设臵删除正常标志
}
return r;
}
算法的时间复杂度分析：
设表长 L.Size记为 n。 元素前移语句的频度是 n-i,因此
元素的移动次数也是由表长 n和位臵 i决定的 。
若 i==n,则由于循环变量的初值大于终值, 前移语句
将不执行, 无需移动元素；若 i==1,则前移语句将循环
执行 n-1次, 需移动表中除开始元素外的所有元素 。 这
两种情况下算法的时间复杂度分别是 O(1)和 O(n)。
令 Ede(n)表示在长度为 n的线性表中删除一个元素所需移动
元素的平均次数, 则
?
?
?
n
1i
iimqdeE
其中, q i表示删除表中第 i个元素的概率； n i是删除表中第 i个
元素时所需要移动元素的次数, 即 n i = n-i,在等概率的假设
下 q1=q2=… qn=,因此得到
2
1n
n
1i
n
1
n
1i
ii i)(nmqdeE
?
??
???? ??
即, 顺序表的删除与插入类似, 约需移动一半元素
,其平均时间复杂度也是 O(n)。
线性表的查找操作可分为：
按序号查找 GetNode (L,i,e) 和
按内容查找 LocateNode(L,e)两种 。
⒊ 查找
当然, 还可以不在整个表查找元素 e,只 在给定
low-up区间查找 值为 e的元素 。
下面给出按内容查找的算法描述：
int LocateNode(sqList &L,int e)
// 查找表 L中值为 e的数据元素 ;
// 返回值为 -1表示没找到, 否则是被查找结点的序号
{ int i=0;
while( i<L.Size && L.elem[i]!= e )i++;
if(i< L.Size) return i+1;
else return -1;
}
⒋ 顺序表的应用例
【 例 2.1】 设表 la和 lb分别表示整数集合 A和 B，
且用数组存储, 求,A=A∪ B。
算法思路,集合中的元素是无重复的, 可将 Lb表中
的元素从表尾起逐个删除, 并在 La表查找被删元素
b,若找不到, 则将元素 b插入 La表, 否则不必插
入, 完成后集合 B为空 。
bool SetUnion(sqList &la,sqList &lb)
{ int b,n,i; bool k,r=true ;
n=Lb.Size; // Lb表的初始长度存入 n
for(i=n; i>0 && r ; i--)
// 从 Lb表中逐次删除表尾元素, 这样不必移动元素
{ r=DeleteNode(Lb,i,b);
// 调用删除算法, 被删元素存入 b
k=LocateNode(La,b); // 在 La表中查找 b
if(!k) r=InsertNode(La,b,La.Size+1);
// La表中找不到元素 b,则插入至 la表尾
} // end_for
return r;
}
算法分析,由于要从 Lb表中逐次删除表尾元素, 则
for循环执行 Lb.Size次, 循环体中的尾删除和尾插入
不需移动元素, 但 LocateNode(La,b) 的时间复杂
度为 La.Size,因此 SetUnion的时间复杂度为：
O(La.Size*Lb.Size)。
【 例 2.2】 设整数表 La和 Lb采用顺序结构存储, 且
表中的整数均按值非递减有序排列, 现要求由 La和
Lb归并产生一个新的整数表 Lc,要求 Lc中的数仍
按值非递减有序排列 。
算法思路,由题意可知, Lc中的数据元素或是 La中
的数据元素, 或是 Lb中的数据元素, 那么只要先设
Lc为空表, 然后将 La或 Lb中的元素逐个插入到 Lc中
即可 。 为使 Lc中元素按值非递减有序排列, 可设两个
指针 i和 j分别指向 La和 Lb中某个元素, 假设 i当前所
指的元素为 a,j当前所指的元素为 b,则当前应插入
到 LC中的元素 c为：
a 当 a ≤ b 时
c =
b 当 a > b时
显然, 指针 i和 j的初值均为 1,在所指元素插入 Lc之
后, 在 La或 Lb中顺序后移 。
此算法执行后整数表 La和 Lb保持不变 。
Bool Merge(sqList& Lc,sqList& La,sqList& Lb)
// 由 La和 Lb归并产生新的整数表 Lc,La和 Lb保持不变 。
{ int i=1,j=1,m=La.Size,n=Lb.Size;
int a,b; bool r=true;
GetNode(La,i,a); // 取 La表指针 i所指元素存入 a
GetNode(Lb,j,b); // 取 Lb表指针 j所指元素存入 b
while(i<=m && j<=n && r)
// La和 Lb表均没到表尾且插入 Lc正常则进入循环体
if(a<=b) // La 表所指元素较小, 将其插入 Lc 表, 指针 I 后移
{ r=InsertNode(Lc,a,Lc.Size+1);
GetNode(La,++i,a);
}
else // Lb表所指元素较小, 将其插入 Lc表, 指针 j后移
{ r=InsertNode(Lc,b,Lc.Size+1);
GetNode(Lb,++j,b);
}
// 下面两个 while循环有且仅有一个被执行
while(i<=m) // 将 La表中剩余元素插入 Lc
{ GetNode(La,i++,a);
r=InsertNode(Lc,a,Lc.Size+1);
}
while(j<=n) // 将 Lb表中剩余元素插入 Lc
{ GetNode(Lb,j++,b);
r=InsertNode(Lc,b,Lc.Size+1) ;
}
return r ;
}
算法分析,由于 La和 Lb是有序表, 每次插入 Lc表的
是 La或 Lb 的一个元素, 采取尾插入, 不必移动元素,
故 Merge时间复杂度为,O(La.Size+Lb.Size)。
⒌ 小结
由顺序表的特点可知, 线性表采用顺序存储有如
下的优缺点 。
优点,
⑴ 不需为表示元素间的逻辑关系而增加额外的存储
空间；
⑵ 可以方便地随机存取表中的任一结点 。
缺点,
⑴ 插入和删除运算不方便, 除表尾的位臵外, 在表
的其它位臵上进行插入和删除操作都必须移动大
量的元素, 因此效率较低；
⑵ 由于顺序表要求占用连续的存储空间, 这样只能
在创建时进行分配, 因此当表长变化较大时, 难以
确定合适的存储规模, 若按可能达到的最大长度预
先分配表空间, 则可能造成一部分空间长期闲臵而
得不到充分利用, 若事先对表长估计不足, 则插入
操作可能使表长超过预先分配的空间而造成溢出 。
线性表的链式存储结构是用一组任意的存储单元
存储线性表的数据元素（这组存储单元可以是不
连续的），对线性表中的每一个数据元素，都需
用两部分来存储：一部分用于存放数据元素值，
称为数据域；另一部分用于存放直接前驱或直接
后继结点的地址（指针），称为指针域，我们把
这种存储单元称为结点。根据链接方式的不同，
链表又可分为单链表、循环链表、双链表等。
2.3 链表
2.3.1 线性表的链式存储结构
链表中仅只包含一个指针域用
来存放直接后继 (或直接前驱 )
结点的地址称做单链表。图
2.2所示为单链表的结点结构。
2.3.2 单链表
头指针,由于单链表中每个结点的存储地址是存放在
其前驱结点的指针域中，而第一个结点没有前驱结点，
因而要专门设立一个指向首元结点的指针 Head，通
常称之为头指针
图 2.3所示为线性表（ Zhao,Qian，
Sun,Li,Zhou,Wu,Zheng，
Wang）的单链表存储结构。通常我们
把链表画成用箭头相链接的结点的序列，
结点之间的箭头表示链域中的指针。如
图 2.3的单链表可按照其逻辑顺序画成
如图 2.4所示的形式，这是因为在使用
链表时，关心的只是它所表示的单表中
数据元素之间的逻辑顺序，而不关心每
个数据元素在存储器中的实际位臵。
由上可见，单链表可由头指针唯一确定，假设 p是指
向线性表中第 i个数据元素 (结点 ai)的指针，则 p->next
是指向第 i+1个数据元素 (结点 ai+1)的指针。换句话说，
若 p->data=ai，则 p->next->data=ai+1。由于结点的
逻辑顺序与物理顺序可以不一致，在单链表中，取得
第 i个数据元素必须从头指针出发寻找，因此，单链表
是非随机存取的存储结构。
为了操作方便, 我们经常在单链表的 首元结点 (第一
个结点 )之前附设一个结点, 称之为 头结点 。 头结点
的数据域不存储任何信息, 头结点的指针域存储指
向首元结点的指针 。
我们仍然先以整数表为例, 讨论单链表的算法, 定
义单链表的结点结构如下：
2.3.3 单链表的基本运算
typedef struct Node
{ int data; // 数据元素 (数据域 )
struct Node *next; // 指向后继的指针 (指针域 ）
} Node;
我们定义单链表结构为：
typedef struct
{ Node *Head; // 链表头指针
int Size; // 链表当前长度 （ 结点数 ）
} LinkedList;
“插入”和“删除”
假设我们要在单链表的两个数据元素 a和 b之间插入
一个数据元素 x，已知 p为其单链表存储结构中指向结
点 a的指针。如图 2.7(a)所示。
图 2.8所示为在单链表中删除 a和 c之间的元素 b时结
点间逻辑关系的变化。
假设 s为指向结点 x的指针，则上述指针修改用语句
描述即为,s ->next = p->next ;
p ->next = s ;
假设 p为指向结点 a的指针，则修改指针用语句描述
为,p -> next = p -> next -> next ;
结论,在单链表中插入和删除一个结点时，仅需修改指
针而不需要移动元素。
⒈ 插入
⑴ 无头结点的单链表中的插入
bool InsertNode (LinkedList&L,int x,int i )
// 无头结点的单链表中插入值为 x的结点, 成为表 L的第 i个元素
{ Node *p,*s ;
if (i<1 || i>L.Size+1) return false; // 参数 i无效, 无法插入
s=new Node; s->data=x; // 建立插入结点
if(i==1) // 插入首元结点
{ s->next=L.Head; // 原首元成为新插入结点的后继结点
L.Head=s; // 新插入结点成为首元结点
}
else // i > 1 && i <= L.Size + 1
{ p=L.Head; // p指向首元结点
for(int j=1; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
s->next=p->next; // 新结点为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
}
L.Size++; // 表长增 1
return true; // 返回插入操作正常完成标志
}
在算法中, 我们对参数 i ==1进行了特殊处理, 原因
是首元结点的位臵是存放在头指针中, 而其余结点的
位臵是在其前趋结点的指针域中, 二者表示不一致 。
如果对 i ==1不做判断, 直接执行 for语句, 将会把新
结点插入成链表的第 2个结点 。 通过设臵头结点, 可
以避免特殊处理, 其原因有二,① 由于首元结点的
位臵被存放在头结点的指针域中, 所以在链表的第一
个位臵上的操作就和在表的其它位臵上操作一致, 无
需进行特殊处理； ② 无论链表是否为空, 其头指针是
指向头结点的非空指针 （ 空表中头结点的指针域为
空 ）, 因此空表和非空表的处理也就统一了 。
⑵ 带头结点的单链表中的插入
bool InsertNode (LinkedList&L,int x,int i )
//带头结点的单链表中插入值为 x的结点, 成为表 L的第 i个元素
{ Node *p,*s ;
if (i<1 || i>L.Size+1) return false; // 参数 i无效, 无法插入
p=L.Head; // p指向头结点
for(int j=0; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
s=new Node; s->data=x; // 建立插入结点
s->next=p->next; // 新结点为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
L.Size++; // 表长增 1
return true; // 返回插入操作正常完成标志
}
算法分析,显然, 插入算法的时间主要耗费在寻访
第 i-1个结点, 算法的平均时间复杂度仍然是 O(n)，
似乎和顺序表相同, 但是由于单链表的插入只是顺
链移动指针并不移动元素, 这对于数据元素占用单
元很多的表来说, 实际时间耗费要少得多 。
⒉ 删除 带头结点的单链表的删除算法
bool DeleteNode(LinkedList&L,int i,int &x )
// 删除单链表 L的第 i个数据元素, 被删元素值存入引用参数 x
{ if(i<1 || i>L.Size) return false; // 参数 i无效, 无法删除
int j=0; Node *q,*p=L.Head; // p指向头结点
for(j=0; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
q=p->next; // 令 q指向被删结点
p->next=q->next; // 修改第 i-1个结点的后继结点
x=q->data; // 被删结点值放入 x
delete q; // 释放被删除结点所占空间
L.Size--; // 表长减 1
return true; // 返回删除操作正常完成标志
}
算法分析,删除算法的时间复杂度分析与插入算法
的时间复杂度分析相同 。
⒊ 查找
在单链表中, 由于结点的逻辑顺序与物理顺序可以不一
致, 因此 GetNode (L,i,e)算法必须从头指针出发寻找,
其实就是上面插入算法中的寻访第 i-1个结点的方法 。
按内容查找 LocateNode(L,e)算法
int LocateNode LinkedList& L,int e)
// 查找值为 e的元素；返回该元素在表中的序号, 返回 -1表示没找到 。
{ Node *p ; int j=1;
p=L.Head->next; // p指向首元结点
// 如果不带头结点则此语句是,p = L.Head;
while(p && p->data!=e) j++,p=p->next ;
if(p) return j; else return -1;
}
⒋ 创建单链表
为了测试实现单链表基本运算的算法, 必须批量输入数据建立
起单链表, 当然是通过调用插入算法建立单链表, 但还根据插入
新结点位臵的不同, 有, 头插入, 法和, 尾插入, 法 。
“头插入, 法,每输入一个元素, 总将其插入至 La表头, 即插入
位臵参数 i ==1,这样插入算法中的寻访第 i-1个结点的 for循环体
一次都不被执行, 只是建立的表中元素链接顺序与输入元素的顺
序相反；
“尾插入, 法,设立一个尾指针 （ 指示尾结点 ）, 初始时 （ 空表 ）
指向头结点, 建表中, 每次将元素插入至尾结点之后, 再将尾指
针移动到新插入结点 。
如果是建立 有序表, 则应反复调用 InsertNode ( LinkedList& L,
int x)函数, 从, 空, 表起, 逐个插入元素, 为了保持有序, 该
算法是根据元素值经比较插入的 。
“头插入, 法建立单链表的算法：
#define endMark -999 // 设定输入结束标志
void CrtLinkList(LinkedList& L)
// 用 "头插入 "法建立带头结点的单链表 L
{ int x ;
// 以下为 La表初始化 （ 建立头结点, 表长臵 0）
L.Head=new Node; L.Head->next=NULL; L.Size=0;
cout<<"Please input integer Create List ";
cout<<"input " << endMark << " end! \n";
// 输出提示信息
cin>>x; // 输入 L表的第一个元素
while(x!=endMark)
{ InsertNode(L,x,1); // 插入到表头
cin>>x; // 输入 L表的其余元素
}
}
⒌ 单链表的应用例
【 例 2.3】 求整数集合 A= (A-B)∪ (B-A)
算法思路,分别用带头结点的单链表 La,Lb表示集合 A和 B，
用 for循环逐个从 Lb表中取元素存入 x中, 在 La表中查找 x，
若找到, 则 x∈ A∩B,将 x从 La表删除；否则 x∈ B－ A,将 x
插入 La表, for循环结束算法完成；此时 La表代表所求的
(A-B) ∪ (B-A)集合, Lb保持不变 。
void Symm_diff(LinkedList& La,LinkedList& Lb)
{ int x,i; Node *p;
p=Lb.Head->next; // p 指向 Lb表的首元结点
for(int j=1; j<=Lb.Size; j++) // 顺 Lb表逐结点检查
{ x=p->data; // 取 p 指针所指结点值存入 x
i=LocateNode(La,x); // 检查 x是否在 La表中
if(i==-1) InsertNode(La,x,1); // x 不在表中, 插入
else DeleteNode(La,i,x); // x 在表中, 删除之
p=p->next;
}
}
循环链表是另一种形式的链式存储结构 。 它的特点
是表中最后一个结点的指针域指向头结点, 整个链
表形成一个环 。 由此, 从表中任一结点出发均可找
到表中其它结点 。 图 2.9所示为单链的循环链表 。 类
似地, 还可以有多重链的循环链表 。
2.3.4循环链表（ circular linked list）
循环链表的操作和单链表基本一致, 差别仅在于
算法中的循环条件不是 p或 p->next是否为空, 而是
它们是否等于头指针 。
有时, 若在循环链表中设立尾指针而不设头指
针 （ 如图 2.10 (a)所示 ）, 可使某些操作简化 。 例如
将两个线性表合并成一个表时, 仅需将一个表的表
尾和另一个表的表头相连接 。 当线性表以图 2.10(a)
的循环链表作存储结构时, 此操作仅需改变两个指
针值即可, 运算时间为 O(1)。 合并后的表如图 2.10
(b)所示 。
我们前面讨论的链式存储结构的结点中只有一个
指示直接后继的指针域, 因此, 从某个结点出发只
能顺指针往后寻查其它结点 。 若要寻查结点的直接
前趋, 则需从表头指针出发, 遍历整个链表 。 为了
克服单链表这种单向性的缺点, 可利用双链表 。
2.3.5双链表 (double linked list)
在双链表的结点中有两个指针
域, 其一指向直接后继, 另一
指向直接前趋, 其结点结构如
图 2.11所示 。
和单循环链表类似, 双链表也可以有循环表, 如图
2.12所示, 链表中存在两个环 。
在双链表中, 若 d为指向表中某一结点的指针, 则显
然有,d -> next -> prior =d -> prior -> next =d;
在双链表中, 有些操作如：
GetNode(L,i,e),LocateNode(L,x)等算法描述和
线性链表的操作相同, 但在插入, 删除时有很大的
不同, 在双链表中需同时修改两个方向上的指针,
图 2.13和图 2.14分别显示了删除和插入结点时指针
修改的情况 。
假设指针 p指向数据域为 a的结点, 则插入时修改指
针的语句是：
s->next=p->next; q = p ->next ;
s->proir=p; p ->next = q ->next ;
s->next->prior=s;
删除时修改指针的语句是：
q ->next ->prior =q->prior ;
p->next=s; delete q ;
#include <iostream.h>
template <class T>
// 模板声明,T是类参数 (可变类型,在声明顺序表对象时被具体化 )
class sqList
{ protected:
T *elem; // elem是存放线性表数据元素的数组指针
int Size; // 顺序表的当前长度 (元素数目 )
int MaxSize; // 顺序表的最大长度 （ 容量 ）
2,4 线性表的应用实例
2.4.1顺序表模板类定义及应用
public:
sqList(int ms=10); // 构造函数
sqList(const sqList<T>&); // 复制构造函数
~sqList() { delete [] elem; } // 析构函数
sqList& operator=(const sqList<T>&);
// "="运算符重载
bool isEmpty() { return Size==0; }
// 判断顺序表是否为空表
bool isFull() { return Size==MaxSize; }
// 判断顺序表是否已, 满,
int Length() { return Size; }
// 求顺序表的长度
bool GetNode(int index,T& e);
// 取表中第 index个数据元素存入 e
int LocateNode(T e); // 查找值为 e的元素
int LocateNode(T e,int low,int up);
// 在给定范围 low-up内查找值为 e的元素
bool InsertNode( T e,int index);
// 插入数据元素 e,index是插入位臵
bool InsertNode(T e); // 按元素值 e的大小插入有序表
bool DeleteNode(int index,T& e);
// 删除序号 index的元素并存入 e
void traverse(char); // 遍历顺序表
}; // 结束类接口定义
template<class T>void visitNodeData(T);
// 遍历表中要调用的输出数据域的函数
// T实例化后才能确定访问方式
// 以下为类实现部分
template <class T>sqList<T>::sqList(int ms)
// 构造函数,申请顺序表存储空间, 当前表长初始化为 0
{ if(ms<=0)
{ cout<<"ERROR:invalid MaxSize!!\n";
return;
}
elem=new T[ms]; MaxSize=ms ; Size=0 ;
}
template <class T> sqList<T>:,sqList (const
sqList<T>& obj) // 由顺序表 obj复制构造当前对象
{ MaxSize=obj.MaxSize; Size=obj.Size;
// 表容量, 表长赋为 obj相应值
elem=new T[MaxSize];
// 为当前对象申请存放元素的存储空间
for(int j=0; j<Size; j++) elem[j] = obj.elem[j];
// 复制 obj的数据元素
}
template <class T>sqList<T>::sqList
operator=(const sqList<T>&origin) // "="运算符重载
{
if(MaxSize!=origin.MaxSize) // 当前表与 origin表容量不等
{ delete[ ] elem; // 释放原来的存放数据元素空间
elem=new T[MaxSize]; // 重新为当前对象申请空间
}
MaxSize=origin.MaxSize; // 当前表容量赋值为 origin表容量
Size=origin.Size; // 当前表长赋值为 origin表长
for(int j=0; j<Size; j++) elem[j]=origin.elem[j] ;
// 复制数据元素
}
template <class T>bool sqList<T>:,GetNode(int index,T& e)
// 取表中第 index个数据元素存入 e
{ if (index<1||index>Size) return false;
e=elem[index-1]; return true;
}
template <class T>int sqList<T>:,LocateNode(T e)
// 查找到值为 e的元素返回元素序号, 否则返回 -1
{ int i=0 ;
while(i<Size && elem[i]!=e ) i++;
if(i<Size) return i+1; else return -1;
}
template <class T>int sqList<T>::LocateNode
(T e,int low,int up) // 在 low-up间查找值为 e的元素
// 返回 -1表示被查元素不存在, 否则是被查元素的序号
{ int i =low –1 ;
while( i<up && elem[i]!=e ) i++;
if(i < up) return i+1; else return –1 ;
}
template <class T>bool sqList<T>::InsertNode( T e,
int index ) // 插入元素 e,index是插入位臵
{ int j; bool r=false ;
if (index<1 || index>Size+1) // 非法插入位臵
cout<<"ERROR:invalid index!!\n";
else
if( isFull( ) ) // 表满 （ 溢出 ）
cout<<"ERROR,overflow !!";
else
{ for(j=Size; j>=index; j--)elem[j]=elem[j-1];
// 元素依次后移
elem[j]=e; Size++; // 插入数据元素,表长增 1
r=true; // 设臵插入正常标志
}
return r;
}
template <class T>int sqList<T>::InsertNode(T e)
// 将数据元素 e插入有序表, 使保持有序
{ int j;
if(isFull()) // 返回, 表溢出无法插入
{cout<<"ERROR,overflow !!"; return false; }
for(j=Size; j>0; j--) // 边查找应插入位臵边移动元素
if(elem[j-1]>e) elem[j]=elem[j-1]; else break;
elem[j]=e; // 插入新数据元素
Size++; // 表长增 1
return true; // 返回插入正常标志
}
template <class T>int sqList<T>::DeleteNode(int
index,T& e) // 删除序号为 index的元素 被删元素存入 e
{ int j; bool r=false;
if (index<1 || index>Size) // 非法删除位臵
cout<<"ERROR:invalid index!!\n";
else
{ e=elem[index-1]; // 被删数据元素值放入 e
for(j=index; j<Size; j++) elem[j-1]=elem[j];
// 数据元素依次前移
Size--; r=true; //表长减 1,设臵删除正常标志
}
return r;
}
template <class T>void sqList<T>::traverse
(char endchar) // 遍历顺序表 (endchar是表结束符 )
{
for(int i=0; i<Size; i++)
visitNodeData(elem[i]);
cout<<endchar<<"\n Length="<<Size<<"\n";
}
用顺序表的模板类定义重新实现 § 2.2的 例 2.1（ 设表
la和 lb分别表示两个整数集合 A和 B,求,A=A∪ B）
的算法 SetUnion及有关函数代码如下：
#include <stdlib.h>
#include <time.h>
#include "SQList.h"
void CrtSetList( sqList<int>&,int );
// 原型声明 产生若干互不相等的整数插入表
bool SetUnion( sqList<int>&,sqList<int>& );
// 集合“并”运算的原型声明
void main()
{ // 声明 sqList对象 La,Lb,类参数 T用 <int>实例化
sqList<int> La(40),Lb(20); // La,Lb容量分别为 40,20
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t;
srand((unsigned)time(&t)); //初始化随机数种子
cout<<"Please input Size of SetA && SetB =? =? (<=20)";
cin>>s1>>s2; // 输入 A,B元素数 <=20,以保证 "并 "后 La的元素数 <=40
cout<<"\nSet A = { "; // 输出集合 A的名称
CrtSetList(La,s1);
// 为集合 A产生 s1个互不相等的整数插入并输出集合元素
cout<<"}\nSet B = { "; // 输出集合 B的名称
CrtSetList(Lb,s2);
// 为集合 B产生 s2个互不相等的整数插入并输出集合元素
if(SetUnion(La,Lb))
// 求集合 A与集合 B的“并” 若正常返回则输出结果
{ cout<<"}\n\n A Union B = { ";
La.traverse( ')' };
}
}
void visitNodeData(int d) // 输出数据域（集合元素值）
{ cout<<d<<" "; }
void CrtSetList(sqList<int>&L,int n)
// 为集合产生 n个互不相等的整数插入顺序表
{ int x,i,j;
for(i=0; i<n; i++) // 产生 n个集合元素,不得重复
{ do { x=rand() % 37; } // 产生 0-36间的随机整数
while((j=L.LocateNode(x))!=-1);
// 在集合中找 x,找不到则脱离循环
L.InsertNode(x,L.Length()+1);
cout<< x << " "; // 输出 x (集合元素边产生边输出 )
}
}
bool SetUnion(sqList<int>&La,sqList<int>&Lb)
{ int m,n,i,k,b; bool r = true;
n=Lb.Length(); m=La.Length();
// Lb,La的初始长度分别存入 n m,检查 B集合元素是否 ∈ A时范围小
for(i=n; i>0 && r; i--)
// 从 Lb表中逐次删除素尾元素不必移动元素
{ Lb.DeleteNode(i,b); // 删除 Lb表的元素，被删元素存入 b
k=La.LocateNode(b,1,m);
// 在 La表原来的范围内找 b，不必考虑新插入的元素
if(k==-1) // La表中找不到元素 b
r=La.InsertNode(b,La.Length()+1); // 插入至 la表尾
} //end_for
return r; // 返回操作是否正常完成
}
#include <iostream.h>
template <class T> struct Node
// 定义单链表结点结构
// 模板 T是类参数 (可变类型,在声明单链表对象时被具体化 )
{ T data; // 数据元素 （ 数据域 ）
Node <T> *next; // 指向直接后继的指针 （ 指针域 ）
};
2.4.2 单链表模板类定义及应用
下面我们首先定义单链表结点结构，然后定义单链表类
template <class T> class LinkedList // 定义单链表类
{ protected:
Node <T> *Head; // 单链表头指针
int Size; // 单链中元素数
public:
LinkedList(); // 构造函数
LinkedList(const LinkedList<T> &); // 复制构造函数
~LinkedList(); // 析构函数
LinkedList& operator=(const LinkedList<T>&);
// "=" 运算符重载
bool isEmpty(){ return Size==0; }
// 判断单链表是否为, 空,
bool isFull(); // 判断单链表是否已 "满 ",无用户空间
int Length(){ return Size; } // 求链表的长度
bool GetNode(int,T&); // 取数据元素
bool InsertNode(T,int); // 插入数据元素
bool InsertNode(T e); // 按元素值 e的大小插入有序表
bool DeleteNode(int,T&); // 删除数据元素
int LocateNode(T e); // 查找数据元素
int LocateNode(T e,int,int);
// 在给定范围内查找值为 e的元素
void traverse(char endchar); // 遍历单链表
friend void Poly_Add (LinkedList<T>&,LinkedList<T>&);
// 多项式求和友元函数,可访问单链表类的私有成员
}; // 结束类接口定义
template<class T>void visitNodeData(T);
// 遍历表中要调用的输出数据域的函数
// T实例化后才能确定访问方式
// 以下为类实现部分
template <class T>LinkedList<T>::LinkedList()
// 构造, 空, 单链表
{ Head=new Node<T>;
// 用头指针申请头结点 (无头结点则 Head=NULL;)
Head->next=NULL; Size=0;
}
template<class T>LinkedList<T>,,LinkedList ( const
LinkedList<T> &obj ) // 由单链表 obj复制构造当前单链表对象
{ Node<T> *q,*p=obj.Head->next; // p指向 obj的首元结点
Head=new Node<T>; // 用头指针申请头结点空间
q=Head; // q初始指向头结点
while(p)
{ q->next=new Node; // 用 q->next申请结点空间
q=q->next; // q移动到新申请结点
q->data=p->data; // 复制结点数据
p=p->next; // p顺链前进到 obj的下一结点
}
q->next=NULL; Size=obj.Size;
}
template<class T>LinkedList<T>::~LinkedList()
// 析构函数
{ Node<T> *q,*p=Head; // p指向头结点
do{ q=p->next; // q指向 p的后继结点
delete p; // 释放 p所指结点空间
p=q; // p指向下一待释放空间的结点
} while(p);
}
template <class T> LinkedList<T>& LinkedList<T>::
operator=(const LinkedList<T>& origin) //,=”重载
{ Node<T> *q,*s,*p = origin.Head;
// p指向 origin表的头结点
q=Head; // q指向当前表 (*this)的头结点
while(p->next && q->next)
// 将 origin表结点数据赋给当前表结点
{ q=q->next; p=p->next; // p,q分别顺链前进
q->data=p->data; // 数据域赋值
}
if(q->next) // 当前表比 origin表长, 需释放其余结点空间
{ p=q->next; // p指向第一个要释放结点
do{ s=p->next; // s指向 p的后继结点
delete p; // 释放 p所指结点空间
p=s; // p指向下一待释放空间结点
}while(p);
} // 注意上面的操作中 q指针没有移动
else
while(p->next) //origin表更长, 申请结点空间复制剩余结点
{ q->next=new Node<T>; // 用 q->next申请结点空间
p=p->next; // p顺链前进到源结点
q=q->next; // q 移动到新申请结点
q->data=p->data; // 数据域赋值
} // end_if
q->next=NULL; // q指向当前表尾结点, 其 next域赋空指针
Size=origin.Size; // 当前表长赋值为 origin表长
return *this; // 返回当前单链表对象
}
template<class T>bool LinkedList<T>::isFull()
// 试着申请结点空间 捕获到异常则无可用的用户空间
{ Node<T> *p;
try{ p = new Node<T>; }
catch(...) {return true;} // 俘获异常, 返回表, 满, 标志
delete p; // 释放刚刚申请的结点空间
return false; // 返回表, 未满, 标志
}
template<class T>bool LinkedList<T>::
GetNode(int i,T& e) // 取第 i个数据元素存入 e
{
if (i<1 || i>Size) // 参数 i无效, 无法取得数据元素
return false;
Node<T> *p=Head->next; // p指向首元结点
for(int j=1; j<i; j++) p=p->next; // 顺链找第 i个结点
e=p->data; return true;
}
template<class T>bool LinkedList<T>::InsertNode(
T x,int i) // 插入结点 x,使其成为表的第 i个元素
{ if(i<1 || i>Size+1) // 参数 i无效, 无法插入
{ cout<<"ERROR,invalid i !!"; return false; }
if(isFull()) // 无可用的用户空间
{ cout<<"ERROR,overflow !!"; return false; }
Node<T> *s,*p=Head; // p指向头结点
for(int j=0; j<i-1; j++) p=p->next; // 寻第 i-1个结点
s=new Node<T>; s->data=x; // 建立插入结点
s->next=p->next; // 新插入结点作为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
Size++; return true; // 表长增 1,插入操作正常完成
}
template<class T>bool LinkedList<T>::InsertNode(T x)
// 插入值为 x的结点, 使保持有序
{ if(isFull()) // 无可用的用户空间
{ cout<<"ERROR,overflow !!"; return false; }
Node<T> *s,*p=Head; // p指向头结点
while(p->next && x>p->next->data) p=p->next;
// 找插入结点的前趋
s=new Node<T>; s->data=x; // 建立插入结点
s->next=p->next; // 新插入结点作为第 i-1个结点的后继
p->next=s; // 原第 i个结点作为新插入结点的后继
Size++; return true; // 表长增 1,插入操作正常完成
}
template<class T>bool LinkedList<T>::
DeleteNode(int i,T &e)
// 删除带头结点的单链表的第 i个数据元素, 被删元素值存入引用参数 x
{ if(i<1 || i>Size) return false; // 参数 i无效, 无法删除
int j=0; Node<T> *q,*p=Head; // p指向头结点
for(j=0; j<i-1; j++) p=p->next; // 寻访第 i-1个结点
q=p->next; // 令 q指向被删除结点
p->next=q->next; // 第 i-1个结点的后继改为原第 i个结点后继
e=q->data; // 被删结点值放入 x
delete q; // 释放被删除结点所占空间
Size--; return true; // 表长减 1,删除操作正常完成
}
template<class T>bool LinkedList<T>::LocateNode(T e)
// 查找值为 e的元素 ;返回 -1表示没找到, 否则返回值是该元素在表中的序号
{ int j=1; Node<T> *p=Head->next; // p指向首元结点
while(p && p->data!=e ) j++,p =p ->next ;
if(p) return j ; else return –1 ;
}
template<class T>int LinkedList<T>::LocateNode
(T e,int low,int up)
//在范围 low-up间找值为 e的元素,返回 -1为没找到, 否则是被查元素的序号
{ int j =1 ;
Node<T> *p = Head->next; // p指向首元结点
while(p && j<low ) j++,p = p->next;
// 找第 low个结点
while(p && j<=up && p ->data!=e)
j++,p =p ->next; // 在结点 low-up间查找 e
if(p && j <= up ) return j; else return–1;
}
template<class T>void LinkedList<T>::traverse (char endchar)
//遍历单链表
{ Node<T> *p=Head->next;
while(p)
{ visitNodeData(p->data) ; p =p->next ; }
cout<< endchar<< "\nLength="<<Size<<"\n";
// endchar是表结束符
}
用带头结点的单链表的模板类定义 重新实现 § 2.3的例 2.3（ 求集
合 A,B的对称差 ?存入集合 A）, 以及利用其它一些基本运算完
成以单链表存储的整数集的集合运算 ∪, ∩的函数如下：
#include "SLList.h"
void Symm_diff(LinkedList<int>&,LinkedList<int>&);
// 求以单链表存储的两个集合“对称差”之原型声明
void CrtLinkList(LinkedList<int>&,int );
// 为集合产生若干互不相等的整数插入链表的原型声明
bool SetUnion(LinkedList<int>&La,LinkedList<int>&Lb);
// 求以单链表存储的集合 A,B的“并” (A∪ B) 的原型声明
void main()
{ LinkedList<int> La,Lb,Lc; // 用 <int>实例化单链表对象
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t; srand((unsigned)time(&t));
// 初始化随时间变化的随机数种子
cout<<"Please input Size of SetA && SetB =? =? ";
cin>>s1>>s2; // 输入集合 A,B元素数
cout<<"\nSet A = { "; // 输出集合 A的名称
CrtLinkList(La,s1); // 产生集合 A的 s1个集合成员并输出之
cout<<"}\n Length="<<s1<<"\n\nSet B = { ";
// 输出 A的成员数、集合 B的名称
CrtLinkList(Lb,s2); // 产生集合 B的 s2个集合成员并输出之
Lc = La; // 用重载的 "="运算符将 La表赋给 Lc表
cout<<" }\nLength="<<s2<<"\n\n(A-B)Union(B-A)={ ";
Symm_diff (La,Lb); // 求 La表与 Lb表的对称差，结果在 La表
La.traverse(?)?); // 输出 A? B所得到的结果表 成员数
cout<<"\nAUnionB={ ";
SetUnion(Lc,Lb); // 求 Lc表与 Lb表的“并”，结果在 Lc表
Lc.traverse(')'); // 输出 A∪ B所得到的结果表、成员数
cout<<"\nAIntersectionB = { ";
Symm_diff(Lc,La); // 求 Lc与 La表的对称差，
// 相当于求 (A∪ B) ? ( A? B) ?A∩B
Lc.traverse(')'); // 输出 A∩B所得到的结果表、成员数
}
void Symm_diff (LinkedList<int>& La,
LinkedList<int>& Lb)
// 求以单链表 La,Lb存储的集合 A,B的对称差
{ int x,i,count=0; // 记录 Lb表中元素插入到 La表中的个数
for(int j=1; j<=Lb.Length(); j++)
{ Lb.GetNode(j,x); // 取 Lb表中元素存入 x
i=La.LocateNode(x,1+count,La.Length());
// 由于集合 B不在集合 A中的元素插入到了 La表头,因此只在 A
// 原来的元素中 1+count~ La.Length() 范围内找即可。
if(i==-1) count++,La.InsertNode(x,1);
// 找不到 x，计数并插入 A集合
else La.DeleteNode(i,x); // 找到 x，则删除之
} // end_for
}
void CrtLinkList(LinkedList<int>& L,int n)
// 为链表 L产生 n个互不相等的整数插入表头
{ int x,i,j;
for(i=0; i<n; i++) // 产生 n个集合元素,不得重复
{ do x=rand() % 37; // 产生 0-36间的随机整数
while((j=L.LocateNode(x))!=-1);
// 在集合中找 x,找不到则脱离循环（要求各元素值不等）
L.InsertNode(x,1); //插入表头
cout<<x<<" "; // 输出 x (集合元素边产生边输出 )
}
}
bool SetUnion(LinkedList<int>&La,
LinkedList<int>&Lb)
// 将 La表和 Lb表所表示的集合做 "并 "，存入 La表,Lb表被清空
{ int m,n,i,k,b; bool r=true;
n=Lb.Length(); // Lb表的初始长度存入 n,删除长度将减小
m=La.Length(); // La表的初始长度存入 m,检查范围 1-m
for(i=n; i>0 && r; i--) // 从 Lb表中删除素尾元素
{ Lb.DeleteNode(i,b); // 调用删除算法
k=La.LocateNode(b,1,m); // 调用查找算法
if(k==-1) r=La.InsertNode(b,La.Length()+1);
// 找不到 b则插入至 la表尾
} //end_for
return r;
}
2.4.3线性表在多项式运算中的应用
在表处理中，常常要用到对符号多项式的处理。在数学
上，一个一元多项式 可按升幂写成：
该多项式是由 n+l个系数唯一确定。因此，在计算机里
，它可用一个线性表 P来表示
其中每一项的指数 i隐含在其系数 pi的序号里 。
设 Qm(x) 是一元 m次多项式，可用线性表 Q来表示：
不失一般性, 设 m<n,则两个多项式相加的结果
可用线性表表示：
我们可以对 P,Q和 R采用顺序存储结构, 也可以采用链
表存储结构 。 使用顺序存储结构可以使多项式相加的算
法十分简单 。 但是, 当多项式中存在大量的零系数时
（ 称这种多项式为稀疏多项式 ）, 顺序存储表示方式就
会浪费大量存储空间 。 例如：多项式 S30000(x)为：
S(x) = 1 + 2x1000 – 4x5000 + 3.5x30000
若采用顺序存储, 就要用一长度为 30001的顺序表来表
示, 表中仅有 3个非零元素 。 为了有效而合理地利用存
储空间, 我们自然会想到只存储非零系数项, 来表示
此类多项式, 但是存储非零系数项的同时必须存储相
应的指数, 才能正确表示这样的一元多项式 。
一般地, 有 m个非零系数项的一元 n次多项式可写成：
其中, 是指数为项的非零系数, 且满足：
那么, 可以用链式存储结构来表示一个长度为 m且每
个元素有两个数据项 （ 系数项和指数项 ） 的线性表 。
也就是说, 用包含 m个结点的单链表便可唯一确定多
项式 。
图 2.15所示为两个如上定义的带头结点的单链表分别表
示多项式可写成：
也就是说, 用包含 m个结点的单链表便可唯一确定多
项式 。
下面我们讨论用单链表表示一元 n次多项式时, 两个
多项式相加 （ 利用原结点空间 ） 的算法, 即要求：
Amax(m,n)(x) = Am(x)+Bn(x)，
算法结束, 结果在 A中, B成为, 空, 。
算法思路,多项式相加的运算规则为：两个多项式中
所有指数相同的项 （ 同类项 ）, 对应系数相加, 若系
数和不为零, 则构成, 和多项式, 的一项；所有指数
不同的项均复抄到, 和多项式, 中 。
我们假定多项式表 A,B已按升幂顺序排列好, 设指针 p,q
分别指向 A,B的当前未处理项中的指数最小项 （ 初始均
指向首元结点 ）, 那么, 多项式相加的过程为：将 p,q所
指结点的指数进行比较, 若 p所指结点的指数小则 p指针
前移, 若 q所指结点的指数小则从 B表中摘除该结点插入
到 A表, q指针前移, 否则是指数相等, 若系数和 ≠0,将
p指结点系数改为系数之和, 反之从 A表删除当前结点,
无论系数和是否为 0,均须从 B表删除当前结点, p,q均
应当前移到下一指数最小项, 重复进行之, 直到 p,q中至
少一个指, 空,, 这时若 q不空, 则将 B表剩余项转移到
A表, 至此算法完成 。
定义多项式的数据项类 polyNode.h的内容为：
class polyData // 多项式的数据项类
{ protected:
int exp; // 指数域
float coef; // 系数域
public:
void GetNode(int &i,float &x)
// 将当前对象的指数,系数取到引用参数 i,x
{ i=exp,x=coef; }
void SetNode(int i,float x)
// 用参数 i,x的值设臵当前对象的指数,系数
{ exp=i,coef=x; }
bool operator<(const polyData& right)
// "<" 运算符重载 (指数域比较 )
{ return exp<right.exp; }
bool operator>(const polyData& right)
// ">,运算符重载 (指数域比较 )
{ return exp>right.exp; }
void operator+=(const polyData& right)
// "+=,运算符重载 (系数域相加 )
{ coef+=right.coef; }
bool coefisZero() // 判断系数域是 0？
{ return coef==0.0; }
};
注意,由于我们在实例化单链表类时, 将 <T>用
<polyData> 具 体 化, 在单链表类中的成员函数
InsertNode(T e) 是按元素 e值的大小插入有序表, 而
polyData的数据元素值有 2个域, 因此我们将比较运
算符 "<",">"重载为左对象与右对象指数比较的结果 。
同理, 运算符 "+="被重载为,"+="号左, 右对象系数
求和赋给左对象 。
// Poly.cpp
#include "SLList.h"
#include "polyNode.h"
void Poly_Add(LinkedList<polyData>&,
LinkedList<polyData>&); //多项式求和
void CrtpolyList(LinkedList<polyData>&);
// 向多项式表插入若干输入项
void main(void)
//从终端读入系数和指数建立 A,B多项式链表,求 A=A+B；
// 并输出原 A,B多项式及和多项式
{ inkedList<polyData> La,Lb;
// 声明单链表对象 La,Lb,<T>被代之为 <polyData>
cout<<"input A coefficient and exponent,
exponent=-1 end!(term<50)\n";
CrtpolyList(La); // 读入若干系数和指数对,插入到 La
cout<<"\n creat polyNom link list A is\n";
La.traverse('/'); // 输出 La表示的多项式 A
cout<<"\ninput B coefficient and exponent,
exponent=-1 end!(term<50)\n";
CrtpolyList(Lb); // 读入若干系数和指数对,插入到 Lb
cout<<"\n creat polyNom link list B is\n";
Lb.traverse('/'); // 输出 Lb表示的多项式 B
cout<<"\n A=A+B outcome is\n";
Poly_Add(La,Lb); // 求和多项式
La.traverse('/'); // 输出和多项式
cout<<"\n";
}
void CrtpolyList(LinkedList<polyData>& L)
// 按升幂序将输入的数据对插入多项式链表 L
{ int i; float x; polyData e;
cin >>i>>x; // 读入 (实数,整数 ) 对,对应于 (系数,指数 )
while(i!=-1) // 读数对插入多项式表,输入 -1为结束标志
{ e.SetNode(i,x); L.InsertNode(e);
cin>>i>>x;
} //按指数序插入有序表
}
void Poly_Add( LinkedList<polyData>& Pa,
LinkedList<polyData>& Pb )
// 求升幂排列的多项式表 Pa与 Pb之和,存入 Pa (利用原结点空间 ),
// 和多项式仍是升幂排列
{ Node<polyData> *p,*q,*r,*s;
int m=Pa.Length(),n=Pb.Length();
int c=0,d=0;
// c统计循环中 Pa增加的项数,d统计循环中 Pb摘除的项数
s=Pa.Head; // s指向和多项式的当前尾结点 (s ->next 指向 p)
p=s->next; q=Pb.Head->next;
//令 p,q分别指向两多项式的首项
while(p && q) //多项式 Pa与 Pb均有未处理的数据项
if(p->data<q->data){ s=p; p=p->next; }
// s,p指针前移 (p所指项的指数较小 )指数序插入有序表
else if(p->data>q->data) //q所指项的指数较小
{ r=q->next; q->next=p; s->next=q;
s=q; q=r; c++; d++;
}
else{ p->data+=q->data;
// 同类项,求系数和存入 p所指项
if((p->data).coefisZero())
// 判断系数和是 0否,是则从 Pa摘除结点
{ s->next=p->next;
delete p; c--;
}
else s=p; // 系数之和 !=0,s前移
// 无论系数和是否为 0,均摘除 Pb中结点
p=s->next; r=q; q=q->next; delete r; d++;
} // 结束 p,q所指项为同类项的处理
if(q)s->next=q; // 若 Pb表中有剩余元素则插入 Pa
Pb.Head->next=NULL,Pb.Size=0; // 臵 Pb表为, 空, 表
Pa.Size=m+c+(n-d); // 计算 Pa表的项数, 臵 Pa表的 Size
}
void visitNodeData(polyData e) // 输出多项式数据域
{ float x; int j;
e.GetNode(j,x);
cout<<"( "<<x<<','<<j<<")→";
}
2.5 小结
本章主要介绍了如下一些基本概念：
线性表 及其 两种存储结构
单链表 循环链表 双链表
给出了线性表的模板类 （ 顺序表, 单链表 ） 并且应
用它们完成了集合运算, 一元多项式的链式表示与
相加等应用实例 。
