链表内容的补充2：静态链表

1.基本结构

链表的一般定义是n个节点通过指针相互连接形成链表。静态链表是借由一维数组对于线性链表进行描述，静态链表的数据域仍然记作变量data，不同于一般的线性链表，其“指针”用一个int 类型的变量cur来表示，而不是返回类型为Node的指针next。静态链表单个元素的类型名称记作component,类似地，指针域用一个Slinklist数组来表示，访问位序为i的元素的指针需要定义slinklist类型的对象space，通过space[i].cur完成对指针的赋值。静态链表的基本结构代码如下：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef struct
{
    int data;
    int cur;
}component,slinklist[1000];

静态链表中的元素位序下标与元素指针需要分别看待，定义一个slinklist型的变量记作space，space[i].cur指示了第i个元素在静态链表中的位置，而假设int 型变量j=space[i].cur，则s[j].data存储了线性表的第i位元素的数据。根据以上的性质，可以实现在静态链表中的定位函数，基本思路如下:  1）定义变量i，初始化为静态链表中第0个元素的位置     2）通过while循环，利用判断条件，当space[i]的数据域不为e时，将i赋值为space[i].cur ，即通过变量cur的值，访问位序为i的元素的后继结点  3）循环直到数据域等于e为止  代码如下:

int locate(slinklist space,int e)
{
    int i=space[0].cur;
    while(i&&space[i].data!=e)
    {
        i=space[i].cur;
    }
    return i;
}

2.静态链表的链表初始化函数以及结点初始化函数

实现了静态链表的定位函数后，可以实现静态链表的插入以及删除算法，静态链表的插入以及删除操作不需要移动元素，只需要修改指针域的值即可完成元素的移动。插入操作需要自行定义两个函数，包括静态链表的链表初始化函数Init(Slinklist space)，以及静态链表节点的初始化函数malloc(Slinklist space).静态链表的链表初始化函数主要思路如下：1）建立一个Slinklist类型的数组space，用于表示结点的数据域以及指针域   2）通过for循环，初始化space数组的指针域，space[0]的指针域记作1，即静态链表space的位序为1的元素后继是位序为2的元素，以此类推，直到space[max-1]的指针域为0，即静态链表space的最后一个元素的后继元素是静态链表的位序为1的元素，达成了一个链表的循环，代码如下：

void Init(slinklist space)
{
   for(int i=0;i<max-1;i++)
  {
     space[i].cur=i+1;
  }
     space[max-1].cur=0;
}

静态链表节点的初始化函数主要思路如下：1）定义一个变量i作为位序为1的元素的后继，语句为：int i=space[0].cur   2）进行条件的判断，如果此时位序为1的元素后继位序不为0时（后继为0表示位序为1的元素后继与表尾元素相同，同时意味着链表已满） space[0].cur=space[i].cur;相当于是有结点插入在位序为1的元素之前，同时该结点的位序由位序为1的元素获得。在应用之中，由于space[0].cur初始化为1，所以i一般由1开始变化。每插入一个新节点，space[0].cur的值会更新。在静态链表的插入操作中，该函数用于获得静态链表逻辑位序为2的结点的物理位序。代码以及示意图如下：

int malloc(slinklist space)
{
    int i=space[0].cur;
    if(space[0].cur)
    {
       space[0].cur=space[i].cur;
    }
   return i;
}

静态链表初始化静态链表中位序为2的结点初始化

3.静态链表的插入函数 

静态链表的初始化插入操作函数基本思路如下：1）假定函数的参数为space数组，要求在静态链表的第m+1位之前插入（位序为m+1,同时m由0开始增加至Max-1） ，待插入的结点数据值为e   2）定义变量j,k,l   变量j初始化为位序为1的结点的后继结点（j=malloc(space)），变量k初始化为max-1，用于在for循环中寻找第m+1个结点的位序（k=space[max-1].cur,初始值为1,经过m-1次循环可以找到结点位置）  3）将新插入的结点的后继结点设置为与此时的第m个结点相同，第m个结点的后继设置为新插入的结点j（此处与单链表插入节点的方法相同）。代码如下：

void Insert(slinklist space,int e,int m)
    {
        int k=max-1;
        int j=malloc(space);
        space[j].data=e;
        for(int i=1;i<=m-1;i++)
        {
            k=space[k].cur;
        }
        space[j].cur=space[k].cur;
        space[k].cur=j;
    }

4.静态链表的遍历操作

静态链表的遍历函数主要的思路为：1）在插入了n个结点后，定义一个变量为k，k初始化为space[max-1].cur，即初始化为物理位序最大的结点的后继   2）进行while循环，当结点i的后继不为0（后继为0意味着结束链表的输出，位序为0的结点数据值为空且其后继的所有节点数据值均为空），输出物理位序为i的结点的数值以及使i访问其逻辑位序的后继。

void travel(slinklist space)
    {
        int i=space[max-1].cur;
        while(space[i].cur!=0)
        {
            cout<<i<<" "<<space[i].data<<" "<<space[i].cur<<endl;
            i=space[i].cur;
        }
    }

静态链表初始化静态链表完成元素插入示意图

静态链表插入元素，遍历元素的主程序代码如下：

int main()
    {
        slinklist space;
        Init(space);
        int m;
        cin>>m;
        int num[m];
        for(int i=0;i<m;i++)
        {
            cin>>num[i];
        }
        for(int k=0;k<=m;k++)
        {
            Insert(space,num[k],k+1);
        }
        travel(space);
        return 0;
    }

 5.静态链表的释放空间操作以及删除结点

静态链表的删除操作，与静态链表的插入操作类似的，仅仅只需通过修改指针域来完成元素的“删除”，在定义删除操作前，前行定义释放逻辑位序为k+1的结点的函数free(slinklist space，k)，释放结点空间的操作等同于将逻辑位序为k+1的结点的后继设置为物理位序为1的元素的后继，再将物理位序为1的元素后继设置为这个释放的结点，相当于将该节点链接入一个无用的链表之中（属于物理位序为1的结点的后继，无法被访问到）。具体代码如下:

int free(slinklist space,int k)
    {
        space[k].cur=space[0].cur;
        space[0].cur=k;
    }

类比单链表的形式，在定义完成free函数后，进行删除操作的基本思路如下：1）定义变量i，表示删除逻辑位序为i的元素 2）定义变量k,m,l 。变量k用于访问逻辑位序为i-1，i，i+1的元素，先通过for循环访问逻辑位序为i-1的元素，用变量m存储其物理位序，此处用 m=space[k].cur语句进行表示   3）进行两次访问后继节点操作后，用变量l存储该节点的物理位序    4）将m的后继结点值赋为l，就达到了删除结点k的目的   4）释放此时位序为k的结点的空间（在访问位序为i-1的元素后进行的第一次访问后继结点语句将k的值赋成i,此处的i与k是等价的）   5） 定义int类型变量e，使用e返回删除的元素值    。代码如下所示：

 void Delete(slinklist space,int i)
    {
        int k=max-1;
        int l,m;
        for(int j=0;j<=i-2;j++)
        {
            k=space[k].cur;
        }
        m=k;
        k=space[m].cur;
        l=space[k].cur;
        space[m].cur=l;
        int e=space[k].data;
        cout<<e<<endl;
        free(space,k);
    }