linked-03.java

java数据结构,简单,易懂,有利于初学者

//=====================程序描述==================
//程序名称:linked-03.java
//程序目的：演示单链表的存入和读取
//作者：张中强
//=====================程序描述==================

class linked03
{
	public static void main(String args[])
	{
		Student stu=new Student();
		stu.setHeader(2);
		stu.add("张三");
		stu.add("李四");
		stu.add("王五");
		stu.add("周六");

		String[] names=stu.getNames();
		int[] pointers=stu.getPointers();

		for(int i=0;i<names.length;i++)
		{
			System.out.print(names[i]+"\t");
		}
		System.out.println();

		for(int i=0;i<pointers.length;i++)
		{
			System.out.print(pointers[i]+"\t");
		}

		System.out.println();
		System.out.println();
		
		System.out.println("一共有"+stu.getSize()+"条数据!");
		System.out.println();
		
		//按链表顺序打印数据
		int header=stu.getHeader();
		while(true)
		{
			System.out.print(names[header]+"\t");
			header=pointers[header];
			if(header==-1)
				break;
		}
		
		System.out.println();
	}
}

class Student
{
	//存储学生姓名
	private String[] names=new String[5];
	//存储指向下一个学生的指针
	private int[] pointers=new int[5];
	//链表头
	private int header;
	
	public Student()
	{
		for(int i=0;i<pointers.length;i++)
		{
			//设置指针值为2，表示该空间可用
			pointers[i]=-2;
		}
	}
	
	//寻找存放学生姓名的可用位置
	private int getFreePos()
	{
		for(int i=0;i<pointers.length;i++)
		{
			if(pointers[i]==-2)
			{
				return i;
			}
		}
		//返回-1，表示空间已满，不可以再存入数据
		return -1;
	}
	public void add(String name)
	{
		//判断链表中是否有数据，如果没有数据，则插入到header处
		if(pointers[header]==-2)
		{
			names[header]=name;
			pointers[header]=-1;
			return;
		}
		
		//首先获取可用位置
		int pos=getFreePos();
		if(pos==-1)
		{
			System.out.println("空间不足，无法插入数据!");
			return;
		}
		//把数据存入到pos位置
		names[pos]=name;
		//如果本节点不是首节点，则修改其前节点，让其指向本节点
		//注意：其前节点一定是指针值为-1的那个节点
		for(int i=0;i<names.length;i++)
		{
			if(pointers[i]==-1)
			{
				pointers[i]=pos;
				break;
			}
		}
		
		//本节点是尾节点，设置其pointer值为-1;
		pointers[pos]=-1;
	}
	
	public int getSize()
	{
		int counter=0;
		//pointer值不为-2的空间已被占用
		for(int i=0;i<names.length;i++)
		{
			if(pointers[i]==-2)
			{
				counter++;
			}
		}
		return names.length-counter;
	}
	
	public void setHeader(int header)
	{
		if(header>names.length)
		{
			System.out.println("指针头设置错误!");
			return;
		}
		this.header=header;
	}
	
	public int getHeader()
	{
		return header;
	}
	
	String[] getNames()
	{
		return names;
	}
	
	int[] getPointers()
	{
		return pointers;
	}
}