静态链表就是利用数组来实现链表,目的是为了整合顺序表和链表的优势。比如顺序表适合定位元素,链表适合删除和插入元素等等。
本例子用Java来实现的,代码方面可能还有些不足,但是运行的结果是准确的,对于理解没有障碍
Demo类
package com.color.datestructure;
public class StaticArrayElemObject {
String val;//本节点的值
int next;//本节点的后继
@Override
public String toString() {
return val + " : " + next;
}
}
实现类
package com.color.datestructure;
public class StaticArray {
private static int numsOfSaeos=0;
public void initSAEO(StaticArrayElemObject[]saeos,int count){
numsOfSaeos=count;
for(int i=0;i<numsOfSaeos;i++){
//给每个元素分配空间
saeos[i]=new StaticArrayElemObject();
//每个元素分配后置指针
saeos[i].next=i+1;
//每个元素赋值
saeos[i].val=(char)('A'+i)+"";
}
//对链表首/尾进行处理
saeos[0].val="我是链表首部!";
saeos[numsOfSaeos-1].next=0;
}
public void printAllSAEOs(StaticArrayElemObject[]saeos){
System.out.println("**************遍历数组****************");
for(int i=0;i<numsOfSaeos;i++){
System.out.println(i+" : "+saeos[i]);
}
}
public void tranverseList(StaticArrayElemObject[]seaos){
if(seaos.length<0)return;
System.out.println("***********遍历链表************");
StaticArrayElemObject seao=seaos[0];
int i=0;
while(i<numsOfSaeos){
System.out.println(seao);
seao=seaos[seao.next];
i++;
}
}
/**
* 这里实现的是后插,即在链表上第position个元素的后面插入
* @param saeos
* @param position
* @param value
* @throws Exception
*/
public void insert(StaticArrayElemObject[]saeos,int position, String value) throws Exception {
if(numsOfSaeos==saeos.length)throw new Exception("已经没有多余空间了!!!");
//插入的对象在数组空闲区域插入,只是改变next的值
StaticArrayElemObject newSaeo=new StaticArrayElemObject();
newSaeo.next=saeos[position].next;
newSaeo.val=value;
saeos[numsOfSaeos]=newSaeo;
saeos[position].next=numsOfSaeos;
numsOfSaeos++;
}
public void delete(StaticArrayElemObject[]saeos,int position) throws Exception {
//这里进行的是删除链表上第position个元素
if(position<=0||position>=numsOfSaeos) throw new Exception("所要删除的元素不存在!!!");
StaticArrayElemObject saeo =saeos[0];
int i=0;
while(i<position-1){
saeo=saeos[saeo.next];
i++;
}
saeos[i].next=saeos[saeos[i].next].next;
}
public void update(StaticArrayElemObject[]saeos,int position, String value) throws Exception {
//这里更新的是链表上第position个元素的值
if(position<=0||position>=numsOfSaeos)throw new Exception("所要修改的元素不存在!!!");
StaticArrayElemObject saeo =saeos[0];
int i=0;
while(i<position-1){
saeo=saeos[saeo.next];
i++;
}
saeos[saeo.next].val=value;
}
public void inquiry(StaticArrayElemObject[]saeos,int position) throws Exception {
//查询数组中的元素很简单,这里主要是进行查询链表上第几个的元素
if(position<=0||position>=numsOfSaeos)throw new Exception("所要查询的元素不存在!!!");
StaticArrayElemObject saeo =saeos[0];
int i=0;
while(i<position){
saeo=saeos[saeo.next];
i++;
}
System.out.println(saeo);
}
public static void main(String[] args) {
StaticArray sa=new StaticArray();
//最高上限为20
StaticArrayElemObject[]saeos=new StaticArrayElemObject[20];
//首次只生成10个
sa.initSAEO(saeos,10);
//遍历数组
sa.printAllSAEOs(saeos);
try {
//插入
StaticArrayElemObject waitInsert=new StaticArrayElemObject();
sa.insert(saeos,4,"测试");
System.out.println("**********插入后的效果****************");
sa.printAllSAEOs(saeos);
//修改
sa.update(saeos,5,"test");
System.out.println("**********修改后的效果****************");
sa.printAllSAEOs(saeos);
//删除
sa.delete(saeos,5);
System.out.println("**********删除后的效果****************");
sa.printAllSAEOs(saeos);
//查询
System.out.println("**********查询的效果****************");
sa.inquiry(saeos,4);
} catch (Exception e) {
e.printStackTrace();
}
}
}