线性表基础总结

发表于 更新于 分类于 Waline：

这两个周重新拿出了大学的数据结构与算法看了看，看完了第二章线性表的部分，又有些新的收获吧，总结一下。

数据结构的基本概念

数据

数据是信息的载体，是描述客观事物属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号的合集。数据是计算机程序加工的原料。

数据元素

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号，姓名等数据项组成。

数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。如整型对象就是集合N={0,1,2,…}

数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

  • 原子类型：其值不可再分的数据类型
  • 结构类型：其值可以再分解为若干成分（分量）的数据类型
  • 抽象数据类型：抽象数据组织及与之相关的操作

数据结构

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构.

数据结构包括三方面的内容：逻辑结构，存储结构和数据的运算。

数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选的逻辑结构，而算法的实现，依赖所采用的存储结构。

逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储结构无关，是独立于计算机的。

数据的逻辑结构分为线性结构和非线性结构。线性表是典型的线性结构。集合，树，图是典型的非线性结构。

存储结构

存储结构是指数据结构在计算机中的表示，也成为物理结构。

主要有顺序存储，链式存储，索引存储和散列存储。

线性表的基本概念

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列。

线性表的特点：

  • 表中元素个数有限
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素都占有相同大小的存储空间。
  • 表中元素具有抽象性，即讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表是一种逻辑结构，表示元素之间的一对一相邻关系。

顺序表和链表表示的是存储结构。

看到的几个简单但巧妙的算法思想

第一个

从顺序表中删除其值在给定值s和t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

算法思想：从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数（初始时k=0），对于当前扫描的元素，若其值不再s和t之间，则前移k个位置，否则执行k++。由于这样，每个不在s到t之间的元素仅移动一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool Del_s_t(SqlList &L, ElemType s, ElemType t) {
    int i, k = 0;
    if (L.length === 0 || s >= t) {
        return false;
    }
    for(i = 0; i < L.length; i++) {
        if(L.data[i] >= s && L.data[i] <= t) {
            k++
        } else {
            L.data[i - k] = L.data[i];
        }
    }
    L.length -= k;
    return true;
}

在这个算法中，i表示当前遍历到的节点，k表示0 - i 之间需要删除的节点的数量，也就意味着0 到 (i - k)之间是需要保留的节点，(i - k) 到 i之间是需要删除的几点。

这个关系，利用数学归纳法，在i等于0时开始，在接下来的遍历到每个节点都保证整个关系，那最后i为L.length时，最终数组的保留节点就应该是0到L.length-k

其实也可以用k表示需要保留的节点数量，那这段代码就变成了

1
2
3
4
5
6
7
8
9
10
11
12
13
bool Del_s_t(SqlList &L, ElemType s, ElemType t) {
    int i, k = 0;
    if (L.length === 0 || s >= t) {
        return false;
    }
    for(i = 0; i < L.length; i++) {
        if(L.data[i] < s || L.data[i] > t) {
            L.data[k++] = L.data[i]
        }
    }
    L.length = k;
    return true;
}

第二个

设将n个整数存放到一位数组R中。设计一个在时间和空间上都尽可能高效的算法。将R中保存的序列循环左移p个位置，即将R中的数据由（X0, X1, …, XR）变为(Xp, Xp+1, … XR, X0, X1, … , Xp - 1)

算法思想：将这个问题视为把数组ab转化为ba，那么就先把a逆置得到a逆b，再将b逆置得到a逆b逆，最后将a逆b逆整个逆置，得到ba。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Reverse(int R[], int from, int to) {
    int i, temp;
    for(i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);
    Reverse(R, p, n - 1);
    Reverse(R, 0, n - 1);h
}

第三个

设一个长度为L的升序序列S，处在第[L / 2]的位置的数称为S的中位数。例如升序序列S1（11，13,15，17,19），则其中位数为15。两个序列的中位数是包含他们所有元素的升序序列的中位数。例如S2（2,4,6,8,20），则S1和S2的中位数为11。现有两个等长的升序序列A和B。设计一个时间和空间上都高效的算法，找出A和B的中位数。

算法思想1：我们很容易想到第一种算法，因为A和B都是升序的，所以设置两个指针i，j，初始时指向A和B的第一个元素，然后每次比较A[i]和B[j]，如果A[i]小，则i++，如果B[j]小，则j++，当比较到第A.length次时，此时较小的就是A和B的中位数。这种算法的时间复杂度是O(n)

算法思想2：可以利用二分法提高效率。分别求两个升序序列A和B的中位数，设为a和b，求序列A和B的中位数的过程如下：

  • 若a=b，则a或者b即为中位数，返回结果。
  • 如果a<b，则舍弃A中较小的一半，同时舍弃B中较大的一半，要求两次舍弃的长度相等。
  • 如果a>b，则舍弃A中较大的一半，同时舍弃B中较小的一半，要求两次舍弃的长度相等。

在保留两个升序序列中，重复上述三个过程，直到两个序列中均只含有一个元素位置，较小者即为所求中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int M_Search(int A[], int B, int n) {
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    while(s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] === B[m2]) {
            return A[m1]
        }
        if (A[m1] < B[m2]) {
            s1 = (s1 + d1) % 2 === 0 ? m1 : m1 + 1;
            d2 = m2;
        } else {
            d1 = m1;
            s2 = (s2 + d2) % 2 === 0 ? m2 : m2 + 1;
        }
    }
    
    return A[s1] < B[s2] ? A[s1] : B[s2];
}