77实用数据结构辅导知识点

实用数据结构1最低要求难点代码改错课后复习题上机题1数组，Arrays类学习目标：1.掌握关于数组概念2.掌握Arrays类以及常用方法1.回忆数组概念、定义及使用；2.掌握Arrays类常用方法3.继承关系：Arrays类是Object类直接子类。如下图所示：Arrays类常用方法:sort()对指定的类型数组按数字升序进行排序。binarySearch()使用二分搜索法来搜索指定的类型数组，以获得指定的值。equals()用于比较两个数组是否相等。fill()用以某个值填充整个数组。asList()接受任意的数组为参数，将其转变为List容器。Java的二分查找算法:privatestaticintbinarySearch0(Object[]a,intfromIndex,inttoIndex,Objectkey){intlow=fromIndex;inthigh=toIndex-1;while(low=high){intmid=(low+high)/2;ComparablemidVal=(Comparable)a[mid];intcmp=midVal.compareTo(key);if(cmp0)low=mid+1;elseif(cmp0)high=mid-1;elsereturnmid;//keyfound}return-(low+1);//keynotfound.}算法思想描述：查找的数组必须是按关键字值排好序；减半查找范围，确定待查元素是否存在于数组中。1、获取中间元素的位置，拿带查元素与中间位置元素比较；2、比中间元素大，在后半部分找；3、比中间元素小，在前半部分找。注意问题：sort()的使用binarySearch()的使用数组与Arrays类的区别练习：请参见读程序写结果中——程序1、程序2、程序3常璐璐，赵玉霞编实用数据结构2最低要求难点代码改错课后复习题上机题2List、ArrayList学习目标：1.掌握ArrayList的具体使用2.掌握List接口的实现ArrayList是一种线性表，在内存中是连续存储的，适合于元素的随机存取。添加和删除操作是需要依据添加的位置来定，如果在ArrayList最后元素后面添加和删除元素，在性能方面还算好，但是如果是在ArrayList中间添加和删除元素的话，代价就会很大。1.ArrayList结构特点：数组大小固定，ArrayList可以自动增加空间ArrayList常用方法：size()返回此列表中的元素数。get()返回此列表中指定位置上的元素。set()用指定的元素替代此列表中指定位置上的元素。add()将指定的元素添加到此列表的尾部；将指定的元素插入此列表中的指定位置。contains()如果此列表中包含指定的元素，则返回true。remove()移除此列表中指定位置上的元素。Object[]toArray()按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。3.遍历方法①for循环语句：for(inti=0;i…;i++)②迭代器：Iteratorit=list.iterator();while(it.hasNext()){Ee=it.next();…}③forEach结构：for(Ee:list){…}4.了解ArrayList与Vector的区别5．List接口的实现6.继承关系如下图：1.List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。2.List接口与其常用实现类的继承实现关系：实用数据结构3最低要求难点代码改错课后复习题上机题3.对比List接口的两个常用实现类简述实现操作特性成员要求List提供基于索引的对成员的随机访问ArrayList提供快速的基于索引的成员访问，对尾部成员的增加和删除支持较好成员可为任意Object子类的对象LinkedList对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员访问支持性能较差成员可为任意Object子类的对象1、上机实现下面程序publicstaticvoidmain(String[]args){Listlist=newArrayList();for(inti=0;i5;i++){list.add(编程词典+i);}ListIteratorli=list.listIterator();while(li.hasNext()){System.out.println(li.next());}}1、练习：请参见读程序写结果中——程序4、程序52、创建一个类Cat：包含属性name，在构造方法中进行初始化；添加一个方法show()，用以打印name属性的值创建一个类CatTest：添加main方法，实现创建一个ArrayList，向其中添加几个Cat对象遍历该集合，并且对每个Cat对象调用show()方法参考代码：classCat{privateStringname;publicCat(Stringname){this.name=name;}publicvoidshow(){System.out.println(name);}}publicclassCatTest{publicstaticvoidmain(String[]args){//创建一个ArrayList，向其中添加几个Cat对象；ArrayListlist=newArrayList();list.add(newCat(mimi));list.add(newCat(qiqi));list.add(newCat(ding));//遍历该集合，并且对每个Cat对象调用show()方法。for(inti=0;ilist.size();i++){Catc=(Cat)list.get(i);c.show();}}}实用数据结构4最低要求难点代码改错课后复习题上机题3LinkedList学习目标：1.掌握LinkedList类的使用方法2.掌握栈和队列的概念1.结点、链表的概念以及链式存储的思想2.LinkedList类的常用方法（对比ArrayList）的掌握3.与ArrayList类比较，各自特点，如何应用、选择LinkedList的常用方法：add()向链表末尾添加一个新的节点remove()删除指定位置上的节点；删除首次出现含有数据elemen的节点。get()得到链表中指定位置处节点中的对象。set()将当前链表index位置结点中的对象替换为参数element指定的对象，并返回被替换的对象。4.用LinkList类实现栈和队列栈中常用方法：pop()从此列表所表示的堆栈处弹出一个元素。push()将元素推入此列表所表示的堆栈。新增以下新方法：构造方法LinkedList()getFirst()和getLast()removeFirst()和removeLast()addFirst()和addLast()5、类继承关系如图：List接口实现：1.LinkedList是采用双向循环链表实现的。2.利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-endedqueue)采用链表的方法来实现栈：用方法addFirst(Objectelement)实现进栈操作。用方法removeFirst()实现出栈。用方法getFirst()实现栈顶数据查询。用方法isEmpty()实现栈是否为空。练习：请参见读程序写结果中——程序6、程序7、程序7上机操作：创建一个类Stack，代表堆栈（其特点为：后进先出），添加方法add(Objectobj)、以及delete()，添加main方法进行验证，要求：使用LinkedList实现堆栈在向LinkedList中添加时，使用addLast()方法在从LinkedList中取出时，使用removeLast()方法实用数据结构5最低要求难点代码改错课后复习题上机题4Collections与Collection学习目标：1.会使用Collections类2.掌握Collection接口1.了解Collection接口2.掌握Collection接口常用方法3.掌握Collections类中常用方法Collection接口中常用方法:toArray()返回包含此collection中所有元素的数组。add()确保此collection包含指定的元素。equals()比较此collection与指定对象是否相等。hashCode()返回此collection的哈希码值。size()返回此collection中的元素数。iterator()返回调用类集的迭代程序remove()从调用类集中删除obj的一个实例。如果这个元素被删除了，则返回true；否则返回false4．Comparable与Comparator的区别联系5、Collections类的继承关系：Collections类中常用方法:binarySearch()使用二分搜索法搜索指定列表，以获得指定对象。sort()根据元素的自然顺序对指定列表按升序进行排序。synchronizedMap()返回由指定映射支持的同步（线程安全的）映射。synchronizedSet()返回指定set支持的同步（线程安全的）set。sort()、reverse()、max()、min()、fill()等方法6、Collection接口的继承关系：1.Collections中的大多数方法都与List或collection有关。1．Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。JavaSDK不提供直接继承自Collection的类，JavaSDK提供的类都是继承自Collection的“子接口”如List和Set。2．Collections类完全由在collection上进行操作或返回collection的静态方法组成。它包含在collection上操作的多态算法，即“包装器”，包装器返回由指定collection支持的新collection，以及少数其他内容。2、Collection的遍历：Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代器，使用该迭代器即可逐一访问Collection中每一个元素。借助Iterator接口实现。实用数据结构6最低要求难点代码改错课后复习题上机题Iterator接口结构：模板代码：Iteratorit=collection.iterator();//获得一个迭代器while(it.hasNext()){Objectobj=it.next();//得到下一个元素}利用Collection接口的iterator()获得一个实现了Iterator接口的迭代器，然后利用其完成Collection接口对象的遍历操作。模板代码如右所示：对象排序方法：1、Comparable接口所有可以”排序“的类都实现了java.lang.Comparable接口Comparable接口中只有一个方法：publicintcompareTo(Objectobj);2、Comparator接口Comparator通常在对于自然排序不能满足需要时使用。Comparator接口定义了两个方法：compare()和equals()。publicinterfaceComparatorT{intcompare(To1,To2);booleanequals(Objectobj);}练习：请参见读程序写结果中——程序9（Collections）练习：请参见读程序写结果中——程序10（Collections、Iterator接口）练习：请参见读程序写结果中——程序11（Comparator接口）实用数据结构7最低要求难点代码改错课后复习题