数据结构 | 第2章 线性表

内容纲要

@[toc]

线性表的类型定义

线性表是n个数据元素的有限序列。
线性表的长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,还可进行插入和删除等。

抽象数据类型线性表定义

ADT List {
        数据对象:...
        数据关系:...
        基本操作:
                InitList(&L)        // 初始化
                        操作结果:构造一个空的线性表L
                DestroyList(&L)     // 结构销毁
                        初始条件:线性表L已存在
                        操作结果:销毁线性表L
                ClearList(&L)       // 线性表置定
                        初始条件:线性表L已存在
                        操作结果:将L重置位空表
                ListEmpty(L)        // 引用
                        初始条件:线性表L已存在
                        操作结果:若L为空表,则返回true,否则返回false
                ListLength(L)
                        初始条件:线性表L已存在
                        操作结果:返回L中数据元素个数
                GetElem(L, i, &e)
                        初始条件:线性表L已存在,1 <= i <= ListLength(L)
                        操作结果:用e返回L中第i个数据元素的值
                LocateElem(L, e, compare())     // 定位函数
                        初始条件:线性表L已存在,compare()是数据元素判定函数,e为给定值
                        操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在,则返回值为0
                PriorElem(L, cur_e, &pre_e)     // 引用
                        初始条件:线性表L已存在
                        操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回其前驱,否则操作失败,pre_e无定义
                NextElem(L, cur_e, &next_e)
                        初始条件:线性表L已存在
                        操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义
                ListInsert(&L, i, e)        // 插入数据元素
                        初始条件:线性表L已存在,1 <= i <= ListLength(L) + 1
                        操作结果:在L中第i个元素之前插入新的数据元素e,L的长度加1
                ListDelete(&L, i, &e)       // 删除数据元素
                        初始条件:线性表L已存在且非空,1 <= i <= ListLength(L)
                        操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
                PutElem(&L, i, &e)      // 改变数据元素的值
                        初始条件:线性表L已存在
                ListTraverse(L, visit())        // 遍历线性表
                        初始条件:线性表L已存在
                        操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()失败,则操作失败
} ADT List
// 算法2.1 时间复杂度为O(ListLength(La) * ListLength(Lb))
void union(List &La, List Lb)
{
        // 将所有在线性表Lb中但不在La中的数据元素插入到La中
        La_len = ListLength(La), Lb_len = ListLength(Lb);       // 求线性表的长度
        for (i = 1; i <= Lb_len; i++)
        {
                GetElem(Lb, i, e);      // 取Lb中第i个数据元素赋给e
                if (!LocateElem(La, e, equal))  ListInsert(La, ++La_len, e);        // La中不存在和e相同的数据元素则插入
        }
}
// 归并算法2.2 时间复杂度为O(ListLength(La) + ListLength(Lb))
void MergeLIst(List La, List Lb, List &Lc)
{
        // 已知线性表La和Lb中的数据元素按值非递减排列
        // 归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列
        InitList(Lc);
        i = j = 1, k = 0;
        La_len = ListLength(La), Lb_len = ListLength(Lb);
        while ((i <= La_len) && (j <= Lb_len))
        {
                // La和Lb均非空
                GetElem(La, i, ai), GetElem(Lb, j, bj);
                if (ai <= bj)
                {
                        ListInsert(Lc, ++k, ai);
                        ++i;
                }
                else
                {
                        ListInsert(Lc, ++k, bj);
                        ++j;
                }
        }
        while (i <= La_len)
        {
                GetElem(La, i++, ai);
                ListInsert(Lc, ++k, ai);
        }
        while (j <= La_len)
        {
                GetElem(Lb, j++, bj);
                ListInsert(Lc, ++k, bj);
        }
}

顺序表基本操作的实现
算法2.1 线性表L的初始化(参数用引用)

Status InitList_Sq(SqList &L)       // 构造一个空的顺序表
{
        L.elem = new ElemType[MAXSIZE];     // 为顺序表分配空间
        if (!L.elem)    exit(OVERFLOW);     // 存储分配失败
        L.length = 0;       // 空表长度为0
        return OK;
}

// 销毁线性表L
void DestoryList(SqList &L)
{
        if (L.elem) delete  L.elem;     // 释放存储空间
}

// 清空线性表L
void ClearList(SqList &L)
{
        L.length = 0;       // 将线性表的长度置为0
}

// 求线性表L的长度
int GetLength(SqList L)
{
        return (L.length);
}

// 判断线性表L是否为空
int IsEmpty(SqList L)
{
        if (L.length == 0)  return 1;
        else    return 0;
}

