Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
51 lines (36 sloc) 2.22 KB

静态链表

静态链表其实就是在不支持指针和对象的语言里使用的,是使用两个数组描述的链表。

数组定义

  1. 两个数组分别是datacur。数组的每个下标就对应一个datacurdata-数据域-用来存放数据元素,cur-游标-相当于单链表中的next指针。
  2. 一般数组会建立得大一些,防止溢出。以下是c语言定义方式:
#define MAXSIZE 1000

typedef int Elemtype;

typedef struct{
	ElemType data;
	int cur;
} Component, StaticLinkList[MAXSIZE];

初始化

一般第一个数组元素的cur存放第一个空数据元素的地址,最后一个数组元素的cur存放第一个数据元素的地址,然后每个空元素的cur存放下一个空元素的地址最终组成备用空间链表,每个数据元素的cur存放下一个数据元素的地址:

#typedey int Status;

//space[0].cur为头指针,值为0时表示空指针
Status InitList(StaticLinkList space){
	int i;
	for(i = 1; i < MAXSIZE; i++)
		space[i].cur = i;
	space[MAXSIZE-1].cur = 0; //目前静态链表为空,所以最后一个元素的cur为0;
}

分配与清理

实际操作中要解决需要时申请、无用时释放的这两个问题,所以就需要实现两个类似于malloc()free()的函数。

  1. malloc()函数作用是:查询备用链表并返回分配的结点下标,若无备用链表则返回0,然后更新备用链表(将备用链表中下一个元素地址赋给第一个数组元素的cur)。
  2. free()函数作用是:将空闲结点回收到备用链表,把第一个数组元素的cur赋给要删除的数据元素的cur,再将要删除的数据元素的cur赋给第一个数组元素的cur

插入操作:

  1. 获得空闲元素的下标,并给其赋值。
  2. 然后找到需要插入的位置,将该位置之前的数据元素的cur赋给新元素的cur,然后将新数据元素的下标赋给该位置之前的数据元素的cur

删除

  1. 首先获得需要删除的数据元素地址。
  2. 将该数据元素之后的数据元素的cur赋给该元素前面的数据元素的cur
  3. 调用类free()函数,将该元素放入备用链表中。
You can’t perform that action at this time.