定义

线性表，全名为线性存储结构。

线性表是n个数据特性相同的元素的组成有限序列，是最基本且常用的一种线性结构(线性表，栈，队列，串和数组都是线性结构），同时也是其他数据结构的基础。具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。

特点

• 是一个有限的序列
• 可以是有序的也可以是无序的。
• 线性表的开始元素没有前驱元素只有后继元素，线性表的结束元素没有后继元素只有前驱元素，除了开头元素和结尾元素以外，每个元素都有且只有一个前驱元素和后继元素。

前驱和后继

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。

• 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；
• 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；

以下图数据中的元素 3 来说，它的直接前驱是 2 ，此元素的前驱元素有 2 个，分别是 1 和 2；同理，此元素的直接后继是 4 ，后继元素也有 2 个，分别是 4 和 5。

存储结构

线性表存储结构分为顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表。

顺序存储结构

定义

顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到从指定位置开始的一块连续的存储空间。

特点

逻辑上相邻的数据元素，物理次序也是相邻的。

只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。

**数组长度和线性表的长度区别：**数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的，线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

优缺点

优点	缺点
无需为表示表中元素之间的逻辑关系而增加额外的存储空间	插入和删除操作需要移动大量元素
可快速的存取表中的任一位置元素	当线性表长度变化比较大时，难以确定存储空间的容量
	容易造成存储空间碎片

基本操作

结构体定义

顺序表可以分为静态分配和动态分配两种：

• 静态分配

#define MaxSize 50  / /顺序表的最大长度
typedef struct{		// typedef类型重命名
    ElemType data[MaxSize]; // 顺序表的元素，ElemType是未明确的数据类型，使用时可以用typedef定义具体类型
    int length;				// 长度
}SqList;

静态分配方法需要预先分配一段固定大小的连续空间，但在运算过程中，进行插入，合并等操作时，容易超过预分配的空间长度，出现溢出问题。

• 动态分配

#define InitSize 50  // 顺序表的初始长度
typedef struct{		// typedef类型重命名
    ElemType *data; // 指向动态分配数组的指针，基地址，*取内容
    int MaxSize;	// 数组的最大容量
    int length;	// 数组的当前个数
}SeqList;
// 定义SqList类型的变量
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

初始化

struct SqList{
	int data[MaxSize]; // 存放顺序表的元素
	int length; // 存放顺序表的长度
	int last;
};

void Init(SqList *L){
	L->data[0] = int(malloc(MaxSize * sizeof(int)));
	int n, i = 0;
	cin >> n;
	L->length = n;
	while (i < n)
	{
		cin >>(L->data[i++]);
	}
	L->last = i - 1;
}

插入

bool InsertList(SqList &L, int i, int e)
{
	// 在顺序表中第i个位置（位序，不是下标）插入数值e
	int j;
	if (i<1 || i>L.length+1) // 是否越界
		return false;
	if (L.length == MaxSize)// 内存已满
		return false;
	L.length++;            // 长度++
	for (j = L.length; j >= i; j--) // 将第i个起的数据后移
		L.data[j] = L.data[j - 1];
	L.data[j] = e;
	return true;
}

删除

bool DeleteList(SqList&L, int i)
{
	// 删除顺序表中第i个元素
	int j;
	if (i<1 || i>L.length)
		return false;   // 判断越界
	for (j = i; j < L.length; j++)
		L.data[j - 1] = L.data[j];
	L.length--;
	return true;
}

查找

bool LocateElem(SqList L, int e)
{
	int i;
    for(i = 0; i < L.length; i++){
        if(L.data[i] == e){
            return i+1;
        }
    }
    return 0;
}

链式存储结构

又称为链表，用于存储逻辑关系为 “一对一” 的数据。

用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），包括数据域和指针域，数据域存数据，指针域指示其后继的信息。

1、单链表

节点

一个完整的链表需要由以下几部分构成：

1. **头指针：**一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；

2. 节点：链表中的节点又细分为头节点、首元节点和其他节点：

   • **头节点：**其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
   • **首元节点：**由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
   • **其他节点：**链表中其他的节点；

链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

基本操作

结构体定义

typedef struct Lnode{	
	ElemType data; 
	struct Lnode *next;
}LNode,*LinkList

初始化

单链表的初始化是指构建一个空表。先创建一个空结点，不存放数据，然后令其指针域为空；

bool InitList_L(LinkList &L){
	L = new Lnode; 
	if(!L) return false;
	L -> next = NULL;
	return true;
}

创建

创建单链表分为头插法和尾插法两种。

• 头插法：是指每次将新结点插入到头结点之后，其创建的单链表和数据输入的顺序正好相反，因此也称为逆序建表。

void CreateList_H(LinkList &L){
	int n;
	LinkList s;
	L = new LNode;
	L -> next = NULL;
	cin>>n;
	while(n--){
		s = new LNode;
		cin>>s->data;
		s->next = L->next;
		L->next = s;
	}
}

• 尾插法：是指每次把新结点链接到链表的尾部，其创建的单链表和数据输入顺序一致，因此也称为正序建表。

void CreatList_R(LinkList &L){	
	int n;
    LinkList s, r;
    L = new Lnode;
    L -> next = NULL;
    r = L;
    cin>>n;
    while(n--){
		s = new LNode; 
        cin >> s->data;
        s -> next = NULL; 
        r -> next = s;
        r = s; 
    }
}

按序取值
从单链表的第一个结点出发，顺指针逐个往下搜索，知道找到第i个结点为止，否则返回最后一个结点的指针NULL。

LinkList GetElem(LinkList L, int i){
	int j = 1; 
    LinkList p = L -> next;
    if(i == 0) return L;
    if(i < 1) return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p;
}

插入结点

p = GetElem(L, i-1);
s -> next = p -> next;
p -> next = s;

删除结点

p = GetElem(L, i-1);
q = p -> next;
p -> next = q -> next;

2、静态链表

静态链表，兼顾了顺序表和链表的优点于一身。

使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。

3、双向链表

在单链表的基础上，再在每个结点中设置一个指向其前驱结点的指针域，这样一个结点既可以指向它的前面又可以指向它的下一个，我们把这种链表称为双向链表。

4、循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

顺序存储和链式存储比较

• 顺序表只需知道第一个元素的位置，就可以通过起始位置的偏移去获取顺序表中的任何元素（随机访问），而链表的存储结构是一个元素中包含下一个数据元素的位置信息，下一个包含下下一个，也就是每个数据元素之间都是单线联系的，你要想知道最后一个元素在哪里，你必须从头走到尾才可以，所以链表是不支持随机访问的。
• 顺序表中的数据元素是存放在一段地址连续的空间中，且这个存储空间是提前分配的，一旦分配好了，在对其进行操作的过程中是不会更改的。而链表支持存储空间动态分配。
• 顺序表在插入删除一个元素的时候需要移动大量元素。而链表在插入和删除一个元素时，不需要移动大量元素，只需要更改插入位置的指针指向就可以。

---

本篇完

顺序存储定义

说这么多的线性表，我们来看看线性表的两种物理结构的第一种——顺序存储结构。
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表（a1,a2……,an)的顺序存储示意图如下:

