数据结构与算法（三）——线性表（下）静态链表篇

大家好，欢迎来到IT知识分享网。

目录

一、前情提要

二、静态链表的介绍

三、代码展示

一、前情提要

        上篇讲到了最基本的链式存储结构——单链表。但单链表的功能可能不能满足我们的需求，所以就衍生出了静态链表。本篇文章将会介绍其功能，并给出相关代码。后面还有双向链表和循环链表，本来想一起写的，但太长了，分三次吧。

二、静态链表的介绍

         Q1：啥叫静态链表？ 

         A：简单点说静态链表是用数组描述的链表。注意：和前面的顺序存储不一样，这里是用数组模拟链表。

         Q2：为啥会出现静态链表这种东西？

         A：这就得说说C语言的伟大了，因为它具有指针的能力，这样使得它可以非常容易的操作内存中的地址和数据。

               但后来的面向对象语言，如：Java、C#等。它们是没有指针这个东西的。更别说一些早期的语言，如：Basic、Fortran等。由于没有指针，按照之前单链表的结构，指针域就没办法实现。所以衍生了静态链表这个产物。

         Q3：那我们是如何用数组描述链表的呢？

         A：首先我们让数组的元素都是由两个数据域组成，称之为Date和Cur。也就是说数组的每一个下标都对应一个Date和Cur。

              数据域Date，用来存放数据元素，也就是我们通常要处理的数据。

              数据域Cur，相当于单链表中的Next指针，存放该元素的后继在数组中的下标，我们把Cur叫做游标。

              这种实现方法也叫游标实现法。

        为了方便插入数据，我们通常会把数组建立更大一些，以便有一些空闲空间插入时不至于溢出。说到这里它的优点和缺点都很明显了。、

      优点&&缺点

        优点：在插入和删除操作时只需要修改游标，不需要移动元素。从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。

        缺点：（1）没有解决连续存储分配带来的表长难以确定的问题。

                   （2）失去了顺序存储结构随机存取的特性。

       “失去了顺序存储结构随机存取的特性。”这句话听起来可能有点懵，我解释一下。因为顺序存储是由数组实现的，给我随机的数组下标我都可以将数据存进去，取出来。而现在变成了链表的形式，变成了链式存储，只能从头到尾进行查找，然后存取。

         总的来说，静态链表就是为了给没有指针的高级语言实现单链表能力的一种方法。尽管大家以后不一定用的上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

          它的功能和单链表也差不多，边分析边写代码吧。

 静态链表创建+初始化操作

      在静态链表中有个约定俗称的规定：

      1.第一个和最后一个结点作为特殊元素处理，不存数据。
      2.我们通常把未被使用的数组元素称之为备用链表，而数组第一个元素（即下标为0的元素）的Cur就存放备用链表的第一个结点的下标。

      3. 数组最后一个元素的Cur则存放第一个有数值的元素（首元结点）的下标，相当于单链表中头结点的作用。当整个链表为空的时候，数组中最后一个元素的Cur为0。

      4.如果一个结点下一位置的数据为空但这个结点数据不为空，则这个结点的Cur用0来表示。因为这个这是最后一个有数据的结点了，没有下一个有数据的结点了，所以Cur为0相当于指针中的NULL。

 画图理解一下：

#define MaxSize 1000 typedef struct { int Data; //两个数据域 int Cur; //一个是存储数据，另外一个就是游标（存储下一个元素的下标） }Component,StaticList[MaxSize];//Component是备用链表，StaticList是 静态链表。 void Init(StaticList Space) //静态链表初始化。主要有两点：1.将Cur游标存储下一个结点的下标 { //2.最后一个结点的Cur游标存储第一个有数值的元素的下标。 for(int i=0;i<MaxSize-1;i++) //space是静态链表，用循环将第i个结点的Cur游标赋值为i+1。 { Space[i].Cur=i+1; } Space[MaxSize-2].Cur=0; //最后一个空闲的结点Cur置为0，相当于指针置为NULL。 Space[MaxSize-1].Cur=0; //最后将最后一个结点的Cur游标初始化为0。先开始是空表所以为0，如果 //不是空表，那么此处就会记录第一个有数值元素的下标。 }

注意：这部分代码网上很多地方都存在问题，这也是我停更两天的原因。这篇文章会给出完整且正确的代码，（辛苦了几天给个赞不过分吧）。

 初始化这部分咱慢慢来说：

