@ysner
2021-09-26T18:25:56.000000Z
字数 12404
阅读 1177
数据结构
JAVA
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T1代码。核心代码为Del函数。
输入为“你想要删除的数字对应的序号”。
我的算法平均时间复杂度为O(1):
因为当删除的元素不是最后一个时,时间复杂度是O(1);当删除的元素是最后一个时,时间复杂度是O(n)。
但是删除n个元素的过程中只会出现一次删除最后一个元素,故平摊时间还是为O(1)。
import java.util.Scanner;
public class hw2_1
{
public static class Node<Integer>
{
int data;
Node<Integer> next;
public Node()
{
next=null;
}
public Node(int d)
{
data=d;
next=null;
}
}
public static class List<Integer>
{
Node<Integer> head;
public List()
{
head=new Node<Integer>();
head.next=null;
}
public void CreateList(int[] a)
{
Node<Integer> s,t;
t=head;
for(int i=0;i<a.length;i++)
{
s=new Node<Integer>(a[i]);
t.next=s;
t=s;
}
t.next=null;
}
public void Del(Node<Integer> p)
/*函数思路:首先判断题目给的结点是否合法,不合法则直接报错。
然后,如果给定的结点非尾结点,则直接用下一结点的信息覆盖该结点储存的信息;
如果给定的结点是尾结点,则从头遍历找到该节点的前驱并修改它的next。
(优化空间:如果让单链表维护一个next是尾结点的指针,可以做到每一次Del操作都是O(1))
*/
{
if(p==null) throw new IllegalArgumentException("you are deleting an unexisting object!");
if(p.next!=null)
{
Node<Integer> t=p.next;
p.next=t.next;
p.data=t.data;
}
else
{
Node<Integer> s=head;
while(s.next.next!=null) s=s.next;
s.next=null;
}
}
public String toString()
{
String ans="";
Node<Integer> p=head.next;
while(p!=null)
{
ans+=p.data+" ";//字符串+数字=字符串
p=p.next;
}
return ans;
}
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
List<Integer> L=new List<Integer>();
Node<Integer> s=L.head;
int[] a=new int[]{1,9,2,6,0,8,1,7};
L.CreateList(a);
System.out.println("Please enter the sequence number you want to remove:");
int i=in.nextInt();
while(i>0)
{
if(s!=null) s=s.next;
i--;
}
L.Del(s);
System.out.println(L.toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T2代码。核心代码为Del函数。
算法时间复杂度为O(n),空间复杂度为O(1)。
import java.util.Scanner;
public class hw2_2
{
public static class SqList<Integer>
{
final int initcap=10;
public int[] data;
public int size;
private int cap;
public SqList()
{
data=new int[initcap];
size=0;
cap=initcap;
}
public void updcap(int newcap)
{
int[] newdata=new int[newcap];
for(int i=0;i<size;i++) newdata[i]=data[i];
data=newdata;
cap=newcap;
}
public void CreateList(int[] a)
{
size=0;
for(int i=0;i<a.length;i++)//Java特产:有直接测量数组长度的函数
{
if(size==cap) updcap(2*cap);
data[size]=a[i];
size++;
}
}
public void SetEle(int i,int w)
{
if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
data[i]=w;
}
public int GetEle(int i)
{
if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
return data[i];
}
public void Del()
/*函数思路:从头到尾遍历顺序表,若元素大于等于0,则用尾插法放入新顺序表;若元素小于0,则不管。
但是鉴于原顺序表的值在遍历过一次后就没用了,故用新元素表的值直接覆盖原顺序表。
*/
{
int t=0;
for(int i=0;i<size;i++)
if(data[i]>=0)
{
SetEle(t,GetEle(i));
t++;
}
size=t;
}
public String toString()
{
String ans="";
for(int i=0;i<size;i++) ans+=data[i]+" ";
return ans;
}
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++) a[i]=in.nextInt();
SqList<Integer> L=new SqList<Integer>();
L.CreateList(a);
L.Del();
System.out.println(L.toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T3代码,与T2代码相比只改了Del函数。核心代码为Del函数。
输入第一行为n(顺序表大小),x,y。第二行为顺序表中的元素。
算法时间复杂度为O(n),空间复杂度为O(1)
import java.util.Scanner;
public class hw2_3
{
public static class SqList<Integer>
{
final int initcap=10;
public int[] data;
public int size;
private int cap;
public SqList()
{
data=new int[initcap];
size=0;
cap=initcap;
}
public void updcap(int newcap)
{
int[] newdata=new int[newcap];
for(int i=0;i<size;i++) newdata[i]=data[i];
data=newdata;
cap=newcap;
}
public void CreateList(int[] a)
{
size=0;
for(int i=0;i<a.length;i++)//Java
{
if(size==cap) updcap(2*cap);
data[size]=a[i];
size++;
}
}
public void SetEle(int i,int w)
{
if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
data[i]=w;
}
public int GetEle(int i)
{
if(i<0||i>=size) throw new IllegalArgumentException("i is not in the range!");
return data[i];
}
public void Del(int x,int y)
/*函数思路:从头到尾遍历顺序表,若元素小于x或大于y,则用尾插法放入新顺序表。
但是鉴于原顺序表的值在遍历过一次后就没用了,故用新元素表的值直接覆盖原顺序表的值,以节省空间。
*/
{
int t=0;
for(int i=0;i<size;i++)
if(data[i]<x||data[i]>y)
{
SetEle(t,GetEle(i));
t++;
}
size=t;
}
public String toString()
{
String ans="";
for(int i=0;i<size;i++) ans+=data[i]+" ";
return ans;
}
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int n=in.nextInt(),x=in.nextInt(),y=in.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++) a[i]=in.nextInt();
SqList<Integer> L=new SqList<Integer>();
L.CreateList(a);
L.Del(x,y);
System.out.println(L.toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T4代码。核心代码为Plus函数。
输入第一行为m(A的元素个数),n(B的元素个数);
第二行为A的元素;
第三行为B的元素。
算法时间复杂度为O(n+m),空间复杂度为O(m+n)。
import java.util.Scanner;
public class hw2_4
{
public static class SqList<Integer>
{
final int initcap=10;
public int[] data;
public int size;
private int cap;
public SqList()
{
data=new int[initcap];
size=0;
cap=initcap;
}
public void updcap(int newcap)
{
int[] newdata=new int[newcap];
for(int i=0;i<size;i++) newdata[i]=data[i];
data=newdata;
cap=newcap;
}
public void Add(int w)
{
if(size==cap) updcap(2*cap);
data[size]=w;
size++;
}
public String toString()
{
String ans="";
for(int i=0;i<size;i++) ans+=data[i]+" ";
return ans;
}
}
public static SqList<Integer> Plus(SqList<Integer> A,SqList<Integer> B)
/*函数思路:二路归并
用i,j分别指向A,B顺序表开头的元素。然后比较指向的两元素。
若A表元素小于B表,则把A表元素插入新顺序表,i后移一位;
若A表元素大于B表,则把B表元素插入新顺序表,j后移一位;
若A表元素等于B表,则把A/B表元素插入新顺序表,i、j均后移一位。
直到一个表被遍历完为止。
然后把另一个表的剩余所有元素均按顺序插入新顺序表即可。
*/
{
SqList<Integer> C=new SqList<Integer>();
int i=0,j=0;
while(i<A.size&&j<B.size)
{
if(A.data[i]<B.data[j])
{
C.Add(A.data[i]);
i++;
}
if(A.data[i]>B.data[j])
{
C.Add(B.data[j]);
j++;
}
if(A.data[i]==B.data[j])
{
C.Add(A.data[i]);
i++;j++;
}
}
while(i<A.size)
{
C.Add(A.data[i]);
i++;
}
while(j<B.size)
{
C.Add(B.data[j]);
j++;
}
return C;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
SqList<Integer> A=new SqList<Integer>(),B=new SqList<Integer>(),L;
int m=in.nextInt(),n=in.nextInt();
for(int i=0;i<m;i++) A.Add(in.nextInt());
for(int i=0;i<n;i++) B.Add(in.nextInt());
L=Plus(A,B);
System.out.println(L.toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T5代码。核心代码为Move函数。
输入第一行为n(单链表L的元素个数);
第二行为L的元素。
import java.util.Scanner;
public class hw2_5
{
public static class Node<Integer>
{
int data;
Node<Integer> next;
public Node()
{
next=null;
}
public Node(int d)
{
data=d;
next=null;
}
}
public static class List<Integer>
{
Node<Integer> head,tail;
public List()
{
head=new Node<Integer>();
tail=head;
head.next=null;
}
public void Add(int w)
{
Node<Integer> t=new Node<Integer>(w);
tail.next=t;
tail=t;
}
public List<Integer> Move()
/*函数思路:新建两个顺序表A,B。
A存储负整数的元素,B存储其余元素。
遍历原单链表,若元素是负整数,则用尾插法插入A,否则用尾插法插入B。
最后将A尾结点的next赋值为B的头结点,以将A和B连接起来。
将A的尾结点赋值为B的尾结点,使得A更加完整。
A即为题目所求单链表。
*/
{
List<Integer> A=new List<Integer>(),B=new List<Integer>();
Node<Integer> t=head.next;
while(t!=null)
{
if(t.data<0) A.Add(t.data);
else B.Add(t.data);
t=t.next;
}
A.tail.next=B.head.next;
A.tail=B.tail;
return A;
}
public String toString()
{
String ans="";
Node<Integer> p=head.next;
while(p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
List<Integer> L=new List<Integer>();
int n=in.nextInt();
for(int i=0;i<n;i++) L.Add(in.nextInt());
L=L.Move();
System.out.println(L.toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T6代码。核心代码为Diff函数。
输入第一行为m(A的元素个数),n(B的元素个数);
第二行为A的元素;
第三行为B的元素。
算法时间复杂度为O(mn),空间复杂度为O(m)。
import java.util.Scanner;
public class hw2_6
{
public static class Node<Integer>
{
int data;
Node<Integer> next;
public Node()
{
next=null;
}
public Node(int d)
{
data=d;
next=null;
}
}
public static class List<Integer>
{
Node<Integer> head,tail;
public List()
{
head=new Node<Integer>();
tail=head;
head.next=null;
}
public void Add(int w)
{
Node<Integer> t=new Node<Integer>(w);
tail.next=t;
tail=t;
}
public boolean check(int w)
{
Node<Integer> t=head.next;
while(t!=null)
{
if(t.data==w) return true;
t=t.next;
}
return false;
}
public String toString()
{
String ans="";
Node<Integer> p=head.next;
while(p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
}
public static List<Integer> Diff(List<Integer> A,List<Integer> B)
/*函数思路:遍历单链表A,判断每个元素是否是单链表B中的元素,若不是,则将该元素用尾插法插入新单链表C。
新单链表C即为题目所求。
*/
{
List<Integer> C=new List<Integer>();
Node<Integer> t=A.head.next;
while(t!=null)
{
if(B.check(t.data)==false) C.Add(t.data);
t=t.next;
}
return C;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
List<Integer> A=new List<Integer>(),B=new List<Integer>();
int m=in.nextInt(),n=in.nextInt();
for(int i=0;i<m;i++) A.Add(in.nextInt());
for(int i=0;i<n;i++) B.Add(in.nextInt());
System.out.println(Diff(A,B).toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T7代码。核心代码为Inter函数。
输入第一行为m(A的元素个数),n(B的元素个数);
第二行为A的元素;
第三行为B的元素。
算法时间复杂度为O(n+m),空间复杂度为O(m+n)。
后来我改进了数据结构,使得第二版代码的空间复杂度优化到O(1)。主要改动是:头插法不再插值,而是插节点。
import java.util.Scanner;
public class hw2_7
{
public static class Node<Integer>
{
int data;
Node<Integer> next;
public Node()
{
next=null;
}
public Node(int d)
{
data=d;
next=null;
}
}
public static class List<Integer>
{
Node<Integer> head,tail;
public List()
{
head=new Node<Integer>();
tail=head;
head.next=null;
}
public void Add(int w)
{
Node<Integer> t=new Node<Integer>(w);
tail.next=t;
tail=t;
}
public void hAdd(int w)
{
Node<Integer> t=new Node<Integer>(w);
t.next=head.next;
head.next=t;
}
public String toString()
{
String ans="";
Node<Integer> p=head.next;
while(p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
}
public static List<Integer> Inter(List<Integer> A,List<Integer> B)
/*函数思路:二路归并+头插法
用i,j分别指向A,B单链表开头的元素。然后比较指向的两元素。
若A表元素小于等于B表,则把A表元素用头插法插入新单链表C,i后移一位;
若A表元素大于B表,则把B表元素用头插法插入C,j后移一位;
直到一个表被遍历完为止。
然后把另一个表的剩余所有元素均按顺序用头插法插入C即可。
新单链表C即为题目所求。
*/
{
List<Integer> C=new List<Integer>();
Node<Integer> a=A.head.next,b=B.head.next;
while(a!=null&&b!=null)
{
if(a.data<=b.data)
{
C.hAdd(a.data);
a=a.next;
}
else
{
C.hAdd(b.data);
b=b.next;
}
}
while(a!=null)
{
C.hAdd(a.data);
a=a.next;
}
while(b!=null)
{
C.hAdd(b.data);
b=b.next;
}
return C;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
List<Integer> A=new List<Integer>(),B=new List<Integer>();
int m=in.nextInt(),n=in.nextInt();
for(int i=0;i<m;i++) A.Add(in.nextInt());
for(int i=0;i<n;i++) B.Add(in.nextInt());
System.out.println(Inter(A,B).toString());
}
}
//主要改动是:头插法不再插值,而是插节点。空间复杂度优化到O(1)
import java.util.Scanner;
public class hw2_7
{
public static class Node<Integer>
{
int data;
Node<Integer> next;
public Node()
{
next=null;
}
public Node(int d)
{
data=d;
next=null;
}
}
public static class List<Integer>
{
Node<Integer> head,tail;
public List()
{
head=new Node<Integer>();
tail=head;
head.next=null;
}
public void Add(int w)
{
Node<Integer> t=new Node<Integer>(w);
tail.next=t;
tail=t;
}
public void hAdd(Node<Integer> t)
{
t.next=head.next;
head.next=t;
}
public String toString()
{
String ans="";
Node<Integer> p=head.next;
while(p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
}
public static List<Integer> Inter(List<Integer> A,List<Integer> B)
{
List<Integer> C=new List<Integer>();
Node<Integer> a=A.head.next,b=B.head.next,t;
while(a!=null&&b!=null)
{
if(a.data<=b.data)
{
t=a.next;
C.hAdd(a);
a=t;
}
else
{
t=b.next;
C.hAdd(b);
b=t;
}
}
while(a!=null)
{
t=a.next;
C.hAdd(a);
a=t;
}
while(b!=null)
{
t=b.next;
C.hAdd(b);
b=t;
}
return C;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
List<Integer> A=new List<Integer>(),B=new List<Integer>();
int m=in.nextInt(),n=in.nextInt();
for(int i=0;i<m;i++) A.Add(in.nextInt());
for(int i=0;i<n;i++) B.Add(in.nextInt());
System.out.println(Inter(A,B).toString());
}
}
第一次作业所有题目源代码的存放链接:https://www.zybuluo.com/ysner/note/1822311
本题代码为T8代码。核心代码为Inter函数。
输入第一行为m(A的元素个数),n(B的元素个数),k;
第二行为A的元素;
第三行为B的元素。
为保证程序的稳定性,我特判了k是否合法。
import java.util.Scanner;
public class hw2_8
{
public static class Node<Integer>
{
int data;
Node<Integer> next;
public Node()
{
next=null;
}
public Node(int d)
{
data=d;
next=null;
}
}
public static class List<Integer>
{
Node<Integer> head,tail;
int size;
public List()
{
head=new Node<Integer>();
tail=head;
head.next=null;
size=0;
}
public void Add(int w)
{
Node<Integer> t=new Node<Integer>(w);
tail.next=t;
tail=t;
size++;
}
public String toString()
{
String ans="";
Node<Integer> p=head.next;
while(p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
}
public static int Inter(List<Integer> A,List<Integer> B,int k)
/*函数思路:二路归并
先特判k是否合法,以保证程序的稳定性。
用i,j分别指向A,B双链表开头的元素。然后比较指向的两元素。
若A表元素小于等于B表,则把A表元素用尾插法插入新双链表C,i后移一位;
若A表元素大于B表,则把B表元素用尾插法插入新双链表C,j后移一位;
直到一个表被遍历完为止。
然后把另一个表的剩余所有元素均按顺序用尾插法插入新双链表C即可。
但是,整个过程中,只要插入了第k个元素,立即终止函数并返回值。
*/
{
if(k<1||k>A.size+B.size) throw new IllegalArgumentException("K is not in the right range!");
List<Integer> C=new List<Integer>();
Node<Integer> a=A.head.next,b=B.head.next;
while(a!=null&&b!=null)
{
if(a.data<=b.data)
{
C.Add(a.data);
if(C.size==k) return a.data;
a=a.next;
}
else
{
C.Add(b.data);
if(C.size==k) return b.data;
b=b.next;
}
}
while(a!=null)
{
C.Add(a.data);
if(C.size==k) return a.data;
a=a.next;
}
while(b!=null)
{
C.Add(b.data);
if(C.size==k) return b.data;
b=b.next;
}
return -1;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
List<Integer> A=new List<Integer>(),B=new List<Integer>();
int m=in.nextInt(),n=in.nextInt(),k=in.nextInt();
for(int i=0;i<m;i++) A.Add(in.nextInt());
for(int i=0;i<n;i++) B.Add(in.nextInt());
System.out.println(Inter(A,B,k));
}
}