常用数据结构-数组实现静态链表

水深无声 2023-10-17 13:41 14阅读 0赞

## 1. 静态链表简介 ##

比起经常使用的动态链表，静态链表似乎用的不多，不过也有一些体现，比如FAT文件系统，所谓的静态和动态，就是指内存管理的动态静态，换言之，使用malloc和free，new和delete动态分配的链表，为动态链表，使用数组等方法则是静态链表。资料中说静态链表常用于没有指针的语言中(如Basic，Fortran)等，但是我学习C++，去学习静态链表更多的是为了学习其中解决问题的一种思路，向左向右最后都向前到达终点。

下图是一张静态链表与对应的单链表的对照图：

![Center][]

由图可以看出，其实静态链表就是通过一个结构体数组来实现链表，每个结构体元素即为一个结点，这个结点包括数据位和“指针”位，其中“指针”位要加引号，因为此“指针”的值如同真正的指针一样，能够通过其找到指向的下一个结点，这个位具体是数组中的元素位置。如，在1号位置中，数据位data=b，而“指针”位cur=6，代表这个结点的下一个结点是位置6的元素，即data=c，cur=3的结点。

其中，构建的这个数组应该分为两部分，一部分是已经有数据的工作单链表，一部分是没使用的备用链表，初始状态的时候工作单链表为空，备用链表为满，然后依次逐个使用备用链表，就如同两个装球的盒子，互相可以扔球。

## 2. 静态链表的实现 ##

1. 构建一个结点结构体，即

typedef struct node  
        {  
            T data;  
            int cur;  
        }Node;

2. 静态链表的初始化

template <class T>  
        myStaSeq<T>::myStaSeq()  
        {  
            for (int i=0; i<MAXNUM-1; ++i)  
            {  
                sqList[i].cur = i+1;  
                sqList[i].data = 0;  
            }  
            sqList[MAXNUM-1].cur = 0;  
            sqList[MAXNUM-1].data = 0;  
            curNow = 0;  
            length = 0;  
            curHead = 0;  
        }

其中，curNow代表备用链表待使用的“最上端”结点，或者称为备用链表的头结点，length为工作链表的长度，curHead为工作链表的头结点。

3. 工作链表的插入结点

注意，无论是所谓的工作链表还是备用链表，实质上都是一个结构体数组，只是人为的分开而已，但是经过一段时间的分配之后，可以得到这样两个数组，从curNow，也就是备用链表的头结点依次通过cur向后寻找，就可以得到完整的备用链表，同理，也可以得到工作链表，从这个角度来看，可以看成两个数组

template <class T>  
    bool myStaSeq<T>::InsertElem(T elem_val)  
    {  
        if (length>=MAXNUM)//如果工作链表的长度已经等于分配的整个数组长度，那么就说明此时备用链表用完了，不能再分配了  
        {  
            cout<<"The backup seqlist if empty!"<<endl;  
            return false;  
        }  
        else  
        {  
            sqList[curNow].data = elem_val;//此时，待使用的备用链表的“头结点”得到使用  
            curNow = sqList[curNow].cur;//备用链表的头结点指向下一个  
            ++length;  
            return true;  
        }  
    }

template <class T>  
    bool myStaSeq<T>::InsertElem(T elem_val, int index)//向工作链表中任意一个位置插入结点，注意，此位置是“第几个”而不是序号  
    {  
        if (index<0||index>length||length>=MAXNUM)//如果插入位置不正确则  
        {  
            cout<<"The index is unlow"<<endl;  
            return false;  
        }  
        else if (0==index)//插入位置是第一个，需要将此插入结点的cur指向本来工作链表的头结点curHead  
        {  
            sqList[curNow].data = elem_val;  
            sqList[curNow].cur = curHead;  
            curHead = curNow;  
            curNow = sqList[curNow].cur;  
      
            ++length;  
            return true;  
        }  
        /*else if (length==index)//这段应该是多余的 
                               //  </pre><pre name="code" class="cpp">  { 
            sqList[curNow].data = elem_val; 
            //sqList[curNow].cur = curHead; 
     
            curNow = sqList[curNow].cur; 
            ++length; 
     
            return true; 
     
        }*/  
        else//如果在中间的话，需要先循环找到这个结点，然后将此节点的cur指向curNow，curNow指向原本此节点的cur，过程同动态链表相同  
        {  
            int indexTemp = curHead;  
            for (int i=0; i<index; ++i)  
            {  
                indexTemp = sqList[indexTemp].cur;  
            }  
            sqList[curNow].data = elem_val;  
            //curNow = sqList[curNow].cur;  
      
            sqList[curNow].cur = sqList[indexTemp].cur;  
            sqList[indexTemp].cur = curNow;  
            curNow = sqList[curNow].cur;  
            ++length;  
            return true;  
        }  
    }

4. 工作链表的删除结点

void myStaSeq<T>::Delete(int index)  
    {  
        if (index<0||index>=length)  
        {  
            cout<<"The index number is unlow!"<<endl;  
            //return;  
        }  
        else if (0==index)//如果是工作链表中第一个结点，那么将工作链表的头结点指向下一个即可，同时将原头结点指向curNow，最后将其变为新的curNow  
        {  
            int curHeadTemp = curHead;  
            sqList[curHead].cur = curNow;  
            curNow = curHead;  
            curHead = sqList[curHeadTemp].cur;  
            --length;  
      
            //return;  
        }  
        /*else if ((length-1)==index)//这段应该是多余的 
        { 
            int indexTemp = curHead; 
            for (int i=0; i<(index-1); ++i) 
            { 
                indexTemp = sqList[indexTemp].cur; 
            } 
            curNow = sqList[indexTemp].cur; 
            --length; 
        }*/  
        else//如果是中间的结点，将其取出  
        {  
            int indexTemp = curHead;  
            for (int i=0; i<(index-1); ++i)  
            {  
                indexTemp = sqList[indexTemp].cur;  
            }  
            curNow = sqList[indexTemp].cur;  
            sqList[indexTemp].cur = sqList[sqList[indexTemp].cur].cur;  
            --length;  
        }  
        return;  
      
    }

5. 工作链表的遍历

void myStaSeq<T>::Traversal()  
    {  
        int cur1 = curHead;  
        for (int i=0; i<length; ++i)  
        {  
            cout<<"List["<<cur1<<"] = "<<sqList[cur1].data<<endl;  
            cur1 = sqList[cur1].cur;  
        }  
        cout<<"The list has showed all."<<endl;  
        return;  
    }

## 3. 注意的问题 ##

1. 本来误以为工作链表的最后一个结点的下一个结点应该是备用链表的第一个，但是如果从工作链表中将中间某个结点删除回备用链表之后，就应该把最后一个结点的下个结点更新，而这个更新毫无意义，所以是我当时脑子糊了~

[Center]: https://img-blog.csdn.net/20170609143913029?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveWhhbl9zaGVu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center