[关闭]
@ysner 2021-09-26T18:25:56.000000Z 字数 12404 阅读 1238

燕山楠的Homework 1

数据结构 JAVA

T1（核心为函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T1代码。核心代码为Del函数。
输入为“你想要删除的数字对应的序号”。

我的算法平均时间复杂度为O(1)：

因为当删除的元素不是最后一个时，时间复杂度是O(1)；当删除的元素是最后一个时，时间复杂度是O(n)。

但是删除n个元素的过程中只会出现一次删除最后一个元素，故平摊时间还是为O(1)。

  1. import java.util.Scanner;
  2. public class hw2_1
  3. {
  4.   public static class Node<Integer>
  5.   {
  6.     int data;
  7.     Node<Integer> next;
  8.     public Node()
  9.     {
  10.       next=null;
  11.     }
  12.     public Node(int d)
  13.     {
  14.       data=d;
  15.       next=null;
  16.     }
  17.   }
  18.   public static class List<Integer>
  19.   {
  20.     Node<Integer> head;
  21.     public List()
  22.     {
  23.       head=new Node<Integer>();
  24.       head.next=null;
  25.     }
  26.     public void CreateList(int[] a)
  27.     {
  28.       Node<Integer> s,t;
  29.       t=head;
  30.       for(int i=0;i<a.length;i++)
  31.       {
  32.         s=new Node<Integer>(a[i]);
  33.         t.next=s;
  34.         t=s;
  35.       }
  36.       t.next=null;
  37.     }
  38.     public void Del(Node<Integer> p)
  39.     /*函数思路：首先判断题目给的结点是否合法，不合法则直接报错。
  40.                 然后，如果给定的结点非尾结点，则直接用下一结点的信息覆盖该结点储存的信息；
  41.                 如果给定的结点是尾结点，则从头遍历找到该节点的前驱并修改它的next。   
  42.     （优化空间：如果让单链表维护一个next是尾结点的指针，可以做到每一次Del操作都是O(1)）
  43.     */
  44.     {
  45.       if(p==null) throw new IllegalArgumentException("you are deleting an unexisting object!");
  46.       if(p.next!=null) 
  47.       {
  48.         Node<Integer> t=p.next;
  49.         p.next=t.next;
  50.         p.data=t.data;
  51.       }
  52.       else
  53.       {
  54.          Node<Integer> s=head;
  55.          while(s.next.next!=null) s=s.next;
  56.          s.next=null;
  57.        }
  58.     }
  59.     public String toString()
  60.     {
  61.       String ans="";
  62.       Node<Integer> p=head.next;
  63.       while(p!=null)
  64.       {
  65.         ans+=p.data+" ";//字符串+数字=字符串
  66.         p=p.next;
  67.       }
  68.       return ans;
  69.     }
  70.   }
  71.   public static void main(String[] args)
  72.   {
  73.     Scanner in=new Scanner(System.in);
  74.     List<Integer> L=new List<Integer>();
  75.     Node<Integer> s=L.head;
  76.     int[] a=new int[]{1,9,2,6,0,8,1,7};
  77.     L.CreateList(a);
  78.     System.out.println("Please enter the sequence number you want to remove:");
  79.     int i=in.nextInt();
  80.     while(i>0)
  81.     {
  82.       if(s!=null) s=s.next;
  83.       i--;
  84.     }
  85.     L.Del(s);
  86.     System.out.println(L.toString());
  87.   }
  88. }

T2 （核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T2代码。核心代码为Del函数。

