一、顺序存储

  • 简单理解就是用结构体存着的数组

    1. 结构体定义

    typedef int Position;
    typedef struct LNode * PtrToLNode;
    struct LNode
    {
        ElmenetType Data[ MAXSIZE ]; // 存储数据信息
        Position Last; // 存储线性表最后一个元素的位置
    };
    typedef PtrToLNode List;

    2. 初始化空表

    List MakeEmpty()
    {
        List PtrL; // 定义线性表的头结点
        PtrL = (List )malloc(sizeof(struct LNode)); // 为整个线性表分配空间
        PtrL->Last = -1; // 此时线性表为空，最后一个元素指向-1
        return PtrL; // 返回头结点
    }

    3. 查找元素

在线性表 PtrL 中查找给定元素 X

思路： 遍历整个线性表，找到就返回 X 所在位置 i ，找不到就返回 -1

int Find(ElementType X, List PtrL)
{
    int i = 0;
    // 从第一个元素遍历到最后一个元素，若数值等于X就跳出
    while (i <= PtrL->Last && PtrL->Data[i] != X ) i ++;
    if (i > PtrL->Last ) return -1; // 线性表中没有X，返回-1
    else return i;
}

4. 插入元素

将给定元素 X 插入到线性表 PtrL 的第 i 个位置

思路： 线性表==从后往前==，把第 i 个位置到最后一个位置（也就是 Last - 1 的位置）的数全往后挪一个，目的是把第 i 个位置腾出来放新插入的元素，最后记得让Last ++

  • 关于为什么从后往前呢？ 因为从后往前挪才能保证每个元素都没有丢失，从前往后挪，前一个元素会把后一个元素的值覆盖掉
    void Insert(ElementType X, int i, List PtrL )
    {
        int j;
        if (PtrL->Last == MAXSIZE - 1) // 此时表示线性表存满，不能插入元素
        {
            cout << "FULL.";
            return;
        }
        if (i < 1 || i > PtrL->Last + 2) // 此时给定的位置 i 不合法
        {
            cout << "The location is not legal.";
            return;
        }
        for (j = PtrL->Last; j >= i - 1; j -- ) // 第i个元素其实是在数列中的第i-1啦
            PtrL->Data[j + 1] = PtrL->Data[j];
        PtrL->Data[i - 1] = X; // 挪完之后赋值
        PtrL->Last ++; // 不要忘了把线性表最后一个元素的位置也往后挪一个
        return;
    }

    5. 删除元素

    删除线性表 PtrL 中第 i 个元素

思路： 线性表==从前往后==，把从第 i + 1 个元素开始到最后一个元素全部往前挪一位，覆盖掉第 i 个位置的元素，相当于删掉了第 i 个元素

  • 为什么不从后往前挪的原因和上面那条一样
    void Delete(int i, List PtrL)
    {
        int j;
        if (i < 1 || i > PtrL->Last + 1) // 此时给定的位置 i 不合法
        {
            cout << "The location is not legal.";
            return;
        }
        for (j = i; j <= PtrL->Last; j ++ )
            PtrL->Data[j - 1] = PtrL->Data[j];
        PtrL->Last -- ; // 挪完不要忘了把最后一个元素的位置也往前挪一个
        return;
    }

    二、链式存储

  • 简单理解就是把每个数据分别存在一个方块里，然后用线（也就是指针）把这些方块串起来

    1. 结构体定义

    typedef struct LNode *List;
    struct LNode{
        ElementType Data; // 存这个方块里的数
        List Next; // 这个指针存的是下一个方块的位置
    };

    2. 求表长

    思路： 就是很简单的遍历一遍…
    int Length(List PtrL)
    {
        List p = PtrL; // p在表头位置
        int j = 0; // 表长初始化为0
        while (p) // 只要p不为NULL就继续循环
        {
            p = p->Next;
            j ++; // 表长++
        }
        return j;
    }

    3. 查找元素

    思路： 很显然就是遍历单链表

    （1）查找指定的数值 X

    List Find(ElementType X, List PtrL)
    {
        List p = PtrL; // p指向表头
        while (p != NULL && p->Data != X)
            p = p->Next;
        return p; // 找到了就会返回X所在的指针，没找到正好会返回NULL
    }

    （2）查找指定的位置 K

    List FindKth(int K, List PtrL)
    {
        List p = PtrL; // p指向表头
        int i = 1; // 表示目前正在遍历第 i 个位置
        while (p != NULL && i < K)
        {
            p = p->Next;
            i ++;
        }
        if (i == K) return p; // 找到返回该位置的指针
        else return NULL; // 找不到返回NULL
    }

    4. 插入元素

    在线性表 PtrL 中插入元素 X 到第 i 个位置

思路： 先找到要插入位置的前一个位置（也就是第 i - 1 个位置），把这个新结点的 Next 指针指向前一个结点的 Next ，然后再将前一个结点的 Next 指向这个新结点，就完成啦~

List Insert(ElementType X, int i, List PtrL)
{
    List p, s;
    if (i == 1) // 如果要在第一个位置插入
    {
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = PtrL; // 让这个新结点指向头结点就好啦
        return s; // 这个新结点变成新的头结点，返回
    }
    p = FindKth(i - 1, PtrL); // 如果不是第一个结点，先找到前一个结点，用p指向前一个结点
    if (p == NULL) // 前一个结点不存在
    {
        cout << "Illegal.";
        return NULL;
    }
    else
    {
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return PtrL;
    }
}

5. 删除元素

在线性表 PtrL 中插入第 i 个元素

思路： 找到被删除元素的前一个位置，让前一个位置的 Next 指向被删除元素的 Next ，释放掉被删除元素，完成~

List Delete(int i, List PtrL)
{
    List p, s;
    if (i == 1) // 删除的是第一个元素
    {
        s = PtrL; // s指向单链表第一个位置
        if (PtrL != NULL) PtrL = PtrL->Next; // 表不为空，就让PtrL指向下一个作为头结点
        else return NULL; // 表为空，没法删去
        free(s); // 释放s的内存
        return PtrL;
    }
    p = FindKth(i - 1, PtrL); // 找到被删除元素的前一个位置，赋为p
    if (p == NULL) // 前一个位置不存在
    {
        cout << "Illegal.";
        return NULL;
    }
    else if(p->Next == NULL) // 删除的位置不存在
    {
        cout << "Illegal.";
        return NULL; 
    }
    else
    {
        s = p->Next; // s指向被删除元素
        p->Next = s->Next;
        free(s);
        return PtrL;
    }
}

三、 顺序存储和链式存储的比较

  • 顺序存储
    • ==需要完整连续的一片空间存储==
    • 可以在 O(1) 的时间复杂度内访问查找
    • 插入删除效率低
    • 大小固定，不能随意拓展
  • 链式存储
    • 内存利用率高，==不需要连续的空间存储==
    • 查找访问效率低，需要从表头开始遍历
    • 插入删除方便
    • 大小不固定，可以随意拓展