第二章：线性表

线性表的类型和定义

所谓线性表，就是数据结构呈现线性结构：

线性结构的基本特征为

1．集合中必存在唯一的一个“第一元素”;
2．集合中必存在唯一的一个“最后元素”;
3．除最后一个元素在外，均有唯一的后继;
4．除第一个元素之外，均有唯一的前驱。

说明

1. 同一个线性表中的元素类型必须相同
2. 复杂线性表中单个数据元素可以包含若干数据项(item)，这种数据元素称为记录(record)，包含若干记录的线性表称为文件(file)。
3. 线性表中元素存在顺序关系，线性表(a1,a2,.....,ai-1,ai,ai+1,…,an)中，ai-1是ai的直接前驱元素，ai+1是ai直接后继元素。
4. 线性表中元素的个数n (n>=0)为线性表的长度，n=0称为空表，i是ai在线性表中的**位序**。
5. 线性表的长度可以根据需要改变。

基本操作（可忽略）

1.初始化操作

InitList(&L)

操作结果:构造一个空的线性表L。

2.结构销毁操作

DestroyList(&L)

初始条件:线性表L已存在。 操作结果:销毁线性表L。

3.引用型操作

ListEmpty(L)(线性表判空)

初始条件:线性表L已存在。 操作结果:若L为空表，则返回TRUE，否则FALSE。

ListLength(L)(求线性表的长度)

初始条件:线性表L已存在。 操作结果:返回L中元素个数。

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无定义。

GetElem( L, i, &e )(求线性表中某个数据元素)

初始条件:线性表L已存在，且 l<i≤LengthList(L)。 操作结果:用e返回L中第i个元素的值。

LocateElem( L, e, compare() )(定位函数)

初始条件:线性表L已存在，e为给定值，compare()是元素判定函数。 操作结果:返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。

ListTraverse(L, visit())(遍历线性表)

初始条件:线性表L已存在，visit()为某个访问函数。 操作结果:依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。

4.加工型操作

ClearList(&L)(线性表置空)

初始条件:线性表L已存在。 操作结果:将L重置为空表。

PutElem( &L, i, e)(改变数据元素的值)

初始条件:线性表L已存在，且1≤i≤LengthList(L) 。 操作结果:L中第i个元素赋值同e的值。

ListInsert(&L, i, e)(插入数据元素)

初始条件:线性表L已存在，且1≤i LengthList(L)+1 。 操作结果:在L的第i个元素之前插入新的元素e，L的长度增1。

ListDelete(&L, i, &e)(删除数据元素)

初始条件:线性表L已存在且非空，1≤i≤ LengthList(L)。 操作结果:删除L的第i个元素，并用e返回其值，L的长度减1。

例题

假设:有两个集合A和B分别用两个线性表LA和LB表示，即:线性表中的数据元素即为集合中的成员。
现要求一个新的集合A=AUB。

上述问题可以转换为：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。

算法实例

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);                  //取Lb中第i个数据元素赋给e
        if(!LocateElem(La, e, equal()))
        ListInsert(La,++La_len, e);         // La中不存在和e相同的数据元素，则插入之
    }
}

这里讲一下参数携带和不携带&的区别，如果参数携带&，说明传入的是参数的实际地址，例如在这里的参数La，那么在函数当中对**La**修改，函数之外的**La**也会进行相应的修改。

时间复杂度:O(ListLength(LA)*ListLength(LB)) (因为LocateElem执行时间和表长成正比。) 以上代码只用作算法演示，不是代码实例，不能直接运行。

线性表示的顺序表示和实现（重点）

线性表的实现主要有两种方式：

1. 顺序实现：数组
2. 链式实现：链表

所谓顺序实现，就是用一组实际地址连续的存储单元，依次存放线性表中的数据元素。
以“存储位置相邻”表示有序对<ai-1,ai>即: LOC(a**i)= LOC(ai-1**)+C

其中： C为一个数据元素所占存储量。 LOC(ai)表示的就是ai的地址。

所有数据元素的存储位置均取决于第一个数据元素的存储位置
LOC(a**i)= LOC(a1**)+ (i-1)×C