算法时间复杂度为O(n)，空间复杂度为O(1)。

  1. import java.util.Scanner;
  2. public class hw2_2
  3. {
  4.   public static class SqList<Integer>
  5.   {
  6.     final int initcap=10;
  7.     public int[] data;
  8.     public int size;
  9.     private int cap;
  10.     public SqList()
  11.     {
  12.       data=new int[initcap];
  13.       size=0;
  14.       cap=initcap;
  15.     }
  16.     public void updcap(int newcap)
  17.     {
  18.       int[] newdata=new int[newcap];
  19.       for(int i=0;i<size;i++) newdata[i]=data[i];
  20.       data=newdata;
  21.       cap=newcap;
  22.     } 
  23.     public void CreateList(int[] a)
  24.     {
  25.       size=0;
  26.       for(int i=0;i<a.length;i++)//Java特产：有直接测量数组长度的函数
  27.       {
  28.         if(size==cap) updcap(2*cap);
  29.         data[size]=a[i];
  30.         size++;
  31.       }
  32.     }
  33.     public void SetEle(int i,int w)
  34.     {
  35.       if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
  36.       data[i]=w;
  37.     }
  38.     public int GetEle(int i)
  39.     {
  40.       if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
  41.       return data[i];
  42.     }
  43.     public void Del()
  44.     /*函数思路：从头到尾遍历顺序表，若元素大于等于0，则用尾插法放入新顺序表；若元素小于0，则不管。
  45.                 但是鉴于原顺序表的值在遍历过一次后就没用了，故用新元素表的值直接覆盖原顺序表。
  46.     */
  47.     {
  48.       int t=0;
  49.       for(int i=0;i<size;i++)
  50.         if(data[i]>=0) 
  51.         {
  52.           SetEle(t,GetEle(i));
  53.           t++;
  54.         }
  55.       size=t;
  56.     }
  57.     public String toString()
  58.     {
  59.       String ans="";
  60.       for(int i=0;i<size;i++) ans+=data[i]+" ";
  61.       return ans;
  62.     }
  63.   }
  64.   public static void main(String[] args)
  65.   {
  66.     Scanner in=new Scanner(System.in);
  67.     int n=in.nextInt();
  68.     int[] a=new int[n];
  69.     for(int i=0;i<n;i++) a[i]=in.nextInt();
  70.     SqList<Integer> L=new SqList<Integer>();
  71.     L.CreateList(a);
  72.     L.Del();
  73.     System.out.println(L.toString());
  74.   }
  75. }

T3 （核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T3代码，与T2代码相比只改了Del函数。核心代码为Del函数。

输入第一行为n（顺序表大小），x，y。第二行为顺序表中的元素。

算法时间复杂度为O(n)，空间复杂度为O(1)

  1. import java.util.Scanner;
  2. public class hw2_3
  3. {
  4.   public static class SqList<Integer>
  5.   {
  6.     final int initcap=10;
  7.     public int[] data;
  8.     public int size;
  9.     private int cap;
  10.     public SqList()
  11.     {
  12.       data=new int[initcap];
  13.       size=0;
  14.       cap=initcap;
  15.     }
  16.     public void updcap(int newcap)
  17.     {
  18.       int[] newdata=new int[newcap];
  19.       for(int i=0;i<size;i++) newdata[i]=data[i];
  20.       data=newdata;
  21.       cap=newcap;
  22.     } 
  23.     public void CreateList(int[] a)
  24.     {
  25.       size=0;
  26.       for(int i=0;i<a.length;i++)//Java
  27.       {
  28.         if(size==cap) updcap(2*cap);
  29.         data[size]=a[i];
  30.         size++;
  31.       }
  32.     }
  33.     public void SetEle(int i,int w)
  34.     {
  35.       if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
  36.       data[i]=w;
  37.     }
  38.     public int GetEle(int i)
  39.     {
  40.       if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
  41.       return data[i];
  42.     }
  43.     public void Del(int x,int y)
  44.     /*函数思路：从头到尾遍历顺序表，若元素小于x或大于y，则用尾插法放入新顺序表。
  45.                 但是鉴于原顺序表的值在遍历过一次后就没用了，故用新元素表的值直接覆盖原顺序表的值，以节省空间。
  46.     */
  47.     {
  48.       int t=0;
  49.       for(int i=0;i<size;i++)
  50.         if(data[i]<x||data[i]>y) 
  51.         {
  52.           SetEle(t,GetEle(i));
  53.           t++;
  54.         }
  55.       size=t;
  56.     }
  57.     public String toString()
  58.     {
  59.       String ans="";
  60.       for(int i=0;i<size;i++) ans+=data[i]+" ";
  61.       return ans;
  62.     }
  63.   }
  64.   public static void main(String[] args)
  65.   {
  66.     Scanner in=new Scanner(System.in);
  67.     int n=in.nextInt(),x=in.nextInt(),y=in.nextInt();
  68.     int[] a=new int[n];
  69.     for(int i=0;i<n;i++) a[i]=in.nextInt();
  70.     SqList<Integer> L=new SqList<Integer>();
  71.     L.CreateList(a);
  72.     L.Del(x,y);
  73.     System.out.println(L.toString());
  74.   }
  75. }

