[数据结构与算法]02_线性表

一、线性表的定义

线性表：零个或多个数据元素的有限序列。

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

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

1.定义

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

2.存储方式

线性表的每个数据元素的类型形同，所以可以用C语言的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中的相邻位置。描述顺序存储结构需要三个属性：
（1）存储空间的起始位置:数组data，它的存储位置就是存储空间的存储位置
（2）线性表的最大存储容量：数组长度MaxSize
（3）线性表的当前长度：length

#define MAXSIZE	20 /* 存储空间初始分配量 */
typedef	int ElemType;
typedef struct
{
	ElemType data[MAXSIZE];
	int length;
}SqList;

3.地址计算

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

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

1.获得元素

获取第i个元素，只要将第i-1个下标的值返回即可。

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

2.插入元素

插入算法的思路：

• 如果插入位置不合理，抛出异常
• 如果线性表的长度大于或等于数组的长度，则抛出异常或者动态增加容量
• 从最后一个开始向前遍历到第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-1;k>=i-1;k--) /* 将要插入位置后数据元素向后移动一位 */
		{
			L->data[k+1] = L->data[k];
		}
	}
	L->data[i-1] = e; /* 将新元素插入 */
	L-length++;
	return OK;
}

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) /* 删除位置不正确 */
		return ERROR;
	*e = L->data[i-1];
	if(i<L->length)
	{
		for(k=i;k<L->length;k++)
			L->data[k-1] = L->data[k];
	}
	L->length--;
	return OK;
}

4.小结

如果元素插入到最后一个位置或者删除最后一个元素，此时的时间复杂度为O(1),因为不需要移动元素；如果元素插入到第一个位置或者删除第一个元素，此时的时间复杂度为O(n)。可推导出平均时间复杂度还是O(n)。这说明线性表的顺序存储结构，在存、读取数据时，不管在哪个位置，时间复杂度都是O(1)；而在插入或删除数据时，时间复杂度都是O(n)。因此，它比较适合元素不太变化，而更多是存取数据的应用。

5 优缺点

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除元素时需要移动大量的元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

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

1.定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据可以存储在内存未被占用的任意位置。在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为称为指针域。这两部分信息组成数据元素的存储映像，称为节点。
把链表中的第一个节点的存储位置叫做头指针，最后一个节点的指针为“空”。有时为了更加方便地对链表进行操作，会在单链表的第一个节点之前设置一个节点，称为头节点（是不是也可以叫做根根节点？）。头节点的数据域不存储任何信息，可以存储如线性表的长度等附加信息，头节点的指针域存储指向第一个节点的指针。

2.头指针和头节点的异同

头指针：

• 头指针是指向链表第一个节点的指针，若链表有头节点，则指向头节点。
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头节点：

• 头节点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域无意义（也可以放链表的长度）
• 有了头节点，对在第一元素节点前插入节点和删除第一节点，其操作与其他节点就统一了
• 头节点不是链表的必要元素

3.代码描述

/* 线性表的单链表存储结构 */
typedef struct Node
{
	ElemType	data;   /* 数据域 */
	struct Node *next; /* 指针域 */
};

五、单链表的读取

在线性表的顺序存储结构中，计算任意一个元素的存储位置是很容易的，但在链表中，由于第i个元素一开始在哪没办法一开始就知道，必须得从头开始找，因此在算法实现上相对要难一些。
获得链表第i个数据的算法思路：
（1）声明一个节点p指向链表的第一个节点，初始化j从1开始
（2）当 j<i 时，就遍历链表，让p的指针向后移动，不断指向下一个节点，j累加1
（3）若遇到链表末尾p为空，则说明第i个元素不存在
（4）否则查找成功。返回节点p的数据

代码实现如下（核心思想是工作指针后移）：

/*  初始条件：顺序线性表:已存在，1<=i<=ListLength(L) */
/*  操作结果：用e返回L中第i个元素数据的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
   int j;
   LinkList p; /* 声明一节点p*/
   p = L->next; /*  让p指向链表L的第一个节点 */
   j=1;  /* j为计数器 */
   while(p && j < i)  /* p不为空指针或者计数器j还没有等于i时，循环继续 */
   {
   		p=p->next;  /* 让p指向下一个节点 */
   		++j;
   }
   if(!p || j > i)
   	return ERROR;  /* 元素不存在 */
   *e = p->data; /* 读取第i个元素的数据 */
   return OK;
}

六、单链表的插入和删除

1.单链表的插入

不用修改其他节点，只需要改变s->next和p->next的指向即可，具体如下：

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

注意：这条语句不能交换顺序

单链表第i个数据插入节点的算法思路：
（1）声明一节点p指向第一个节点，初始化j从1开始
（2）当 j < i 时就遍历链表，让p的指针往后移动，j的值累加1
（3）若到链表的末尾p为空，则说明第i个元素不存在
（4）否则查找成功，在系统生成一个节点s
（5）将数据元素e赋值给s->data
（6）单链表的插入标准语句：s->next = p->next;p->next = s;（顺序不能交换）
（7）返回成功

代码实现如下：

/* 初始化条件：顺序线性表L已经存在，1<=i<=ListLength(L) */
/* 操作结果：在L中第i个位置之前插入新的元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
	int j;
	LinkList p,s;
	j=1;
	while(p && j < i)
	{
		p=p->next;
		++j;
	}
	if(!p && j > i)
		return ERROR;
	s = (LinkList*)malloc(sizeof(node));  /* 生成新节点 */
	s->next = p->next;
	p->next = s;
}