顺序存储方式

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

线性表中，我们估算这个线性表的最大存储容量，建立一个数组，数组的长度就是这个最大存储容量。但在实际使用中，我们并不是每个时刻都使用这最大的存储容量，我们希望能够更加高效的使用空间，因此我们使用malloc申请空间，realloc来调整空间大小，做到此点。可看空间分配与释放来具体了解函数作用。

来看线性表的顺序存储的结构代码。

#define INITSIZE 20  //初始化的大小
#define EXPANDTIMES 2 //每次的扩容倍数
typedef int ELemType; //用int来模拟数据项类型
typedef struct
{
	ElemType* data; //存储数据的初始位置
	int capacity; //容量（总共的:未使用的+已经使用的）
	int size;//已经使用的
}Sqlist;

关于数组和指针我在这就不多讲了，想要了解的可以去看我的数组与指针。

Init_List(*L)

bool Init_List(Sqlist *L)
{
	assert(L != NULL);//对输入也检测一下，使用空指针可能会导致程序奔溃，具体原因自己去搜，后续不解释
	L->data = (int*)malloc(sizeof(ELemType) * INITSIZE);//申请一段堆空间来存储元素
	//assert(L->data != NULL);//因为malloc可能会申请失败，判断一下
	if (L->data == NULL)
	{
		return false;
	}
	else
	{
		L->capacity = INITSIZE;//初始容量通过宏定义设定
		L->size = 0;//初始使用的大小当然是0喽
		return true;
	}
}

为了能够拥有动态空间大小，我们在这使用了堆空间作为存储空间，不用了记得free

Change_List(*L, flag)

bool Change_List(Sqlist* L,int flag)//改变容量
{
	assert(L != NULL);
	ELemType* temp = L->data;
	int newsize = flag == -1 ? L->capacity / EXPANDTIMES : L->capacity * EXPANDTIMES;//简单的判断，
	temp = (ELemType*)realloc(temp,newsize * sizeof(ELemType));//扩容也可能会失败，这样做是防止旧数据丢失
	if (temp == NULL)
	{
		return false;
	}
	else
	{
		L->data = temp;//将申请到的空间交给data
		L->capacity = newsize;//更改容量
		return true;
	}
}

Is_Empty(*L)

bool Is_Empty(Sqlist* L)
{
	assert(L != NULL);
	return L->size == 0;//只用检测一下使用的大小为不为0，就ok
}

Clear_List(*L)

bool Clear_List(Sqlist* L)
{
	assert(L != NULL);
	free(L->data);//因为空间是malloc来的，不用就free掉
	Init_List(L);//最简单的做法，重新给他初始化下，就消除了数据，也缩小了容量
	//L->size = 0;//最最最简单的方法因为数据是否有效，我们说了算，容量没变
	return true;
}