T4（核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T4代码。核心代码为Plus函数。

输入第一行为m(A的元素个数),n(B的元素个数)；

第二行为A的元素；

第三行为B的元素。

算法时间复杂度为O(n+m)，空间复杂度为O(m+n)。

  1. import java.util.Scanner;
  2. public class hw2_4
  3. {
  4.   public static class SqList<Integer>
  5.   {
  6.     final int initcap=10;
  7.     public int[] data;
  8.     public int size;
  9.     private int cap;
  10.     public SqList()
  11.     {
  12.       data=new int[initcap];
  13.       size=0;
  14.       cap=initcap;
  15.     }
  16.     public void updcap(int newcap)
  17.     {
  18.       int[] newdata=new int[newcap];
  19.       for(int i=0;i<size;i++) newdata[i]=data[i];
  20.       data=newdata;
  21.       cap=newcap;
  22.     } 
  23.     public void Add(int w)
  24.     {
  25.       if(size==cap) updcap(2*cap);
  26.       data[size]=w;
  27.       size++;
  28.     }
  29.     public String toString()
  30.     {
  31.       String ans="";
  32.       for(int i=0;i<size;i++) ans+=data[i]+" ";
  33.       return ans;
  34.     }
  35.   }
  36.   public static SqList<Integer> Plus(SqList<Integer> A,SqList<Integer> B)
  37.   /*函数思路：二路归并
  38.               用i,j分别指向A,B顺序表开头的元素。然后比较指向的两元素。
  39.               若A表元素小于B表，则把A表元素插入新顺序表，i后移一位；
  40.               若A表元素大于B表，则把B表元素插入新顺序表，j后移一位;
  41.               若A表元素等于B表，则把A/B表元素插入新顺序表，i、j均后移一位。
  42.               直到一个表被遍历完为止。
  43.               然后把另一个表的剩余所有元素均按顺序插入新顺序表即可。
  44.  */
  45.   {
  46.     SqList<Integer> C=new SqList<Integer>();
  47.     int i=0,j=0;
  48.     while(i<A.size&&j<B.size)
  49.     {
  50.       if(A.data[i]<B.data[j])
  51.       {
  52.         C.Add(A.data[i]);
  53.         i++;
  54.       }
  55.       if(A.data[i]>B.data[j])
  56.       {
  57.         C.Add(B.data[j]);
  58.         j++;
  59.       }
  60.       if(A.data[i]==B.data[j])
  61.       {
  62.         C.Add(A.data[i]);
  63.         i++;j++;
  64.       }
  65.     }
  66.     while(i<A.size) 
  67.     {
  68.       C.Add(A.data[i]);
  69.       i++;
  70.     }
  71.     while(j<B.size) 
  72.     {
  73.       C.Add(B.data[j]);
  74.       j++;
  75.     }
  76.     return C; 
  77.   }
  78.   public static void main(String[] args)
  79.   {
  80.     Scanner in=new Scanner(System.in);
  81.     SqList<Integer> A=new SqList<Integer>(),B=new SqList<Integer>(),L;
  82.     int m=in.nextInt(),n=in.nextInt();
  83.     for(int i=0;i<m;i++) A.Add(in.nextInt());
  84.     for(int i=0;i<n;i++) B.Add(in.nextInt());
  85.     L=Plus(A,B);
  86.     System.out.println(L.toString());
  87.   }
  88. }

