还剩37页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第一章绪论上机实训设为在算法前边定义的整数类型已赋值的变量,分析下列各算法中加下划线语句的执
1.n行次数,并给出各算法的时间复杂度Tn1int i=1,k=0;While in-1{k=k+10*i;i=i+1;2int i=1,k=0;do{k=k+10*i;i=i+1;}while i!=n;3int i=1,j=1;while i=nj=n{i=i+1;;j=j+14int x=n;int y=0;whilex=y+1*y+1{;y++5int i,j,k,x=0;Fori=0;in;i++For j=0;ji;j++For k=0;kj;k++x=x+2;参考答案1On2On3On4On1/25On
3.如下算法是用冒泡排序法对数组中的个整数类型的数据元素从小到大进行排序,求2a n该算法的时间复杂度void bubbleSort int a[]{int n=a.length;㊀int i,j,t mp,flag=l;fori=l;inflag==l;i++{flag=0;forj=0;jn-i;j++{//在尾部插入元素public voidaddT element{//如果链表是空的if header==null{header=new Nodeelement,null;//只有一个节点,都该指向该节点headwe,tail tail=header;else{;//仓建新节点Node newNode=new Nodeelement,null Utail.next;//尾节点的指向新节点将新节点作为㊀㊀=newNod nexttail=n wNode;//尾节点++;㊀siz//头部插入public voidaddAtHeadT element{//创建新节点,让新节点的指向//并以新节点作为新的next headerheaderNode newNode=new Nodeelement,null;newNode.next=header;header=newNode;//若插入前是空表if tail==null{tail=header;size++;//删除指定索引处的元素㊀㊀㊀㊀public Tci1tint ind x{ifindex0||indexsize-1{索弓超出线性表范围”;}throw newIndexOutOfBoundsException INodedel=null;//若要删除的是头节点ifindex==0{del=header;header=header.next;else;//获取待删除节点的前一个节Node prev=getNodeBylndex index-1点获取待删除节点㊀㊀del=pr v.n xt;//prev.next=del.next;工;//将被删除节点的引用置为空del.next=nu1nextsize--;return del.data;//删除最后一个元素public Tremove{return deletesize-1;//判断线性表是否为空public booleanisEmpty{return size==0;//清空线性表public voidclear{//将置为header,tail nullheader=null;tail=null;size=0;public StringtoString{n nif isEmpty{return[];}else{㊀;StringBuilder sb=new StringBuildr[”forNode current=header;current!=null;current=current.next{Hsb,appendcurrent.data.toString+”,;;int len=sb.length[㊀㊀HHreturn sb.delete n-2,len.app nd.toString;大链表反转*Greturn*/㊀㊀㊀㊀public NodeReverseIteratively{Nod pRv rsedHad=this.header;NodepNode=this.header;Node pPrev=null;while pNode!=null{,㊀㊀Node pNext=pNod nxt;if pNext==null{pReversedHead=pNode;pNode.next=pPrev;pPrev=pNode;pNode=pNext;this.header=pReversedHead;return this.header;大查找单链表的中间节点*Qreturn*/public NodeSearchMid{Node p=this.header q=this.header;fwhile p!=nullp.next!=nullp.next.next!=null p=p.next.next;q=q.next;nSystem.out.printinMid:+q.data;return q;//测试类public classMain02{public static void mainString[]args throwsException{//测试构造函数LinkListInteger list=new LinkList1;//测试添加元素・for int i=2;i=9;i++list addi;System.out.printInlist;//链表反转list.ReverseIteratively;System.out.printinlist;//查找单链表的中间节点list,SearchMid;System.out.printInlist;第三章栈和队列上机实训
1.编写一个程序,用两个队列实现一个栈参考答案package c03;import java.util.LinkedList;import java.util.Queue;public classMainOl{public static void mainString[]args{.pushl;push2;.push3;.pop0;push4;pop;pop;private staticQueueObject queuel=new LinkedListObject;private staticQueueObject queue2=new LinkedListObject;public staticvoid pushObjectitem{if Iqueuel.isEmpty queue
1.offeritem;elsequeue
2.offeritem;System.out.printing入栈元素为+item;.public staticvoid pop{if!isEmpty{ifqueue
1.isEmpty{whilequeue
2.sizel{queue
1.offerqueue
2.poll;System,out.printin“出栈元素为+queue
2.poll;.}else{while queue
1.sizel{queue
2.offer queue
1.isEmptyqueue
2.isEmptyO;
2.编写一个程序,输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序参考答案package c03;import java.util.Arrays;import java.util.Stack;public classMain02{public staticvoid mainString[]args{int[]arrl={1,2,3,4,5};int[]arr2={4,5,3,2,1};System.out.print In进栈序列+Arrays.toString arrl;System,out.print In进栈序列+Arrays.toString arr2;System,out.printin判断结果+IsPopOrder arrl,arr2;public staticboolean IsPopOrderint[]pushA,int口popA{StackInteger stack=new StackO;forint i=0,j=0;ipushA.length;{stack,pushpushA[i++1;while!stack.isEmptystack,peek==popA[j]jpopA.lengthstack,pop;.j++;}return stack.isEmpty;・第四章串上机实训
1.已知两个串si二〃fg cdbcabcadr”,s2二〃abc〃,试求两个串的长度,判断串s2是否是串si的子串,并指出串s2在串si中的位置参考答案public classMain02{public staticvoid mainString[]args{String si=T ma student”,s2=student”,s3=teacher”;System.out.printin si.indexOf s2;System.out.printin si.indexOf s3;System.out.printin s
2.charAt3;System.out.printin s
3.substring2,5;}si:14;s2:3s2在si的开始位置是
92.已知si二Tm a student”,s2=〃student”,s3=〃teacher”,试求下列各运算的结果
51.indexOf s2;
52.indexOf s3;
53.charAt3;
54.substring2,5;参考答案public classMain02{public staticvoid mainString[]args{String si二T mastudent”,s2=student”,s3=teacher”;System.out.printin si.indexOf s2;System,out.printin si.indexOf s3;System,out.printin s
2.charAt3;System.out.printlns
3.substring2,5;6-1dach
3.设s、t为两个字符串,分别放在两个一维数组中,m、n分别为其长度,判断t是否为s的子串如果是,输出子串所在位置第一个字符,否则输出0参考答案public classMain03{public staticint strMatchchar[]s,char[]t{int i二0,j=0;int m=s.length,n=t.length;if mnreturn0;else{fori=0;im;i++{forj=0;jn;j++{ifsLi+j]!=t[j]break;else{ifj=n-ls[i+j]=t[j]return i+1;return0;public staticvoid mainString[]args{int m,n;System.out.printin请输入两个字符串的长度M和N;Scanner sc=new ScannerSystem,in;m=sc.nextlnt;n=sc.nextlnt;sc.nextLine;System,out.printin请输入第一个长度为+m+”的字符串;char[]s二sc.nextLine.toCharArray;System.out.printin请输入第二个长度为+n+”的字符串;chart]t=sc.nextLine.toCharArray;System.out.printin t;
4.输入一个字符串,内有数字和非数字字符,如akl23x45617960302gef4563,将其中连续的数字作为一个整体,依次存放到一数组a中,例如123放入a
[0],456放入a[l],…编程统计其共有多少个整数,并输出这些数参考答案import java.util.Scanner;public classMain04{public staticvoid mainString[]args{Scanner sc二new ScannerSystem.zn;System,o〃力printin”请输入字符串:;char[]s=sc.nextLine.toCharArray;int[]a=new int
[100];boolean flag=false;String tmp=int c=0;forint i=O;is.length;i++{ifflag{ifs[i]=,0,s[i]=,9,{tmp+=s[i];}else{a[c]=Integer,parse历ftmp;C++;flag=false;tmp=nn;}else{ifs[i]=,0,s[i]=,9,{tmp+=s[i];flag=true;ifi==s.length-lflag=true{a[c]=Integer.pi-setmp;C++;System.owtprintlnc;forint i=0;ic;i++{System.o〃£.printa[i]+H H;
5.编写程序,统计在输入字符串中各个不同字符出现的频度参考答案import java.util.Scanner;public classMain05{public staticvoid mainString[]args{Scanner sc=new ScannerSystem.fn;System.o〃f.println请输入字符串:;char[J ch=sc.nextLine.toCharArray;char[]s=new char
[100];int[]num=new int
[100];if a[j]a[j4-l]{flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;参考答案0n
23.下边算法是一个有n个数据元素的数组a中删除第pos个位置的数组元素,求该算法的时间复杂度boolean deleteinta[],int pos{int n=a.length;if pos0||pos=n//删除失败返回return false;for int j=pos+l;jn;j++{//顺次移位填补a[j-l]=a[j];//删除成功返回return true;参考答案0n
4.分析如下算法的空间复杂度staticvoidreversalint[]a,int[]b{int n=a.length;forint i=0;in;i++{b[i]=a[n-l-i];参考答案0nint i=0,j=0,n=0;fori=0;ich.length;i++{forj=0;jvn;j++ifch[i]=s[j]break;ifjn{num[j]++;}else{s[n]=ch[i];num[n]=l;n++;fori=0;in;i++System.oeLprintln“字符+s[i]+”出现了+num[i]+次第五章多维数组和广义表上机实训如果矩阵中存在这样的一个元素满足条件是第行中值最小的元素,且I.A A[i,j]A[i,j]i又是第列中值最大的元素,此时则称之为该矩阵的一个马鞍点请编程查找出的矩阵j M*N A中的所有马鞍点参考答案import java.util.Scanner;public classMainOl{public staticvoid mainString[]args{Scanner sc=new ScannerSystem.in;int m=sc.nextlnt;int n=sc.nextlnt;;//定义的数组/数据元素的输入int[][]a=new int[m][n]M*Nfor int i=0;im;i++{for intj=0;jn;j++{a[i][j]=sc.nextlnt;}int[]R=new int[m];int[]C=new int[n];.找每行的最小值并保存到数组中//I Rfor int i=0;im;i++{R[i]=a[i]
[0];for intj=l;jn;j++{ifR[i]a[i][j]{R[i]=a[i][j];},找每列的最大值并保存到数组中//2Cfor intj=0;jn;j++{C[j]=a
[0][j];for int i=l;im;i++{if C[j]a[i][j]{C[j]=a[i][j];}.遍历每个元素与和的值是否相等,如果相等则是马鞍点//3a[i][j],R[i]C[j]并输出for inti=0;im;i++{for intj=0;jn;j++{if a[i][j]==R[i]a[i][j]==C[j]第+彳亍,第+歹System.out.printIn i+1+”j+1+”U:n+a[i][j];
2.编写程序实现广义表以下相关操作广义表的构造、求广义表的深度、求广义表的长度、按照深度优先顺序打印广义表、求广义表表头、求广义表表尾参考答案import java.util.Stack;广义表操作*、广义表的构造*1构造一个空的广义表*1,
11.2根据现有的广义表,构造一个新的广义表*根据广义表字符串构造一个广义表*
1.
3、广义表的深度*
2、广义表的长度*
3、按照深度优先顺序打印广义表*
4、求广义表表头*
5、求广义表表尾{㊀㊀㊀*6public classGen ralizdTabl//原子节点public staticfinal intTAG_ITEM=0;//表节点public staticfinal intTAG_TABLE=1;大广义表支持的符号包括,,},,*广义表表示符号,使用字符串构造广义表时第一个字符必须是,,L L之(I—并以,L,,尸,,「之一结束,大并且各符号相对应11private charmStartSymb=;11private charmEndSymb=;private NodemGenTable;public GeneralizedTable{㊀mGenTable=new Nod null,null,TAG_TABLE,null;//使用广义表构造一个新的广义表srcpublic GeneralizedTableGeneralizedTablesrc{if src!=null{mGenTable=src.mGenTable;*@param genTable*/public GeneralizedTableStringgenTable{if genTable==null{throw㊀㊀㊀new NullPointerExceptiongenTable isnull inconstructor Gn ralizdTabl㊀!・・,;}initTablegenTable;private voidinitTableString genTable{String ts=n ngenTable.replaceAll\\s,;int len=ts.length;StackCharacter symbStack=new StackCharacter;StackNodenodeStck=new StackNode;initSymbolicCharactorts;mGenTable=new㊀Nodnull,null,TAG_TABLE,null;Node itemNode,tableNode=mGenTable,tmpNode;for inti=0;ilen;i++{if ts.charAti==mStartSymb{tmpNode=new Nodenull,null,TAG_TABLE,null;//tableNode=tableNode.mPt;symbStack.pushts.charAti;if symbStack.size1{nodeStck.pushtableNode;tableNode.mPh=tmpNode;tableNode=tableNode.mPh;}else{tableNode.mPt=tmpNode;tableNode=tableNode.mPt;}else ifts.charAti==mEndSymb{if symbStack.isEmpty{throw newIllegalArgumentException IllegalArgumentException inconstructor・・・GeneralizedTable!;if symbStack.size1{tableNode=nodeStck.pop;symbStack.pop;}else ifts.charAti==,{tableNode.mPt=new Nodenull,null,TAG_TABLE,null;tableNode=tableNode.mPt;}else{㊀㊀it mNocte=new Nodmill,null,TAG_ITEM,ts.charAt i;tableNode.mPh=itemNode;if!symbStack.isEmpty{throw newnIllegalArgumentExceptionIllegalArgumentExceptioninconstructorGeneralizedTable}private voidinitSymbolicCharactorString ts{mStartSymb=ts.charAt0;switch mStartSymb{11case:1TmEndSymb=;break;1case*{:1fmEndSymb=};㊀br ak;1case*[:!]T;mEndSymb=break;default:throw newIllegalArgumentException IllegalArgumentExceptioninitSymbolicCharactor;}public voidprint{printmGenTable;private voidprintNode node{if node==null{return;}if node.mTag==0{System.out.printnode.mData.toString+”\t;printnode.mPh;print node.mPt;义表的》策度public intdepth{//5if mGenTable==null{nthrow newNullPointerException GeneralizedTable isnull!..11method depth;return depthmGenTable;private intdepthNode node{if node==null||node.mTag==TAG_ITEM{return0;}㊀㊀int depHeader=0,d pTar=0;depHeader=1+depthnode.mPh;depTear=depthnode.mPt;return depHeaderdepTeardepHeader:depTear;}//广义表的长度public intlength{if mGenTable==null||mGenTable.mPt==null{return-1;int tLen=0;Node node=mGenTable;while node.mPt!=null{node=node.mPt;㊀if node.mPh==nullnode.mPt==null{br ak;tLen++;}return tLen;public GeneralizedTablegetHeader{if isEmptyreturnnull;Node node=mGenTable.mPt;GeneralizedTable gt=new GeneralizedTable;gt.mGenTable.mPt=node.mPh;return gt;public GeneralizedTablegetTear{if isEmptyreturn null;=㊀Node nodmGenTable.mPt;GeneralizedTable gt=new GeneralizedTable;gt.mGenTable.mPt=node.mPt;return gt;public booleanisEmpty{if mGenTable==null{return true;=㊀Node nodmGenTable.mPt;return node==null||node.mPh==null;{//广义表节点public classNode//广义表的表节点Node mPh;//广义表表尾节点㊀Nod mPt;院子节点;,表节点int mTag;//mTag==0,mTag==1//广义表的数据值Object mData;public NodeNodeph,Node pt,int tag,Object data{mPh=ph;mPt=pt;mTag=tag;mData=data;*@param argspublic staticvoid mainString[]args{;,//String tStr=a,b,c,a,d,d,g,c,k,g,c”,;String p=a,b,a,b,c,a,a,b,c”,;String p2=2”;//String space=”;String big={{a,b},{{a,g},{h},{a,n,f,{a,b,c}}},c}”String middle=[[p],[g]]],[h],
[2]];GeneralizedTable gTab=new GeneralizedTablemiddle;㊀㊀Gen ralizdTable header,tear;gTab.print;System.out.printin;System.out.printInlength:+gTab.length;■㊀㊀Syst m.out.printin cipth:”+gTab.depth;header=gTab.getHeader;if header!=null{nSystem.out.printinheader:;header.print;tear=gTab.getTear;if tear!=null{nSystem.out.printintear:;tear.print;第六章树上机实训
1.编写一个程序,计算一颗二叉树的深度参考答案package c06;class TreeNode{int val=0;TreeNode left=null;TreeNode right=null;public TreeNodeintval{this,val=val;public classMainOl{public intgetMaxDepthTreeNode root{if root==null{return0;}else{int left=getMaxDepthroot,left;int right=getMaxDepthroot,right;return1+Math,maxleft,right;
2.编写一个程序,输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树假设输入的前序遍历和中序遍历结果中都不含重复的数字参考答案package c06;public classMain02{public staticvoid mainString[]args{int[]preOrder={l,2,4,7,3,5,6,8};int□in0rder={4,7,2,1,5,3,8,6;BinaryTreeNode node=reConstruct preOrder,inOrder;,printTreenode;.}public staticclass BinaryTreeNodeint value;,BinaryTreeNode left;BinaryTreeNode right;.}public staticBinaryTreeNode reConstructint[]preOrder,int[]inOrder{ifpreOrder==null||inOrder==null||preOrder,length!=inOrder.length||preOrder.Ie ngthl.return null;returnconstructpreOrder,0,preOrder,length-1,inOrder,0,inOrder,length-1;.}public staticBinaryTreeNode constructint[]preOrder,int ps,int pe,int[]inOrder,intis,int ie{if pspereturn null;int value=preOrder[ps];int index=is;whileindex=ieinOrder[index]!=value{index++;.System,out.printin当前各参数的数值为-ps:+ps+pe:+pe+is+is+”ie“+ie+”index+index+“rootValue+value;if indexie{throw newRuntimeExceptioninvalid input+index;.BinaryTreeNode node=new BinaryTreeNode;node.value=value;node.left=constructpreOrder,ps+1,ps+index-is,inOrder,is,index-1;第二章线性表上机实训编写一个顺序表类的成员函数,实现对顺序表循环右移位的操作即原来顺序表为
1.k ai,循环向右移动位后变成a,•••,a-k,a-k+i,•••,k a-k+i,•••,a,a a,•••,a-ko2n n nnb2n要求时间复杂度为0no参考答案package sjsx.cO2;import java.util.Arrays;public classSequenceListT{//默认长度private intDEFAULT_SIZE=2;//定义一个数组用于保存原性表的长度private Object[]elementData;//用于保存数组长度private intcapacity;//保存顺序表中当前元素的个数private intsize=0;★/*构造一个默认长度的空线性表*/*㊀㊀㊀public Squ ncList{capacity=DEFAULT_SIZE;elementData=new Object[capacity];/**大用一个初始化元素来创建线性表初始化元素*@param element/*public SequenceListT element{this;㊀㊀㊀1m ntData
[0]=element;++;㊀siz★/*大用一个元素和指定长度来创建线性表元素*@param element指定长度*@param initSizenode.right=constructpreOrder,ps+index-is+1,pe,inOrder,index+1,ie;return node;}public staticvoid printTreeBinaryTreeNodenode{if node!=null{printTreenode,left;System,out.printnode.value+;printTreenode,right;第七章图的基本知识上机实训
1.设无向图G有n个顶点,m条边试编写用邻接表存储该图的算法参考答案public classArcNode{//边结点的类型定义int adjVex;//存放与邻接的点的序号ArcNode nextArc;//指向Vi下一个邻接点的边结点int weightpublicArcNode{adjVex=0;weight=0;nextArc=null;public classVNodeT{//顶点结点类型定义T data;//存储顶点的名称或其相关信息ArcNode firstArc;〃指向顶点Vi的第一个邻接点的边结点public VNode{data=null;firstArc=null;public classALGraphT{protected finalint MAXSIZE=10;©SuppressWarningsrawtypesprotected VNode[]adjList;〃顶点结点信息int n,e;〃图的顶点数和弧数public ALGraph{adjList=new VNode[MAXSIZE];}©SuppressWarnings{“resource,unchecked public void CreateLinkO{//创建无向图的邻接表inti,j,k;T vl,v2;ArcNode s;String str;Scanner sc=new ScannerSystem,in;System.out.printin请输入图的顶点数及边数“;System.out.print顶点数n=;n=sc.nextlnt;;System.out.print数e=/z;e=sc.nextlnt;System,out.printin请输入图的顶点信息“;str=sc.next;fori=0;i〈n;i++{adjList[i]=new VNodeT;adjList[i].data=str.charAt i,,〃构造顶点信息adjList[i].firstArc=null;System.〃左printin请输入图的边的信息”;for k=0;ke;k++System.〃力print请输入第+k+l+”条边的两个端点;str=sc.next;〃输入一条边的两个顶点vl=TObjectstr.charAt0;v2=TObjectstr.charAt1;//确定两个顶点在图G中的位置i=LocateVexvl;j=LocateVexv2;//算法6-4ifi=0j=0{s=new ArcNode;s.adjVex=j;s.nextArc=adjList[i].firstArc;adjList[i].firstArc=s;s=new ArcNode;s.adjVex=i;s.nextArc二adjList[j].firstArc;adjList[j].firstArc二s;//在图中查找顶点v,找到后返回其在顶点数组中的索引号,若不存在,返回-1public intLocateVexTv{inti;fori=0;in;i++ifadjList[i].data==vreturn i;return-1;}public voidDisplayAdjList{〃在屏幕上显示图的邻接表表示inti;ArcNode p;System,out.printin图的邻接表表示“;fori=0;in;i++{System.out.print\n+adjList[i].data;p=adjList[i].firstArc;whilep!=null{System.out,print C一一+P.adjVex;p=p.nextArc;System.out.printin;public classMainOl{public staticvoid mainString[]args{ALGraphCharacter G=new ALGraphCharacter;G.CreateLink;G.DisplayAdjList;
2.设计算法,求出无向连通图中距离顶点V的最短路径长度最短路径长度以边数为单位计算为K的所有的结点,要求尽可能地节省时间算法思想:利用广度优先遍历对图进行遍历,从vO开始,依次访问与vO相邻接的各个顶点,利用一个队列存储所有已经访问过的顶点和该顶点与vO的最短路径,并将该顶点的标志位置为1表示已经访问过依次取出队列的各个顶点,如果该顶点存在未访问过的邻接点,首先判断该顶点是否距离vO的最短路径为K,如果满足条件将该邻接点输出,否则将该邻接点入队,并将距离vO的层次加1重复执行上述操作,直到队列为空或者存在满足条件的顶点为止参考答案存储结构使用1题中的邻接链表结构,此外将直接引用,不再重复描述import java.util.AiTays;import java.util.Scanner;public classMain02f{private staticint MAX-100;public staticvoid BSLevelALGraphG,int vO,int k{int[]visited=new\nt\MAX\\Arrays-visited,;intf][]queue二new int[MAX]
[2];int front=0,rear=-1,v,level=l,yes=O;ArcNode p;rear++;queue|rear][O]=vO;qucuc[rcar][l]=l;visited[vO]=l;System.owfprintlnlevel;do{v二queue[front]
[0];level=queue[front][l];front++;p=G.adjList[v].firstArc;while p!=null{if visited[p.adj Vex]==0{iflevel==k{ifyes==O{yes=1;System.0〃£.print“距离+G.adjList[vO]data+”最短的路径为”+k+的顶点有”+G.adjList[p.adjVex].data;}else{System.owtprintn,n+G.adjList|p.adj Vex].data;visited[p.adj Vex]=l;rear++;queue[rear][O]=p.adjVex;queue[rear]
[1]=level+1;p=p.nextArc;{while front=G.nlevelk+l;public staticvoid mainString[]args{Scanner sc=new ScannerSystem.Zw;ALGraphCharacter G=new ALGraphCharacter;G.CreateLink;55^©
111.0〃牛打山”请输入距离长”;int k=sc.nextlntQ;B5LeveZG,0,k;第八章查找上机实训
1.编程实现哈希表的基本功能,要求解决冲突的方法为线性探测法参考答案public class HashBuck2K V{fstatic classNodeK,V{public Kkey;public V val;public NodeK,V next;㊀public NodeKkey,V val{this.key=k y;this.val=val;public NodeK,V[]array;public intusedSize;public HashBuck2{㊀this.array=Nod K,V[]new Node
[8];public voidputK key,Vval{int hash=key.hashCode;int index=hash%㊀array,1ngth;NodeK,V cur=array[index];while cur!=null{if cur.key.equalskey{cur.val=val;return;cur=cur.next;㊀・㊀NodeK,V node=new Nodekey,val;nod nxt=array[index];array[index]=node;this.usedSize++;if loadFactor
0.75{resize;public VgetK key{int hash=key.hashCode;int index=hash%array.length;㊀Nod K,V cur=array[index];while cur!=null{ifcur.key.equalskey{return cur.val;cur=cur.naxt;}return null;public voidresize{Node[]newArray=new Node[this.array.length*2];for inti=0;i this.array.length;i++{NodeK Vcur=array[i];while cur!=nullf{㊀int hash=cur.key.hashCode;int index=hash%array,1ngth;Node K,VcurNext=cur.next;cur.next=newArray[index];newArray[index]=cur;cur=curNext;this.array=newArray;public doubleloadFactor{/㊀㊀return this,us dSizthis.array.length*
1.0;class Student{public intid;㊀Stud ntintid{this.id=id;㊀㊀@Ov rrid㊀㊀public booleanqualsObj cto{if this==o returntrue;if o==null||getClass!=o•getClassreturn false;㊀・㊀㊀Student student=Student o;return id==stud ntid;@0v rridpublic int hashCode{return Objects.hashid;classHashBuck2Test{publicstatic void mainString[]args{HashBuck2Student,Integer hashBuck2=naw HashBuck2;Student si=new Student10001;Student s2=new Student10001;Student s3=new Student10003;hashBuck
2.putsi,89;hashBuck
2.putsi,60;hashBuck
2.puts2,94;hashBuck
2.puts3,100;System.out.printInhashBuck
2.getsi;System.out.printInhashBuck
2.gets2;写出二分查找的递归算法参考答案
2.public classBinarySearch{/**二分查找算法*夫有序数组@param srcArray查找元素*@param key的数组下标,没找到返回-*©return key1*/public staticvoid mainString[]args{int srcArray[]={3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};System.out.printinbinSearchsrcArray,81;System.out.printinbinSearchRecursionsrcArray,0,srcArray.length-1r//二分查找递归实现81;public staticint binSearchRecursionint srcArray[],int mid=end-start/2+start;if srcArray[mid]==key{return mid;if start=end{return-1;}else if keysrcArray[mid]{int start,int end,int key{return binSearchRecursionsrcArray,mid+1,end,key;}else if keysrcArray[mid]return{binSearchRecursionsrcArray,start,mid-1,key;return-1;//二分查找普通循环实现key{public staticint binSearchint srcArray[],int intmid=srcArray.length/2;ifkey==srcArray[mid]{return mid;int start=0;int end=srcArray.length-1;while start=end{mid=end-start/2+start;ifkeysrcArray[mid]{end=mid-1;}else ifkeysrcArray[mid]{start=mid+1;}else{return mid;return-1;第九章排序上机实训
1.冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法参考答案package c09;public classMainOl{public staticvoid Sort(int[]list)boolean change=true;int low=0;int high=list,length-1;int nFlag=0;while lowhighchange change=false;for inti=low;ihigh;i++if list[i]listEi+1]int temp=list[i];list Ei]=list[i+1];listEi+1]=temp;change=true;}high一;for inti=high;ilow;i一if list[i]list Ei-1]int temp=list[i];list Ei].=list[i-1];list Ei-1]=temp;change=true;low++;public SequenceListTelement,int initSize{capacity=1;if capacityinitSize{capacity=initSize+2;elementData=new Object[capacity];㊀elementData
[0]=lament;size++;*向顺序表中插入元素待插入的元素㊀㊀㊀*©param1m nt夫待插入的位置@param index*/public voidinsert Telement,int index{ifindex0||indexsize{工”数组越界异常;㊀㊀throw newnd xOutOfBoundsExcptionensureCapacitysize+1;//把以后的元素都后移一位㊀ind xSystem.arraycopyelementData,index,elementData,index+1,size-index;elementData[index]=element;size++;/**表长**@return*/public intlength{return size;★//向表中添加元素**@param element*/㊀㊀public voidaddT1ment{insert element,size;★/*得到线性表存储的对象*获得的位置*@param index得到的结果*@returnpublic staticvoid mainStringargsEJ{int E]iArray=new int[]{38,5,19,26,49,97,1,66;SortiArray;for inti=0;iiArray,length;i++{System,out.printf%d,iArray[i];}
2.设有一个数组中存放了一个无序的关键序列KI、K
2、…、Kn现要求将Kn放在将元素排o序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n参考答案package c09;public classMain02public staticvoid adjustint[]list,{int low=0;int high=list,length-1;.inti=low;intj=high;int tmp=list[high];while highlow・{while highlowlist[low]=tmplow++;list[high]=list[low];list[low]=tmp;high一;while highlowlist[high]=tmphigh一;if highlowlist[low]=list[high];list[high]=tmp;,low++;.}public staticvoidmainStringargs[]{int[]iArray=new intE]{60,55,48,37,10,90,84,58;adjust iArray;for inti=0;iiArray,length;i++{,System,out.printf”,iArray[i]㊀public Tg tint index{if index0||indexsize工数组越界异常”;㊀㊀throw newnd xOutOfBoundsExcption returnTelementData[index];/*★*判断线性表是否为空*@return*/public booleanisEmpty{return size==0;/**大清空线性表*/public voidclear{㊀㊀㊀Arrays.fill1m ntData,null;size=0;size,/*大*获取指定位置的前一个元素夫线性表位置,若是取线性表最后一个元素,必须@param indexindex=*为线性表元素个数㊀siz*Qreturn*/public TpriorElemint index{ifindexOindexsize+lreturn TelementData[index-1];else{工”数组越界异常”;㊀throw newnd xOutOfBoundsException/**文删除指定位置的元素*©param index*/public voiddeleteint index{ifindex0||indexsize-l{index,工”数组越界异常”;throw new ndexOutOfBoundsException}else{//把数组前移一位System.arraycopyelementData,index+1,elementData,size-index-1;size--;//清空最后一个元素elementData[size]=null;★/**获取指定线性表位置的后一个元素大线性表位置,若是取线性表第个元素,必须@param index0index=-l*@return*/㊀㊀public Tn xtElmint index{if index==-l{return TelementData
[0];else ifindexsize-lindex-l{return TelementData[index+1];}{工数组越界异常;㊀㊀Is throw newndexOutOfBoundsException/***确保数组所需长度大于数组原有长度*数组所需长度©param incapacity*/㊀㊀private voidnsur CapacityintmCapacity{ifmCapacitycapacity{capacity=mCapacity+2;}elementData=Arrays.copyOfelementData,capacity;/**大实现对顺序表元素的输出*/public voiddisplay{for inti=0;ithis.length;i++{System.out.printthis.geti+”n;}System.out.printin;*实现对顺序表循环右移位的操作k*循环右移的位数@param k*/㊀public voidshitint k{int n=this.length,p=0,i,j,1;Obj cttemp;fori=l;i=k;i4-+//求和的最大公约数;if n%i==0k%i==0n kp p=ifor i=0;ip;i+4-{1e1=i+n-k%n;temp=this.elementData[i];while l!=i{;this,elementData[j]=this.elementData
[1];j=l1=j+n-k%n;//循环右移一^步this.elementData[j]=temp;//测试public classMainOl{publicstaticvoidmainString[]args throwsException{SqList L=newSqList10;for inti=0;i=8;i++L,inserti,i;右移前顺序表中的各个数据元素为”;System.out.println L,display;L.shit3;”右移位后顺序表中的各个数据元素为”;System.out.printIn3L,display;编写两个单链表类的成员函数,分别实现链表反转、查找单链表的中间节点两个功能
2.参考答案public classLinkListT{//定义一个内部类,代表链表的节点㊀Nodprivate classNode{保存数据private Tdata;//指向下个节点的引用private Node next;////无参构造器public Node{//初始化全部属性的构造器public NodeTdata,Nodenext{this.data=data;this.next=next;保存头结点private Nodeheader;//保存尾节点保存已含有的节点数private Nodetail;//private intsize;////创建空链表public LinkList{header=null;tail=null;//已指定数据元素创建链表,只有一个元素public LinkListTelement{header=new Nodeelementnull;f//只有一个节点,都指向该节点㊀㊀㊀h ader,tail tail=h adr;++;㊀siz//返回链表的长度㊀public int1ngth{return size;//获取指定索引处的元素㊀public Tg tintindex{return this.getNodeByIndexindex.data;//获取指定位置的节点工㊀㊀㊀㊀private Nodg tNodBy ndxint index{ifindex0||indexsize-1{索弓|超出线性表范围”;throw newIndexOutOfBoundsException从开始遍历㊀㊀㊀㊀Node current=h adr;//h adrfor inti=0;isizecurrent!=null;i+current=current.next{ifi==index{return current;}return null;//按值查找所在位置publicintlocate Telement{Node current=header;for inti=0;isizecurrent!=null;i++,current=current.next{ifcurrent.data.equalselement{return i;return-1;//指定位置插入元素㊀publicvoidinsert Telement,intindex{ifindex0||ind xsize{工索弓[超出线性表范围”;㊀㊀thrownewnd xOutOfBoundsExcption//如果是空链表ifheader==null{addelement;else{//当为时,即在链表头处插入㊀ind x0if0==index{addAtHeadelement;else{获取前一个节点//让Node prev=getNodeBylndex index-1;//prev的指向新节点,新节点的指向原来的下一next nextprev个节点++;㊀prev.next=new Nodeelement,prev.next;siz。