数据结构——JAVA实现静态链表

淡淡的烟草味﹌ 2022-06-16 23:54 140阅读 0赞

# 数据结构——JAVA实现静态链表 #

package com.kexin.study2;
    
    import java.util.Scanner;
    
    /**
     * 用JAVA实现静态链表 完成学生信息基本操作
     * 
     * @author KeXin
     *
     */
    
    public class NodeList {
    	static final int Max_Size = 100;
    	static Scanner scan = new Scanner(System.in);
    	Node list[];
    	int av[]; // 使用游标只是模拟指针但是删除元素的时候并没有从数组中删除，所以会浪费很多空间，
    	int av_len; // 使用av将数组中可以覆盖掉上的位置记录下来当加入新元素的时候使用av
    	int length;
    	String name;
    	double score;
    
    	/**
    	 * 初始化链表
    	 * 
    	 * @param list
    	 * @param cur
    	 */
    	public NodeList(int size) {
    		this.list = new Node[Max_Size];
    		this.length = size;
    		this.av = new int[10];
    		this.av_len = 1;
    		Node node = new Node(null, 0, 0);
    		this.list[0] = node;
    		this.list[0].setCur(1);
    		for (int i = 1; i <= size; i++) {
    			node = new Node(null, 0, 0);
    			System.out.print("Input No." + i + " student's name:");
    			this.name = scan.next();
    			System.out.print("Input No." + i + " student's score:");
    			this.score = scan.nextDouble();
    			this.list[i] = node;
    			this.list[i].setName(name);
    			this.list[i].setScore(score);
    			this.list[i].setCur(i + 1);
    		}
    		this.list[size].setCur(0);
    		this.av[0] = size+1;
    	}
    
    	/**
    	 * 获取位置i上的元素
    	 * 
    	 * @param L
    	 * @param i
    	 * @return
    	 */
    	public Node GetElem(NodeList L, int i) {
    		Node node = L.list[i];
    		return node;
    	}
    
    	/**
    	 * 插入新元素
    	 * 
    	 * @param L
    	 * @param i
    	 * @param n
    	 * @return
    	 */
    	public NodeList InsertList(NodeList L, int i) {
    		int j = L.length;
    		if (i < 0 || i > j) {
    			System.out.println("Error!Wrong position to insert!");
    			return L;
    		}
    		if (j < Max_Size) {
    			System.out.print("Input No." + i + " student's name:");
    			this.name = scan.next();
    			System.out.print("Input No." + i + " student's score:");
    			this.score = scan.nextDouble();
    			int pre_cur = 0; // 要插入位置的前驱元素
    			for (int m = 0; m < i - 1; m++) {
    				pre_cur = L.list[m].getCur();
    			}
    			int p_cur = L.list[pre_cur].getCur(); // 要插入位置的后继元素
    			int p = L.av[L.av_len-1];
    			Node n = new Node(name, score, p_cur);
    			L.list[p] = n;
    			L.list[pre_cur].setCur(p);
    			if(L.av_len==1){
    				L.length++;
    			}else{
    				L.av_len--;
    			}
    		} else {
    			System.out.println("Error!No space to insert!");
    		}
    		return L;
    	}
    
    	/**
    	 * 删除元素
    	 * 
    	 * @param L
    	 * @param i
    	 * @return
    	 */
    	public NodeList DeleteList(NodeList L, int i) {
    		int len = L.length;
    		int pre_cur, p_cur;
    		if (i < 0 || i > len) {
    			System.out.println("Error!Wrong position to delete!");
    			return L;
    		}
    		if (len > 0) {
    			pre_cur = 0; // 要删除位置的前驱元素
    			for (int m = 0; m < i - 1; m++) {
    				pre_cur = L.list[m].getCur();
    			}
    			int p = L.list[pre_cur].getCur();	//要删除元素的位置 添加到av
    			L.av[L.av_len] = p;
    			L.av_len++;
    			p_cur = L.list[L.list[pre_cur].getCur()].getCur(); // 要删除位置的后继元素
    			L.list[pre_cur].setCur(p_cur);
    			System.out.println(L.list[pre_cur].getName());
    			// L.length--;
    		} else {
    			System.out.println("Error!No element to delete!");
    		}
    		return L;
    	}
    
    	/**
    	 * 打印链表
    	 * 
    	 * @param L
    	 */
    	public void PrintList(NodeList L) {
    		int len = L.length;
    		Node n;
    		System.out.println("i, name, score, cur");
    		for (int i = 0; i <= len; i++) {
    			n = L.list[i];
    			System.out.println("[" + i + "," + n.getName() + "," + n.getScore() + "," + n.getCur() + "]");
    		}
    	}
    
    	public static void main(String[] args) {
    		System.out.print("Input the size of list:");
    		int size = scan.nextInt();
    		NodeList list = new NodeList(size);
    		list.PrintList(list);
    		System.out.print("No.1:");
    		Node node = list.GetElem(list, 1);
    		System.out.println("[" + node.getName() + "," + node.getScore() + "]");
    		System.out.print("Input the position to insert:");
    		list = list.InsertList(list, scan.nextInt());
    		list.PrintList(list);
    		System.out.print("Input the position to delete:");
    		list.DeleteList(list, scan.nextInt());
    		list.PrintList(list);
    		System.out.print("Input the position to insert:");
    		list = list.InsertList(list, scan.nextInt());
    		list.PrintList(list);
    	}
    }
    class Node {
    	private String name;
    	private double score;
    	int cur;
    
    	public Node(String name, double score, int cur) {
    		super();
    		this.name = name;
    		this.score = score;
    		this.cur = cur;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    
    	public double getScore() {
    		return score;
    	}
    
    	public void setScore(double score) {
    		this.score = score;
    	}
    
    	public int getCur() {
    		return cur;
    	}
    
    	public void setCur(int cur) {
    		this.cur = cur;
    	}
    }