数据结构（严蔚敏）chapter 2 arrays

DataStructuresandAlgorithmswithJavaChapter2Arrays©DepartmentofBiophysics本章学习重点常见的数据存储结构：数组数组的基本操作及其Java实现一种特殊的数组：有序数组（按关键字排序）有序数组的二分查找算法算法效率的评价：大O表示法TheArrayWorkshopAppletSupposethatyou’recoachingakids-leaguebaseballteam:Solution:

需要一个简单的数据结构对出勤记录进行存储，同时可能需要执行额外的操作。problem:

keeptrackofwhichplayersarepresentatthepracticefield.

Youcanuseasimpledatastructuretoholdthisdata.Thereareseveralactionsyouwouldliketobeabletoperform:Insertion:

Insert

aplayer

into

the

datastructure

whentheplayerarrivesatthefield.Searching:

Checktoseeifaparticularplayerispresentby

searching

for

hisorhernumberinthestructure.Deletion:

Delete

aplayer

fromthedatastructure

whentheplayergoeshome.appletThesethreeoperationswillbethefundamentalonesinmostofthedatastoragestructures.需要指出的是：演示过程中，每点击一下鼠标代表后台一步操作。Insertion:

每次插入操作执行步骤一次即可完成

原因：新的数据项总是插在数组中的第一个位置或最后一个空位上

内因：数组中已有数据项数目已知，即算法知道空位的位置。appletSearching：如果在数组中未出现输入关键字，检测所有数据条目后显示未找到数据项；查找数组头部的元素快，查找尾部的元素慢设数据项个数为n，则一个数据项的平均查找长度为n/2,最坏情况下需要n步完成Deletion：只有找到一个数据后，才能删除。一般情况下，删除操作后，应该保持原有数据结构，即数组中不允许出现空单元。删错操作完，必须将后面的数据项前移。从演示过程中，我们可以看出，删除操作需要平均查找数据项的平均时间为n/2,前移操作填充空单元的平均时间为n/2，总共需要N步。appletTheDuplicatesIssue：设计数据结构时，需要决定数据项的关键字是否可以重复，如对于棒球队员来讲，重复的号码是不行的，如果有人穿着相同号码的球衣的话，跟踪并了解球员在场情况就会变得很困难。再如人事档案中工号。针对applet，算法运行效率的比较允许重复的查找、插入和删除VS.

不允许重复记录的操作applet①TheBasicsofArrays

injava②DividingaProgramintoclasses

③ClassInterfaces④

JavaCodeforanOrdered

Array⑤Logarithms⑥StoringObjects⑦BigONotation⑧WhyNotUseArraysforEverything?OverviewofthisChapter①TheBasicsofArraysinjavaCREATINGANARRAYInmanyprogramminglanguages(evenobject-orientedoneslikeC++)arraysareaprimitivetype,butinJavathey’retreatedasobjects.Accordinglyyoumustusethenewoperatortocreateanarray:单一语句申明方法说明：[]告诉编译器当前申明的是一个数组对象。intArray是一个指向数组的引用，并非数组本身，数组对象的具体值存放在其他地址中，而intArray仅仅保存数组的地址。【ArrayinJava】

数组有一个字段length

存储数组中数据项的个数（大小、长度）数组大小固定一旦数组被创建，数组大小便不可改变。ACCESSINGARRAYELEMENTSArrayelementsareaccessedusingsquarebrackets.Thisissimilartohowotherlanguageswork:说明：第一个元素下标为0。一个有10个元素的数组下标是从0至9。如果访问下标<0或>length的数据项，报错。INITIALIZATION说明：用｛｝直接初始化数组，取代了引用声明和使用new来创建数组；数组大小有列表中元素个数决定Anarrayexample：Listing2.1array.javap23-24//--------------------------------------------------------------arr[0]=77;//insert10itemsarr[1]=99;arr[2]=44;arr[3]=55;arr[4]=22;arr[5]=88;arr[6]=11;arr[7]=00;arr[8]=66;arr[9]=33;nElems=10;//now10itemsinarrayInsertion操作实现：面向过程编程能否实现？//--------------------------------------------------------------searchKey=66;//finditemwithkey66for(j=0;j<nElems;j++)//foreachelement,if(arr[j]==searchKey)//founditem?break;//yes,exitbeforeendif(j==nElems)//attheend?System.out.println("Can'tfind"+searchKey);//yeselseSystem.out.println("Found"+searchKey);//noSearching操作：//--------------------------------------------------------------searchKey=55;//deleteitemwithkey55for(j=0;j<nElems;j++)//lookforitif(arr[j]==searchKey)break;for(intk=j;k<nElems;k++)//movehigheronesdownarr[k]=arr[k+1];nElems--;//decrementsizeDeletion操作：体会：

上面一个数组的实例，只需要一个类方法main()。所有操作没有很好地封装，看不到对象之间的交互，读起来，感觉累！！！实现面向对象的代码优化：①将数据存储结构（数组）从程序中分离出来②为程序创建一个操作数据结构的用户③改进用户与存储结构之间的通信②DividingaProgramintoclasses