（1）      首先有个问题：我们怎么去找到备用链表的第一个结点呢？

               这个就得用到我们第一个结点的Cur来锁定备用链表的第一个空闲结点。

（2）      其次，我们怎么去连续的使用备用链表呢？比如用完A结点，马上又可以申请一块B内存供我使用。

               这个就需要利用Cur达到数组模拟指针的一个效果。将空闲的结点，用过Cur链接在一起，形成备用链表，用完A内存，通过Space[A].Cur找到B内存。（Cur可以看作Next指针）

  (3)        我们怎么知道备用链表是否用完了呢？

              所以我们给Space[i].Cur赋值的时候，要在倒数第二个结点，将它的Cur置为0。(相当于空指针NULL)。

  (4)    上面一个问题的回答为什么是倒数第二个结点，倒数第一个结点干嘛去了？

           因为我们上面说过，静态链表有几个约定俗成的规定。第一个结点和最后一个结点它不存数据。第一个结点Cur存备用链表第一个结点位置，最后一个结点Cur存第一个储存数据的结点（首元结点）的位置。

           自然而然，倒数第二个结点变成了最后一个可以保存数据的结点，也就是最后一个空闲结点，最后一个结点肯定指针指向NULL，所以倒数第二个结点的Cur置为0。

（5）最后一个结点的Cur为什么置为0？

         因为初始化的时候，静态链表为空，一开始默认为0。后面进行插入操作等操作的时候会改变。

  这几个问题搞清楚这块应该就没啥问题了。

静态链表的插入操作

    首先你插入一个数据，至少得有块空间吧。在单链表中我们是用的malloc，但是静态链表是使用的数组模拟，所以我们要自己写个函数来实现malloc。

    那么问题来了，我们怎么知道哪些空间没被使用过呢？

    解决的办法就是，利用第一个结点中Cur所定位的第一个备用链表，作为待插入的新结点。

    直接上代码看吧。

int Malloc_StaticList(StaticList Space) //申请一块空的内存区域 { //因为第一个结点的Cur记录的是备用链表的第一个结点。 int Pos_Cur=Space[0].Cur;//除非这个链表满了，不然Pos_Cur就是一块空的内存区域。 if(Space[0].Cur) //如果Space[0].Cur==0那么说明，链表满了放不了了。 Space[0].Cur=Space[Pos_Cur].Cur; //如果Space[0]！=0，那么 Pos_Cur这个下标的结点是空的。 return Pos_Cur;//然后Space[0]是第一个结点，他的Cur要记录备用链表第一个结点。 //而现在Pos_Cur这个结点要被用了，他就不是备用链表中的一部分了。 } //所以此时Space[0].Cur就得换，根据性质备用结点的Cur存储的是下一个空结点位置。 //综上所述Space[0].Cur值修改为Pos_Cur的下一个结点（即Space[Pos_Cur].Cur）。 

   大家看不懂代码的时候，得多看看我写的注释，尽力写详细了。

        这里的逻辑应该很好看懂，先通过第一个结点找到备用链表的第一个空闲结点，然后判断备用链表是否为空，如果为空就不通过if判断，直接返回0。如果不为空，那么Space[0].Cur就重新定位新的空闲结点的位置，毕竟上一个被用了要换一个，以旧换新这个词可以很好的形容。最后返回”旧的”空闲结点的下标。

   上面那都是准备工作，接下来就是插入部分了。  

//查询链表中共有多少个结点 int ListLength(StaticList Space) { int count=0; for(int i=Space[MaxSize-1].Cur;i!=0;i=Space[i].Cur) //循环算出目前链表中有多少个结点 { count++; } return count; } //在Space这个静态链表中，插入一个结点，这个结点插在Node这个结点之前。 bool ListInsert(StaticList Space,int Node,int Data) { if(Node<1||Node>ListLength(Space)+1)//解释一下这个函数，如果Node==2,那就是在第2个结点 { //前插入一个结点，也可以说在第一个结点后面插入一个结点。 return false; //条件判断：首先Node从1开始。如果Node==ListLength+1。 } //假设ListLength为x，那么说明Node插在第x个结点后面插入。 //这就是极限了，Node不能再大了，因为长度为x，没有第x+1个结 //点了，没法在后面插。所以无法满足这俩条件，都没法插入。 int New_Cur=Malloc_StaticList(Space);//申请一块区域 if(New_Cur) //如果Pos_Cur！=0，那么说明找到一个空闲结点。 { Space[New_Cur].Data=Data;//先把数据给存进去 int Cur=MaxSize-1; //利用最后一个结点定位首元结点。 for(int i=1;i<=Node-1;i++)//通过循环Cur，来找到Node前面一个结点。 { Cur=Space[Cur].Cur; } //循环完之后Cur是Node前面那个结点的指针，指向Node。 Space[New_Cur].Cur=Space[Cur].Cur;//新的结点指针通过Cur指向Node。 Space[Cur].Cur=New_Cur; //然后Node上一个结点的Cur指向新结点，修改成New_Cur。 return true; } return false;//到了这一步都还没有return true的话，说明插入失败 } 

