linked-06.java

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

//=====================程序描述==================
//程序名称:linked-06.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();
		
		System.out.println("反转数据之前的状态");
		System.out.println();

		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();
		System.out.println();
		
		//反转数据
		stu.reverse();
		
		System.out.println("------------------------------------------------------------------------------");
		System.out.println("反转数据之后的状态");
		System.out.println();

		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();

		//按链表顺序打印数据
		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[10];
	//存储指向下一个学生的指针
	private int[] pointers=new int[10];
	//链表头
	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;
	}
	
	public int IndexOf(String value)
	{
		//链表的查找只能从链表头开始找
		int ptr;
		ptr=header;
		int index=-1;
		while(ptr!=-1)
		{
			index++;
			if(names[ptr]==value)
			{
				return index;
			}
			ptr=pointers[ptr];
		}
		return -1;
	}
	
	public void insert(int index,String value)//插入的数据作为链表的第index个节点
	{
		//第一步，检查链表中是否还有可用空间
		if(getFreePos()==-1)
		{
			System.out.println("链表中空间不足!");
			return;
		}
		//第二步，检查插入索引是否超出了链表当前的索引
		if(index<0 | index>getSize())
		{
			System.out.println("你所指定的索引不是合法的索引值!");
			return;
		}
		//第三步，将新的节点先放入到数组中，并且要记录放入位置
		int pos=getFreePos();//pos是新节点的物理位置
		
		//插入
		names[pos]=value;
		
		//第四步，判断是否是要插入到链表的首部
		if(index==0)
		{
			//让新插入元素的指针指向原链表的首部
			pointers[pos]=header;
			//改变链表的头部，让其指向新插入的元素
			header=pos;
		}
		else
		{
			//需要从header开始，顺藤摸瓜找到index-1位置
			int ptr=header;
			for(int i=0;i<index-1;i++)
			{
				ptr=pointers[ptr];
			}
			//新插入节点的指针指向原来index-1位置节点的指针
			pointers[pos]=pointers[ptr];
			//让索引为index-1位置的节点的指针指向这个新节点
			pointers[ptr]=pos;
		}
	}
	public void delete(int index)
	{
		if(getSize()==0)
		{
			System.out.println("链表中没有节点!");
			return;
		}
		//判断将要删除的元素的索引是否在合法的索引范围内
		if(index<0 | index>getSize())
		{
			System.out.println("索引超出边界!");
			return;
		}
		//判断是否是删除第一个节点
		if(index==0)
		{
			//保存指针值
			int tempptr=header;
			//设置第二个元素为链表头
			header=pointers[header];
			//将第一个元素从内存中释放
			names[tempptr]=null;
			pointers[tempptr]=-2;
		}
		else
		{
			//找到要删除的节点的前一节点(的物理位置)
			int ptr;
			ptr=header;
			for(int i=0;i<index-1;i++)
			{
				ptr=pointers[ptr];
			}
			//保存将要删除的节点的物理位置值
			int tempptr=pointers[ptr];
			//让将要删除的节点的前一节点的指针指向被删除的节点的指针
			pointers[ptr]=pointers[tempptr];
			//释放要删除的节点占用的内存
			names[tempptr]=null;
			pointers[tempptr]=-2;
		}
	}
	public void reverse()
	{
		int ptr=header;
		int curPos;
		int n=0;
		int next;
		next=pointers[ptr];//保存下一节点位置
		while(true)
		{
			curPos=ptr;//保存当前位置
			ptr=next;//得到下一位置
			
			if(n==0)//说明是链表中的第一项
			{
				pointers[curPos]=-1;//变为结束项
			}
			next=pointers[ptr];//修改下一节点指针之前先保存
			pointers[ptr]=curPos;//将下一节点指向本节点
			if(next==-1)//说明是尾节点
			{
				header=ptr;
				break;
			}
			n++;
		}
	}
}