线性表 | DS

定义和基本操作

• 线性表

  具有相同数据类型的 $n$ 个数据元素的有限序列（$n \geq 0$）

  空表：表长 $n$ 为 0

• 线性表逻辑特性

  只有一个表头元素

  只有一个表尾元素

  表头无前驱、表尾无后继

  除表头表尾，每个元素只有一个直接前驱和一个直接后继

• 线性表特点

  表中元素的个数有限

  表中元素具有逻辑上的顺序性，在序列中各个元素有其先后次序

  表中元素都是数据元素。每个元素都是单个元素

  表中元素的数据类型都相同，这意味着每个元素都占有相同大小的存储空间

  表中元素具有抽象性。即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容

• 线性表基本操作

  初始化、求表长、判空、插入、删除、按值查找、按位查找、打印、销毁

存储结构

顺序表示

• 顺序表

  线性表的顺序存储

• 顺序表特点

  1）表中元素的逻辑顺序与其物理顺序相同

  2）随机访问

  每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数

  通过首地址和元素序号可在时间 O(1) 内找到指定的元素

  通常用高级程序设计语言中的数组来描述线性表的顺序存储结构

  线性表中元素的位序从 1 开始，数组中元素下标从 0 开始

  3）存储空间连续，分配只能预先进行

  4）存储密度高，每个结点只存储数据元素

链式表示

• 单链表/线性链表

  $n$ 个结点链结成一个链表，即为线性表的链式存储结构

  由于此链表中的每个结点只包含一个指针域，故又称线性链表或单链表

• 单链表特点

  1）非随机存取

  2）元素离散地分布在存储空间

  3）存储空间利用率稍低

• 开始结点：存储有第一个数据元素的结点

  头结点：数据域可以不存储信息，也可存储一些描述链表属性的信息；指针域存储指向开始结点的指针

  第一个结点：头结点/开始结点

  头指针：指向第一个结点，通常用作链表的标识

• 头结点的引入，方便了运算的实现：

  1）对第一个元素的操作和对其他位置上元素的操作一致，无需特殊处理，算法统一

  2）空表和非空表的处理也得到统一（无论链表是否为空，其头指针都是指向头结点的非空指针）

  表长不计头结点

• 双链表

  可以很方便地找到其前驱结点，因此插入删除的时间复杂度仅为 O(1)（单链表插入删除操作时间复杂度为 O(n) 时是因为花了 O(n) 去找前驱结点了）

  插入结点的语句顺序注意下，不要着急把 p->next 改了

• 循环单链表

  有时不设头指针而仅设尾指针，这样对在表头和表尾插入元素都只需要 O(1) 的时间复杂度。但删除尾结点依然麻烦，因为还是需要遍历找到尾结点的前驱结点

  所以对于经常删除尾结点的线性表，直接排除（循环）单链表和不带尾结点指针的非循环双链表

  循环单链表和单链表所占内存空间相同

  判空：头结点的 next 指针是否等于头指针

• 循环双链表

  判空：头结点的 prior 和 next 指针是否都等于头指针

• 静态链表

  借助数组来描述线性表的链式存储结构

  实质是一维结构体数组，结点也有数据域 data 和指针域 next。这里的指针是结点的相对地址（数组下标），又称游标

  静态链表也要预先分配一块连续的内存空间

代码实现

单链表

/* 单链表结点 */
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

/**
 * 尾插法建立单链表
 * @param liList 单链表
 * @param arr    存放元素值的数组
 * @param num    元素个数
 * T(n)=O(n)
 */
void createListT (LinkList &liList, int arr[], int num) {
    // 初始化链表,设置头结点
    liList = (LNode*)malloc(sizeof(LNode));
    liList->next = NULL;

    // s用来接纳新结点,r用来跟踪链表尾结点
    LNode *s, *r;
    r = liList;

    // 尾插操作
    for (int i = 0; i < num; ++i) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = arr[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;  // 尾结点指针置空
}

/**
 * 头插法建立单链表
 * @param liList 待建单链表
 * @param arr    存放元素值的数组
 * @param num    元素个数
 * T(n)=O(n)
 */
void createListH(LinkList &liList, int arr[], int num) {
    // 初始化链表,设置头结点
    liList = (LNode*)malloc(sizeof(LNode));
    liList->next = NULL;

    // s用来接纳新结点
    LNode *s;

    // 头插操作
    for (int i = 0; i < num; ++i) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = arr[i];
        s->next = liList->next;
        liList->next = s;
    }
}

/**
 * 按位序查找结点
 * T(n)=O(n)
 */
LNode *getElemBySeq(LinkList liList, int seq) {
    // 位序校验
    if (seq < 0) return NULL;

    LNode *p = liList;
    while (seq-- > 0 && p != NULL) {
        p = p->next;
    }
    return p;  // 若seq大于表长则返回NULL
}

/**
 * 按值查找结点
 * 返回数据域等于给定值val的第一个结点(的指针)
 * T(n)=O(n)
 */
LNode *getElemByVal(LinkList liList, ElemType val) {
    LNode *p = liList->next;
    while (p != NULL && p->data != val) {
        p = p->next;
    }
    return p;  // 找不到则返回NULL
}