其中LOC(a1)为基地址

各种数据类型所占的存储空间xuaimian的博客-CSDN博客数据类型占用空间
在顺序实现中，数据的逻辑位置和数据的物理位置保持相对一致，如下图所示：

顺序表的特点

1. 元素的逻辑位置相邻，其物理位置也相邻。
2. 只要确定了存储线性表的起始位置,线性表中任一数据元素都可以随机存取。
3. 通常用数组描述数据结构中的顺序存储结构。
4. 存取效率高，结构紧凑

   说明：通常用数组来描述数据结构中的顺序存储结构，由于线性表长度可变，且所需最大存储空间随问题而变，可用动态分配的一维数组。

#define LIST_INIT_SIZE 100          //线性表存储空间的初始分配量
#define LISTINCREMENT 10            //线性表存储空间的分配增量
typedef struct{
    ElemType *elem;                 //存放线性表的数组
    int length;                     //当前长度
    int listsize;                   //当前分配的存储容量(以sizeof(ElemType)为单位)
}SeqList;

括号里面的代码的意思是定义一个结构变体,其中elem是用来存放数据的数组的指针，ElemType需要自行声明数据的类型。 关于结构体的相关概念请看下面的链接：

C语言结构体 - 两猿社 - 博客园

数据元素的插入

假设一个线性表为L，需要在其第i个位置插入一个元素。
那么我们只要找到第i-1个数，把i-1个数后面的元素全部后移即可。
就像下图所示

在索引为3的位置插入一个元素50.

算法实现：

Status ListInsert_Sq(SqList &L, int i,ElemType e){
    //在顺序表L的第i个元素之前插入新的元素e
    //i的合法范围为1≤i≤L.length+1
    if(i<1 || i>L.length+1) return ERROR;                        //若插入位置不合法，返回ERROR
    //插入元素
    q=&(L.elem[i-1]);                                           //用q来表示插入位置
    for(p= &(L.elem[L.length-1]);p>=q；--p)                     //将线性表最后一个数据的地址赋值给p，递减循环至插入位置的那一个数
        *(p+1)=*p;                                              //插入位置及之后的元素右移
    *q=e;                                                             //插入e
    ++L.length;                                                     //表长增1
    return OK;    
    if (L.length >= L.listsize){                                //判断插入元素后是否超出限制的存储空间，若当前存储空间已满，增加分配
        newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));//重新分配地址
        if (!newbase) exit(OVERFLOW);                           //存储分配失败
        L.elem = newbase;                                       //新基址赋值给elem
        L.listsize += LISTINCREMENT;                            //增加存储容量
    }
}

算法时间复杂度为： O( ListLength(L))

由于L是一个结构变体，所以其中的所有属性都要进行更改。

数据元素的删除

从第i-1个元素右边开始至最后一个元素，每个元素往左移动一个位置即可
如下图所示

删除索引为4的元素。

算法实现：

Status ListDelete_Sq(SqList &L, int i, ElemType &e){
    if((i< 1)||(i> L.length)) return ERROR;                         //删除位置不合法
    p=&(L.elem[i-l]);                                               //p为被删除元素的位置
    e=*p;                                                           //被删除元素的值赋给e
    q=&(L.elem[L.length-1]);                                        //q表尾元素的位置
    for (++p;p<= q;++p) 
        *(p-1)=*p;                                                     //被删除元素之后的元素左移
    --L.length                                                      //表长减1
    return OK;
}ListDelete_Sq

算法时间复杂度为： O( ListLength(L))

优缺点分析

• 优点
  • 顺序表的结构简单
  • 顺序表的存储效率高，是紧凑结构
  • 顺序表是一个随机存储结构（直接存取结构）
• 缺点
  • 在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。
  • 对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。

单链表（重点）

单链表的结构如下：

这里的头结点是为了方便而自己定义的。
元素之间使用指针进行串联。
简单的来说，数据的逻辑位置和实际位置可能不一样：

链表需要通过指针来指向下一个数据的实际内存地址，从而在内存中找到下一个数据。

指针忘记的可以看下面的链接进行复习

1分钟彻底理解C语言指针的概念_C语言中文网

