前言

我们今天来学习线性表，线性表是数据结构中比较简单的一个数据结构了，但是它的重要性不容忽略，废话不多，直接正文。

初识线性表

线性表的定义

线性表是具有相同类型的n（n>=0）个元素的有限序列，其中n为表长，当n=0时，该表为空表

线性表的特点：

1.表中元素个数有限
2.表中元素具有逻辑上的顺序性，在序列中各个元素排序有其先后次序
3.表中元素都是数据元素，每个元素都是单个元素
4.表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
5.表中元素具有抽象性，即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容
6.线性表是一种逻辑结构，表示元素之间一对一相邻的关系
7.线性表在数据元素有限集中，除第一个元素无直接前驱，最后一个元素无直接后续以外，每个数据元素有且仅有一个直接前驱元素和一个直接后继元素。

线性表的基本操作

还记得之前说过运算的定义依靠数据的逻辑结构实现，运算的实现针对于数据的存储结构吗？不过不记得你可以去看看数据结构入门篇

线性表是一种逻辑结构，因此具体操作我们是无法实现的，不过我们可以定义这些操作。

我们主要从参数，返回值来说一下基本操作吧

&L指传入一个引用，这个引用指向线性表表头

InitList(&L):
初始化表。构造一个空的线性表。
DestroyList(&L):
销毁操作。销毁线性表，并释放线性表L所占用的内存空间。 LocateElem(L,e):
按值查找操作。在表中L查找具有给定关键字值得元素。
GetELem(L,i):
按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e):
插入操作。在表L中的第i个位置上插入指定元素e。
LIstDelete(&L,i,&e):
删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L):
输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):
判空操作。若L为空表，则返回TRUE,否则返回FALSE。
Length(L):
求表长。返回线性表L的长度，即L中数据元素的个数。

以上就是线性表的对基本操作的定义，对这些操作的实现我们得依靠存储结构来说了。

线性表根据存储结构的不同又分为顺序表与链表，接下来我们就逐一说一下他们两个吧！

顺序表

顺序表就是线性表的顺序表示，它的主要特点是逻辑结构与存储结构相同都是连续的。

顺序表的定义

一组地址连续存放的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻

这样一说会感觉这个和数组十分相似啊。的确十分相似，但是却有所不同，详见下文。

顺序表与数组

相同之处：数组与线性表相同都是一组地址连续存放的存储单元依次存放元素

不同之处：数组下标从0开始，而顺序表下标从1开始。数组有最大存储空间是静态的，而顺序表可以是动态的。

定义的实现

顺序表定义的实现有两种分别是静态分配和动态分配。它们的区别是使用静态分配时顺序表的容量是被规定好的，无法增加的。使用动态分配时顺序表的容量可以变大。

实现数组静态分配：

# define MaxSize 100;
typedef struct{
	ElemType date[MaxSize];//ElemType是某种元素类型
	int length ;//顺序表长度
}sqList;//顺序表名字

我们使用结构体实现顺序表的定义，这里使用了某种类型的数组存放某种数据，数组容量为常量MaxSize。

实现数组动态分配：

# define MaxSize 100;
typedef struct{
	ElemType *date;
	int length;
}sqList;

动态分配语句：

C： L.data = (Elemtype*)malloc(sizeof(ElemType)*InitSize);
C++：L.data = new ElemType[InitSize]

顺序表的基本操作

顺序表的基本操作有插入，删除，查找

顺序表的插入

这个是给顺序表L在指定位置i处，插入元素e

bool ListInsert (SqList &L,int i,ElemType e){
//除去不合法的i，保证不能空下一个位置
//length+1是因为有可能最后一个位置插入
	if(i<1||i>L.length+1){
		return false;
	}
	if(i>=MaxSize){
		return false;
	}
	//每个元素向后移动给i-1下标位置空出来
	for(int j=L.length;j>=i;j--){
		L.date[j]=L.date[j-1];
	}
	L.date[i-1]=e;
	return true;
}

顺序表的删除

传入要删除的位置和一个元素的引用来保存要删除元素的值

bool ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length){
		return false;
	}
	//保存要删除的元素
	e=L.date[i-1];
	//后面的元素向前逐个移动
	for(int j=i;j<L.length;j++){
		L.date[j-1]=L.date[j];
	}
	L.length--;
	return true;
}

顺序表的查找

按值查找元素位置（位置从1开始）