T5（核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T5代码。核心代码为Move函数。

输入第一行为n(单链表L的元素个数)；

第二行为L的元素。

  1. import java.util.Scanner;
  2. public class hw2_5
  3. {
  4.   public static class Node<Integer>
  5.   {
  6.     int data;
  7.     Node<Integer> next;
  8.     public Node()
  9.     {
  10.       next=null;
  11.     }
  12.     public Node(int d)
  13.     {
  14.       data=d;
  15.       next=null;
  16.     }
  17.   }
  18.   public static class List<Integer>
  19.   {
  20.     Node<Integer> head,tail;
  21.     public List()
  22.     {
  23.       head=new Node<Integer>();
  24.       tail=head;
  25.       head.next=null;
  26.     }
  27.     public void Add(int w)
  28.     {
  29.       Node<Integer> t=new Node<Integer>(w);
  30.       tail.next=t;
  31.       tail=t;
  32.     }
  33.     public List<Integer> Move()
  34.     /*函数思路：新建两个顺序表A，B。
  35.                 A存储负整数的元素，B存储其余元素。
  36.                 遍历原单链表，若元素是负整数，则用尾插法插入A，否则用尾插法插入B。
  37.                 最后将A尾结点的next赋值为B的头结点，以将A和B连接起来。
  38.                 将A的尾结点赋值为B的尾结点，使得A更加完整。
  39.                 A即为题目所求单链表。
  40.     */
  41.     {
  42.       List<Integer> A=new List<Integer>(),B=new List<Integer>();
  43.       Node<Integer> t=head.next;
  44.       while(t!=null)
  45.       {
  46.         if(t.data<0) A.Add(t.data);
  47.         else B.Add(t.data);
  48.         t=t.next;
  49.       }
  50.       A.tail.next=B.head.next;   
  51.       A.tail=B.tail;
  52.       return A;
  53.     }
  54.     public String toString()
  55.     {
  56.       String ans="";
  57.       Node<Integer> p=head.next;
  58.       while(p!=null)
  59.       {
  60.         ans+=p.data+" ";
  61.         p=p.next;
  62.       }
  63.       return ans;
  64.     }
  65.   }
  66.   public static void main(String[] args)
  67.   {
  68.     Scanner in=new Scanner(System.in);
  69.     List<Integer> L=new List<Integer>();
  70.     int n=in.nextInt();
  71.     for(int i=0;i<n;i++) L.Add(in.nextInt());
  72.     L=L.Move();
  73.     System.out.println(L.toString());
  74.   }
  75. }

T6（核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T6代码。核心代码为Diff函数。

输入第一行为m(A的元素个数),n(B的元素个数)；

第二行为A的元素；

第三行为B的元素。

