Skip to content

Latest commit

 

History

History
249 lines (179 loc) · 5.48 KB

2.3.6 顺序表和链表的比较.md

File metadata and controls

249 lines (179 loc) · 5.48 KB
Raw

2.3.6 顺序表和链表的比较


  学习完顺序表和链表，那我们在日后的实际算法选择中，到底如何去做选择呢？

  我们从四个方式来对顺序表和链表作比较。分别是：① 存取方式、② 逻辑结构和物理结构、③ 基本操作、④ 内存空间。

  1. 存取方式

    • 顺序表：可以实现顺序存取和随机存取

    • 单链表：只能实现顺序存取

  2. 逻辑结构和物理结构

    • 顺序表：逻辑相邻物理上也相邻，通过相邻表示逻辑关系

    • 单链表：逻辑相邻物理上不一定相邻，通过指针表示逻辑关系

  3. 基本操作（时间复杂度）

    • 插入 & 删除

      • 顺序表：O(n)，且需要大量移动元素

      • 单链表：O(1)（结点指针已知）；O(n)（结点指针未知）

    • 按值查找

      • 顺序表：O(n)，遍历查找

      • 单链表：O(n)，遍历查找

    • 按序号查找

      • 顺序表：O(1)，直接得到内存地址

      • 单链表：O(n)，遍历层层查找

  4. 内存空间

    • 顺序存储：无论静态分配还是非静态（动态）分配都需要预先分配合适的内存空间

      • 静态分配时预分配空间太大会造成浪费，太小会造成溢出

      • 动态分配时虽不会溢出但是扩充空间需要大量移动元素，操作效率低

    • 链式存储：在需要时分配结点空间即可，高效方便，但每个结点指针都需要额外的空间

  • 那在不同的情况下，顺序表和单链表我们如何去做选择？

    顺序表 单链表
    规模难估计 √
    存储密度 √
    按序号访问 √
    插入和删除 √
    基于数组 √
    基于指针 √

  我们在顺序表与链表的三个常用操作中去实现其具体的算法。分别是：求最值、逆置、归并。

  • 求最值及逆置——数据：

    L = (3, 1, 5, 9, 2)

  • 求最值

    • 顺序表：

      int min = L[0];
int max = L[0];
for(int i=0; i<n; i++) {
    if(min > L[i])
        min = L[i];
    if(max < L[i])
        max = L[i];
}

      时间复杂度：O(n)

    • 单链表（含头结点，不特殊说明均含头结点）：

      int min = p->next->data;
int max = p->next->data;

for(; p!=NULL; p=p->next) {
    if(min > p->data)
        min = p->data;
    if(max < p->data)
        max = p->data;
}

/*
// while 实现
while(p != NULL) {
    if(min > p->data)
        min = p->data;
    if(max < p->data)
        max = p->data;
    p = p->next;
}
*/

      时间复杂度：O(n)

  • 逆置

    • 顺序表：

      int i = 0;
int j = n-1;
while(i < j) {
    int temp = L[i];
    L[i] = L[j];
    L[j] = temp;
}

      时间复杂度：O(n)

    • 单链表：

      // 找到尾结点指针 r
LNode *r;
while(r->next) {
    r = r->next;
}

// 将头结点后每次第一个结点放到尾结点
LNode *p;
while(p->next != r) {
    int *temp = p->next;
    p->next = temp->next;
    temp->next = r->next;
    r->next = temp;
}

      时间复杂度：O(n)

  • 归并

    • 输入：

      L1=(1, 2, 3, 5) 、 L2=(4, 6, 7, 8)

    • 输出：

      L=(1, 2, 3, 4, 5, 6, 7, 8)

    • 顺序表：

      int i=0, j=0;   // L1 和 L2 数组下标
int k=0;        // 新生成数组下标
for(; i<L1_Length && j<L2_Length; k++) {
    if(L1[i] < L2[j])
        L[k] = L1[i++];
    else
        L[k] = L2[j++];
}
while(i < L1_Length)
    L[k++] = L1[i++];
while(i < L2_Length)
    L[k++] = L1[j++];

      时间复杂度：O(n)，这里的 n 是指两个数组的元素个数之和

    • 单链表：

      // L 头结点为 r
while(p->next != NULL && q->next != NULL) {
    if(p->next->data < q->next->data) {
        r->next = p->next;
        p->next = p->next->next;
    }
    else {
        r->next = q->next;
        q->next = q->next->next;
    }
    r = r->next;
}
if(p->next != NULL)
    r->next = p->next;
if(q->next != NULL)
    r->next = q->next;
free(p);
free(q);

      时间复杂度：O(n)，这里的 n 是指两个链表的元素个数之和


💡 题型

  xxx

单项选择题

  1. xxxx（ ）

    A. xxx
    B. XX
    C. Xx
    D. xX

    查看解析

    答案：x

-- 完 --