【Java数据结构】线性表

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了哨位结点）。 

我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。 在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。 

线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。(以上定义参考百度，懒得解释#-_-)

线性表模型

package cn.deu;

public class MyArray {
     long [] arr;

     int num;

	public MyArray() {
		arr=new long[50];
	}

	public MyArray(int n){
		arr=new long[n];
	}

	//插入
	public void insert(int n){
		//无序插入法/*arr[num++]=n;*/
		//冒泡法
		/*long t=0;
		arr[num++]=n;
		for (int i = 0; i < num; i++) {
			for (int j = i+1; j < num; j++) {
				if(arr[i]>arr[j])
				{
					t=arr[i];
					arr[i]=arr[j];
					arr[j]=t;
				}
			}
		}*/
		int i;
		for (i = 0; i < num; i++) {
			if(arr[i]>n)
				break;
		}

		for (int j = num; j > i; j--) {
			arr[j]=arr[j-1];
		}
		arr[i]=n;
		num++;
	}

	//查找
	public int find(int n){
		//线性查找
//		for (int i = 0; i < num; i++) {
//			if(arr[i]==n)
//				return i;
//		}
//		return -1;
		int lower=0;
		int upper=num;
		int mid=0;

		//二分查找
		while(true)
		{
			mid=(lower+upper)/2;
			if(arr[mid]==n)
				return mid;
			else
			if(lower>upper)
			return -1;
			else
			{	if(arr[mid]>n)
			    upper=mid-1;
				else
			    lower=mid+1;
			}
		}
	}

	//显示
	public void show(){
		for (int i = 0; i < num; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}

	//删除
	public void delete(int n){
		if(find(n)==-1)
			System.out.println("没有发现数据，删除失败！");
		else
		{
			for (int i = find(n); i < num; i++) {
				arr[i]=arr[i+1];
			}
			num--;
		}
	}

	//修改
	public void change(int n,int m){
		if(find(n)==-1)
			System.out.println("没有发现数据，修改失败！");
		else
		{
			arr[find(n)]=m;
		}
	}

}

线性表测试

package en.edu.Test;

import cn.deu.MyArray;

public class Test {

	public static void main(String[] args) {
		MyArray list=new MyArray();
		//插入测试
        list.insert(12);
        list.insert(2134);
        list.insert(132);
        list.insert(67);
        list.insert(9);
        list.insert(12345);
        list.insert(90);
        //查找测试
        System.out.println(list.find(132));
        System.out.println(list.find(110));
        //显示测试
        list.show();
        //删除测试
        list.delete(12345);
        list.show();
        list.delete(15);
        list.show();
        //修改测试
        list.change(9, 45);
        list.show();
        list.change(14, 20);
        list.show();
	}

}

结果：
4
-1
9 12 67 90 132 2134 12345 
9 12 67 90 132 2134 
没有发现数据，删除失败！
9 12 67 90 132 2134 
45 12 67 90 132 2134 
没有发现数据，修改失败！
45 12 67 90 132 2134 

转载请注明出处：http://blog.csdn.net/acmman/article/details/50520267