数据结构——线性表

线性表的定义

线性表：简称表，是n（n≥0）个具有相同类型数据元素的有限序列。

线性表的长度：线性表中数据元素的个数。

空表：长度等于零的线性表，记为：L=( )。

非空表记为：L＝（a₁, a₂, …, a_i_-1, a_i, …, a_n)。

其中，a_i（1≤i≤n）称为数据元素；下角标 i 表示该元素在线性表中的位置或序号

线性表的特征

n个数据元素的有限序列

线性结构的基本特征为:

集合中必存在唯一的一个“第一元素”
集合中必存在唯一的一个 “最后元素”
除最后元素在外，均有唯一的后继；
除第一元素之外，均有唯一的前驱
元素个数n—表长度，n=0空表
1<i<n时 –a_i的直接前驱是a_i-1，a₁无直接前驱 –a_i的直接后继是a_i+1，a_n无直接后继
元素同构，且不能出现缺项

线性表的抽象数据类型定义

ADT List

Data： D={ a_i | a_i ∈ElementSet, i=1, 2, …, n, n≥0}

Relation： R={ <a_i-1, a_i >| a_i-1, a_i∈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); }
}