Java及MySQL常见面试题.docx

Java实现单链表：链表中的节点。key代表节点的值，next是指向下一个节点的指针package com.primer.structure.single_list;02/* * 单链表 节点 * author sd */08 public class Node_Single 09 public String key;/节点的值11 public Node_Single next;/指向下一个的指针12 public Node_Single(String key)/初始化head14 this.key = key;15 this.next = null;16 17 public Node_Single(String key,Node_Single next)18 this.key = key;19 this.next = next;20 21 public String getKey() 22 return key;23 24 public void setKey(String key) 26 this.key = key;27 28 public Node_Single getNext() 30 return next;31 32 public void setNext(Node_Single next) 34 this.next = next;35 36 Override37 public String toString() 38 return Node_Single key= + key + , next= + next + ;39 2.代码简单实现的单链表。链表的遍历，增加，删除package com.primer.structure.single_list;/* * 单链表 * author sd * */public class SingleList private Node_Single head = null;/头节点private Node_Single tail = null;/尾节点(空节点)相当于哨兵元素/* * 初始化一个链表（设置head ） * param key */public void initList(Node_Single node)head = node;head.next = tail;/* * 添加一个元素 * param node */public void addTolist(Node_Single node)if(head = null)initList(node);elseNode_Single tmp = head;head = node;node.next = tmp;/* * 遍历链表，删除某一个节点 * param node * param myList */public void deleteNode(Node_Single node,SingleList myList)if(myList = null)return ;Node_Single tmp =null;for(tmp = myList.getHead();tmp!=null;tmp = tmp.next)if(tmp.next !=null & node.getKey().equals(tmp.next.getKey()/该元素和后一个元素相同。指针指向下一元素的下一元素if(tmp.next.next != null)tmp.next = tmp.next.next;elsetmp.next = null;public void printList(SingleList myList)Node_Single tmp =null;for(tmp = myList.getHead();tmp!=null;tmp = tmp.next)System.out.println(tmp.getKey();public Node_Single getHead() return head;public void setHead(Node_Single head) this.head = head;public Node_Single getTail() return tail;public void setTail(Node_Single tail) this.tail = tail;public static void main(String args)SingleList myList = new SingleList();Node_Single node_1 = new Node_Single(1);Node_Single node_2 = new Node_Single(2);Node_Single node_3 = new Node_Single(3);Node_Single node_4 = new Node_Single(4);Node_Single node_5 = new Node_Single(5);Node_Single node_6 = new Node_Single(6);Node_Single node_7 = new Node_Single(7);myList.addTolist(node_1);myList.addTolist(node_2);myList.addTolist(node_3);myList.addTolist(node_4);myList.addTolist(node_5);myList.addTolist(node_6);myList.addTolist(node_7);myList.deleteNode(node_3, myList);myList.printList(myList);另外的实现java实现范型单、双结点，单双列表(2008-10-20 17:51:01)转载/单结点的定义public class MyNode T data;MyNode next;/ MyNode node;/默认构造方法/ MyNode()/data=0;/构造方法MyNode(T node)this.data=node;/重载toString()方法，方便输出。public String toString()return String.valueOf(data);public static void main(String args) MyNode node1=new MyNode(35);MyNode node2=new MyNode(66);System.out.println(node1:+node1.data);System.out.println(node2:+node2.data);/双结点的定义import java.util.*;class MyDNode extends MyNode/ MyDNode node;T pre;/qianT next;/hou/ T data;MyDNode(T data)super(data);this.pre=null;MyDNode(MyNode node)super(node);this.pre=null;public String toString()return String.valueOf(data);public static void main(String args) MyDNode n=new MyDNode(35);System.out.println(n);/单链表的实现public class MyList public MyNode head;public T node;public int length;MyList()head=null;length=0;MyList(T n)this.node=n;length=1;/get length of listpublic int getLength()return length;public String toString() /输出的格式String s=;MyNode tempNode=head;for(int i=1;i=length;i+)s=s+getNode(i)+-;tempNode=tempNode.next;return s;/将节点node添加到单链表末尾void append(MyNode node)if(node=null)return;if(head=null)head=node;elsegetNode(length).next=node;length+;/根据参数返回单链表的第pos个节点MyNode getNode(int pos)if(lengthpos|pos1)return null;MyNode tempNode=head;for(int i=1;ipos;i+)tempNode=tempNode.next;return tempNode;/刪除MyNode delNode(int pos)if(poslength)return null; MyNode tempnode=getNode(pos);/獲得要刪除的結點if(pos=1)/head nodehead=getNode(1).next;/直接刪除頭指針else getNode(pos-1).next=tempnode.next;/tepnode.pre=getNode(pos=1).pre;tempnode.next=null;length-=1;return tempnode;MyNode insertNode(int pos)MyNode e = new MyNode(8);if(poslength)return null;MyNode newnode=getNode(pos);if(pos=1)/head nodehead=getNode(1).next;/直接插入頭指針else /getNode(pos-1).next=newnode.next;/e.next=newnode;/getNode(pos).next=e;e.next = getNode(pos).next;getNode(pos).next = e;/newnode.next=null;length+=1;return newnode;/合并两个单链表，将第二个单链表连接到第一个单链表末尾；static void join(MyList ml_a,MyList ml_b)if(ml_a.length=0)ml_a=ml_b;return;ml_a.getNode(ml_a.length).next=ml_b.getNode(1);ml_a.length+=ml_b.length; /翻转一个单链表；void convert()if(length0;i-)temp.next=getNode(i);temp=temp.next;temp.next=null;head=head2;/复制一个单链表void copyList()/判断单链表是否相等boolean equals(MyList ml)return false;public static void main (String args) MyList ml=new MyList();MyList m2=new MyList();/ MyList ee=new MyList(99);/System.out.print(ee);MyNode nodes=new MyNode5;for(int i=0;inodes.length;i+)/wrong:nodesi.data=i*10;nodesi=new MyNode(i*5);m2.append(nodesi);MyNode n =new MyNode(1);MyNode n1 =new MyNode(21);MyNode n2 =new MyNode(31);ml.append(n); /将节点node添加到单链表末尾ml.append(n1); /将节点node添加到单链表末尾ml.append(n2); System.out.print(列表一：);System.out.println(ml);System.out.print(列表二：);System.out.println(m2);/System.out.print(列表一翻转后为：);/ml.convert();System.out.print(列表二翻转后为：);m2.convert();System.out.println(m2);System.out.println(合并后的列表为：);MyList.join(ml,m2);System.out.println(ml);ml.delNode(3);System.out.println(删除第三个元素后的列表为：);System.out.println(ml);System.out.println(插入第三个元素后的列表为：);ml.insertNode(2);System.out.println(ml);/双链表的实现class MyDlist2 extends MyListT pre;/-构造函数MyDlist2()head=null;pre=null;length=0;MyDlist2(T n) / head=n;pre=n;length=1;MyDNode dell(int pos) /删除列表结点if(poslength)return null; MyDNode tempnode=(MyDNode)getNod(pos);if(pos=1)/删除head nodegetNod(pos+1).pre=null;else /如果删除的不是头结点getNod(pos-1).next=tempnode.next;getNod(pos+1).pre=tempnode.pre;length-=1;return tempnode;MyDNode getNod(int pos)if(lengthpos|pos1)return null;MyDNode tempNode=(MyDNode)head;for(int i=1;i=pos;i+)tempNode=(MyDNode)tempNode.next;/tempNode.pre=getNod(pos-1);return tempNode;MyDNode inserlist(int pos,MyDNode date) /插入列表结点if(poslength)return null; /MyDNode newnode=(MyDNode)getNod(2);if(pos=1)/head nodegetNod(1).next=null;else /如果插入的不是头结点qian chagetNod(pos-1).next=date;getNod(pos).pre=date;date.pre=getNod(pos-1);date.next=getNod(pos);/newnode.next=null;length+=1;return date;public static void main (String args) MyDlist2 aa=new MyDlist2();MyDlist2 cc=new MyDlist2();MyDNode bb=new MyDNode(8);MyDNode nodes=new MyDNode5;for(int i=0;inodes.length;i+)nodesi=new MyDNode(i*10);aa.append(nodesi);MyDNode www=new MyDNode4;for(int i=0;iwww.length;i+)wwwi=new MyDNode(i*3);cc.append(wwwi);System.out.println(Dlist1 is:+cc);cc.convert();System.out.println(Dlist1 conver :+cc);System.out.println(Dlist2 is:+aa);aa.convert();System.out.println(Dlist1 conver :+aa);/aa.dell(2);/ System.out.println(Dlist2 del:+aa);aa.inserlist(3,bb);System.out.println(Dlist2insert:+aa); / MyDlist2.join(aa,cc);/System.out.println(Two Dlist join :+aa);几种经典算法排序：/插入排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/* * author treeroot * since 2006-2-2 * version 1.0 */public class InsertSort implements SortUtil.Sort /* (non-Javadoc) * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void sort(int data) int temp; for(int i=1;i0)&(datajdataj-1);j-) SortUtil.swap(data,j,j-1); /冒泡排序:for(var i=0; iarr.length; i+) for(var j=i+1; j=arr.length-1; j+) if(eval(arri) eval(arrj) temp = arri;arri = arrj;arrj = temp;package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/* * author treeroot * since 2006-2-2 * version 1.0 */public class BubbleSort implements SortUtil.Sort /* (non-Javadoc) * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void sort(int data) int temp; for(int i=0;ii;j-) if(datajdataj-1) SortUtil.swap(data,j,j-1); /选择排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/* * author treeroot * since 2006-2-2 * version 1.0 */public class SelectionSort implements SortUtil.Sort /* * (non-Javadoc) * * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void sort(int data) int temp; for (int i = 0; i i; j-) if (dataj 2;i/=2) for(int j=0;ji;j+) insertSort(data,j,i); insertSort(data,0,1); /* * param data * param j * param i */ private void insertSort(int data, int start, int inc) int temp; for(int i=start+inc;i=inc)&(dataj1) quickSort(data,i,k-1); if(j-k)1) quickSort(data,k+1,j); /* * param data * param i * param j * return */ private int partition(int data, int l, int r,int pivot) do while(data+lpivot); SortUtil.swap(data,l,r); while(l0) int j=stacktop-; int i=stacktop-; pivotIndex=(i+j)/2; pivot=datapivotIndex; SortUtil.swap(data,pivotIndex,j); /partition l=i-1; r=j; do while(data+lpivot); SortUtil.swap(data,l,r); while(lTHRESHOLD) stack+top=i; stack+top=l-1; if(j-l)THRESHOLD) stack+top=l+1; stack+top=j; /new InsertSort().sort(data); insertSort(data); /* * param data */ private void insertSort(int data) int temp; for(int i=1;i0)&(datajdataj-1);j-) SortUtil.swap(data,j,j-1); /归并排序:package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/* * author treeroot * since 2006-2-2 * version 1.0 */public class MergeSort implements SortUtil.Sort /* (non-Javadoc) * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void sort(int data) int temp=new intdata.length; mergeSort(data,temp,0,data.length-1); private void mergeSort(int data,int temp,int l,int r) int mid=(l+r)/2; if(l=r) return ; mergeSort(data,temp,l,mid); mergeSort(data,temp,mid+1,r); for(int i=l;i=r;i+) tempi=datai; int i1=l; int i2=mid+1; for(int cur=l;curr) datacur=tempi1+; else if(tempi1= THRESHOLD) mergeSort(data, temp, l, mid); else insertSort(data, l, mid - l + 1); if (r - mid) THRESHOLD) mergeSort(data, temp, mid + 1, r); else insertSort(data, mid +