注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

静态链表---弄了好几天了,终于理解了  

2014-10-02 21:15:38|  分类: 数据结构---严老 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个是真的十分的不好理解啊!终于理解了他的删除,他的一切,多看看~
不错的简介,静态的链表~多亏了

在静态链表中,每一个结点包含两部分内容,一部分是data(即有意义的数据),另一部分是cur(存储该元素下一个元素所在数组对应的下标)。

有几个特殊的结点:

首先是下标为0的结点中不包含有意义的数据,它的cur存储的是备用链表(即没有存储的数据的那些结点)第一个结点的下标。如上图2所示,数组第一个元素的cur存放的是7。

其次是数组最后一个元素,数组最后一个元素的cur存放的是静态链表的第一个结点的下标(此处的第一个结点,是指有实质意义的数据的结点)。

最后就是链表的最后一个元素(并不一定是数组的最后一个元素),链表最后一个元素的cur一般存放0,表示它后面的结点为空了。

const int Max=1000;
typedef struct
{
int data;
int cur;//cur 静态鼠标
}SqList[Max];
//静态的链表,使用我们的数组表示;

void InitList(SqList l)
{
// 构造一个空的链表,表头为L的最后一个单元L[MAXSIZE-1],其余单元链成
// 一个备用链表,表头为L的第一个单元L[0],“0”表示空指针
l[Max-1].cur=0;
for(int i=0;i<Max-1;i++)
{
l[i].cur=i+1;
}
//这个是怎么意思呢!第一元素的cur中保存我们的第1个结点的位置啊!
}

cur 其实就是相当于我们的Next;保存我们的下一位元素的下标~

int Malloc(SqList l)
{//头结点的Cur 保存的是我们的要申请的空间的下标的保存他的cur的下标;
int i=l[0].cur;
if(i)
{//如果不为0,即就是不是用完空间了;
l[0].cur=l[i].cur;
}
return i;
}

每次我们加入新的成员的时候~下标为0 的元素都保存着我们的第一个未用的空间的下标。

每次使用后~都把下一个元素的下标的都交给了我们的,l[0].cur;

void ListDelte(SqList l,int i,int &e)
{// 删除在L中第i个数据元素e,
int k=Max-1;
int j;
if(i<1||i>ListLength(l))
{
return false;
}
while(j=1;j<i;j++)//前一个结点的下标;
{
k=l[k].cur;
}
j=l[k].cur;
e=l[j].data;
l[k].cur=l[j].cur;//保证跳过我们的这个结点;他前面的结点,用他后面的结点表示;
Free(l,j);
return true;
}

删除的话,就是这样的问题,你首先删除的时候,为了保证原来的,静态表的连接的顺序不变,首先就像我们的一班的线性表一样的。

吧上一个结点的next直接指向我们的现在的下一个结点l[k].cur=l[j].cur;

接下来的就是考率怎么办吧现在的cur搞定啊!,就是我们的_j的值得大小;不可能让我闷得下标为j的cur为j。

所以,free的意思就是把cur的位置改变一下!让现在的下一个备用结点的下标指示为j的cur,而现在的j。。。的上一个的原来的cur就直接成为第一个备用。那么增加的时候,直接的执行l[j]=加入的!l[j].cur=下一个的。。。。。

int Free(SqList l,int j)
{ // 将下标为k的空闲结点回收到备用链表(成为备用链表的第一个结点)
l[j].cur=l[0].cur;
//这个的意思就是把现在的备用的结点第一个转给,,,,, // 回收结点的"游标"指向备用链表的第一个结点
l[0].cur=j;// 备用链表的头结点指向新回收的结点

}

bool Insert(SqList l,int i,int e)
{
if(i<1||i>(ListLength(l)))
{
return false;
}
int j=Malloc(l);//申请新单元的下标;
int k=Max-1;
if(j)
{
l[j].data=e;
for(int x=1;x<i;x++)//前一个元素的位置;为前一个元素的下标;
{
k=l[k].cur;
}
l[j].cur=l[k].cur;//后面卡的顺序并不是我们的结点的顺讯!!!
l[k].cur=j;
}

}

