静态链表

我在《 数据结构 第二章 :双链表，循环链表，静态链表以及对比总结》，初步认识了静态链表。

第一次去理解代码，其实有一点点费力。但是也不是那么复杂，主要抓住下面这一点

静态链表：分配一整个连续内存空间每个节点，每个节点集中安置；静态链表中没有用指针，但是数组的索引值 Index充当了指针的作用。

静态链表就是为那行没有指针的编程语言二存在的，存储数据用的是连续的空间，但是逻辑上连续的空间，在物理上无需连续，还是抓住了链表的特点。

typedef struct 
{
    ElemType data;
    int cur;//其实可以把它看着指针，指针也不少一个数吗？
}SLinkList[MaxSize];

cur: 就是下一个结点的数组下标，其实可以把它看着指针，指针也不少一个数吗？

算法解析

第一次实现静态链表，我面对的一个问题就是 如何寻找到没有使用的数据结点，我给出的解决方案是：

• cur = 0，表示结尾
• cur =MaxSize ，表示没有使用该段空间

所以需要开辟一个没有存储数据（插入结点等操作需要开辟空间）的结点就需要使用循环扫描出cur== MaxSize 的结点（没有使用的结点）。

有没有不需要循环的方法呢？当然是有的，我们来看看书上的一个例子。

题目

实现集合运算 $(A-B)U(B-U)$ 来讨论静态链表的算法。

初步理解

为了更好的理解，我想提讲述出它的具体原理

在静态链表中 存着两个链表

1. 链表1（备用链表）. 头节点 为 SLinkList[0],存储着没有数据的结点
2. 链表2（数据链表）. 头结点为 SLinkList[1] （也可以不是 SLinkList[1] ，只要是空闲结点就可以了）,存储着有数据的结点，

当然它是如何他是如何存储两个链表在一个数组中呢？

回想我们单链表是如何找到链表的呢？ 找到头结点

那很简单，我们也只需要规定， L[0]为备用链表的头结点，L[1]为存储数据的头结点

开辟一个存储数据的结点：从备用链表中取出-->一个结点到数据链表中

删除回收一个存储数据的结点：从将被删除的结点-->插入到备用链表中

是不是很有启发性呢，经典的空间换取时间，当然我们这样多花费了1个空间（备用链表的头结点），就避免了时间复杂度为O(n)的大循环。

代码

InitSpace _SL

函数功能：初始化链表，由于此时没有存储数据，其实就是创建 备用链表

void InitSpace _SL(SLinkList &space)
{
    for(i=0;i<MaxSize-1;i++) //数组下标从0开始，只需要循环到 MaxSize-2
        space[i].cur=i+1;
    space[MaxSize - 1]==0;//0表示NULL ,space[MaxSize - 1]也就是 备用链表的尾结点
}

如上图，每个cur指向下一个结点。

Malloc_SL

函数功能：从备用链表中取出（拿出来并在备用链表中删除）一个可以存储数据的新结点，返回其的数组下标（地址），返回0表示分配空间失败

int Malloc_SL(SLinkList &space)
{
    i=space[0].cur;//备用链表的第一个结点取出
    if(space[0].cur)//如果 space[0].cur==0 说明备用链表被使用完了，分配空间失败
        space[0].cur=space[i].cur;//将取出的结点从备用链表中删除
    return i;
}

Free_SL

函数功能： 将被删除的结点k,连接到备用链表的头结点之后（回收K结点）

Free_SL(SLinkList &space ,int k)
{
    space[k].cur=space[0].cur;sapce[0].cur=k;
}

画的太丑了

difference

函数作用：依次此输入 A,B的元素，计算$(A-B)U(B-U)$， ，计算结果到space ,S返回数据链表的头结点。

此函数使用许多功能，插入元素，删除元素等功能都在这里有体现

当然你要理解 $(A-B)U(B-U)$