int ListDelete(Sqlist L,ElemType e){
	int i;
	for(i=0;i<L.length;i++){
		if(L.date[i]==e)
			return i+1;
	}
	return 0;
}

如果是按位置查找直接L.date[i-1]即可得位置为i处的值是多少。

链表

链表我们最常见的就是单链表，除此之外还有一些特殊链表，我们重点还是说说单链表。

单链表的定义

单链表是线性表的链式存储，通过一组任意的存储单元来存储线性表中的数据元素，通过指针来实现逻辑关系

定义的实现

单链表的每一块都分为数据域和指针域，指针域用来存放逻辑上下一块内存的地址

typedef struct LNode{
	ElemType date;
	struct LNode *next;
}LNode,*LinkList;

链表又有两种，一种是有头结点的，一种是没有头结点的。我们为了提高效率一般使用带头结点的单链表，后面操作讲解也都是带头结点的链表。

头结点放在链表的最前面，结构与每一块结点相同，不过数据域中为空或者存放链表长度等重要元素，头结点的指针域指向链表的第一个元素。

使用头结点能帮助我们处理头部时方法与其他位置处理方法相同，操作时不需要判断是否为首元素了，大大提高了代码效率。

单链表的基本操作

单链表基本操作有：创建单链表，查找，插入和删除。

创建单链表

创建单链表我们分为头插法创建和尾插法创建，区别就是生成的链表顺序与插入时顺序是否相同。显然头插法创建单链表是顺序相同。
头插法
头插法就是每次插入元素时在链表的头结点后插入，最后生成的链表顺序与插入时顺序相反。

