数据结构_知识点_静态链表

1. 静态链表定义

静态链表其实就是使用数组去代替指针以实现单链表。
结点定义如下：

typedef struct
{
    elemType data;
    int cur;
}staticLinkList[maxSize];

需要注意的是：

1. 数组的第一个和最后一个元素作为特殊元素吹，不存数据。下标为0的元素存放第一个没被使用的结点，数组最后一个元素的cur则存放第一个有数据的结点的下标。
2. 静态链表可以理解为存有两个链表，一个是已存放数据的链表，一个是待存放数据的链表。
   </br>

已存放数据链表：

第一个元素为数组最后一个元素；最后一个元素的cur指向下标为0的元素（即数组第一个元素）。
</br>

备用链表：

第一个元素为下标为0的元素（即数组第一个元素），此元素的cur为第一个为空的结点的下标；最后一个元素为数组最后一个元素。

2. 插入和删除

插入：首先要为结点分配空间（由于已经提前通过声明数组，所以此时需要找到未被使用的结点），然后在已存放数据链表查找插入位置的前一个结点即第 i - 1个结点，然后通过改变结点的cur做到插入。

int mallocNode(staticLinkList l)
{
    //静态链表性质
    //头结点的指针域指向第一个为空的结点
    //为空结点的指针域指向下一个为空的指针域 
    int i = l[0].cur;
    
    if(l[0].cur)
    {
        //使第一个结点的cur指向下一个未使用结点
        l[0].cur = l[i].cur;
    }
    
    return i;       
}

bool insert(staticLinkList &l,int i,elemType e)
{
    int j,k,m;
    
    k = maxSize - 1;
    
    if(i < 1 || i > listLength(l) + 2)
        return false;
        
    j = mallocNode(l);

    if(j)
    {
        l[j].data = e;
        
        //找到第 i - 1 个元素
        for(m = 1;m <= i - 1;m++)
            k = l[k].cur;
        //插入元素的cur等于第 i - 1 个元素的cur 
        l[j].cur = l[k].cur;
        //第 i - 1 个元素的cur等于插入元素的下标
        l[k].cur = j;
        
        return true;
    }
    
    return false;           
}

删除：
第一，找到删除结点的下标
第二，把删除结点的前一个结点cur改成删除结点的cur；
第三，把删除结点通过头插法插入到备用链表中（即单链表的释放结点空间）

void freeNode(staticLinkList &l, int i)
{
    //用头插法插入到空结点链中 
    l[i].cur = l[0].cur;
    l[0].cur = i;
}

bool deleteNode(staticLinkList &l, int i)
{
    int j,k;
    
    if(i < 1 || i >listLength(l))
        return false;
        
    k = maxSize - 1;
    
    //找到删除结点的下标 
    for(j = 1;j <= i - 1;j++)
        k = l[k].cur;
    
    //把删除结点的前一个结点cur改成删除结点的cur
    j = l[k].cur;
    l[k].cur = l[j].cur;
    
    freeNode(l,j);
    
    return true;
} 

总结

1. 静态链表分为两个链表：已用链表，备用链表。
   已用链表的第一个结点为数组最后一个结点，已用链表最后一个结点的cur为0。
   备用链表的第一个结点为数组第一个结点即下标为0的结点，最后的一个结点的cur为maxSize，即指向最后一个结点。
2. 因此，分配结点和释放结点分别要在已用链表和备用链表第一个结点开始处理。
3. 插入，删除对cur的处理和单链表的处理基本一样。