1
第二章 线性表
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.4 顺序表的应用
2.5 有序表
2.1 线性表及其逻辑结构
线性表的逻辑结构和物理结构，以及它们之间的相互关系
定义与之相适应的运算
设计相应的算法
分析算法的效率
2
2.1线性表及其逻辑结构
1.线性表具有相同特性的 n个数据元素的一个有限序列,
记为 L＝ (a1,a2,… ai,ai+1,…,an)
数据元素之间的关系是：
ai-1领先于 a i,a i领先于 a i＋ 1，即元素在位臵上是有序的；
称 ai-1是 a i的直接 前驱 元素,a i+1是 a i的直接 后继 元素；
除 a1外，每个元素 有且仅有一个 直接前驱元素；
除 an外，每个元素 有且仅有一个 直接后继元素；
线性表中数据元素的个数 n(n>=0）称为线性表的 长度 ；
当 n=0时，称为 空表 。
3
2.1线性表及其逻辑结构线性表是最常用且最简单的一种数据结构它的 形式化定义 为,List=(D,R)
其中,D={ai|1≤i ≤n,ai属 ElemType类型 }
R={r}
r={<ai,ai+1>| 1≤i ≤n-1}
R是一个序偶的集合，表示线性表中数据元素之间的相邻关系。
逻辑图
a1 a2 … ai ai+1 an…
4
2.1线性表及其逻辑结构
ADT List
{
数据对象：
D={ai| 1≤i≤n,n≥0,ai是 ElemType类型 }
数据关系：
R={<ai,ai+1>|ai,ai+1∈ D,i=1,…,n -1}
基本运算：
InitList(&L):初始化线性表,构造一个空表
DestroyList(&L):销毁线性表,释放表占存储空间…
Displist(L);输出线性表,显示表中所有元素值
}
ElemType是任何合法的数据类型
5
例 1 分析 26 个英文字母组成的英文表,
（ A,B,C,D,……,Z ）
例 2 分析学生情况登记表,
分析,数据元素都是同类型 (字符 ),元素间关系是 线性 的姓 名 学 号 性 别 年龄 健康情况王小林 790631 男 18 健康陈 红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
分析,数据元素都是同类型 （记录），
元素间关系是 线性 的。
2.1线性表及其逻辑结构
6
2.1线性表及其逻辑结构
2.基本运算
InitList(L),初始化线性表：构造一个空的线性表 L
DestroyList(L),销毁线性表：释放线性表 L占用的内存空间。
ListEmpty(L),判线性表是否为空表,若 L为空表,则返回真,否则返回假
ListLength(L),求线性表的长度,返回 L中元素个数。
DispList(L),输出线性表,当线性表 L不为空时,顺序显示 L中各结点的值域。
7
2.1线性表及其逻辑结构
GetElem(L,i,e):求线性表 L中指定位臵的某个数据元素,用 e返回 L中第 i （ 1≤i≤ ListLength(L))个元素的值。
ListDelete(L,i,e),删除数据元素：删除 L中的第 i
（ 1≤i≤ListLength(L))个元素，并用 e返回其值,L的长度减 1。
LocateElem(L,e),定位查找,返回 L中第 1个值域与
e相等的位序。若这样的元素不存在,则返回值为 0。
ListInsert(L,i,e),插入数据元素：在 L的第 i(
1≤i≤ListLength(L)+1)个元素之前插入新的元素 e，
L的长度增 1。
想一想：这些运算已经实现了吗？
8
对上述的运算的两点说明：
这些运算是在逻辑结构上定义的操作。只给出这些运算的功能是,做什么,,至于,如何做,等实现细节，只有待确定了存储结构之后才考虑。
这些运算仅是基本运算集，基于基本运算可进行复杂的运算，即通过基本运算可派生出复杂的运算。
2.1线性表及其逻辑结构
9
例 2.1 有一个线性表 L=(‘a’,‘c’,‘a’,‘d’,‘b’),求以下基本运算的执行结果
ListLength(L)
ListEmpty(L)
GetElem(L,3,e)
LocateElem(L,‘a’)
ListInsert(L,4,‘e’)
ListDelete(L,3)
=5
=0
e=‘a’
=1
L=(‘a’,‘c’,‘a’,‘e’,‘d’,‘b’)
L=(‘a’,‘c’,‘e’,‘d’,‘b’)
2.1线性表及其逻辑结构
10
2.1线性表及其逻辑结构例 2.2 求两个集合的并,即 C=A∪ B
分析：设 A,B分别由两个线性表 LA和 LB表示，要求将 LA和 LB合并后的 DE放入到线性表 LC中。
算法思想：
① 初始化 LC；
② 将 LA中所有元素复制到 LC中；
③ 依次从 LB中取出一个 DE；
④ 判断 LC中是否存在；
⑤ 若不存在，则插入到 LC中。
11
2.1线性表及其逻辑结构例 2.2 求两个集合的并,即 C=A∪ B
void unionList(List LA,List LB,List &LC)
{/*将 LA和 LB中的元素归并到 LC中 */
int lena,lenb,i; ElemType e; InitList(LC);
for (i=1;i<=ListLength(LA);i++)
/*将 LA的所有元素插入到 Lc中 */
{ GetElem(LA,i,e);
ListInsert(LC,i,e);
}
lena=ListLength(LA); /*求线性表的长度 */
lenb=ListLength(LB);
12
2.1线性表及其逻辑结构例 2.2 求两个集合的并,即 C=A∪ B
for (i=1;i<=lenb;i++)
{ GetElem(LB,i,e);
/*取 LB中第 i个数据元素赋给 e*/
if (!LocateElem(LA,e))
ListInsert(LC,++lena,e);
/*LA中不存在和 e相同者,则插入到 LC中 */
}
}
13
2.2线性表的顺序存储结构
2.2.1 顺序存储结构把线性表中的所有元素按照其 逻辑顺序 依次存储到从计算机存储器中指定存储位臵开始的 一块连续的 存储空间中。
假设首元素 a1的存放地址为 LOC(a1)(称为 首地址 )，
线性表每个元素占用 k(k= sizeof(ElemType))个存储单元
，则第 i个元素 ai的存储位臵为,LOC(ai) = LOC(a1) +
K *（ i-1）
设有一维数组 M[10]，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素 M[0]的第一个字节的地址是 98，则 M[3]的第一个字节的地址是?
LOC( M[3] ) = 98 + 5 × (4-1) =113
14
2.2线性表的顺序存储结构
ADT List
{
数据对象：
D={ai| 1≤i≤n,n≥0,ai是 ElemType类型 }
数据关系：
R={<ai,ai+1>|ai,ai+1∈ D,i=1,…,n -1}
基本运算,
} 1、定义 ElemType类型
2、定义存储线性表的顺序存储结构体
…
1,用 C/C++实现线性表的顺序存储结构需注意两个主要步骤：
15
2.2线性表的顺序存储结构
#include "stdafx.h"
#include <malloc.h>
typedef char ElemType;
说明：为了使用系统的 malloc()
函数在内存为线性表分配存储空间，必须包含此头文件
#define MaxSize 50
//ElemType 定义为字符类型
//线性表数据元素的最大数目
typedef struct //存储线性表的结构体
{
ElemType data[MaxSize];//存储线性表数据元素
int length;//存储线性表的元素个数 —长度
} SqList;
说明：以上定义与申明必须位于主函数之前
(1)申明与定义
2,用 C/C++实现线性表的顺序存储结构
16
2.2线性表的顺序存储结构使用 C/C++提供的内存分配语句 malloc，
在计算机内存中分配一个大小、结构与 SqList
类型相同的存储空间，并将该存储空间的首地址赋给指针变量 L。
SqList * L
L=(SqList *)malloc(sizeof(SqList))
//定义一个指向 SqList类型的指针
typedef struct //存储线性表的结构体
{
ElemType data[MaxSize];//存储线性表数据元素
int length;//存储线性表的元素个数 —长度
} SqList;
(2)在计算机内存中为线性表分配存储空间
//分配内存空间
17
2.2线性表的顺序存储结构
L=(SqList *)malloc(sizeof(SqList))
void *malloc(unsigned size );
函数原形 函数功能,Allocates memory blocks
必须包含的头文件为 <malloc.h>或者 <stdlib.h>
18
2.2线性表的顺序存储结构
a1
a2
ai
an
…
…
…
…
0
1
i-1
n-1
MaxSize-1
数据元素下标
1、数组下标从 0开始，所以顺序表中第 i个元素的下标是 i-1
2,MaxSize是事先定义的一个常数，它是顺序表所能存储的最大元素个数
3、线性表满，表示表中有
MaxSize个元素，表的长度为 MaxSize;若表中有 n个元素 (n<MaxSize)，表的长度为 n;若表中无任何元素
(n=0)，称线性表为空表。aMaxSize
19
2.2线性表的顺序存储结构
a1
a2
ai
an
…
…
…
…
0
1
i-1
n-1
MaxSize-1
数据元素下标设 L是指向该顺序表的指针，如何访问顺序表中的第 i个元素？
e=L->data[i-1]
1、将表中第 i个元素的值赋给变量 e
L->data[i-1]=e
2、将变量 e的值赋给表中第 i个元素
20
2.2线性表的顺序存储结构
1、用一个含有 n个元素的数组建立顺序表
void CreateList(SqList *&L,ElemType a[],int n)
{
int i;
for(i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
2.2.2 顺序表的建立及基本运算的实现问：若 n>MaxSize,会出现什么问题？
如何改进？
21
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(1)初始化线性表 InitList(L):构造一个空的顺序表
void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList));//分配存储空间
L->length=0;//将顺序表长度设置为 0
}
该算法 (函数 )为线性表分配内存空间,并将线性表长度设置为 0(表示是一个空表 )。
2、顺序表基本运算算法
22
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(2)销毁线性表 DestroyList(L):释放顺序表占用的内存空间
void Destroy(SqList *&L)
{
free(L);
}
(3)判断线性表是否为空 ListEmpty(L):若 L为空返回真
(即 1),否则返回假 (即 0)
int ListEmpty(SqList *L)
{
return(L->length==0);
}
23
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(4)求线性表长度 ListLength(L):返回 L中元素个数
int ListLength(SqList *L)
{
return(L->length);
}
(5)输出线性表 DispList(L):顺序显示 L中各元素的值
void DispList(SqList *L)
{
int i;
if(ListEmpty(L)) return;//若线性表为空,返回
for(i=0;i<L->length;i++)
printf("%c",L->data[i]);
printf("\n");
}
24
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(6)求线性表中第 i个元素的值 GetElem(L,i,e):
int GetElem(SqList *L,int i,ElemType &e)
{
if(i<1 || i>L->length)
return 0; //位序参数不正确,函数返回假
e=L->data[i-1]; //取出表中第 i个元素的值
return 1; //运算成功,函数返回真 (1)
}
25
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(7)按元素查找 LocateElem(L,e):在 L中查找第一个值域与 e相等的元素的逻辑位序
int LocateElem (SqList *L,ElemType e)
{
int i=0;//从第 1个元素开始查找
while(i<L->length && L->data[i]!=e) i++;
if(i>=L->length)
return 0;//查不到,返回 0
else
return i+1;//返回查到元素的位序值
}
26
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e
插入前,L＝ (a1,…a i-1,ai,…,an)
插入后,L＝ (a1,…a i-1,e,ai,…,an)
① 进行合法性检查,1≤i ≤ n+1；
② 检查线性表是否已满；
③ 将第 n至第 i个元素逐一后移一个单位；
④ 在第 i个位臵处插入新元素；
⑤ 将表的长度加 1。
算法思想：
27
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e
‘q’
‘a’
‘b’
0
1
2
5
‘f’
3
4
6
7
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
设调用为 ListInsert(L,5,‘g’)
i--; i=4
‘d’
‘c’
线性表长度 L->length=？
‘g’
j=6=5=4
线性表长度 =6
插入前的线性表：
L=(‘q’,‘a’,‘f’,‘b’,‘d’,‘c’)
‘g’L->length++;
=7
28
2.2线性表的顺序存储结构插入算法 ListInsert (L,i,e)
int ListInsert( SqList *&L,int i,ElemType e)
{/*在顺序存储结构的线性表 L的第 i个 DE位臵插入 e*/
int j;
if(i<1||i>L->length+1) return 0; /*i的合法性判断 */
if (L->length==MaxSize ) return 0 ; /*表满 */
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
i--;
L->length++;
return 1;
}
29
2.2线性表的顺序存储结构
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e的算法时间复杂度分析,
设表长 L->length=n(本例 n=6)
若插入位置 i=1,移动次数为,n次若插入位置 i=2,移动次数为,n-1次算法的时间复杂度 T(n)=O(n)
若插入位置 i=3,移动次数为,n-2次…
若插入位置 i=n+1,移动次数为,0次若插入位置为 i(i∈ {1,2,…,n+1})
移动次数为,n-i+1次
=n-1+1
=n-2+1
=n-3+1
=n-(n-1)+1
按最坏情况计 (i=1)
分析方法 1(考虑最坏情况 ):
‘q’
‘a’
‘b’
0
1
2
5
‘f’
3
4
6
7
‘d’
‘c’
30
2.2线性表的顺序存储结构
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e的算法时间复杂度分析,
设表长 L->length=n(本例 n=6)
T(n)=
线性表有 n+1个位置可插入一次新元素分析方法 2(计算每个位置上可能出现插入的平均次数 )
则在任一位置 i∈ {1,…,n+1} 上插入一次的概率是,1/(n+1)
则在每个位置上都可能出现插入的移动次数的期望值
(即以概率为权的加权平均值）为,
1
1
)1(
1
1n
i
in
n
=O(n)
根据方法 1的分析,在 i上插入,需移动的次数为,n-i+1次
31
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(9)删除数据元素 ListDelete(L,i,e):删除线性表 L的第
i个元素,并用变量 e返回该元素的值
删除前,L＝ (a1,…a i-1,ai,a i+1 …,an)
删除后,L＝ (a1,…a i-1,ai+1,…,an)
① 进行合法性检查,i是否满足 1≤i ≤ n；
② 判断线性表是否已空,L－ >Length是否为 0；
③ 将第 i个位臵的 DE赋给 e；
④ 将第 i+1至第 n个元素逐一向前移一个单位；
⑤ 将表的长度减 1。
算法思想：
32
2.2线性表的顺序存储结构
(9)删除数据元素 ListDelete(L,i,e):删除线性表 L的第
‘q’
‘a’
0
1
2
5
‘f’
3
4
6
7
‘d’
‘c’
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;//
设调用为 ListDelete(L,4,e)
‘b’
i=3是第 4个元素的下标
e=‘b’用于返回该元素值
j=3,表长 =6,
L->data[3]=L->data[4]
=4 表长
4 5
j=5,表长 =6,
删除了一个元素，线性表长度减 1
i个元素,并用变量 e返回该元素的值 表长度 =6=5
‘q’
‘a’
‘f’
‘d’
‘c’
‘b’
33
2.2线性表的顺序存储结构删除算法 ListDelete (L,i,e)
int ListDelete(Sqlist *&L,int i,elemtype &e)
{/*在顺序存储结构的线性表 L中删除第 i个 DE，并用 e返回 */
int j;
if(i<1||i>L->length) return 0;/*i值有错或者表已空 */
e=L->data[i-1]; /*将被删除元素赋给 e*/
for(j=i;j<=L->length;j++) /*将第 i+1至 n个元素前移 */
L->data[j-1]=L->data[j];
L->length--; /*表长减 1*/
return 1;
}
34
2.2线性表的顺序存储结构删除算法 ListInsert (L,i,e)
执行次数与 删除位臵 i及 n有关：
问题规模是表的长度 n
最好情况,
最坏情况,
i=n时，移动次数为 0
i=1时，移动次数为 n-1，时间复杂度为 O（ n）
n-i删除第 i个元素时，须执行的次数为：
时间复杂度分析因此,T（ n）＝ O（ n）
等概率的情况下，移动的平均次数为：
2/)1()(
1
ninPEis n
i
i
因此,T（ n）＝ O（ n）
35
2.2线性表的顺序存储结构线性表顺序存储结构的特点
1,逻辑上相邻的元素，其物理位臵也相邻；
2,可随机存取表中任一元素；
3,必须按最大可能长度预分配存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构；
4,插入删除时，需移动大量元素，平均移动元素为 n/2。
36
2.2线性表的顺序存储结构例 2.4 有一个顺序表 L，假设元素类型 ElemType为整型，并且所有元素均不相等。设计一个算法，以第一个元素为分界线，将所有小于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。
算法思想：
(1)设臵变量 i，初值为 0,j初值为 L->Length-1;
基准 pivot为 L->data[0].
(2)当 i!=j时：
从右向左扫描,j>i时，将 data[j]与 pivot比较，若
data[j]>pivot,j--;否则，将 data[j]赋给 data[i]。
从左向右扫描,i<j时，将 data[i]与 pivot比较，若
data[i]<pivot,i++;否则，将 data[i]赋给 data[j]。
(3)当 i=j时：将 pivot赋给 data[i].
37
3 5 6 1 4 2 7 9 8 0
pivot=L->data[0]=3
0 5
61 3
i ji i i jjjjjj
2
int i=0,j=L->length-1;
ElemType pivot=L->data[0];
while(i!=j)
{
while(j>i&&L->data[j]>pivot)
j--;
L->data[i]=L->data[j];
while(i<j&&L->data[i]<pivot)
i++;
L->data[j]=L->data[i];
}
L->data[i]=pivot;
38
2.2线性表的顺序存储结构例 2.11 在顺序存储结构上归并两个有序的线性表
LA和 LB为一个新的有序线性表 LC。
① 初始化,臵 LC为空表,设臵变量 i,j初值为 0,分别指向
LA和 LB的第一个 DE,k表示 LC的长度,初值为 0。
② 当 i<=Length(LA) and j<=Length(LB),
判断,若 i所指的元素 <j所指的元素,则将 i所指的元素插入在 LC的 k+1(表尾 )前,并且 i,k的值分别加 1;
否则,将 j所指的元素插入在 LC的 k+1(表尾 )前,并且 j,
k的值分别加 1。
③ 重复第二步直到某个表的元素插入完毕。
④ 将未插入完的表中余下的元素，依次插入在 LC后。
算法思想：
39
2.2线性表的顺序存储结构例：顺序结构上的归并有序表算法
Void UnionList( Sqlist*LA,Sqlist*LB,Sqlist*&LC)
{ int i=0,j=0,k=0; /*i,j,k分别作为 LA,LB,LC的下标 */
LC=(SqList *)malloc (sizeof (Sqlist));
LC->Length=0;
while (i< LA->Length && j< LB->Length){
if (LA->data[i]<LB->data[j])
{LC->data[k]= LA->data[i]; i++; k++;}
else
{LC->data[k]= LB->data[j]; k++; j++;}
}
while (i< LA->Length) /*LA未完，将其余元素插入 LC中 */
while ( j< LB->Length) /*LB未完，将其余元素插入 LC中 */
{LC->data[k]= LA->data[i]; i++; k++;}
LC->Length=k;
{LC->data[k]= LB->data[j]; k++; j++;}
}
时间复杂度：
T(n)=O(ListLength(LA)+ListLength(LB))
40
2.3 线性表的链式存储结构
2.3.1 线性表的链式存储结构 —链表
2.3.2 单链表基本运算的实现
2.3.3 双链表
2.3.4 循环链表
2.3.5 静态链表
41
2.3.1 线性表的链式存储结构 —链表
1、线性表的顺序存储结构存在的缺陷由于顺序表所能存储的最大元素个数 (MaxSize)事先由设计人员估计给定，
在程序运行过程中是个固定值。
(1)若事先估计不足，会造成数组下标越界
(2)若估计,过量,,会造成存储空间极大浪费
42
2.3.1 线性表的链式存储结构 —链表
2、链表由若干个含有 数据域 和 指针域 存储单元组成，这些存储单元称为结点，存储单元的地址常常是不连续的，称这样的存储结构为链表。
data
数据域
next
指针域 data数据域 next指针域结点 a 结点 b
‘h’ ‘g’结点 b地址
43
2.3.1 线性表的链式存储结构 —链表
3、链式存储结构的特点
(1)用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
(2)存储单元称为结点，每个结点由
2种类型的存储区域组成,
a.存储数据的区域
b.存储地址的区域称为数据域称为指针域
(3)链表的结点是在程序运行过程中动态建立的，与顺序存储结构不同，不必事先给定链表结点最大数目。
44
2.3.1 线性表的链式存储结构 —链表
4、单链表每个结点都有 1个数据域和一个指针域的链表称为单链表。
…head a1 a2 an ∧
NULL
开始结点 终端结点头结点头指针说明,链表的第 1个结点称为头结点,其数据域不存储数据,其指针域存储的是开始结点的首地址。若头结点指针域为空，表明链表为空表。
45
2.3.1 线性表的链式存储结构 —链表
5、双链表每个结点都有 1个数据域和 2个指针域的链表称为双链表。
a1 a2 … an ∧dhead
开始结点 终端结点头结点头指针
46
2.3.1 线性表的链式存储结构 —链表
typedef struct LNode//定义单链表结点的结构体
{
ElemType data;//数据域
struct LNode *next;//指针域,存放后继结点地址
}LinkList;
6、用 C/C++实现链式存储结构 (单链表 )
#include "stdafx.h"
#include "malloc.h"//为了使用内存分配语句 malloc
typedef int ElemType ;
(1)申明与定义
47
N个结点通过指针域组成的表，称为 线性链表 （单链表）
线性链表最后一个结点的指针域为“空” (NULL或 ∧ )；
用一个头指针指示链表中的第一个结点的存储位臵；
链表 L=(a1,a2,….a n)逻辑表示为：
头指针head a
1 a2 an ^…...
开始结点 空表,head=NULL
2.3.1 线性表的链式存储结构 —链表空表时：判空条件是？
头指针
…...head
头结点
a2 an ∧a1
开始结点 终端结点带头结点链表的引入是为了便于插入和删除算法的实现
，使算法的实现和判空等其他的处理达到一致。
Head－ >next=Null
48
2.3.1 线性表的链式存储结构 —链表
LinkList *head,*p;定义指向单链表结点的指针变量
head=(LinkList *)malloc(sizeof(LinkList));
/*在内存空间建立一个结点，结点首地址返回给指针变量 head */
head->next=NULL; //指针域设臵为空,表明该结
//点无后继结点,
head
(2)建立单链表
p=(LinkList *)malloc(sizeof(LinkList));
∧ p
head->next=p; p->data=‘a’;
‘a’
p->next=NULL;
∧
49
2.3.2 单链表基本运算的实现
1.插入结点运算结点 a 结点 b
‘h’ ‘i’
data nextdata next
……
—在结点 b前插入新结点 x
结点 x
‘k’
data next
S
P
S->next=P->next;
P->next=S;
结点 a 结点 b
‘h’ ‘i’
data nextdata next
……
结点 x
‘k’
data next
S
P
50
2.3.2 单链表基本运算的实现
2.删除结点运算结点 a 结点 c
‘a’ ‘c’
data nextdata next
……
结点 b
‘b’
data nextP
p->next=p->next->next;
—删除结点 b
(1)最简单的情形
51
2.3.2 单链表基本运算的实现
2.删除结点运算结点 a 结点 c
‘a’ ‘c’
data nextdata next
……
结点 b
‘b’
data nextP
p->next=p->next->next;
free(s);
—删除结点 b
S
(1)最简单的情形
p->next=s->next;
(2)使用指针 S指向结点 b
s=p->next;
52
2.3.2 单链表基本运算的实现
3、建立单链表
(1)头插法建表,
从一个空链表开始，依次从数组 a中读取一个元素 ai(i∈ {0,…,n -1}),使用内存分配语句生成一个新结点，将 ai的值存放到新结点数据域中，然后将新结点插入到当前链表表头的后继结点上 (即新结点总是插入到表中开始结点的位臵上 —头插法 ),直到数组 a中所有元素读完并全部插入到链表中为止。
53
LinkList *s; int i;
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL:
for(i=0;i<n;i++)
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=a[i];
s->next=L->next;
L->next=s;
}
‘a’
‘b’
‘c’
‘d’
0
1
2
3
数组 a,n=4
i
L ∧
s
‘a’ ∧
s
‘b’
‘a’ ∧b’
c’
c’ b’ ‘a’∧
d’
‘a’∧b’c’d’
结束头插法建立单链表的过程
4
54
‘a’
‘b’
‘c’
‘d’
0
1
2
3
数组 a,n=4
L ‘a’∧‘b’‘c’‘d’
由此可见，头插法生成的链表中结点的次序与原数组元素的顺序相反头结点头插法建立单链表的结果
55
(1)头插法建表的完整算法,
void CreateListF(LinkList *&L,ElemType a[],int n)
{ /*将数组 a中的 n个元素用头插法建立单链表 L*/
LinkList *s; int i;
L=(LinkList *)malloc(sizeof(LinkList)
/*创建头结点 */
L->next=NULL;
for (i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList))
/*创建新结点 */
s->data=a[i]; s->next=L->next;L->next=s;
} /*将 *s插在原开始结点之前,头结点之后 */
}
56
2.3.2 单链表基本运算的实现
3、建立单链表
(2)尾插法,
从一个空链表开始，依次从有 n个元素的数组 a中读取一个元素 ai(i∈ {0,…,n -
1}),使用内存分配语句生成一个新结点，
将 ai的值存放到新结点数据域中，然后将新结点插入到当前链表表尾上 (即总是表尾的终端结点位臵上插入新结点 —尾插法 ),直到数组 a中所有元素读完并插入到链表中为止。
57
LinkList *s,*r; int i;
L=(LinkList*)malloc(sizeof(LinkList));
r=L;
for(i=0;i<n;i++)
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=a[i]; r->next=s; r=s;
}
r->next=NULL:
‘a’
‘b’
‘c’
‘d’
0
1
2
3
数组 a,n=4
i
L
s
‘a’ ‘c’‘b’ ‘d’∧
尾插法建立单链表的过程
s s s
r r r r r
4
58
(2)尾插法建表的完整算法,
void CreateListR(LinkList *&L,ElemType a[],int n)
{ /*将数组 a中的 n个元素用尾插法建立单链表 L*/
LinkList *s,*r; int i;
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL; /*创建头结点 */
r=L; /*r始终指向终端结点,开始时指向头结点 */
for (i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点 */
s->data=a[i];r->next=s; /*将 *s插入 *r之后 */
r=s;
}
r->next=NULL;/*终端结点 next域臵为 NULL*/
}
59
(1)初始化线性表
4.采用单链表实现线性表基本运算的算法建立一个空链表 (即只有一个头表结点的链表 )
L ∧
头结点
void InitList(LinkList *&L)
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
60
(2)销毁线性表
4.采用单链表实现线性表基本运算的算法
void DestroyList(LinkList *&L)
{
LinkList *p=L,*q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
L ‘a’ ‘c’‘b’ ‘d’∧
头结点 q
p
∧
结束
61
4.采用单链表实现线性表基本运算的算法
(3)判断线性表是否为空
int ListEmpty(LinkList *L)
{
return(L->next==NULL);
}
62
4.采用单链表实现线性表基本运算的算法
(4)求线性表的长度 ListLength(L)
a1 a2 an-1 ^an…
L p
i=0
p
i++
int ListLength(LinkList *L)
{ /*求单链表 L的长度 */
LinkList *p=L; int i=0;
while (p->next!=NULL)
{ i++; p=p->next;}
return(i);
}
int ListLength(LinkList *L)
{ /*求单链表 L的长度 */
LinkList *p=L->next;
int i=0;
while (p!=NULL)
{ i++; p=p->next;}
return(i);
}
63
(5) 输出线性表 DispList(L)
void DispList(LinkList *L)
{ /*输出单链表 L中的所有 DE*/
LinkList *p=L->next;
while (p!=NULL)
{ printf("%c",p->data);
p=p->next;
}
printf("\n");
}
a1 a2 an-1 ^an…L
4.采用单链表实现线性表基本运算的算法
64
int GetElem(LinkList *L,int i,ElemType &e)
{ /*取单链表 L中的第 i个 DE,并用 e返回 */
[臵初值部分 ]
while (循环控制条件 )
[循环体 ]
if (出循环后判断条件 ) return 0;
else
{ e=p->data;
return 1;
}
}
(6)取元素函数 GetElem (L,i,e)
4.采用单链表实现线性表基本运算的算法
65
int GetElem(LinkList *L,int i,ElemType &e)
{ int j=1; LinkList *p=L->next;
/*移动指针 p，计数变量 j*/
while (j<i && p!=NULL)
{ j++;
p=p->next; }
if (p==NULL) return 0;
else
{ e=p->data;
return 1;}
}
问题：如何臵初值？怎样对 i的合法性进行检查?如何确定出循环的判定条件？
if (j>i) return 0;
{ e=p->data;
return 1;
}
else或
4.采用单链表实现线性表基本运算的算法
66
循环条件分析：
int j=1; LinkList *p=L->next; while (j<i && p!=null)
条件 1控制取第 i个，防止了 i<1,条件 2防止 i>表长。
两个条件有 6种组合：
1,j<i && p=null 空表且 i>1或 i>表长 +1,异常,return 0；
2,j=i && p=null 空表且 i=1或 i=表长 +1,异常,return 0；
3,j>i && p=null 空表且 i<1,异常,return 0；
4,j<i && p!=null 继续循环；
5,j=i && p!=null 确定第 i个结点，正常出循环；
6,j>i && p!=null i<1，异常出循环,return 0；
4.采用单链表实现线性表基本运算的算法
67
int GetElem(LinkList *L,int i,ElemType &e)
{ int j=1; LinkList *p=L->next;
while (j<i && p!=NULL)
{
j++; p=p->next; }
if (p==NULL||j>i) return 0;
else { e=p->data; return 1;}
}
//条件 1控制取第 i个,防止了 i<1,条件 2防止 i>表长
{只用一个条件是不充分的 }
{移动指针 p,计数变量 j}
i的 合法性判断 已经蕴涵在 while和 if条件中；
算法时间复杂度分析,while最多执行 i-1次，最坏情况是取第 n个结点，需执行 n-1次，因此：
T(n)=O(n)
(6)取元素函数 GetElem (L,i,e)
4.采用单链表实现线性表基本运算的算法
68
4.采用单链表实现线性表基本运算的算法
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p=L->next;
int n=1;
while (p!=NULL&&p->data!=e)
{
p=p->next;//指向下一个结点
n++;//结点位序号加 1
}
if(p==NULL)
return(0);
else
return(n);//找到，函数返回位序号
}
(7)按元素值查找 LocateElem (L,i,e)
69
定位：得到指向第 i个 DE的直接前驱的指针 p；
插入运算可由定位、生成新结点和修改指针三步来完成,
生成新结点：利用 malloc函数生成一个新的结点 s；
修改指针,s->next=p->next;
p->next=s;
顺序不能变注意,凡是对 next域进行修改时，一定要检查原来的 next域指针所指的结点是否已经有其他的指针指向该结点，否则就会出现断链的可能。
(8)插入运算 ListInsert (L,i,e)
4.采用单链表实现线性表基本运算的算法
70
(8)插入元素数据 ListInsert(L,i,e)
int j=0;LinkList *p=L,*s;
while(j<i-1 && p!=NULL)
{
j++;p=p->next;
}
if(p==NULL||j>i-1)
return 0;
else
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
} L ‘a’
‘c’
‘b’ ‘d’∧
p
s
设调用语句为,ListInsert(L,3,‘c’)
j=0i=3 12
算法思路,先在单链表中寻找第 i-1个结点，若找到，则将新结点插入到第 i-1
个结点之后 (即第 i个结点之前 )。
71
int ListInsert(LinkList *&L,int i,ElemType e)
{ /*在单链表 L的第 i个位臵插入元素 e*/
int j=0; LinkList *p=L,*s;
while (j<i-1 && p!=NULL)
/*查找第 i-1个结点 */
{ j++; p=p->next;}
if (p==NULL||j>i-1) return 0;
/*未找到位序为 i-1的结点 */
else /*找到位序为 i-1的结点 *p*/
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点 *s*/
s->data=e;
s->next=p->next; /*将 *s插入到 *p之后 */
p->next=s;
return 1;
}
}?算法时间复杂度分析,T(n)=O(n)
4.采用单链表实现线性表基本运算的算法
72
与 GetElem(L,i,e)函数的区别：
初值保证能在第一个 DE之前插入,1≤i ≤表长 +1
循环定位条件,定位 在 i的直接前驱 i-1.?
循环条件分析,?
第一次循环 p!=null,j有三种可能：
1,j<i-1 继续循环；
2,j=i-1 此时 i=1,表示在第一个元素前作插入操作；
3,j>i-1 此时 i<1不合法；
第二次循环后 p可能为 null,但 j>i-1不可能，出现的各种可能情况如下：
1,p!=null &&j<i-1 继续循环；
2,p!=null && j=i-1 已经定位，出循环；
3,p=null && j<=i-1 i不合法 (i>=表长 +2),出循环
4.采用单链表实现线性表基本运算的算法
73
a…
p
b …
(a) 删除前
a…
p
b …
(b)p->next=p->next->next
a…
p
…
(c) 删除后删除运算可由定位
、修改指针和释放结点来完成
定位：得到指向 b的直接前驱 a的指针 p；
修改指针,q=p->next;
p->next= p->next->next;
释放结点,free(q);
（ 9）删除运算 ListDelete (L,i,e)
4.采用单链表实现线性表基本运算的算法
74
int ListDelete(LinkList *&L,int i,ElemType &e)
{ /*删除单链表 L中的第 i个 DE，并用 e返回 */
int j=0; LinkList *p=L,*q;
while (j<i-1 && p->next!=NULL) /*查找第 i-1个结点 */
{ j++; p=p->next;}
if (p==NULL||j>i-1) return 0;
/*未找到位序为 i-1的结点 */
else /*找到位序为 i-1的结点 *p*/
{ q=p->next; /*q指向要删除的结点 */
e=q->data;
p->next=q->next; /*从单链表中删除 *q结点 */
free(q); /*释放 *q结点 */
return 1;
}
}
4.采用单链表实现线性表基本运算的算法
75
删除算法讨论：
删除范围为 [1,表长 ]，不能删除头结点；
出循环的 5种可能情况：
1,p->next=null &&j<i-1 空表或 i>表长
2,P->next=null && j=i-1 空表且 i=1,或 i＝表长 +1
3,p-next=null && j>i-1 空表且 i<1
4,p->next!=null &&j=i-1 非空表且已定位
5,P->next!=null && j>i-1 非 空表且 i<1
时间复杂度分析,while至多执行 i-1次，当
i=n时为最坏情形，故,T(n)=O(n)
4.采用单链表实现线性表基本运算的算法
76
5.线性表链式存储结构的特点
1,逻辑上相邻的元素，其物理位臵不一定相邻；
元素之间的邻接关系由指针域指示。
2,链表是非随机存取结构；对链表的存取必须从头指针开始。
3,链表是一种动态存储结构；链表的结点可调用 malloc()申请和 free()释放。
4,插入删除运算非常方便；只需修改相应的指针值。
77
例 2.5 有一个带头结点的单链表 L={a1,b1,a2,b2,…a n,bn},
设计一个算法将其拆分成两个带头结点的单链表 L1和
L2,L1={a1,,a2,…a n},L2={bn,bn-1,…b 1}。要求 L1使用 L的头结点。
① 初始化,p指向 L的第一个 DE结点,臵 L2为空表,p2指向
L2,L1,r1指向 L的头结点,设臵变量 i初值为 0。
② 当 p!=NULL时,
判断,if(i%2==0) 用头插法将 *p插入到 L2当中，否则用尾插法将 *p插入到 L1当中。
③ 将利用尾插法建立的最后一个数据结点的 next域臵为
NULL。
算法思想：
书中对于该例题给出的算法，本人认为可移植性差或者说健壮性较差，因为只要给出的单链表 L的 DE不是偶数，该算法就不能执行。
78
void split(LinkList *&L,LinkList *&L1,LinkList *&L2)
{ int i=0;
LinkList *r1,*p2,*s,*p=L->next;
r1=L1=L;
L2=(LinkList*)malloc(sizeof(LinkList));
L2->next=NULL;p2=L2;
while (p!=NULL)
{ i++;
if (i%2==0)
{ s=p->next; p->next=p2->next;
p2->next=p; p=s;
}
else { r1->next=p; r1=p; p=p->next;}
} r1->next=NULL;
}
79
[例 2.6]有一个带头结点的单链表 L,设计一个算法使其元素递增有序。
L 9 76 1 ∧
L 1 76 9 ∧
80
void Sort(LinkList *&L)
{
LinkList *p=L->next,*q,*r;
if(p!=NULL)
{
r=p->next; p->next=NULL;
p=r;
while(p!=NULL)
{ r=p->next; q=L;
while(q->next!=NULL&&q->next->data<p->data)
q=q->next;
p->next=q->next; q->next=p; p=r;
}
}
}
L 9 106 1 ∧
p
r
∧
q NULL
NULL
结束
∧
81
L 1 6 9 10 ∧
L成为一个元素递增有序的单链表
L 9 106 1
p
r
q NULL
NULL
∧
82
例：在单链表上实现归并两个有序表，要求产生的结果有序表仍旧用原有序表的结点空间。
void unionlist(LinkList *&LA,LinkList *&LB,LinkList *&LC)
{ /*已知单链线性表 LA和 LB的元素按值非递减排列，归并 LA
和 LB得到新的单链线性表 LC,LC的元素也按值非递减排列 */
/*用 LA的头结点作为 LC的头结点 */
/*插入剩余段 */
/*释放 LB的头结点 */
Linklist *pa,*pb,*pc;
pa= LA->next; pb=LB->next;
LC=pc=LA;
while(pa!=null&&pb!=null)
{ if(pa->data<pb->data) {pc->next=pa;pc=pa; pa=pa->next;}
else {pc->next=pb; pc=pb;pb=pb->next;}}
if(pa!=null) pc->next=pa;
esle pc->next=pb;
free(LB)}
83
1 3 4 ^6LA
2 5 7 ^8LB
pa
pb
pc
LC
pc pa
pc pb
pc papapc pa
pc pbpc
pc
1 2 3 4LC
5 6 7 ^8
84
单链表中的缺陷在单链表中,由于每个结点只包含有一个指向后继结点的指针,所以当访问过一个结点后,只能接着访问它的后继结点,而无法访问它的前驱结点 。
85
2.3.3 双链表
…L a1 a2 an ∧
数据域指针域 指针域
prior data next
(1)双链表的结点结构
(2)双链表存储前驱结点首地址存储后继结点首地址
86
2.3.3 双链表
typedef struct LNode//
{
ElemType data;//数据域
struct LNode *next;//后继指针域
struct LNode *prior;//前驱指针域
}DLinkList;
(3)定义双链表结点类型说明,双单链表只比单链表多了个前驱指针，
因而单链表的所有基本运算算法都适合于双链表，但有些算法 (如插入和删除结点 )要相应增加对前驱指针的处理语句。
87
2.3.3 双链表
(4)双链表的插入 —在指针 p所指的结点 A
后插入一个新结点 C
……
s
p
操作过程操作语句
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
……
p s
prior next
data
prior next
data
prior next
data
A B
C
A BC
88
2.3.3 双链表
(5)双链表的删除 —删除指针 p所指结点的后继结点 S
……
p s
p->next=s->next; 或 p->next=p->next->next;
s->next->prior=p;
free(s);
89
2.3.3 双链表
(6)双链表基本运算的实现双链表的基本运算算法,与单链表相似，不再在课堂上详细介绍,留给同学们自学，双链表的所有基本运算算法都要掌握！自学时要注意与单链表的相应算法进行比较。
90
2.3.3 双链表
[例 2.7](p48)
L 1 5 9 ∧7
L 9 7 1 ∧5
[例 2.8](p49)
L 5 7 1 ∧9
L 1 5 9 ∧7
91
1,循环单链表
2.3.4 循环链表
L ‘a’ ‘c’‘b’ ‘d’∧
2,循环双链表
…L a1 a2 an ∧
p若 p->next==L,则结点 p是尾结点。
“头尾相连,的链表
92
[例 2.9](p50)有一个带头结点的循环单链表 L，
设计一个算法统计其 data域值为 x的结点个数。
同学们自己分析课本给出的算法
2.3.4 循环链表
[例 2.10](p50)同学们自己分析课本给出的算法
93
a.静态链表的结构体申明
2.3.5 静态链表
#define MaxSize 100 //能存储的最大元素个数
typedef char ElemType[10];
typedef struct
{
ElemType data;//数据域,最多放 10个字符
int next;//游标域,存放后继结点的下标
} StaticList[MaxSize];
StaticList sL;
用一维数组来描述的链式线性表
94
b.静态链表的存储结构
2.3.5 静态链表数组下标 data next
数据序号
0 3 表头
1 张斌 4 2
2 刘丽 5 4
3 李英 1 1
4 陈华 2 3
5 王奇 6 5
6 董强 7 6
7 王萍 0 7
8 -1
9 -1
3 李英 1 张斌 4 陈华 2 刘丽 5 王奇 6 董强 7 王萍 0
下标,0 3 1 4 2 5 6 7
1 2 3 4 5 6 7表头
typedef char ElemType[8];
#define MaxSize 10
…
typedef struct
{
ElemType data;
int next;
}StaticList[MaxSize];
…
StaticList sL;
sL[3].data=“李英” sL[3].next=1
静态链表
sL
空结点
95
数组下标 data next
数据序号
0 3 表头
1 张斌 4 2
2 刘丽 5 4
3 李英 1 1
4 陈华 2 3
5 王奇 6 5
6 董强 7 6
7 王萍 0 7
8 -1
9 -1
删除陈华数组下标 data next
数据序号
0 3 表头
1 张斌 2 2
2 刘丽 5 3
3 李英 1 1
4 陈华 -1
5 王奇 6 4
6 董强 7 5
7 王萍 0 6
8 -1
5 -1
sL[1].next=sL[4].next;
3 李英 1 张斌 4 陈华 2 刘丽 5 王奇 6 董强 7 王萍 0
下标 0 3 1 4 2 5 6 7
1 2 3 4 5 6 7表头
sL[4].next=-1;
李英 张斌 2 刘丽 5 王奇 6 董强 7 王萍 0
下标 2 5 6 7
1 2 6表头
96
静态链表特点
1、链表的最大长度为表中可容纳的数据结点的最大个数,是一固定值，在程序执行期间不能改变；
2、当链表的数据结点数等于最大长度时，称链表已满,此时不能再插入新的数据结点 (上溢）；
3、链表中每个数据结点的游标域的值是该结点的后继结点的一维下标，处于表尾的数据结点的游标域的值总是设为 0（表示无后继）；
4、若头结点的游标域为 0，表明为空表；
97
4、表中被删除的数据结点的游标域的值总是设为 -1,表明为空结点；
5、与动态链表相似,静态链表的头结点的数据域不用于存储数据，头结点的后继是表中第 1个数据结点，第 1个数据结点的后继为表中的第 2个数据结点，以此类推,第 n-1个数据结点的后继为表中的第 n个数据结点,n称为数据结点序号，它并不一定等于数据结点的一维下标。
静态链表特点
98
小 结本章作业：练习题 2.1,2.2,2.3
(2)深入掌握线性表的两种存储方法
a.顺序表
b.链表动态链表静态链表单链表双链表循环单链表非循环单链表循环双链表非循环双链表
(3)重点掌握顺序表和链表的各种基本运算算法
(1)理解线性表的逻辑结构特点
99
第二章 习题
1.线性表的逻辑顺序和物理顺序总是一致的，这种说法 ——.
A 正确 B 不正确
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ——.
A 必须连续 B 部分地址必须连续
C 一定是不连续的 D 连续不连续都可以
2.不带头结点的单链表 head为空的判定条件是 ——.
A head=Null B head->next=Null
C head->next=head D head!=Null
100
第二章 习题
4,非空循环单链表 head尾结点 *P满足 ——.
A p->next=Null B p=Null
C p->next=head D p=head
5,在一个单链表中，已知 *q结点是 *P结点的前驱结点，若 *q结点和 *P结点之间插入 *s结点，则执行 ——.
A s->next=p->next; p->next=s;
B p->next=s->next; s->next=p;
C q->next=s; s->next=p;
D p->next=s; s->next=q;
第二章 线性表
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.4 顺序表的应用
2.5 有序表
2.1 线性表及其逻辑结构
线性表的逻辑结构和物理结构，以及它们之间的相互关系
定义与之相适应的运算
设计相应的算法
分析算法的效率
2
2.1线性表及其逻辑结构
1.线性表具有相同特性的 n个数据元素的一个有限序列,
记为 L＝ (a1,a2,… ai,ai+1,…,an)
数据元素之间的关系是：
ai-1领先于 a i,a i领先于 a i＋ 1，即元素在位臵上是有序的；
称 ai-1是 a i的直接 前驱 元素,a i+1是 a i的直接 后继 元素；
除 a1外，每个元素 有且仅有一个 直接前驱元素；
除 an外，每个元素 有且仅有一个 直接后继元素；
线性表中数据元素的个数 n(n>=0）称为线性表的 长度 ；
当 n=0时，称为 空表 。
3
2.1线性表及其逻辑结构线性表是最常用且最简单的一种数据结构它的 形式化定义 为,List=(D,R)
其中,D={ai|1≤i ≤n,ai属 ElemType类型 }
R={r}
r={<ai,ai+1>| 1≤i ≤n-1}
R是一个序偶的集合，表示线性表中数据元素之间的相邻关系。
逻辑图
a1 a2 … ai ai+1 an…
4
2.1线性表及其逻辑结构
ADT List
{
数据对象：
D={ai| 1≤i≤n,n≥0,ai是 ElemType类型 }
数据关系：
R={<ai,ai+1>|ai,ai+1∈ D,i=1,…,n -1}
基本运算：
InitList(&L):初始化线性表,构造一个空表
DestroyList(&L):销毁线性表,释放表占存储空间…
Displist(L);输出线性表,显示表中所有元素值
}
ElemType是任何合法的数据类型
5
例 1 分析 26 个英文字母组成的英文表,
（ A,B,C,D,……,Z ）
例 2 分析学生情况登记表,
分析,数据元素都是同类型 (字符 ),元素间关系是 线性 的姓 名 学 号 性 别 年龄 健康情况王小林 790631 男 18 健康陈 红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
分析,数据元素都是同类型 （记录），
元素间关系是 线性 的。
2.1线性表及其逻辑结构
6
2.1线性表及其逻辑结构
2.基本运算
InitList(L),初始化线性表：构造一个空的线性表 L
DestroyList(L),销毁线性表：释放线性表 L占用的内存空间。
ListEmpty(L),判线性表是否为空表,若 L为空表,则返回真,否则返回假
ListLength(L),求线性表的长度,返回 L中元素个数。
DispList(L),输出线性表,当线性表 L不为空时,顺序显示 L中各结点的值域。
7
2.1线性表及其逻辑结构
GetElem(L,i,e):求线性表 L中指定位臵的某个数据元素,用 e返回 L中第 i （ 1≤i≤ ListLength(L))个元素的值。
ListDelete(L,i,e),删除数据元素：删除 L中的第 i
（ 1≤i≤ListLength(L))个元素，并用 e返回其值,L的长度减 1。
LocateElem(L,e),定位查找,返回 L中第 1个值域与
e相等的位序。若这样的元素不存在,则返回值为 0。
ListInsert(L,i,e),插入数据元素：在 L的第 i(
1≤i≤ListLength(L)+1)个元素之前插入新的元素 e，
L的长度增 1。
想一想：这些运算已经实现了吗？
8
对上述的运算的两点说明：
这些运算是在逻辑结构上定义的操作。只给出这些运算的功能是,做什么,,至于,如何做,等实现细节，只有待确定了存储结构之后才考虑。
这些运算仅是基本运算集，基于基本运算可进行复杂的运算，即通过基本运算可派生出复杂的运算。
2.1线性表及其逻辑结构
9
例 2.1 有一个线性表 L=(‘a’,‘c’,‘a’,‘d’,‘b’),求以下基本运算的执行结果
ListLength(L)
ListEmpty(L)
GetElem(L,3,e)
LocateElem(L,‘a’)
ListInsert(L,4,‘e’)
ListDelete(L,3)
=5
=0
e=‘a’
=1
L=(‘a’,‘c’,‘a’,‘e’,‘d’,‘b’)
L=(‘a’,‘c’,‘e’,‘d’,‘b’)
2.1线性表及其逻辑结构
10
2.1线性表及其逻辑结构例 2.2 求两个集合的并,即 C=A∪ B
分析：设 A,B分别由两个线性表 LA和 LB表示，要求将 LA和 LB合并后的 DE放入到线性表 LC中。
算法思想：
① 初始化 LC；
② 将 LA中所有元素复制到 LC中；
③ 依次从 LB中取出一个 DE；
④ 判断 LC中是否存在；
⑤ 若不存在，则插入到 LC中。
11
2.1线性表及其逻辑结构例 2.2 求两个集合的并,即 C=A∪ B
void unionList(List LA,List LB,List &LC)
{/*将 LA和 LB中的元素归并到 LC中 */
int lena,lenb,i; ElemType e; InitList(LC);
for (i=1;i<=ListLength(LA);i++)
/*将 LA的所有元素插入到 Lc中 */
{ GetElem(LA,i,e);
ListInsert(LC,i,e);
}
lena=ListLength(LA); /*求线性表的长度 */
lenb=ListLength(LB);
12
2.1线性表及其逻辑结构例 2.2 求两个集合的并,即 C=A∪ B
for (i=1;i<=lenb;i++)
{ GetElem(LB,i,e);
/*取 LB中第 i个数据元素赋给 e*/
if (!LocateElem(LA,e))
ListInsert(LC,++lena,e);
/*LA中不存在和 e相同者,则插入到 LC中 */
}
}
13
2.2线性表的顺序存储结构
2.2.1 顺序存储结构把线性表中的所有元素按照其 逻辑顺序 依次存储到从计算机存储器中指定存储位臵开始的 一块连续的 存储空间中。
假设首元素 a1的存放地址为 LOC(a1)(称为 首地址 )，
线性表每个元素占用 k(k= sizeof(ElemType))个存储单元
，则第 i个元素 ai的存储位臵为,LOC(ai) = LOC(a1) +
K *（ i-1）
设有一维数组 M[10]，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素 M[0]的第一个字节的地址是 98，则 M[3]的第一个字节的地址是?
LOC( M[3] ) = 98 + 5 × (4-1) =113
14
2.2线性表的顺序存储结构
ADT List
{
数据对象：
D={ai| 1≤i≤n,n≥0,ai是 ElemType类型 }
数据关系：
R={<ai,ai+1>|ai,ai+1∈ D,i=1,…,n -1}
基本运算,
} 1、定义 ElemType类型
2、定义存储线性表的顺序存储结构体
…
1,用 C/C++实现线性表的顺序存储结构需注意两个主要步骤：
15
2.2线性表的顺序存储结构
#include "stdafx.h"
#include <malloc.h>
typedef char ElemType;
说明：为了使用系统的 malloc()
函数在内存为线性表分配存储空间，必须包含此头文件
#define MaxSize 50
//ElemType 定义为字符类型
//线性表数据元素的最大数目
typedef struct //存储线性表的结构体
{
ElemType data[MaxSize];//存储线性表数据元素
int length;//存储线性表的元素个数 —长度
} SqList;
说明：以上定义与申明必须位于主函数之前
(1)申明与定义
2,用 C/C++实现线性表的顺序存储结构
16
2.2线性表的顺序存储结构使用 C/C++提供的内存分配语句 malloc，
在计算机内存中分配一个大小、结构与 SqList
类型相同的存储空间，并将该存储空间的首地址赋给指针变量 L。
SqList * L
L=(SqList *)malloc(sizeof(SqList))
//定义一个指向 SqList类型的指针
typedef struct //存储线性表的结构体
{
ElemType data[MaxSize];//存储线性表数据元素
int length;//存储线性表的元素个数 —长度
} SqList;
(2)在计算机内存中为线性表分配存储空间
//分配内存空间
17
2.2线性表的顺序存储结构
L=(SqList *)malloc(sizeof(SqList))
void *malloc(unsigned size );
函数原形 函数功能,Allocates memory blocks
必须包含的头文件为 <malloc.h>或者 <stdlib.h>
18
2.2线性表的顺序存储结构
a1
a2
ai
an
…
…
…
…
0
1
i-1
n-1
MaxSize-1
数据元素下标
1、数组下标从 0开始，所以顺序表中第 i个元素的下标是 i-1
2,MaxSize是事先定义的一个常数，它是顺序表所能存储的最大元素个数
3、线性表满，表示表中有
MaxSize个元素，表的长度为 MaxSize;若表中有 n个元素 (n<MaxSize)，表的长度为 n;若表中无任何元素
(n=0)，称线性表为空表。aMaxSize
19
2.2线性表的顺序存储结构
a1
a2
ai
an
…
…
…
…
0
1
i-1
n-1
MaxSize-1
数据元素下标设 L是指向该顺序表的指针，如何访问顺序表中的第 i个元素？
e=L->data[i-1]
1、将表中第 i个元素的值赋给变量 e
L->data[i-1]=e
2、将变量 e的值赋给表中第 i个元素
20
2.2线性表的顺序存储结构
1、用一个含有 n个元素的数组建立顺序表
void CreateList(SqList *&L,ElemType a[],int n)
{
int i;
for(i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
2.2.2 顺序表的建立及基本运算的实现问：若 n>MaxSize,会出现什么问题？
如何改进？
21
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(1)初始化线性表 InitList(L):构造一个空的顺序表
void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList));//分配存储空间
L->length=0;//将顺序表长度设置为 0
}
该算法 (函数 )为线性表分配内存空间,并将线性表长度设置为 0(表示是一个空表 )。
2、顺序表基本运算算法
22
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(2)销毁线性表 DestroyList(L):释放顺序表占用的内存空间
void Destroy(SqList *&L)
{
free(L);
}
(3)判断线性表是否为空 ListEmpty(L):若 L为空返回真
(即 1),否则返回假 (即 0)
int ListEmpty(SqList *L)
{
return(L->length==0);
}
23
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(4)求线性表长度 ListLength(L):返回 L中元素个数
int ListLength(SqList *L)
{
return(L->length);
}
(5)输出线性表 DispList(L):顺序显示 L中各元素的值
void DispList(SqList *L)
{
int i;
if(ListEmpty(L)) return;//若线性表为空,返回
for(i=0;i<L->length;i++)
printf("%c",L->data[i]);
printf("\n");
}
24
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(6)求线性表中第 i个元素的值 GetElem(L,i,e):
int GetElem(SqList *L,int i,ElemType &e)
{
if(i<1 || i>L->length)
return 0; //位序参数不正确,函数返回假
e=L->data[i-1]; //取出表中第 i个元素的值
return 1; //运算成功,函数返回真 (1)
}
25
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(7)按元素查找 LocateElem(L,e):在 L中查找第一个值域与 e相等的元素的逻辑位序
int LocateElem (SqList *L,ElemType e)
{
int i=0;//从第 1个元素开始查找
while(i<L->length && L->data[i]!=e) i++;
if(i>=L->length)
return 0;//查不到,返回 0
else
return i+1;//返回查到元素的位序值
}
26
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e
插入前,L＝ (a1,…a i-1,ai,…,an)
插入后,L＝ (a1,…a i-1,e,ai,…,an)
① 进行合法性检查,1≤i ≤ n+1；
② 检查线性表是否已满；
③ 将第 n至第 i个元素逐一后移一个单位；
④ 在第 i个位臵处插入新元素；
⑤ 将表的长度加 1。
算法思想：
27
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e
‘q’
‘a’
‘b’
0
1
2
5
‘f’
3
4
6
7
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
设调用为 ListInsert(L,5,‘g’)
i--; i=4
‘d’
‘c’
线性表长度 L->length=？
‘g’
j=6=5=4
线性表长度 =6
插入前的线性表：
L=(‘q’,‘a’,‘f’,‘b’,‘d’,‘c’)
‘g’L->length++;
=7
28
2.2线性表的顺序存储结构插入算法 ListInsert (L,i,e)
int ListInsert( SqList *&L,int i,ElemType e)
{/*在顺序存储结构的线性表 L的第 i个 DE位臵插入 e*/
int j;
if(i<1||i>L->length+1) return 0; /*i的合法性判断 */
if (L->length==MaxSize ) return 0 ; /*表满 */
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
i--;
L->length++;
return 1;
}
29
2.2线性表的顺序存储结构
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e的算法时间复杂度分析,
设表长 L->length=n(本例 n=6)
若插入位置 i=1,移动次数为,n次若插入位置 i=2,移动次数为,n-1次算法的时间复杂度 T(n)=O(n)
若插入位置 i=3,移动次数为,n-2次…
若插入位置 i=n+1,移动次数为,0次若插入位置为 i(i∈ {1,2,…,n+1})
移动次数为,n-i+1次
=n-1+1
=n-2+1
=n-3+1
=n-(n-1)+1
按最坏情况计 (i=1)
分析方法 1(考虑最坏情况 ):
‘q’
‘a’
‘b’
0
1
2
5
‘f’
3
4
6
7
‘d’
‘c’
30
2.2线性表的顺序存储结构
(8)插入元素 ListInsert(L,i,e):在 L中第 i个元素位置上插入新元素 e的算法时间复杂度分析,
设表长 L->length=n(本例 n=6)
T(n)=
线性表有 n+1个位置可插入一次新元素分析方法 2(计算每个位置上可能出现插入的平均次数 )
则在任一位置 i∈ {1,…,n+1} 上插入一次的概率是,1/(n+1)
则在每个位置上都可能出现插入的移动次数的期望值
(即以概率为权的加权平均值）为,
1
1
)1(
1
1n
i
in
n
=O(n)
根据方法 1的分析,在 i上插入,需移动的次数为,n-i+1次
31
2.2线性表的顺序存储结构
2.2.2 顺序表的建立及基本运算的实现
(9)删除数据元素 ListDelete(L,i,e):删除线性表 L的第
i个元素,并用变量 e返回该元素的值
删除前,L＝ (a1,…a i-1,ai,a i+1 …,an)
删除后,L＝ (a1,…a i-1,ai+1,…,an)
① 进行合法性检查,i是否满足 1≤i ≤ n；
② 判断线性表是否已空,L－ >Length是否为 0；
③ 将第 i个位臵的 DE赋给 e；
④ 将第 i+1至第 n个元素逐一向前移一个单位；
⑤ 将表的长度减 1。
算法思想：
32
2.2线性表的顺序存储结构
(9)删除数据元素 ListDelete(L,i,e):删除线性表 L的第
‘q’
‘a’
0
1
2
5
‘f’
3
4
6
7
‘d’
‘c’
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;//
设调用为 ListDelete(L,4,e)
‘b’
i=3是第 4个元素的下标
e=‘b’用于返回该元素值
j=3,表长 =6,
L->data[3]=L->data[4]
=4 表长
4 5
j=5,表长 =6,
删除了一个元素，线性表长度减 1
i个元素,并用变量 e返回该元素的值 表长度 =6=5
‘q’
‘a’
‘f’
‘d’
‘c’
‘b’
33
2.2线性表的顺序存储结构删除算法 ListDelete (L,i,e)
int ListDelete(Sqlist *&L,int i,elemtype &e)
{/*在顺序存储结构的线性表 L中删除第 i个 DE，并用 e返回 */
int j;
if(i<1||i>L->length) return 0;/*i值有错或者表已空 */
e=L->data[i-1]; /*将被删除元素赋给 e*/
for(j=i;j<=L->length;j++) /*将第 i+1至 n个元素前移 */
L->data[j-1]=L->data[j];
L->length--; /*表长减 1*/
return 1;
}
34
2.2线性表的顺序存储结构删除算法 ListInsert (L,i,e)
执行次数与 删除位臵 i及 n有关：
问题规模是表的长度 n
最好情况,
最坏情况,
i=n时，移动次数为 0
i=1时，移动次数为 n-1，时间复杂度为 O（ n）
n-i删除第 i个元素时，须执行的次数为：
时间复杂度分析因此,T（ n）＝ O（ n）
等概率的情况下，移动的平均次数为：
2/)1()(
1
ninPEis n
i
i
因此,T（ n）＝ O（ n）
35
2.2线性表的顺序存储结构线性表顺序存储结构的特点
1,逻辑上相邻的元素，其物理位臵也相邻；
2,可随机存取表中任一元素；
3,必须按最大可能长度预分配存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构；
4,插入删除时，需移动大量元素，平均移动元素为 n/2。
36
2.2线性表的顺序存储结构例 2.4 有一个顺序表 L，假设元素类型 ElemType为整型，并且所有元素均不相等。设计一个算法，以第一个元素为分界线，将所有小于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。
算法思想：
(1)设臵变量 i，初值为 0,j初值为 L->Length-1;
基准 pivot为 L->data[0].
(2)当 i!=j时：
从右向左扫描,j>i时，将 data[j]与 pivot比较，若
data[j]>pivot,j--;否则，将 data[j]赋给 data[i]。
从左向右扫描,i<j时，将 data[i]与 pivot比较，若
data[i]<pivot,i++;否则，将 data[i]赋给 data[j]。
(3)当 i=j时：将 pivot赋给 data[i].
37
3 5 6 1 4 2 7 9 8 0
pivot=L->data[0]=3
0 5
61 3
i ji i i jjjjjj
2
int i=0,j=L->length-1;
ElemType pivot=L->data[0];
while(i!=j)
{
while(j>i&&L->data[j]>pivot)
j--;
L->data[i]=L->data[j];
while(i<j&&L->data[i]<pivot)
i++;
L->data[j]=L->data[i];
}
L->data[i]=pivot;
38
2.2线性表的顺序存储结构例 2.11 在顺序存储结构上归并两个有序的线性表
LA和 LB为一个新的有序线性表 LC。
① 初始化,臵 LC为空表,设臵变量 i,j初值为 0,分别指向
LA和 LB的第一个 DE,k表示 LC的长度,初值为 0。
② 当 i<=Length(LA) and j<=Length(LB),
判断,若 i所指的元素 <j所指的元素,则将 i所指的元素插入在 LC的 k+1(表尾 )前,并且 i,k的值分别加 1;
否则,将 j所指的元素插入在 LC的 k+1(表尾 )前,并且 j,
k的值分别加 1。
③ 重复第二步直到某个表的元素插入完毕。
④ 将未插入完的表中余下的元素，依次插入在 LC后。
算法思想：
39
2.2线性表的顺序存储结构例：顺序结构上的归并有序表算法
Void UnionList( Sqlist*LA,Sqlist*LB,Sqlist*&LC)
{ int i=0,j=0,k=0; /*i,j,k分别作为 LA,LB,LC的下标 */
LC=(SqList *)malloc (sizeof (Sqlist));
LC->Length=0;
while (i< LA->Length && j< LB->Length){
if (LA->data[i]<LB->data[j])
{LC->data[k]= LA->data[i]; i++; k++;}
else
{LC->data[k]= LB->data[j]; k++; j++;}
}
while (i< LA->Length) /*LA未完，将其余元素插入 LC中 */
while ( j< LB->Length) /*LB未完，将其余元素插入 LC中 */
{LC->data[k]= LA->data[i]; i++; k++;}
LC->Length=k;
{LC->data[k]= LB->data[j]; k++; j++;}
}
时间复杂度：
T(n)=O(ListLength(LA)+ListLength(LB))
40
2.3 线性表的链式存储结构
2.3.1 线性表的链式存储结构 —链表
2.3.2 单链表基本运算的实现
2.3.3 双链表
2.3.4 循环链表
2.3.5 静态链表
41
2.3.1 线性表的链式存储结构 —链表
1、线性表的顺序存储结构存在的缺陷由于顺序表所能存储的最大元素个数 (MaxSize)事先由设计人员估计给定，
在程序运行过程中是个固定值。
(1)若事先估计不足，会造成数组下标越界
(2)若估计,过量,,会造成存储空间极大浪费
42
2.3.1 线性表的链式存储结构 —链表
2、链表由若干个含有 数据域 和 指针域 存储单元组成，这些存储单元称为结点，存储单元的地址常常是不连续的，称这样的存储结构为链表。
data
数据域
next
指针域 data数据域 next指针域结点 a 结点 b
‘h’ ‘g’结点 b地址
43
2.3.1 线性表的链式存储结构 —链表
3、链式存储结构的特点
(1)用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
(2)存储单元称为结点，每个结点由
2种类型的存储区域组成,
a.存储数据的区域
b.存储地址的区域称为数据域称为指针域
(3)链表的结点是在程序运行过程中动态建立的，与顺序存储结构不同，不必事先给定链表结点最大数目。
44
2.3.1 线性表的链式存储结构 —链表
4、单链表每个结点都有 1个数据域和一个指针域的链表称为单链表。
…head a1 a2 an ∧
NULL
开始结点 终端结点头结点头指针说明,链表的第 1个结点称为头结点,其数据域不存储数据,其指针域存储的是开始结点的首地址。若头结点指针域为空，表明链表为空表。
45
2.3.1 线性表的链式存储结构 —链表
5、双链表每个结点都有 1个数据域和 2个指针域的链表称为双链表。
a1 a2 … an ∧dhead
开始结点 终端结点头结点头指针
46
2.3.1 线性表的链式存储结构 —链表
typedef struct LNode//定义单链表结点的结构体
{
ElemType data;//数据域
struct LNode *next;//指针域,存放后继结点地址
}LinkList;
6、用 C/C++实现链式存储结构 (单链表 )
#include "stdafx.h"
#include "malloc.h"//为了使用内存分配语句 malloc
typedef int ElemType ;
(1)申明与定义
47
N个结点通过指针域组成的表，称为 线性链表 （单链表）
线性链表最后一个结点的指针域为“空” (NULL或 ∧ )；
用一个头指针指示链表中的第一个结点的存储位臵；
链表 L=(a1,a2,….a n)逻辑表示为：
头指针head a
1 a2 an ^…...
开始结点 空表,head=NULL
2.3.1 线性表的链式存储结构 —链表空表时：判空条件是？
头指针
…...head
头结点
a2 an ∧a1
开始结点 终端结点带头结点链表的引入是为了便于插入和删除算法的实现
，使算法的实现和判空等其他的处理达到一致。
Head－ >next=Null
48
2.3.1 线性表的链式存储结构 —链表
LinkList *head,*p;定义指向单链表结点的指针变量
head=(LinkList *)malloc(sizeof(LinkList));
/*在内存空间建立一个结点，结点首地址返回给指针变量 head */
head->next=NULL; //指针域设臵为空,表明该结
//点无后继结点,
head
(2)建立单链表
p=(LinkList *)malloc(sizeof(LinkList));
∧ p
head->next=p; p->data=‘a’;
‘a’
p->next=NULL;
∧
49
2.3.2 单链表基本运算的实现
1.插入结点运算结点 a 结点 b
‘h’ ‘i’
data nextdata next
……
—在结点 b前插入新结点 x
结点 x
‘k’
data next
S
P
S->next=P->next;
P->next=S;
结点 a 结点 b
‘h’ ‘i’
data nextdata next
……
结点 x
‘k’
data next
S
P
50
2.3.2 单链表基本运算的实现
2.删除结点运算结点 a 结点 c
‘a’ ‘c’
data nextdata next
……
结点 b
‘b’
data nextP
p->next=p->next->next;
—删除结点 b
(1)最简单的情形
51
2.3.2 单链表基本运算的实现
2.删除结点运算结点 a 结点 c
‘a’ ‘c’
data nextdata next
……
结点 b
‘b’
data nextP
p->next=p->next->next;
free(s);
—删除结点 b
S
(1)最简单的情形
p->next=s->next;
(2)使用指针 S指向结点 b
s=p->next;
52
2.3.2 单链表基本运算的实现
3、建立单链表
(1)头插法建表,
从一个空链表开始，依次从数组 a中读取一个元素 ai(i∈ {0,…,n -1}),使用内存分配语句生成一个新结点，将 ai的值存放到新结点数据域中，然后将新结点插入到当前链表表头的后继结点上 (即新结点总是插入到表中开始结点的位臵上 —头插法 ),直到数组 a中所有元素读完并全部插入到链表中为止。
53
LinkList *s; int i;
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL:
for(i=0;i<n;i++)
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=a[i];
s->next=L->next;
L->next=s;
}
‘a’
‘b’
‘c’
‘d’
0
1
2
3
数组 a,n=4
i
L ∧
s
‘a’ ∧
s
‘b’
‘a’ ∧b’
c’
c’ b’ ‘a’∧
d’
‘a’∧b’c’d’
结束头插法建立单链表的过程
4
54
‘a’
‘b’
‘c’
‘d’
0
1
2
3
数组 a,n=4
L ‘a’∧‘b’‘c’‘d’
由此可见，头插法生成的链表中结点的次序与原数组元素的顺序相反头结点头插法建立单链表的结果
55
(1)头插法建表的完整算法,
void CreateListF(LinkList *&L,ElemType a[],int n)
{ /*将数组 a中的 n个元素用头插法建立单链表 L*/
LinkList *s; int i;
L=(LinkList *)malloc(sizeof(LinkList)
/*创建头结点 */
L->next=NULL;
for (i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList))
/*创建新结点 */
s->data=a[i]; s->next=L->next;L->next=s;
} /*将 *s插在原开始结点之前,头结点之后 */
}
56
2.3.2 单链表基本运算的实现
3、建立单链表
(2)尾插法,
从一个空链表开始，依次从有 n个元素的数组 a中读取一个元素 ai(i∈ {0,…,n -
1}),使用内存分配语句生成一个新结点，
将 ai的值存放到新结点数据域中，然后将新结点插入到当前链表表尾上 (即总是表尾的终端结点位臵上插入新结点 —尾插法 ),直到数组 a中所有元素读完并插入到链表中为止。
57
LinkList *s,*r; int i;
L=(LinkList*)malloc(sizeof(LinkList));
r=L;
for(i=0;i<n;i++)
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=a[i]; r->next=s; r=s;
}
r->next=NULL:
‘a’
‘b’
‘c’
‘d’
0
1
2
3
数组 a,n=4
i
L
s
‘a’ ‘c’‘b’ ‘d’∧
尾插法建立单链表的过程
s s s
r r r r r
4
58
(2)尾插法建表的完整算法,
void CreateListR(LinkList *&L,ElemType a[],int n)
{ /*将数组 a中的 n个元素用尾插法建立单链表 L*/
LinkList *s,*r; int i;
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL; /*创建头结点 */
r=L; /*r始终指向终端结点,开始时指向头结点 */
for (i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点 */
s->data=a[i];r->next=s; /*将 *s插入 *r之后 */
r=s;
}
r->next=NULL;/*终端结点 next域臵为 NULL*/
}
59
(1)初始化线性表
4.采用单链表实现线性表基本运算的算法建立一个空链表 (即只有一个头表结点的链表 )
L ∧
头结点
void InitList(LinkList *&L)
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
60
(2)销毁线性表
4.采用单链表实现线性表基本运算的算法
void DestroyList(LinkList *&L)
{
LinkList *p=L,*q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
L ‘a’ ‘c’‘b’ ‘d’∧
头结点 q
p
∧
结束
61
4.采用单链表实现线性表基本运算的算法
(3)判断线性表是否为空
int ListEmpty(LinkList *L)
{
return(L->next==NULL);
}
62
4.采用单链表实现线性表基本运算的算法
(4)求线性表的长度 ListLength(L)
a1 a2 an-1 ^an…
L p
i=0
p
i++
int ListLength(LinkList *L)
{ /*求单链表 L的长度 */
LinkList *p=L; int i=0;
while (p->next!=NULL)
{ i++; p=p->next;}
return(i);
}
int ListLength(LinkList *L)
{ /*求单链表 L的长度 */
LinkList *p=L->next;
int i=0;
while (p!=NULL)
{ i++; p=p->next;}
return(i);
}
63
(5) 输出线性表 DispList(L)
void DispList(LinkList *L)
{ /*输出单链表 L中的所有 DE*/
LinkList *p=L->next;
while (p!=NULL)
{ printf("%c",p->data);
p=p->next;
}
printf("\n");
}
a1 a2 an-1 ^an…L
4.采用单链表实现线性表基本运算的算法
64
int GetElem(LinkList *L,int i,ElemType &e)
{ /*取单链表 L中的第 i个 DE,并用 e返回 */
[臵初值部分 ]
while (循环控制条件 )
[循环体 ]
if (出循环后判断条件 ) return 0;
else
{ e=p->data;
return 1;
}
}
(6)取元素函数 GetElem (L,i,e)
4.采用单链表实现线性表基本运算的算法
65
int GetElem(LinkList *L,int i,ElemType &e)
{ int j=1; LinkList *p=L->next;
/*移动指针 p，计数变量 j*/
while (j<i && p!=NULL)
{ j++;
p=p->next; }
if (p==NULL) return 0;
else
{ e=p->data;
return 1;}
}
问题：如何臵初值？怎样对 i的合法性进行检查?如何确定出循环的判定条件？
if (j>i) return 0;
{ e=p->data;
return 1;
}
else或
4.采用单链表实现线性表基本运算的算法
66
循环条件分析：
int j=1; LinkList *p=L->next; while (j<i && p!=null)
条件 1控制取第 i个，防止了 i<1,条件 2防止 i>表长。
两个条件有 6种组合：
1,j<i && p=null 空表且 i>1或 i>表长 +1,异常,return 0；
2,j=i && p=null 空表且 i=1或 i=表长 +1,异常,return 0；
3,j>i && p=null 空表且 i<1,异常,return 0；
4,j<i && p!=null 继续循环；
5,j=i && p!=null 确定第 i个结点，正常出循环；
6,j>i && p!=null i<1，异常出循环,return 0；
4.采用单链表实现线性表基本运算的算法
67
int GetElem(LinkList *L,int i,ElemType &e)
{ int j=1; LinkList *p=L->next;
while (j<i && p!=NULL)
{
j++; p=p->next; }
if (p==NULL||j>i) return 0;
else { e=p->data; return 1;}
}
//条件 1控制取第 i个,防止了 i<1,条件 2防止 i>表长
{只用一个条件是不充分的 }
{移动指针 p,计数变量 j}
i的 合法性判断 已经蕴涵在 while和 if条件中；
算法时间复杂度分析,while最多执行 i-1次，最坏情况是取第 n个结点，需执行 n-1次，因此：
T(n)=O(n)
(6)取元素函数 GetElem (L,i,e)
4.采用单链表实现线性表基本运算的算法
68
4.采用单链表实现线性表基本运算的算法
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p=L->next;
int n=1;
while (p!=NULL&&p->data!=e)
{
p=p->next;//指向下一个结点
n++;//结点位序号加 1
}
if(p==NULL)
return(0);
else
return(n);//找到，函数返回位序号
}
(7)按元素值查找 LocateElem (L,i,e)
69
定位：得到指向第 i个 DE的直接前驱的指针 p；
插入运算可由定位、生成新结点和修改指针三步来完成,
生成新结点：利用 malloc函数生成一个新的结点 s；
修改指针,s->next=p->next;
p->next=s;
顺序不能变注意,凡是对 next域进行修改时，一定要检查原来的 next域指针所指的结点是否已经有其他的指针指向该结点，否则就会出现断链的可能。
(8)插入运算 ListInsert (L,i,e)
4.采用单链表实现线性表基本运算的算法
70
(8)插入元素数据 ListInsert(L,i,e)
int j=0;LinkList *p=L,*s;
while(j<i-1 && p!=NULL)
{
j++;p=p->next;
}
if(p==NULL||j>i-1)
return 0;
else
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
} L ‘a’
‘c’
‘b’ ‘d’∧
p
s
设调用语句为,ListInsert(L,3,‘c’)
j=0i=3 12
算法思路,先在单链表中寻找第 i-1个结点，若找到，则将新结点插入到第 i-1
个结点之后 (即第 i个结点之前 )。
71
int ListInsert(LinkList *&L,int i,ElemType e)
{ /*在单链表 L的第 i个位臵插入元素 e*/
int j=0; LinkList *p=L,*s;
while (j<i-1 && p!=NULL)
/*查找第 i-1个结点 */
{ j++; p=p->next;}
if (p==NULL||j>i-1) return 0;
/*未找到位序为 i-1的结点 */
else /*找到位序为 i-1的结点 *p*/
{ s=(LinkList *)malloc(sizeof(LinkList));
/*创建新结点 *s*/
s->data=e;
s->next=p->next; /*将 *s插入到 *p之后 */
p->next=s;
return 1;
}
}?算法时间复杂度分析,T(n)=O(n)
4.采用单链表实现线性表基本运算的算法
72
与 GetElem(L,i,e)函数的区别：
初值保证能在第一个 DE之前插入,1≤i ≤表长 +1
循环定位条件,定位 在 i的直接前驱 i-1.?
循环条件分析,?
第一次循环 p!=null,j有三种可能：
1,j<i-1 继续循环；
2,j=i-1 此时 i=1,表示在第一个元素前作插入操作；
3,j>i-1 此时 i<1不合法；
第二次循环后 p可能为 null,但 j>i-1不可能，出现的各种可能情况如下：
1,p!=null &&j<i-1 继续循环；
2,p!=null && j=i-1 已经定位，出循环；
3,p=null && j<=i-1 i不合法 (i>=表长 +2),出循环
4.采用单链表实现线性表基本运算的算法
73
a…
p
b …
(a) 删除前
a…
p
b …
(b)p->next=p->next->next
a…
p
…
(c) 删除后删除运算可由定位
、修改指针和释放结点来完成
定位：得到指向 b的直接前驱 a的指针 p；
修改指针,q=p->next;
p->next= p->next->next;
释放结点,free(q);
（ 9）删除运算 ListDelete (L,i,e)
4.采用单链表实现线性表基本运算的算法
74
int ListDelete(LinkList *&L,int i,ElemType &e)
{ /*删除单链表 L中的第 i个 DE，并用 e返回 */
int j=0; LinkList *p=L,*q;
while (j<i-1 && p->next!=NULL) /*查找第 i-1个结点 */
{ j++; p=p->next;}
if (p==NULL||j>i-1) return 0;
/*未找到位序为 i-1的结点 */
else /*找到位序为 i-1的结点 *p*/
{ q=p->next; /*q指向要删除的结点 */
e=q->data;
p->next=q->next; /*从单链表中删除 *q结点 */
free(q); /*释放 *q结点 */
return 1;
}
}
4.采用单链表实现线性表基本运算的算法
75
删除算法讨论：
删除范围为 [1,表长 ]，不能删除头结点；
出循环的 5种可能情况：
1,p->next=null &&j<i-1 空表或 i>表长
2,P->next=null && j=i-1 空表且 i=1,或 i＝表长 +1
3,p-next=null && j>i-1 空表且 i<1
4,p->next!=null &&j=i-1 非空表且已定位
5,P->next!=null && j>i-1 非 空表且 i<1
时间复杂度分析,while至多执行 i-1次，当
i=n时为最坏情形，故,T(n)=O(n)
4.采用单链表实现线性表基本运算的算法
76
5.线性表链式存储结构的特点
1,逻辑上相邻的元素，其物理位臵不一定相邻；
元素之间的邻接关系由指针域指示。
2,链表是非随机存取结构；对链表的存取必须从头指针开始。
3,链表是一种动态存储结构；链表的结点可调用 malloc()申请和 free()释放。
4,插入删除运算非常方便；只需修改相应的指针值。
77
例 2.5 有一个带头结点的单链表 L={a1,b1,a2,b2,…a n,bn},
设计一个算法将其拆分成两个带头结点的单链表 L1和
L2,L1={a1,,a2,…a n},L2={bn,bn-1,…b 1}。要求 L1使用 L的头结点。
① 初始化,p指向 L的第一个 DE结点,臵 L2为空表,p2指向
L2,L1,r1指向 L的头结点,设臵变量 i初值为 0。
② 当 p!=NULL时,
判断,if(i%2==0) 用头插法将 *p插入到 L2当中，否则用尾插法将 *p插入到 L1当中。
③ 将利用尾插法建立的最后一个数据结点的 next域臵为
NULL。
算法思想：
书中对于该例题给出的算法，本人认为可移植性差或者说健壮性较差，因为只要给出的单链表 L的 DE不是偶数，该算法就不能执行。
78
void split(LinkList *&L,LinkList *&L1,LinkList *&L2)
{ int i=0;
LinkList *r1,*p2,*s,*p=L->next;
r1=L1=L;
L2=(LinkList*)malloc(sizeof(LinkList));
L2->next=NULL;p2=L2;
while (p!=NULL)
{ i++;
if (i%2==0)
{ s=p->next; p->next=p2->next;
p2->next=p; p=s;
}
else { r1->next=p; r1=p; p=p->next;}
} r1->next=NULL;
}
79
[例 2.6]有一个带头结点的单链表 L,设计一个算法使其元素递增有序。
L 9 76 1 ∧
L 1 76 9 ∧
80
void Sort(LinkList *&L)
{
LinkList *p=L->next,*q,*r;
if(p!=NULL)
{
r=p->next; p->next=NULL;
p=r;
while(p!=NULL)
{ r=p->next; q=L;
while(q->next!=NULL&&q->next->data<p->data)
q=q->next;
p->next=q->next; q->next=p; p=r;
}
}
}
L 9 106 1 ∧
p
r
∧
q NULL
NULL
结束
∧
81
L 1 6 9 10 ∧
L成为一个元素递增有序的单链表
L 9 106 1
p
r
q NULL
NULL
∧
82
例：在单链表上实现归并两个有序表，要求产生的结果有序表仍旧用原有序表的结点空间。
void unionlist(LinkList *&LA,LinkList *&LB,LinkList *&LC)
{ /*已知单链线性表 LA和 LB的元素按值非递减排列，归并 LA
和 LB得到新的单链线性表 LC,LC的元素也按值非递减排列 */
/*用 LA的头结点作为 LC的头结点 */
/*插入剩余段 */
/*释放 LB的头结点 */
Linklist *pa,*pb,*pc;
pa= LA->next; pb=LB->next;
LC=pc=LA;
while(pa!=null&&pb!=null)
{ if(pa->data<pb->data) {pc->next=pa;pc=pa; pa=pa->next;}
else {pc->next=pb; pc=pb;pb=pb->next;}}
if(pa!=null) pc->next=pa;
esle pc->next=pb;
free(LB)}
83
1 3 4 ^6LA
2 5 7 ^8LB
pa
pb
pc
LC
pc pa
pc pb
pc papapc pa
pc pbpc
pc
1 2 3 4LC
5 6 7 ^8
84
单链表中的缺陷在单链表中,由于每个结点只包含有一个指向后继结点的指针,所以当访问过一个结点后,只能接着访问它的后继结点,而无法访问它的前驱结点 。
85
2.3.3 双链表
…L a1 a2 an ∧
数据域指针域 指针域
prior data next
(1)双链表的结点结构
(2)双链表存储前驱结点首地址存储后继结点首地址
86
2.3.3 双链表
typedef struct LNode//
{
ElemType data;//数据域
struct LNode *next;//后继指针域
struct LNode *prior;//前驱指针域
}DLinkList;
(3)定义双链表结点类型说明,双单链表只比单链表多了个前驱指针，
因而单链表的所有基本运算算法都适合于双链表，但有些算法 (如插入和删除结点 )要相应增加对前驱指针的处理语句。
87
2.3.3 双链表
(4)双链表的插入 —在指针 p所指的结点 A
后插入一个新结点 C
……
s
p
操作过程操作语句
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
……
p s
prior next
data
prior next
data
prior next
data
A B
C
A BC
88
2.3.3 双链表
(5)双链表的删除 —删除指针 p所指结点的后继结点 S
……
p s
p->next=s->next; 或 p->next=p->next->next;
s->next->prior=p;
free(s);
89
2.3.3 双链表
(6)双链表基本运算的实现双链表的基本运算算法,与单链表相似，不再在课堂上详细介绍,留给同学们自学，双链表的所有基本运算算法都要掌握！自学时要注意与单链表的相应算法进行比较。
90
2.3.3 双链表
[例 2.7](p48)
L 1 5 9 ∧7
L 9 7 1 ∧5
[例 2.8](p49)
L 5 7 1 ∧9
L 1 5 9 ∧7
91
1,循环单链表
2.3.4 循环链表
L ‘a’ ‘c’‘b’ ‘d’∧
2,循环双链表
…L a1 a2 an ∧
p若 p->next==L,则结点 p是尾结点。
“头尾相连,的链表
92
[例 2.9](p50)有一个带头结点的循环单链表 L，
设计一个算法统计其 data域值为 x的结点个数。
同学们自己分析课本给出的算法
2.3.4 循环链表
[例 2.10](p50)同学们自己分析课本给出的算法
93
a.静态链表的结构体申明
2.3.5 静态链表
#define MaxSize 100 //能存储的最大元素个数
typedef char ElemType[10];
typedef struct
{
ElemType data;//数据域,最多放 10个字符
int next;//游标域,存放后继结点的下标
} StaticList[MaxSize];
StaticList sL;
用一维数组来描述的链式线性表
94
b.静态链表的存储结构
2.3.5 静态链表数组下标 data next
数据序号
0 3 表头
1 张斌 4 2
2 刘丽 5 4
3 李英 1 1
4 陈华 2 3
5 王奇 6 5
6 董强 7 6
7 王萍 0 7
8 -1
9 -1
3 李英 1 张斌 4 陈华 2 刘丽 5 王奇 6 董强 7 王萍 0
下标,0 3 1 4 2 5 6 7
1 2 3 4 5 6 7表头
typedef char ElemType[8];
#define MaxSize 10
…
typedef struct
{
ElemType data;
int next;
}StaticList[MaxSize];
…
StaticList sL;
sL[3].data=“李英” sL[3].next=1
静态链表
sL
空结点
95
数组下标 data next
数据序号
0 3 表头
1 张斌 4 2
2 刘丽 5 4
3 李英 1 1
4 陈华 2 3
5 王奇 6 5
6 董强 7 6
7 王萍 0 7
8 -1
9 -1
删除陈华数组下标 data next
数据序号
0 3 表头
1 张斌 2 2
2 刘丽 5 3
3 李英 1 1
4 陈华 -1
5 王奇 6 4
6 董强 7 5
7 王萍 0 6
8 -1
5 -1
sL[1].next=sL[4].next;
3 李英 1 张斌 4 陈华 2 刘丽 5 王奇 6 董强 7 王萍 0
下标 0 3 1 4 2 5 6 7
1 2 3 4 5 6 7表头
sL[4].next=-1;
李英 张斌 2 刘丽 5 王奇 6 董强 7 王萍 0
下标 2 5 6 7
1 2 6表头
96
静态链表特点
1、链表的最大长度为表中可容纳的数据结点的最大个数,是一固定值，在程序执行期间不能改变；
2、当链表的数据结点数等于最大长度时，称链表已满,此时不能再插入新的数据结点 (上溢）；
3、链表中每个数据结点的游标域的值是该结点的后继结点的一维下标，处于表尾的数据结点的游标域的值总是设为 0（表示无后继）；
4、若头结点的游标域为 0，表明为空表；
97
4、表中被删除的数据结点的游标域的值总是设为 -1,表明为空结点；
5、与动态链表相似,静态链表的头结点的数据域不用于存储数据，头结点的后继是表中第 1个数据结点，第 1个数据结点的后继为表中的第 2个数据结点，以此类推,第 n-1个数据结点的后继为表中的第 n个数据结点,n称为数据结点序号，它并不一定等于数据结点的一维下标。
静态链表特点
98
小 结本章作业：练习题 2.1,2.2,2.3
(2)深入掌握线性表的两种存储方法
a.顺序表
b.链表动态链表静态链表单链表双链表循环单链表非循环单链表循环双链表非循环双链表
(3)重点掌握顺序表和链表的各种基本运算算法
(1)理解线性表的逻辑结构特点
99
第二章 习题
1.线性表的逻辑顺序和物理顺序总是一致的，这种说法 ——.
A 正确 B 不正确
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ——.
A 必须连续 B 部分地址必须连续
C 一定是不连续的 D 连续不连续都可以
2.不带头结点的单链表 head为空的判定条件是 ——.
A head=Null B head->next=Null
C head->next=head D head!=Null
100
第二章 习题
4,非空循环单链表 head尾结点 *P满足 ——.
A p->next=Null B p=Null
C p->next=head D p=head
5,在一个单链表中，已知 *q结点是 *P结点的前驱结点，若 *q结点和 *P结点之间插入 *s结点，则执行 ——.
A s->next=p->next; p->next=s;
B p->next=s->next; s->next=p;
C q->next=s; s->next=p;
D p->next=s; s->next=q;
