作者：whisper

链接：http://proprogrammar.com:443/article/763

声明：请尊重原作者的劳动，如需转载请注明出处

---

线性结构的定义

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性结构的特点

① 只有一个首结点和尾结点；
② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。
线性结构反映结点间的逻辑关系是一对一
线性结构包括线性表、堆栈、队列、字符串、数组等等。
其中，最典型、最常用的是 线性表

2.1 线性表的定义和特点

线性表的定义：用数据元素的有限序列表示

例如：分析 26 个英文字母组成的英文表
（A， B， C， D， ……， Z）
数据元素都是字母; 元素间关系是线性
同一线性表中的元素必定具有相同特性

2.2 案例引入

案例 2.1 ： 一元多项式的运算

案例 2.2： 稀疏多项式的运算

*创建一个新数组 c
*分别从头遍历比较 a 和 b 的每一项
指数相同，对应系数相加，若其和不为零，则在 c 中增加一个新项
指数不相同，则将指数较小的项复制到 c 中
*一个多项式已遍历完毕时，将另一个剩余项依次复制到 c 中即可
*顺序存储结构存在问题
存储空间分配不灵活 链式存储结构

运算的空间复杂度高

2.3 线性表的类型定义

线性表的类型定义
1. 线性表的顺序存储
2. 线性表的链式存储
线性表的重要基本操作
1. 初始化 2.取值
3. 查找 4. 插入
5. 删除

2.4 线性表的顺序表示和实现

线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
简言之，逻辑上相邻，物理上也相邻
顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组 V[n]来实现。

顺序存储

顺序表的类型定义

#defineMAXSIZE 100 //最大长度
typedef struct {
    ElemType *elem; //指向数据元素的基地址
    int length; //线性表的当前长度
}SqList；

以图书表的顺序存储结构类型为例：

#define MAXSIZE 10000 //图书表可能达到的最大长度
typedef struct //图书信息定义
{
    char no[20]; //图书 ISBN
    char name[50]; //图书名字
    float price; //图书价格
}Book;
typedef struct
{
    Book *elem; //存储空间的基地址
    int length; //图书表中当前图书个数
}SqList; //图书表的顺序存储结构类型为 SqList

线性表的重要基本操作

1. 初始化
2. 取值
3. 查找
4. 插入
5. 删除

重要基本操作的算法实现

1. 初始化线性表 L（参数用引用）
Status InitList_Sq（SqList &L） { //构造一个空的顺序表 L
    L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间
    if（!L.elem） exit（OVERFLOW） ; //存储分配失败
    L.length=0; //空表长度为 0
    return OK;
}

2.初始化线性表 L （参数用指针）
Status InitList_Sq（SqList *L） { //构造一个空的顺序表 L
    L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间
    if（! L-> elem） exit（OVERFLOW） ; //存储分配失败
    L-> length=0; //空表长度为 0
    return OK;
}

补充： 几个简单基本操作的算法实现

销毁线性表 L
void DestroyList（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;
}

2. 取值（根据位置 i 获取相应位置数据元素的内容）

获取线性表 L 中的某个数据元素的内容
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;
} 随机存取

3.查找（根据指定数据获取数据所在的位置）
顺序查找图示

在线性表 L 中查找值为 e 的数据元素
int LocateELem（SqList L， ElemType e）
{
    for （i=0;i< L.length;i++）
        if （L.elem[i]==e） return i+1;
    return 0;
}
查找算法时间效率分析 ？？？

4.插入（插在第 i 个结点之前）

插第 4 个结点之前，移动 6－4+1 次
插在第 i 个结点之前，移动 n-i+1 次
【算法步骤】
（1）判断插入位置 i 是否合法。
（2）判断顺序表的存储空间是否已满。
（3）将第 n 至第 i 位的元素依次向后移动一个位置，空出第 i 个位置。
（4）将要插入的新元素 e 放入第 i 个位置。
（5）表长加 1，插入成功返回 OK。
【算法描述】

