跳转至

线性表

线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。线性表是基本且常用的一种线性结构，同时也是其他数据结构的基础，尤其单链表，是贯穿整个数据结构课程的基本技术。

线性表的定义和特点

由 \((n \ge 0)\) 个数据特性相同的元素构成的有序序列称为线性表。相邻数据元素之间存在着序偶关系。

线性表中元素的个数 \(n(n \ge 0)\) 定义为线性表的长度，\(n = 0\) 时称为空表。

对于非空的线性表或线性结构，其特点是：

  1. 存在唯一的一个被称作“第一个”的数据元素；
  2. 存在唯一的一个被称作“最后一个”的数据元素；
  3. 除第一个元素外，结构中的每个数据元素均只有一个前驱；
  4. 除最后一个元素外，结构中的每个数据元素均只有一个后继；

案例引入

  • 一元多项式的运算
  • 稀疏多项式的运算
  • 图书管理系统

线性表的顺序表示和实现

线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也成称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。线性表的顺序存储结构是一种随机存取的存储结构。

线性表中基本操作的实现

  1. 取值。时间复杂度为\(O(1)\)
  2. 查找。平均查找长度（Average Search Length, ASL）。\(ASL = \sum_{i=1}^{n}p_{i}C_{i}\)
  3. 插入。\(E_{ins}\)为在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）。\(E_{ins}=\sum_{i=1}^{n+1}p_{i}(n-i+1)\)。由此平均时间复杂度为\(O(n)\)
  4. 删除。\(E_{del}\)为在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）。\(E_{del}=\sum_{i=1}^{n}p_{i}(n-i)\)。由此平均时间复杂度为\(O(n)\)

算法示例

  • 定义部分 

    /* 状态 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2

/* 最大值 */
#define MAXSIZE 1000

typedef int Status;
typedef int ElemType;

/* 本例中i值的合法范围在 1 <= i <= n + 1 */

/* 顺序表 */
typedef struct
{
    ElemType* elem;
    int length;
} SqList;

  • 顺序表的初始化 

    /* 构造一个空的顺序表 */
Status InitList(SqList* L)
{

    L->elem = malloc(sizeof(ElemType) * MAXSIZE);
    if (L->elem == NULL)
    {
        return OVERFLOW;
    }
    L->length = 0;
    return OK;
}

  • 顺序表的取值 

    /* 取第i个元素 */
Status GetElem(SqList* L, int i, ElemType* e)
{
    if (i < 1 || i > L->length)
    {
        return ERROR;
    }
    *e = L->elem[i - 1];
    return OK;
}

  • 顺序表的查找 

    /* 查找。成功返回i，不成功返回0 */
int LocateElem(SqList* L, ElemType e)
{
    int i = 0;
    for (i = 0; i < L->length; i += 1)
    {
        if (L->elem[i] == e)
        {
            return i + 1;
        }
    }
    return 0;
}

  • 顺序表的插入 

    /* 插入。在第i个位置插入元素。*/
Status ListInsert(SqList* L, int i, ElemType e)
{
    int j = 0;

    if (i < 1 || i > L->length + 1)
    {
        return ERROR;
    }
    if (L->length == MAXSIZE)
    {
        return ERROR;
    }

    for (int j = L->length - 1; j >= i - 1; j -= 1)
    {
        L->elem[j + 1] = L->elem[j];
    }
    L->elem[i - 1] = e;
    L->length += 1;

    return OK;
}

  • 顺序表的删除 

    /* 删除。删除顺序表中第i个元素。*/
Status ListDelete(SqList* L, int i)
{
    int j = 0;

    if (i < 1 || i > L->length)
    {
        return ERROR;
    }

    for (j = i; j < L->length; j += 1)
    {
        L->elem[j - 1] = L->elem[j];
    }
    L->length -= 1;

    return OK;
}

线性表的链式表示和实现

单链表的定义和表示

线性表的链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 \(a_{i}\) 与其直接后继数据元素 \(a_{i + 1}\) 之间的逻辑关系，对数据元素 \(a_{i}\) 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成的数据元素 \(a_{i}\) 的存储映像，称为结点（node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点（\(a_{i}（1 \le i \le n）\)的存储映像）链结成一个链表，即为线性表的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。

一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。

  • 首元结点。首元结点是指链表中存储第一个数据元素 \(a_{i}\) 的结点。
  • 头结点。头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据与可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数类型时，头结点的数据域中可以存放该线性表的长度。
  • 头指针。头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头结点所指结点为该线性表的首元结点。

单链表基本操作的实现

算法示例

  • 定义部分 

    /* 状态 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

/* 本例中i值的合法范围在 1 <= i <= n + 1 */

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

  • 单链表的初始化 

    /* 构造一个带头节点的空的单链表L，L就是当前单链表的头节点 */
Status InitList(LinkList* L)
{
    (*L) = malloc(sizeof(LNode));
    if ((*L) == NULL)
    {
        return ERROR;
    }
    (*L)->next = NULL;
    return OK;
}

  • 单链表的取值 

    /* 取第i个元素 */