增加元素进入之后啊,我们呢,首先就是要,申请一个头结点,就是我们 的了l[o].cur;就是我们的插入的元素的下标,然后把把当前的元素的下标的cur给予l[o].cur,让他表示备用结点的首个下标,同时我们呢~为了表示链表是否到达最后的标志就是碰到有下表的cur为0;

说以,,,我们的 

l[j].cur=l[k].cur;

l[k].cur=j;

让当前插入的元素的cur表示为0,就是这个意思啊!

遇到0了,就证明我们的链表已经用完了啊;

bool IsEmpty(SqList l)//来储存我们的第一个元素的下标,最后个cur
{
if(l[Max-1].cur==0)
{
return true;
}
return false;
}

最大的元素的cur是否为0;

int ListLength(SqList l)
{
int i,j=0;
i=l[Max-1].cur;// i指向第一个元素的下标
while(i)
{
j++;
i=l[i].cur;
}
return j;
}

bool GetElement(SqList l,int i,int &e)
{
//得到第i个元素的值;
int k=ListLength(l);
if(l<i||i<0)
{
return false;
}
k=Max-1; // k指向表头序号
int j;
for(j=1;j<=i;j++)
{
k=l[k].cur;
}
e=l[k].data;
return true;
}

int LocaElem(SqList l,int e)
{// 在静态单链线性表L中查找第1个值为e的元素。若找到,则返回它在L中的
// 位序,否则返回0。
int i=l[Max-1].cur;
while(i&&l[i].data!=e)
{
i=l[i].cur;//这个元素的cur保存下一个元素的下标;
}
if(i==0)
{
return false;
}
return i;
}

bool PriorElem(SqList l,int cur_e,int &pror_e)
{
// 初始条件:线性表L已存
// 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
// 否则操作失败,pre_e无定义
int i=l[Max-1].cur;//前面的个
int j=l[i].cur;//后面个,找前驱,必须的有我们的后驱!
while(j&&l[j].data!=cur_e)
{
i=j;
j=l[j].cur;
}
if(!j)
{
return false;
}
pror_e=l[i].data;
return true;
}

bool CleaList(SqList L)
{
// 初始条件:线性表L已存在。操作结果:将L重置为空表
int i,j,k;
i=L[MAXSIZE-1].cur; // 链表第一个结点的位置
L[MAXSIZE-1].cur=0; // 链表空
k=L[0].cur; // 备用链表第一个结点的位置
L[0].cur=i; // 把链表的结点连到备用链表的表头
while(i) // 没到链表尾
{
j=i;
i=L[i].cur; // 指向下一个元素
}
L[j].cur=k; // 备用链表的第一个结点接到链表的尾部
return true;

}

这个就是我们的最后的清空的工作啊,

所谓的清空,第一点:我们的标的l[max-1].cur=0;

这个是必须的啊!

如果这个是0,的话,l[0].cur的值,也应该改啊!,但是现在他的值,第一个备份的结点:

l[max-1].cur存放了我们的第一个结点的位置啊!

L[0].cur; // 备用链表第一个结点的位置

我们的呢,现在吧备用的结点占了,最后的时候连接起来啊!



i=L[MAXSIZE-1].cur; // 链表第一个结点的位置
L[MAXSIZE-1].cur=0; // 链表空
k=L[0].cur; // 备用链表第一个结点的位置
L[0].cur=i; // 把链表的结点连到备用链表的表头
while(i) // 没到链表尾
{
j=i;
i=L[i].cur; // 指向下一个元素
}
L[j].cur=k; // 备用链表的第一个结点接到链表的尾部

原来的 L[j].cur 其实为0,这个就是为了,找到他的位置,哈哈!

  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017