4. 在线性表 L 中第 i 个数据元素之前插入数据元素 e
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 种可能）的平均移动次数，该如何计算？

5. 删除（删除第 i 个结点）

删除第 4 个结点，移动 6－4 次
删除第 i 个结点，移动 n-i 次
【算法描述】
5. 将线性表 L 中第 i 个数据元素删除
Status ListDelete_Sq（SqList &L， int i） {
    if（（i<1） ||（i>L.length）） return ERROR; //i 值不合法
    for （j=i;j<=L.length-1;j++）
        L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
    --L.length; //表长减 1
    return OK;
}

【算法分析】
算法时间主要耗费在移动元素的操作上
若删除尾结点，则根本无需移动（特别快）；
若删除首结点，则表中 n-1 个元素全部前移（特别慢）；

查找、 插入、删除算法的平均时间复杂度为 O（n）
显然，顺序表的空间复杂度 S（n） =O（1）
（没有占用辅助空间）

顺序表（顺序存储结构） 的特点

（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
这种存取元素的方法被称为随机存取法

顺序表的优缺点

优点：
存储密度大（结点本身所占存储量/结点结构所占存储量）
可以随机存取表中任一元素
缺点：
在插入、删除某一元素时，需要移动大量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充
为克服这一缺点 链表

2.5 线性表的链式表示和实现

链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻线性表的链式表示又称为非顺序映像或链式映像。

例 画出 26 个英文字母表的链式存储结构
逻辑结构：（a， b， …， y， z）
链式存储结构：

各结点由两个域组成：

数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置

与链式存储有关的术语

（1）结点：数据元素的存储映像。由数据域和指针域两部分组成
（2）链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
（3） 单链表、双链表、循环链表：
结点只有一个指针域的链表，称为单链表或线性链表
有两个指针域的链表，称为双链表
首尾相接的链表称为循环链表
循环链表示意图：

（4）头指针、头结点和首元结点

头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素 a1 的结点
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
讨论 1. 如何表示空表？
有头结点时，当头结点的指针域为空时表示空表

讨论 2. 在链表中设置头结点有什么好处？
第一：便于首元结点的处理
首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
第二：便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
讨论 3. 头结点的数据域内装的是什么？
头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

链表的优缺点

优点
—数据元素的个数可以自由扩充
—插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点
—存储密度小
—存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行
访问（顺藤摸瓜）

2.5.1 单链表的定义和实现

单链表的存储结构定义
typedef struct LNode{
    ElemType data; //数据域
    struct LNode *next; //指针域
}LNode， *LinkList; // *LinkList 为 Lnode 类型的指针
    LNode *p LinkList p

注意区分指针变量和结点变量两个不同的概念
LNode *p
p：表示什么？
*p：表示什么？

若 p->data=ai， 则 p->next->data=？
注意区分指针变量和结点变量两个不同的概念
LNode *p
•指针变量 p：表示结点地址
•结点变量*p：表示一个结点

2.5.2 单链表基本操作的实现

（1） 初始化
（2）取值
（3）查找
（4）插入
（5）删除

（1） 初始化（构造一个空表 ）

【算法步骤】
（1）生成新结点作头结点
（2）用头指针 L 指向头结点
（3）头结点的指针域置空

Status InitList_L（LinkList &L）
{
    L=new LNode;
    L->next=NULL;
    return OK;
}

补充：几个简单基本操作的算法实现

第一：销毁

Status DestroyList_L（LinkList &L） {
    LinkList p;
    while（L）
    {
        p=L;
        L=L->next;
        delete p;
    }
    return OK;
}

补充：几个简单基本操作的算法实现

第二：清空 // 将 L 重置为空表

Status ClearList（LinkList & L） {
    LinkList p， q;
   p=L->next; //p 指向第一个结点
   while（p）
   { q=p->next; delete p; p=q; }
   L->next=NULL; //头结点指针域为空
   return OK;
}

补充：几个简单基本操作的算法实现

第三：求表长