Status GetElem(LinkList L, int i, ElemType* e)
{
    LinkList p = L->next;
    int j = 1;

    while (p != NULL && j < i)
    {
        p = p->next;
        j += 1;
    }

    if (p == NULL || j > i)
    {
        return ERROR;
    }
    *e = p->data;
    return OK;
}

  • 单链表的按值查找 

    /* 查找。成功返回e结点地址，不成功返回NULL */
LNode* LocateElem(LinkList L, ElemType e)
{
    LinkList p = L->next;
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}

  • 单链表的插入 

    /* 插入。在带头节点的单链表L中第i个位置插入值为e的新结点。*/
Status ListInsert(LinkList L, int i, ElemType e)
{
    LinkList p = L; // 当前指向头节点
    int j = 0; // 所以是第0个位置

    // 在i-1的后面进行插入
    while (p != NULL && j < i - 1) // i - 1为循环到带插入位置的前一个位置
    {
        p = p->next;
        j += 1;
    }

    if (p == NULL || j > i - 1)
    {
        return ERROR;
    }

    LNode* q = malloc(sizeof(LNode));
    if (q == NULL)
    {
        return ERROR;
    }
    q->data = e;
    q->next = p->next;
    p->next = q;

    return OK;
}

  • 单链表的删除 

    /* 删除。删除顺序表中第i个元素。*/
Status ListDelete(LinkList L, int i)
{
    LinkList p = L;
    int j = 0;

    // 删除i-1后面的结点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j += 1;
    }
    if (p->next == NULL || j > i - 1)
    {
        return ERROR;
    }
    LinkList q = p->next;
    p->next = q->next;
    free(q);
    return OK;
}

  • 前插法创建单链表（一次性创建n个结点） 

    /* 前插法创建单链表 带头结点 */
Status CreateList_H(LinkList* L, int n)
{
    int i = 0;

    (*L) = malloc(sizeof(LNode));
    if ((*L) == NULL)
    {
        return ERROR;
    }
    (*L)->next = NULL;

    LinkList head = *L;
    for (i = 0; i < n; i += 1)
    {
        LinkList p = malloc(sizeof(LNode));
        if (p == NULL)
        {
            return ERROR;
        }
        printf("请输入元素: ");
        scanf("%d", &(p->data));
        p->next = head->next;
        head->next = p;
    }
    return OK;
}

  • 后插法创建单链表（一次性创建n个结点） 

    /* 后插法创建单链表 带头结点 */
Status CreateList_R(LinkList* L, int n)
{
    int i = 0;

    (*L) = malloc(sizeof(LNode));
    if ((*L) == NULL)
    {
        return ERROR;
    }
    (*L)->next = NULL;

    LinkList p = *L;
    for (i = 0; i < n; i += 1)
    {
        LinkList q = malloc(sizeof(LNode));
        if (q == NULL)
        {
            return ERROR;
        }
        printf("请输入元素: ");
        scanf("%d", &(q->data));
        q->next = NULL;
        p->next = q;
        p = q;
    }

    return OK;
}

循环链表

循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

在单链表中，判断终止条件为 p != NULL 或 p->next != NULL ，而循环单链表的判断条件为 p != L 或 p->next != L 。

某些情况下，若在循环链表中设立尾指针而不设头指针，可使一些操作简化。例如，两个线性表合并成一个表。

双向链表

对于单链表，如果要寻找结点的直接前驱，则必须从表头指针出发。为克服单链表这种单向性的缺点，可以利用双向链表（Double Linked List）。在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

算法示例

  • 定义部分 

    /* 状态 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

/* 本例中i值的合法范围在 1 <= i <= n + 1 */

/* 单链表结构 */
typedef struct DuLNode
{
    ElemType data;
    struct DuLNode* prior;
    struct DuLNode* next;
} DuLNode, *DuLinkList;

/* 获取双向链表的第i个结点的地址 */
DuLinkList GetElem_DuL(DuLinkList L, int i)
{
    DuLinkList p = L;
    int j = 0;

    while (p != NULL && j < i)
    {
        p = p->next;
        j += 1;
    }

    if (p == NULL || j > i)
    {
        return NULL;
    }
    return p;
}

  • 双向链表的插入 

    /* 在双向链表的第i个位置插入结点，i结点必须存在 */
Status ListInsert_DuL(DuLinkList L, int i, ElemType e)
{
    DuLinkList p = NULL, q = NULL;
    p = GetElem_DuL(L, i);
    if (p == NULL)
    {
        return ERROR;
    }

    q = malloc(sizeof(DuLNode));
    if (q == NULL)
    {
        return ERROR;
    }

    q->prior = p->prior;
    p->prior->next = q;

    q->next = p;
    p->prior = q;

    q->data = e;
    return OK;
}

  • 双向链表的删除 

    /* 删除双向链表的第i个位置的结点，i位置必须存在 */
