第四章Java常用数据结构

1、2021/3/261第四章第四章 算法与数据结构算法与数据结构 （数组、向量及字符处理）（数组、向量及字符处理）1、数组（Array）2、向量（Vector）3、字符处理（String）4、算法:递归、排序、查找5、复杂数据结构2021/3/262程序程序 算法算法 数据结构数据结构w 软件:刻画现实世界,解决现实世界中的问题w 语言:实现的工具w 算法:问题的解的描述w 数据结构:现实世界的数据模型w 程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。瑞士科学家沃思（Niklaus Wirth,1984年图灵奖得主）在1976年出版了著名的程序算法数据结构一书。不了解施加

2、于数据上的算法就无法决定如何构造数据,反之,算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。简而言之,程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。2021/3/2631、数组、数组一维数组一维数组:定义定义一维数组的定义方式为: type arrayName ; 其中类型(type)可以为Java中任意的数据类型,包 括基本类型和类类型,数组名arrayName为一个 合法的标识符, 指明该变量是一个数组类型变量。 例如: int intArray ; 声明了一个整型数组,数组中的每个元素为整型数据。2021/3/264 我们还可以定义一个类类型的数组,例如: D

3、ate dateArray ;声明了一个容纳复合数据类型Date的数组。1、数组、数组一维数组一维数组:定义定义 与C、C+不同,Java在数组的定义中并不为数组元素分配内存,因此 中不用指出数组中元素的个数,即数组长度,而且对于如上定义的一个数组是不能访问它的任何元素的。必须经过初始化后,才能应用数组的元素。2021/3/265 除了这种定义数组的方式之外,java语言还提供了其他的定义形式,如下所示:type arrayName;1、数组、数组一维数组一维数组:定义定义对于以上举出的例子,我们也可以这样定义:int intArray; Date dateArray;2021/3/266一维

4、数组定义之后一维数组定义之后,必须经过初始化才可以引用必须经过初始化才可以引用。数组的。数组的初始化分为静态初始化和动态初始化两种初始化分为静态初始化和动态初始化两种:1、数组、数组一维数组一维数组:初始化初始化 静态初始化静态初始化:在定义数组的同时对数组元素进行初始在定义数组的同时对数组元素进行初始化化,例如例如: int intArray =1,2,3,4;/定义了一个含有定义了一个含有4个个 / 元素的元素的int型数组。型数组。2021/3/267 动态初始化动态初始化:使用运算符使用运算符new为数组分配空间为数组分配空间,对于简对于简单类型的数组单类型的数组,其格式如下其格式如下

5、: type arrayName =new typearraySize; type arrayName=new typearraySize;1、数组、数组一维数组一维数组:初始化初始化对于复合类型的数组对于复合类型的数组,需要经过两步空间分配。需要经过两步空间分配。 首先首先: type arrayName =new typearraySize; 然后然后:arrayName0=new type(paramList); arrayNamearraySize-1=new type(paramList);2021/3/268例如例如:String stringArrar; /定义一个定义一个Str

6、ing类型的数组类型的数组stringArray = new String3; /给数组给数组stringArray分配分配3个应用空间个应用空间,初始化每个引用值为初始化每个引用值为nullstringArray0=new String(“how”);stringArray1=new String(“are”);stringArray2=new String(“you”);初始化各数组元素1、数组、数组一维数组一维数组:初始化初始化2021/3/269当定义了一个数组当定义了一个数组,并用运算符并用运算符new为它分配了内存空为它分配了内存空间后间后,就可以引用数组中的每一个元素了。元素的引

7、用就可以引用数组中的每一个元素了。元素的引用方式为方式为: arrayNameindex1、数组、数组一维数组一维数组:引用引用index为数组下标为数组下标,可以是整型常数或表达式可以是整型常数或表达式,如如:arrayName1, arrayNamei, arrayName6*i等。下标是等。下标是0序的序的,即即从从0开始开始,一直一直到数组长度减到数组长度减1。2021/3/2610 另外另外,与与C、C+中不同中不同,Java对数组元素要进对数组元素要进行越界检查以保证安全性。同时行越界检查以保证安全性。同时,对于每个数组都对于每个数组都有一个属性有一个属性length指明它的长度指

