三、线性表

3.1 线性表的定义

零个或多个数据元素的有限序列

有几个点要注意：

首先它是一个序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且仅有一个前驱和后继。

线性表强调的是有序的

如图所示：

所以线性表元素的个数n (n≥0)定义为线性表的长度，当n=0时，称为空表。

3.1.1实例

当然是，星座通常都是用白羊座打头，双鱼座收尾，当中的星座都有前驱和后继，而且一共也只有十二个，所以它完全符合线性表的定义。

班级里的点名册，是不是线性表呢？

是，这和友谊关系，爱情关系都不同，它是有限序列，而且它也满足类型相同的特点。

点名册中，每个学生除了学生的学号外，还可以有同学的姓名，性别、出生年月什么的，这些其实就是之前说的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成

3.2线性表的抽象数据类型

把排好的队解散重新排–这是一个线性表重置为空表的操作

ADT 抽象数据类型名
Data
    线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitList (*L);  初始化操作， 建立一个空的线性表L
  ListEmpty (L);  若线性表为空，返回true,否则返回false。
  ClearList(*L);  将线性表清空。
  GetElem (L,i,*e) ;  将线性表L中的第i个位置元素值返回给e。
  LocateElem(L,e);  在线性表L中查找与给定值e相等的元素，如果查找成功，返回
该元素在表中序号表示成功;否则，返回0表示失败。
  ListInsert ( *L,i,e); 在线性表L中的第i个位置插入新元素e。
  ListDelete ( *L,i,*e);  删除线性表L中第i个位置元素，并用e返回其值。
  ListLength (L); 返回线性表L的元素个数。
endADT

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

比如，要实现两个线性表集合A和B的并集操作。即要使得集合A=A∪B。**说白了，就是把存在集合B中但并不存在A中的数据元素插入到A中即可。**仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。我们假设La表示集合A, Lb表示集合B,则实现的代码如下:

/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void union (List *La,List Lb )
{
  int La_len, Lb_len,i;
  ElemType e;
  /*声明与La和Lb相同的数据元素e*/
  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) ) /*La中不存在和e相同数据元素*/
    ListInsert (La, ++La len,e) ; /*插入*/
  }
}

这里，我们对于union操作，用到了前面线性表基本操作ListLength、 GetElem、LocateElem、ListInsert 等，可见，对于复杂的个性化的操作，其实就是把基本操作组

合起来实现的。

3.3 线性表的顺序存储结构

3.3.1 顺序存储定义

说这么多的线性表，我们来看看线性表的两种物理结构的第一种顺序存储结构。

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

3.3.2顺序存储方式

线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

为了建立一个线性表，要在内存中找块地，于是这块地的第一个 位置就非常关键，它是存储空间的起始位置。

代码比较简单就不写出来了，截图好了。

这里，我们就发现描述顺序存储结构需要三个属性:

存储空间的起始位置: 数组data,它的存储位置就是存储空间的存储位置。

线性表的最大存储容量:数组长度MaxSize。

线性表的当前长度: length。

3.3.3数据长度与线性表长度区别

数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，

这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

3.3.4 地址计算方法

由于我们数数都是从1开始数的，线性表的定义也不能免俗，起始也是1,可C 语言中的数组却是从0开始第一个 下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系

其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。**存储器中的每个存储单元都有自己的编号,这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。**试想一下， 我是班级成绩第五名，我后面的10名同学成绩名次是多呢?当然是6, 7, …15，因为5 +1，5+2, .，. 5+ 10。由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。

LOC(ai)= LOC(ai)+c

所以对于第i个数据元素a的存储位置可以由a1推算得出:

LOC(ai)= LOC(ai)+(i-1)*c

用图更好理解呢！

通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数， 因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为0(1)。 我们通常把具有这一特 点的存储结构称为随机存取结构。

3.4 顺序存储结构的插入与删除

3.4.1 获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem 操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。来看代码:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码，如OK等*/
/*初始条件:顺序线性表L已存在，1≤i≤ListLength(L) */
/*操作结果:用e返回L中第i个数据元素的值*/
Status GetElem (SqList L,int i,ElemType *e)
{
  if (L.1ength==01I 1<1 11 i>L.length)
  return ERROR;
  *e=L.data[i-1] ;
  return OK;
}

注意这里返回值类型Status 是-一个整型，返回OK代表1, ERROR代表0。之后代码中出现就不再详述。

3.4.2 插入操作