void difference(SLinkList &space,int &S)
{
	InitSpace_SL(space);   //初始化静态链表（创建备用链表）
    S=Malloc_SL(space);    //生成数据链的头结点
    r=S;                   //r为当前A集合链表的表尾
    scanf(m,n);           //输入数据链表的大小 m :A  n: B
    //生成链表A,并填入数据 
    for(j=1;j<=m;++j)
    {
        i=Malloc_SL(space);
        Scanf(space[i].data);//输入数据 
        space[r].cur=i;      //插入数据到数据链表
        r=i;                 //r为当前A集合链表的表尾
    }
    space[r].cur=0;          //数据链尾结点为NULL(0)
    for(j=1;j<=n;j++)
    {
        scanf(b);
        p=S;  //p存储着要删除结点前驱结点
        k=space[S].cur; //k指向集合A元素的下一个结点
        //遍历A集合 数据b是否也在A中（是否重复）
        while(k!=space[r].cur&&space[k].data!=b) 
         // k!=space[r].cur 到达存储A集合链表的表尾 space[k].data!=b b不在元素 A
        {
            p=k;//p存储着要删除结点前驱结点
            k=space[k].cur;//遍历下一个结点
        }
        if(k==Space[r].cur)
            //数据b没有重复，加入数据b
            //数据b插入到 r结点之后
        {
            i=Malloc_SL(space);
        	space[i].data=b; 
            space[i].cur=space[r].cur;
        	space[r].cur=i;      
        }
        else//数据B重复了
        {
            space[p].cur=space[k].cur;   //此时K删除点
            if(r==k) //如果删除的是r结点，需要改r的指向
               r=p;
        }
    }
}

看不明白，多阅读几遍，就明白了。

假设A集合为 {c,b,e,g,f,d} B为 {a,b,n,f}

那样运行结构为

静态链表代码

上述算法，创建链表，插入数据都是整合在difference() 中的。根据上述算法的基本思路，可以实现一下静态链表的基本操作。可以对比我在《 数据结构 第二章 :双链表，循环链表，静态链表以及对比总结》,中实现的静态链表，插入数据平均时间复杂度不在是O(n)，经典的空间换时间。

对于链表，无非就三种操作，遍历元素，插入元素，删除元素，

在我实现的方法中，规定

1. 链表1（备用链表）. 头节点 为 SLinkList[0],存储着没有数据的结点
2. 链表2（数据链表）. 头结点为 SLinkList[1],存储着有数据的结点，

代码

#include<stdio.h>

/**
关于如何判断 节点是否被使用

其实有两种实现方法
1. 专门设置一个数值例如 cur=-1 表示改节点没有被使用

当然这个时有一定的缺点的，在插入元素的时候也需要去遍历一个元素去找那个节点没有被使用。

2.  在静态链表中 存着两个链表
链表1（备用链表）. 头节点 为 SLinkList[0],存储着没有数据的结点
链表2（数据链表）. 头结点为  SLinkList[1],存储着有数据的结点， 

插入元素，需要从备用链表中取一个元素---到数据链表，
删除一个结点，需要从数据链表中被删除结点---链接到备用链表

这样，我们多花费一个空间就可以减少 不少的时间复杂度
**/

#define MaxSize 100
typedef struct 
{
	char data;
	int cur;
}SLinkList[MaxSize];





bool Init_SLinkList(SLinkList& L); //初始化链表
bool Insert_SLinkList(SLinkList& L, int i, char e); //按位插入元素
int Locate_SLinkList(SLinkList L, char e); //返回元素e的索引,返回0则不存在
bool GetElem_SLinkList(SLinkList L, int i, char& e);// 按索引查找元素
bool Delte_SLinkList(SLinkList& L, int i, char& e);//删除 第i个元素，删除数据返回到e


int MallocNode(SLinkList& L);//寻找到一个可用 结点 ,返回0，表示空间用完
bool GetNode_SLinkList(SLinkList L, int i, int& k); //获取第i个结点Node的地址k
bool InsertNext_SLinkList(SLinkList& L, char e, int k);//在任意k结点之后插入元素
bool DeleteNode_SLinkList(SLinkList& L, int k);  //删除指定结点,k为删除结点的地址