算法时间复杂度为O(mn)，空间复杂度为O(m)。

  1. import java.util.Scanner;
  2. public class hw2_6
  3. {
  4.   public static class Node<Integer>
  5.   {
  6.     int data;
  7.     Node<Integer> next;
  8.     public Node()
  9.     {
  10.       next=null;
  11.     }
  12.     public Node(int d)
  13.     {
  14.       data=d;
  15.       next=null;
  16.     }
  17.   }
  18.   public static class List<Integer>
  19.   {
  20.     Node<Integer> head,tail;
  21.     public List()
  22.     {
  23.       head=new Node<Integer>();
  24.       tail=head;
  25.       head.next=null;
  26.     }
  27.     public void Add(int w)
  28.     {
  29.       Node<Integer> t=new Node<Integer>(w);
  30.       tail.next=t;
  31.       tail=t;
  32.     }
  33.     public boolean check(int w)
  34.     {
  35.       Node<Integer> t=head.next;
  36.       while(t!=null)
  37.       {
  38.         if(t.data==w) return true;
  39.         t=t.next;
  40.       }
  41.       return false;
  42.     }
  43.     public String toString()
  44.     {
  45.       String ans="";
  46.       Node<Integer> p=head.next;
  47.       while(p!=null)
  48.       {
  49.         ans+=p.data+" ";
  50.         p=p.next;
  51.       }
  52.       return ans;
  53.     }
  54.   }
  55.   public static List<Integer> Diff(List<Integer> A,List<Integer> B)
  56.   /*函数思路：遍历单链表A，判断每个元素是否是单链表B中的元素，若不是，则将该元素用尾插法插入新单链表C。
  57.               新单链表C即为题目所求。
  58.    */
  59.   {
  60.     List<Integer> C=new List<Integer>();
  61.     Node<Integer> t=A.head.next;
  62.     while(t!=null)
  63.     {
  64.       if(B.check(t.data)==false) C.Add(t.data);
  65.       t=t.next;
  66.     }
  67.     return C;
  68.   }
  69.   public static void main(String[] args)
  70.   {
  71.     Scanner in=new Scanner(System.in);
  72.     List<Integer> A=new List<Integer>(),B=new List<Integer>();
  73.     int m=in.nextInt(),n=in.nextInt();
  74.     for(int i=0;i<m;i++) A.Add(in.nextInt());
  75.     for(int i=0;i<n;i++) B.Add(in.nextInt());
  76.     System.out.println(Diff(A,B).toString());
  77.   }
  78. }

T7（核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T7代码。核心代码为Inter函数。

输入第一行为m(A的元素个数),n(B的元素个数)；

第二行为A的元素；

第三行为B的元素。

算法时间复杂度为O(n+m)，空间复杂度为O(m+n)。

后来我改进了数据结构，使得第二版代码的空间复杂度优化到O(1)。主要改动是：头插法不再插值，而是插节点。

  1. import java.util.Scanner;
  2. public class hw2_7
  3. {
  4.   public static class Node<Integer>
  5.   {
  6.     int data;
  7.     Node<Integer> next;
  8.     public Node()
  9.     {
  10.       next=null;
  11.     }
  12.     public Node(int d)
  13.     {
  14.       data=d;
  15.       next=null;
  16.     }
  17.   }
  18.   public static class List<Integer>
  19.   {
  20.     Node<Integer> head,tail;
  21.     public List()
  22.     {
  23.       head=new Node<Integer>();
  24.       tail=head;
  25.       head.next=null;
  26.     }
  27.     public void Add(int w)
  28.     {
  29.       Node<Integer> t=new Node<Integer>(w);
  30.       tail.next=t;
  31.       tail=t;
  32.     }
  33.     public void hAdd(int w)
  34.     {
  35.       Node<Integer> t=new Node<Integer>(w);
  36.       t.next=head.next;
  37.       head.next=t;
  38.     }
  39.     public String toString()
  40.     {
  41.       String ans="";
  42.       Node<Integer> p=head.next;
  43.       while(p!=null)
  44.       {
  45.         ans+=p.data+" ";
  46.         p=p.next;
  47.       }
  48.       return ans;
  49.     }
  50.   }
  51.   public static List<Integer> Inter(List<Integer> A,List<Integer> B)
  52.   /*函数思路：二路归并+头插法
  53.               用i,j分别指向A,B单链表开头的元素。然后比较指向的两元素。
  54.               若A表元素小于等于B表，则把A表元素用头插法插入新单链表C，i后移一位；
  55.               若A表元素大于B表，则把B表元素用头插法插入C，j后移一位;
  56.               直到一个表被遍历完为止。
  57.               然后把另一个表的剩余所有元素均按顺序用头插法插入C即可。
  58.               新单链表C即为题目所求。
  59.     */
  60.   {
  61.     List<Integer> C=new List<Integer>();
  62.     Node<Integer> a=A.head.next,b=B.head.next;
  63.     while(a!=null&&b!=null)
  64.     {
  65.       if(a.data<=b.data) 
  66.       {
  67.         C.hAdd(a.data);
  68.         a=a.next;
  69.       }
  70.       else
  71.       {
  72.         C.hAdd(b.data);
  73.         b=b.next;
  74.       }
  75.     }
  76.     while(a!=null) 
  77.     {
  78.       C.hAdd(a.data);
  79.       a=a.next;
  80.     }
  81.     while(b!=null) 
  82.     {
  83.       C.hAdd(b.data);
  84.       b=b.next;
  85.     }
  86.     return C;
  87.   }
  88.   public static void main(String[] args)
  89.   {
  90.     Scanner in=new Scanner(System.in);
  91.     List<Integer> A=new List<Integer>(),B=new List<Integer>();
  92.     int m=in.nextInt(),n=in.nextInt();
  93.     for(int i=0;i<m;i++) A.Add(in.nextInt());
  94.     for(int i=0;i<n;i++) B.Add(in.nextInt());
  95.     System.out.println(Inter(A,B).toString());
  96.   }
  97. }