// 线性表的取值
int GetElem(SqList L, int i, ElemType &e)
{
        if (i < 1 || i > L.length)    return ERROR;       // 判断i值是否合理,若不合理,返回ERROR
        e = L.elem[i - 1];      // 第i - 1的单元存储着第i个数据
        return OK;
}

算法2.3 顺序表的查找

  • 在线性表L中查找与指定值e相同的数据元素的位置
  • 平均查找长度ASL
  • 从表的一端开始,逐个进行记录的关键字和给定值的比较。找到,返回该元素的位置序号,未找到,返回0
// 时间复杂度:O(n)
int LocateElem(SqLIst, ElemType e)
{
        // 在线性表L中查找值为e的数据元素,返回其序号
        for (i = 0; i < L.length; i++)
                if (L.elem[i] == e) return i + 1;       // 查找成功,返回序号
        return 0;       // 查找失败,返回0
}

顺序表的插入

  • 插入位置在最后
  • 插入位置在中间
  • 插入位置在最前面

插入思想

  1. 判断插入位置i是否合法
  2. 判断顺序表的存储空间是否已满,若已满返回ERROR
  3. 将第n至第i位的元素依次向后移动一个位置,空出第i个位置
  4. 将要插入的新元素e放入第i个位置
  5. 表长加1,插入成功

算法2.4 顺序表的插入

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
        if (i < 1 || i > L.length + 1)    return ERROR;       // i值不合法
        if (L.length == MAXSIZE)    return ERROR;       // 当前存储空间已满
        for (j = L.length - 1; j >= i - 1; j--)
                L.elem[j + 1] = L.elem[j];      // 插入位置及之后的元素后移
        L.elem[i - 1] = e;      // 将新元素e放入第i个位置
        L.length++;     // 表长增1
        return OK;
}

移动位置和插入位置的和是n+1
顺序表插入算法的平均时间复杂度为O(n)

顺序表的删除:

删除算法演示:

  • 删除位置在最后

  • 删除位置在中间

  • 删除位置在最前面

  • 算法思想:

    1. 判断删除位置i是否合法(1<=i<=n)
    2. 将第i+1至第n位的元素依次向前移动一个位置
    3. 表长减1,删除成功
Status ListDelete_Sq(SqList &L, int i)
{
        if ((i < 1) || (i > L.length))    return ERROR;       // i值不合法
        for (j = i; j <= L.length; j++)
                L.elem[j - 1] = L.elem[j];
        L.length--;
        return OK;
}

平均移动次数:(n-1)/2
平均时间复杂度O(n)

顺序表的特点

  • 查找、插入、删除算法的平均时间复杂度为O(n),空间复杂度为O(1)

  • 优点

    • 存储密度大(结点本身所占存储量/结点结构所占存储量 = 1)
    • 可以随机存取表中任一元素O(1)
  • 缺点(为克服:链表)

    • 在插入、删除某一元素时,需要移动大量元素
    • 浪费存储空间
    • 属于静态存储形式,数据元素的个数不能自由扩充

线性表的链式表示和实现

  • 单链表是由头指针唯一确定,因此单链表可以由头指针的名字来命名

  • 各结点由两个域组成

    1. 数据域:存储元素数值数据
    2. 指针域:存储直接后继结点的存储位置

与链式存储有关的术语

  1. 结点:数据元素的存储映像。由数据域和指针域两部分组成
  2. 链表:n个结点由指针链组成一个链表
  3. 单链表、双链表、循环链表
    • 结点只有一个指针域的链表,称为单链表
    • 结点有两个指针域的链表,称为双链表(前趋后继)
    • 首尾相接的链表称为循环链表
  4. 头指针、头结点和首元结点:
    • 头指针:是指向链表中第一个结点的指针
    • 首元结点:存储第一个数据元素a~1~的结点
    • 头结点:是在链表的首元结点之前附设的一个结点

头结点的数据域装什么?

  • 头结点的数据域可以为空,也可存放线性表长度等附加信息,但此结点不能计入链表长度值。

