线性表——静态链表的设计思路与实现

总的实现代码如下：

/*
静态链表不同于动态链表，
静态链表没有物理空间上的连续，
它的元素的顺序是理论空间上的连续,
所以它失去了顺序储存结构随机存取的特性 
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXSIZE 260

typedef int ElemType, Status;

typedef struct Node{
	ElemType data;		//数据域 
	int cur;			//cursor 游标，指针域, cur为0时表示无指向 
}Component, *StaticLinkList;

int ListLength(StaticLinkList L)			//查询静态链表的长度 
{
	int length = 0;
	int i = L[MAXSIZE - 1].cur;
	while(i)
	{
		i = L[i].cur;
		length++;
	}
	return length;			
}

void PrintList(StaticLinkList L)
{
	int i = L[MAXSIZE - 1].cur;
	while(i)
	{
		printf("%-5d\n", L[i].data);
		i = L[i].cur;
	}
	return;
}

bool EmptyList(StaticLinkList L)				//查询静态链表是否为空 
{
	if(L[MAXSIZE - 1].cur == 0)
	    return true;
	return false;
}

bool FullList(StaticLinkList L)					//查询静态链表是否已满 
{
	if(ListLength(L) == MAXSIZE - 1)
	    return true;
	return false;
}

int GetElem(StaticLinkList L, ElemType e)		//按值查找
{
	int i = L[MAXSIZE - 1].cur, k = 0;
	while(i)
	{
		k++;
		if(e == L[i].data)
			return k;
		
		i = L[i].cur;
	}
	return -1; 
}

bool GetLocation(StaticLinkList L, int location, ElemType *data)			//按位置查找 
{
	if(location < 1 || location > ListLength(L))
    {
    	data = NULL;
    	return false;
	}
	int i = L[MAXSIZE - 1].cur, j = 0;
    for(j = 1; j < location; j++)
	    i = L[i].cur;
	*data = L[i].data;
    return true;
}

StaticLinkList InitLinkList(StaticLinkList space)			//初始化静态链表 
{
	space = (StaticLinkList)malloc(sizeof(Component));
	if(space == NULL)
	    return NULL;
	int i;
	for(i = 0; i < MAXSIZE - 1; i++)
	    space[i].cur = i + 1;
	space[MAXSIZE - 1].cur = 0;			//游标最后一位初始化，即单链表的尾指针NULL 
	return space;
}

int Malloc_SSL(StaticLinkList space)		//储存未被使用的节点的游标, 实现malloc函数 
{
	int i = space[0].cur;
	if(space[0].cur)
	    space[0].cur = space[i].cur;
	return i;
 } 
 
bool ListInsert(StaticLinkList L, int i, ElemType e)		//插入元素的操作
{
	int k = MAXSIZE - 1;
	if(i < 1 || i > ListLength(L) + 1 || i > MAXSIZE - 1)
	{
		return false;
	} 
	int j = Malloc_SSL(L), l;
	if(j)
	{
		L[j].data = e;
		for(l = 1; l <= i - 1; l++)
		    k = L[k].cur;
		L[j].cur = L[k].cur;
		L[k].cur = j;
	}
	return true;
}

void AddList(StaticLinkList L, ElemType arr[], int num)
{
	int i;
	for(i = 1; i <= num; i++)
	    L[i].data = arr[i - 1];
	L[0].cur = num + 1;
	L[num].cur = 0;
	L[MAXSIZE - 1].cur = 1;
	return;
}

void Free_SSL(StaticLinkList space, int k)			//实现空间的释放， 模拟free函数 
{
	space[k].cur = space[0].cur;
	space[0].cur = k;
}

bool ListDelete(StaticLinkList L, int i)			//删除某个位置的元素, 按位删除, i位所删除的位置 
{
	if(i < 1 || i > ListLength(L))
		return false;
	int j, k = MAXSIZE - 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;
} 

void ClearList(StaticLinkList L)
{
	L[MAXSIZE - 1].cur = 0;
}

void Destroy(StaticLinkList L)
{
	free(L);
	L = NULL;
}

void ChangeElem_StaticLinkList(StaticLinkList L, int i, ElemType e)			//将指定位置的值修改 
{
	int j, k = L[MAXSIZE - 1].cur;
	for(j = 1; j <= i; j++)
	    k = L[k].cur;
	L[k].data = e;
	return;
}

int main()
{
	return 0;
}