线性表

文中出现皆为伪代码，具体代码可见笔者github。整理辛苦，请勿转载
去tm的Github，目前本人很忙没时间去弄Github

一、线性表的逻辑结构

线性表是一种最简单的线性结构

线性结构的基本特征：

线性结构是一个数据元素的有序集

　　1.集合中必存在唯一的一个“第一元素”
　　

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

线性结构的最主要特征：

节点之间是一个一对一的关系

抽象数据类型线性表定义如下：

ADT List {
	数据对象：	
	D = { Ai | Ai 属于ElemSet , i = 1,2,….,n}	
		{ 称n为线性表的表长；称n ＝ 0 时的线性表为空表}
	数据关系：
	R1 = { <Ai-1, Ai> | Ai-1 , Ai 属于 D , i = 2,3,….,n}
		 { 称线性表为(A1,A2,…,Ai,…,An)，称 i 为Ai 在线性表中的位序}	 
	基本操作：
		1.结构初始化操作
		2.结构销毁操作
		3.引用型操作
		4.加工型操作
} ADT List

初始化操作：

1	InitList( &L )

　　操作结果：
　　
　　构建一个空的线性表L

结构销毁操作:

1	DestroyList( &L )

　　初始条件：
　　
　　　　线性表L已存在
　　
　　操作结果：
　　
　　　　摧毁线性表L （不仅仅销毁内容，这是和clear的区别，最重要的是结构没有了）

引用性操作:

ListEmpty( L ) ：判断是否为空
ListLength( L ) ：求该线性表的表长
PriorElem( L , cur_e, &pre_e) ：若L线性表存在，求当前元素的直接前驱是谁，并用其返回。
NextElem( L , cur_e, &next_e) ：若L线性表存在，求当前元素的直接后继是谁，并用其返回。
GetElem( L , i , &e) ：按序号查找的操作。即找到线性表L中第i个元素的值，并用e返回。
LocateElem( L , e , compare( ) ) ：按值查找的操作。即找到线性表L中第一个与e的值相等的元素，并返回其位置。
ListTraverse( L , visit( ) ) ：遍历操作。{
	初始条件：线性表L存在；
		visit( )为访问某个函数；
	操作结果：依次对L中每个元素调用函数visit( )。一旦visit( )，则操作失败。
}

加工型操作:

ClearList( &L ) ：清空所有的值
PutElem( &L , i , &e ) ：将第i个元素的值改为e
ListInsert( &L , i , e ) ：在线性表中第 i 个位置插入一个值e
ListDelete( &L , i , &e ) ：将线性表中第 i 个位置的值删除，删除的值用e返回

利用上诉定义的线性表类型，可以实现其他更复杂的操作。

有序表:

　　若线性表中的数据元素相互之间可以比较，并且数据元素在表中依值非递增或递减有序数列，则称之为有序表　　

二、线性表的线性储存结构

顺序映象:以x的储存位置和y的储存位置之间某种关系表示逻辑关系<x,y>

最简单的一种储存映象方法是：令y的储存位置和x的储存位置相邻。

顺序表:用一组地址连续的储存单元依次存放线性表中的数据元素

顺序表是一个随机存取结构

线性表的起始地址，称做线性表的基地址。

以“储存位置相邻”表示有序对< ai-1 , ai >

即：LOC( ai ) = LOC( ai-1 ) + C [C:一个数据元素所占储存量]

所有数据元素的储存位置均取决于第一个数据元素的储存位置。

即：LOC( ai ) = LOC( a1 ) + ( i - 1)*C [LOC( a1 ):基地址]

存取结构:与储存结构是两个不同的概念
存储结构:是这个数据结构在计算机中的表示
存取结构:是在一个数据结构上对查找操作的时间性能的一种描述

通常有两种存取结构：随机存取结构和顺序存取结构

随机存取结构:是指在一个数据结构上进行查找的时间性能是O(1)，即查找任一数据元素的时间是相等的，均为常数时间，例如顺序表是一种随机存取结构。
顺序存取结构:是指在一个数据结构上进行查找的时间是O(n)，即查找一个数据元素的时间是线性的，与该元素在结构中的位置有关，例如单链表是一种顺序存取结构。

===

顺序映像的C语言描述

===

[在线性表的静态分配顺序存储结构中，线性表的最多数据个数为LISTSIZE，元素数量不能随意增加，这是以数组形式描述线性表的缺点]

线性表的静态分配顺序存储结构

#define LISTSIZE 100 	//存储空间最大分配量
typedef struct {
	ElemType elem [LISTSIZE];
	int length;		//当前长度
}Sqlist;			//俗称—顺序表