Status ListDelete_DuL(DuLinkList L, int i)
{
    DuLinkList p = GetElem_DuL(L, i);
    if (p == NULL)
    {
        return ERROR;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}

顺序表和链表的比较

空间性能比较

时间性能比较

线性表的应用

算法示例

  • 线性表的合并

例：求解一般集合的并集问题。

已知两个集合 \(A\) 和 \(B\) ，现要求一个新的集合 \(A = A \cup B\) 。例如，设 $$ A = (7, 5, 3, 11) \newline B = (2, 6, 3) $$ 合并后 $$ A = (7, 5, 3, 11, 2, 6) $$

示例代码：顺序表合并 

/* 将所有在线性表LB中但不在线性表LA中的元素插入到LA中 */
void MergeList(SqList* LA, SqList* LB)
{
    int m = LA->length;
    int n = LB->length;
    int i = 0;
    ElemType e;

    for (i = 1; i <= n; i += 1)
    {
        GetElem(LB, i, &e);
        if (LocateElem(LA, e) == 0)
        {
            m += 1;
            ListInsert(LA, m, e);
        }
    }
    return;
}

  • 有序表的合并

若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表（Ordered List）。

例：求解有序集合的并集问题。

有序集合是指集合中的元素有序排列。已知两个有序集合 \(A\) 和 \(B\) ，数据元素按指非递减有序排列，现要求一个新的集合 $ C = A \cup B$ ，使集合 \(C\) 中的数据元素任按值非递减有序排列。

例如，设 $$ A = (3, 5, 8, 11) \newline B = (2, 6, 8, 9, 11, 15, 20) $$ 则 $$ C = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) $$

  1. 顺序有序表的合并 

    /* 已知顺序有序表LA和LB的元素按值非递减排列 */
/* 归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列 */
void MergeList_Sq(SqList* LA, SqList* LB, SqList* LC)
{
    int m = LA->length;
    int n = LB->length;

    int* pa = LA->elem;
    int* pb = LB->elem;
    int* pc = LC->elem;

    int i = 1, j = 1;

    LC->length = m + n;

    while (i <= m || j <= n)
    {
        if (i > m)
        {
            *pc++ = *pb++;
            j += 1;
        }
        else if (j > n)
        {
            *pc++ = *pa++;
            i += 1;
        }
        else if (*pa <= *pb)
        {
            *pc++ = *pa++;
            i += 1;
        }
        else
        {
            *pc++ = *pb++;
            j += 1;
        }
    }

    return;
}

  2. 链式有序表的合并 

    /* 已知单链表LA和LB的元素按值非递减排列 */
/* 归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列 */
/* 合并后LA，LB链表引用为NULL。LC为合并后单链表 */
void MeargList_L(LinkList* LA, LinkList* LB, LinkList* LC)
{
    LinkList pa = (*LA)->next, pb = (*LB)->next;
    LinkList pc = *LC;

    *LA = NULL;
    *LB = NULL;

    while (pa != NULL && pb != NULL)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pb = pb->next;
        }
        pc = pc->next;
    }

    pc->next = pa == NULL ? pb : pa;

    return;
}

案例分析与实现

算法示例

  • 稀疏多项式的运算 - 多项式的创建 

    typedef struct PNode
{
    float coef; // 系数
    int expn; // 指数
    struct PNode* next; // 指针域
} PNode, *Polynomial;

/* 输入n项的系数和指数，建立表示多项式的有序链表P（带头结点） */
void CreatePolyn(Polynomial* P, int n)
{
    int i = 0;
    Polynomial node = NULL;
    Polynomial p = NULL, q = NULL;
    Polynomial pre = NULL;

    *P = malloc(sizeof(PNode));
    (*P)->next = NULL;
    p = *P;

    for (i = 1; i <= n; i++)
    {
        node = malloc(sizeof(PNode));
        printf("请输入系数和指数，用空格隔开：");
        scanf("%f %d", &(node->coef), &(node->expn));

        pre = p;
        q = pre->next;
        while (q != NULL && q->expn < node->expn)
        {
            pre = q;
            q = q->next;
        }

        if (q != NULL && q->expn == node->expn)
        {
            q->coef += node->coef;
            free(node);
        }
        else
        {
            pre->next = node;
            node->next = q;
        }
    }
    return;
}

  • 稀疏多项式的运算 - 多项式的相加 

    /* 合并后pb应该释放，但是本例未详细处理 */
/* pa += pb */
void AddPolyn(Polynomial Pa, Polynomial Pb)
{
    Polynomial pa = Pa->next, pb = Pb->next;
    Polynomial pre = pa;
    Polynomial node = NULL;

    while (pa != NULL && pb != NULL)
    {
        if (pa->expn == pb->expn)
        {
            pa->coef += pb->coef;
            node = pb;
            pre = pa;
            pa = pa->next;
            pb = pb->next;
            free(node);
        }
        else if (pa->expn < pb->expn)
        {
            pre = pa;
            pa = pa->next;
        }
        else if (pa->expn > pb->expn)
        {
            node = pb;
            pb = pb->next;
            pre->next = node;
            node->next = pa;
        }
    }

    if (pa == NULL && pb != NULL)
    {
        pre->next = pb;
    }

    return;
}