线性表——静态链表

前言：

  其实C语言真是好东西，它具有一定的指针能力，这使得我们能够非常容易地操作内存中的地址和数据，这比其它的高级语言更加的灵活方便，后来面向对象的语言，例如Java，C#等，虽然他们不使用指针，但是因为是启用了对象引用机制，从某种角度来讲也间接实现了指针的某些作用，但是如Basic ，Fortran等早期的编程高级语言，由于没有指针，链表结构按照我们前面的做法，就没有办法实现了。那么怎么办呢？

   有人脑洞大开，既然我们没有指针，那么我们可以避其短处，我们采用数组来代替指针来描述单链表，真实不得不佩服他们的智慧，我们来看看他们是怎么做到的。

解决思路：

  首先为什么叫他静态链表呢？顾名思义——他肯定不是通过malloc或者new来申请堆空间，更何况堆空间的申请需要指针的帮助，所以呢我们这里还是通过数组来解决：每个数组元素的内容都包括两部分，①data存放数据②cur存放下一个数据的数组下标（相当于*next）。我们把这种通过数组描述的链表叫做静态链表（也称为：游标实现法）。

  通常情况下我们为了方便插入数据，我们通常会把数组建立的大一些，以便有闲暇空间可以存储，不至于溢出。

/*线性表的静态链表储存结构*/
#define MAXSIZE 100
typedef int Elemtype;
typedef struct
{
	Elemtype data;
	int cur;
}Component,StaticLinkList[MAXSIZE];

  特殊处理：数组的第一个元素和最后一个元素不存数据，我们通常将未被使用的数组元素成为备用链表。而数组的第一个元素（即下标为0）的元素的cur存放备用链表的第一个节点的下标；数组的最后一个元素的cur则存放第一个有数据元素的下标，相当于链表中头节点的作用。整个链表的结构如下图：

 

  假设我们已经将数据存放进入静态链表中了，比如分别存放着“甲”，“乙”，“丁”，“戊”，”己“，”庚“呈现出下图的状态：

  此时：甲存有下一个数据的下标2，乙存3，丁存4....庚为最后一个元素，cur设置为0。第一个元素的cur存放7。最后那个呢存放1。

 

静态链表的操作：

  1  插入操作：

      静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，不需要时释放。这需要我们设计一个函数来模拟malloc和free。同时呢为了辨明数组中那些分量未被使用？解决办法是：将所有未被使用过的及已被删除的分量用游标来链接成一个备用链表，每当经行插入时我们可以从备用链表中取第一个节点作为带插入的新节点。

/*若备用空间链表非空，则返回分配节点的下标，否则返回0*/
int Malloc_SLL(StaticLinkList space)
{
	int i = space[0].cur;//返回第一个备用空间的下标

	if(space[0].cur)//还有空间
	{
		space[0].cur = space[i].cur;//更新首元素cur
	}
	return i;
}

  这段代码的作用是：返回数组头元素的cur域值，也就是下一个可用的节点空间。实现了malloc的功能。

 

  现在如果需要在”乙“，“丁”之间插入一个值为”丙“元素，按照以前的手法是将包括丁之后的元素全部向后移动一个位置，但是现在不用，因为我们有新手段。

     新元素”丙“想插队是吧？可以，你先悄悄地在队伍最后一排第七个游标位置待着，我们找到”乙“，告诉他你的cur不是3，而是7，同时呢你告诉”丙“你的cur不是8是3。这样我们就实现了不移动数组元素的插入手法。

/*在L中的第i个元素之前插入新的元素e。*/
bool ListInsert(StaticLinkList L , int i , Elemtype e)
{
	int j,k,l;
	k = MAX_SIZE - 1;//k是最后一个元素的下标

	if(i<1 || i<ListLength(L)+1)
		return false;

	j = Malloc_SSL(L);//获得可用空间的下标
	if(j)
	{
		L[j].data = e;
		for(l = i;i<=i-1;++l)//找到第i个元素之前的位置
			k = L[k].cur;

		L[j].cur = L[k].cur;//将第i个元素的cur赋值给新元素
		L[k].cur = j;//将新元素的下标给第i之前的元素cur

		return true；
	}
	return false；
}

 

静态链表的删除操作：

  如果甲接到一个非常紧急的电话，他需要离开，那么它所占的空间需要释放，和前面的元素一样，原来是需要free来释放节点，那么我们同样也许自己来实现。

/*删除在L中的第i个节点元素e */
bool ListDelete(StaticLinkList L ,int i)
{
	int j,k;

	if(i<1 || i> ListLength(L))
		return false;

	k = MAX_SIZE -1;

	for(j = 1;j<= i-1 ;++j)
	{
		k = L[k].cur;
	}

	j = L[k].cur;
	L[k].cur = L[j].cur;
	Free_SSL(L,j);//回收函数

	return true;
}

 

  有了刚才的基础这段代码不难看懂，所以呢我们来实现Free_SSL函数和ListLength函数。

/*将下标为k的空闲节点回收到备用链表中*/
void Free_SSL(StaticLinkList space ,int k)
{
	space[k].cur = space[0].cur;
	space[0].cur = k;
}
/*初始条件：静态链表L已经存在。返回L中的数据个数*/
int ListLength(StaticLinkList L)
{
	int j = 0;
	int i = L(MAX_SIZE-1).cur;
	while(i)
	{
		i = L[i].cur;
		++j;
	}
	return j;
}

 

总结：我们对静态链表进行评价：

  优点：再插入和删除时，只需要修改游标，不需要移动元素，从而改进了在顺序表中的插入和删除操作的移动大量元素的缺点。

        缺点：1.没有解决连续分配带来的表长难以确定的问题

                   2.失去了顺序表随机存取的特性。