线性表的顺序存储和链式存储结构的区别

• 顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取，缺点是插入或删除操作需移动大量元素。
• 链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，插入和删除不需要移动大量元素，缺点是不能随机存取。

  节点和单链表的C语言表述

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

  LNode里面包含了指针指向的数据data，以及下一个相邻的指针*next。 上述代码定义了一个LNode类型，别名也叫LinkList，在这里*LNode = LinkList。 也就是说在主函数里面定义一个LNode指针可以定义成*LNode L，也可以定义成LinkList L。

在单链表中获取第i个数据

1. 单链表是一种链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
2. 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。
3. 令指针 p 始终指向线性表中第 j 个数据元素。

具体过程如下：
首先我们定义获取单链表中的元素的函数是这样的： GetElem(L, i, &e)
其中，L表示头结点，i表示需要获取元素的索引，&e表示获取到第i个元素之后返回的元素。
上面算法中的p是自定义的一个指针，用来通过移动找到第i个元素。
j就是p指针指向的索引。
当p指针指向了第i个元素，那么j=i。

例如：我们要找到下面这张图的第三个元素：30

寻找过程如下：



如此便找到了30这个元素。

注意这里为了便于计算，索引不是从0开始的，而是从1开始的。

算法实现：

Status GetElem_L(LinkList L, int i, ElemType &e){           //L是带头结点的链表的头指针，以e返回第i个元
    p=L->next; j = 1;                                       //p指向第一个结点，j为计数
    while(p && j<i){                                        //j=i的时候循环停止
        p=p->next;
        ++j;
    }                                                       //顺指针向后查找，直到p指向第i个元素或p为空
    if (!p || j>i ) return ERROR;                           //第i个元素不存在
    e=p->data;                                              //取得第i个元素
    return OK;
}

算法时间复杂度为:O(ListLength(L))

在单链表中插入元素

比如我要在a**i-1和a**i中插入一个元素e。

实现的过程很简单：
1.

2.

3.

需要注意的是，这里的顺序不能颠倒。 因为元素a**i需要通过ai-1**才能获取，如果先把ai-1的指针指向元素e，那么ai的地址就不能通过指针找到了。

算法实例

Status ListInsert_L(LinkList L, int i, ElemType e){
    //L为带头结点的单链表的头指针，本算法
    //在链表中第i个结点之前插入新的元素e
    p=L; j= 0;
    while(p && j < i-l){
        p= p->next;
        ++j;                                      //寻找第i-1个结点
    }      
    if(!p ||j> i-1)
        return ERROR;                             //i大于表长或者小于1
    s = (LinkList) malloc (sizeof(LNode));        //生成新结点
    s->data = e,
    s->next = p->next;
    p->next = s;                                  //插入元素s，s的数值是e,下一个指针是第i+1个指针
    return OK;
}// LinstInsert_L

算法的时间复杂度为:O(ListLength(L))

单链表中的删除操作

这个很简单看图就懂了


算法实例

Status ListDelete_L(LinkList L, int i, ElemType &e) {
    // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点
    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;   free(q);
    return OK;
} // ListDelete_L

算法的时间复杂度：O(ListLength(L))

创建单链表

算法实例

void CreateList_L(LinkList &L, int n) {
    // 逆序输入 n 个数据元素，建立带头结点的单链表
    L = (LinkList) malloc (sizeof (LNode));
    L->next = NULL;    // 先建立一个带头结点的单链表
    for (i = n; i > 0; --i) {
        p = (LinkList) malloc (sizeof (LNode));
        scanf(&p->data);    // 输入元素值
        p->next = L->next; L->next = p;  // 插入
    }
} // CreateList_L

其余链表

循环链接

循环链表如下：

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

双向链表

//双向链表的结构体定义
typedef struct  DuLNode {
    ElemType         data;   // 数据域
    struct DuLNode   *prior;  
                               // 指向前驱的指针域
    struct DuLNode  *next;  
                               // 指向后继的指针域
} DuLNode, *DuLinkList;

• “查询” 和单链表相同。
• “插入” 和“删除”时需要同时修改两个方向上的指针。