/**
 * 后插(在结点p后插入新结点s)
 * T(n)=O(1)
 */
void insertBehind(LNode *p, LNode *s) {
    s->next = p->next;
    p->next = s;
}

/**
 * 在指定位序seq插入新结点s
 * T(n)=O(n)
 */
void insertBySeq(LinkList liList, int seq, LNode *s) {
    // 位序校验
    if (seq < 1) return;

    // 后插到第i-1个结点的后面
    insertBehind(getElemBySeq(liList, seq-1), s);
}

/**
 * 前插1(在给定结点p前插入新结点s)
 * T(n)=O(n)
 */
void insertFront1(LNode *p, LNode *s, LinkList liList) {
    // 转化为后插:插到p的前驱结点的后面
    LNode *q = liList;
    while (q->next != p) {
        q = q->next;
    }
    insertBehind(q, s);
}

/**
 * 前插2(在给定结点p前插入新结点s)
 * T(n)=O(1)
 */
void insertFront2(LNode *p, LNode *s) {
    // 伪前插真后插:后插,然后数据域交换
    insertBehind(p, s);
    ElemType tmp = p->data;
    p->data = s->data;
    s->data = tmp;
}

/**
 * 根据前驱结点删除结点(即删除后继结点)
 * T(n)=O(1)
 */
void delLNodeByPre(LNode *pre) {
    LNode *q = pre->next;
    pre->next = pre->next->next;
    free(q);
}

/**
 * 按位序删除结点
 * T(n)=O(n)
 */
void delLNodeBySeq(LinkList liList, int seq) {
    // 位序校验
    if (seq < 1) return;

    // 根据前驱结点进行删除操作
    delLNodeByPre(getElemBySeq(liList, seq-1));
}

/**
 * 根据后继结点删除结点
 * @param p 要删除的结点
 * T(n)=O(1)
 */
void delLNodeByNext(LNode *p) {
    // 不能用于删除尾结点
    if (p->next == NULL) return;

    // 将后继结点的数据域赋予其自身,然后删除后继结点
    p->data = p->next->data;
    delLNodeByPre(p);
}

/**
 * 求表长(带头结点)
 * T(n)=O(n)
 */
int getLiListLen(LinkList liList) {
    LNode *p = liList->next;
    int len = 0;
    while (p != NULL) {
        ++len;
        p = p->next;
    }
    return len;
}

/**
 * 两个非递减单链表A、B归并为一个非递减单链表C
 */
void mergeLiList1(LinkList A, LinkList B, LinkList &C) {
    // 设置指针跟踪A、B当前的最小值结点
    LNode *p = A->next;
    LNode *q = B->next;

    // 初始化C
    C = A;  // 用A的头结点做C的头结点
    C->next = NULL;

    LNode *r = C;  // 设置指针r跟踪C尾结点
    free(B);  // B的头结点没用了

    // 归并操作
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            r->next = p;
            p = p->next;
        } else {
            r->next = q;
            q = q->next;
        }
        r = r->next;
    }
    
    // 收尾工作
    r->next = NULL;
    if (p != NULL) r->next = p;
    if (q != NULL) r->next = q;
}

/**
 * 两个非递减单链表A、B归并为一个非递增单链表C
 */
void mergeLiList2(LinkList A, LinkList B, LinkList &C) {
    LNode *p = A->next;
    LNode *q = B->next;
    C = A;
    C->next = NULL;
    free(B);

    // 归并操作
    LNode *s;  // 指向要头插的结点
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            s = p;
            p = p->next;
        } else {
            s = q;
            q = q->next;            
        }
        // 头插
        insertBehind(C, s);
    }

    // 收尾工作
    while (p != NULL) {
        s = p;
        p = p->next;
        // 头插
        insertBehind(C, s);
    }
    while (q != NULL) {
        s = q;
        q = q->next;
        // 头插
        insertBehind(C, s);
    }
}

双链表

/* 双链表结点 */
typedef struct DLNode {
    ElemType data;
    struct DLNode *prior, *next;
} DLNode, *DLinkList;

/**
 * 尾插建表
 * @param L 待建双链表
 * @param a 存放元素值的数组
 * @param n 元素个数
 */
void createDlistT(DLinkList &L, int a[], int n) {
    // 初始化双链表,设置头结点
    L = (DLNode*)malloc(sizeof(DLNode));
    L->prior = NULL;
    L->next = NULL;

    DLNode *s;  // 接纳新结点
    r = L;  // 跟踪尾结点

    for (int i = 0; i < n; ++i) {
        s = (DLNode*)malloc(sizeof(DLNode));
        s->data = a[i];
        r->next = s;
        s->prior = r;
        r = s;
    }
    r->next = NULL;
}

/**
 * 后插(s插到p后)
 */
void insertBehindD(DLNode *p, DLNode *s) {
    s->next = p->next;
    s->prior = p;
    p->next = s;
    if (s->next != NULL) s->next->prior = s;
}

/**
 * 删除p的后继
 */
void delDLNode(DLNode *p) {
    DLNode *q = p->next;
    p->next = q->next;
    if (q->next != NULL) q->next->prior = p;
    free(q);
}

静态链表

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

// 静态链表以next==-1作为其结束的标志