8、明它的长度,例如例如: intArray.length指明数组指明数组intArray的长度的长度 例:模拟抽彩游戏模拟抽彩游戏1、数组、数组一维数组一维数组:边界检查边界检查2021/3/2611 Public class LotteryDrawing /模拟抽彩游戏模拟抽彩游戏 public static void main(String args) String input = JOptionPane.showInputDialog (How many numbers do you need to draw?); int k = Integer.parseInt(input); inpu

9、t = JOptionPane.showInputDialog (What is the highest number you can draw?);int n = Integer.parseInt(input);/ numbers 用来存放 1 2 3 . . . n int numbers = new intn; for (int i = 0; i numbers.length; i+) numbersi = i + 1; / result用不存放选取出的数 int result = new intk; for (int i = 0; i result.length; i+) / 在0-N

10、-1之间产生选取出的数 int r = (int)(Math.random() * n);2021/3/2612n / 将选出的数放入resultn resulti = numbersr;n / move the last element into the random locationn numbersr = numbersn - 1;n n-; n / 将result排序输出n Arrays.sort(result);n System.out.printlnn (Bet the following combination. Itll make you rich!);n for (int i

11、 = 0; i result.length; i+)n System.out.println(resulti);n System.exit(0); 2021/3/2613在任何语言中,多维数组都被看作数组的数组。比如二维数组是一个特殊的一维数组,其每一个元素又是一个一维数组。我们主要以二维数组为例来说明,高维数组与此类似。1、数组、数组多维数组多维数组2021/3/2614二维数组的定义方式 type arrayName ; 例如: int intArray ; 1、数组、数组二维数组二维数组:定义定义也可以采用另一种定义方式: type arrayName;与一维数组一样,这时对数组元素也没

12、有分配内存空间,同样要使用运算符new来分配内存,然后才可以访问每个元素。2021/3/2615二维数组的初始化也分为静态和动态两种。 静态初始化静态初始化:在定义数组的同时为数组分配空间。 int intArray =1,2,2,3,3,4;不必指出数组每一维的大小,系统会根据初始化时给出的初始值的个数自动算出数组每一维的大小。1、数组、数组二维数组二维数组:初始化初始化2021/3/2616动态初始化动态初始化:对高维数组来说,分配内存空间有下面两种方法:1.直接为每一维分配空间,如: type arrayName =new typearraylength1arraylength2例如:

13、int a =new int23;1、数组、数组二维数组二维数组:初始化初始化2021/3/26172.从最高维开始（而且必须从最高维开始）,分别为每一维分配空间,如: String s =new String2 ; s0=new String2; s1=new String3; s00=new String(“Good”); s01=new String(“Luck”); s10=new String(“to”); s11=new String(“you”); s12=new String(“!”);1、数组、数组二维数组二维数组:初始化初始化2021/3/2618二维数组的引用二维数组的引

14、用 对二维数组中每个元素对二维数组中每个元素,引用方式为引用方式为: arrayNameindex1index2 其中其中index1和和index2为数组下标为数组下标,为整型常数和表达为整型常数和表达式式,都都是是0序的序的。1、数组、数组二维数组二维数组:引用及示例引用及示例2021/3/2619n数组是用来表达一组同类型数据的数据结构1、数组、数组java.util.Arraysn在Java中数组是定长的,数组的大小不会动态变化n数组变量的值是数组对象实例的引用n在java.util包中的Arrays类提供了一些操作数组的方法n在java.util包中的Vector提供了动态变长数组的

15、功能,Vector的容量可以随着需要变化2021/3/2620nint binarySearch(type a, type key)n数组a必须已经排序,否则返回值无意义n当数组a中有重复的值时,该方法返回的值不确定n如果key存在,则返回它在数组a中的位置n如果不存在,则返回它的“-(插入位置-1)”nvoid fill(type a, type val)void fill(type a, int fromIndx, int toIndex, type val)n包括afromIndx,但不包括atoIndexnfromIndx= toIndex时,范围是一个空的范围1、数组、数组java.

16、util.Arrays2021/3/2621nboolean equals(type a, type a2)n两个数组大小相同,并且每一个元素相等n两个null数组是相等的1、数组、数组java.util.Arrays2021/3/2622nvoid sort(type a)void sort(type a, int fromIndx, int toIndex)void sort(type a, Comparator c)void sort(type a, int fromIndx, int toIndex, Comparator c)n包括afromIndx,但不包括atoIndexnfro