LinkList List_HeadInsert (LinkList &L){
	LNode *s;
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	scanf("%d",&x);
	while(x!=99999){
		s=(LNode*)malloc(sizeof(LNode));
		s->date=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}

尾插法
尾插法就是每次插入元素时在链表的末尾插入元素，最后生成的链表顺序与插入时顺序相同。

LinkList List_HeadInsert (LinkList &L){
	LNode *s,*r;
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	*r=L;
	scanf("%d",&x);
	while(x!=99999){
		s=(LNode*)malloc(sizeof(LNode));
		s->date=x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}

单链表的查找

查找又根据需求分为按序查找和按值查找。

按序查找

如果查找时需要查找某个位置元素的结点，那么就是按序查找。传入的参数为一个链表和需要查找的位置。

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

按值查找

如果需要在链表中查找某个值e的结点，则：

LNode *LocateElem(LinkList L,ElemType e){
	LNode *p=L->next;
	while(p!=NULL&&p->date!=e){
		p=p->next;
	}
	return p;
}

单链表的插入

插入有两种，第一种是插入到指定位置，第二种是默认在链表头部插入
插入到指定位置

要求插入到i位置处时，需要先找到i-1处的结点，然后插入

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

默认插入头部

在链表头部插入元素时：

s->next=head；
head=s;

单链表的删除

删除i位置的结点：

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

如果需要删除指定结点*q那么只需要：

q=p->next;
p->date=p->next->date;
p->next=q->next;
free(q);

特殊链表

特殊链表有：双链表，循环链表和静态链表。

双链表

双链表顾名思义就是比单链表高级了一点，一个双链表的结点在单链表的基础上又增加了一个指针，这个指针指向它的前一个结点
结点情况如下：

指针域	数据域	指针域
prior	date	next

定义的实现：

typedef struct DNode{
	ElemType date;
	struct DNode *prior,*next;
}DNode,*DLinklist;

结点发生改变了。对链表的一些操作也会发生改变
插入操作：

s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;

删除操作：

p->next=q->next;
q->next->prior=p;
free(q);

循环链表

之前的链表都是条状的，循环链表是头尾相连了，就是将链表的尾部与头部连接起来。有因为条状链表有单链表与双链表之分，所以循环链表也有两种分别是：循环单链表与循环双链表

对于循环单链表我们一般设置尾指针这样操作效率会更高。

对于循环双链表我们头结点的prior结点指向最后一个节点，尾结点的next指针指向头结点，以形成循环双链表。

之前的链表我们判断是否为空表都是看最后一个结点的next结点是否为空。显然，循环链表不可以这样判断，我们判断方式如下：

循环单链表判断空链表条件：

if(L->next==L)

循环双链表判断空链表条件：

if(L->next==L&&L->prior==L)

静态链表

静态链表这个名字听起来高大上，其实也是非常简单的，它和数组是非常相似的。先来看它的结构组成：

#define MaxSize 50
typedef struct DNode{
	ElemType date;
	int next;
}SLinkList[MaxSize];

它其实就是一个数组只不过不连续而已，结点分为两部分。date域存放数据，而next域存放下一个存放数据的数组的下标。

使用数组下标索引实现了逻辑结构。

线性表的常用操作

到此为止我们已经学过了线性表按照存储结构不同的两种分类，分别是顺序表与链表，以及他们的一些基本操作。但是在我们以后在做题时候，不会直接来考插入，删除等操作，它们都是贯穿在很多的大的操作中去的，我愿把他们称为非基本操作。。

下面我们来讲一下对于线性表的一些常考的操作分别是：最值，逆置，归并

最值

最值顾名思义就是求出线性表中的最大以及最小值，我们分别用顺序表与链表实现。

顺序表实现：

int min = L[0];
int max = L[0];
for(int i = 0; i < n; i++){
	if(min > L[i])
		min = L[i];
	if(max < L[i])
		max = L[i];
}

链表实现:

int min = p -> next ->data;
int max = p -> next ->data;
p = p -> next;
while(p != NULL){
	if(min > p ->data)
		min = p ->data;
	if(max < p ->data)
		max = p ->data;
	p = p ->next;
}

逆置

逆置就是把线性表中元素顺序调反

顺寻表实现

int i = 0;
int j = n-1;
while(i < j){
	temp = L[i];
	L[i] = L[j];
	L[j] = temp;
	i++;
	j--;
}

链表实现

//r为尾结点
while(p ->next != r){
	temp = p -> next;
	p -> next = temp -> next;
	temp -> next = r -> next;
	r -> next = temp;
}

归并

归并就是把两个线性表变为一个，这里其实又有两种了，一种是无序归并，还有一种是有序的归并。无序归并十分简单，这里就不说了，我们主要讲的就是有序归并。

有序归并的栗子：
L1=(1,8,6)
L2=(5,6,9)
归并后为：L3=(1,5,6,6,8,9)

顺序表实现

int i = 0, j = 0;
int k = 0;
for( ; i < L1_Size && j < L2_Size; k++){
	if(L1[i] < L2[j])
		L[k] = L1[i++];
	else
		L[k] = L2[j++];
}
while(i < L1_Size)
	L[k++] = L1[i++];
while(j < L2_Size)
	L[k++] = L2[j++];

链表实现归并

while(p->next!=NULL && q->next!=NULL){
	if(p->next->data < q->next->data){
		r->next = p->next;
		p->next= p->next->next;
		r = r->next;
	}
	else{
		r->next = q->next;
		q->next= q->next->next;
		r = r->next;
	}
}
if(p->next != NULL) r -> next = p ->next;
if(q->next != NULL) r -> next = q ->next;
free(p); 
free(q)

顺序表与链表的比较及选择

到这里我们的顺序表与链表就全部学习完了，那我们在什么时候应该选择顺序表，什么时候又该选择链表呢？我们对顺序表与链表做一个比较来看看吧！！

逻辑结构和物理结构

顺序表：

逻辑相邻物理上也相邻，通过相邻表示逻辑关系

单链表：

逻辑相邻物理上不一定相邻，通过指针表示逻辑关系

基本操作的时间复杂度
插入和删除：

单链表为O(1)(节点指针已知)；O(n)(节点指针未知)，但操作时只需修改指针

顺序表为O(n)且需要大量移动元素

查找：

按值查找中单链表和顺序表（无序）都为O(n)

按序查找中单链表为O(n)，顺序表为O(1)

内存空间
顺序存储：

无论静态分配还是非静态都需要预先分配合适的内存空间 静态分配时预分配空间太大回造成浪费，太小会造成溢出

动态分配时虽不会溢出但是扩充需要大量移动元素，操作效率低

链式存储：

在需要时分配结点空间即可，高效方便，但指针要使用额外空间

如何选择合适的线性表呢？

根据上面的比较做了以下选择总结：

问题情况	顺序表（较稳定）	单链表（较动态）
规模难以估计		*
存储密度大	*
按序号访问	*
插入与删除		*
基于数组	*
基于指针		*

结言

本来打算两天就总结一篇数据结构的，但是我大意了，写起来属实很费劲，很累，甚至一度向放弃。

But我是不会放弃的，下一篇栈与队列，敬请关注！

有问题请指正，感谢支持！