第 1 页第 2 页线性表是最简单、也是最基本的一种线性数据结构。其存储表示法主要有两种,顺序存储结构 和 链式存储结构 。这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学习理解和掌握。
学习的意义：
第 3 页
2.1 线性表的类型定义 2.4 有序表
2.1.1 线性表的定义 2.5 顺序表和链表的综合比较
2.1.2 线性表的基本操作
2.2 线性表的顺序表示和实现
2.2.1 顺序表 ——线性表的顺序存储表示
2.2.2 顺序表中基本操作的实现
2.2.3 顺序表其他算法举例
2.3 线性表的链式表示和实现
2.3.1 单链表和指针
2.3.2 单链表的基本操作
2.3.3 单链表的其他基本操作
2.3.4 循环链表
2.3.5 双向链表
主要内容：
第 4 页线性表是 n 个类型相同数据元素的有限序列，表中相邻的数据元素之间存在“序偶”关系。通常记作（ a1,a2,a3,…,a n ）。
姓名 电话号码蔡颖 63214444
陈红 63217777
刘建平 63216666
王小林 63218888
张力 63215555
...
2,1 线性表的类型定义例 1、数学中的数列（ 11,13,15,17,19,21）
例 2、英文字母表（ A,B,C,D,E? Z ）。
例 3、某单位的电话号码簿。
2.1.1 线性表的定义第 5 页
2.1.1 线性表的定义特性,设 A=（ a1,a2,...,ai -1,ai,ai+1,…,a n ） 是一线性表
线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；
在表中 ai-1 领先于 ai,ai 领先于 ai+1,称 ai-1 是 ai 的直接前驱,ai+1 是 ai 的直接后继；
在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；
线性表中元素的个数 n 称为 线性表的长度,n=0 时称为 空表 ；
ai是线性表的第 i 个元素，称 i 为数据元素 ai 的 序号,每一个元素在线性表中的位置，仅取决于它的序号；
第 6 页
2.1.1 线性表的定义
1,二元组表示
L = < D,S >,其中,D = { a1,a2,a3，,...,an}
S = {R} R = {< a1,a2 >,<a2,a3 >,< a 3,a4 > … < a n-1,an> }
线性表的其他表示方式,
2、图形表示顶点：表示数据边：表示是数据间的顺序结构关系
ai+1a1 ai-1a2 ai an
第 7 页
2.1.2 线性表的基本操作
1,初始化线性表 L InitList(&L)
2,销毁线性表 L DestoryList(&L)
3,清空线性表 L ClearList(&L)
4,求线性表 L的长度 ListLength(L)
5,判断线性表 L是否为空 ListEmpty(L)
6,获取线性表 L中的某个数据元素内容 GetElem(L,i,&e)
7,检索值为 e的数据元素 LocateELem(L,e)
8,返回线性表 L中 cur_e的直接前驱元素 PriorElem(L,cur_e,&pre_e)
9,返回线性表 L中 cur_e的直接后继元素 NextElem(L,cur_e,&next_e)
10,在线性表 L中插入一个数据元素 ListInsert(&L,i,e)
(1≦ i≦ ListLength(L)+1)
11,删除线性表 L中第 i个数据元素 ListDelete(&L,i,&e)
(1≦ i≦ ListLength(L))
12,输出线性表 L中的每个数据元素 ListTraverse(L)
第 8 页
2.1.2 线性表的基本操作说明,
1、上面列出的操作，只是线性表的一些常用的基本操作；
2、不同的应用，基本操作可能是不同的；
3、线性表的复杂操作可通过基本操作实现；
第 9 页
2.1.2 线性表的基本操作
【 例 2-1 】 假设线性表 L=(23,56,89,76,18),i=3,x=56,y=88,
则对 L的一组操作及结果如下：
ListLength(L);
GetElem(L,i,e)
PriorElem(L,x,&pre_x)
NextElem(L,x,&next_x)
LocateElem(L,x)
ListInsert(&L,i,y)
ListDelete(&L,i+1,&e)
//结果为 5
//e的值为 89
//pre_x的值为 23
//next_x的值为 89
//结果为 2
//所得结果为 (23,56,88,89,76,18)
//所得结果为 (23,56,88,76,18)
e的值为 89
第 10 页
2.1.2 线性表的基本操作
【 例 2-2 】 利用两个线性表 La和 Lb分别表示两个集合 A和
B，现要求一个新的集合 A=A∪ B。
【 分析 】 这个问题相当于对线性表作如下操作：
扩大线性表 La，将存在于线性表 Lb中而不存在于线性表 La中的数据元素插入到线性表 La中去 。
【 具体步骤 】
（ 1）从线性表 Lb中取得一个数据元素；
（ 2）依该数据元素的值在线性表 La中进行查访；
（ 3）若线性表 La中不存在和其值相同的数据元素，则将从 Lb中删除的这个数据元素插入到线性表 La中；
（ 4）重复以上操作直至 Lb为空表。
第 11 页
2.1.2 线性表的基本操作
【 例 2-2 】 利用两个线性表 La和 Lb分别表示两个集合 A和
B，现要求一个新的集合 A=A∪ B。
【 具体算法 】
void union (List &La,List &Lb)
{
La_len = ListLength (La); //求线性表 La的长度
while ( !ListEmpty(Lb) ) //Lb表中的元素尚未处理完
{
ListDelete (Lb,1,&e); //从 Lb中删除第一个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
DestroyList (Lb); //销毁线性表 Lb
}
该算法运行完后，线性表 Lb被销毁！如果要求 Lb保持原先的值，
算法又如何写？？？【 具体算法 】 ___运行后 Lb仍保持原先的值
i i (List a,ist )
{
a_l istL th (La); //求线性表 La的长度
Lb_len = ListLength (Lb); //求线性表 Lb的长度
for (i = 1; i <= Lb_len; i++) //Lb表中的元素尚未处理完
{
GetElem (Lb,i,&e); //从 Lb中取出第 i个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
}
第 12 页
2.1.2 线性表的基本操作
【 例 2-3 】 已知一个非纯集合Ｂ（ 即集合 B中可能有相同元素），试构造一个纯集合 A，使Ａ中只包含 B中所有值各不相同的成员。
【 分析 】 假设仍以线性表表示集合，则此问题和例 2-2类似，即构造线性表 La，使其只包含线性表 Lb中所有值不相同的数据元素。所不同之处是，操作实施之前，线性表 La不存在，则操作的第一步首先应该构造一个空的线性表，之后的操作步骤和例 2-2相同。
【 具体步骤 】
（ 1）构造一个空的线性表 La；
（ 2）从线性表 Lb中取得一个数据元素；
（ 3）依该数据元素的值在线性表 La中进行查访；
（ 4）若线性表 La中不存在和其值相同的数据元素，则从 Lb中删除的这个数据元素插入到线性表 La中。
（ 5）重复（ 2）至（ 4）的操作直至 Lb为空表为止。
第 13 页
2.1.2 线性表的基本操作
【 例 2-3 】 已知一个非纯集合Ｂ（ 即集合 B中可能有相同元素），试构造一个纯集合 A，使Ａ中只包含 B中所有值各不相同的成员。
【 具体算法 】
void purge (List &La,List &Lb)
{
InitList (La); La_len = 0 //创建一个空的线性表 La
while ( !ListEmpty(Lb) ) //Lb表中的元素尚未处理完
{
ListDelete (Lb,1,&e); //从 Lb中删除第一个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
DestroyList (Lb); //销毁线性表 Lb
}
该算法运行完后，线性表 Lb同样被销毁！如果要求 Lb保持原先的值，算法又如何写？？？【 具体算法 】 ___运行后 Lb仍保持原先的值
i r e (List a,ist )
{
I itList (La); La_len = 0; //创建一个空的线性表 La
Lb_len = ListLength (Lb); //求线性表 Lb的长度
for (i = 1; i <= Lb_len; i++) //Lb表中的元素尚未处理完
{
GetElem (Lb,i,&e); //从 Lb中取出第 i个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
}
第 14 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 分析 】 两个集合相等，指的是这两个集合中包含的成员相同。当以线性表表示集合时，则要求分别表示这两个集合的线性表 La和 Lb，不仅长度相同，所含数据元素也必须一一对应。值得注意的是，两个“相同”的数据元素在各自的线性表中的“位序”不一定相同。因此，如果在一个线性表中找不到和另一个线性表的某个数据元素相同的数据元素，则立即可以得出“两个集合不等”的结论；反之，
只有当判别出“其中一个线性表只包含和另一个线性表相同的全体成员”时，才得出“两个集合相等”的结论。
【 方法一 】 ____使用辅助结构 Lc
（ 1）若线性表 La和线性表 Lb的长度不等，则返回两集合不等；
（ 2）构造一个线性表 Lc；
（ 3）将线性表 La中的数据元素复制到线性表 Lc中，使得 Lc与 La相同；
（ 4）对 Lb中的每个数据元素，在 Lc中进行查询；
（ 5）若 Lc中存在与该数据元素相同的数据元素，则从 Lc中删除该元素；
（ 6）重复（ 4）和（ 5）步，直到 Lb中的数据元素都遍历完为止；
（ 7）如果 Lc为空，则返回两集合相等，否则，返回两集合不等。
第 15 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 具体算法 】 ____方法一
bool isequal (List La,List Lb)
{
if ( ListLength(La) !=
ListLength(Lb) )
return (FALSE);
InitList (&Lc);
La_len = ListLength (La);
Lb_len = ListLength (Lb);
for (k = 1; k <= La_len; k++)
{
GetElem (La,k,e);
ListInsert (&Lc,k,e);
}
found = TRUE;
for (k = 1; k <= Lb_len,found; k++)
{
GetElem (Lb,k,e);
i = LocateElem (Lc,e);
if (i == 0)
found = FALSE;
else
ListDelete (&Lc,i,e);
}
if (found && ListEmpty(Lc))
return (TRUE);
else
return (FALSE);
DestroyList (&Lc);
}
算法中构造的线性表 Lc是一辅助结构，它的引入是为了在程序执行过程中不破坏原始数据 La，因此算法的最后应销毁 Lc！如果不使用辅助结构 Lc，那算法又如何设计呢？？？
第 16 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 方法二 】 ____不使用辅助结构 Lc
（ 1）若线性表 La和线性表 Lb的长度不等，则返回两集合不等；
（ 2）对 Lb中的每个数据元素，在 La中进行查询；
（ 3）若 La中不存在与该数据元素相同的数据元素，则返回两集合不等；
（ 4）重复（ 2）和（ 3）步，直到 Lb中的数据元素都遍历完为止；
（ 5）返回两集合相等。
第 17 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 具体算法 】 ____方法二
bool isequal (List La,List Lb)
{
if ( ListLength(La) != ListLength(Lb) )
return (FALSE);
Lb_len = ListLength (Lb);
for (k = 1; k<= Lb_len; k++)
{
GetElem (Lb,k,e);
i = LocateElem (La,e);
if (i == 0) return (FALSE);
}
return (TRUE);
}
该算法的正确性是因为集合中不存在两个相同的元素！！！！！
第 18 页为了存储线性表，至少要保存两类信息：
1）线性表中的数据元素；
2）线性表中数据元素的顺序关系；
如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？
通常线性表有两种存储表示方法：顺序存储表示和链式存储表示。
第 19 页线性表的顺序存储结构，就是用一组 连续的内存单元 依次 存放线性表的数据元素。
a1
a2
ai-1
ai
ai+1
an
线性表（ a1,a2,a3,..,an ）
的顺序存储结构用顺序存储结构存储的线性表
——称为顺序表
2.2 线性表的顺序表示和实现
2.2.1 顺序表 ——线性表的顺序存储表示第 20 页
2.2.1 顺序表 ——线性表的顺序存储表示说明：
· 在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（
表示）出来；
· 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第 i个元素的存储位置与第 1个元素的存储位置的关系是：
Loc(ai ) = Loc( a1 )+ ( i – 1) t
a1
a2
ai-1
ai
ai+1
an
t个单元
Loc( a1 )
Loc(ai )
第 21 页
2.2.1 顺序表 ——线性表的顺序存储表示怎样在计算机上实现线性表的顺序存储结构？
可用 C语言中的一维数组来表示,但数组不是线性表,因为线性表的长度可变。数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定,如,
#define MAX 100
int v[MAX];
第 22 页
2.2.1 顺序表 ——线性表的顺序存储表示顺序表的类型定义
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct {
ElemType * elem; //线性表存储空间基址 (一维数组 )
int length; //当前线性表长度
int listsize; //当前分配的线性表存储空间大小
int incrementsize; //约定增补空间量 (以 ElemType为单位 )
} SqList;
SqList,类型名，
SqList类型的变量是结构变量，它的四个域分别是：
*elem,存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；
length,存放线性表的表长；
listsize,用于存放当前分配（存放线性表元素）的存储空间的大小。
incrementsize,约定增补空间量（当线性表空间不够时）
第 23 页
2.2.1 顺序表 ——线性表的顺序存储表示存放线性表元素的一维数组设 A = （ a1,a2,a3,..,an ） 是一线性表,L是 SqList 类型的结构变量
，用于存放线性表 A,则 L在内存中的状态如图所示：
顺序表通过元素的存储顺序反映线性表元素间的逻辑关系
a1
a2
ai-1
ai
ai+1
an
0
1
i-2
i-1
i
n-1
99
L.elem
L.lenght
L.Listsize
L.incrementsize
n
99
10
第 24 页功能,构造一个空的顺序表。
方法,首先要按需为其动态分配一个存储区域，然后设其当前长度为０。
2.2.2 顺序表中基本操作的实现
１、初始化操作算法,
void InitList_Sq (SqList &L)
{
L.elem = new ElemType[LIST_INIT_SIZE];
//为顺序表分配初始大小为 LIST_INIT_SIZE的数组空间
L.length = 0; //顺序表中当前所含元素个数为 0
L.listsize = LIST_INIT_SIZE; //该顺序表可以容纳数组元素的个数
L.incrementsize = LISTINCREMENT; //需要扩容时每次可增加的元素个数
}
等价于,L.elem = (ElemType *)
malloc (LIST_INIT_SIZE *
sizeof(ElemType))
第 25 页功能,在顺序表 L中查找其值与给定值 e相等的数据元素的位序，如果未找到，则返回 0。
方法,从第一个元素起，依次和 e相比较，直到找到一个其值与 e相等的数据元素，
则返回它在线性表中的“位序”；或者查遍整个顺序表都没有找到其值和 e相等的元素后返回 0。
2.2.2 顺序表中基本操作的实现
2、查找元素操作算法,（书本上的写法）
int LocateElem_Sq (SqList L,ElemType e)
{
i = 1; //i初始值为第一个元素的位序
p = L.elem; //p的初值为第一个元素的存储位置
while (i <= L.length && *p++ != e) //依次进行判定
++i;
if (i <= L.length) //找到满足判定的数据元素为第 i个元素
return (i);
return (0); //该线性表中不存在满足判定的数据元素
}
算法,（另一种写法）
int LocateElem_Sq (SqList L,ElemType e)
{
for (i = 0; i < L.length; i++)
if (L.elem[i] == e)
return (i+1);
return (0);
}
注意：位序是从 1到
L.length!
第 26 页功能,在顺序表 L 中的第 i ( 1≦ i≦ L.length+1)个数据元素之前插入一个新元素 x。
插入前线性表为：
(a1,a2,a3,…,a i-1,ai,,… a n )
插入后，线性表长度为 L.length+1,线性表为：
(a1,a2,a3,…,a i-1,x,ai,,… a n )
2.2.2 顺序表中基本操作的实现
３、插入元素操作第 27 页
2.2.2 顺序表中基本操作的实现插入前 插入后
_____插入操作示意图
a1
a2
ai-1
ai
ai+1
an
0
1
i-2
i-1
i
n-1
MAX-1
n
P_len
a1
a2
ai-1
x
ai
an
0
1
i-2
i-1
n-2
n-1
n
MAX-1
n+1
P_len
３、插入元素操作一般情况下，在顺序表Ｌ中第 i个元素之前插入一个新的元素时，首先需将 L.elem[L.length-1]至
L.elem[i-1]依次往后移动一个位置。显然，此时顺序表的长度应该小于数组的最大容量；否则，在移动元素之前，必须先为顺序表“扩大数组容量”。
第 28 页
2.2.2 顺序表中基本操作的实现
３、插入元素操作算法,
void ListInsert_Sq (SqList &L,int i,ElemType e)
{
if (i < 1 || i > L.length+1) ErrorMessage (―i值不合法！” );
if (L.length >= L.listsize)
increment (L); //当前存储空间已满，为 L增加 L.incrementsize个元素空间
q = &L.elem[i-1]; //q为插入位置
for (p = &L.elem[L.length-1]; p >= q; --p) //插入位置及之后的元素右移
*(p+1) = *p;
*q = e;
L.length++; //表长增 1
}
void increment (SqList &L)
{
ElemType a[ ]; //ElemType *a;
a = new ElemType[L.listsize+L.incrementsize];
for (i = 0; i < L.length; i++)
a[i] = L.elem[i];
delete [ ]L.elem; //free (L.elem);
L.elem = a;
L.listsize += L.incrementsize;
}
可用 realloc (L.elem,
(L.listsize+L.incrementsize)*s
izeof(ElemType));来代替
void ErrorMessage (char *s)
{
cout << s << endl; //printf (“%s\n”,s);
exit (1);
}
一般情况下，当插入位置 i=L.length+1时,for循环的执行次数为
0，即不需要移动元素；反之，若 i=1，则需将顺序表中全部（ n
个）元素依次向后移动。然而，当顺序表中数据元素已占满空间时，不论插入位置在何处，为了扩大当前的数组容量，都必须移动全部数据元素，因此，从最坏的情况考虑，顺序表插入算法的时间复杂度为 O(n)，其中 n为线性表的长度。
第 29 页删除算法的主要步骤,
1）若 i 不合法或表 L空，算法结束，并返回 0； 否则转 2）
2） 将第 i个元素之后的元素（不包括第 i个元素）依次向前移动一个位置 ;
3）表长 - 1
2.2.2 顺序表中基本操作的实现功能,在顺序表 L 中删除第 i ( 1≦ i≦ L.length)个数据元素。
删除前线性表为：
(a1,a2,a3,…,a i-1,ai,ai+1,… a n )
删除后，线性表长度为 L.length-1,线性表为：
(a1,a2,a3,…,a i-1,ai+1,,… a n )
4、删除元素操作一般情况下，从顺序表Ｌ中删除第 i个元素时，需将 L.elem[i]至 L.elem[L.length-1]的元素依次往前移动一个位置。
第 30 页
2.2.2 顺序表中基本操作的实现
３、删除元素操作算法,
void ListDelete_Sq (SqList &L,int i,ElemType &e)
{
if (i < 1 || i > L.length) ErrorMessage (―i值不合法！” );
p = &L.elem[i-1]; //p为被删除元素的位置
e = *p; //被删除元素赋值给 e
q = L.elem + L.length –1; //表尾元素的位置
for (++p; p <= q; p++) //被删除元素之后的元素左移
*(p-1) = *p;
L.length--; //表长减 1
}
等价于：
e = L.elem[i-1];
memcpy (L.elem+i-1,L.elem+i,
(L.length-i)*sizeof(ElemType));
或
memmove (L.elem+i-1,L.elem+i,
(L.length-i)*sizeof(ElemType))
和插入的情况相类似，当删除的位置 i=L.length时，算法中
for循环的执行次数为 0，即不需要移动元素；反之，若 i=1，则需将顺序表中从第 2个元素起至最后一个元素（共 n个元素）依次向前移动一个位置。因此，顺序表删除元素算法的时间复杂度也为
O(n),其中 n为线性表的长度。
第 31 页
2.2.2 顺序表中基本操作的实现
5、销毁结构操作功能,和结构创建相对应，当程序中的数据结构不再需要时，
应该及时进行“销毁”，并释放它所占的全部空间，以便使存储空间得到充分的利用。
算法,
void DestoryList_Sq (SqList &L)
{
delete [ ]L.elem; //free(L.elem);
L.listsize = 0;
L.length = 0;
}
第 32 页
2.2.2 顺序表中基本操作的实现
6、其他操作对于顺序表来说，其他的操作很容易实现。请同学们在课后自己独立完成！
第 33 页
2.2.2 顺序表中基本操作的实现插入位置 移动元素个数
1 n
2 n-1
i n-i+1
n 1
n+1 0
（ 1）插入算法时间复杂度分析算法时间复杂度取决于移动元素的个数,移动元素的个数不仅与表长有关，而且与插入位置有关。
a1
a2
ai-1
ai
ai+1
an
0
1
i-1
i-2
n-1
.
.
7、插入和删除操作的时间分析第 34 页
（ 1）插入算法时间复杂度分析由此可见,
·在顺序表中插入一个元素,平均要移动表的一半元素。
·表长为 n的顺序表，插入算法的时间复杂度为 O（ n）
E i n =
1
1
n
i
p i (n – i +1)
假设在线性表的任何位置插入元素的概率相同，即
pi= 1/(n+1)
pi:在第 i个元素之前插入元素的概率，在长度为 n的顺序表中插入一个元素，所需移动元素个数数学期望值为：
ninnE in
n
i 2
1)1(
1
1 1
1
第 35 页
（ 2）删除算法时间复杂度分析由此可见,
·在顺序表中删除一个元素,平均要移动表的一半元素。
·表长为 n的顺序表，删除算法的时间复杂度为 O（ n）
E dl =?
n
i 1
q i (n – i )
假设在线性表的任何位置删除元素的概率相同，即
qi= 1/n
qi：删除第 i个元素的概率，在长度为 n的顺序表中删除一个元素，所需移动元素个数数学期望值为：
ninnE d l
n
i 2
1)(1
1
第 36 页
2.2.3 顺序表其他算法举例
【 例 2-5 】设 A=(a1,a2,…,am )和 B=(b1,b2,…,bn )均为顺序表，试比较 A,B的大小 。
【 分析 】 这是对两个顺序表进行比较的操作，因此在算法中不应该破坏已知表。从题目的要求看，只有在两个表的长度相等，且每个对应元素都相同时才相等；否则两个顺序表的大小主要取决于两表中除去前面相同的元素后的第一个元素。
【 具体步骤 】
（ 1）设一变量 j（初值为 1）；
（ 2）当 j小于 A的长度和 B的长度时，若 aj<bj，则返回 -1，若
aj>bj时，则返回 1，否则 j++;
（ 3）重复第（ 2）步，直到 j大于 A或 B的长度；
（ 4）如果 A的长度等于 B的长度，则返回 0；如果 A的长度小于 B
的长度，则返回 -1；否则返回 1。
第 37 页
2.2.3 顺序表其他算法举例
【 例 2-5 】设 A=(a1,a2,…,am )和 B=(b1,b2,…,bn )均为顺序表，试比较 A,B的大小 。
【 具体算法 】
int compare (SqList A,SqList B)
{
j = 1;
while (j <= A.length && j <= B.length)
if (A.elem[j] < B.elem[j]) return (-1);
else if (A.elem[j] > B.elem[j]) return (1);
else j++;
if (A.length == B.length) return (0);
else if (A.length < B.length) return (-1);
else return (1);
}
等价于：
If (j < A.length) return (1);
else if (j < B.length) return (-1);
else return (0);
此算法中只有一个 while循环，它的执行次数依赖于待比较的顺序表的表长。因此算法的时间复杂度为：
O(Min(A.length,B.length))
第 38 页
2.2.3 顺序表其他算法举例
【 例 2-6 】设计一个算法，用尽可能少的辅助空间将顺序表中的前 m
个元素和后 n个元素进行整体互换。即将线性表
（ a1,a2,…,am,b1,b2,…,bn） 改变成
（ b1,b2,…,bn,a1,a2,…,am）
【 分析 】 此题的难点在于要求用尽可能少的辅助空间。如果没有这个限制，可以另设一个和已知顺序表空间大小相同的顺序表，然后进行元素复制即可。
【 具体算法 】 ___借助于辅助空间
void exchang (SqList &A,int m,int n)
{
ElemType a[ ]; //ElemType *a;
a = new ElemType[A.length]; //a=(ElemType *)malloc
(A.length*sizeof(ElemType));
memcpy (a,A.elem+m,n*sizeof(ElemType));
memcpy (a+n,a.elem,m*sizeof(ElemType));
delete [ ]A.elem; //free (A.elem);
A.elem = a;
}
第 39 页
2.2.3 顺序表其他算法举例
1 2 … k-1 k k+1 … m+k-1 m+k … m+n
b1 b2 … bk-1 a1 a2 … … … am bk bk+1 … bn
b1 b2 … bk-1 a1 a2 … … … am bk+1 … bn
【 例 2-6 】线性表数据互换。
【 方法一 】 从表中第 m+1个元素起依次插入到元素 a1之前，则首先需将该元素 bk（ k=1,2,…,n ）暂存在一个辅助变量中，然后将它之前的 m个元素（ a1,a2,…,am ）依次后移一个位置。
b1 b2 … bk-1 bk a1 a2 … … … am bk+1 … bn
w
w
_______将 bk插入到（ a1,a2,…,a m）之前的过程
【 具体算法 】 ___方法一
void exchang (SqList &A,int m,int n)
{
for (k = 1; k <= n; k++)
{
w = A.elem[m+k-1];
for (j = m+k-1; j >=k; j--)
A.elem[j] = A.elem[j-1];
A.elem[k-1] = w;
}
}
算法的复杂度,由于对每一个 bk都需要移动 m个元素，
因此算法的时间复杂度为 O(m*n)。
第 40 页
2.2.3 顺序表其他算法举例
1 2 … i i+1 … i+k i+k+1 i+m-1 i+m … … n
a1 a2 … ai ai+1 … ai+k ai+k+1 … ai+m-1 ai+m … … an
【 例 2-6 】线性表数据互换。
【 方法二 】 先将线性表“逆置”成（ bn,…,b2,b1,am,…,a2,a1 ），
然后分别再对前 n个元素（ bn,…,b2,b1 ）和后 m个元素
（ am,…a2,a1 ）进行“逆置”，便可得到所求结果。
_______顺序表中部分元素（ ai,ai+1,…,a i+m）逆置前后的状况
a1 a2 … ai+m ai+m-
1
… ai+k+1 ai+k … ai+1 ai … … an
【 具体算法 】 ___方法二
void invert (ElemType &R[ ],int s,int t)
{
for (k = s; k <= (s+t)/2; k++)
{
w = R[k];
R[k] = R[t-k+s];
R[t=k+s] = w;
}
}
void exchange2 (SqList &A,int m,int n)
{
invert (A.elem,0,m+n-1);
invert (A.elem,0,n-1);
invert (A.elem,n,m+n-1);
}
算法的时间复杂度为：
O(t-s+1)。
算法的时间复杂度为：
O(m+n),O(n),O(m)，
按最坏情况估计为：
O(m+n)。
第 41 页
2.2.3 顺序表其他算法举例
【 例 2-7 】已知一个非纯集合 B（即集合 B中可能有相同元素），试构造一个纯集合 A，使 A中只包含 B中所有值各不相同的成员。（假设以顺序线性表表示集合）。
【 方法 】 依次取得顺序表 B中的元素，在顺序表 A中进行查询，若没有值相同的元素出现，则将它插入到 A的表尾。 B中的第一个元素必定会插入到 A中，因此对它不再进行查询，而是直接“复制”到 A表中 。
【 具体算法 】
void purge_Sq (SqList &A,SqList &B)
{
A.elem[0] = B.elem[0];
A.length = 1;
for (i = 1; i < B.length; i++)
{
e = B.elem[i];
j = 0;
while (j < A.length && A.elem[j] != e) j++;
if (j == A.length)
{
A.elem[A.length] = e;
A.length++;
}
}
}
算法的复杂度,O(n2)，其中 n为 B表的长度 。
第 42 页线性表的顺序表示和实现小结：
顺序表是线性表最简单的一种存储结构小 结顺序表的特点：
1 通过元素的存储顺序反映 线性表中数据元素之间的逻辑关系；
2 可随机存取顺序表的元素；
3 顺序表的插入、删除操作要通过移动元素实现；
第 43 页
2.3 线性表的链式表示和实现线性表的链式存储结构是用一组 任意 的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。
ai+1a1 ai-1a2 ai an
第 44 页
2.3.1 单链表和指针
a4
a3
a1
a2
0
1010
1024
1014
1010
1012
1014
1016
1018
1020
1022
1024
1026
用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。
用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的
ai-
1
aia2a1 ai+1 na
H
第 45 页结点,数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点 ；
结点的数据域,结点中用于保存数据元素的部分 ;
结点的指针域,结点中用于保存数据元素直接后继存储地址的部分 ;
线性链表有关术语
2.3.1 单链表和指针结点 数据域 指针域存储后继结点存储地址存储数据元素第 46 页头指针,用于存放线性链表中第一个结点的存储地址 ;
空指针,不指向任何结点，线性链表最后一个结点的指针通常是指空指针，用 NULL表示 ;
线性链表的每个结点中只有一个指针域故也称为 单链表
线性链表有关术语
2.3.1 单链表和指针
ai-1 aia2a1 ai+1 nan
H
空指针头指针第 47 页怎样在计算机上实现线性链表？
2.3.1 单链表和指针第 48 页
2.3.1 单链表和指针结点变量图示
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
LNode,结构类型名；
LNode类型结构变量有两个域：
data,用于存放线性表的数据元素，
next,用于存放元素直接后继结点的地址；
·该类型结构变量用于表示线性链表中的一个结点；
LNode *p,p为指向结点 (结构 )的指针变量；
LinkList H,头指针为 H的单链表；
数据域 指针域
data next
LNode类型结构变量
p
p是 LNode类型的指针变量
单链表的结点类型定义及指向结点的指针类型定义第 49 页
2.3.1 单链表和指针方法一：
LNode *p;
p = new LNode;
方法二：
p = (LNode *) malloc ( sizeof (LNode ) );
单链表中结点的创建
p
第 50 页
2.3.1 单链表和指针调用 free ( p )
0
1
2
99
p
调用 free ( p ) 图示
delete p 或 free ( p )
功能：将指针变量 p所指示的存储空间，回收到系统内存空间中去使用方法：
...
LNode *p;
p = (LNode *) malloc (sizeof (LNode));
// 一旦 p所指示的内存空间不再使用，
//调用 free( ) 回收之
free(p);
第 51 页
2,3,2 单链表的基本操作如何在线性链表上实现线性表的基本操作？
如何插入？删除？查找元素？
nai-1 aia2a1 ai+1 a
H
第 52 页
2,3,2 单链表的基本操作
【 分析 】 当以单链表表示线性表时，整个链表由一个“头指针”
来表示，线性表的长度即为链表中的结点个数，只能通过“遍历
‖链表来实现。
1、求线性表的长度
【 具体算法 】
int ListLength_L (LinkList L)
{
p = L; k = 0;
while (p)
{
k++; p = p->next;
}
return (k);
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 53 页
2,3,2 单链表的基本操作
2、查找元素操作
【 分析 】 在单链表 L中查找和给定值 e相等的数据元素的过程和顺序表类似，从第一个结点起，依次和 e相比较，直到找到一个其值和 e相等的元素，则返回它在链表中的“位置”；或者查遍整个链表都不存在这样的一个元素后，返回,NULL‖。
【 具体算法 】
LNode * LocateElem_L (LinkList L,ElemType e)
{
p = L;
while (p && p->data != e)
p = p->next;
return (p);
}
注意,返回值为结点值为 e的指针算法的时间复杂度,O(n)，其中 n为表长 。
第 54 页
2,3,2 单链表的基本操作
yx
3、插入结点操作
【 分析 】 由于在单链表中不要求两个互为“前驱”和“后继”的数据元素紧挨存放，则在链表中插入一个新的数据元素时，不需要移动数据元素，而只需要在链表中添加一个新的结点，并修改相应的指针链接。插入操作分为：后插和前插。
z
p
as
后插（在 p所指结点后插入 s所指的结点）
（ 1） S->next = p->next
（ 2） p->next = s
第 55 页
2,3,2 单链表的基本操作
yx
3、插入结点操作
z
p
as
前插（在 p所指结点前插入 s所指的结点）
（ 1） q->next = s
（ 2） s->next = p
q
前插时，首先要找到插入结点 p的前驱结点的指针 q，
然后才能进行插入操作。要找到前驱结点，这只要从链表的头指针起进行查询即可。令 q的初始值等于头指针，查找结束的条件是 q->next == p；若否，则指针 q后移。还有一点要注意的是，如果 p所指结点是链表中的第一个结点，则
“前插”操作尚需修改链表的头指针。
第 56 页
2,3,2 单链表的基本操作
3、插入结点操作
【 具体算法 】
void * ListInsert_L (LinkList &L,LNode *p,LNode *s,char mode)
{
if (p == L) //将 s结点插入到链表的第一个结点之前
{ s->next = L; L = s; return; }
if (mode ==?A‘) //后插
{ s->next = p->next; p->next = s; return; }
q = L; //前插
while (q->next != p)
q = q->next;
q->next = s;
s->next = p;
}
算法的时间复杂度：
后插 O(1)，前插 O(n)，其中 n为表长 。
第 57 页
2,3,2 单链表的基本操作
x
4、删除结点操作
【 分析 】 和插入类似，在单链表中删除一个结点时，也不需要移动数据元素，仅需修改相应的指针链接。但由于删除结点时，需要修改的是它的“前驱”结点的指针域，因此和“前插”操作一样，首先应当找到它的前驱结点。
zy
p
（ 1） q->next = p->next;
（ 2） free (p);
q
第 58 页
2,3,2 单链表的基本操作
4、删除结点操作
【 具体算法 】
void * ListDelete_L (LinkList &L,LNode *p,ElemType &e)
{
if (p == L) //删除链表中第一个结点，修改链表头指针
L = p->next;
else
{
q = L; //查找被删除结点的前驱结点的指针
while (q->next != p)
q = q->next;
q->next = p->next; //修改 q结点的指针域
}
e = p->data; delete p; //返回被删除结点的数据元素，并释放结点空间
}
算法时间复杂度,O(n)，其中 n为表长 。
第 59 页
2,3,3 单链表的其他基本操作举例
【 分析 】 链表是一种动态管理的结构，它和顺序表不同，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统根据需求即时生成的。因此
，建立链表的过程是一个动态生成的过程。即从“空表”起，依次建立结点，并逐个插入链表。所谓“逆序”创建链表指的是，依和线性表的逻辑顺序相“逆”
的次序输入元素，逆序生成链表可以为处理头指针提供方便。
【 例 2-8 】逆序创建链表。
a b c d e ^
b c d e ^
c d e ^
d e ^
e ^
^
e ^
d
c
b
a
线性表
(a,b,c,d,e)的逆序创建过程：
第 60 页
2,3,3 单链表的其他基本操作举例
【 例 2-8 】逆序创建链表。
【 具体算法 】
void CreateList_L (LinkList &L,ElemType A[ ],int n)
{
L = NULL; //建立一个空的单链表
for (i = n-1; i >= 0; i--)
{
s = new LNode; //生成新结点
s->data = A[i]; //赋元素值
s->next = L; //插入在第一个结点之前
L = s;
}
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 61 页
2,3,3 单链表的其他基本操作举例
【 例 2-9 】逆置单链表。
【 分析 】 若对顺序表中的元素进行逆置可以借助“交换”前后相应元素来完成。
而对单链表进行逆置，则不能如法炮制。因为对于链表中的第 i个结点，都需要顺链查找第 n-i+1（设链表长度为 n）个结点，将使逆置链表操作的时间复杂度达到
O(n2)。因此逆置单链表的操作应借助修改链表中的指针来完成。
【 方法 】 设想逆置后的单链表是一个新建的链表，但表中的结点不是新生成的，
而是从原（待逆置的）链表中依次“删除”得到。由此，逆置单链表的操作可类似上例逆序创建链表进行：设逆置链表的初态为一空表，“删除”已知链表中的第一个结点，然后将它“插入”到逆置链表的“表头”，即使它成为逆置链表中
“新”的第一个结点，如此循环，直到原链表为空表止。
第 62 页
2,3,3 单链表的其他基本操作举例
【 例 2-9 】逆置单链表。
a1 a2 a3 a4 a5 ^
head
(a) 逆置前的链表
(b) 逆置后的链表
a1 ^ a2 a3 a4 a5
head
(c) 逆置过程中的链表
a1 ^ a2 a3 a4 a5 ^
head
s p
第 63 页
2,3,3 单链表的其他基本操作举例
【 例 2-9 】逆置单链表。
【 具体算法 】
void InvertLinkedList (LinkList &L)
{
p = L; L = NULL; //设逆置后的链表的初态为空表
while ( p ) //p为待逆置链表的头指针
{
s = p; p = p->next //从 p所指链表中删除第一个结点（ s结点）
s->next = L; L = s; //将 s结点插入到逆置表的表头
}
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 64 页
2,3,3 单链表的其他基本操作举例
【 方法 】 设线性表 A,B分别用头指针为 head_a,head_b
的两个带头结点的线性链表存储,归并后的递减有序表头指针为 head,将两表数据较小的结点依次取出插入到新表
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 65 页
2,3,3 单链表的其他基本操作举例
73 n9
52 n7
head_a
head_b
79 n2
head
38 7
8
5
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 66 页
【 具体算法 】
LNode * merge_link ( LinkList &head_a,LinkList &head_b)
{
LNode *p,*q;
LinkList head;
head = (LNode *) malloc (sizeof (LNode));
head->next = NULL;
p = head_a->next; q = head_b->next;
while ( (p != NULL) && (q != NULL) )
If (p->data < q->data)
{ head_a->next = p->next; p->next = head->next;
head->next = p; p = head_a->next; }
else { head_b->next = q->next; q->next = head->next;
head->next = q; q = head_b->next; }
2,3,3 单链表的其他基本操作举例
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 67 页
while (p != NULL)
{
head_a->next = p->next; p->next = head->next;
head->next = p; p = head_a->next;
}
while(q!=NULL)
{
head_b->next = q->next; q->next = head->next;
head->next = q; q = head_b->next;
}
free (head_a); free (head_b);
return (head);
}
2,3,3 单链表的其他基本操作举例
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 68 页线性链表小结线性链表是线性表的一种链式存储结构线性链表的特点
1 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；
2 插入删除操作通过修改结点的指针实现；
3 不能随机存取元素；
第 69 页
1 循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点
2 循环链表图示
2,3,4 循环链表
(a)非空表 （ b） 空表
head
head
a1 an
第 70 页
2,3,4 循环链表说明,
· 在 解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；
· 循 环链表与单链表操作的主要差别是算法中循环结束的条件不是 p或 p->link是否为 NULL，而是它们是否等于首指针；
· 对 循环链表，有时不给出头指针，而是给出尾指针
aa1 an
给出尾指针的循环链表第 71 页
2,3,4 循环链表
b
aa
1
a
n
bb
1
b
n
aa
1
a
n
b
1
b
nq
q
p
p
两循环链表合并：
p = a->next;
q = b->next;
a->next = q->next;
b->next = p;
free (q);
第 72 页
1 双向链表的概念
2,3,5 双向链表
(a)结点图示数据域指针域 指针域结点存储数据元素存储后继结点的地址存储前趋结点的地址双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。
第 73 页
2.3.5 双向链表
2 双向链表图示
head
(b)空的双向循环链表
（ c） 非空 的双向循环链表
head a b
typedef struct DuLNode
{
ElemType data;
struct DuLNode * prior,*next;
} DuLNode,*DuLinkList;
第 74 页在双向链表中删除结点时指针变化情况在双向链表中插入一个结点时指针的变化情况
p
ai-1
x①
②
③
④
ai
pai ai+1
①
②
ai-1
2.3.5 双向链表
3、双向链表的基本操作算法第 75 页
2.3.5 双向链表
p->prior = q;
1）插入操作算法 (在 p 所指结点之前插入 q 结点的过程 )
q = (DuLNode *) malloc (sizeof (DuLNode));
q->data = x;
q->prior = p->prior;
p->prior->next = q;
q->next = p; ai-1
① ② ③④
ai
p
x
q
第 76 页
2.3.5 双向链表
free (p);
ai+1
①
②
ai-1
2）删除操作算法 (删除 p所指向的结点 )
(p->prior)->next = p->next;
(p->next)->prior = p->prior;
ai
p
第 77 页链表结构的讨论
通常链表的定义定义为一个指向链表中第一个结点或头结点的头指针。
好处,定义简单不足,虽然可以完成线性表的任何操作，但给某些“简单操作”
带来不便。例如，求线性表的长度，在表中最后一个元素后面插入或删除最后一个元素等，对顺序表而言，其时间复杂度为 o(1)，
而对于链表来说，则为 o(n)。
第 78 页链表结构的讨论
通常链表的改进链表的定义中加上“头指针”、“尾指针”和“链表长度”三个域。
typedef struct
{
LinkList head,tail; //头指针、尾指针
int length; //链表长度
} AdvancedLinkList;
第 79 页
2.4 有序表若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值递减会递增有序排列，即 ai≧ ai-1 或 ai≦ ai-1
（ i=2,3,…,n ），则称该线性表为 有序表 （ ordered list）。
有序表的基本操作和线性表大致相同，但由于有序表中的数据元素有序排列，因此在有序表中插入元素的操作应按“有序关系”进行。和线性表相同，有序表也可以有 顺序表 和 链表 两种存储表示方法。
假设某有序表以顺序表的形式存储，其数据元素依值递增排列，先要插入一个新的数据元素 x，则应该使插入之后的顺序表仍保持有序表的特性。
【 具体算法 】
void OrdInsert_Sq (SqList &L,ElemType x)
{
i = L.length – 1;
while (i >=0 && x < L.elem[i])
{
L.elem[i+1] = L.elem[i]; //值大于 x的元素后移
i--;
}
L.elem[i+1] = x; //插入元素 x
L.length++; //表长增 1
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 80 页
2.4 有序表
【 例 2-11 】 以顺序有序表表示集合，由一个非纯集合 B构造一个纯集合 A，使 A中只包含 B中所有值各不相同的成员 。
【 分析 】 由于此例中操作的对象是“有序表”，则表中所有值相同的元素必定连续出现。则在 La表中进行“查访”的操作变得简单化了，因为不需要在整个 La表中进行“查访”，而只要和 La表中最后一个元素比较即可。同时，由于 La表的表长不会大于 Lb表，则可用同一个顺序表表示。换个角度看问题，当前要实现的算法功能是从一个以顺序表表示的有序表中“删除”所有值相同的多余元素，而使所有值不相同的元素均压缩到顺序表的前部空间中。
【 具体算法 】
void purge_Osq (SqList &L)
{
i = 0; j = 1;
while (j < L.length)
{
if (L.elem[i] != L.elem[j])
{ L.elem[i+1] = L.elem[j]; i++; }
j++;
}
L.length = i + 1;
}
（ 1） ―删除”的操作是隐含的，仅以
j++操作代替。（ 2）逻辑上的两个线性表 La和 Lb用同一顺序有序表 L表示。
（ 3） i指示 La表中“当前所含”的最后一个元素,j指示 Lb表中“当前被考察”
的元素。（ 4）若该元素和 La中最后一个元素不等，则说明它不是“多余”的，
应当“插入”到 La表中；否则“不予理睬”，继续考察 Lb表中下一个元素。
算法的时间复杂度,O(n)，其中 n为表长 。
第 81 页
2.4 有序表
【 例 2-12 】 分别以两个（带头结点的）循环有序链表表示集合 A和 B，
完成求这两个集合的并集 C（ C = A∪ B）的操作。集合 C仍以循环有序链表表示，并且不另分配新的空间，而是利用集合 A和 B的结点来构造集合 C的链表 。操作完成后，集合 A和 B的链表不再存在。
【 分析 】 根据并集的定义,C的成员应为 A的成员和 B的成员之“和
”，相同的成员只取一个，则可从 C为空集起，逐个将集合 A和 B中不同的成员插入到集合 C中。换句话说,C的链表中的结点或“取自
” A的链表，或“取自” B的链表。
第 82 页
2.4 有序表
【 例 2-12 】 分别以两个（带头结点的）循环有序链表表示集合 A和 B，完成求这两个集合的并集 C（ C
= A∪ B）的操作。集合 C仍以循环有序链表表示，并且不另分配新的空间，而是利用集合 A和 B的结点来构造集合 C的链表 。操作完成后，集合 A和 B的链表不再存在。
【 方法 】 利用链表中结点元素“有序”的特性，可作如下处理,（ 1）设置三个指针,pa,pb和 rc，其中 pa和 pb分别指向集合 A和 B的链表中某个结点,rc指向
C链表中最后一个结点；（ 2）若 pa->data < pb->data，说明 pa所指结点的元素在 B表中不可能出现，应将 pa结点链接到 C链表中（ rc->next = pa）；（ 3）若
pa->data > pb->data，则说明 pb所指结点的元素在 A表中不可能出现，应将 pb
结点链接到 C链表中（ rc->next = pb）；（ 4）若 pa->data = pb->data，则应将其中任一结点（ pa或 pb所指）链接到 C链表中，并释放另一结点空间。
指针 pa和 pb的初始状态,若链表不空，则分别指向各自链表中第一个结点；
否则指向头结点，指针 rc指向 C链表的头结点。
重复操作的条件是,A表和 B表都“不空”；反之表明至少有一个表已经处理完毕，即该链表中的结点或已链接到 C表中，或已释放。此时，只需将“剩余”
结点链接到 C链表中即可。
第 83 页
2.4 有序表
(a) 操作之前的链表
La4 7 10 21 40 56
7 9 21 Lb68
La4 7 10 21 40 56
9 21 Lb68
rc pa
pb
(b) 操作过程中的链表求“并集”操作示意图第 84 页
2.4 有序表求“并集”操作示意图
(c) 操作完成之后的链表
4 7 10 21 40 56
9 La68
第 85 页
2.4 有序表 ang【 具体算法 】
void union_OL (LinkList &La,LinkList &Lb)
{
pa = La->next->next; //pa指向 A中当前考察的结点
pb = Lb->next->next; //pb指向 B中当前考察的结点
rc = La->next; //rc指向 C当前的表尾结点
while (pa != La->next && pb != Lb->next)
{
if (pa->data < pb->data) //链接 A的结点,pa指向 A中下一结点
{ rc->next = pa; rc = pa; pa = pa->next; }
else if (pa->data > pb->data) //链接 B的结点,pb指向 B中下一结点
{ rc->next = pb; rc = pb; pb = pb->next; }
else //链接 A的元素，释放 B的结点,pa,pb分别指向各自下一元素
{
rc->next = pa; rc = pa; pa = pa->next;
qb = pb; pb = pb->next; delete qb;
}
} //while
if (pb == Lb->next)
rc->next = pa; //链接 A的剩余段
else
{
rc->next = pb; pb = Lb->next; //pb指向 B的头结点
Lb->next = pa; La = Lb; //构成 C的循环链
}
delete pb; //释放 B表的表头
}
算法的时间复杂度,O(m+n)，其中 m,n分别为两个表的长度 。
第 86 页
2.4 有序表【 改进算法 】void union_OL_1 (LinkList &La,LinkList &Lb)
{
La->next->data = MAX; Lb->next->data = MAX;
pa = La->next->next; //pa指向 A中当前考察的结点
pb = Lb->next->next; //pb指向 B中当前考察的结点
rc = La->next; //rc指向 C当前的表尾结点
while (pa != La->next || pb != Lb->next)
{
if (pa->data < pb->data) //链接 A的结点,pa指向 A中下一结点
{ rc->next = pa; rc = pa; pa = pa->next; }
else if (pa->data > pb->data) //链接 B的结点,pb指向 B中下一结点
{ rc->next = pb; rc = pb; pb = pb->next; }
else //链接 A的元素，释放 B的结点,pa,pb分别指向各自下一元素
{
rc->next = pa; rc = pa; pa = pa->next;
qb = pb; pb = pb->next; delete qb;
}
} //while
rc->next = La->next; //封闭链环
delete Lb->next; //释放 B表的表头
}
算法的时间复杂度,O(m+n)，其中 m,n分别为两个表的长度 。
第 87 页
2.4 有序表
【 例 2-13 】 假设以有序链表表示集合，设计算法判别两个给定集合是否相等。
【 分析 】 两个集合相等的条件是不仅长度相同，各个对应元素都相等。由于此例中以有序链表表示集合，则只要同步扫描两个链表，
若从头至尾每个对应的元素都相等，则表明两个集合相等。
【 具体算法 】
void isequal_OL (LinkList A,LinkList B)
{
pa = A->next; pb = B->next;
while (pa && pb && pa->data == pb->data)
{ pa = pa->next; pb = pb->next; }
if (pa == NULL && pb == NULL) return (TRUE);
return (FALSE);
}
算法的时间复杂度,O(n)，其中 n为集合的大小 。
第 88 页
2.5 顺序表和链表的综合比较线性表和有序表有两种存储表示,顺序表和链表顺序表：
需要预分配一定长度的存储空间。太大易造成存储空间的浪费，太小又将造成频繁地进行存储空间的再分配。
顺序表是一种随机存储的结构，对顺序表中任一元素进行存取的时间相同。
顺序表对插入、删除操作需要移动近一半的数据元素 。
链表：
存储分配灵活，链表中的结点可在程序执行过程中动态生成。
链表是一种顺序存储的结构，对链表中的每个结点都必须从头指针所指结点起顺链扫描。
链表对插入、删除操作不需要移动数据元素 。
第 89 页第二章 线性表小结本章学习了线性表的顺序存储结构 ——顺序表，链式存储结构,
线性链表,循环链表,双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，
线性表的同一操作的算法是不同的，在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实的基础。
第 90 页习 题
P43,
2.5 2.7 2.8 2.9 2.11 2.13
学习的意义：
第 3 页
2.1 线性表的类型定义 2.4 有序表
2.1.1 线性表的定义 2.5 顺序表和链表的综合比较
2.1.2 线性表的基本操作
2.2 线性表的顺序表示和实现
2.2.1 顺序表 ——线性表的顺序存储表示
2.2.2 顺序表中基本操作的实现
2.2.3 顺序表其他算法举例
2.3 线性表的链式表示和实现
2.3.1 单链表和指针
2.3.2 单链表的基本操作
2.3.3 单链表的其他基本操作
2.3.4 循环链表
2.3.5 双向链表
主要内容：
第 4 页线性表是 n 个类型相同数据元素的有限序列，表中相邻的数据元素之间存在“序偶”关系。通常记作（ a1,a2,a3,…,a n ）。
姓名 电话号码蔡颖 63214444
陈红 63217777
刘建平 63216666
王小林 63218888
张力 63215555
...
2,1 线性表的类型定义例 1、数学中的数列（ 11,13,15,17,19,21）
例 2、英文字母表（ A,B,C,D,E? Z ）。
例 3、某单位的电话号码簿。
2.1.1 线性表的定义第 5 页
2.1.1 线性表的定义特性,设 A=（ a1,a2,...,ai -1,ai,ai+1,…,a n ） 是一线性表
线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；
在表中 ai-1 领先于 ai,ai 领先于 ai+1,称 ai-1 是 ai 的直接前驱,ai+1 是 ai 的直接后继；
在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；
线性表中元素的个数 n 称为 线性表的长度,n=0 时称为 空表 ；
ai是线性表的第 i 个元素，称 i 为数据元素 ai 的 序号,每一个元素在线性表中的位置，仅取决于它的序号；
第 6 页
2.1.1 线性表的定义
1,二元组表示
L = < D,S >,其中,D = { a1,a2,a3，,...,an}
S = {R} R = {< a1,a2 >,<a2,a3 >,< a 3,a4 > … < a n-1,an> }
线性表的其他表示方式,
2、图形表示顶点：表示数据边：表示是数据间的顺序结构关系
ai+1a1 ai-1a2 ai an
第 7 页
2.1.2 线性表的基本操作
1,初始化线性表 L InitList(&L)
2,销毁线性表 L DestoryList(&L)
3,清空线性表 L ClearList(&L)
4,求线性表 L的长度 ListLength(L)
5,判断线性表 L是否为空 ListEmpty(L)
6,获取线性表 L中的某个数据元素内容 GetElem(L,i,&e)
7,检索值为 e的数据元素 LocateELem(L,e)
8,返回线性表 L中 cur_e的直接前驱元素 PriorElem(L,cur_e,&pre_e)
9,返回线性表 L中 cur_e的直接后继元素 NextElem(L,cur_e,&next_e)
10,在线性表 L中插入一个数据元素 ListInsert(&L,i,e)
(1≦ i≦ ListLength(L)+1)
11,删除线性表 L中第 i个数据元素 ListDelete(&L,i,&e)
(1≦ i≦ ListLength(L))
12,输出线性表 L中的每个数据元素 ListTraverse(L)
第 8 页
2.1.2 线性表的基本操作说明,
1、上面列出的操作，只是线性表的一些常用的基本操作；
2、不同的应用，基本操作可能是不同的；
3、线性表的复杂操作可通过基本操作实现；
第 9 页
2.1.2 线性表的基本操作
【 例 2-1 】 假设线性表 L=(23,56,89,76,18),i=3,x=56,y=88,
则对 L的一组操作及结果如下：
ListLength(L);
GetElem(L,i,e)
PriorElem(L,x,&pre_x)
NextElem(L,x,&next_x)
LocateElem(L,x)
ListInsert(&L,i,y)
ListDelete(&L,i+1,&e)
//结果为 5
//e的值为 89
//pre_x的值为 23
//next_x的值为 89
//结果为 2
//所得结果为 (23,56,88,89,76,18)
//所得结果为 (23,56,88,76,18)
e的值为 89
第 10 页
2.1.2 线性表的基本操作
【 例 2-2 】 利用两个线性表 La和 Lb分别表示两个集合 A和
B，现要求一个新的集合 A=A∪ B。
【 分析 】 这个问题相当于对线性表作如下操作：
扩大线性表 La，将存在于线性表 Lb中而不存在于线性表 La中的数据元素插入到线性表 La中去 。
【 具体步骤 】
（ 1）从线性表 Lb中取得一个数据元素；
（ 2）依该数据元素的值在线性表 La中进行查访；
（ 3）若线性表 La中不存在和其值相同的数据元素，则将从 Lb中删除的这个数据元素插入到线性表 La中；
（ 4）重复以上操作直至 Lb为空表。
第 11 页
2.1.2 线性表的基本操作
【 例 2-2 】 利用两个线性表 La和 Lb分别表示两个集合 A和
B，现要求一个新的集合 A=A∪ B。
【 具体算法 】
void union (List &La,List &Lb)
{
La_len = ListLength (La); //求线性表 La的长度
while ( !ListEmpty(Lb) ) //Lb表中的元素尚未处理完
{
ListDelete (Lb,1,&e); //从 Lb中删除第一个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
DestroyList (Lb); //销毁线性表 Lb
}
该算法运行完后，线性表 Lb被销毁！如果要求 Lb保持原先的值，
算法又如何写？？？【 具体算法 】 ___运行后 Lb仍保持原先的值
i i (List a,ist )
{
a_l istL th (La); //求线性表 La的长度
Lb_len = ListLength (Lb); //求线性表 Lb的长度
for (i = 1; i <= Lb_len; i++) //Lb表中的元素尚未处理完
{
GetElem (Lb,i,&e); //从 Lb中取出第 i个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
}
第 12 页
2.1.2 线性表的基本操作
【 例 2-3 】 已知一个非纯集合Ｂ（ 即集合 B中可能有相同元素），试构造一个纯集合 A，使Ａ中只包含 B中所有值各不相同的成员。
【 分析 】 假设仍以线性表表示集合，则此问题和例 2-2类似，即构造线性表 La，使其只包含线性表 Lb中所有值不相同的数据元素。所不同之处是，操作实施之前，线性表 La不存在，则操作的第一步首先应该构造一个空的线性表，之后的操作步骤和例 2-2相同。
【 具体步骤 】
（ 1）构造一个空的线性表 La；
（ 2）从线性表 Lb中取得一个数据元素；
（ 3）依该数据元素的值在线性表 La中进行查访；
（ 4）若线性表 La中不存在和其值相同的数据元素，则从 Lb中删除的这个数据元素插入到线性表 La中。
（ 5）重复（ 2）至（ 4）的操作直至 Lb为空表为止。
第 13 页
2.1.2 线性表的基本操作
【 例 2-3 】 已知一个非纯集合Ｂ（ 即集合 B中可能有相同元素），试构造一个纯集合 A，使Ａ中只包含 B中所有值各不相同的成员。
【 具体算法 】
void purge (List &La,List &Lb)
{
InitList (La); La_len = 0 //创建一个空的线性表 La
while ( !ListEmpty(Lb) ) //Lb表中的元素尚未处理完
{
ListDelete (Lb,1,&e); //从 Lb中删除第一个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
DestroyList (Lb); //销毁线性表 Lb
}
该算法运行完后，线性表 Lb同样被销毁！如果要求 Lb保持原先的值，算法又如何写？？？【 具体算法 】 ___运行后 Lb仍保持原先的值
i r e (List a,ist )
{
I itList (La); La_len = 0; //创建一个空的线性表 La
Lb_len = ListLength (Lb); //求线性表 Lb的长度
for (i = 1; i <= Lb_len; i++) //Lb表中的元素尚未处理完
{
GetElem (Lb,i,&e); //从 Lb中取出第 i个元素，并将其值赋给 e
if (!LocateElem(La,e)) //La中不存在值为 e的数据元素
ListInsert (La,++La_len,e); //将该元素 e插入到 La中最后一个元素后
}
}
第 14 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 分析 】 两个集合相等，指的是这两个集合中包含的成员相同。当以线性表表示集合时，则要求分别表示这两个集合的线性表 La和 Lb，不仅长度相同，所含数据元素也必须一一对应。值得注意的是，两个“相同”的数据元素在各自的线性表中的“位序”不一定相同。因此，如果在一个线性表中找不到和另一个线性表的某个数据元素相同的数据元素，则立即可以得出“两个集合不等”的结论；反之，
只有当判别出“其中一个线性表只包含和另一个线性表相同的全体成员”时，才得出“两个集合相等”的结论。
【 方法一 】 ____使用辅助结构 Lc
（ 1）若线性表 La和线性表 Lb的长度不等，则返回两集合不等；
（ 2）构造一个线性表 Lc；
（ 3）将线性表 La中的数据元素复制到线性表 Lc中，使得 Lc与 La相同；
（ 4）对 Lb中的每个数据元素，在 Lc中进行查询；
（ 5）若 Lc中存在与该数据元素相同的数据元素，则从 Lc中删除该元素；
（ 6）重复（ 4）和（ 5）步，直到 Lb中的数据元素都遍历完为止；
（ 7）如果 Lc为空，则返回两集合相等，否则，返回两集合不等。
第 15 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 具体算法 】 ____方法一
bool isequal (List La,List Lb)
{
if ( ListLength(La) !=
ListLength(Lb) )
return (FALSE);
InitList (&Lc);
La_len = ListLength (La);
Lb_len = ListLength (Lb);
for (k = 1; k <= La_len; k++)
{
GetElem (La,k,e);
ListInsert (&Lc,k,e);
}
found = TRUE;
for (k = 1; k <= Lb_len,found; k++)
{
GetElem (Lb,k,e);
i = LocateElem (Lc,e);
if (i == 0)
found = FALSE;
else
ListDelete (&Lc,i,e);
}
if (found && ListEmpty(Lc))
return (TRUE);
else
return (FALSE);
DestroyList (&Lc);
}
算法中构造的线性表 Lc是一辅助结构，它的引入是为了在程序执行过程中不破坏原始数据 La，因此算法的最后应销毁 Lc！如果不使用辅助结构 Lc，那算法又如何设计呢？？？
第 16 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 方法二 】 ____不使用辅助结构 Lc
（ 1）若线性表 La和线性表 Lb的长度不等，则返回两集合不等；
（ 2）对 Lb中的每个数据元素，在 La中进行查询；
（ 3）若 La中不存在与该数据元素相同的数据元素，则返回两集合不等；
（ 4）重复（ 2）和（ 3）步，直到 Lb中的数据元素都遍历完为止；
（ 5）返回两集合相等。
第 17 页
2.1.2 线性表的基本操作
【 例 2-4 】 判别两个集合 A和 B是否相等。
【 具体算法 】 ____方法二
bool isequal (List La,List Lb)
{
if ( ListLength(La) != ListLength(Lb) )
return (FALSE);
Lb_len = ListLength (Lb);
for (k = 1; k<= Lb_len; k++)
{
GetElem (Lb,k,e);
i = LocateElem (La,e);
if (i == 0) return (FALSE);
}
return (TRUE);
}
该算法的正确性是因为集合中不存在两个相同的元素！！！！！
第 18 页为了存储线性表，至少要保存两类信息：
1）线性表中的数据元素；
2）线性表中数据元素的顺序关系；
如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？
通常线性表有两种存储表示方法：顺序存储表示和链式存储表示。
第 19 页线性表的顺序存储结构，就是用一组 连续的内存单元 依次 存放线性表的数据元素。
a1
a2
ai-1
ai
ai+1
an
线性表（ a1,a2,a3,..,an ）
的顺序存储结构用顺序存储结构存储的线性表
——称为顺序表
2.2 线性表的顺序表示和实现
2.2.1 顺序表 ——线性表的顺序存储表示第 20 页
2.2.1 顺序表 ——线性表的顺序存储表示说明：
· 在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（
表示）出来；
· 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第 i个元素的存储位置与第 1个元素的存储位置的关系是：
Loc(ai ) = Loc( a1 )+ ( i – 1) t
a1
a2
ai-1
ai
ai+1
an
t个单元
Loc( a1 )
Loc(ai )
第 21 页
2.2.1 顺序表 ——线性表的顺序存储表示怎样在计算机上实现线性表的顺序存储结构？
可用 C语言中的一维数组来表示,但数组不是线性表,因为线性表的长度可变。数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定,如,
#define MAX 100
int v[MAX];
第 22 页
2.2.1 顺序表 ——线性表的顺序存储表示顺序表的类型定义
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct {
ElemType * elem; //线性表存储空间基址 (一维数组 )
int length; //当前线性表长度
int listsize; //当前分配的线性表存储空间大小
int incrementsize; //约定增补空间量 (以 ElemType为单位 )
} SqList;
SqList,类型名，
SqList类型的变量是结构变量，它的四个域分别是：
*elem,存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；
length,存放线性表的表长；
listsize,用于存放当前分配（存放线性表元素）的存储空间的大小。
incrementsize,约定增补空间量（当线性表空间不够时）
第 23 页
2.2.1 顺序表 ——线性表的顺序存储表示存放线性表元素的一维数组设 A = （ a1,a2,a3,..,an ） 是一线性表,L是 SqList 类型的结构变量
，用于存放线性表 A,则 L在内存中的状态如图所示：
顺序表通过元素的存储顺序反映线性表元素间的逻辑关系
a1
a2
ai-1
ai
ai+1
an
0
1
i-2
i-1
i
n-1
99
L.elem
L.lenght
L.Listsize
L.incrementsize
n
99
10
第 24 页功能,构造一个空的顺序表。
方法,首先要按需为其动态分配一个存储区域，然后设其当前长度为０。
2.2.2 顺序表中基本操作的实现
１、初始化操作算法,
void InitList_Sq (SqList &L)
{
L.elem = new ElemType[LIST_INIT_SIZE];
//为顺序表分配初始大小为 LIST_INIT_SIZE的数组空间
L.length = 0; //顺序表中当前所含元素个数为 0
L.listsize = LIST_INIT_SIZE; //该顺序表可以容纳数组元素的个数
L.incrementsize = LISTINCREMENT; //需要扩容时每次可增加的元素个数
}
等价于,L.elem = (ElemType *)
malloc (LIST_INIT_SIZE *
sizeof(ElemType))
第 25 页功能,在顺序表 L中查找其值与给定值 e相等的数据元素的位序，如果未找到，则返回 0。
方法,从第一个元素起，依次和 e相比较，直到找到一个其值与 e相等的数据元素，
则返回它在线性表中的“位序”；或者查遍整个顺序表都没有找到其值和 e相等的元素后返回 0。
2.2.2 顺序表中基本操作的实现
2、查找元素操作算法,（书本上的写法）
int LocateElem_Sq (SqList L,ElemType e)
{
i = 1; //i初始值为第一个元素的位序
p = L.elem; //p的初值为第一个元素的存储位置
while (i <= L.length && *p++ != e) //依次进行判定
++i;
if (i <= L.length) //找到满足判定的数据元素为第 i个元素
return (i);
return (0); //该线性表中不存在满足判定的数据元素
}
算法,（另一种写法）
int LocateElem_Sq (SqList L,ElemType e)
{
for (i = 0; i < L.length; i++)
if (L.elem[i] == e)
return (i+1);
return (0);
}
注意：位序是从 1到
L.length!
第 26 页功能,在顺序表 L 中的第 i ( 1≦ i≦ L.length+1)个数据元素之前插入一个新元素 x。
插入前线性表为：
(a1,a2,a3,…,a i-1,ai,,… a n )
插入后，线性表长度为 L.length+1,线性表为：
(a1,a2,a3,…,a i-1,x,ai,,… a n )
2.2.2 顺序表中基本操作的实现
３、插入元素操作第 27 页
2.2.2 顺序表中基本操作的实现插入前 插入后
_____插入操作示意图
a1
a2
ai-1
ai
ai+1
an
0
1
i-2
i-1
i
n-1
MAX-1
n
P_len
a1
a2
ai-1
x
ai
an
0
1
i-2
i-1
n-2
n-1
n
MAX-1
n+1
P_len
３、插入元素操作一般情况下，在顺序表Ｌ中第 i个元素之前插入一个新的元素时，首先需将 L.elem[L.length-1]至
L.elem[i-1]依次往后移动一个位置。显然，此时顺序表的长度应该小于数组的最大容量；否则，在移动元素之前，必须先为顺序表“扩大数组容量”。
第 28 页
2.2.2 顺序表中基本操作的实现
３、插入元素操作算法,
void ListInsert_Sq (SqList &L,int i,ElemType e)
{
if (i < 1 || i > L.length+1) ErrorMessage (―i值不合法！” );
if (L.length >= L.listsize)
increment (L); //当前存储空间已满，为 L增加 L.incrementsize个元素空间
q = &L.elem[i-1]; //q为插入位置
for (p = &L.elem[L.length-1]; p >= q; --p) //插入位置及之后的元素右移
*(p+1) = *p;
*q = e;
L.length++; //表长增 1
}
void increment (SqList &L)
{
ElemType a[ ]; //ElemType *a;
a = new ElemType[L.listsize+L.incrementsize];
for (i = 0; i < L.length; i++)
a[i] = L.elem[i];
delete [ ]L.elem; //free (L.elem);
L.elem = a;
L.listsize += L.incrementsize;
}
可用 realloc (L.elem,
(L.listsize+L.incrementsize)*s
izeof(ElemType));来代替
void ErrorMessage (char *s)
{
cout << s << endl; //printf (“%s\n”,s);
exit (1);
}
一般情况下，当插入位置 i=L.length+1时,for循环的执行次数为
0，即不需要移动元素；反之，若 i=1，则需将顺序表中全部（ n
个）元素依次向后移动。然而，当顺序表中数据元素已占满空间时，不论插入位置在何处，为了扩大当前的数组容量，都必须移动全部数据元素，因此，从最坏的情况考虑，顺序表插入算法的时间复杂度为 O(n)，其中 n为线性表的长度。
第 29 页删除算法的主要步骤,
1）若 i 不合法或表 L空，算法结束，并返回 0； 否则转 2）
2） 将第 i个元素之后的元素（不包括第 i个元素）依次向前移动一个位置 ;
3）表长 - 1
2.2.2 顺序表中基本操作的实现功能,在顺序表 L 中删除第 i ( 1≦ i≦ L.length)个数据元素。
删除前线性表为：
(a1,a2,a3,…,a i-1,ai,ai+1,… a n )
删除后，线性表长度为 L.length-1,线性表为：
(a1,a2,a3,…,a i-1,ai+1,,… a n )
4、删除元素操作一般情况下，从顺序表Ｌ中删除第 i个元素时，需将 L.elem[i]至 L.elem[L.length-1]的元素依次往前移动一个位置。
第 30 页
2.2.2 顺序表中基本操作的实现
３、删除元素操作算法,
void ListDelete_Sq (SqList &L,int i,ElemType &e)
{
if (i < 1 || i > L.length) ErrorMessage (―i值不合法！” );
p = &L.elem[i-1]; //p为被删除元素的位置
e = *p; //被删除元素赋值给 e
q = L.elem + L.length –1; //表尾元素的位置
for (++p; p <= q; p++) //被删除元素之后的元素左移
*(p-1) = *p;
L.length--; //表长减 1
}
等价于：
e = L.elem[i-1];
memcpy (L.elem+i-1,L.elem+i,
(L.length-i)*sizeof(ElemType));
或
memmove (L.elem+i-1,L.elem+i,
(L.length-i)*sizeof(ElemType))
和插入的情况相类似，当删除的位置 i=L.length时，算法中
for循环的执行次数为 0，即不需要移动元素；反之，若 i=1，则需将顺序表中从第 2个元素起至最后一个元素（共 n个元素）依次向前移动一个位置。因此，顺序表删除元素算法的时间复杂度也为
O(n),其中 n为线性表的长度。
第 31 页
2.2.2 顺序表中基本操作的实现
5、销毁结构操作功能,和结构创建相对应，当程序中的数据结构不再需要时，
应该及时进行“销毁”，并释放它所占的全部空间，以便使存储空间得到充分的利用。
算法,
void DestoryList_Sq (SqList &L)
{
delete [ ]L.elem; //free(L.elem);
L.listsize = 0;
L.length = 0;
}
第 32 页
2.2.2 顺序表中基本操作的实现
6、其他操作对于顺序表来说，其他的操作很容易实现。请同学们在课后自己独立完成！
第 33 页
2.2.2 顺序表中基本操作的实现插入位置 移动元素个数
1 n
2 n-1
i n-i+1
n 1
n+1 0
（ 1）插入算法时间复杂度分析算法时间复杂度取决于移动元素的个数,移动元素的个数不仅与表长有关，而且与插入位置有关。
a1
a2
ai-1
ai
ai+1
an
0
1
i-1
i-2
n-1
.
.
7、插入和删除操作的时间分析第 34 页
（ 1）插入算法时间复杂度分析由此可见,
·在顺序表中插入一个元素,平均要移动表的一半元素。
·表长为 n的顺序表，插入算法的时间复杂度为 O（ n）
E i n =
1
1
n
i
p i (n – i +1)
假设在线性表的任何位置插入元素的概率相同，即
pi= 1/(n+1)
pi:在第 i个元素之前插入元素的概率，在长度为 n的顺序表中插入一个元素，所需移动元素个数数学期望值为：
ninnE in
n
i 2
1)1(
1
1 1
1
第 35 页
（ 2）删除算法时间复杂度分析由此可见,
·在顺序表中删除一个元素,平均要移动表的一半元素。
·表长为 n的顺序表，删除算法的时间复杂度为 O（ n）
E dl =?
n
i 1
q i (n – i )
假设在线性表的任何位置删除元素的概率相同，即
qi= 1/n
qi：删除第 i个元素的概率，在长度为 n的顺序表中删除一个元素，所需移动元素个数数学期望值为：
ninnE d l
n
i 2
1)(1
1
第 36 页
2.2.3 顺序表其他算法举例
【 例 2-5 】设 A=(a1,a2,…,am )和 B=(b1,b2,…,bn )均为顺序表，试比较 A,B的大小 。
【 分析 】 这是对两个顺序表进行比较的操作，因此在算法中不应该破坏已知表。从题目的要求看，只有在两个表的长度相等，且每个对应元素都相同时才相等；否则两个顺序表的大小主要取决于两表中除去前面相同的元素后的第一个元素。
【 具体步骤 】
（ 1）设一变量 j（初值为 1）；
（ 2）当 j小于 A的长度和 B的长度时，若 aj<bj，则返回 -1，若
aj>bj时，则返回 1，否则 j++;
（ 3）重复第（ 2）步，直到 j大于 A或 B的长度；
（ 4）如果 A的长度等于 B的长度，则返回 0；如果 A的长度小于 B
的长度，则返回 -1；否则返回 1。
第 37 页
2.2.3 顺序表其他算法举例
【 例 2-5 】设 A=(a1,a2,…,am )和 B=(b1,b2,…,bn )均为顺序表，试比较 A,B的大小 。
【 具体算法 】
int compare (SqList A,SqList B)
{
j = 1;
while (j <= A.length && j <= B.length)
if (A.elem[j] < B.elem[j]) return (-1);
else if (A.elem[j] > B.elem[j]) return (1);
else j++;
if (A.length == B.length) return (0);
else if (A.length < B.length) return (-1);
else return (1);
}
等价于：
If (j < A.length) return (1);
else if (j < B.length) return (-1);
else return (0);
此算法中只有一个 while循环，它的执行次数依赖于待比较的顺序表的表长。因此算法的时间复杂度为：
O(Min(A.length,B.length))
第 38 页
2.2.3 顺序表其他算法举例
【 例 2-6 】设计一个算法，用尽可能少的辅助空间将顺序表中的前 m
个元素和后 n个元素进行整体互换。即将线性表
（ a1,a2,…,am,b1,b2,…,bn） 改变成
（ b1,b2,…,bn,a1,a2,…,am）
【 分析 】 此题的难点在于要求用尽可能少的辅助空间。如果没有这个限制，可以另设一个和已知顺序表空间大小相同的顺序表，然后进行元素复制即可。
【 具体算法 】 ___借助于辅助空间
void exchang (SqList &A,int m,int n)
{
ElemType a[ ]; //ElemType *a;
a = new ElemType[A.length]; //a=(ElemType *)malloc
(A.length*sizeof(ElemType));
memcpy (a,A.elem+m,n*sizeof(ElemType));
memcpy (a+n,a.elem,m*sizeof(ElemType));
delete [ ]A.elem; //free (A.elem);
A.elem = a;
}
第 39 页
2.2.3 顺序表其他算法举例
1 2 … k-1 k k+1 … m+k-1 m+k … m+n
b1 b2 … bk-1 a1 a2 … … … am bk bk+1 … bn
b1 b2 … bk-1 a1 a2 … … … am bk+1 … bn
【 例 2-6 】线性表数据互换。
【 方法一 】 从表中第 m+1个元素起依次插入到元素 a1之前，则首先需将该元素 bk（ k=1,2,…,n ）暂存在一个辅助变量中，然后将它之前的 m个元素（ a1,a2,…,am ）依次后移一个位置。
b1 b2 … bk-1 bk a1 a2 … … … am bk+1 … bn
w
w
_______将 bk插入到（ a1,a2,…,a m）之前的过程
【 具体算法 】 ___方法一
void exchang (SqList &A,int m,int n)
{
for (k = 1; k <= n; k++)
{
w = A.elem[m+k-1];
for (j = m+k-1; j >=k; j--)
A.elem[j] = A.elem[j-1];
A.elem[k-1] = w;
}
}
算法的复杂度,由于对每一个 bk都需要移动 m个元素，
因此算法的时间复杂度为 O(m*n)。
第 40 页
2.2.3 顺序表其他算法举例
1 2 … i i+1 … i+k i+k+1 i+m-1 i+m … … n
a1 a2 … ai ai+1 … ai+k ai+k+1 … ai+m-1 ai+m … … an
【 例 2-6 】线性表数据互换。
【 方法二 】 先将线性表“逆置”成（ bn,…,b2,b1,am,…,a2,a1 ），
然后分别再对前 n个元素（ bn,…,b2,b1 ）和后 m个元素
（ am,…a2,a1 ）进行“逆置”，便可得到所求结果。
_______顺序表中部分元素（ ai,ai+1,…,a i+m）逆置前后的状况
a1 a2 … ai+m ai+m-
1
… ai+k+1 ai+k … ai+1 ai … … an
【 具体算法 】 ___方法二
void invert (ElemType &R[ ],int s,int t)
{
for (k = s; k <= (s+t)/2; k++)
{
w = R[k];
R[k] = R[t-k+s];
R[t=k+s] = w;
}
}
void exchange2 (SqList &A,int m,int n)
{
invert (A.elem,0,m+n-1);
invert (A.elem,0,n-1);
invert (A.elem,n,m+n-1);
}
算法的时间复杂度为：
O(t-s+1)。
算法的时间复杂度为：
O(m+n),O(n),O(m)，
按最坏情况估计为：
O(m+n)。
第 41 页
2.2.3 顺序表其他算法举例
【 例 2-7 】已知一个非纯集合 B（即集合 B中可能有相同元素），试构造一个纯集合 A，使 A中只包含 B中所有值各不相同的成员。（假设以顺序线性表表示集合）。
【 方法 】 依次取得顺序表 B中的元素，在顺序表 A中进行查询，若没有值相同的元素出现，则将它插入到 A的表尾。 B中的第一个元素必定会插入到 A中，因此对它不再进行查询，而是直接“复制”到 A表中 。
【 具体算法 】
void purge_Sq (SqList &A,SqList &B)
{
A.elem[0] = B.elem[0];
A.length = 1;
for (i = 1; i < B.length; i++)
{
e = B.elem[i];
j = 0;
while (j < A.length && A.elem[j] != e) j++;
if (j == A.length)
{
A.elem[A.length] = e;
A.length++;
}
}
}
算法的复杂度,O(n2)，其中 n为 B表的长度 。
第 42 页线性表的顺序表示和实现小结：
顺序表是线性表最简单的一种存储结构小 结顺序表的特点：
1 通过元素的存储顺序反映 线性表中数据元素之间的逻辑关系；
2 可随机存取顺序表的元素；
3 顺序表的插入、删除操作要通过移动元素实现；
第 43 页
2.3 线性表的链式表示和实现线性表的链式存储结构是用一组 任意 的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。
ai+1a1 ai-1a2 ai an
第 44 页
2.3.1 单链表和指针
a4
a3
a1
a2
0
1010
1024
1014
1010
1012
1014
1016
1018
1020
1022
1024
1026
用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。
用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的
ai-
1
aia2a1 ai+1 na
H
第 45 页结点,数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点 ；
结点的数据域,结点中用于保存数据元素的部分 ;
结点的指针域,结点中用于保存数据元素直接后继存储地址的部分 ;
线性链表有关术语
2.3.1 单链表和指针结点 数据域 指针域存储后继结点存储地址存储数据元素第 46 页头指针,用于存放线性链表中第一个结点的存储地址 ;
空指针,不指向任何结点，线性链表最后一个结点的指针通常是指空指针，用 NULL表示 ;
线性链表的每个结点中只有一个指针域故也称为 单链表
线性链表有关术语
2.3.1 单链表和指针
ai-1 aia2a1 ai+1 nan
H
空指针头指针第 47 页怎样在计算机上实现线性链表？
2.3.1 单链表和指针第 48 页
2.3.1 单链表和指针结点变量图示
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
LNode,结构类型名；
LNode类型结构变量有两个域：
data,用于存放线性表的数据元素，
next,用于存放元素直接后继结点的地址；
·该类型结构变量用于表示线性链表中的一个结点；
LNode *p,p为指向结点 (结构 )的指针变量；
LinkList H,头指针为 H的单链表；
数据域 指针域
data next
LNode类型结构变量
p
p是 LNode类型的指针变量
单链表的结点类型定义及指向结点的指针类型定义第 49 页
2.3.1 单链表和指针方法一：
LNode *p;
p = new LNode;
方法二：
p = (LNode *) malloc ( sizeof (LNode ) );
单链表中结点的创建
p
第 50 页
2.3.1 单链表和指针调用 free ( p )
0
1
2
99
p
调用 free ( p ) 图示
delete p 或 free ( p )
功能：将指针变量 p所指示的存储空间，回收到系统内存空间中去使用方法：
...
LNode *p;
p = (LNode *) malloc (sizeof (LNode));
// 一旦 p所指示的内存空间不再使用，
//调用 free( ) 回收之
free(p);
第 51 页
2,3,2 单链表的基本操作如何在线性链表上实现线性表的基本操作？
如何插入？删除？查找元素？
nai-1 aia2a1 ai+1 a
H
第 52 页
2,3,2 单链表的基本操作
【 分析 】 当以单链表表示线性表时，整个链表由一个“头指针”
来表示，线性表的长度即为链表中的结点个数，只能通过“遍历
‖链表来实现。
1、求线性表的长度
【 具体算法 】
int ListLength_L (LinkList L)
{
p = L; k = 0;
while (p)
{
k++; p = p->next;
}
return (k);
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 53 页
2,3,2 单链表的基本操作
2、查找元素操作
【 分析 】 在单链表 L中查找和给定值 e相等的数据元素的过程和顺序表类似，从第一个结点起，依次和 e相比较，直到找到一个其值和 e相等的元素，则返回它在链表中的“位置”；或者查遍整个链表都不存在这样的一个元素后，返回,NULL‖。
【 具体算法 】
LNode * LocateElem_L (LinkList L,ElemType e)
{
p = L;
while (p && p->data != e)
p = p->next;
return (p);
}
注意,返回值为结点值为 e的指针算法的时间复杂度,O(n)，其中 n为表长 。
第 54 页
2,3,2 单链表的基本操作
yx
3、插入结点操作
【 分析 】 由于在单链表中不要求两个互为“前驱”和“后继”的数据元素紧挨存放，则在链表中插入一个新的数据元素时，不需要移动数据元素，而只需要在链表中添加一个新的结点，并修改相应的指针链接。插入操作分为：后插和前插。
z
p
as
后插（在 p所指结点后插入 s所指的结点）
（ 1） S->next = p->next
（ 2） p->next = s
第 55 页
2,3,2 单链表的基本操作
yx
3、插入结点操作
z
p
as
前插（在 p所指结点前插入 s所指的结点）
（ 1） q->next = s
（ 2） s->next = p
q
前插时，首先要找到插入结点 p的前驱结点的指针 q，
然后才能进行插入操作。要找到前驱结点，这只要从链表的头指针起进行查询即可。令 q的初始值等于头指针，查找结束的条件是 q->next == p；若否，则指针 q后移。还有一点要注意的是，如果 p所指结点是链表中的第一个结点，则
“前插”操作尚需修改链表的头指针。
第 56 页
2,3,2 单链表的基本操作
3、插入结点操作
【 具体算法 】
void * ListInsert_L (LinkList &L,LNode *p,LNode *s,char mode)
{
if (p == L) //将 s结点插入到链表的第一个结点之前
{ s->next = L; L = s; return; }
if (mode ==?A‘) //后插
{ s->next = p->next; p->next = s; return; }
q = L; //前插
while (q->next != p)
q = q->next;
q->next = s;
s->next = p;
}
算法的时间复杂度：
后插 O(1)，前插 O(n)，其中 n为表长 。
第 57 页
2,3,2 单链表的基本操作
x
4、删除结点操作
【 分析 】 和插入类似，在单链表中删除一个结点时，也不需要移动数据元素，仅需修改相应的指针链接。但由于删除结点时，需要修改的是它的“前驱”结点的指针域，因此和“前插”操作一样，首先应当找到它的前驱结点。
zy
p
（ 1） q->next = p->next;
（ 2） free (p);
q
第 58 页
2,3,2 单链表的基本操作
4、删除结点操作
【 具体算法 】
void * ListDelete_L (LinkList &L,LNode *p,ElemType &e)
{
if (p == L) //删除链表中第一个结点，修改链表头指针
L = p->next;
else
{
q = L; //查找被删除结点的前驱结点的指针
while (q->next != p)
q = q->next;
q->next = p->next; //修改 q结点的指针域
}
e = p->data; delete p; //返回被删除结点的数据元素，并释放结点空间
}
算法时间复杂度,O(n)，其中 n为表长 。
第 59 页
2,3,3 单链表的其他基本操作举例
【 分析 】 链表是一种动态管理的结构，它和顺序表不同，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统根据需求即时生成的。因此
，建立链表的过程是一个动态生成的过程。即从“空表”起，依次建立结点，并逐个插入链表。所谓“逆序”创建链表指的是，依和线性表的逻辑顺序相“逆”
的次序输入元素，逆序生成链表可以为处理头指针提供方便。
【 例 2-8 】逆序创建链表。
a b c d e ^
b c d e ^
c d e ^
d e ^
e ^
^
e ^
d
c
b
a
线性表
(a,b,c,d,e)的逆序创建过程：
第 60 页
2,3,3 单链表的其他基本操作举例
【 例 2-8 】逆序创建链表。
【 具体算法 】
void CreateList_L (LinkList &L,ElemType A[ ],int n)
{
L = NULL; //建立一个空的单链表
for (i = n-1; i >= 0; i--)
{
s = new LNode; //生成新结点
s->data = A[i]; //赋元素值
s->next = L; //插入在第一个结点之前
L = s;
}
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 61 页
2,3,3 单链表的其他基本操作举例
【 例 2-9 】逆置单链表。
【 分析 】 若对顺序表中的元素进行逆置可以借助“交换”前后相应元素来完成。
而对单链表进行逆置，则不能如法炮制。因为对于链表中的第 i个结点，都需要顺链查找第 n-i+1（设链表长度为 n）个结点，将使逆置链表操作的时间复杂度达到
O(n2)。因此逆置单链表的操作应借助修改链表中的指针来完成。
【 方法 】 设想逆置后的单链表是一个新建的链表，但表中的结点不是新生成的，
而是从原（待逆置的）链表中依次“删除”得到。由此，逆置单链表的操作可类似上例逆序创建链表进行：设逆置链表的初态为一空表，“删除”已知链表中的第一个结点，然后将它“插入”到逆置链表的“表头”，即使它成为逆置链表中
“新”的第一个结点，如此循环，直到原链表为空表止。
第 62 页
2,3,3 单链表的其他基本操作举例
【 例 2-9 】逆置单链表。
a1 a2 a3 a4 a5 ^
head
(a) 逆置前的链表
(b) 逆置后的链表
a1 ^ a2 a3 a4 a5
head
(c) 逆置过程中的链表
a1 ^ a2 a3 a4 a5 ^
head
s p
第 63 页
2,3,3 单链表的其他基本操作举例
【 例 2-9 】逆置单链表。
【 具体算法 】
void InvertLinkedList (LinkList &L)
{
p = L; L = NULL; //设逆置后的链表的初态为空表
while ( p ) //p为待逆置链表的头指针
{
s = p; p = p->next //从 p所指链表中删除第一个结点（ s结点）
s->next = L; L = s; //将 s结点插入到逆置表的表头
}
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 64 页
2,3,3 单链表的其他基本操作举例
【 方法 】 设线性表 A,B分别用头指针为 head_a,head_b
的两个带头结点的线性链表存储,归并后的递减有序表头指针为 head,将两表数据较小的结点依次取出插入到新表
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 65 页
2,3,3 单链表的其他基本操作举例
73 n9
52 n7
head_a
head_b
79 n2
head
38 7
8
5
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 66 页
【 具体算法 】
LNode * merge_link ( LinkList &head_a,LinkList &head_b)
{
LNode *p,*q;
LinkList head;
head = (LNode *) malloc (sizeof (LNode));
head->next = NULL;
p = head_a->next; q = head_b->next;
while ( (p != NULL) && (q != NULL) )
If (p->data < q->data)
{ head_a->next = p->next; p->next = head->next;
head->next = p; p = head_a->next; }
else { head_b->next = q->next; q->next = head->next;
head->next = q; q = head_b->next; }
2,3,3 单链表的其他基本操作举例
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 67 页
while (p != NULL)
{
head_a->next = p->next; p->next = head->next;
head->next = p; p = head_a->next;
}
while(q!=NULL)
{
head_b->next = q->next; q->next = head->next;
head->next = q; q = head_b->next;
}
free (head_a); free (head_b);
return (head);
}
2,3,3 单链表的其他基本操作举例
【 例 2-10 】 将两个递增有序线性链表归并成一个递减有序表 。
第 68 页线性链表小结线性链表是线性表的一种链式存储结构线性链表的特点
1 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；
2 插入删除操作通过修改结点的指针实现；
3 不能随机存取元素；
第 69 页
1 循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点
2 循环链表图示
2,3,4 循环链表
(a)非空表 （ b） 空表
head
head
a1 an
第 70 页
2,3,4 循环链表说明,
· 在 解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；
· 循 环链表与单链表操作的主要差别是算法中循环结束的条件不是 p或 p->link是否为 NULL，而是它们是否等于首指针；
· 对 循环链表，有时不给出头指针，而是给出尾指针
aa1 an
给出尾指针的循环链表第 71 页
2,3,4 循环链表
b
aa
1
a
n
bb
1
b
n
aa
1
a
n
b
1
b
nq
q
p
p
两循环链表合并：
p = a->next;
q = b->next;
a->next = q->next;
b->next = p;
free (q);
第 72 页
1 双向链表的概念
2,3,5 双向链表
(a)结点图示数据域指针域 指针域结点存储数据元素存储后继结点的地址存储前趋结点的地址双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。
第 73 页
2.3.5 双向链表
2 双向链表图示
head
(b)空的双向循环链表
（ c） 非空 的双向循环链表
head a b
typedef struct DuLNode
{
ElemType data;
struct DuLNode * prior,*next;
} DuLNode,*DuLinkList;
第 74 页在双向链表中删除结点时指针变化情况在双向链表中插入一个结点时指针的变化情况
p
ai-1
x①
②
③
④
ai
pai ai+1
①
②
ai-1
2.3.5 双向链表
3、双向链表的基本操作算法第 75 页
2.3.5 双向链表
p->prior = q;
1）插入操作算法 (在 p 所指结点之前插入 q 结点的过程 )
q = (DuLNode *) malloc (sizeof (DuLNode));
q->data = x;
q->prior = p->prior;
p->prior->next = q;
q->next = p; ai-1
① ② ③④
ai
p
x
q
第 76 页
2.3.5 双向链表
free (p);
ai+1
①
②
ai-1
2）删除操作算法 (删除 p所指向的结点 )
(p->prior)->next = p->next;
(p->next)->prior = p->prior;
ai
p
第 77 页链表结构的讨论
通常链表的定义定义为一个指向链表中第一个结点或头结点的头指针。
好处,定义简单不足,虽然可以完成线性表的任何操作，但给某些“简单操作”
带来不便。例如，求线性表的长度，在表中最后一个元素后面插入或删除最后一个元素等，对顺序表而言，其时间复杂度为 o(1)，
而对于链表来说，则为 o(n)。
第 78 页链表结构的讨论
通常链表的改进链表的定义中加上“头指针”、“尾指针”和“链表长度”三个域。
typedef struct
{
LinkList head,tail; //头指针、尾指针
int length; //链表长度
} AdvancedLinkList;
第 79 页
2.4 有序表若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值递减会递增有序排列，即 ai≧ ai-1 或 ai≦ ai-1
（ i=2,3,…,n ），则称该线性表为 有序表 （ ordered list）。
有序表的基本操作和线性表大致相同，但由于有序表中的数据元素有序排列，因此在有序表中插入元素的操作应按“有序关系”进行。和线性表相同，有序表也可以有 顺序表 和 链表 两种存储表示方法。
假设某有序表以顺序表的形式存储，其数据元素依值递增排列，先要插入一个新的数据元素 x，则应该使插入之后的顺序表仍保持有序表的特性。
【 具体算法 】
void OrdInsert_Sq (SqList &L,ElemType x)
{
i = L.length – 1;
while (i >=0 && x < L.elem[i])
{
L.elem[i+1] = L.elem[i]; //值大于 x的元素后移
i--;
}
L.elem[i+1] = x; //插入元素 x
L.length++; //表长增 1
}
算法的时间复杂度,O(n)，其中 n为表长 。
第 80 页
2.4 有序表
【 例 2-11 】 以顺序有序表表示集合，由一个非纯集合 B构造一个纯集合 A，使 A中只包含 B中所有值各不相同的成员 。
【 分析 】 由于此例中操作的对象是“有序表”，则表中所有值相同的元素必定连续出现。则在 La表中进行“查访”的操作变得简单化了，因为不需要在整个 La表中进行“查访”，而只要和 La表中最后一个元素比较即可。同时，由于 La表的表长不会大于 Lb表，则可用同一个顺序表表示。换个角度看问题，当前要实现的算法功能是从一个以顺序表表示的有序表中“删除”所有值相同的多余元素，而使所有值不相同的元素均压缩到顺序表的前部空间中。
【 具体算法 】
void purge_Osq (SqList &L)
{
i = 0; j = 1;
while (j < L.length)
{
if (L.elem[i] != L.elem[j])
{ L.elem[i+1] = L.elem[j]; i++; }
j++;
}
L.length = i + 1;
}
（ 1） ―删除”的操作是隐含的，仅以
j++操作代替。（ 2）逻辑上的两个线性表 La和 Lb用同一顺序有序表 L表示。
（ 3） i指示 La表中“当前所含”的最后一个元素,j指示 Lb表中“当前被考察”
的元素。（ 4）若该元素和 La中最后一个元素不等，则说明它不是“多余”的，
应当“插入”到 La表中；否则“不予理睬”，继续考察 Lb表中下一个元素。
算法的时间复杂度,O(n)，其中 n为表长 。
第 81 页
2.4 有序表
【 例 2-12 】 分别以两个（带头结点的）循环有序链表表示集合 A和 B，
完成求这两个集合的并集 C（ C = A∪ B）的操作。集合 C仍以循环有序链表表示，并且不另分配新的空间，而是利用集合 A和 B的结点来构造集合 C的链表 。操作完成后，集合 A和 B的链表不再存在。
【 分析 】 根据并集的定义,C的成员应为 A的成员和 B的成员之“和
”，相同的成员只取一个，则可从 C为空集起，逐个将集合 A和 B中不同的成员插入到集合 C中。换句话说,C的链表中的结点或“取自
” A的链表，或“取自” B的链表。
第 82 页
2.4 有序表
【 例 2-12 】 分别以两个（带头结点的）循环有序链表表示集合 A和 B，完成求这两个集合的并集 C（ C
= A∪ B）的操作。集合 C仍以循环有序链表表示，并且不另分配新的空间，而是利用集合 A和 B的结点来构造集合 C的链表 。操作完成后，集合 A和 B的链表不再存在。
【 方法 】 利用链表中结点元素“有序”的特性，可作如下处理,（ 1）设置三个指针,pa,pb和 rc，其中 pa和 pb分别指向集合 A和 B的链表中某个结点,rc指向
C链表中最后一个结点；（ 2）若 pa->data < pb->data，说明 pa所指结点的元素在 B表中不可能出现，应将 pa结点链接到 C链表中（ rc->next = pa）；（ 3）若
pa->data > pb->data，则说明 pb所指结点的元素在 A表中不可能出现，应将 pb
结点链接到 C链表中（ rc->next = pb）；（ 4）若 pa->data = pb->data，则应将其中任一结点（ pa或 pb所指）链接到 C链表中，并释放另一结点空间。
指针 pa和 pb的初始状态,若链表不空，则分别指向各自链表中第一个结点；
否则指向头结点，指针 rc指向 C链表的头结点。
重复操作的条件是,A表和 B表都“不空”；反之表明至少有一个表已经处理完毕，即该链表中的结点或已链接到 C表中，或已释放。此时，只需将“剩余”
结点链接到 C链表中即可。
第 83 页
2.4 有序表
(a) 操作之前的链表
La4 7 10 21 40 56
7 9 21 Lb68
La4 7 10 21 40 56
9 21 Lb68
rc pa
pb
(b) 操作过程中的链表求“并集”操作示意图第 84 页
2.4 有序表求“并集”操作示意图
(c) 操作完成之后的链表
4 7 10 21 40 56
9 La68
第 85 页
2.4 有序表 ang【 具体算法 】
void union_OL (LinkList &La,LinkList &Lb)
{
pa = La->next->next; //pa指向 A中当前考察的结点
pb = Lb->next->next; //pb指向 B中当前考察的结点
rc = La->next; //rc指向 C当前的表尾结点
while (pa != La->next && pb != Lb->next)
{
if (pa->data < pb->data) //链接 A的结点,pa指向 A中下一结点
{ rc->next = pa; rc = pa; pa = pa->next; }
else if (pa->data > pb->data) //链接 B的结点,pb指向 B中下一结点
{ rc->next = pb; rc = pb; pb = pb->next; }
else //链接 A的元素，释放 B的结点,pa,pb分别指向各自下一元素
{
rc->next = pa; rc = pa; pa = pa->next;
qb = pb; pb = pb->next; delete qb;
}
} //while
if (pb == Lb->next)
rc->next = pa; //链接 A的剩余段
else
{
rc->next = pb; pb = Lb->next; //pb指向 B的头结点
Lb->next = pa; La = Lb; //构成 C的循环链
}
delete pb; //释放 B表的表头
}
算法的时间复杂度,O(m+n)，其中 m,n分别为两个表的长度 。
第 86 页
2.4 有序表【 改进算法 】void union_OL_1 (LinkList &La,LinkList &Lb)
{
La->next->data = MAX; Lb->next->data = MAX;
pa = La->next->next; //pa指向 A中当前考察的结点
pb = Lb->next->next; //pb指向 B中当前考察的结点
rc = La->next; //rc指向 C当前的表尾结点
while (pa != La->next || pb != Lb->next)
{
if (pa->data < pb->data) //链接 A的结点,pa指向 A中下一结点
{ rc->next = pa; rc = pa; pa = pa->next; }
else if (pa->data > pb->data) //链接 B的结点,pb指向 B中下一结点
{ rc->next = pb; rc = pb; pb = pb->next; }
else //链接 A的元素，释放 B的结点,pa,pb分别指向各自下一元素
{
rc->next = pa; rc = pa; pa = pa->next;
qb = pb; pb = pb->next; delete qb;
}
} //while
rc->next = La->next; //封闭链环
delete Lb->next; //释放 B表的表头
}
算法的时间复杂度,O(m+n)，其中 m,n分别为两个表的长度 。
第 87 页
2.4 有序表
【 例 2-13 】 假设以有序链表表示集合，设计算法判别两个给定集合是否相等。
【 分析 】 两个集合相等的条件是不仅长度相同，各个对应元素都相等。由于此例中以有序链表表示集合，则只要同步扫描两个链表，
若从头至尾每个对应的元素都相等，则表明两个集合相等。
【 具体算法 】
void isequal_OL (LinkList A,LinkList B)
{
pa = A->next; pb = B->next;
while (pa && pb && pa->data == pb->data)
{ pa = pa->next; pb = pb->next; }
if (pa == NULL && pb == NULL) return (TRUE);
return (FALSE);
}
算法的时间复杂度,O(n)，其中 n为集合的大小 。
第 88 页
2.5 顺序表和链表的综合比较线性表和有序表有两种存储表示,顺序表和链表顺序表：
需要预分配一定长度的存储空间。太大易造成存储空间的浪费，太小又将造成频繁地进行存储空间的再分配。
顺序表是一种随机存储的结构，对顺序表中任一元素进行存取的时间相同。
顺序表对插入、删除操作需要移动近一半的数据元素 。
链表：
存储分配灵活，链表中的结点可在程序执行过程中动态生成。
链表是一种顺序存储的结构，对链表中的每个结点都必须从头指针所指结点起顺链扫描。
链表对插入、删除操作不需要移动数据元素 。
第 89 页第二章 线性表小结本章学习了线性表的顺序存储结构 ——顺序表，链式存储结构,
线性链表,循环链表,双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，
线性表的同一操作的算法是不同的，在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实的基础。
第 90 页习 题
P43,
2.5 2.7 2.8 2.9 2.11 2.13