array.java程序包含了一个大的方法。数据的存储结构本身可以成类程序中使用这个结构的部分也可成类通过将程序划分成不同的类，可以有很多好处：

i)clarifythefunctionalityoftheprogram

ii)makingprogramseasiertodesignandunderstand

iii)makingprogramseasiertomodifyandmaintain分两类p25

将数组封装到类lowArray中，同时在这个类中封装一些其他类(lowArrayApp)可以访问这个数组的方法，方法提供lowArray与lowArrayApp之间的交互。lowArrayApp用户创建了一个lowArray类的对象并用它存储和操作数据。

lowArray---工具(容器类containerclass)

存储数据结构、提供访问数据结构的方法和其他诸如排序等复杂的操作

lowArrayApp----工具的使用者③Class

Interfaces面向对象编程需要考虑的主要方面：划分类—明确程序的结构类之间如何分配任务—确定类内部操作类之间如何进行交互—确定类间关联通常，如果一个类被多个用户使用，那么对这个类的设计就要求易用性好。类的用户通过类接口的方式与类相连。由于类的字段通常是私有(封装性要求)，那么接口通常指类的方法，即类的方法执行什么操作，参数如何？通过调用方法，类用户与类对象进行交互。Thewaythataclassuserrelatestotheclassiscalledthe

classinterface.数据内部封装方法

接口lowArray.java只演示了将程序划分为类，我们利用highArray.java重新分配类之间的责任/任务，从而获悉更多OOP的优点。highArray.java取消使用setElem()和getElem()方法访问数组下标,换用insert(),find()和delete().类自身处理下标问题，这些方法不需要使用下标作参数。highArray.java可以集中精力处理问题，而不是怎样做，即什么元素要被插入、删除和查找，而不是如何（利用下标或其他数据结构参数等）执行这些操作。p28：

highArray.java比lowArray.java的main()方法短小简单，lowArray中main方法处理的细节现在被highArray类中的方法解决实现了。数据结构类中封装了对数组的操作，用户类使用方便快捷，甚至不需要知道用什么数据结构存储了数据对象。即结构被隐藏在接口背后。ABSTRACTION“抽象”：从what(什么)中将how(如何)分离出来的过程，即类中的操作如何进行，相对什么是类用户可见的，称之为抽象。抽象是软件工程中的重要方面。抽象，使程序设计更简单，相当于问题转化的过程。④JavaCodeforanOrderedArrayDefinition：

Imagineanarrayinwhichthedataitemsarearrangedinorderofascendingkeyvalues;thatis,withthesmallestvalueatindex0,andeachcellholdingavaluelargerthanthecellbelow.Suchanarrayiscalledanorderedarray.Linearvs.BinarySearch

Linearsearchesoperate

inmuchthesamewayasthesearchesintheunorderedarray.Binarysearches

operateeffectivelyintheorderedarray.

e.g.theguess-a-numbergame使用OrdArray类来封装数组和它的算法。类的核心是find()方法，通过它可以用二分查找来定位一个特定的数据项。applet二分查找的基本思想是：（设R[low..high]是当前的查找区间）

（1）首先确定该区间的中点位置：

（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：

①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。

②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。

从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。intBinSearch(SeqListR，KeyTypeK)

{//在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零

intlow=1，high=n，mid；//置当前查找区间上、下界的初值

while(low<=high){//当前查找区间R[low..high]非空

mid=(low+high)/2；

if(R[mid].key==K)returnmid；//查找成功返回

if(R[mid].kdy>K)

high=mid-1;//继续在R[low..mid-1]中查找

else

low=mid+1；//继续在R[mid+1..high]中查找

}

return0；//当low>high时表示查找区间为空，查找失败

}//BinSeareh二分查找算法THEOrdArrayCLASSIngeneral,theorderedArray.javaprogramissimilartohighArray.java.Themaindifferenceisthatfind()usesabinarysearch：

find() insert() delete() size()

p38FeaturesofOrdArraymajoradvantage

searchtimesaremuchfasterthaninanunorderedarray.disadvantage

insertiontakeslonger（allthedataitemswithahigherkeyvaluemustbemoveduptomakeroom）∴Orderedarraysarethereforeusefulinsituationsinwhichsearchesarefrequent,butinsertionsanddeletionsarenot.⑤Logarithms二分查找比较次数r=2s设s表示步数，r表示搜索范围，r与s的关系归纳如下：s=log2(r)⑥StoringObjects在Java中，数据结构只存储long类型的简单变量，而其他数据类型(int,string等)视为object。而在现实社会中，存储的数据记录是许多字段的组合

e.g:

apersonnelrecord-lastname,firstname,age,SocialSecuritynumber,andsoforthastampcollection-thenameofthecountrythatissuedthestamp,itscatalognumber,condition,currentvalue,andsoon.Person类示例给出对象是如何存储的THEPersonCLASSAconstructorenablesanewPersonobjecttobecreatedanditsfieldsinitialized.ThedisplayPerson()methoddisplaysaPersonobject’sdata,andthegetLast()methodreturnsthePerson’slastname;thisisthekeyfieldusedforsearches.THEclassDataArray.javaPROGRAMPerson类的程序是在highArray.java基础上作简单修改：数组类型改为Person.关键字(姓氏)现在是一个String对象，作比较时用equals()方法，而非==操作符。

