线性表入门——静态链表

线性表是一种简单的数据结构，其主要特点是元素之间存在“一对一”的关系，除去第一个元素，每个元素都存在唯一一个“前驱节点”，除去最后一个元素都存在唯一一个“后继节点”。
简单的线性表有：数组、单链表、双向链表、静态链表等。每种线性表有各自的优缺点，数组不仅逻辑上，物理上位置也相邻，可随机存取，但删除或插入元素时需要移动大量元素，而且需要预先分配一个较大的空间。链表不要求物理位置上也相邻，方便删除和插入，但没有随机存取的特性。
主要介绍第三种——静态链表：

    typedef char ElemType;/*ElemType可以为多种类型,为方便，在这定义它是char;*/
    typedef struct{
                                  ElemType data;
                                  int cur;
                          }slink;//构建静态链表的存储结构

利用一维数组的特性，引入cur作为类似于链表中指针存在，可以具有链式存储结构的优点，但是缺点是仍不能实现动态分配。

静态链表结构如图所示，cur类似于指针指向下一个元素。为了实现空间的分配，将第一个节点space[0].cur作为备用链表的头指针（即可用内存空间的头指针，指向第一个空节点），space[1].cur作为已用链表的头指针（指向第一个数据）。（图中，space[9]的cur赋值为0代表已用链表到达末尾。数组末尾space[14].cur也为0）。

介绍完静态链表的构造，接下来介绍一些基本操作：
1、初始化：

void initlink(slink space[])
 {//初始化;/*将space中各分量链成一个备用链表；用space[0].cur作为头指针;*/
       int i;
       for(i=0;i<max-1;i++)
       { 
               space[i].data='*';//将空节点data赋值为'*'
               space[i].cur=i+1;
       }
      space[i].data='*';
      space[max-1].cur=0;   //'0'代表NULL;
 }

2、查找元素：

int locateElem(slink s[],ElemType e,int head){
/*查找元素e在链表中第一次出现的位置;若找到，返回所在位置的下标，否则返回0;*/
      int i=s[head].cur;
      while(i&&s[i].data!=e)
      {
             i=s[i].cur;//顺链下行
      }
     return i;
}

3、申请空间：

int malloc_slink(slink space[])
{
        int i;
        i=space[0].cur;//space[0].cur为备用链表的头指针，指向第一个空间;
        if(space[0].cur)//如果空间可用
        {
                space[0].cur=space[i].cur;//头指针后移，指向下一个空结点;
        }
        return i;//返回申请的i结点下标
}

4、释放空间：

void free_slink(slink space[],int k)
{
        space[k].data='*';
        space[k].cur=space[0].cur;
        space[0].cur=k;/*将k挂到备用链表的头指针后面表示这块空间已经被释放*/
}

4、创建输入链表

int putin(slink space[])
{
        int current,head;
        initlink(space);//初始化
        head=malloc_slink(space);//申请第一个节点作为已用链表的头节点
        current=head;
        int i,m,j;
        printf("请输入待输入的元素个数：\n");
        scanf("%d",&m);
        printf("请依次输入元素：\n");
        for(i=1;i<=m;i++)//循环输入数据
        {
                j=malloc_slink(space);//申请节点
               getchar();//吃回车
               scanf("%c",&space[j].data);
               space[current].cur=j;
               current=j;
         }
        space[current].cur=0;//已用链表最后一个节点的cur赋值为0，代表结束
        return head;//创建成功，返回头指针
}

4、删除数据：

int delete_slink(slink space[],int head,int place)
{
        int i=head;
        while(space[i].cur!=0&&space[i].cur!=place)//从已用链表开始查找是否存在给定位置
        {
                i=space[i].cur;
        }
        if(0==space[i].cur)//未发现下标为place的节点
        {
                printf("删除失败!\n");
                return 0;
        }
        if(space[i].cur==place)
        {
                space[place-1].cur=space[place].cur;//抽出该节点
                free_slink(space,place);//释放空间
                printf("删除成功!\n");
                return 0;
}

5、插入数据：

void insert_slink(slink space[],int head)
{
        int i;
       ElemType c;
        i=malloc_slink(space);
        printf("\n输入:\n");
       getchar();
       scanf("%c",&c);//输入元素
       space[i].data=c;
       space[i].cur=space[head].cur;//插入头指针后,头指针不移动
       space[head].cur=i;
}