线性表

1.1 线性结构

线性结构的特点：在数据元素的非空有限集中，

（1）存在唯一的一个被称做“第一个”的数据元素；

（2）存在唯一的一个被称做“最后一个”的数据元素‘’；

（3）除第一个之外，集合中的每个数据元素均只有一个前驱；

（4）除最后一个之外，集合中每个数据元素均只有一个后继。

1.2 线性表的类型定义

线性表是n个类型相同的数据元素的有限序列。在不同的情况下各不同。

在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。

数据元素称为记录，含有大量记录的线性表又称为文件。

注：同一线性表中的元素必定具有相同的特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

线性表一般表示为 L=(a₁,a₂,…,a_i-1,a_i,a_i+1,…a_n)

L为线性表的名称，n为线性表L中元素的个数，称为表长，当n=0时，称为空表。a₁是线性表的第一个元素，称为首元素。a_n是最后一个数据元素，称为“尾元素”。a_i为线性表L的第i个数据元素，i称为其位序，a_i的前驱是a_i-1，a_i的后继为a_i+1。

线性表中不是所有的元素都有前驱或者是都有后继的，首元素无前驱，尾元素无后继。

在非空表中的每一个数据元素都有一个确定的位置。

1.2.1 线性表的抽象数据类型描述

基本操作

InitList(&L)：构造一个空的线性表L

DestroyList(&L)：线性表L已存在时，销毁线性表L

ClearList(&L) ：线性表L已存在时，将L重置为空表

ListEmpty(L)：线性表L已存在，若L为空表，则返回TRUE，否则返回FALSE

ListLength(L)：线性表L已存在时，返回L中数据元素的个数

GetElem(L，i，&e)：线性表L已存在时（1≤i≤ListLength(L)），用e返回L中第i个数据元素的值，返回值为e。

ListInsert(&L，i，e)：线性表L已存在时（1≤i≤ListLength(L)），在L中的第i个位置之前插入新的数据元素e，L的长度加1。即新插入的数据元素e在L的第i的位置上，原来第i个位置及其之后的元素均向后移动一个位置。

ListDelete(&L，i，&e)：线性表L已存在且非空时（1≤i≤ListLength(L)），删除L的第i个数据元素，并用e返回其值，L的长度减1。即删除第i个数据元素后，原来第i+1及其后面的数据元素均向前移动一个位置。并用e来接收原来第i个位置的数据元素。

LocateElem(L，e)：按元素值进行查找。返回L中第1个值域与e相等的数据元素的序号，若这样的元素不存在，则返回值为0。

注：当函数中的参数改变时（函数运行前后的变量），需要在参数前面添加&符号。&符号为地址运算符，对变量应用地址运算符就可以获得它的位置。

1.2.2 例题：合并线性表

已知线性表L_A，L_B，表中的数据元素按值非递减有序排列，现要求将L_A和L_B归并为一个新的线性表L_C，且L_C中的数据元素仍按值非递减有序排列。

L_A = （1，3，5，7，9）

L_B = （2，4，6，7，8，9，10）

则

L_C=（1，2，3，4，5，6，7，7，8，9，9，10）

分析：非递减有序排列，即数据元素有相等的。非递减：递增或相等。

• 设L_C为空表，将L_A或L_B中的元素逐个插入到L_C中即可。

• L_C中的元素按值非递减有序排列，可设两个指针i和j分别指向L_A和L_B中的某个元素，若i指向的元素为a，j指向的元素为b，则当前应插入到L_C中的元素c。

  当a≤b时，c=a。当a＞b时，c=b。

• 指针i和j的初值均为1，在所指元素插入L_C后，在L_A或L_B中顺序后移。

代码：

void MergeList(List La,List Lb,List &Lc) {
    InitList(Lc);   // 初始化Lc
    i=j=1;k=0;      // 将指针i,j的初值设为1,k的初值设为0。指针i,j表示该元素在当前线性表中的位置。
    La_len =ListLength(La) ;Lb_len=ListLength(Lb);  // 获取La和Lb的长度La_len,Lb_len
    while(i<=La_len&&j<=Lb_len){  //判断La和Lb是否均为空，用∪，如果均为空，则不执行循环。
        GetElem(La,i,ai);   // 根据GetElem()函数 获取线性表La中第i个位置的数据元素，并用ai返回其值。
        GetElem(Lb,j,bj);   // 根据GetElem()函数 获取线性表Lb中第j个位置的数据元素，并用bj返回其值。
        if(ai<=bj){
            ListInsert(&Lc,++k,ai);  // 当ai≤bj时，在Lc中的第k个位置插入ai。
            i++;   // ai插入到Lc中之后，对i自增1，指针i跳转到下一个La的位置。
        }
        else{
            ListInsert(&Lc,++k,bj); // 当ai>bj时，在Lc中的第k个位置插入bj。
            j++;
        }
    }
    // 当Lb中的数据元素为空时，则将La中的各个元素依次取出，并插入到Lc中。
    while(i<=La_len){
        GetElem(La,i++,ai);
        ListInsert(&Lc,++k,ai);
    }
    // 当La中的数据元素为空时，则将Lb中的各个元素依次取出，并插入到Lc中。
    while(j<=Lb_len) {
        GetElem(Lb,j++,bj);
        ListInsert(&Lc,++k,bj);
    }
}
// 该算法的时间复杂度为O(La_len+Lb_len)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

算法设计取决于数据逻辑结构，有了逻辑结构，就可以设计算法。算法的实现则依赖于数据的存储结构。