线性表的定义
线性表:简称表,是n(n≥0)个具有相同类型数据元素的有限序列。
线性表的长度:线性表中数据元素的个数。
空表:长度等于零的线性表,记为:L=( )。
非空表记为:L=(a1, a2 , …, ai-1, ai , …, an)。
其中,ai(1≤i≤n)称为数据元素;下角标 i 表示该元素在线性表中的位置或序号
线性表的特征
n个数据元素的有限序列

线性结构的基本特征为:
- 集合中必存在唯一的一个“第一元素”
- 集合中必存在唯一的一个 “最后元素”
- 除最后元素在外,均有 唯一的后继;
- 除第一元素之外,均有 唯一的前驱
- 元素个数n—表长度,n=0空表
- 1<i<n时 –ai的直接前驱是ai-1,a1无直接前驱 –ai的直接后继是ai+1,an无直接后继
- 元素同构,且不能出现缺项
线性表的抽象数据类型定义
ADT List
Data: D={ ai | ai ∈ElementSet, i=1, 2, …, n, n≥0}
Relation: R={ <ai-1, ai >| ai-1, ai∈D, i=2, …, n, }
Operation:
- InitList(&L):初始化线性表,构造一一个空的线性表L。
- DestroyList(&L):销毁线性表,释放线性表L占用的内存空间。
- ListEmpty(L):判断线性表是否为空表,若L为空表,则返回真,否则返回假。
- ListLength(L):求线性表的长度,返回L中元素的个数。
- DispList(L):输出线性表,当线性表L不为空时顺序显示L中各结点的值域。
- GetElem(L,i,&e):求线性表中某个数据元素值,用e返回L中第i(1≤i≤n)个元素的值。
- LocateElem(L,e):按元素值查找,返回L中第一个值域与e相等的元素的序号,若这样的元素不存在,则返回值为0。
- ListInsert(&L,i,e):插人数据元素,在L的第i(1≤i≤n+1)个位置插人-一个新的元素e,L的长度增1。
- ListDelete(&L,i,&e):删除数据元素,删除L的第i(1≤i≤n)个元素,并用e返回其值,L的长度减1。
endADT
线性表的作用主要体现在两个方面,当个线性表实现后,程序员可以直接使用它来存放数据,即作为存放数据的容器,另外程序员可以直接使用它的基本运算来完成更复杂的功能。线性表基本运算是与求解问题相关的,上面列出的9个基本运算是线性表最常用的功能,在实际应用中大家可以根据需要进行增减。
实例
例题一
假设:有两个集合 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 相同的数据元素,则插入之
}
}
例题二
双表归并——试将非递减的有序表 La 和 Lb 归并为另一个有序表 Lc。
思路:
先设LC为空表,再按下法将LA或LB中的元素逐个插入到LC中:设置三个指针i、j和k分别指向LA、LB和LC中的当前元素a、b和c,LC中的当前元素c按如下方法确定:

void MergeList(List La, List Lb, List &Lc)
{
//本算法将非递减的有序表 La 和 Lb 归并为 Lc
InitList(Lc); // 构造空的线性表 Lc
i = j = 1; k = 0;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while((i <= La_len) && (j <= Lb_len)) {
//La 和 Lb 均非空,i = j = 1, k = 0
GetElem(La, i, ai);
GetElem(Lb, j, bj);
if (ai <= bj) {
ListInsert(Lc, ++k, ai); ++i;
} else {
ListInsert(Lc, ++k, bj); ++j; }
}
while (i <= La_len) {
// 当La不空时
GetElem(La, i++, ai);
ListInsert(Lc, ++k, ai); }
while (j <= Lb_len) {
// 当Lb不空时
GetElem(Lb, j++, bj);
ListInsert(Lc, ++k, bj); }
}