intListLength_L（LinkList L） {
   //返回 L 中数据元素个数
   LinkList p;
   p=L->next;
   i=0;
   while（p） {
      i++;
   p=p->next; }
   return i;
}

第四：判断表是否为空

int ListEmpty（LinkList L） {
   //若 L 为空表，则返回 1，否则返回 0
   if（L->next） //非空
      return 0;
   else
      return 1;
}

（2） 取值（根据位置 i 获取相应位置数据元素的内容）

//获取线性表 L 中的某个数据元素的内容
Status GetElem_L（LinkList L， int i， ElemType &e） {
    p=L->next; j=1; //初始化
    while（p&&j<i） { //向后扫描，直到 p 指向第 i 个元素或 p 为空
        p=p->next; ++j;
    }
    if（!p || j>i） return ERROR; //第 i 个元素不存在
    e=p->data; //取第 i 个元素
    return OK;
}//GetElem_L

（3） 查找（根据指定数据获取数据所在的位置）

//在线性表 L 中查找值为 e 的数据元素
LNode *LocateELem_L （LinkList L， Elemtype e） {
    //返回 L 中值为 e 的数据元素的地址，查找失败返回 NULL
    p=L->next;
    while（p &&p->data!=e）
        p=p->next;
    return p;
}

【算法描述】
//在线性表 L 中查找值为 e 的数据元素
int LocateELem_L （LinkList L， Elemtype e） {
    //返回 L 中值为 e 的数据元素的位置序号，查找失败返回 0
    p=L->next; j=1;
    while（p &&p->data!=e）
    {p=p->next;j++; }
    if（p） return j;
    else return 0;
}

（4） 插入（插在第 i 个结点之前）

//在 L 中第 i 个元素之前插入数据元素 e
Status ListInsert_L（LinkList &L， int i， ElemType e） {
    p=L;j=0;
    while（p&&j<i−1） {p=p->next;++j;} //寻找第 i−1 个结点
    if（!p||j>i−1） return ERROR; //i 大于表长+ 1 或者小于 1
    s=new LNode; //生成新结点 s
    s->data=e; //将结点 s 的数据域置为 e
    s->next=p->next; //将结点 s 插入 L 中
    p->next=s;
    return OK;
}//ListInsert_L

（5） 删除（删除第 i 个结点）

【算法描述】

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

链表的运算时间效率分析

（1）查找:因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O（n）。
（2）插入和删除:因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O（1）。
但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O（n） 。

单链表的建立（前插法）

从一个空表开始，重复读入数据：
—生成新结点
—将读入数据存放到新结点的数据域中
—将该新结点插入到链表的前端

单链表的建立（前插法）

【算法描述】

void CreateList_F（LinkList &L， int n） {
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的单链表
    for（i=n;i>0;--i） {
        p=new LNode; //生成新结点
        cin>>p->data; //输入元素值
        p->next=L->next; L->next=p; //插入到表头
    }
}//CreateList_F

单链表的建立（尾插法）

从一个空表 L 开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点。
初始时， r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后， r 指向新结点。

【算法描述】
void CreateList_L（LinkList &L， int n） {
    //正位序输入 n 个元素的值，建立带表头结点的单链表 L
    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 指向新的尾结点
    }
}//CreateList_L

2.5.3 循环链表

说明 从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到；

说明对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后一个结点

如何查找开始结点和终端结点？

示例：循环链表的合并

示例： 循环链表的合并

LinkList Connect（LinkList Ta， LinkList Tb）
{//假设 Ta、 Tb 都是非空的单循环链表
    p=Ta->next; //①p 存表头结点
   Ta->next=Tb->next->next; //②Tb 表头连结 Ta 表尾
   deleteTb->next; //③释放 Tb 表头结点
   Tb->next=p; //④修改指针
   returnTb;
}

2.5.4 双向链表

（b） 双向循环链表
d->next->prior = L->prior->next = L
双向链表的插入

双向链表的插入

（1） s->prior=p->prior;
（2） p->prior->next=s;
（3） s->next=p;
（4） p->prior=s;
双向链表的删除