[为了实现线性表最大存储数据元素数可随意变化，可以使用一个动态分配的数组来取代上面的固定长度数组，如下描述]

线性表的动态分配顺序存储结构

#define LIST_INIT_SIZE 100		//初始分配量
#define LISTINCREMENT 10		//分配增量
typedef struct {
	ElemType *elem;		//存储空间基地址
	int length;			//当前长度
	int listsize;		//当前分配的存储容量							//以sizeof(ElemType)为单位
}Sqlist

线性表的基本操作在顺序表中的实现:

1. InitList( &L )	//结构初始化
2. LocateElem( L , e , compare( ) )	//查找
3. ListInsert( &L , i , e )				//插入元素
4. ListDelete( &L , i , &e ) 			//删除元素

InitList( &L ) 的实现

//构造一个空表，这对表是一个加工型的运算，因此，将L设为引用参数。首先动态分布存储空间，然后，将length设为0，表示表中没有数据元素。
int InitList (Sqlist &L) {
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
	if( ! L.elme ) 
		exit (OVERFLOW);		//存储分配失败
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;	//初始存储容量
	return OK;
}

LocateElem( L , e , compare( ) )的实现:

线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。

顺序表中完成该运算最简单的方法是：从第一个元素a1起依次和x比较，直到找到一个和x值相等的元素，则返回它在顺序表中的存储下标或序号（两者差一）；或者查遍整个顺序表都没有与x相等的元素，则返回ERROR。

int LocateElem (Sqlist L, ElemType x) {
	i = 0;
	while ( i <= L.length && L.elem[ i ] ! = x ) {
		i++;
	}
	if( i > L.length - 1) {
		return ERROR;
	} else {
		return i;		//返回的是存储位置
	}
}

[本算法的主要运算是比较，显然比较的次数与x在表中的位置有关，也与表长有关。当a1 = x时，比较一次成功；当an ＝ x时，比较n次成功，按值查找的平均比较次数为（n + 1）/ 2 ，时间复杂度为O( n )。]

ListInsert( &L , i , e )的实现:

[分析] 插入元素时，线性表的逻辑结构发生什么变化？

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;
		//插入位置不合法
	}
	q = &( L.elem[ i - 1] );		// q表示插入位置
	p = &( L.elem[ L.length - 1] );
	for( ; p >= q ; - - p) {
		*(p+1) = *p;			// 插入位置及之后的元素右移
	}
	*q = e;					// 插入e
	++L.length;		// 表长增1
	return OK;
	if( L.length > L.listsize ) {
		return OVERFLOW;
		//当前存储空间已满
	}
}			//算法时间复杂度为O( ListLength( L ) )

ListDelete( &L , i , &e ) 的实现:

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

三、线性表的链式储存结构

单链表

　　定义：用一组地址任意的存储单元存放线性表中的数据元素。
　　
　　以元素(数据元素的映象) + 指针(后继元素的储存位置) ＝结点(表示数据元素或数据元素的映象)
　　
　　链表的定义：以结点的序列表示线性表
　　
　　以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。(头指针作为第一个结点的前驱)

　　有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为“头指针”。　　

可以说，头指针唯一确定了单链表。
当线性表为空表时，头指针的指针域为空

结点和单链表的C语言描述

typedef struct LNode {
	ElemType data;		//数据域
		struct LNode *next;		//指针域
	} LNode, *LinkList;
	
	
	LinkList L;				//定义一个L,L为单链表的头指针

单链表操作的实现

1.GetElem( L , i , &e )		//取第i个数据
2.ListInsert( &L , i , e )		//插入数据元素	3.ListDelete( &L , i , e )		//删除数据元素
4.ClearList( &L )			//重新置为一个空表
5.CreateList( &L , n )		//生成含n个数据元素的链表

GetElem( L , i , e )在单链表中的实现:

　　单链表是一种顺序存储结构，若要找到第 i 个数据元素，就必须先找到第 i-1个数据元素。
　　
　　因此，查找第 i 个数据元素的基本操作是：移动指针，比较 j 和 i 。
　　
　　令指针 p 始终指向现行表中第 j 个数据元素。　　

Status GetElem_L( LinkList L, int i, ElemType &e) {
// L是带头结点链表的头指针，e返回第 i 个元素
	p = L -> next;			//p指向第一个结点
	j = 1;				// j是计数器
	while ( p && 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))

ListInsert( &L , i , e )在单链表中的实现：

　　有序对<ai-1, ai>改变为<ai-1, e>和<e, ai>
　　
　　可见，在链表中插入结点，只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。
　　
　　因此，在单链表中第i个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。
　　