2.单链表的删除

如图，若要删除节点q，则只需执行如下操作：

q = p->next;
p->next = q->next;

这两句代码是将p的后继节点改成q的后继节点，这里是不是可以合并成一句？

p->next = p->next->next;

单链表第i个数据删除节点的算法思路：
（1）声明一节点p指向链表的第一个节点，初始化j从1开始
（2）当 j < i时，就遍历链表，让p的指针向后移动，j累计1
（3）若到链表末尾 p为空，则说明第i个元素不存在
（4）否则查找成功，将要删除的节点p->next赋值给q
（5）单链表的删除标准语句是p->next = q ->next;
（6）将节点q中的数据赋值给e作为返回
（7）释放q节点
（8）返回成功

/* 初始化条件：顺序线性表L已经存在，1<=i<=ListLength(L) */
/* 操作结果：删除第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while(p->next && j < i)
	{
		p=p->next;
		++j;
	}
	if(!(p->next) || j > i)
		return ERROR;
	q = p->next;
	p->next = q->next;
	*e = q->data;
	free(q); /* 让系统回收此节点，释放内存 */
	return OK;
}

3.小结

分析单链表的插入和删除可以发现，它们都是由两部分组成：第一部分是遍历查找第i个元素，第二部分就是插入和删除元素。从整体算法上来说，它们的时间复杂度都是O(n)。如果我们在不知道第i个元素的指针位置，单链表数据结构在插入和删除上，与线性表的顺序存储结构没有太大的优势。但如果，我们希望从第i个位置插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-1个元素，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越明显 。

六、单链表的整表创建

单链表整表创建的算法思路：
（1）声明一个节点p和计数器变量i
（2）初始化一空链表L
（3）让L的头节点的指针指向NULL，即建立一个带头节点的单链表
（4）循环：
a.生成一新节点赋值给p
b.随机生成一数字赋值给p的数据域p->data
c.将p插入到头节点与前一新节点之间

实现代码如下：

void CreateListHead(LinkList *L,int n)
{
	LinkList p;
	int i;
	srand(time(0));  /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;  /* 先建立一个带头节点的单链表
	for(i=0;i<n;i++)
	{
		p = (linkList)malloc(sizeof(Node));  /* 生成新节点 */
		p->data = rand()%100+1;  /* 随机生成100以内的数字*/
		p->next = (*L)->nextl
		(*L)->next = p;  /* 插入到表头 */
	}
}

如果把新节点插入到最后，代码实现如下：

void CreateListTail(LinkList *L,int )
{
	LinkList p,r;
	int i;
	srand(time(0));  /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(None));
	r = *L;  /* r为指向尾部的节点 */
	for(i=0;i<n;i++)
	{
		p = (Node*)malloc(sizeof(None));  /* 生成新节点 */
		p->data = rand()%100+1;
		r->next = p;  /* 将表尾终端节点的指针指向新节点 */
		r = p;  /* 将当前的新节点定义为表尾终端节点 */
	}
	r->next = NULL;  /* 表示当前链表结束  */
}

七、单链表的整表删除

单链表整表删除的算法思路如下：
（1）声明一个节点p和q
（2）将第一个节点赋值为p
（3）循环
a.将下一节点赋值给q
b.释放p
c,将q赋值给p

代码实现如下：

Status ClearList(LinkList *L)
{
	LinkList p,q;
	p = (*L)->next;  /* 指向第一个节点 */
	while(p)   /* 没到表尾 */
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return OK;
}

八、单链表结构和顺序存储结构的优缺点

1.存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

2.时间性能

（1）查找

• 顺序结构：O(1)
• 单链表：O(n)

（2）插入和删除

• 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
• 单链表在找出某位置的指针后，插入和删除时间仅为O(1)

3.空间性能

• 顺序存储结构需要预分配存储空间，分大了浪费，分小了会发生上溢
• 单链表不需要分配存储空间，只要有可以分配，元素个数也不受限制

4.小结

• 若线性表需要频繁查找，很少进行插入和删除操作，宜用顺序存储结构。若需要频繁插入和删除，宜用单链表结构。
• 当线性表中的元素个数变化较大或者根本不知道多大时，最好用单链表结构，这样可以不用考虑存储空间的大小问题。

总之，线性表的顺序存储结构和单链表各有优缺点，要综合平衡采用哪种数据结构更能满足和达到需求和性能。

九、循环链表

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

其实循环链表的单链表的主要差异就在于循环条件的判断条件上，原来是判断p->next是否为为空，现在则是p->next是否等于头节点。

十、双向链表

1.定义

双向链表是在单链表的每个节点上，再设置一个指向其前驱节点的指针域。

/* 线性表的双向链表存储结构 */
typedef struct DulNode
{
	ElemType data;
	struct DulNode *prior;
	struct DulNode *next;
}DulNode,*DuLinkList;

同样，双向链表也可以是循环表。

2.插入数据元素

双向链表是由单向链表扩展而来的，因此很多操作和单向链表是相同的。

代码实现如下：

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

3.删除数据元素

代码实现如下：

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

相比于插入，删除要简单很多。

4.小结

双向链表相比于单链表要复杂一些，逼近它多了prior指针。另外由于它的每个节点都要记录两个指针，所以在空间上要多占用一些。不过，由于它的良好的对称性，给某个节点的前后节点的操作带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。