package 顺序表;
import java.util.ArrayList;
import java.util.Scanner;
public class OrderList {
/**
* @param args
* @author 刘雁冰
* @2015-1-31 21:00
*/
/*
* (以下所谓"位置"不是从0开始的数组下标表示法，而是从1开始的表示法.)
* (如12,13,14,15,16数据中，位置2上的数据即是13)
*
* 利用JAVA实现数据结构-线性表-顺序表
* 实现插入，查找，删除，合并等功能
* 插入:输入位置，返回该位置上的数据值
* 查找:输入查找的数据值，返回该数据值在顺序表中的位置
* 删除:输入要删除的位置，返回删除后的顺序表结果
* 合并:输入两组数据，并将两组数组按照升序结果合并在一起输出。
* 若两组数据中有重复的数值，在合并后的顺序表中结果唯一，保证无重复值
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("输入整型数字作为顺序表，输入-1结束输入过程:");
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
ArrayList<Integer>list=new ArrayList<Integer>();
while(m!=-1){
list.add(m);
m=sc.nextInt();
}
int a[]=new int[list.size()];
for (int i=0;i<list.size();i++){
a[i]=list.get(i);
}
System.out.println("********************请选择选项，确定要执行的操作:*******************************************");
System.out.println("********************选项--1:在指定位置上插入数据 *******************************************");
System.out.println("********************选项--2:根据数据查找第一次出现该数据的位置 ******************************");
System.out.println("********************选项--3:根据输入的位置，删除该位置上的数据 ******************************");
System.out.println("********************选项--4:输入两组数组，并将两组数组按照升序组合在一起 *********************");
int n=sc.nextInt();
OrderList order=new OrderList();
switch(n){
case 1:{
System.out.println("请输入要插入的位置:");
int insertP=sc.nextInt();
System.out.println("请输入要插入该位置的值:");
int insertN=sc.nextInt();
order.ListInsert(list, insertP, insertN);
break;
}
case 2:{
System.out.println("请输入要查找的数据");
int searchP=sc.nextInt();
System.out.println("第一次出现该数据所在的位置是:");
System.out.println(order.ListSeach(a,searchP)+"号位置");
break;
}
case 3:{
System.out.println("请输入要删除的位置:");
Scanner delete=new Scanner(System.in);
int deleteP=delete.nextInt();
order.ListDelete(a, deleteP);
break;
}
case 4:{
System.out.println("请输入第一个数组，按-1结束输入");
Scanner sc1=new Scanner(System.in);
int num1=sc1.nextInt();
ArrayList<Integer>list1=new ArrayList<Integer>();
while(num1!=-1){
list1.add(num1);
num1=sc1.nextInt();
}
int la[]=new int[list1.size()];
for(int i=0;i<list1.size();i++){
la[i]=list1.get(i);
}
System.out.println("请输入第二个数组，按-1结束输入");
Scanner sc2=new Scanner(System.in);
int num2=sc2.nextInt();
ArrayList<Integer>list2=new ArrayList<Integer>();
while(num2!=-1){
list2.add(num2);
num2=sc2.nextInt();
}
int lb[]=new int[list2.size()];
for(int i=0;i<list2.size();i++){
lb[i]=list2.get(i);
}
order.ListMerge(la, lb);
break;
}
default:{
System.out.println("输入有误!");
System.out.println();
System.out.print("请重新");
order.main(null);
break;
}
}
}
/*
* 插入方法
* insertPoint:插入位置
* insertValue:插入数值
* ArrayList list:将输入的数据链表传递过来
* int []a:获取list链表值并且保存在a数组中，作为结果输出
*/
public void ListInsert(ArrayList list,int insertPoint,int insertValue){
int j;
if(insertPoint<1||insertPoint>list.size()){
System.out.println("插入位置错误!");
}
list.add(insertPoint-1,insertValue);
Object []a=new Object[list.size()];
for(int i=0;i<list.size();i++){
a[i]=list.get(i);
}
System.out.println("插入后的结果如下:");
//结果消除最后一个数值的,符号
for(int i=0;i<a.length;i++){
if(i==a.length)
System.out.print(a[i]);
else
System.out.print(a[i]+",");
}
}
/*
* int []a:传递main()方法中构造好的数组
* searchPoint:要查找的数值的位置
*/
public int ListSeach(int []a,int searchPoint){
int i=0;
while(i<=a.length&&a[i]!=searchPoint){
i++;
}
if(i<=a.length)
return i+1; //返回的是位置，非数组下标
else
return 0;
}
/*
* int []a:传递main()方法中构造好的数组
* deletePoint:要删除的位置
*/
public void ListDelete(int []a,int deletePoint){
int j;
if(deletePoint<1||deletePoint>a.length){
System.out.println("删除位置错误!");
}
//将deletePoint位置后的数据值前移
for(j=deletePoint;j<a.length;j++){
a[j-1]=a[j];
}
System.out.println("删除指定位置的数据后的结果如下：");
//结果消除最后一个数值的,符号
//这里特定不输出数组最后一个数值
for(int i=0;i<a.length-1;i++){
if(i==a.length-2)
System.out.print(a[i]);
else
System.out.print(a[i]+",");
}
}
/*
* int[] a,int []b:为新输入的两个数组
*/
public void ListMerge(int []la,int []lb){
ArrayList<Integer> listC=new ArrayList<Integer>();
int i,j,t;
i=0;j=0;
//对数组a进行简单排序
for(i=0;i<la.length;i++){
for(j=0;j<la.length-i-1;j++){
if(la[j]>la[j+1]){
t=la[j];
la[j]=la[j+1];
la[j+1]=t;
}
}
}
//对数组b进行简单排序
for(i=0;i<lb.length;i++){
for(j=0;j<lb.length-i-1;j++){
if(la[j]>lb[j+1]){
t=lb[j];
lb[j]=lb[j+1];
lb[j+1]=t;
}
}
}
i=0;j=0;
while(i<la.length&&j<lb.length){
if(la[i]<lb[j]) //a,b数组中，先输入较小数
listC.add(la[i++]);
else{
if(la[i]==lb[j]){ //a,b数组中有重复值的情况下，输入a数组该位置的值，确保合并后的数组没有重复值
listC.add(la[i++]);
j++; //跳过b数组中该位置的值
}
else
listC.add(lb[j++]);
}
}
//两个while循环，确保a,b数组比较后剩余的值均存入合并后的数组中
while(i<la.length){
listC.add(la[i++]);
}
while(j<lb.length){
listC.add(lb[j++]);
}
System.out.println();
System.out.println("两个数组合并之后的结果是:");
int []lc=new int [listC.size()];
for(int k=0;k<listC.size();k++){
lc[k]=listC.get(k);
}
for(int k=0;k<lc.length;k++){
if(k==lc.length-1)
System.out.println(lc[k]);
else
System.out.print(lc[k]+",");
}
}
}