void test()
{
	SLinkList L;
	Init_SLinkList(L);
	char e;
	//插入数据测试
	for (int i=1; i < 10; i++)
	{
		InsertNext_SLinkList(L, 'a'+i-1, i);
	}
	printf("插入数据完成^_^\n \n");
	int i=L[1].cur;
	int j=1;
	while (i)
	{
		printf("第%3d个数据为 %3c  cur为%3d\n", j, L[i].data,L[i].cur );
		i = L[i].cur;
		j++;
	}
	//获取修改数据测试
	GetElem_SLinkList(L, 4, e);
	printf("第  4个数据为 %3c\n\n", e);
	Insert_SLinkList(L, 3, 'z');
	printf("在第3个数据插入 z 完成\n");
	GetElem_SLinkList(L, 3, e);
	printf("第  3个数据为 %3c\n\n", e);
	GetElem_SLinkList(L, 4, e);
	printf("第  4个数据为 %3c\n\n", e);
	printf("z是第%3d个元素\n", Locate_SLinkList(L, 'z'));
	//删除数据测试
	printf("删除第 3个元素\n");
	Delte_SLinkList(L, 3, e);
	 i = L[1].cur;
	 j = 1;
	while (i)
	{
		printf("第%3d个数据为 %3c  cur为%3d\n", j, L[i].data, L[i].cur);
		i = L[i].cur;
		j++;
	}
	getchar();
}
int main()
{
	test();
	return 0;
}


/*
初始化静态链表，其实就在创建备用链表
*/
bool Init_SLinkList(SLinkList& L)
{
	//备用连的头结点 L[0]，创建备用链表
	for (int i = 2; i < MaxSize - 1; i++) //遍历到MaxSize -2即可
		L[i].cur = i+1;
	//第一个结点从2开始
	L[0].cur = 2;
	//备用链表表尾
	L[MaxSize-1].cur = 0;

	//创建数据链表的头结点  L[1]
	L[1].cur = 0;
	return true;
}
/*
返回一个备用链表里的地址
0表示链表已满
*/
int MallocNode(SLinkList& L)
{
	int i = L[0].cur;//从备用链表取出的结点
	if (L[0].cur)//如果备用链表没有满
		L[0].cur = L[i].cur;//该结点从备用链表中删除
	return i;
}

bool DeleteNode_SLinkList(SLinkList& L, int k)
{
	//将k结点和后面一个结点交换数据
	int p = L[k].cur;
	L[k].data = L[p].data;
	L[k].cur= L[p].cur;
	//删除结点p
	L[p].cur = L[0].cur; L[0].cur = p;
	return true;
}

bool GetNode_SLinkList(SLinkList L, int i, int& k)
{
	if (i<1 || i>MaxSize - 2)
		return false;
	int p = L[1].cur;
	int j = 1;//计数器
	//遍历数据链表
	while (p && j < i)
	{
		p = L[p].cur;
		j++;
	}
	if (!p && j > i)//i<0或者第i个数据不存在
		return false;
	k = p;
	return true;
}

bool InsertNext_SLinkList(SLinkList& L, char e, int k)
{
	if (k<1 || k >= MaxSize) //结点不存在
		return false;
	int p = MallocNode(L);
	if (!p)//如果分配失败
		return false;
	L[p].data = e;
	L[p].cur = L[k].cur;
	L[k].cur = p;
	return false;
}

bool Insert_SLinkList(SLinkList& L, int i, char e)
{
	int k;
	if (!GetNode_SLinkList(L, i-1, k))
		return false;
	return InsertNext_SLinkList(L, e, k);
}

int Locate_SLinkList(SLinkList L, char e)
{
	int k = L[1].cur;
	int i = 1;
	while (k && L[k].data != e)
	{
		k = L[k].cur;
		i++;
	}
	if (k == 0)//如果e不存在
		i = 0;
	return i;
}

bool GetElem_SLinkList(SLinkList L, int i, char& e)
{
	int k;
	if (!GetNode_SLinkList(L, i, k))
		return false;
	e = L[k].data;
	return false;
}
bool Delte_SLinkList(SLinkList& L, int i, char& e)
{
	int k;
	if (!GetNode_SLinkList(L, i,k ))
		return false;
	e = L[k].data;
	DeleteNode_SLinkList(L, k);
	return false;
}