insert.java

已经编写好的数据结构课本程序可以减轻您的负担

// =============== Program Description ===============
// 程序名称： insert.java                               
// 程序目的： 设计一个在链表内插入节点的程序。 
// Written By Kuo-Yu Huang. (WANT Studio.)            
// ===================================================
import ConsoleReader.*;				// 导入已定义的数据输入类

public class insert
{	
	public static void main (String args[])
	{
		int Data[][] =			// 输入数据
			{{  1,  3,  5,  7,  2,
			    4,  6,  8,  9,  0},
		  	 { 15, 35, 10, 67, 25,
		  	   65, 38, 70, 30, 20} };
		  
		Node NewList = new Node();	// 产生一个Node类		
		int DataNum;			// 数据的编号
		int DataTotal;			// 数据的总数
		int KeyValue;			// 欲插入位置
		int Header = 0;			// 首节点位置
		int FreeNode;			// 可用节点
		int NewNode;			// 新节点位置
		int i;				// 循环计数变量
				
		for ( i=0 ; i<10 ; i++ )
		{
			FreeNode = NewList.FindFree();
			DataNum = Data[0][i];	// 设定数据编号
			DataTotal = Data[1][i];	// 设定数据总数

			NewList.Create(Header,FreeNode,DataNum,DataTotal);
		}
		
		NewList.PrintList(Header);
		System.out.println("Enter 0 to EXIT");
		
		while (true)
		{		
			NewNode = NewList.FindFree();			
			System.out.print("Please input the data number : ");
						// 读入数据的编号
			ConsoleReader console = new ConsoleReader(System.in);								
			DataNum = console.readInt();
			
			if ( DataNum == 0 )
				break;
		
			System.out.print("Please input the data total : ");
						// 读入数据的总数					
			DataTotal = console.readInt();
		
			NewList.Num[NewNode] = DataNum;
			NewList.Total[NewNode] = DataTotal;
			System.out.print("Please input the data number for Insert : ");
						// 读入欲插入位置
			KeyValue = console.readInt();
						// 调用插入节点
			Header = NewList.Insert(Header,NewNode,KeyValue);
			NewList.PrintList(Header);
			System.out.println("Enter 0 to EXIT");				
		}
	}
	
}

class Node
{
	int MaxLength = 20;			// 定义链表的最大长度
	int Num[] = new int[MaxLength];	// 链表的数据项
	int Total[] = new int[MaxLength];	// 链表的数据项
	int Next[] = new int[MaxLength];	// 链表的下一个节点位置
	
	public Node ()				// Node构造函数
	{
		for ( int i = 0 ; i < MaxLength ; i++ )
			Next[i] = -2;		// -2表示未用节点
	}
	
// ---------------------------------------------------
// 查找可用节点位置
// ---------------------------------------------------	
	public int FindFree()
	{
		int	i;

		for ( i=0 ; i< MaxLength ; i++ )
			if ( Next[i] == -2 )
				break;
		return i;
	}

// ---------------------------------------------------
// 建立链表
// ---------------------------------------------------		
	public void Create(int Header,int FreeNode,int DataNum,int DataTotal)
	{
		int Pointer;			// 现在的节点位置
	
		if ( Header == FreeNode )	// 新的链表
		{	
			Num[Header] = DataNum;	// 设定数据编号
			Total[Header] = DataTotal;// 设定数据名称
			Next[Header] = -1;	// 将下一个节点的位置，-1表示空节点
		}
		else
		{			
			Pointer = Header;	// 现在的节点为首节点							
			Num[FreeNode] = DataNum;// 设定数据编号
						// 设定数据名称
			Total[FreeNode] = DataTotal;
			Next[FreeNode] = -1;	// 将下一个节点的位置，-1表示空节点
						// 找寻链表尾端
			while ( Next[Pointer] != -1)
				Pointer = Next[Pointer];

						// 将新节点串联在原链表尾端
			Next[Pointer] = FreeNode;	
		}
	}

// ---------------------------------------------------
// 打印出链表数据
// ---------------------------------------------------		
	public void PrintList(int Header)
	{
		int	Pointer;
		
		Pointer = Header;
		while ( Pointer != -1 )
		{
			System.out.print("["+Num[Pointer]);
			System.out.print(","+Total[Pointer]+"]");
			Pointer = Next[Pointer];
		}
		System.out.println("");
	}
	
// ---------------------------------------------------
// 插入节点至链表内                            
// ---------------------------------------------------
	public int Insert(int Header,int NewNode,int KeyValue)
	{
		int	Pointer;		// 节点声明

		Pointer = Header;		// Pointer指针设为首节点

		while ( true )
		{
			if ( Pointer == -1 )	// 插入在首节点前
			{
				Next[NewNode] = Header;
				Header = NewNode;
				break;
			}
			if ( Num[Pointer] == KeyValue ) // 插入在链表中间或尾端
			{
				Next[NewNode] = Next[Pointer];
				Next[Pointer] = NewNode;
				break;
			}
				Pointer = Next[Pointer];	// 往下一个节点
		}
		return Header;
	}	
}