（1） 这块先说说Node的判断吧。

   判断的意义是啥？

 因为我们如果要插入，肯定是我画箭头那几个位置插入吧。

那如果在下图我标注1，2那两个箭头上插，显然是不行的，连结点都没有，你插什么插。

 Node==x说明，在第x个结点前面插，在第x-1个结点后面插。

 看到这里自己再去琢磨琢磨这两个条件，实在看不懂再看注释，应该能理解。

（2）如何定位到Node前一个结点上面去？

  因为我们最后一个结点的Cur记录的是首元结点，再通过首元结点的Cur找到第二个结点，再通过第二个结点的Cur找到第三个结点。。。这样一来，我们就可以通过for循环来找到Node前一个结点。

（3）找到Node前一个结点有啥用？

  就是为了插入，我们单链表那练过很多了，先新结点指向Node，这里需要借助Node前一个结点的Cur。然后Node前一个结点修改指向，指向改为新的结点。

插入所有问题都说完了。

静态链表的删除

 自己在上面手写了一个Malloc函数，下面也得又对应的Free函数来释放内存。

注意：这里不是动态内存开辟，是数组模拟。必须手写。

挺简单的，方法在单链表中都用过。

//在下标为number的结点，回收成为备用链表的一部分 void Free_StaticList(StaticList Space,int Number) { Space[Number].Cur=Space[0].Cur; //下标为Numbe的结点，Cur指向备用链表的第一个结点 Space[0].Cur=Number; //第一个结点的Cur指向Number，这样Number就变成了备用链表 //中的第一个结点了。 } //删除第k个这个下标位置的结点 bool Delete_Static(StaticList Space,int k) { if(k<1||k>ListLength(Space)) //和上面的if判断相似但有点不同，这里是删除第k个结点 { //k肯定得k>=1&&k<=ListLength return false; } //先找到第k-1个结点吧 int Cur=MaxSize-1; //通过最后一个结点找到首元结点，再不断通过Cur遍历 for(int i=1;i<=k-1;i++) { Cur=Space[Cur].Cur; } //这个循环跟之前的一样都是找到第k个结点前一个结点下标位置。 int k_Cur=Space[Cur].Cur;//找出k结点下标位置。 Space[Cur].Cur=Space[k_Cur].Cur;//k前面节点Cur直接指向k后面的结点 Free_StaticList(Space,k_Cur);//Free掉以k_Cur为下标的结点。 } 

感觉一些方法前面都涉及到了，注释应该都听清楚了，就不分步解释了。

三、代码展示

       注释尽力写详细了。

