《大话数据结构》静态链表（也称之为：模拟链表，游标实现法）

本文主要是介绍《大话数据结构》静态链表（也称之为：模拟链表，游标实现法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.定义

用数组描述的链表叫做：静态链表

我们让数组的元素都由两个数据域组成：

数据域data，用来存放数据元素，也就是我们要处理的数据；

游标cur，相当于单链表中next指针，存放该元素的后继在数组中的下标

对数组第一个和最后一个元素作为特殊元素处理，不存数据

模拟链表的存储结构及初始化的数组状态

#define MAXMIZE 10000//链表的最大长度
typedef struct
{int data;int cur;//游标
}component,list[MAXMIZE ]//初始化模拟链表
/*将一维数纽 space 中各分量链成一备用链表*/
/*space[O].cur为头指针， "0"表示空指针 */
int initlist(list space)
{for(int i=0;i<MAXMIZE-1;i++)space[i].cur=i+1;space[MAXMIZE-1].cur=0;//目前模拟链表为空，最后一个元素的cur为0return 1;    
}

核心的结构如下图所示，

我标出来的就是初始化数组状态干的事情

 

1.模拟链表的插入操作

首先，需用自己实现类似动态链表中类似malloc()和free()这样的函数

/ *若备用空间链表非空，则返回分配的结点下标，否则返回0. * /
#define MAXMIZE 1000
typedef struct
{int data;int cur;
}list[MAXMIZE];int Malloc(list space)
{int i=space[0].cur;//要返回的是第一个空闲的游标//由于第一个游标拿出去使用了，所以就得把它的下一个游标拿出来备用if(space[0].cur)space[0].cur=space[i].cur;return i;
}

插入操作，你得去按照下面的图这样理解，才更好理解一下

但是为啥是这种状态呢？是如何把数一个个这么插入的呢？这本书没说啊！很烦，但是存入之后的结构如下图所示

妈的，想了两天总算有点收获了，我把插入后的结果结合代码进行说明（吐槽：还好我算法书看得多啊，一般人直接看这这个肯定蒙逼，我也是逼自己去理解，妈的，理解了，心情就是舒服很多）

 

下面的应该是最后的状态了，也就是说需要将插入的元素放在空闲的空间当中，这两张图为啥和我们前面初始化模拟链表的不一样呢？是因为他在模拟链表中放了一些数进去，导致相应的数组的第一个元素和最后一个元素的游标发生了一定的变化

一定要注意空闲空间

/* 在L中第 i 个元素之前插入新的数据元素e */#define MAXMIZE 1000
typedef struct
{int i;int cur;
}list[MAXMIZE];//模拟链表的初始化，讲解都是直接按照最原始的初始化图讲的，为了一般性
//为啥要这样进行初始化，原因是,第一个元素是专门用来标记下标为1的游标的，不放什么元素的
//最后一个元素是专门用来标记头节点的，同样也不放什么元素
//上述这俩很重要，所以拿出来说明
int init(list space)
{for(int i=0;i<MAXMIZE-1;i++)list[i].cur=i+1;list[MAXMIZE-1].cur=0;
}//下面这个意思是每次都要获取第一个元素的游标
//同时，获取完毕之后，第一个元素的游标会发生改变
void Malloc(list space)
{int i=space[0].cur;if(i)space[0].cur=space[i].cur;return i;
}//重点来了，上面蒙逼的过程结合下面的插入元素的代码来解释
//首先，那个“甲乙丙。。”都是用这个函数来插入元素的
//你将模拟链表初始化以后，就可以开始插入新元素了
//比如你想在下标为1（i=1）的地方插入一个元素e
int insert(list L,int i,int e)
{int k=MAXMIZE-1;int j;//获取第一个元素的下标，这个时候j=1j=Malloc(L);//获取一个空闲空间if(j){L[j].data=e;//这个时候下标为1的地方就放个元素e//这个for循环也是有意思，它只对i>=2的有想法，比2大的元素的游标我给你改变光for(int l=1;l<=i-1;l++)k=L[k].cur;//由于i=1，上述的语句不执行，执行下列语句L[j].cur=L[k].cur;//L[1].cur=0L[k].cur=j;//L[999].cur=1if(i<1 || i>ListLength(L)+1)return 0;    return 1;    }}
//说白了，就是改变了插入位置i的游标，以及头节点的游标
//你再仔细对比一下，是不是和新插入的“庚”的情况是否一样，想明白真滴是麻烦

2.模拟链表的删除操作

删除元素时，原来是需要释放结点的函数 free （）

/*删除在L中第i个数据元素e */
#define MAXMIZE 1000
typedef struct
{int data;int cur;
}list[MAXMIZE];int init(list space)
{for(int i=0;i<MAXMIZE-1;i++)list[i].sur=i+1;list[MAXMIZE-1].sur=0;
}int delete(list L ,int i)
{k=MAXMIZE-1;for(int j=1;j<=i-1;i++)k=L[k].cur;j=L[k].cur;L[k].cur=L[j].cur;Free(L,j);return 1;
}/*将下标为k的空间节点回收到备用链表 */
void Free(list space,int k)
{space[k].cur=space[0].cur;//把第一个元素的cur值给要删除的k，来说明该元素存储的是第一个元素的游标（也就是把它变成初始化链表的最前面的那个特殊点）space[0].cur=k;
}

补充ListLength函数

/*初始条件:静态链表L已存在。操作结果：返回L中数据元素个数*/#define MAXMIZE 1000
typedef struct
{int data;int cur;
}list[MAXMIZE];int length(list L)
{int j;//   用游标从头节点开始统计int i=L[MAXMIZE-1].cur;while(i){//游标i=1开始，然后是i=L[i].cur=2。。。。。可以参考那个有“甲乙丙的图片”i=L[i].cur;j++;}return j;}

 

 

 

 

 

这篇关于《大话数据结构》静态链表（也称之为：模拟链表，游标实现法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---