第二版代码（优化后）

  1. //主要改动是：头插法不再插值，而是插节点。空间复杂度优化到O(1)
  2. import java.util.Scanner;
  3. public class hw2_7
  4. {
  5.   public static class Node<Integer>
  6.   {
  7.     int data;
  8.     Node<Integer> next;
  9.     public Node()
  10.     {
  11.       next=null;
  12.     }
  13.     public Node(int d)
  14.     {
  15.       data=d;
  16.       next=null;
  17.     }
  18.   }
  19.   public static class List<Integer>
  20.   {
  21.     Node<Integer> head,tail;
  22.     public List()
  23.     {
  24.       head=new Node<Integer>();
  25.       tail=head;
  26.       head.next=null;
  27.     }
  28.     public void Add(int w)
  29.     {
  30.       Node<Integer> t=new Node<Integer>(w);
  31.       tail.next=t;
  32.       tail=t;
  33.     }
  34.     public void hAdd(Node<Integer> t)
  35.     {
  36.       t.next=head.next;
  37.       head.next=t;
  38.     }
  39.     public String toString()
  40.     {
  41.       String ans="";
  42.       Node<Integer> p=head.next;
  43.       while(p!=null)
  44.       {
  45.         ans+=p.data+" ";
  46.         p=p.next;
  47.       }
  48.       return ans;
  49.     }
  50.   }
  51.   public static List<Integer> Inter(List<Integer> A,List<Integer> B)
  52.   {
  53.     List<Integer> C=new List<Integer>();
  54.     Node<Integer> a=A.head.next,b=B.head.next,t;
  55.     while(a!=null&&b!=null)
  56.     {
  57.       if(a.data<=b.data) 
  58.       {
  59.         t=a.next;
  60.         C.hAdd(a);
  61.         a=t;
  62.       }
  63.       else
  64.       {
  65.         t=b.next;
  66.         C.hAdd(b);
  67.         b=t;
  68.       }
  69.     }
  70.     while(a!=null) 
  71.     {
  72.       t=a.next;
  73.       C.hAdd(a);
  74.       a=t;
  75.     }
  76.     while(b!=null) 
  77.     {
  78.       t=b.next;
  79.       C.hAdd(b);
  80.       b=t;
  81.     }
  82.     return C;
  83.   }
  84.   public static void main(String[] args)
  85.   {
  86.     Scanner in=new Scanner(System.in);
  87.     List<Integer> A=new List<Integer>(),B=new List<Integer>();
  88.     int m=in.nextInt(),n=in.nextInt();
  89.     for(int i=0;i<m;i++) A.Add(in.nextInt());
  90.     for(int i=0;i<n;i++) B.Add(in.nextInt());
  91.     System.out.println(Inter(A,B).toString());
  92.   }
  93. }

