数据结构之静态链表的游标表示及其实现（附完整代码）

       转载请注明出处：http://blog.csdn.net/jsrcdjcyy/article/details/52164899

       静态链表的游标实现法有点抽象，如果对线性链表的基本操作以及原理不熟悉的话，将会很难理解得了链表的游标实现法。如果对链表的基本操作和思想很熟悉，自己动手编写过线性表的链式表示及其实现的代码，那么，理解游标表示法的难度将会下降很多。在学习游标实现法的过程中，博主建议同学们对比一下链表的链式表示是怎么实现的，然后再好好回过头来仔细琢磨游标实现法，相信很容易就能理解了。本篇博文是我看了严蔚敏老师的《数据结构（C语言版）》以及《数据结构与算法分析——C语言描述》两本书后，结合教材所讲用C语言实现了静态链表的游标表示及其实现的基本操作，供以后复习所用。两本教材上（特别是后者）有很多现成的例程供读者阅读，博主写的代码就是看这两本书后编写出来的。

       了解过计算机高级编程语言大家庭的我们都知道，并非所有的编程语言都支持指针这种数据类型。诸如BASIC、FORTRAN等许多语言都不支持指针。如果程序中需要利用链表但是又不能使用指针，那么就只能采用类似于指针的办法。我们把这种办法称作游标实现法。在链表的指针实现中有如下两个必不可少的重要特点，那就是：

      1、数据存储在一组结构体中，每一个结构体包含有数据以及指向下一个结构体的指针。

      2、一个新的结构体可以通过调用malloc函数而从系统全局内存中得到，并可以通过调用free函数而被释放。

      如此，我们可以知道，游标法必须得满足以上两个特性才能模拟出指针的效果。满足特性1的办法是要申请一个全局的结构体数组。对于该数组中的任何单元，其数组下标可以用来代表一个地址。对于所申请到的结构体数组，其每个数组元素都是包含Element域和Next域的结点。其中，Element域用来存放结点的数据信息，Next域不再是我们熟悉的指针域，而是游标指示器。游标指示器指示其后继结点在结构体数组中的相对位置（即数组下标）。

结构体的声明如下：

struct Node
{
    ElementType Element;
    Position Next;
};

struct Node CursorSpace[SpaceSize];

      对于特性2，在此可以通过上面定义的结构体数组CursorSpace[SpaceSize]中的单元来代行malloc和free的职能。为此，我们遵行以下的规则来初始化该结构体数组的Next域，如下表所示：

一个初始化的数组CursorSpace

Slot	Element	Next
0	--	1
1	--	2
2	--	3
3	--	4
4	--	5
5	--	6
6	--	7
...	--	...
SpaceSize-1	--	0

      链表的各个结点预先存放在结点数组CursorSpace中，在这个数组中，0的值等价于NULL指针，数组的下标代表的就是一个地址。在使用此游标链表之前，应该使用一个循环把结点数组给“串联”起来。假如数组下标为n，则CursorSpace[n]表示此实际结点，CursorSpace[n].Next表示下一个指向的结点（Next域内存放的就是下一个数组元素的下标，代表下一个结点在结点数组中的位置）。在本例程中，函数CursorAlloc的功用等同于malloc的职能，函数CursorFree的功用等同于free的职能，我们可以通过不断的调用这两个函数来实现“分配结点”和“回收结点”的过程。这样，就能完整的模拟指针实现的各种操作，比如插入、删除、遍历等了。

编译软件：VC++6.0 

测试用例结果截图如下：

源代码如下：

/********************************** 
静态链表的游标表示和实现（完整代码，C实现）
Author:大地在我腳下 
Date:2016-08-09
Email:jsrcdjcyy@163.com 
**********************************/    
#include <stdio.h>

#define SpaceSize 20   //这个数字最好别太大，适当最好。太大了用不到会增加太多计算机内存空间的开销

typedef int ElementType;
typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;//之所以用position和List代替int，主要是为了让人更加明白变量的用途

void InitializeCursorSpace();//CursorSpace结构体数组初始化
static Position CursorAlloc();//作用类似于malloc函数
static void CursorFree(Position);//作用类似于free函数
int IsEmpty(const List);//测试一个链表是否为空
int IsLast(const Position);//测试是否是链表的末尾
Position Find(ElementType, const List);//寻找给定元素的位置
void Delete(ElementType, List);//删除给定元素
Position FindPrevious(ElementType, const List);//寻找给定元素的前一个元素的位置
void Insert(ElementType,List,Position);//插入给定元素
void DeleteList(List);//删除线性表内所有数据
void TraverseList(List);  //遍历单链表并输出  

