静态链表的游标实现

以前学习的各种链表都是由指针实现的，链表中结点的分配和回收(即释放)都是由系统提供的标准函数malloc和free动态实现的，故称之为动态链表。但是有的高级语言，如BASIC、FORTRAN等，没有提供”指针”这种数据类型，此时若想采用链表做存储结构，就必须使用”游标”来模拟指针，由程序员自己编写”分配结点”和”回收结点”的过程。

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>用游标实现链表，其方法是：定义一个较大的结构数组作为备用结点空间(即存储池)。当申请结点时，每个结点应含有两个域：data域和cursor域。data域用来存放结点的数据信息，需注意的是，此时的cursor域不在是指针而是游标指示器，游标指示器指示其后继结点在结构数组中的相对位置(即数组下标)。数组的第0个分量可以设计成表的头结点，头结点的next域指示了表中第一个结点的位置。表中当前最后一个结点的域为0，表示静态单链表的结束。我们把这种用游标指示器实现的单链表叫做静态单链表，static linked list。静态单链表同样可以借助一维数组来描述：

#define Maxsize =<wbr></wbr>链表可能达到的最大长度

typedef struct

{

<wbr><wbr><wbr><wbr>ElemType data;</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>int cursor;</wbr></wbr></wbr></wbr>

}Component, StaticList[Maxsize];

假如有如上的静态链表S中存储这线性表（a，b，c，d，e，f，g，h，i），Maxsize=11，如图所示，要在第四个元素后插入元素e，方法是：先在当前表尾加入一个元素e，即：S[9].data = e;然后修改第四个元素的游标域，将e插入到链表中，即：S[9].cursor = S[4].cursor; S[4].cursor = 9;，接着，若要删除第8个元素h，则先顺着游标链通过计数找到第7个元素存储位置6，删除的具体做法是令S[6].cursor = S[7].cursor。

上述例子中未考虑对已释放空间的回收，这样在经过多次插入和删除后，会造成静态链表的”假满”，即表中有很多空闲空间，但却无法再插入元素。造成这种现象的原因是未对已删除的元素所占的空间进行回收。解决这个问题的方法是将所有未被分配的结点空间以及因删除操作而回收的结点空间用游标链成一个备用静态链表。当进行插入操作时，先从备用链表上取一个分量来存放待插入的元素，然后将其插入到已用链表的相应位置。当进行删除操作时，则将被删除的结点空间链接到备用链表上以备后用。这种方法是指在已申请的大的存储空间中有一个已用的静态单链表，还有一个备用单链表。已用静态单链表的头指针为1.备用静态单链表的头指针需另设一个变量av来表示。

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>静态单链表的几个基本操作算法：

space为一维数组名

这里的下标表示的就是数组的下标

？下列三个操作的只有space备用链表，那么怎么访问已用链表内的数据呢？space[0].cur指向的是空闲的结点呀。后面的difference例子，另利用了一个S来做已用链表的头指针。

int LocateElem_SL(SLinkList space[])

{ //在静态单链线性表L中查找第一个值为e的元素。若找到，则返回它在L中的位序，否则//返回0

<wbr><wbr><wbr><wbr>i = S[0].cur;</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>while(i &amp;&amp; S[i].data != e)</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>i = S[i].cur;</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>return i;</wbr></wbr></wbr></wbr>

}

<wbr></wbr>

void initSpace_SL(SLinkList space[])

{ //将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，”0”表示空指针

<wbr><wbr><wbr><wbr>for(i=0; i &lt; Maxsize-1; ++i )</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>space[i].cur = i + 1;</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>space[Maxsize-1].cur = 0;</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

}

<wbr></wbr>

int Malloc_SL(SLinkList space[])

{ //若备用空间链表非空，则返回分配的结点下标，否则返回0,<wbr></wbr>结果是将备用链表的头指针之后的开头第一个元素分配出去

<wbr><wbr><wbr><wbr>i = space[0].cur;</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>if(space[0].cur)</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>space[0].cur = space[i].cur; //</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>备用链表的头指针指向的第一个元素后移一个位置

<wbr><wbr></wbr></wbr><wbr><wbr>return i</wbr></wbr>；

}

<wbr></wbr>

void Free_SL(SLinkList space[], int k)

