静态链表

╰+攻爆jí腚メ 2022-08-08 14:50 127阅读 0赞

静态链表相当于是用一个数组来实现线性表的链式存储结构，大概结构图如下![1358343961_3547.png][]

![1358344260_1739.png][]

在静态链表中，每一个结点包含两部分内容，一部分是data（即有意义的数据），另一部分是cur（存储该元素下一个元素所在数组对应的下标）。

有几个特殊的结点：

首先是下标为0的结点中不包含有意义的数据，它的cur存储的是备用链表（即没有存储的数据的那些结点）第一个结点的下标。如上图2所示，数组第一个元素的cur存放的是7。

其次是数组最后一个元素，数组最后一个元素的cur存放的是静态链表的第一个结点的下标（此处的第一个结点，是指有实质意义的数据的结点）。

最后就是链表的最后一个元素（并不一定是数组的最后一个元素），链表最后一个元素的cur一般存放0，表示它后面的结点为空了。

**静态链表的结构：**

#define MAX_SIZE = 1000 ；
    typedef struct {
         ElemType data ;
         int cur ; 
    } Component ,  StaticLinkList[MAX_SIZE];

**静态链表的初始化：**

Status InitList(StaticLinkList L) {
        for(int i = 0; i < MAX_SIZE - 1 ; ++i) {
            space[i].cur =  i+1 ;       
       }
       space[MAX_SIZE-1].cur = 0 ;
       return OK;
    }

如果要插入新的结点到静态链表中，首先需要得到一个备用链表的位置来存放新的结点，malloc\_ssl就是得到一个备用链表的下标，并且返回。

int Malloc_SSL(StaticLinkList L ) {
           int i = space[MAX_SIZE-1].cur ;               //得到第一个结点的下标
           if(space[0].cur){                             //如果存在备用链表
                   i = space[0].cur ;                    //得到备用链表的第一个结点的下标
            }
          space[0].cur = space[i].cur ;                  //备用结点的第一个结点将被使用，于是备用结点小标往后一个结点移动
           return i ;
    }

**插入新结点操作：**

Status InserList(StaticLinkList L ,  int  i ,   ElemType e) {
           int k = MAX_SIZE - 1;
           if( i < 1 || i > Length(L) + 1)
               return ERROR ;
           int j = Malloc_SSL(L);                 //得到备用链表的第一个元素
           if (j){                                //如果元素存在
                     L[j].data = e ;                 
                     for(int m = 1 ; m < i ; ++m) //得到第i-1个元素的下标
                         k = L[k].cur ;
                    L[j].cur = L[k].cur ;         //将第i-1个元素的cur设置为新加的这个结点的下标，将新加的这个结点的下标设置为之前第i-1个元素存储的cur值
                    L[k].cur = j ;
                    return OK ;
           }
          return ERROR ;
    }

**删除静态链表中的元素:**

Status DeleteLinkList(StaticLinkList   L ,  int   i ) {
            if(i < 1 || i > ListLength(L))
                  return ERROR ;
            int k = MAX_SIZE - 1 ;
            for(int j = 1 ; j < i ; ++j) {              //找到第i-1个元素
                     k = L[k].cur   ;
            }
            j = L[K].cur ;                              //得到第i个元素的下标
            L[k].cur = L[j].cur ;                       //将第i个元素存储的cur值赋值给第i-1个元素的cur
            Free_SSL(L ,  j);                           //释放掉第i个元素，第i个元素的下标为j
            return OK;
    }

**其中Free\_SSL就是将该下标的结点放到备用链表中去。**

void Free_SSL(StaticLinkList   L ,  int  i ) {
             L[i].cur  = space[0].cur ;             //将之前的备用链表的第一个结点的小标存入到L[i]的cur中
            space[0].cur = i ;                      //下标为i的元素成为备用链表的第一个结点
    }

转自

http://blog.csdn.net/scu\_daiwei/article/details/851106

[1358343961_3547.png]: https://img-my.csdn.net/uploads/201301/16/1358343961_3547.png
[1358344260_1739.png]: https://img-my.csdn.net/uploads/201301/16/1358344260_1739.png