Status ListInsert_L (LinkList &L, int i, ElemType e) {
//L是带头结点链表的头指针
//在链表中第i个结点之前插入新的新的元素e
	p = L;
	j = 0;
	while ( p && j < i-1) {
		p = p -> next;		//寻找第i-1 个结点
		++j;
	}
	if( !p || j > i -1) {
		return ERROR;	// i大于表长或小于1
	}
	s = new LNode;
	if( s == NULL) {
		return ERROR;
	}
	s -> data = e;			//生成新节点
	s -> next = p -> next;	//“->next” 在赋值号右侧出现，可以理解为指针域；在左侧出现，可以理解为地址。
	p -> next = s;			//插入
	return OK;
}					//算法时间复杂度为O(ListLength(L))

[分析] 此算法时间复杂度为O(n)，顺序表的插入算法时间复杂度也为O(n)。但为什么单链表的插入好于顺序表呢？因为单链表的O(n)是比较操作，而顺序表的O(n)为移动操作，对于计算机来说，比较操作不知道比移动操作快到哪里去了，所以单链表的插入操作算法强于顺序表的插入操作算法。

前插结点：设 p 指向链表中的某个结点，s指向带插入的值为x的新结点，将s插入到p的前面，与后插不同的是：首先要找到p的前驱q，然后再完成在q之后插入s，设单链表头指针为L。

q = L;
while ( q -> next < p) {
	q = q -> next;
}				//找*p的直接前驱
s -> next = q -> next;
q -> next = s;
//前插操作因为要找*p的前驱，时间复杂度为O(n)
//其实前插操作也可以用后插操作来实现，即将*s插入到*p的后面，然后将 p ->data 与 s ->data 交换即可。

ListDelete( &L , i , e )在单链表中的实现:

　　在单链表中删除第 i 个结点的基本操作为：找到线性表中第 i-1 个结点，修改其指向后继的指针.
　　

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;
	delete(q);		//删除并释放结点
	return OK;
}				//时间复杂度为O(n)

ClearList( &L )在单链表中的实现：

		
void ClearList_L ( &L ) {
//将单链表重新置为一个空表
	while(L->next) {
		p = L ->next;
		L ->next = p ->next;
		delete(p);
	}
}			//时间复杂度为O(n)

如何从线性表得到单链表：

　　链表是一个动态的结构，它不需要预分配空间。因此生成链表的过程就是结点“逐个插入”的过程。
　　
构造单链表的两个方法：

　　1.头插法
　　
　　2.尾插法　　

头插法:

　　　　逆序输入n个数据元素的值，建立带头结点的单链表。即新的元素在单链表的首位。
　　
　　　　eg：元素1，2，3，4，5；头插结果：5，4，3，2，1

操作步骤：1.建立一个空表
		2.输入数据元素an，建立结点并插入
		3.输入数据元素an-1，建立结点并插入
		4.依次类推，直到输入a1为止

void CreateList_L (LinkList &L, int n) {
//先建立带头结点的单链表
//先建立一个带头结点的单链表
	L = new LNode;
	L ->next = NULL;
	for( i = n , i > 0; - - i) {
		p = new LNode;
		scanf(&p -> data);		//输入元素值
		p ->next = L ->next;
		L ->next = p;			//插入
	}
}						//时间复杂度为O(n)

尾插法:

　　　　正序输入n个数据元素的值，建立(不)带头结点的单链表。即新的元素在单链表的末位。
　　　　

LinkList Create_LinkList( ) {
//无头结点的单链表
	LinkList L = NULL;
	LNode *s, *r = NULL;
	int x;
	scanf(“%d”,  &x);			//设数据结构元素类型为int
	while( x != flag) {
		s = (LNode *)malloc(sizeof(LNode));
		s -> data = x;
		if(L = NULL) {
			L = s;			//第一个结点的处理
		} else {
		r -> next = s;		//其它结点的处理
		}// if
		r = s;				// r 指向新的尾结点	
		scanf(“%d”, &x);
	}// while
	if(r != NULL) {
		r -> next = NULL;		//非空表最后结点的指针域为空
	}// if
	return L;
}// Create_LinkList

LinkList Create_LinkList ( ) {
//建立带头结点的单链表
	LinkList L = (LNode *)malloc(sizeof(LNode) );
	L -> next = NULL;				//空表
	LNode *r, *s = L;
	int x;
	scanf(“%d”, &x);
	while(x != flag) {
		s = (LNode *)malloc(sizeof(LNode));
		s -> data = x;
		r -> next = s;
		r = s;					//r指向新的尾结点
		scanf(“%d”, &x);
	}// while
	r -> next = null;
	return L;
}// Create_LinkList

头结点有哪些优点：

