Skip to content

Latest commit

 

History

History
205 lines (168 loc) · 3.99 KB

README.md

File metadata and controls

205 lines (168 loc) · 3.99 KB

顺序表

顺序表：用顺序存储方式实现的线性表。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

  • $LOC(L)$
  • $LOC(L)+sizeof(ElemType)$
  • $LOC(L)+2*sizeof(ElemType)$
  • $...$

1. 静态分配

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];
    int length;
} SqList;
void InitList(SqList &L)
{
    // for (int i = 0; i < MaxSize; i++)
    // {
    //     L.data[i] = 0;
    // }
    L.length = 0;
}

$MaxSize*sizeof(ElemType)$

  • 使用“静态数组”实现
  • 大小一旦确定就无法改变

2. 动态分配

#define InitSize 10
typedef struct
{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;
void InitList(SeqList &L)
{
    // 用 malloc 函数申请一篇连续的存储空间
    L.data = (int *)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}
void IncreaseSize(SeqList &L, int len)
{
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++)
    {
        L.data[i] = p[i]; // 时间复杂度高
    }
    L.MaxSize += len;
    free(p);
}
  • malloc：动态申请一整片连续的内存空间
  • free：释放内存空间
L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize)

C++ 可以使用 new，delete 关键字。

  • 使用“动态数组”实现
  • L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize)
  • 顺序表存满时，可再用 malloc 动态扩展顺序表的最大容量
  • 需要将数据元素复制到新的存储区域，并用 free 函数释放原区域

3. 顺序表的特点

  • 随机访问：即可以在 $O(1)$ 时间内找到第 $i$ 个元素。
  • 存储密度高：每个结点只存储数据元素。
  • 扩展容量不方便：静态分配不能扩展容量，动态分配可以扩展但时间复杂度高。
  • 插入、删除元素操作不方便，需要移动大量元素。

4. 插入操作

$$ L=(\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5) $$

$$ [a_0,a_1,a_2,a_3,a_4] $$

bool ListInsert(SqList &L, int i, int e)
{
    // i 的值必须是合法的位序
    if (i < 1 || i > L.length + 1)
    {
        return false;
    }
    // 如果存储空间已满，则不能插入
    if (L.length >= MaxSize)
    {
        return false;
    }
    // 插入操作
    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

插入位置之后的元素都要后移。

  • 最好时间复杂度：$O(1)$
  • 最坏时间复杂度：$O(n)$
  • 平均时间复杂度：$O(n)$

5. 删除操作

bool ListDelete(SqList &L, int i, int &e)
{
    // i 的值必须是合法的位序
    if (i < 1 || i > L.length)
    {
        return false;
    }
    // 删除操作
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

删除位置之后的元素都要前移。

  • 最好时间复杂度：$O(1)$
  • 最坏时间复杂度：$O(n)$
  • 平均时间复杂度：$O(n)$

代码要点：

  • 代码中注意位序 $i$ 与数组下标的区别。
  • 算法要有健壮性，注意判断 $i$ 的合法性。
  • 移动元素时，从靠前的元素开始？还是从表尾元素开始？
  • 分析代码，理解为什么有的参数需要加 &（C++ 语法中的引用）。

6. 按位查找

int GetElem(SqList L, int i)
{
    // i 的值必须是合法的位序
    if (i < 1 || i > L.length)
    {
        return false;
    }
    return L.data[i - 1];
}
  • 时间复杂度：$O(1)$

7. 按值查找

int LocateElem(SqList L, int e)
{
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
        {
            return i + 1;
        }
    }
    return 0;
}
  • 最好时间复杂度：$O(1)$
  • 最坏时间复杂度：$O(n)$
  • 平均时间复杂度：$O(n)$