今天学习了下静态链表,简单总结如下:
静态链表相当于是用一个数组来实现线性表的链式存储结构,大概结构图如下
在静态链表中,每一个结点包含两部分内容,一部分是data(即有意义的数据),另一部分是cur(存储该元素下一个元素所在数组对应的下标)。 有几个特殊的结点: 首先是下标为0的结点中不包含有意义的数据,它的cur存储的是备用链表(即没有存储的数据的那些结点)第一个结点的下标。如上图2所示,数组第一个元素的cur存放的是7。 其次是数组最后一个元素,数组最后一个元素的cur存放的是静态链表的第一个结点的下标(此处的第一个结点,是指有实质意义的数据的结点)。 最后就是链表的最后一个元素(并不一定是数组的最后一个元素),链表最后一个元素的cur一般存放0,表示它后面的结点为空了。
静态链表的结构: #define MAX_SIZE = 1000 ; typedef struct { ElemType data ; int cur ; }Component , StaticLinkList[MAX_SIZE];
静态链表的初始化: Status InitList(StaticLinkList L) { for(int i= 0 ; i < MAX_SIZE-1 ; ++i) { space[i].cur = i+1 ; } space[MAX_SIZE-1].cur = 0 ; return OK ; }
如果要插入新的结点到静态链表中,首先需要得到一个备用链表的位置来存放新的结点,malloc_ssl就是得到一个备用链表的下标,并且返回。 int Malloc_SSL(StaticLinkList L ) { int i = space[MAX_SIZE-1].cur ; //得到第一个结点的下标 if(space[0].cur) //如果存在备用链表 { i = space[0].cur ; //得到备用链表的第一个结点的下标 } space[0].cur = space[i].cur ; //备用结点的第一个结点将被使用,于是备用结点小标往后一个结点移动 return i ; }
插入新结点操作: Status InserList(StaticLinkList L , int i , ElemType e) { int k = MAX_SIZE-1 ; if( i < 1 || i >Length(L)+1) return ERROR ; int j = Malloc_SSL(L) ; //得到备用链表的第一个元素 if (j) //如果元素存在 { L[j].data = e ; for(int m = 1 ; m < i ; ++m) //得到第i-1个元素的下标 k = L[k].cur ; L[j].cur = L[k].cur ; //将第i-1个元素的cur设置为新加的这个结点的下标,将新加的这个结点的下标设置为之前第i-1个元素存储的cur值 L[k].cur = j ; return OK ; } return ERROR ; } 删除静态链表中的元素: Status DeleteLinkList(StaticLinkList L , int i ) { if(i < 1 || i > ListLength(L)) return ERROR ;
int k = MAX_SIZE - 1 ; for(int j = 1 ; j < i ; ++j) //找到第i-1个元素 { k = L[k].cur ; } j = L[K].cur ; //得到第i个元素的下标 L[k].cur = L[j].cur ; //将第i个元素存储的cur值赋值给第i-1个元素的cur Free_SSL(L , j); //释放掉第i个元素,第i个元素的下标为j return OK; } 其中Free_SSL就是将该下标的结点放到备用链表中去。 void Free_SSL(StaticLinkList L , int i ) { L[i].cur = space[0].cur ; //将之前的备用链表的第一个结点的小标存入到L[i]的cur中 space[0].cur = i ; //下标为i的元素成为备用链表的第一个结点 }
|
|
来自: 昵称18218015 > 《数据结构》