首页 > 代码库 > 小猪的数据结构学习笔记(四)
小猪的数据结构学习笔记(四)
小猪的数据结构学习笔记(四)
线性表之静态链表
——转载请注明出处:coder-pig
本章引言:
在二,三中中我们分别学习了顺序表中的线性表与单链表,线性表有点类似于
我们前面所学的数组,而单链表使用的最多的是指针,这里问个简单的问题,
如果是在以前没有指针的话,前辈先人们怎么实现单链表呢?大家思考下!
没有指针,那么用什么来代替呢?前辈先人们非常机智,想出了使用下标+游标的方式
来实现单链表的效果!也就是今天要讲的——静态链表!
当然你也可以直接跳过本章,因为有了单链表就没有必要用静态链表了!
我们学习的是一些思维方式,当条件限制了你的时候,不允许你使用这种方式;
那么你如何用另一种方式去解决同样的问题呢?学多点东西没什么坏处的!
开始本章的讲解吧!
本章学习路线图:
正文:
什么是静态链表?
所谓的静态链表其实就是使用三个属性来表示一个节点,
数组下标:区分每个节点的标志
数据:存放该节点的数据
游标:类似于链表中的指针,指向下一个元素的下标
初始化静态链表:
流程:
step 1:使用for循环,为数组中的每个元素进行赋值
step 2:将最后一个节点的游标设置为0
step 3:返回ok即可
代码示例如下:
//初始化静态链表,和数组的初始化类似 Status InitList(StaticLinkList space) { int i; for(i = 0;i < MAXSIZE - 1;i++) { //每个的游标指向下一个下标,第0个游标指向第1个下标节点 space[i].cursor = i + 1; //最后一个节点需要节点的游标设置为0 space[MAXSIZE - 1].cursor = 0; return OK; } }
插入元素到静态链表
简单例子:
比如有一静态链表S,存储的数据依次为:{a,b,c,d,e,f},MAXSIZE = 20,现在想在第三个元素后面插入
一个元素,流程如下:
①定义一个方法获得一个备用结点,即开辟第七个结点,返回结点下标return 7;
②为该节点赋值S[7].cursor = e;
③接着修改第三个元素的游标,s[9].cursor = s[3].cursor;s[3].cursor = 9;
代码示例如下:
//获得备用链表的结点下标 int Get_Free(StaticLinkList space) { int i = space[0].cursor; //设置下一个结点为备用结点 if(space[0].cursor)space[0] = space[i].cursor; //返回新建结点的下标 return i; }
//往静态链表的第i个位置插入数据元素 Status List_Insert(StaticLinkList L,int i,ElemType e) { int j,k,l; k = MAXSIZE - 1; //数组的最后一个元素 //判断插入位置是否合法 if(i < 1 || i > ListLength(L) + 1) { return ERROR; } //获取一个空白结点下标 j = Get_Free(L); if(j) { //把e放到空白结点的数据域 L[j].data = http://www.mamicode.com/e;>删除静态链表中的元素:
删除的逻辑就稍微简单点了,
比如我们删除的是第5个元素,我们只需要S[4].curosr = S[5].cursor
让后将空闲结点释放掉,即
代码示例如下:
//删除某个节点 Status List_delete(StaticLinkList L , int i ) { //判断删除位置是否合法 if(i < 1 || i > ListLength(L))return ERROR ; //获取最后一个节点,因为它的cursor指向第一个有效结点 int k = MAX_SIZE - 1 ; for(int j = 1 ; j < i ; ++j) { //获取第i - 1个元素的下标 k = L[k].cursor ; } //得到第i个元素的下标 j = L[K].cur ; //将删除节点的cursor赋值给前一个结点 L[k].cur = L[j].cur ; //释放到第i个元素,下标为j Free_Node(L,j); return OK; }/*将下标为k的空闲结点回收到备用结点*/ void Free_Node(StaticLinkList space,int k) { //将之前的备用链表的第一个结点下标存放到L[k]的cursor中 space[k].cursor = space[0].cur; //下标为k的元素称为第一个空闲结点 space[0].cursor = k; }获得静态链表的元素个数:
这个就是遍历一次表而已,当获取到的值为0时,说明已经到达空闲结点,此时返回长度!
代码示例如下:
/*获得L中数据元素的个数*/ int List_length(StaticLinkList L) { int j = 0; int i = L[MAX - 1].cursor; while(i) { i = L[i].cursor; j++; } return j; }静态链表特点总结:
从名字上就知道这是链表啦,肯定是有和单链表类似的特性的,比如插入删除不需要移动元素
只需修改游标;同时也失去了顺序存储结构的随机存取的特性,而且没有解决数组带来的表长
难以确定的问题!说到底就是给没有指针的编程语言提供一种链表功能的实现而已,有指针的
话肯定是直接用的单链表,不过这种方式十分巧妙,值得我们借鉴!
小猪的数据结构学习笔记(四)