T8（核心是函数）

第一次作业所有题目源代码的存放链接：https://www.zybuluo.com/ysner/note/1822311

本题代码为T8代码。核心代码为Inter函数。

输入第一行为m(A的元素个数),n(B的元素个数),k；

第二行为A的元素；

第三行为B的元素。

为保证程序的稳定性，我特判了k是否合法。

  1. import java.util.Scanner;
  2. public class hw2_8
  3. {
  4.   public static class Node<Integer>
  5.   {
  6.     int data;
  7.     Node<Integer> next;
  8.     public Node()
  9.     {
  10.       next=null;
  11.     }
  12.     public Node(int d)
  13.     {
  14.       data=d;
  15.       next=null;
  16.     }
  17.   }
  18.   public static class List<Integer>
  19.   {
  20.     Node<Integer> head,tail;
  21.     int size;
  22.     public List()
  23.     {
  24.       head=new Node<Integer>();
  25.       tail=head;
  26.       head.next=null;
  27.       size=0;
  28.     }
  29.     public void Add(int w)
  30.     {
  31.       Node<Integer> t=new Node<Integer>(w);
  32.       tail.next=t;
  33.       tail=t;
  34.       size++;
  35.     }
  36.     public String toString()
  37.     {
  38.       String ans="";
  39.       Node<Integer> p=head.next;
  40.       while(p!=null)
  41.       {
  42.         ans+=p.data+" ";
  43.         p=p.next;
  44.       }
  45.       return ans;
  46.     }
  47.   }
  48.   public static int Inter(List<Integer> A,List<Integer> B,int k)
  49.   /*函数思路：二路归并
  50.               先特判k是否合法，以保证程序的稳定性。
  51.               用i,j分别指向A,B双链表开头的元素。然后比较指向的两元素。
  52.               若A表元素小于等于B表，则把A表元素用尾插法插入新双链表C，i后移一位；
  53.               若A表元素大于B表，则把B表元素用尾插法插入新双链表C，j后移一位;
  54.               直到一个表被遍历完为止。
  55.               然后把另一个表的剩余所有元素均按顺序用尾插法插入新双链表C即可。
  56.               但是，整个过程中，只要插入了第k个元素，立即终止函数并返回值。
  57.     */
  58.   {
  59.     if(k<1||k>A.size+B.size) throw new IllegalArgumentException("K is not in the right range!");
  60.     List<Integer> C=new List<Integer>();
  61.     Node<Integer> a=A.head.next,b=B.head.next;
  62.     while(a!=null&&b!=null)
  63.     {
  64.       if(a.data<=b.data) 
  65.       {
  66.         C.Add(a.data);
  67.         if(C.size==k) return a.data;
  68.         a=a.next;
  69.       }
  70.       else
  71.       {
  72.         C.Add(b.data);
  73.         if(C.size==k) return b.data;
  74.         b=b.next;
  75.       }
  76.     }
  77.     while(a!=null) 
  78.     {
  79.       C.Add(a.data);
  80.       if(C.size==k) return a.data;
  81.       a=a.next;
  82.     }
  83.     while(b!=null) 
  84.     {
  85.       C.Add(b.data);
  86.       if(C.size==k) return b.data;
  87.       b=b.next;
  88.     }
  89.     return -1;
  90.   }
  91.   public static void main(String[] args)
  92.   {
  93.     Scanner in=new Scanner(System.in);
  94.     List<Integer> A=new List<Integer>(),B=new List<Integer>();
  95.     int m=in.nextInt(),n=in.nextInt(),k=in.nextInt();
  96.     for(int i=0;i<m;i++) A.Add(in.nextInt());
  97.     for(int i=0;i<n;i++) B.Add(in.nextInt());
  98.     System.out.println(Inter(A,B,k));
  99.   }
  100. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注