{ //将下标为k的空闲结点回收到备用链表,这个元素位于头指针之后的第一个位置上

<wbr><wbr><wbr>space[k].cur = space[0].cur;</wbr></wbr></wbr>

<wbr><wbr><wbr>space[0].cur = k;</wbr></wbr></wbr>

}

void difference(SLinkList space[], int & S)<wbr><wbr><wbr>//</wbr></wbr></wbr>这个暂时是算法，以后改成实码

{ //依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)and(B-A)

<wbr>//</wbr>的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为其头指针

//这里S和space[0].cur两个头指针的区别？一个是已用链表一个是静态链表？是的，s指向//的就是第一个可用的元素,注意，上面的分配和删除都是在链表的开始第一个结点上，但是//到了添加结点到S所指向的可用链表上时，添加操作的位置是最后。

//in all，关于备用链表的操作位置在备用链表的开头上，关于已用链表的操作，位置在已用//链表的末尾上。

<wbr><wbr><wbr><wbr><wbr>InitSpace_SL(space);<wbr><wbr>//<wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>初始化备用空间

<wbr><wbr><wbr><wbr><wbr>S = Malloc_SL(space); //<wbr></wbr></wbr></wbr></wbr></wbr></wbr>生成S的头结点，S的cur指向的下一个才是真正开始的data

<wbr><wbr><wbr><wbr><wbr>r = S;<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>// r</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>指向S的当前最后结点

<wbr><wbr><wbr><wbr><wbr>scanf(m,n);<wbr><wbr>//<wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>输入A和B的元素个数

<wbr><wbr><wbr><wbr><wbr>for(j = 1; j &lt;= m; ++j)<wbr><wbr><wbr>//</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>建立集合A的链表

<wbr><wbr><wbr><wbr><wbr>{</wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>i = Malloc_SL(space); //</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>分配结点

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>scanf(space[i].data);<wbr><wbr>//</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>输入A的元素值

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>space[r].cur = i;<wbr><wbr><wbr>//</wbr></wbr></wbr>插入到表尾

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>r = i;

}

space[r].cur = 0;

for(j = 1; j <= n; ++j)<wbr><wbr><wbr>//</wbr></wbr></wbr>依次输入b的值，若不在A中，则插入，否则删除

{

<wbr><wbr><wbr><wbr>scanf(b);</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>p = S;</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>k = space[S].cur;<wbr><wbr><wbr>//k</wbr></wbr></wbr></wbr></wbr></wbr></wbr>指向集合A中第一个结点,<wbr><span style="color:red">p</span></wbr>在k的前面一个

<wbr><wbr><wbr><wbr>while(k != space[r].cur &amp;&amp; space[k].data != b)<wbr><wbr>//</wbr></wbr></wbr></wbr></wbr></wbr>在当前表中查找

<wbr><wbr><wbr><wbr>{</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>p = k;</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>k = space[k].cur;</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

}

if( k == space[r].cur) //当前表中不存在此元素，插入在r所指结点之后，且r的

//位置不变，因为r标识的是元素A，即查询的结束。那么若B中的元素是重的呢？

//即B中有两个相同的元素，A中也有，B的元素第一次出现，就把A中的相应元

//素删了，<wbr><wbr><wbr></wbr></wbr></wbr>这种情况不会出现，因为集合是有互异性的，不能有相同的元素。

{

<wbr><wbr><wbr><wbr>i = Malloc_SL(space);</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>space[i].data = b;</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr>space[i].cur = space[r].cur;<wbr><wbr><wbr>//<wbr><span style="color:red">== 0</span></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>space[r].cur = i;<wbr><wbr><wbr><wbr><wbr><wbr>//<span style="color:red">r</span></wbr></wbr></wbr></wbr></wbr></wbr>的后面就是i

}

else<wbr><wbr><wbr><wbr>//</wbr></wbr></wbr></wbr>该元素已在表中，删除之

{<wbr><wbr>//</wbr></wbr>此时k就是要删除的这个结点，p是k之前的结点

<wbr><wbr><wbr><wbr><wbr>space[p].cur = space[k].cur;</wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr>Free_SL(space, k);</wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr>if(r == k) r = p;<wbr><wbr><wbr><wbr>//</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>若删除的是r所指结点，则需修改尾指针-----这个自己

//写肯定想不到

}

}

}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/zzhangjiej/archive/2008/09/04/2880675.aspx