链表的特点:

  • 结点在存储器中位置任意(任意存储法
  • 只能通过头指针进入链表(顺序存取法

单链表的定义和表示

带头结点的单链表

  • 单链表的存储结构
    typedef struct Lnode {
        ElemType data;
        struct Lnode *next;
    } Lnode, *LinkList;
    // 定义链表L: LinkList L;
    // 定义结点指针p:Lnode *p <=> LinkList p;

例:存储学生学号、姓名、成绩的单链表结点类型定义:

typedef struct student {
        char num[8];        // 数据域
        char name[8];       // 数据域
        int score;      // 数据域
        struct student * next;      // 指针域
} Lnode, * LinkList;

// 为了统一链表的操作,通常这样定义:
typedef struct {
        char num[8];        // 数据域
        char name[8];       // 数据域
        int score;      // 数据域
} ElemType;

typedef struct Lnode {
        ElemType data;      // 数据域
        struct Lnode *next;     // 指针域
} Lnode, * LinkList;

单链表基本操作的实现

  • 单链表的初始化(带头结点的单链表)

    1. 生成新结点作头结点,用头指针L指向头结点
    2. 将头结点的指针域置空
      Status InitList_L(LinkList &L) {
      L = new Lnode;      // 或L = (LinkList) malloc (sizeof(Lnode));
      L -> next = NULL;
      return OK;
      }
  • 判断链表是否为空

    int ListEmpty(LinkList L) {
        if (L -> next)
                return 0;
        else
                return 1;
    }
  • 单链表的销毁
    从头指针开始,依次释放所有结点

    Status DestroyList_L(LinkList &L) {
        Londe * p;
        while (L)
        {
                p = L;
                L = L -> next;
                delete p;
        }
        return OK;
    }
  • 清空链表

Status ClearList(LinkList &L)
{
        Lnode * p, * q;     // 或LinkList p, q;
        p = L -> next;
        while (p)
        {
                q = p -> next;
                delete p;
                p = q;
        }
        L -> next = NULL;        // 头结点指针域为空
        return OK;
}
  • 求单链表表长
    int ListLength_L(LinkList L)
    {
        LinkList p;
        p = L -> next;
        i = 0;
        while (p)
        {
                i++;
                p = p -> next;
        }
        return i;
    }

  • 取值——取单链表中第i个元素的内容

    从链表的头指针出发,顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止。因此,链表不是随机存取结构

  1. 从第1个结点(L -> next)顺链扫描,用指针p指向当前扫描到的结点,p初值为L -> next
  2. j做计数器,累计当前扫描到的结点数,j初值为1
  3. 当p指向扫描到的下一结点时,j++
  4. 当j == i时,p所指的结点就是要找的第i个结点
    Status GetElem_L(LinkList L, int i, ElemType &e)
    {
        p = L -> next, j = 1;
        while (p && j < i)
        {
                p = p -> next;
                ++j;
        }
        if (!p || j > i) return ERROR;
        e = p -> data;
        return OK;
    }
  • 按值查找——根据指定数据获取所在位置(地址)

    Lnode * LocateElem_L(LinkList L, Elemtype e)
    {
        p = L -> next;
        while (p && p -> data != e)
                p = p -> next;
        return p;
    }
  • 按值查找——根据指定数据获取所在位置序号

    int LocateElem_L(LinkList L, Elemtype e)
    {
        p = L -> next, i = 1;
        while (p && p->data != e)
        {
                p = p->next, i++;
        }
        if (p)  return i;
        else    return 0;
    }
  • 插入——在第i个结点前插入值为e的新结点

    Status ListInsert_L(LinkList &L, int i, ElemType e)
    {
        p = L, j = 0;
        while (p && j < i - 1)       // 寻找第i - 1个结点,p指向i - 1结点
        {
                p = p->next;
                ++j;
        }
        if (!p || j > i - 1) return ERROR;       // i大于表长+1或小于1,插入位置非法
        s = new LNode, s->data = e;      // 生成新结点s,将结点s的数据域置为e
        s->next = p->next;        // 将结点s插入L中
        p->next = s;
        return OK;
    }
  • 删除——删除第i个结点

    // 将线性表中第i个数据元素删除
    Status ListDelete(LinkList &L, int i, ElemType &e)
    {
        p = L, j = 0;
        while (p->next && j < i - 1)
        {
                p = p->next;
                ++j;
        }       // 寻找第i个结点,并令p指向其前驱
        if (!(p->next) || j > i - 1)  return ERROR;       // 删除位置不合理
        q = p->next;     // 临时保存被删结点的地址以备释放
        p->next = q->next;        // 改变删除结点前驱结点的指针域
        e=q->data;       // 保存删除结点的数据域
        delete q;       // 释放删除结点的空间
        return OK;
    }
  • 查找

    // 时间复杂度O(n)
    Lnode * LocateElem_L(LinkList L, Elemtype e)
    {
        // 在线性表L中查找值为e的数据元素
        // 找到,则返回L中值为e的数据元素的地址,失败返回NULL
        p = L->next;
        while (p && p->data != e)
                p = p->next;
        return p;
    }
  • 建立单链表:头插法——元素插入在链表头部,也叫头插法

    1. 从一个空表开始,重复读入数据
    2. 生成新结点,将读入数据存放到新结点的数据域中
    3. 从最后一个结点开始,依次将各结点插入到链表的前端
      // 时间复杂度为O(n)
      L = new LNode;      // 或C语言如下
      L = (LinkList)malloc(sizeof(LNode));
      L->next == NULL;
      void CreateList_H(LinkList &L, int n)
      {
      L = new LNode;
      L->next = NULL;      // 先建立一个带头结点的单链表
      for (i = n; i > 0; --i)
      {
              p = new LNode;      // 生成新结点p = (LNode *)malloc(sizeof(LNode));
              cin >> p->data;        // 输入元素值scanf(&p->data);
              p->next = L->next;        // 插入到表头
              L->next = p;
      }
      }
  • 建立单链表:尾插法——元素插入在链表尾部,也叫后插法

    1. 从一个空表L开始,将新结点逐个插入到链表的尾部,尾指针r指向链表的尾结点
    2. 初始时,r同L均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点后,r指向新结点
      // 正位序输入n个元素的值,建立带表头结点的单链表L
      void CreateList_R(LinkList &L, int n)
      {
      L = new LNode;
      L->next = NULL;
      r = L;      // 尾指针r指向头结点
      for (i = 0; i < n; ++i)
      {
              p = new LNode;      // 生成新结点
              cin >> p->data;        // 输入元素值
              p->next = NULL;
              r->next = p;     // 插入到表尾
              r = p;      // r指向新的尾结点
      }
      }
      // 时间复杂度为O(n)

循环链表

  • 是一种头尾相接的链表

  • 带尾指针循环链表的合并

    // 时间复杂度O(1)
    LinkList Connect(LinkList Ta, LinkList Tb)
    {
        p = Ta->next;
        Ta->next = Tb->next->next;
        delete Tb->next;
        Tb->next = p;
        return Tb;
    }

双向链表

// 结构定义
typedef struct DulNode {
        Elemtype data;
        struct DulNode * prior, * next;
} DulNode, * DuLinkList;

双向循环俩表

  • 让头结点的前驱指针指向尾结点
  • 让尾结点和后继指针指向头结点
  • 对称性:p->prior->next = p = p->next->prior

双向链表的插入

Status LinkInsert_DuL(DuLinkList &L, int i, ElemType e)
{
        if (!(p = GetElemP_DuL(L, i)))      return ERROR;
        s = new DuLNode;
        s->date = e;
        s->prior = p->prior;
        p->prior->next = s;
        s->next = p;
        p->prior = s;
        return OK;
}

双向链表的删除

// 时间复杂度O(1)
Status ListDelete_DuL(DuLink &L, int i, ElemType &e)
{
        if (!(p = GetElemP_DuL(L, i)))      return ERROR;
        e = p->data;
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);
        return OK;
}

单链表、循环链表和双向链表的时间效率比较

查找首元结点查找尾结点查找结点*p的前驱结点
带头结点的单链表LL->next 时间复杂度O(1)从L->next依次向后遍历 时间复杂度O(n)通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表L->next 时间复杂度O(1)从L->next依次向后遍历 时间复杂度O(n)通过p->next可以找到其前驱 时间复杂度O(n)
带头结点仅设尾指针R的循环单链表R->next->next 时间复杂度O(1)R 时间复杂度O(1)通过p->next可以找到其前驱 时间复杂度O(n)
带头结点的双向循环链表LL->next->next 时间复杂度O(1)L->prior 时间复杂度O(1)p->prior 时间复杂度O(1)

顺序表和链表的比较

  • 链表的优点:
    • 结点空间可以动态申请和释放
    • 数据元素的逻辑次序靠结点的指针指示,插入和删除时不需要移动数据元素
  • 链表的缺点:
    • 存储密度小,每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时,指针域所占空间的比重很大
    • 非随机存取结构。对任一节点的操作都要从头指针依指针链查找到该节点,增加了算法的复杂度

线性表的应用

线性表的合并

假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=A∪B

  • 算法步骤:
    依次取出Lb中的每个元素,执行以下操作:

    1. 在La中查找该元素
    2. 若找不到,则将其插入La的最后
      // 时间复杂度O(ListLength(La)*ListLength(Lb))
      void union(List &La, List Lb)
      {
      La_len = ListLength(La);
      Lb_len = ListLength(Lb);
      for (i = 1; i <= Lb_len; i++)
      {
      GetElem(Lb, i, e);
      if (!LocateElem(La, e))     ListInsert(&La, ++La_len, e);
      }
      }

有序表的合并

已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。

  • 算法步骤

    1. 创建一个空表Lc
    2. 依次从La或Lb中摘取元素值较小的结点插入到Lc表的最后,直至其中一个表变空为止
    3. 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
  • 用顺序表实现

    // 时间复杂度 = 空间复杂度 = O(ListLength(La) + ListLength(Lb))
    void MergeList_Sq(SqList LA, SqList LB, SqList &LC)
    {
    pa = LA.elem;
    pb = LB.elem;   // 指针pa和pb的初值分别指向两个表的第一个元素
    LC.length = LA.length + LB.length;  // 新表长度为待合并两表的长度之和
    LC.elem = new ElemType[LC.length];  // 为合并后的新表分配一个数组空间
    pc = LC.elem;   // 指针pc指向新表的第一个元素
    pa_last = LA.elem + LA.length - 1;  // 指针pa_last指向LA表的最后一个元素
    pb_last = LB.elem + LB.length - 1;  // 指针pb_last指向LB表的最后一个元素
    while (pa <= pa_last && pb <= pb_last)    // 两个表都非空
    {
    if (*pa <= *pb)  *pc++ = *pa++;
    else    *pc++ = *pb++;
    }
    while (pa <= pa_last)    *pc++ = *pa++;
    while (pb <= pb_last)    *pc++ = *pb++;
    }
  • 用链表实现

    // 时间复杂度O(ListLength(La) + ListLength(Lb)) 空间复杂度O(1)
    void MergeList_L(LinkList &La, LiskList &Lb, LinkList &Lc)
    {
    pa = La->next, pb = Lb->next;
    pc = Lc = La;   // 用La的头结点作为Lc的头结点
    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        pc->next = pa ? pa : pb; // 插入剩余段
        delete Lb;  // 释放Lb的头结点
    }
    }

