Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 1页第 2章 线性表主要内容：
1．线形表的类型定义
2,线形表的顺序表示和实现
3,线形表的链式表示和实现
4,有序表
5．顺序表和链表的综合比较
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 2页线性表 是一种最简单的 线性结构
线性结构的基本特征为,
线性结构是一个数据元素的 有序（次序）集
1．集合中必存在唯一的一个,第一元素,；
2．集合中必存在唯一的一个,最后元素,；
3．除最后元素在外，均有 唯一的后继 ；
4．除第一元素之外，均有 唯一的前驱 。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 3页
2.1 线形表的类型定义
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 4页抽象数据类型线性表的定义
ADT List {
数据对象：
D＝ { ai | ai ∈ElemSet,i=1,2,...,n,n≥0 }
{称 n 为线性表的表长 ; 称 n=0 时的线性表为空表。 }
数据关系：
R1＝ { <ai-1,ai >|ai-1,ai∈D,i=2,...,n }
{设线性表为 (a1,a2,.,,,ai,.,,,an),称
i 为 ai 在线性表中的位序。 }
基本操作：
结构初始化操作结构销毁操作引用型操作加工型操作
} ADT List
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 5页初始化操作
InitList( &L )
操作结果,构造一个空的线性表 L。
结构销毁操作
DestroyList( &L )
初始条件,线性表 L 已存在。
操作结果,销毁线性表 L。
引用型操作
ListEmpty( L )
初始条件,线性表 L已存在。
操作结果,若 L为空表，则返回 TRUE，
否则 FALSE。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 6页
ListLength( L )
初始条件,线性表 L已存在。
操作结果,返回 L中元素个数。
PriorElem( L,cur_e,&pre_e )
初始条件,线性表 L已存在。
操作结果,若 cur_e是 L的元素，但不是第一个，则用 pre_e 返回它的前驱，否则操作失败,pre_e无定义。
NextElem( L,cur_e,&next_e )
初始条件,线性表 L已存在。
操作结果,若 cur_e是 L的元素，但不是最后一个，则用 next_e返回它的后继，否则操作失败,next_e无定义。
引用型操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 7页
GetElem( L,cur_e,&next_e )
初始条件,线性表 L已存在,1≤i≤LengthList(L)
操作结果,用 e返回 L中第 i个元素的值。
LocateElem( L,e,compare( ) )
初始条件,线性表 L已存在,compare( )是元素判定函数。
操作结果,返回 L中第 1个与 e满足关系 compare( )的元素的位序。
若这样的元素不存在，则返回值为 0。
ListTraverse(L,visit( ))
初始条件,线性表 L已存在。
操作结果,依次对 L的每个元素调用函数 visit( )。一旦
visit( )失败，则操作失败。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 8页
ClearList( &L )
初始条件,线性表 L已存在。
操作结果,将 L重置为空表。
PutElem( L,i,&e )
初始条件,线性表 L已存在,1≤i≤LengthList(L)
操作结果,L中第 i个元素赋值同 e的值。
ListInsert( &L,i,e )
初始条件,线性表 L已存在,1≤i≤LengthList(L)+1
操作结果,在 L的第 i个元素之前插入新的元素 e,L的长度增 1。
ListDelete(&L,i,&e)
初始条件,线性表 L已存在且非空,1≤i≤LengthList(L)
操作结果,删除 L的第 i个元素，并用 e返回其值,L的长度减 1。
加工型操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 9页例 2-1 假设有两个集合 A和 B分别用两个线性表 LA和 LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合
A＝ A∪B 。
上述问题可演绎为，要求对线性表作如下操作：扩大线性表 LA，将存在于线性表 LB中而不存在于线性表 LA中的数据元素插入到线性表
LA中去。
1．从线性表 LB中依次取得每个数据元素 ; GetElem(LB,i,e)
2．依值在线性表 LA中进行查访 ; LocateElem(LA,e,equal( ))
3．若不存在，则插入之。 ListInsert(LA,n+1,e)
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 10页算法 2.1
void union(List &La,List Lb) {
// 将所有在线性表 Lb中但不在 La中的数据元素插入到 La中
La_len = ListLength(La);
Lb_len =ListLength(Lb); // 求线性表的长度
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb,i,e);
// 取 Lb中第 i个数据元素赋给 e
if(!LocateElem(La,e,equal( ))
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
}
} // union
1 3 4 8 2 4 5
La Lb
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 11页例 2-2
已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B中所有值各不相同的数据元素。
仍选用线性表表示集合
从集合 B 取出物件放入集合 A要求集合 A中同样物件不能有两件以上
因此，算法的策略应该和例 2-1相同集合 B集合 A
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 12页算法 2.2
void purge(List &La,List &Lb) {
// 构造线性表 La，使其只包含 Lb 中所有值不相同的数据元素，
// 操作完成后，线性表 Lb 不再存在
InitList(La); La_len=0; // 创建一个空的线性表 La
while (!ListEmpty(Lb)) { // Lb 表的元素尚未处理完
ListDelete( Lb,1,e );
// 从 Lb 中删除第一个数据元素赋给 e
if (!LocateElem( La,e) )
ListInsert( La,++La_len,e );
// 若 La 中不存在值和 e 相等的数据元素，则插入之
} // while
DestroyList(Lb); // 销毁线性表 Lb
} // purge
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 13页
2.2 线性表的顺序表示和实现
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 14页
2.2.1 顺序表 —线性表的顺序存储表示
线性表的顺序存储,用一组地址连续的存储单元依次存放线性表中的数据元素。
顺序线性表称为 顺序表。
在程序设计语言中，采用一维数组来实现。
需要考虑数组容量的动态扩充；
a1 a2 … ai-1 ai … an
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 15页顺序表的定义
//----- 线性表的动态分配顺序存储结构 -----
#define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct {
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的数组容量 (以 ElemType为单位 )
int incrementsize; //约定的增补空间量 (以 ElemType为单位 )
} SqList;
a1 a2 … ai-1 ai … an
L.elem 线性表的 起始地址称作线性表的 基地址
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 16页
2.2.2 顺序表中基本操作的实现
1.初始化操作
2.查找元素操作
3.插入元素操作
4,删除元素操作
5,销毁结构操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 17页
1.初始化操作（算法 2.4 ）
void InitList_Sq( SqList &L,int maxsize = LIST_INIT_SIZE,
int incresize = LISTINCREMENT ) {
// 构造一个最大容量为 maxsize 的顺序表
L.elem = new ElemType [maxsize];
// 为顺序表分配一个最大容量为 maxsize 的数组空间
L.length = 0; // 顺序表中当前所含元素个数为 0
L.listsize = maxsize;
// 该顺序表可以容纳 maxsize 个数据元素
L.incrementsize = incresize;
// 需要时可扩容 incresize 个元素空间
} // InitList_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 18页
2.查找元素操作（算法 2.5）
int LocateElem_Sq( SqList L,ElemType e) {
// 在顺序线性表 L 中查找第 1 个值与 e 相等的数据元素，
// 若找到，则返回其在 L 中的位序，否则返回 0
i = 1; // i 的初值为第 1 个元素的位序
p = L.elem; // p 的初值为第 1 个元素的存储位置
while (i <= L.length && *p++ != e ) ++i; // 依次进行判定
if (i <= L.length)
return i; // 找到满足判定的数据元素为第 i 个元素
else
return 0; // 该线性表中不存在满足判定的数据元素
} // LocateElem_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 19页
3.插入元素操作（算法 2.6）
void ListInsert_Sq( SqList &L,int i,ElemType e ) {
// 在顺序线性表 L 的第 i 个元素之前插入新的元素 e,i 的合法值
//为 1≤i≤L.length+1,若表中容量不足，则按该顺序表的预定义增量
//扩容
if (i < 1 || i > L.length+1) ErrorMessage(,i 值不合法,);
if (L.length >= L.listsize) increment( L,L.incrementsize );
// 当前存储空间已满，为 L增加分配 L.incrementsize 个元素空间
q = &(L.elem[i-1]); // q为插入位置
for(p =&(L.elem[L.length-1]); p >= q; --p)
* (p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入 e
++L.length; // 表长增 1
}
// ListInsert_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 20页其中为顺序表追加空间的函数为,
void increment ( SqList &L,int k ) {
// 为顺序表扩大 k 个元素空间
ElemType a[];
a = new ElemType[L.listsize+k];
// a 为临时过渡的辅助数组
for(i = 0; i <L.length;i++)
a[i] = L.elem[i]; // 腾挪原空间数据
delete [] L.elem; // 释放数据元素所占原空间
L.elem = a; // 移交空间首地址
L.listsize += k; // 扩容后的顺序表最大空间
delete [] a; // 释放辅助数组空间
}
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 21页
4,删除元素操作（算法 2.7）
void ListDelete_Sq(SqList &L,int i,ElemType &e) {
// 在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值。
// i 的合法值为 1≤i≤L.length 。
if ((i < 1) || (i > L.length)) ERROR(“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
} // ListDelete_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 22页
5,销毁结构操作（ 算法 2.8）
void DestroyList_Sq( SqList &L ) {
// 释放顺序表 L 所占存储空间
delete[] L.elem;
L.listsize = 0;
L.length = 0;
}// DestroyList_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 23页
6,插入和删除操作的时间分析
插入操作的时间分析考虑插入移动元素的平均情况,
假设在第 i 个元素之前插入的概率为 Pi,则在长度为 n 的线性表中 插入一个元素所需移动元素次数的期望值 为：
若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：
1
1
)1(n
i iis
inpE
1
1
)1(11 n
iis
innE 2n?
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 24页重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 25页
2.2.3 顺序表其它算法举例
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 26页例 2.6 用顺序表实现例 2.2集合的合并（算法 2.13）
void purge_Sq( SqList &A,Sqlist &B ) {
// 已知顺序表 A 为空表，将顺序表 B 中所有值不同的元素插入到
// A 表中，操作完成后，释放顺序表 B 的空间
A.elem[0] = B.elem[0]; // 将 B 表中的第一个元素插入 A 表
A.length = 1;
for ( i=1; i<B.length; i++ ) {
e = B.elem[i]; // 从 B 表中取得第 i 个元素
j = 0;
while (j<A.length && A.elem[j] != e ) ++j;
// 在 A 表中进行查询
if ( j == A.length ) { // 该元素在 A 表中未曾出现
A.elem[A.length] = e; // 插入到 A 表的表尾
A.length ++; // A 表长度增 1
}// if
}//for
delete[] B.elem;
B.listsize = 0; // 释放 B 表空间
}// purge_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 27页
2.3 线性表的链式表示和实现
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 28页
2.3.1 单链表和指针用一组 地址任意 的存储单元 存放 线性表中的数据元素。
元素 + 指针 (指示后继元素存储位置 ) = 结点
以,结点的序列,表示线性表称作 链表
a1 a2 an-1 an ^……
head
数据域 指针域
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 29页头结点头指针头指针 空指针线性表为空表时，头结点的指针域为空
a1 a2 …,.,a n ^
有时为了操作方便，在第一个结点之前虚加一个“头结点”，以 指向头结点的指针 为链表的头指针 。
以线性表中第一个数据元素 a1的存储地址 作为线性表的地址，称作线性表的 头指针 。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 30页线性表的单链表的存储表示
typedef struct LNode {
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode,*LinkList;
若设 LNode *p,*q; LinkList H;
则 p,q,H都是指针变量,
p->data 表示数据域
p->next 表示指针域
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 31页指针赋值的操作指针指向结点 p=q
q p
指针指向后继 p=q->next
指针移动 p=p->next
q p
p p
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 32页
p
q
指针赋值的操作链指针改接 p->next =q
链指针改接后继 p->next =q->next
p
q
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 33页
2.3.2 单链表的基本操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 34页
1.求线性表的长度（ 算法 2.14 ）
int ListLength_L( LinkList L ) {
// L 为链表的头指针，本函数返回 L 所指链表的长度
p=L; k=0;
while ( p ) {
k++;
p=p->next; // k 计非空结点数
} //while
return k;
} // ListLength
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 35页
2.查找元素操作（ 算法 2.15 ）
LNode* LocateElem_L( LinkList L,ElemType e ) {
// 在 L 所指的链表中查找第一个值和 e 相等的数据元素，
//若存在，则返回它在链表中的位置，即指向该数据元
//素所在结点的指针；否则返回 NULL
p=L;
while ( p && p->data != e ) p=p->next;
return p;
} // LocateElem_L
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 36页
3.插入结点操作（ 算法 2.16 ）
void ListInsert_L( LinkList &L,Lnode* p,Lnode* s ) {
// 指针 p 指向 L 为头指针的链表中某个结点，将 s 结点
//插入到 p 结点之前
if (p == L) { // 将 s 结点插入在链表的第一个结点之前
s->next = L;
L = s; } //if
else {
q = L;
while (q->next != p ) q = q->next;
// 查找 p 的前驱结点 q
q->next = s;
s->next = p;
// 在链表中 q 结点之后插入 s 结点
}//else
} // ListInsert
q q p
L
s
q
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 37页
4.删除结点操作（ 算法 2.17 ）
void ListDelete_L( LinkList &L,Lnode* p,ElemType &e ) {
// p指向 L为头指针的链表中某个结点，从链表中删除该结点并由 e返回其元素
if (p == L) { // 删除链表中第一个结点，修改链表头指针
L = p->next;
}//if
else {
q = L;
while (q->next != p ) q = q->next; // 查找 p 的前驱结点 q
q->next = p->next ; // 修改 q 结点的指针域
}//else
e = p->data;
delete p; // 返回被删结点的数据元素，并释放结点空间
}// ListDelete_L
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 38页例 2.7 逆序创建链表（ 算法 2.18 ）
void CreateList_L(LinkList &L,ElemType A[],int n ) {
// 已知一维数组 A[n]中存有线性表的数据元素，逆序创
//建单链线性表 L
L = NULL; // 先建立一个空的单链表
for ( i = n-1; i >= 0; --i ) {
s = new LNode; // 生成新结点
s->data = A[i]; // 赋元素值
s->next = L;
L = s; // 插入在第一个结点之前
}//for
}// CreateList
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 39页例 2.9 单链表完成例 2.1（ 算法 2.20 ）
void union_L( LinkList &La,LinkList &Lb ) {
// 将 Lb 链表中所有在 La 链表中不存在的结点插入到 La 链表中，
// 并释放 Lb 链表中多余结点
if (!La) La = Lb;
// La 为空表，则由 Lb 链表的结点作为结果
else
while ( Lb ) { // Lb 链表非空
s = Lb; Lb = Lb->next; // 从 Lb 链表中删除第一个结点
else {
p = La;
while ( p && p->data != s ->data ) { // 在 La 链表中查找
pre = p;
p = p->next; }//while
if ( p ) delete s; // 找到相同元素，释放 s 结点
else { pre->next = s; s->next = NULL;}
// 将 s 结点插入在 La 链表的表尾 }//else
}// while(Lb)
}// union_L
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 40页
2.3.4 循环链表
最后一个结点的指针域的指针又指回第一个结点的链表
和单链表的差别仅在于,判别 链表中最后一个结点的 条件 不再是“后继是否为空”，而是,后继是否为头结点” 。
a1 a2 an-1 anhead
循环链表
……
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 41页
2.3.5 双向链表
//-----线性表的双向链表存储结构 -----
typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior; // 指向前驱的指针域
struct DuLNode *next; // 指向后继的指针域
} DuLNode,*DuLinkList;
双向链表
a1 a2
an ^
head ……
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 42页算法 2.21
void ListInsert_DuL(DuLinkList &L,DuNode* p,DuNode* s ) {
// 在带头结点的双向循环链表 L 中 p 结点之前插入 s 结点
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s; }
// ListInsert_DuL
a1 a2 a3 a4
p
s
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 43页
ai-1 ai
e
s->prior = p->prior;
p
s
插入
p-> prior -> next = s;
s->next = p;
p->prior = s;
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 44页算法 2.22
void ListDelete_DuL(DuLinkList &L,DuNode* p,ElemType &e) {
// 删除带头结点的双向循环链表 L中 p结点，并以 e返回它的数据元素
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
} // ListDelete_DuL
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 45页
ai-1
删除
ai ai+1
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
p
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 46页
2.4 有序表
有序表（ ordered list）的定义线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列即
ai≥ai-1 或 ai-1 ≤ ai
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 47页算法 2.23
void OrdInsert_Sq( SqList &L,ElemType x ) {
// 在顺序有序表 L 中插入数据元素 x，要求插入之后仍满足,有序,特性
i = L.length-1; // 从最后一个元素起进行查找比较
while (i>=0 && L.elem[i] ) {
L.elem[i+1] = L.elem[i]; // 值大于 x 的元素后移
i--;
}//while
L.elem[i+1] = x; // 插入元素 x
L.length++; // 表长增 1
} // OrdInsert_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 48页算法 2.24
void purge_Osq( SqList &L ) {
// 已知 L 为顺序有序表，本算法删除 L 中值相同的多余元素
i = -1; j = 0; // 设新的 La表为一个空表
while ( j < L.length ) {
if ( j==0 || L.elem[i] != L.elem[j] )
L.elem[++i] = L.elem[j]; // 将 L.elem[j]“插入,到 La 表中
// 且 La 表的表长增 1
j++; // 继续检查 Lb 表中下一个元素
}//while
L.length = i+1;
}// purge_Osq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 49页
i j
0 1 2 3 4 5 6 7 8 9 10 11
2 2 3 3 3 4 5 5 7 8 8 8
i j ji
3
j j ji
4
ji
5
j ji
7
ji
8
j j j
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 50页
2.5 顺序表和链表的综合比较选择何种顺序结构的考虑因素？
线性表的长度 n是否能预选确定？在程序执行过程中，
n的变化范围多大?
对线性表进行的主要操作是哪些？
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 1页第 2章 线性表主要内容：
1．线形表的类型定义
2,线形表的顺序表示和实现
3,线形表的链式表示和实现
4,有序表
5．顺序表和链表的综合比较
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 2页线性表 是一种最简单的 线性结构
线性结构的基本特征为,
线性结构是一个数据元素的 有序（次序）集
1．集合中必存在唯一的一个,第一元素,；
2．集合中必存在唯一的一个,最后元素,；
3．除最后元素在外，均有 唯一的后继 ；
4．除第一元素之外，均有 唯一的前驱 。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 3页
2.1 线形表的类型定义
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 4页抽象数据类型线性表的定义
ADT List {
数据对象：
D＝ { ai | ai ∈ElemSet,i=1,2,...,n,n≥0 }
{称 n 为线性表的表长 ; 称 n=0 时的线性表为空表。 }
数据关系：
R1＝ { <ai-1,ai >|ai-1,ai∈D,i=2,...,n }
{设线性表为 (a1,a2,.,,,ai,.,,,an),称
i 为 ai 在线性表中的位序。 }
基本操作：
结构初始化操作结构销毁操作引用型操作加工型操作
} ADT List
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 5页初始化操作
InitList( &L )
操作结果,构造一个空的线性表 L。
结构销毁操作
DestroyList( &L )
初始条件,线性表 L 已存在。
操作结果,销毁线性表 L。
引用型操作
ListEmpty( L )
初始条件,线性表 L已存在。
操作结果,若 L为空表，则返回 TRUE，
否则 FALSE。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 6页
ListLength( L )
初始条件,线性表 L已存在。
操作结果,返回 L中元素个数。
PriorElem( L,cur_e,&pre_e )
初始条件,线性表 L已存在。
操作结果,若 cur_e是 L的元素，但不是第一个，则用 pre_e 返回它的前驱，否则操作失败,pre_e无定义。
NextElem( L,cur_e,&next_e )
初始条件,线性表 L已存在。
操作结果,若 cur_e是 L的元素，但不是最后一个，则用 next_e返回它的后继，否则操作失败,next_e无定义。
引用型操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 7页
GetElem( L,cur_e,&next_e )
初始条件,线性表 L已存在,1≤i≤LengthList(L)
操作结果,用 e返回 L中第 i个元素的值。
LocateElem( L,e,compare( ) )
初始条件,线性表 L已存在,compare( )是元素判定函数。
操作结果,返回 L中第 1个与 e满足关系 compare( )的元素的位序。
若这样的元素不存在，则返回值为 0。
ListTraverse(L,visit( ))
初始条件,线性表 L已存在。
操作结果,依次对 L的每个元素调用函数 visit( )。一旦
visit( )失败，则操作失败。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 8页
ClearList( &L )
初始条件,线性表 L已存在。
操作结果,将 L重置为空表。
PutElem( L,i,&e )
初始条件,线性表 L已存在,1≤i≤LengthList(L)
操作结果,L中第 i个元素赋值同 e的值。
ListInsert( &L,i,e )
初始条件,线性表 L已存在,1≤i≤LengthList(L)+1
操作结果,在 L的第 i个元素之前插入新的元素 e,L的长度增 1。
ListDelete(&L,i,&e)
初始条件,线性表 L已存在且非空,1≤i≤LengthList(L)
操作结果,删除 L的第 i个元素，并用 e返回其值,L的长度减 1。
加工型操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 9页例 2-1 假设有两个集合 A和 B分别用两个线性表 LA和 LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合
A＝ A∪B 。
上述问题可演绎为，要求对线性表作如下操作：扩大线性表 LA，将存在于线性表 LB中而不存在于线性表 LA中的数据元素插入到线性表
LA中去。
1．从线性表 LB中依次取得每个数据元素 ; GetElem(LB,i,e)
2．依值在线性表 LA中进行查访 ; LocateElem(LA,e,equal( ))
3．若不存在，则插入之。 ListInsert(LA,n+1,e)
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 10页算法 2.1
void union(List &La,List Lb) {
// 将所有在线性表 Lb中但不在 La中的数据元素插入到 La中
La_len = ListLength(La);
Lb_len =ListLength(Lb); // 求线性表的长度
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb,i,e);
// 取 Lb中第 i个数据元素赋给 e
if(!LocateElem(La,e,equal( ))
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
}
} // union
1 3 4 8 2 4 5
La Lb
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 11页例 2-2
已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B中所有值各不相同的数据元素。
仍选用线性表表示集合
从集合 B 取出物件放入集合 A要求集合 A中同样物件不能有两件以上
因此，算法的策略应该和例 2-1相同集合 B集合 A
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 12页算法 2.2
void purge(List &La,List &Lb) {
// 构造线性表 La，使其只包含 Lb 中所有值不相同的数据元素，
// 操作完成后，线性表 Lb 不再存在
InitList(La); La_len=0; // 创建一个空的线性表 La
while (!ListEmpty(Lb)) { // Lb 表的元素尚未处理完
ListDelete( Lb,1,e );
// 从 Lb 中删除第一个数据元素赋给 e
if (!LocateElem( La,e) )
ListInsert( La,++La_len,e );
// 若 La 中不存在值和 e 相等的数据元素，则插入之
} // while
DestroyList(Lb); // 销毁线性表 Lb
} // purge
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 13页
2.2 线性表的顺序表示和实现
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 14页
2.2.1 顺序表 —线性表的顺序存储表示
线性表的顺序存储,用一组地址连续的存储单元依次存放线性表中的数据元素。
顺序线性表称为 顺序表。
在程序设计语言中，采用一维数组来实现。
需要考虑数组容量的动态扩充；
a1 a2 … ai-1 ai … an
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 15页顺序表的定义
//----- 线性表的动态分配顺序存储结构 -----
#define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
typedef struct {
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的数组容量 (以 ElemType为单位 )
int incrementsize; //约定的增补空间量 (以 ElemType为单位 )
} SqList;
a1 a2 … ai-1 ai … an
L.elem 线性表的 起始地址称作线性表的 基地址
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 16页
2.2.2 顺序表中基本操作的实现
1.初始化操作
2.查找元素操作
3.插入元素操作
4,删除元素操作
5,销毁结构操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 17页
1.初始化操作（算法 2.4 ）
void InitList_Sq( SqList &L,int maxsize = LIST_INIT_SIZE,
int incresize = LISTINCREMENT ) {
// 构造一个最大容量为 maxsize 的顺序表
L.elem = new ElemType [maxsize];
// 为顺序表分配一个最大容量为 maxsize 的数组空间
L.length = 0; // 顺序表中当前所含元素个数为 0
L.listsize = maxsize;
// 该顺序表可以容纳 maxsize 个数据元素
L.incrementsize = incresize;
// 需要时可扩容 incresize 个元素空间
} // InitList_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 18页
2.查找元素操作（算法 2.5）
int LocateElem_Sq( SqList L,ElemType e) {
// 在顺序线性表 L 中查找第 1 个值与 e 相等的数据元素，
// 若找到，则返回其在 L 中的位序，否则返回 0
i = 1; // i 的初值为第 1 个元素的位序
p = L.elem; // p 的初值为第 1 个元素的存储位置
while (i <= L.length && *p++ != e ) ++i; // 依次进行判定
if (i <= L.length)
return i; // 找到满足判定的数据元素为第 i 个元素
else
return 0; // 该线性表中不存在满足判定的数据元素
} // LocateElem_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 19页
3.插入元素操作（算法 2.6）
void ListInsert_Sq( SqList &L,int i,ElemType e ) {
// 在顺序线性表 L 的第 i 个元素之前插入新的元素 e,i 的合法值
//为 1≤i≤L.length+1,若表中容量不足，则按该顺序表的预定义增量
//扩容
if (i < 1 || i > L.length+1) ErrorMessage(,i 值不合法,);
if (L.length >= L.listsize) increment( L,L.incrementsize );
// 当前存储空间已满，为 L增加分配 L.incrementsize 个元素空间
q = &(L.elem[i-1]); // q为插入位置
for(p =&(L.elem[L.length-1]); p >= q; --p)
* (p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入 e
++L.length; // 表长增 1
}
// ListInsert_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 20页其中为顺序表追加空间的函数为,
void increment ( SqList &L,int k ) {
// 为顺序表扩大 k 个元素空间
ElemType a[];
a = new ElemType[L.listsize+k];
// a 为临时过渡的辅助数组
for(i = 0; i <L.length;i++)
a[i] = L.elem[i]; // 腾挪原空间数据
delete [] L.elem; // 释放数据元素所占原空间
L.elem = a; // 移交空间首地址
L.listsize += k; // 扩容后的顺序表最大空间
delete [] a; // 释放辅助数组空间
}
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 21页
4,删除元素操作（算法 2.7）
void ListDelete_Sq(SqList &L,int i,ElemType &e) {
// 在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值。
// i 的合法值为 1≤i≤L.length 。
if ((i < 1) || (i > L.length)) ERROR(“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
} // ListDelete_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 22页
5,销毁结构操作（ 算法 2.8）
void DestroyList_Sq( SqList &L ) {
// 释放顺序表 L 所占存储空间
delete[] L.elem;
L.listsize = 0;
L.length = 0;
}// DestroyList_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 23页
6,插入和删除操作的时间分析
插入操作的时间分析考虑插入移动元素的平均情况,
假设在第 i 个元素之前插入的概率为 Pi,则在长度为 n 的线性表中 插入一个元素所需移动元素次数的期望值 为：
若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：
1
1
)1(n
i iis
inpE
1
1
)1(11 n
iis
innE 2n?
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 24页重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 25页
2.2.3 顺序表其它算法举例
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 26页例 2.6 用顺序表实现例 2.2集合的合并（算法 2.13）
void purge_Sq( SqList &A,Sqlist &B ) {
// 已知顺序表 A 为空表，将顺序表 B 中所有值不同的元素插入到
// A 表中，操作完成后，释放顺序表 B 的空间
A.elem[0] = B.elem[0]; // 将 B 表中的第一个元素插入 A 表
A.length = 1;
for ( i=1; i<B.length; i++ ) {
e = B.elem[i]; // 从 B 表中取得第 i 个元素
j = 0;
while (j<A.length && A.elem[j] != e ) ++j;
// 在 A 表中进行查询
if ( j == A.length ) { // 该元素在 A 表中未曾出现
A.elem[A.length] = e; // 插入到 A 表的表尾
A.length ++; // A 表长度增 1
}// if
}//for
delete[] B.elem;
B.listsize = 0; // 释放 B 表空间
}// purge_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 27页
2.3 线性表的链式表示和实现
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 28页
2.3.1 单链表和指针用一组 地址任意 的存储单元 存放 线性表中的数据元素。
元素 + 指针 (指示后继元素存储位置 ) = 结点
以,结点的序列,表示线性表称作 链表
a1 a2 an-1 an ^……
head
数据域 指针域
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 29页头结点头指针头指针 空指针线性表为空表时，头结点的指针域为空
a1 a2 …,.,a n ^
有时为了操作方便，在第一个结点之前虚加一个“头结点”，以 指向头结点的指针 为链表的头指针 。
以线性表中第一个数据元素 a1的存储地址 作为线性表的地址，称作线性表的 头指针 。
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 30页线性表的单链表的存储表示
typedef struct LNode {
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode,*LinkList;
若设 LNode *p,*q; LinkList H;
则 p,q,H都是指针变量,
p->data 表示数据域
p->next 表示指针域
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 31页指针赋值的操作指针指向结点 p=q
q p
指针指向后继 p=q->next
指针移动 p=p->next
q p
p p
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 32页
p
q
指针赋值的操作链指针改接 p->next =q
链指针改接后继 p->next =q->next
p
q
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 33页
2.3.2 单链表的基本操作
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 34页
1.求线性表的长度（ 算法 2.14 ）
int ListLength_L( LinkList L ) {
// L 为链表的头指针，本函数返回 L 所指链表的长度
p=L; k=0;
while ( p ) {
k++;
p=p->next; // k 计非空结点数
} //while
return k;
} // ListLength
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 35页
2.查找元素操作（ 算法 2.15 ）
LNode* LocateElem_L( LinkList L,ElemType e ) {
// 在 L 所指的链表中查找第一个值和 e 相等的数据元素，
//若存在，则返回它在链表中的位置，即指向该数据元
//素所在结点的指针；否则返回 NULL
p=L;
while ( p && p->data != e ) p=p->next;
return p;
} // LocateElem_L
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 36页
3.插入结点操作（ 算法 2.16 ）
void ListInsert_L( LinkList &L,Lnode* p,Lnode* s ) {
// 指针 p 指向 L 为头指针的链表中某个结点，将 s 结点
//插入到 p 结点之前
if (p == L) { // 将 s 结点插入在链表的第一个结点之前
s->next = L;
L = s; } //if
else {
q = L;
while (q->next != p ) q = q->next;
// 查找 p 的前驱结点 q
q->next = s;
s->next = p;
// 在链表中 q 结点之后插入 s 结点
}//else
} // ListInsert
q q p
L
s
q
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 37页
4.删除结点操作（ 算法 2.17 ）
void ListDelete_L( LinkList &L,Lnode* p,ElemType &e ) {
// p指向 L为头指针的链表中某个结点，从链表中删除该结点并由 e返回其元素
if (p == L) { // 删除链表中第一个结点，修改链表头指针
L = p->next;
}//if
else {
q = L;
while (q->next != p ) q = q->next; // 查找 p 的前驱结点 q
q->next = p->next ; // 修改 q 结点的指针域
}//else
e = p->data;
delete p; // 返回被删结点的数据元素，并释放结点空间
}// ListDelete_L
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 38页例 2.7 逆序创建链表（ 算法 2.18 ）
void CreateList_L(LinkList &L,ElemType A[],int n ) {
// 已知一维数组 A[n]中存有线性表的数据元素，逆序创
//建单链线性表 L
L = NULL; // 先建立一个空的单链表
for ( i = n-1; i >= 0; --i ) {
s = new LNode; // 生成新结点
s->data = A[i]; // 赋元素值
s->next = L;
L = s; // 插入在第一个结点之前
}//for
}// CreateList
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 39页例 2.9 单链表完成例 2.1（ 算法 2.20 ）
void union_L( LinkList &La,LinkList &Lb ) {
// 将 Lb 链表中所有在 La 链表中不存在的结点插入到 La 链表中，
// 并释放 Lb 链表中多余结点
if (!La) La = Lb;
// La 为空表，则由 Lb 链表的结点作为结果
else
while ( Lb ) { // Lb 链表非空
s = Lb; Lb = Lb->next; // 从 Lb 链表中删除第一个结点
else {
p = La;
while ( p && p->data != s ->data ) { // 在 La 链表中查找
pre = p;
p = p->next; }//while
if ( p ) delete s; // 找到相同元素，释放 s 结点
else { pre->next = s; s->next = NULL;}
// 将 s 结点插入在 La 链表的表尾 }//else
}// while(Lb)
}// union_L
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 40页
2.3.4 循环链表
最后一个结点的指针域的指针又指回第一个结点的链表
和单链表的差别仅在于,判别 链表中最后一个结点的 条件 不再是“后继是否为空”，而是,后继是否为头结点” 。
a1 a2 an-1 anhead
循环链表
……
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 41页
2.3.5 双向链表
//-----线性表的双向链表存储结构 -----
typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior; // 指向前驱的指针域
struct DuLNode *next; // 指向后继的指针域
} DuLNode,*DuLinkList;
双向链表
a1 a2
an ^
head ……
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 42页算法 2.21
void ListInsert_DuL(DuLinkList &L,DuNode* p,DuNode* s ) {
// 在带头结点的双向循环链表 L 中 p 结点之前插入 s 结点
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s; }
// ListInsert_DuL
a1 a2 a3 a4
p
s
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 43页
ai-1 ai
e
s->prior = p->prior;
p
s
插入
p-> prior -> next = s;
s->next = p;
p->prior = s;
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 44页算法 2.22
void ListDelete_DuL(DuLinkList &L,DuNode* p,ElemType &e) {
// 删除带头结点的双向循环链表 L中 p结点，并以 e返回它的数据元素
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
} // ListDelete_DuL
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 45页
ai-1
删除
ai ai+1
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
p
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 46页
2.4 有序表
有序表（ ordered list）的定义线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列即
ai≥ai-1 或 ai-1 ≤ ai
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 47页算法 2.23
void OrdInsert_Sq( SqList &L,ElemType x ) {
// 在顺序有序表 L 中插入数据元素 x，要求插入之后仍满足,有序,特性
i = L.length-1; // 从最后一个元素起进行查找比较
while (i>=0 && L.elem[i] ) {
L.elem[i+1] = L.elem[i]; // 值大于 x 的元素后移
i--;
}//while
L.elem[i+1] = x; // 插入元素 x
L.length++; // 表长增 1
} // OrdInsert_Sq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 48页算法 2.24
void purge_Osq( SqList &L ) {
// 已知 L 为顺序有序表，本算法删除 L 中值相同的多余元素
i = -1; j = 0; // 设新的 La表为一个空表
while ( j < L.length ) {
if ( j==0 || L.elem[i] != L.elem[j] )
L.elem[++i] = L.elem[j]; // 将 L.elem[j]“插入,到 La 表中
// 且 La 表的表长增 1
j++; // 继续检查 Lb 表中下一个元素
}//while
L.length = i+1;
}// purge_Osq
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 49页
i j
0 1 2 3 4 5 6 7 8 9 10 11
2 2 3 3 3 4 5 5 7 8 8 8
i j ji
3
j j ji
4
ji
5
j ji
7
ji
8
j j j
Da
ta
Str
uc
tur
e
数据结构——
第
2
章线性表胡建华 2009-7-24计算机教研室第 50页
2.5 顺序表和链表的综合比较选择何种顺序结构的考虑因素？
线性表的长度 n是否能预选确定？在程序执行过程中，
n的变化范围多大?
对线性表进行的主要操作是哪些？