if(a[j].getLast().equals(searchName))//founditem?insert()方法创建一个新的Person对象，插入到数组中，而非long类型。p40

程序显示了数据存储结构可以通过与简单类型同样的方法来处理对象。⑦BigONotationAutomobilesaredividedbysizeintoseveralcategories:Similarly,it’susefultohaveashorthandwaytosayhowefficientacomputeralgorithmis.Incomputerscience,thisroughmeasureiscalledBigOnotation.subcompactscompactsmidsize目前所见到的算法的大O表示法：

即算法的速度与数据项个数之间的关系无序数组的插入：常数新数据总是放在下一个有空的地方，执行一步操作Wecansaythatthetime,T,toinsertanitemintoanunsortedarrayisaconstantK:e.g.hash表的查找线性查找：与N成正比

在数组数据项的线性查找中，寻找特定数据项所需的比较次数平均为数据项总数的一半，设数据项总数为N，搜索时间T与N的一半成正比。二分查找：与log(N)成正比Similarly,wecanconcoctaformularelatingTandNforabinarysearch:BigOnotation与上面的公式表示法类似，但省去了常数k∵比较算法时，并不在乎具体的微处理器芯片或编译器，需要比较的是对应不同的N值，T如何变化，而不是具体的数字。∴不需要常数k。BigOnotation

使用大写字母O，含义为“大约是”.InBigOnotation,wewouldsaythat：

alinearsearchtakesO(N)time；abinarysearchtakesO(logN)time；

InsertionintoanunorderedarraytakesO(1),orconstanttime.(常数级时间)excellentgoodfairO(N2)poorc<log2n<n<n*log2n<n^2<n^3<2^n<3^n<n!example1 1）sum=0；（1次）

2）for(i=1;i<=n;i++)（n次）

3）for(j=1;j<=n;j++)（n^2次）

4）sum++；（n^2次）

T(n)=2n^2+n+1=O(n^2)example2 for(i=1;i<n;i++)... { y=y+1;①n-1次

for(j=0;j<=(2*n);j++) x++;② }

T(n)=2n^2-n-1+(n-1)=2n^2-2example3

i=1;①1次

while(i<=n)i=i*2;②设语句2的频度是f(n),则：

2^f(n)<=n;f(n)<=log2n取最大值f(n)=log2n,则该程序的时间复杂度T(n)=O(log2n)⑧WhyNotUseArraysforEverything?仅使用数组似乎就能完成所有的工作，为什么不用数组进行所有的数据存储呢？无序数组可以很快进行插入（O(1)时间）,但查找却要花费O(N)时间.有序数组可以查找很快，用O(logN)时间，但插入操作却花费了O(N)时间.两种数组,平均半数的数据项为了填补空必须移动，删除操作平均需要O(N)时间.数组一旦被创建，其大小固定。但开始设计程序时，大多数情况不知道会有多少数据项将会放入到数组中，所以需要猜测数组大小.过大浪费空间，过小会溢出。--后面我们会介绍更加灵活的数据结构SummaryArraysinJavaareobjects,createdwiththenewoperator.Unorderedarraysofferfastinsertionbutslowsearchinganddeletion.Wrappinganarrayinaclassprotectsthearrayfrombeinginadvertentlyaltered.Aclassinterfacecomprisesthemethods(andoccasionallyfields)thattheclassusercanaccess.Abinarysearchcanbeappliedtoanorderedarray.Linearsearchesrequiretimeproportionaltothenumberofitemsinanarray.Binarysearchesrequiretimeproportionaltothelogarithmofthenumberofitems.BigOnotationprovidesaconvenientwaytocomparethespeedofalgorithms.AnalgorithmthatrunsinO(1)timeisthebest,O(logN)isgood,O(N)isfair,andO(N2)isprettybad.习题1向一个无序数组中插入一个数据项：A费时与数组的大小成正比B需要多次比较C需要移动其他数据项来提供空间D不管已有多少数据项都花费同样的时间2在无序数组中，允许重复会导致：A所有操作时间都会增加B在某些情况下查找时间的增加C总会增加插入的时间D有时会减少插入的时间3如果类A要使用类B，那么：A类A中的方法应该很好理解B如果类B与程序交互是更加可取的C比较复杂的操作都应放在类A中D类B能做的操作越多越好4与无序数组相比，有序数组：A删除更快B插入更快C创建更快D查找更快5在一个含有200个数据项的数组中完成二分查找所需要检查的最大数据项个数是：A200B8C1D136大O表示法表示了：A算法的速度是如何与数据项的个数相关的B含有给定大小的数据结构的算法运行时间C含有给定数据项数目的算法的运行时间D数据结构的大小是如何与数据项的个数相关的7Java中创建了一个数组需要使用关键字8当类A使用类B时，可以被类A访问的类B中的方法和字段称作是类B的9O(1)意味着一个操作执行了的时间10简单类型变量和都可以存入数组中new接口常量对象编程作业向hig