案例分析与实现

一元多项式的运算

稀疏多项式的运算

  • 创建一个新数组c
  • 分别从头遍历比较a和b的每一项
    • 指数相同,对应系数相加,若和不为0,则在c中增加一个新项
    • 指数不相同,将指数较小的项复制到c中
  • 一个多项式已遍历完毕时,将另一个剩余项依次复制到c中即可

多项式创建:

  1. 创建一个只有头结点的空链表
  2. 根据多项式项的个数n,循环n次执行以下操作:
    • 生成一个新结点*s
    • 输入多项式当前项的系数和指数赋给新结点*s的数据域
    • 设置一前驱指针pre,用于指向待找到的第一个大于输入项指数的结点的前驱,pre初值指向头结点
    • 指针q初始化,指向首元结点
    • 循链向下逐个比较链表中当前结点与输入项指数,找到第一个大于输入项指数的结点*q
    • 将输入项结点s插入到q之前
void CreatePolyn(Polynomial &P, int n)
{   // 输入m项的系数和指数,建立表示多项式的有序链表P
    p = new PNode;
    p->next = NULL;  // 先建立一个带头结点的单链表
    for (i = 1; i <= n; ++i)
    {   // 依次输入n个非零项
        s = new PNode;  // 生成新结点
        cin >> s->coef >> s->expn;    // 输入系数和指数
        pre = P;    // pre用于保存q的前驱,初值为头结点
        q = P->next; // q初始化,指向首元结点
        while (q && q->expn < s->expn)
        {
            pre = q;
            q = q->next;
        }
        s->next = q; // 将输入项s插入到q和其前驱结点pre之间
        pre->next = s;
    }
}

多项式相加:

  1. 指针p1和p2初始化,分别指向Pa和Pb的首元结点
  2. p3指向和多项式的当前节点,初值为Pa的头结点
  3. 当指针p1和p2均未到达相应表尾时,则循环比较p1和p2所指结点对应的指数值
  4. 将非空多项式的剩余段插入到p3所指结点之后
  5. 释放Pb的头结点

图书信息管理系统

struct Book
{
    char id[20];
    char name[50];
    int price;
}
typedef struct {    // 顺序表
    Book * elem;
    int length;
} SqList;
typedef struct LNode {  // 链表
    Book data;
    struct LNode *next;
} LNode, * LinkList;

留下评论

您的电子邮箱地址不会被公开。