第2章 线形表
所学内容：线性表的类型定义；线性表类型的实现——顺序映象；链式映象；一元多项式的表示。
线性结构：一个数据元素的有序（次序）集。
线性结构的基本特征：集合中必存在唯一的一个“第一元素”；集合中必存在唯一的一个“最后元素”；除最后元素外，均有唯一的后继；除第一元素外，均有唯一的前驱。
一．线性表的类型定义
ADT List{
数据对象：
D = {
a(i) |
a(i)属于ElemSet, i = 1, 2, …..n,
n>= 0 } 称n为线形表的表长，称n=0时的线形表为空表
数据关系：
R1 = {<
a(i-1) ,a(i)
> | a(i-1)
, a(i) 属于
D, i = 2, …… n}
设线形表为（
a(1)，a(2)
，。。。。a(i)
，。。。。。。。a(n)
）称i为a在线形表中的次序。
基本操作：
{结构初始化}
InitList(&L)
操作结果：构造一个空的线形表L。
{销毁结构}
DestroyList(&L)
初始条件：线性表L存在。
操作结果：销毁线性表L。
{引用型操作}
ListEmpty(L)
ListLength(L)
PriorElem(L,
cur_e, &pre_e)
NextElem(L, cur_e,
&next_e)
GetElem(L, i,
&e)
LocateElem(L, e,
compare() )
ListTraverse(L,
visit() ) 遍历
{加工型操作}
ClearList(&L)
PutElem(L, i,
&e)
ListInsert(&L,
i, e)
ListDelete(&L,
i, &e)
例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)
void union(List
&La, List Lb)
{
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 相同的数据元素，则插入
}
}
例2：
已知一个非纯集合B（数据元素有重复），试构造一个纯集合A（数据元素无重复），使A中只包含B中所有值各不相同的数据元素。
解法1：对集合B不进行排序
void purge(List
&La, List Lb)
{
InitList(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 相同的数据元素，则插入
}
}
LocateElem时间复杂度为n，还有一个外循环，所以该算法的时间复杂度为
解法2：首先对集合B进行排序，然后调用函数purge（…..）
void purge(List
&La, List Lb)
{
InitList(LA);
La_len = ListLength(La);
Lb_len = ListLength(Lb); //求线形表的长度
For(i=1; i
<=Lb_len; i ++)
{
GetElem(Lb, i, e); //取Lb中第I个元素赋给e
If(ListEmpty(LA) || ! equal(en, e) )
{
ListInsert(La,
++La_len, e)//La中不存在和e 相同的数据元素，则插入
en = e; //en表示LA中的最后一个元素
}
}
}
外循环为n，ListEmpty时间复杂度为常量，所以该算法的时间复杂度为常量n
例3：归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样的特性
设La =（
a(1)，a(2)
，。。。。。a(i)
，。。。。。。。a(n)
）
Lb=（
b(1) ，b(2)
，。。。。。b( j )
，。。。。。。。b(m)
）
Lc =（c(1)
，c(2)
，。。。。。c(i)
，。。。。。。。c(m+n)
）
则
1． 分别从LA和LB中取得当前元素ai和aj;
2． 若ai<=aj，则将ai插入到LC中，否则将bj插入到LC中
void MergeList(List La, List Lb,List &Lc)
{
InitList(Lc);
i=j=1;
k=0;
La_len
= ListLength(La);
Lb_len
= ListLength(Lb);
while((i<=La_len)
&& (j<=Lb_len) )
{
//La和Lb均非空
GetElem(La,
i, ai);
GetElem(Lb,
j, bj);
if(ai
<= bj)
{
ListInsert(Lc,
++k, ai);
++i;
}
else
{
ListInsert(Lc,
++k, aj);
++j;
}
}
//当LA或LB有一个遍历完后
while(i
<= La_len)
{
GetElem(La,
i++, ai);
ListInsert(Lc,
++k, ai);
}
while(j
<= Lb_len)
{
GetElem(Lb,
b++, bj);
ListInsert(Lc,
++k, bj);
}
}
二．线性表类型的实现——顺序映象
1.定义：用一组地址连续的存储单元依次存放线性表中的数据元素。第一个数据元素的的地址，就为该线性表的起始地址，或称做线性表的基地址。
2.顺序映象的C语言描述：
#define
LIST_INIT_SIZE 80 //线性表存储空间的初始分配量
#define
LISTINCREMENT 10 //线性表存储空间的分配增量
typedef
struct{
ElemType *elem; //存储空间基址
Int
length; //当前长度
Int
listsize; //当前分配的存储容量，以sizeof(ElemType)为单位
}SqList; //顺序表
线形表的初始化：
Status
InitList_Sq(SqList& L)
{
//构造一个空的线形表
L.elem
= (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
If(!
L.elem)
Exit(OVERFLOW);
L.length
= 0;
L.listsize
= LIST_INIT_SIZE;
return
OK;
}
3.线形表的操作：
a. LocateElem的实现
int LocateElem(SqList L, ElemType e,
Status(*compare)(ElemType, ElemType))
{
i = 0; // i 的初值为第1元素的位序
p = L.elem; //p的初值第1元素的存储位置
While(i <= L.length &&
!(*compare)(*p++, e))
++i;
if(i <= L.length)
return i;
else
return 0;
}
该算法的时间复杂度O（ListLength(L)
）
b. ListInsert(&L, i, e)的实现
插入元素时，线形表的逻辑结构发生了什么变化？
1．（a1,…….a(i-1),a(i),….,a(n)）变为（a1,…….a(i-1),e,a(i),….,a(n)）
2.长度加1
status ListInsert_Sq(SqList &L,
int pos, ElemType e)
{
if(pos < 1 || pos > L.length()
) //插入位置不合法
return ERROR;
if(L.length == L.listsize) //当前存储空间已满，增加分配
{
newbase = (ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
exit(OVERFLOW); //存储分配失败
L.elem = newbase; //新基址
L.listsize += LISTINCREMENT; //增加存储容量
}
q =
&(L.elem[pos-1]); //q指示插入位置
For(p =
&(L.elem[L.length –1]); p>=q; --p)
*(p+1) = *p; //插入位置及之后的元素右移
*q = e; //插入e
++L.length; //表长增1
return OK;
}
时间复杂度O（ListLength(L)）
c. ListDelete(&L, i, &e)的实现：
删除元素时，线性表的逻辑结构发生什么变化？
1.（a1,…….a(i-1),a(i),a(i+1)….,a(n)）变为（a1,…….a(i-1),a(i+1),….,a(n)）
2. 长度减1
status ListDelete_Sq(SqList &L,
int pos, ElemType &e)
{
if(pos < 1 || pos > L.length()
) //插入位置不合法
return ERROR;
p = &(L.elem[pos-1]); //p为删除元素的位置
e = *p; //被删除元素的值赋给e
q = L.elem + L.length –1; //表尾元素的位置
for(++p; p<=q;
++p)
*(p-1) = *p; //被删除元素之后的元素左移
--L.length; //表长减1
return OK;
}
时间复杂度O（ListLength(L)）
(待续）