17、mIndx= toIndex时,范围是一个空的范围n排序算法都具有n*log(n)的计算复杂性,效率高n排序算法都保证稳定,即排序算法不会改变相等元素的顺序n对不同类型的数组,算法的实现并不完全相同n可以用自己的Comparator对象声明自定义的顺序1、数组、数组java.util.Arrays2021/3/2623njava.lang.Systemnvoid arraycopy(Object src, int src_position, Object dst, int dst_position, int length)n范围不能越界n可对任何同类型的数组进行复制n数组复制过程中做严格的类型

18、检查数组复制过程中做严格的类型检查n更详细的内容参见JDK文档1、数组、数组数组的复制数组的复制2021/3/2624 向量向量(Vector)是是java.util类包提供的一个工具类。它类包提供的一个工具类。它对应于类似数组的顺序存储的数据结构对应于类似数组的顺序存储的数据结构,但是具有比数组更但是具有比数组更强大的功能。强大的功能。它是允许不同类型元素共存的变长数组它是允许不同类型元素共存的变长数组。每。每个个Vector类的对象可以表达一个完整的数据序列。类的对象可以表达一个完整的数据序列。Vector类的对象不但可以保存顺序的一列数据类的对象不但可以保存顺序的一列数据,而且还提而且还

19、提供了许多有用的方法来操作和处理这些数据。供了许多有用的方法来操作和处理这些数据。 另外另外,Vector类对象所表达的序列中元素的个数是可类对象所表达的序列中元素的个数是可变的变的,即即Vector实现了变长数组实现了变长数组。2、向量、向量2021/3/2625 Java中的数组只能保存固定数目的元素,且必须把所有需要的内存单元一次性的申请出来,而不能先创建数组再追加数组元素数量,为了解决这个问题Java中引入了向量类Vector。Vector也是一组对象的集合,但相对于数组,Vector可以追加对象元素数量,可以方便的修改和维护序列中的对象。2、向量、向量2021/3/2626向量比较适

20、合在如下情况下使用向量比较适合在如下情况下使用: 1. 需要处理的对象数目不定,序列中的元素都是对象或可以表示为对象。 2. 需要将不同类的对象组合成一个数据序列。 3. 需要做频繁的对象序列中元素的插入和删除。 4. 经常需要定位序列中的对象和其他查找操作。 5. 在不同的类之间传递大量的数据。 Vector类的方法相对于数组要多一些,但是使用这个类也有一定的局限性,例如其中的对象不能是简单数据类型等。2、向量、向量2021/3/2627Vector类有三个构造函数: Vector():构造一个空的向量 Vector(int capacity):以指定的存储容量构造一个空的向量 Vector

21、(int capacity, int capacityIncrement):以指定的存储容量和容量增量构造一个空的Vector。例如: Vector MyVector=new Vector(100,50); 这个语句创建的MyVector向量序列初始有100个元素的空间,以后一旦使用殆尽则以50为单位递增,使序列中元素的个数变化成150,200,。在创建Vector序列时,不需要指明序列中元素的类型,可以在使用时确定。2、向量、向量 创建向量类的对象创建向量类的对象2021/3/2628有两种添加元素的方法: addElement( Object obj):将新元素添加到序列尾部。 inser

