线性表的概念

线性结构

线性结构的特点：

  • 存在唯一一个被称为第一个的元素
  • 存在唯一一个被称为最后一个的元素
  • 除第一个之外，集合中的每个数据元素均只有一个前驱
  • 除最后一个之外，集合中每个数据元素均只有一个后继

线性表是n个数据元素的有限序列，相邻数据元素之间存在序偶关系。

抽象数据类型：线性表

  1. ADT List{
  2.     数据对象: D = {ai|ai∈ElemSet, i = 1, 2, ..., n, n≥0}
  3.     数据关系:R1 = {<a_{i-1}, ai> |a_{i-1},ai∈D, i = 2, ..., n}
  4.     基本操作:
  5.         InitList(&L)
  6.             操作结果:构造一个空的线性表L
  8.         DestroyList(&L)
  9.             初始条件:线性表L已存在
  10.             操作结果:销毁线性表L
  12.         ClearList(&L)
  13.             初始条件:线性表L已存在
  14.             操作结果:将L重置为空表
  16.         ListEmpty(L)
  17.             初始条件:线性表L已存在
  18.             操作结果:若L为空表返回TRUE,非空返回FALSE
  20.         ListLength(L)
  21.             初始条件:线性表L已存在
  22.             操作结果:返回L中数据元素个数
  24.         GetElem(L, i, &e)
  25.             初始条件:线性表L已存在,1≤i≤ListLength(L)
  26.             操作结果:用e返回L中第i个数据元素的值
  28.         LocateElem(L, e, compare())
  29.             初始条件:线性表L已存在,compare()是数据元素判定函数
  30.             操作结果:返回L中第1个与e满足compare()函数的数据元素的位序,若这样的数据元素不存在则返回值为0
  32.         PriorElem(L, cur_e, &pre_e)
  33.             初始条件:线性表L已存在
  34.             操作结果:若cur_e是L的数据元素且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义
  36.         NextElem(L, cur_e, &next_e)
  37.             初始条件:线性表L已存在
  38.             操作结果:若cur_e是L的数据元素且不是最后一个,则用next_e返回它的前驱,否则操作失败,next_e无定义
  40.         ListInsert(&L, i, e)
  41.             初始条件:线性表L已存在,1≤i≤ListLength(L)
  42.             操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
  44.         ListDelete(&L, i, &e)
  45.             初始条件:线性表L已存在且非空,1≤i≤ListLength(L)
  46.             操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
  48.         ListTraverse(L, visit())
  49.             初始条件:线性表L已存在
  50.             操作结果:依次对L的每个数据元素调用函数visit(),visit()失败则操作失败
  51. }ADT List

线性表清空和销毁的区别

  • 销毁类似格式化，释放空间，破坏原有数据，销毁完就彻底弃用，再想使用只能创建一个新线性表
  • 清空类似快速格式化，标记空间里的值被清空（但实际上还存在，只是我们认为值没了），清空完还可以接着用该线性表，写入新的值时直接覆盖原有的值

合并两个线性表LA和LB


扩大线性表A，遍历线性表LB中的每个元素，对每个元素遍历线性表LA查找，若不存在则插入之，时间复杂度O(nm)

伪代码：

  1. def UnionList(List &LA, List LB):
  2.     for i in range(0, LB.length):
  3.         GetElem(LB, i, e)
  4.         if !LocateElem(LA, e, equal):
  5.             ListInsert(LA, ++ LA.length, e)

归并两个非递减线性表LA，LB为新的非递减线性表LC


设双指针i，j分别指向LA，LB中的元素a，b，当前应插入到LC中的元素c为

笔记二：线性表 - 图1

遍历双指针，其中一个指针遍历完后，将另一个线性表余下的所有元素插入LC，时间复杂度O(n+m)

伪代码：

def MergeList(List LA, List LB, List &LC):
    InitList(LC)
    i = j = k = 0
    while i <= LA.length and j <= LB.length:
        GetElem(LA, i, ai)
        GetElem(LB, i, ai)
        if ai <= bi:
            ListInsert(LC, ++ k, ai)
            i ++
        else:
            ListInsert(LC, ++ k, bj)
            j ++
        while i <= LA.length:
            GetElem(LA, i ++, ai)
            ListInsert(LC, ++ k, ai)
        while j <= LB.length
            GetElem(LB, j ++, bj)
            ListInsert(LC, ++ k, bj)