GetElem_List(*L,i)

ELemType GetElem_List(Sqlist* L, int i)
{
	assert(L != NULL && i < L->size && i >= 0);//保证改下标必须为有效下标，后续不解释
	return L->data[i];
}

LocateElem_List(*L,e)

int LocateElem_List(Sqlist* L, ELemType e)
{
	assert(L != NULL);
	int pos = -1;
	for (int i = 0; i < L->size; i++)//遍历是必须的
	{
		if (e == L->data[i])
		{
			pos = i;
			break;
		}
	}
	return pos;
}

Insert_List(*L,i,e)

bool Insert_List(Sqlist* L,int i,ELemType e)
{
	assert(L != NULL && i >= 0 && i <= L->size);//为满足线性表的定义，应对下标进行检测
	if (L->capacity == L->size)//容量不足是需要进行扩容
	{
		if (!Change_List(L,1)) //扩容成功才能继续放数据
		{
			return false;
		}
	}
	int pos = L->size;
	while (L->size != i)//向后挪动一位
	{
		L->data[pos] = L->data[pos - 1];
		pos--;
	}
	L->data[pos] = e;
	L->size++;
	return true;
}

尾插的话，i=L->size;头插i=0;

Delect_List(*L, i)

与插入反向操作

bool Delect_List(Sqlist* L, int i)//
{
	assert(L != NULL && i < L->size && i >= 0);
	while (i != L->size-1)//向前挪动一位
	{
		L->data[i] = L->data[i+1];
		i++;
	}
	L->size--;
	if (L->capacity > INITSIZE && L->size < L->capacity / EXPANDTIMES)
		Change_List(L, -1);
	return true;
}

Length_List(*L)

int Length_List(Sqlist* L)
{
	assert(L != NULL);
	return L->size;//我们有专门的数据项来记录长度，直接返回就行
}

Destory_List(*L)

因为clear只会清除数据(存储空间有一部分清不掉）,我们要专门free掉

bool Destroy_List(Sqlist* L)
{
	L->capacity = 0;
	L->size = 0;
	free(L->data);//Destroy以后就彻底不能用了，因为0乘以任何数还是0
	L->data = NULL;
	return true;
}

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

优点

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速地存取表中任位置的元素。（顺序读取快，O(1));

缺点

插入和删除操作需要移动大量元素 O(n)
当线性表长度变化较大时,难以确定存储空间的容量 (用数组就是这样，所以我们有扩容/缩容）
造成存储空间的“碎片”（绝大部分时间capacity > size，有一部分空间闲置）

一、顺序存储二叉树概述

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。顺序结构存储就是使用数组来储存，一般使用数组只适合表示完全二叉树，因为不完全二叉树会有空间的浪费。

下图就是树和数组对应的关系图：

顺序二叉树有下面几个显著的特征（n 表示二叉树中的第几个元素，从 0 开始）：

1. 第 n 个元素的左子节点为第 2 * n + 1 个元素；
2. 第 n 个元素的右子节点为第 2 * n + 2 个元素；
3. 第 n 个元素的父节点为第 ( n - 1 ) / 2 个元素。

我们随便选两个节点来验证其中一个特性。比如 元素2 是第 1 个元素，对应数组中的 arr[1]，则根据公式 元素2 的左子节点应当为 2*1+1 = 3，也就是第 3 个元素，对应数组中的 arr[3]，刚好与二叉树的第 3 个元素符合。

二、顺序存储二叉树的操作

【案例需求】

已知一个数组为：

arr = {1,2,3,4,5,6,7}

要求以二叉树前序遍历的方式对数组进行遍历，前序遍历的结果应当为：

1,2,4,5,3,6,7

【思路分析】

这个需求实际上是在考察顺序存储二叉树的重要特征：第 n 个元素的左子节点为 2n+1、右子节点为 2n+2。

根据它的特征我们可以知道：第 0 个元素 arr[0] 的左子节点为 arr[1]、右子节点为 arr[2]；第 1 个元素 arr[1] 的左子节点为 arr[3]、右子节点为 arr[4] …

【代码实现】

利用顺序存储二叉树的公式，我们可以很容易写出对数组以二叉树形式的前序遍历：

/**
 * 顺序存储二叉树
 */
class ArrayBinaryTree{
    int[] arr;	// 数组

    public ArrayBinaryTree(int[] arr){
        this.arr = arr;
    }

    /**
     * 前序遍历：根->左->右
     * @param index 数组索引，也即第几个元素
     */
    public void preOrder(int index){
        System.out.println(arr[index]);  // 先打印根
        if ((index*2+1) < arr.length){	// 判断左子节点是否存在
            preOrder(index*2+1);	// 再打印左子树
        }
        if ((index*2+2) < arr.length){	// 判断右子节点是否存在
            preOrder(index*2+2);	// 最后打印右子树
        }
    }
}

运行结果如下：