struct Node
{
    ElementType Element;
    Position Next;
};

struct Node CursorSpace[SpaceSize];

void main()
{   int i,m,data,data_find,data_delete; 
    Position P,LHead;
    InitializeCursorSpace();  //初始化结构体数组的Next域
	
    LHead=CursorAlloc();  //作用类似于用malloc申请一个内存空间，然后把申请到的内存空间的“首地址”赋给一个变量
    printf("The piosition of LHead is:%d
",LHead);  
    CursorSpace[LHead].Next=0;  
    CursorSpace[LHead].Element=0;
    P=LHead;  //LHead相当于链表中的头结点

    //初始化链表
    printf("Please input the number of data:");
	scanf("%d",&m);
    printf("
The original input is as follows:
"); 
    for(i=0;i<m;i++)  
    {  scanf("%d",&data);
        Insert(data,LHead,P);  
        P=CursorSpace[P].Next;    //插入数据的过程中，游标相应的也必须同步往后移动
    } 
   TraverseList(LHead);  

   //寻找链表中某个数据的位置
   printf("
Please input the data you wanna find:");
   scanf("%d",&data_find);
   P=Find(data_find,LHead);  
   printf("The position of data is:%d
",P);  

   //删除链表中某个数据，然后遍历输出
   printf("
Please input the data you wanna delete:"); 
   scanf("%d",&data_delete);
   Delete(data_delete,LHead);  
   TraverseList(LHead);  
    
   //清空链表，遍历后输出（实际上此时链表已空，并无数据输出） 
   DeleteList(LHead);
   printf("
After clearing,now the list is:");
   TraverseList(LHead);
   printf("
");
}

void InitializeCursorSpace()
{
        int i;
        for (i = 0; i < SpaceSize - 1; i++)
		{
                CursorSpace[i].Next = i + 1;
        }
		CursorSpace[0].Element=0;
        CursorSpace[SpaceSize - 1].Next = 0;
}

static Position CursorAlloc()
{
        Position P;
        P = CursorSpace[0].Next;
        CursorSpace[0].Next = CursorSpace[P].Next;
        return P;
}

static void CursorFree(Position P)
{
        CursorSpace[P].Next = CursorSpace[0].Next;
        CursorSpace[0].Next = P;
}

//如果L是空的，返回true
int IsEmpty(List L)
{
    return CursorSpace[L].Next == 0;
}

//如果P是链表最后一个元素，返回true
int IsLast(Position P)
{
    return CursorSpace[P].Next == 0;
}

//返回X在L中的位置
Position Find(ElementType X, List L)
{
     Position P;
    P = CursorSpace[L].Next;
     while (P && CursorSpace[P].Element != X)
        P = CursorSpace[P].Next;
    return P;
}

//删除给定元素X
void Delete(ElementType X, List L)
{
    Position P, q,TmpCell;
    P = FindPrevious(X, L);

    if (!IsLast(P)) 
	{
    TmpCell = CursorSpace[P].Next;
    CursorSpace[P].Next = CursorSpace[TmpCell].Next;
    CursorFree(TmpCell);
    }
}

Position FindPrevious(ElementType x, const List L)
{    Position  P = L;
     while (CursorSpace[P].Next && CursorSpace[CursorSpace[P].Next].Element != x)
              P = CursorSpace[P].Next;
     return P;
}

void Insert(ElementType X,List L,Position P)
{
    Position TmpCell;
    TmpCell = CursorAlloc();
    if (0 == TmpCell)   
		printf("List out of space!");
    CursorSpace[TmpCell].Element = X;
    CursorSpace[TmpCell].Next = CursorSpace[P].Next;
    CursorSpace[P].Next = TmpCell;
}

void DeleteList(List L)
{ Position P,Tem;
  P = CursorSpace[L].Next;
  CursorSpace[L].Next=0;
  while(P)
  {Tem=CursorSpace[P].Next;
   CursorFree(P);
   P=Tem;
  }
}

void TraverseList(List L)
{Position P=CursorSpace[L].Next;
 if(IsEmpty(L))  printf("empty!");
 else
 {printf("Now the data of list is as follows:
");
 while(P)
 {printf("%d",CursorSpace[P].Element);
  P=CursorSpace[P].Next;
  putchar(32);
 }
 printf("
");  
}
}