1. p->prior->next=p->next;
2. p->next->prior=p->prior;

双向链表的删除
Status ListDelete_DuL（DuLinkList &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;
    delete p;
    return OK;
}

2.6 顺序表和链表的比较

2.7 线性表的应用

应用 1：线性表的合并
应用 2：有序表的合并
应用 3：有序链表的合并

2.7.1 顺序表的合并

应用 1：问题描述： 假设利用两个线性表 La 和 Lb 分别表示两个集合 A 和 B， 现要求一个新的集合

【算法步骤】
依次取出 Lb 中的每个元素，执行以下操作：
在 La 中查找该元素
如果找不到，则将其插入 La 的最后
O（ListLength（LA） × ListLength（LB））
【算法步骤】
依次取出 Lb 中的每个元素，执行以下操作：
在 La 中查找该元素
如果找不到，则将其插入 La 的最后
【算法描述】
定义了一个 SqList，作为把 SqList 当成一个数据类型，它有相应的运算
【算法步骤】 【算法描述】
依次取出 Lb         void union（SqList &La， SqList Lb） {
中的每个元素，       La_len=ListLength（La） ;
执行以下操作：       Lb_len=ListLength（Lb） ;
在 La 中查找           for（i=1;i<=Lb_len;i++） {
该元素                       GetElem（Lb， i， e） ;
如果找不到，             if（!LocateElem（La， e））
则将其插入的最后      La ListInsert（&La， ++La_len， e） ;
                              }
                         }

2.7.2 有序表的合并

应用 2：问题描述： 已知线性表 La 和 Lb 中的数据元素按值非递减有序排列，现要求将 La 和 Lb 归并为一个新的线性表 Lc，且 Lc 中的数据元素仍按值非递减有序排列.
La=（1 ， 7， 8）
Lb=（2， 4， 6， 8， 10， 11）
Lc=（1， 2， 4， 6， 7 ， 8， 8， 10， 11） .

【算法描述】
void union（SqList &La， SqList Lb）
{
}

【算法步骤】－有序的顺序表合并
（1） 创建一个空表 Lc
（2） 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
（3） 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后时间复杂度？
【算法步骤】－有序的顺序表合并
（1） 创建一个空表 Lc
（2） 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
（3） 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后时间和空间复杂度？
【算法描述】－有序的顺序表合并
T（n） = O（ListLength（LA） + ListLength（LB））
S（n） = O（n）

应用 3：有序链表合并－－重点掌握
—将这两个有序链表合并成一个有序的单链表。
—要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。
—表中允许有重复的数据。

【算法描述】－有序的链表合并
void MergeList_L（LinkList &La， LinkList &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 的头结点
}
T（n） = O（ListLength（LA） + ListLength（LB））
S（n） = O（1）

两道思考题：

问题 1：要求合并后的表无重复数据，如何实现

提示： 要单独考虑

pa->data = =pb->data

问题 2：将两个非递减的有序链表合并为一个非递增的有序链表，如何实现？
要求结果链表仍使用原来两个链表的存储空间， 不另外占用其它的存储空间。表中允许有重复的数据。
疑问：那就两两比较“摘取”大的元素不就行了？
【算法步骤】
（1） Lc 指向 La
（2） 依次从 La 或 Lb 中“摘取”元素值较小的结点插 入到 Lc 表的表头结点之后，直至其中一个表变空为止
（3） 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后
（4） 释放 Lb 表的表头结点
作业：
【算法描述】
【时间与空间复杂度】

2.8 案例分析与实现

案例 2.1 ：一元多项式的创建

数组表示
（每一项的指数 i 隐含在其系数 pi的序号中）
如何创建一元多项式？

案例 2.3： 图书信息管理系统，如何管理数据和组织数据

图书顺序表

小结

重点 1：掌握线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。
重点 2：熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。
重点 3：熟练掌握顺序表的查找、插入和删除算法
重点 4：熟练掌握链表的查找、插入和删除算法
重点 5：能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合

 

---

亲爱的读者：有时间可以点赞评论一下