#include <stdio.h> #include <stdlib.h> #define MaxSize 1000 typedef struct { int Data; //两个数据域 int Cur; //一个是存储数据，另外一个就是游标（存储下一个元素的下标） }Component,StaticList[MaxSize];//Component是备用链表，StaticList是 静态链表。 void Init(StaticList Space) //静态链表初始化。主要有两点：1.将Cur游标存储下一个结点的下标 { //2.最后一个结点的Cur游标存储第一个有数值的元素的下标。 for(int i=0;i<MaxSize-1;i++) //space是静态链表，用循环将第i个结点的Cur游标赋值为i+1。 { Space[i].Cur=i+1; } Space[MaxSize-2].Cur=0; //最后一个空闲的结点Cur置为0，相当于指针置为NULL。 Space[MaxSize-1].Cur=0; //最后将最后一个结点的Cur游标初始化为0。先开始是空表所以为0，如果 //不是空表，那么此处就会记录第一个有数值元素的下标。 } int Malloc_StaticList(StaticList Space) //申请一块空的内存区域 { //因为第一个结点的Cur记录的是备用链表的第一个结点。 int Pos_Cur=Space[0].Cur;//除非这个链表满了，不然Pos_Cur就是一块空的内存区域。 if(Space[0].Cur) //如果Space[0].Cur==0那么说明，链表满了放不了了。 Space[0].Cur=Space[Pos_Cur].Cur; return Pos_Cur; //如果Space[0]！=0，那么 Loc_Cur这个下标的结点是空的。 //然后Space[0]是第一个结点，要记录备用链表第一个结点。 } //而现在Pos_Cur这个结点要被用了，他就不是备用链表中的一部分了。 //所以此时Space[0].Cur就得换，根据性质备用结点的Cur存储的是下一 //个空结点位置。 //综上所述Space[0].Cur值修改为Pos_Cur的下一个结点., //（即Space[Pos_Cur].Cur）。 //查询链表中共有多少个结点 int ListLength(StaticList Space) { int count=0; for(int i=Space[MaxSize-1].Cur;i!=0;i=Space[i].Cur) //循环算出目前链表中有多少个接待你 { count++; } return count; } //在Space这个静态链表中，插入一个结点，这个结点插在Node这个结点之前。 bool ListInsert(StaticList Space,int Node,int Data) { if(Node<1||Node>ListLength(Space)+1) //解释一下这个函数 { //如果Node==2,那就是在第2个结点前插入一个结点 //也可以说在第一个结点后面插入一个结点。 return false; //条件判断：首先Node从1开始。如果 //Node==ListLength+1，ListLength是链表长度 } //假设链表长度为x，那么说明Node插在第x个结点后面。 //这就是极限了，不能再大了，因为长度为x，没有第x+1 //个结点了。所以无法满足这俩条件，都没法插入. int New_Cur=Malloc_StaticList(Space);//申请一块区域 if(New_Cur) //如果New_Cur！=0，那么说明找到一个空闲结点。 { Space[New_Cur].Data=Data;//先把数据给存进去 int Cur=MaxSize-1; //利用最后一个结点定位首元结点。 for(int i=1;i<=Node-1;i++)//通过循环Cur，来找到Node前面一个结点。 { Cur=Space[Cur].Cur; } //循环完之后Cur指的是Node前面那个结点的指针，指向Node。 Space[New_Cur].Cur=Space[Cur].Cur;//新的结点指针通过Cur指向Node。 Space[Cur].Cur=New_Cur; //然后Node上一个结点的Cur指向新结点，修改成New_Cur。 return true; } return false;//到了这一步都还没有return true的话，说明插入失败 } //在下标为number的结点，回收成为备用链表的一部分 void Free_StaticList(StaticList Space,int Number) { Space[Number].Cur=Space[0].Cur; //下标为Numbe的结点，Cur指向备用链表的第一个结点 Space[0].Cur=Number; //第一个结点的Cur指向Number，这样Number就变成了备用链表 //中的第一个结点了。 } //删除第k个这个下标位置的结点 bool Delete_Static(StaticList Space,int k) { if(k<1||k>ListLength(Space)) //和上面的if判断相似但有点不同，这里是删除第k个结点 { //k肯定得k>=1&&k<=ListLength return false; } //先找到Pos这个点吧 int Cur=MaxSize-1; //通过最后一个结点找到首元结点，再不断通过Cur遍历 for(int i=1;i<=k-1;i++) { Cur=Space[Cur].Cur; } //这个循环跟之前的一样都是找到第k个结点前一个结点下标位置。 int k_Cur=Space[Cur].Cur;//找出k结点下标位置。 Space[Cur].Cur=Space[k_Cur].Cur;//k前面节点Cur直接指向k后面的结点 Free_StaticList(Space,k_Cur);//Free掉以k_Cur为下标的结点。 } void PrintList(StaticList Space) //通过最后一个结点定位首元节点再不断遍历 { for(int i=Space[MaxSize-1].Cur;i!=0;i=Space[i].Cur) { printf("%d ",Space[i].Data); } printf("\n"); } int main() { StaticList Space; Init(Space); ListInsert(Space,1,1); ListInsert(Space,2,2); ListInsert(Space,3,3); ListInsert(Space,4,4); PrintList(Space); Delete_Static(Space,2); PrintList(Space); return 0; }