刚才我们也谈到，这里的时间复杂度为0(1)。 我们现在来考虑，如果我们要实现ListInsert (*L,e),即在线性表L中的第i个位置插入新元素e，应该如何操作?

插入算法的思路:

如果插入位置不合理，抛出异常;

如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;

从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;

将要插入元素填入位置i处;

表长加1。

/*初始条件:顺序线性表L已存在，1≤i≤ListLength(L)，*/
/*操作结果:在L中第i个位置之前插入新的数据元素e, L的长度加1*/
Status ListInsert (SqList *L,int i, ElemType e)
{
  int k;
  if (L->length==MAXSIZE)  /*顺序线性表已经满*/
  return ERROR;
  if(i<1 || i>L->length+1)  /*当i不在范围内时*/
  return ERROR;
  if (i<=L->length)  /*若插入数据位置不在表尾*/
    {
        for (k=L->length-l;k>=i-1;k--)/*将要插入位置后数据元素向后移动一位*/
    L->data[k+1]-L->data[k];
    }
  L->data[i-1]=e;  /*将新元素插入*/
  L-> length++;
  return OK;
}

3.4.3 删除操作

书上讲的例子很有意思，哈哈哈哈！！！

删除算法的思路:

如果删除位置不合理，抛出异常;

取出删除元素;

从删除元素 位置开始遍历到最后-一个元素 位置，分别将它们都向前移动一个位置;

表长减1

/*初始条件:顺序线性表L已存在，1≤i≤ListLength(L)，*/
/*操作结果:删除在L中第i个数据元素，并用e返回其值, L的长度减1*/
Status ListDelete(SqList *L,int i, ElemType *e)
{
  int k;
  if (L->length==0)  /*顺序线性表已经满*/
  return ERROR;
  if(i<1  || i>L->length+1)  /*当i不在范围内时*/
  return ERROR;
  if (i<=L->length)  /*若数据位置不在表尾*/
    {
        for (k = i;k < L->length;k++)/*将要插入位置后数据元素向后移动一位*/
    L->data[k+1]-L->data[k];
    }
  L->data[i-1]=e;  /*将新元素插入*/
  L-> length++;
  return OK;
}

下面讨论下时间复杂度

当要插入或删除的元素在最后一个位置，那么时间复杂度为O（1），因为不需要移动元素

最坏的情况当然是插入或删除第一个元素，此时所有的元素都要向后移，时间复杂度为O（n）

以上平均下来，为（n-1）/2

通过前面讨论过时间复杂度的推导，可以得出，平均时间复杂度还是0[n)。这说明什么?线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是0(1);而插入或删除时，时间复杂度都是0[n)。**这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。**当然，它的优缺点还不只这些…

3.4.4 线性表顺序存储结构的优缺点

3.5 线性表的链式存储结构

3.5.1 顺序存储结构不足的解决办法

前面讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系，他们在内存中也是挨着的，中级没有空袭，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。

干脆所有元素都不要考虑相邻位置了，哪里有空位就到哪里，而只是让每个元素知道它下一个元素的位置，这样就可以在第一个元素时，就知道第二个元素的位置（内存地址），在第二个元素时，再找到第三个的位置（内存地址）

3.5.2线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中,除了要存数据元素信息外，还要存储它的后继元素的存储地址。

1.数据域和指针域

因此，为了表示每个数据元素ai 与其直接后继数据元素ai+1 之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

书上说的太好了，看书真的比看视频更有收获！！！

同学们，快去看书吧！

n个结点(a的存储映像)链结成一个链表,即为线性表(a1, a2, an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起

2.头指针

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示)。

有时，我们为了更加方便地对链表进行操作，**会在单链表的第一个结点前附设一个结点，称为头结点。**头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针

3.5.3 头指针与头结点的异同

异同点如下：

3.5.4 线性表链式存储结构代码描述

/*线性表的单链表存储结构*/
typedef struct Node
{
ElemType data;
struct Node *next;
} Node;
typedef struct Node *LinkList; /*定义 LinkList*/

从这个结构定义中,我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next 的值是一个指针。p->next指向谁呢?当然是指向第i+1个元素，即指向ai+1 的指针也就是说，如果p->data=ai,那么p->next->data=ai+1

上面这段话需要反复咀嚼！！！甚至自己可以拿笔画一下，多画几次就记住了~

p指针一个结点，相当于干了两件事

分别是指向了结点的数据域与和指针域

指向数据域是p->data

指向指针域是指针域里本来有个指针，p呢，它又指向这个指针，这个指针呢有指向下一个结点的data所以就有了上面这个图

以此类推