22、tElementAt(Object obj, int index):将新元素插 入到指定位置。2、向量、向量向向量序列中添加元素向向量序列中添加元素2021/3/2629下面是使用这两种方法的例子:Vector MyVector=new Vector();for (int i=1;i=10;i+) MyVector.addElement(new Random();MyVector.insertElementAt(middle,5);2、向量、向量向向量序列中添加元素向向量序列中添加元素2021/3/2630使用以下方法修改或删除向量序列中的元素: 1. setElementAt(Object

23、obj,int index) 将向量序列index位置处的对象元素设置成为obj,如果这个位置原来有元素则被覆盖。 2. removeElement(Object obj) 删除向量序列中第一个与指定的obj对象相同的元素,同时将后面的元素前提,补上空位。这个方法返回的是布尔值。 3. removeElementAt(int index) 删除index指定位置处的元素,同时将后面的元素前提。2、向量、向量修改或删除向量序列中的元素修改或删除向量序列中的元素2021/3/26314. removeAllElements() 清除向量序列中的所有元素。下例中先创建了一个Vector,再删除掉其中

24、的所有字符串对象“to”。Vector MyVector=new Vector(100);for (int i=0;ijava demoOfStringBuffer buffer=abclength=3capacity=192021/3/26572. append public synchronized StringBuffer append(对象类型 对象名) append方法将指定的参数对象转化成字符串,附加在原来的字符串对象之后。3. insert public synchronized StringBuffer insert(int 插入位置,对象类型 对象名) 在指定的位置插入给出的

25、参数对象所转化而得的字符串。3、字符串、字符串StringBuffer:基本方法基本方法2021/3/26584. setChatAt() public synchronized void setCharAt(int index,char ch) 用来设置指定索引index位置的字符值。5. setLength public synchronized void setLength(int newLength) 如果希望明确地定义字符缓冲区的长度,则可以用此方法。如果newlength大于现在的长度,串尾将补0,如果小于,那么newlength后的字符将丢失。3、字符串、字符串StringBuf

26、fer:基本方法基本方法2021/3/2659 1. C/C+的字符串只是简单的以零字符结尾的字符数组,而Java中,字符串是一个封装的对象,这种处理对于编程者提供了许多有利之处。 2. C/C+中可以通过指针直接对字符串所在的内存地址进行操作,并且不对越界情况进行检查,Java中只能通过类String或StringBuffer所提供的接口对字符串进行操作,并且要对越界情况进行检查并报告,这样大大增加了安全性。 3. 由于类String和StringBuffer的接口都经明确说明,所以我们可以预知Java中字符串处理的功能;而在C/C+中,只有通过库函数或者自定义函数对字符串进行处理。 3、字

27、符串、字符串JavaJava与与C/C+C/C+处理字符串的差别处理字符串的差别2021/3/2660从一个字符串析取子字符串从一个字符串析取子字符串n构造方法nStringTokenizer(String str) /缺省分隔符,为空格nStringTokenizer(String str, String delim) /指定分隔符nStringTokenizer(String str,String delim, boolean returnDelims)nint countTokens():返回Token的数目nboolean hasMoreTokens():是否还有下一个TokennSt

28、ring nextToken():返回下一个TokennString nextToken(String delim) :改变分隔符,从当前位置处,继续返回下一个Token。3、字符串、字符串StringTokenizer2021/3/2661StringTokenizer st = new StringTokenizer(this is a test);while (st.hasMoreTokens() println(st.nextToken();输出结果为:thisisatest 3、字符串、字符串StringTokenizer2021/3/2662字符串与数值的转化字符串与数值的转化n

29、java.langjava.lang包中的包中的IntegerInteger类、类、LongLong类、类、FloatFloat类、类、DoubleDouble类分别提供了相应的方法用来进行字类分别提供了相应的方法用来进行字符串与数值间的转换符串与数值间的转换n转化为整形转化为整形nInteger.parseInt(Integer.parseInt(字符串）字符串）n例例: : Integer.parseInt( Integer.parseInt(“1234512345”）n再如再如:long x;String s=:long x;String s=“10001000”; ;n x= Inte

30、ger.parseLong(s); x= Integer.parseLong(s);2021/3/2663转化为转化为floatfloat的的doubledouble型型格式格式: :Float.valueOf(String s).floatValue();Float.valueOf(String s).floatValue();Double.valueOf(String s).doubleValue();Double.valueOf(String s).doubleValue();FloatFloat.parseFloatFloatDoubleDouble.parseDoubleDouble

31、例例: :float x; double y;float x; double y; String s=“23.45”; String s=“23.45”; x=Float.valueOf(s).floatValue(); x=Float.valueOf(s).floatValue(); y=Double.valueOf(s).doubleValue(); y=Double.valueOf(s).doubleValue();2021/3/2664数值转化为字符使用使用S Stringtring类中定义的类中定义的valueOf()valueOf()方法方法, ,便可将一便可将一个数值个数值 转换

32、为字符串转换为字符串 如如: : float x=123.45f; float x=123.45f; String s; String s; s=String.valueOf(x s=String.valueOf(x);2021/3/2665屏幕抓取的例子 public class ScreenScraping extends JFramenn / JLabel and JComboBox for item namesn private JLabel itemJLabel;n private JComboBox itemJComboBox;n / JLabel and JTextField f

33、or conversion raten private JLabel rateJLabel;n private JTextField rateJTextField;n / JLabel and JTextField for item pricen private JLabel priceJLabel;n private JTextField priceJTextField;n / JButton to search HTML code for item pricen private JButton searchJButton;n / JLabel and JTextArea for HTML

34、coden private JLabel sourceJLabel;n private JTextArea sourceJTextArea;n 2021/3/2666 / items that can be found in HTML coden private String items = IBM 笔记本电脑笔记本电脑,n Sony T9数码相机数码相机, ARCHOS爱可视爱可视MP4 ;n n / small piece of HTML code containing items and pricesn private String htmlText = n + IBM 笔记本电脑笔记本

35、电脑n + €2035.67n + Sony T9数码相机数码相机n + €641.55n + ARCHOS爱可视爱可视MP4n + €1201.83n + ;n n / no-argument constructorn public ScreenScraping()n n createUserInterface();n 2021/3/2667n/ create and position GUI components; register event handlersn private void createUserInterface()n

36、n / get content pane for attaching GUI componentsn Container contentPane = getContentPane();n n / enable explicit positioning of GUI componentsn contentPane.setLayout( null );n / set up itemJLabeln itemJLabel = new JLabel();n itemJLabel.setBounds( 8, 16, 40, 21 );n itemJLabel.setText( Item: );n cont

37、entPane.add( itemJLabel );n n / set up itemJComboBoxn itemJComboBox = new JComboBox( items );n itemJComboBox.setBounds( 56, 16, 184, 21 );n contentPane.add( itemJComboBox );nn 2021/3/2668/ set up rateJLabeln rateJLabel = new JLabel();n rateJLabel.setBounds( 8, 48, 40, 21 );n rateJLabel.setText( Rate

38、: );n contentPane.add( rateJLabel );n / set up rateJTextFieldn rateJTextField = new JTextField();n rateJTextField.setBounds( 56, 48, 184, 21 );n rateJTextField.setHorizontalAlignment( JTextField.RIGHT );n contentPane.add( rateJTextField );n / set up priceJLabeln priceJLabel = new JLabel();n priceJLa

39、bel.setBounds( 8, 80, 40, 21 );n priceJLabel.setText( Price: );n contentPane.add( priceJLabel );n n / set up priceJTextFieldn priceJTextField = new JTextField();n priceJTextField.setBounds( 56, 80, 96, 21 );n 2021/3/2669npriceJTextField.setHorizontalAlignment( JTextField.CENTER );n priceJTextField.s

40、etEditable( false );n contentPane.add( priceJTextField );n / set up searchJButtonn searchJButton = new JButton();n searchJButton.setBounds( 160, 80, 80, 23 );n searchJButton.setText( Search );n contentPane.add( searchJButton );n searchJButton.addActionListener(n new ActionListener() / anonymous inne

41、r classn n / event handler called when searchJButton is pressedn public void actionPerformed( ActionEvent event )n n searchJButtonActionPerformed( event );n n / end anonymous inner classn ); / end call to addActionListener2021/3/2670n / set up sourceJLabeln sourceJLabel = new JLabel();n sourceJLabel

42、.setBounds( 8, 112, 48, 16 );n sourceJLabel.setText( Source: );n contentPane.add( sourceJLabel );n / set up sourceJTextArean sourceJTextArea = new JTextArea();n sourceJTextArea.setBounds( 8, 136, 232, 105 );n sourceJTextArea.setText( htmlText );n sourceJTextArea.setLineWrap( true );n contentPane.add

43、( sourceJTextArea );n n / set properties of applications windown setTitle( Screen Scraping ); / set title bar stringn setSize( 259, 278 ); / set window sizen setVisible( true ); / display windown n / end method createUserInterface n 2021/3/2671n n / find and display price substringn private void sea

44、rchJButtonActionPerformed( ActionEvent event )n n / get raten String rate = rateJTextField.getText();n / rate is an empty stringn if ( rate.equals( ) )n n JOptionPane.showMessageDialog( null, n Please enter conversion rate first.,n Missing Rate, JOptionPane.WARNING_MESSAGE );n n return; / exit metho

45、dn n 2021/3/2672n / search for location of item and pricen String selectedItem = n ( String ) itemJComboBox.getSelectedItem();n int itemLocation = htmlText.indexOf( selectedItem );n int priceBegin = htmlText.indexOf( €, itemLocation );n int priceEnd = htmlText.indexOf( , priceBegin );n / st

46、ore price found in double pricen String priceText = htmlText.substring(n priceBegin + 6, priceEnd );n double price = Double.parseDouble( priceText );n / convert price from euros to dollarsn double conversionRate = Double.parseDouble(n rateJTextField.getText() );n price *= conversionRate; n / display

47、 price of item in priceJTextFieldn DecimalFormat dollars = new DecimalFormat( $0.00 );n priceJTextField.setText( dollars.format( price ) );n / end method searchJButtonActionPerformedn / main methodn public static void main( String args ) n n ScreenScraping application = new ScreenScraping();n applic

48、ation.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );n private String htmlText = + IBM 笔记本电脑笔记本电脑 + €2035.67 + Sony T9数码相机数码相机 + €641.55 + ARCHOS爱可视爱可视MP4 + €1201.83 + ;2021/3/2673算法算法指的是一种计算过程,具有以下性质:q 通用性:即适用于某一类问题中的所有个体,而不只是用来解决一个具体的问题。q 能行性:即应有明确的步骤一步一步地引导计算的进行。q 机械性

49、:即每个步骤都是机械的、定死的,不需要计算者临时动脑筋。q 有限性:至少对某些输入数据,算法应在有限多步内结束,并给出计算结果。q 离散性:算法的输入数据及输出数据都应是离散的符号。4、算法、算法:递归、排序、查找递归、排序、查找2021/3/2674算法的基本要求:q 正确q 易维护（可读,易修改）q 方便使用q 高效 速度快 运行时间少,时间复杂度低 占用内存少 空间复杂度低v 算法的效率可以测试,用大量输入数据测量运行的时间和占用的内存,通过比较判别和选择效率高的算法v 更重要的是编程前的分析和估计,即理论的计算,给出事前的判断4、算法、算法:递归、排序、查找递归、排序、查找2021/3

50、/2675递归递归一个关于递归的故事 一个没有去过北京的人问:天安门是什么样子?去过北京的人答道:天安门有个城楼,城楼上有个国徽,国徽里有个天安门,天安门有个城楼,城楼上有个国徽,国徽里有个天安门, 4、算法、算法:递归、排序、查找递归、排序、查找递归递归2021/3/26764、算法、算法:递归、排序、查找递归、排序、查找递归递归q 递归是常用的编程技术,其基本思想是“自己调用自己”。q 数学上最常见、最简单的递归问题就是自然数的阶乘。n n=1 n! = 1;n n1 n! = n * (n-1)!;适合用递归方法求解的问题适合用递归方法求解的问题q 有一个初始状态q 后续的情况可由前面的

51、状态推出n 如Fibonacci数列F1 = F2 = 1; Fn = Fn-1 + Fn-2 (n=3)2021/3/2677递归与循环递归与循环long Fibonacci(int n) if( n=1| n=2 ) return 1; else return Factorial(n-1) + Factorial(n-2) ;long Fibonacci(int n) int i; long f1,f2,fn; if( n=1| n=2 ) return 1; f1 = 1; f2 = 1; for( i=3; i=n; i+) fn = f1 + f2; f1 = f2; f2 = fn

52、; return fn;4、算法、算法:递归、排序、查找递归、排序、查找递归递归2021/3/2678递归问题欣赏递归问题欣赏河内塔（河内塔（ Hanoi Tower）问题）问题:这是一个流传很久的游戏。1. 有三根杆子A,B,C。A杆上有n只碟子 2. 每次移动一块碟子,小的只能叠在大的上面 3. 把所有碟子从A杆经C杆全部移到B杆上. 递归求解递归求解:1. 若只有一只碟子,直接将它从A杆移到B杆;2. 把n-1只碟子从A杆经B杆移动到C杆,将A杆上第n只碟子移到B杆;然后再将n-1只碟子从C杆经A杆移到B杆。 4、算法、算法:递归、排序、查找递归、排序、查找递归递归2021/3/2679

53、 此外,递归是人工智能语言Lisp/Prolog等进行问题求解的基本手段。递归问题欣赏递归问题欣赏8皇后问题皇后问题:把8个皇后放在8 x 8的棋盘上,使得任何一个都不将其他7个的军。骑士巡游问题骑士巡游问题:给出一个n x n的棋盘,一位骑士按国际象棋的规则移动放在第（0,0）格里,找出一种可以走遍整个棋盘的方案（如果存在的话）。即做n2-1次移动,使得棋盘上每个格子都恰好只被访问一次。4、算法、算法:递归、排序、查找递归、排序、查找递归递归2021/3/26804、算法、算法:递归、排序、查找递归、排序、查找排序排序 排序排序是指对一些数据信息的重新组织,通常是对一个数组进行重新操作,使得

54、信息由大到小（降序）或者由小到大（升序）存储。要求排序是很一种基本的需要。我们所感兴趣的是如何寻找到一个好的办法来进行排序。 2021/3/2681就地排序算法就地排序算法:不增加新的存储空间1、插入排序法（Insert Sort）将一个数插入到序列中的合适位置。2、选择排序法（Selection Sort）每次把最小（大）的元素交换到最前面。3、冒泡排序法（Bubble Sort）比较并交换相邻的元素,直到所有元素都被放到合适的位置。4、算法、算法:递归、排序、查找递归、排序、查找排序排序2021/3/26824、算法、算法:递归、排序、查找递归、排序、查找排序排序:插入排序（思想）插入排序

55、（思想）2021/3/26834、算法、算法:递归、排序、查找递归、排序、查找排序排序:插入排序（算法）插入排序（算法）int a = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=1; i= 0 & x aj ) aj+1 = aj; j-; aj+1 = x;2021/3/2684nWorst casen递增/递减nComparison = n(n-1)/2nAveragen= n(n-1)/4nSpacenNone4、算法、算法:递归、排序、查找递归、排序、查找排序排序:插入排序（分析）插入排序（分析）2021

56、/3/26854、算法、算法:递归、排序、查找递归、排序、查找排序排序:选择排序（算法）选择排序（算法）int num = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=0; inum.length-1; i+) /最后一个元素无需比较 k = i; x = numi; for(j=i+1; jnum.length; j+) if(numj n2nAverage casen=n2/4 - n2nSpacenNone4、算法、算法:递归、排序、查找递归、排序、查找排序排序:选择排序（分析）选择排序（分析）2021/3/2687

57、4、算法、算法:递归、排序、查找递归、排序、查找排序排序:冒泡排序（算法）冒泡排序（算法）int a = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=1; i=i; j-) if( aj-1aj) x = aj-1; aj-1 = aj; aj = x; 2021/3/2688nWorst casen递增/递减nComparison = n(n-1)/2 - n2nAverage casen=n2/4 - n2nSpacenNone4、算法、算法:递归、排序、查找递归、排序、查找排序排序:冒泡排序（分析）冒泡排序（分析）2

58、021/3/2689其他就地排序算法:q 前面三种算法的变种q 快速排序算法（Quick Sort）q 4、算法、算法:递归、排序、查找递归、排序、查找排序排序:其他就地排序算法其他就地排序算法2021/3/2690n待排序的数据（N个）放在一个一维数组中,另设一个10*N的二维数组,设待排序数据中最大的数是4位,则排序需要4轮扫描,每轮包括分散扫描和集中扫描:n分散扫描将数据分散到二维数组中。求出个待排序数据的个位数,以此个位数位行下标,保存到二维数组相应的行中。如104,24将保存到第三行中（0序）,90则被保存到第一行中。如果两个数的个位数相同,则保存到同一行中,但它们列下标的先后顺序则

59、由它们在一维数组中的先后顺序决定。n集中扫描将二维数组中的数据按照行优先顺序返回到一维数组中。如上面的三个数据返回到一维数组中后成为:90,104,24。第二轮扫描针对十位数做分散扫描和集中扫描,扫描后一维数组中的数据为:104,24,90。第三轮针对百位数,扫描后得到最终排序:24,90,104。4、算法、算法:递归、排序、查找递归、排序、查找排序排序:桶排序（思想）桶排序（思想）2021/3/2691009012310402445678911040240902901040243104024090402409010401041024234567890900024090110423456789

60、2021/3/2692n用空间换时间,效率高4、算法、算法:递归、排序、查找递归、排序、查找排序排序:桶排序（分析）桶排序（分析）2021/3/26934、算法、算法:递归、排序、查找递归、排序、查找查找查找 查找是利用给出的匹配关键值,在一个数据集合或数据序列中找出符合匹配关键值的一个或一组数据的过程。q 顺序查找:最简单的查找算法,程序从数据序列的第一个数据开始,逐个与匹配关键值比较,直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据顺序查找不要求待查找的数据序列是否已经排好序序列是否已经排好序。q 二分查找:当待查找数据序列中数据比较多时,顺序查找的效率将十分低。二分查找可以提高查找效率二分查找可以提高查找效率,但要求