1.由于开始结点的位置被存放在头结点的指针域中，所以在连表的第一个位置上的操作和对其他位置的操作一致，无需进行其他特殊处理。

2.无论链表是否为空，其头指针是指向头结点的非空指针（空表中的头结点的指针域为空），因此空表和非空表的处理也就统一了。

四、其他形式的链表

双向链表

typedef struct DuLNode {
	ElemType data;				//数据域
	struct DuLNode *prior;		//指向前驱的指针域
	struct DuLNode *next;		//指向后继的指针域
}DuLNode, *DuLinkList;

循环链表

　　最后一个结点的指针域的指针又指回第一个结点的链表
　　
　　和单链表的差别仅在于，判断连表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。
　　
　　对于单链表只能从头结点遍历整个链表，而单循环链表则可以从表中任意结点遍历链表。

　　不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。　　

双向循环链表

　　特点：
　　
　　　　1.“查询”和单链表相同；
　　　　
　　　　2.“插入”和“删除”时需要同时修改两个方向上的指针；
　　　　　
插入的实现

//假设插入为s，p为ai-1
s -> next = p -> next;
p -> next = s;
s -> next -> prior = s;
s -> prior = p;

删除的实现

1
2
3

//删除ai，p为ai-1
p -> next = p -> next -> next;
p -> next -> prior = p;

静态链表

　　借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组的下标），称之为静态链表
　　
　　特点：
　　
　　　　1.所有数据元素均存储在一个连续的空间段，但是相邻的两个元素不一定处在相邻的空间。
　　　　
　　　　2.修改指针域即可完成插入和删除操作，不需要移动数据元素，但是也不能随机访问静态链表中的元素。
　　　　
　　　　3.一次性分配所有存储空间，插入、删除时无需再向操作系统申请或释放空间，但同时也限制了链表的最大表长。

线性表的静态单链表存储结构

#define MAXSIZE 1000
typedef struct {
	ElemType data;
	int next;
} component, SLinkList[MAXSIZE];

　　静态链表适用于不包含“指针”的高级语言，或者最大元素数固定并且插入删除元素操作频繁的链表中。有关基于静态链表上的线性表的操作基本与动态链表相同除了一些描述方法有些区别外，算法思路是相同的。　　

五、[总结]顺序表和链表的比较

顺序表和链表各有优缺点

顺序表的优点:

　　1.方法简单，各种高级语言中均有数组，容易实现。

　　2.不用为表示结点间的逻辑关系而增加额外的存储开销。

　　3.顺序表具有按元素符号随机访问的特点. 　　

顺序表的缺点

　　1.在顺序表中做插入、删除操作时，平均移动大约表中一半的元素，因此n较大的顺序表效率低。

　　2.需要预先分配足够大的存储空间，估计大了，可能会导致顺序表后部大量闲置；分配小了，又会造成溢出。

链表的优缺点恰好与顺序表相反

六、在实际中怎样选择存储结构？

基于存储的考虑

顺序表在程序执行之前，必须明确规定它的存储规模，也就是说事先要对[MAXSIZE]有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表。

链表不用事先估计存储规模，但链表的存储密度较低，显然链表的存储密度是小于1的。

存储密度：假设分母是整个结点的大小，分子是数据域所占的空间。

基于运算的考虑

在顺序表中按序号访问ai的时间复杂度是O(1)，而链表中按顺序访问的时间复杂度是O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优先于链表。但如果经常做的运算是插入和删除，则后者优于前者，原因见上文。

基于环境的考虑

顺序表容易实现，任何高级语言都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。

总之，两种存储结构各有长短，选择哪一种由实际问题中的主要元素决定。通常“较稳定”的线性表用顺序存储，而频繁做插入删除的即动态性较强的线性表应选择链式存储。

七、线性表的逆置

逆置SqList

　　就是数组转置，略

逆置LinkList

基本操作：
	1.标志后继结点
	2.修改指针，即将*p插入到头结点之后
	3.重置结点*p，即使p重新指向原表中后继

实现

void inverse (LinkList &L) {
//逆置带头结点的单链表L
	p = L -> next;
	L -> next = NULL;
	while( p ) {
		succ = p -> next;		//succ指向p的后继
		p -> next = L -> next;
		L -> next = p;			// *p插入在头结点的后面
		p = succ;
	}
}

八、章节总结

1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。重点掌握：初始化、查找、插入、删除、遍历、逆置、合并、分解等操作。

3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点以及试用场合。

SaberDa的幻想乡

C++/ JS　　|　　呐呐呐　　|　　gli97@gwmail.gwu.edu　　|　　没有什么胜利可言挺住就意味着一切