uml与面向对象系统分析与设计与java9

1、第六讲 算法与数据结构 （数组、向量及字符处理）1、数组（Array）2、向量（Vector）3、字符处理（String）4、算法：递归、排序、查找5、复杂数据结构程序 算法 数据结构 软件：刻画现实世界，解决现实世界中的问题 语言：实现的工具 算法：问题的解的描述 数据结构：现实世界的数据模型 程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。瑞士科学家沃思（Niklaus Wirth，1984年图灵奖得主）在1976年出版了著名的程序算法数据结构一书。不了解施加于数据上的算法就无法决定如何构造数据，反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。简而言

2、之，程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。1、数组一维数组：定义一维数组的定义方式为： type arrayName ； 其中类型(type)可以为Java中任意的数据类型，包 括简单类型和组合类型，数组名arrayName为一个 合法的标识符， 指明该变量是一个数组类型变量。 例如： int intArray ； 声明了一个整型数组，数组中的每个元素为整型数据。 我们还可以定义一个复合类型的数组，例如： Date dateArray ；声明了一个容纳复合数据类型Date的数组。 与C、C+不同，Java在数组的定义中并不为数组元素分配内存，因此 中不用指出数组中元素的

3、个数，即数组长度，而且对于如上定义的一个数组是不能访问它的任何元素的。必须经过初始化后，才能应用数组的元素。1、数组一维数组：定义 除了这种定义数组的方式之外，java语言还提供了其他的定义形式，如下所示：type arrayName； 对于以上举出的例子，我们也可以这样定义：int intArray； Date dateArray;1、数组一维数组：定义一维数组定义之后，必须经过初始化才可以引用。数组的初始化分为静态初始化和动态初始化两种： 静态初始化：在定义数组的同时对数组元素进行初始化，例如： int intArray =1,2,3,4;/定义了一个含有4个 / 元素的int型数组。1、

4、数组一维数组：初始化 动态初始化：使用运算符new为数组分配空间，对于简单类型的数组，其格式如下： type arrayName =new typearraySize; type arrayName=new typearraySize;对于复合类型的数组，需要经过两步空间分配。 首先： type arrayName =new typearraySize; 然后：arrayName0=new type(paramList); arrayNamearraySize-1=new type(paramList);1、数组一维数组：初始化例如：String stringArrar; /定义一个Strin

5、g类型的数组stringArray = new String3; /给数组stringArray分配3个应用 /空间，初始化每个引用值为nullstringArray0=new String(“how”);stringArray1=new String(“are”);stringArray2=new String(“you”);初始化各数组元素1、数组一维数组：初始化当定义了一个数组，并用运算符new为它分配了内存空间后，就可以引用数组中的每一个元素了。元素的引用方式为： arrayNameindex index为数组下标，可以是整型常数或表达式，如：arrayName1, arrayName

6、i, arrayName6*i等。下标是0序的，即从0开始，一直到数组长度减1。1、数组一维数组：引用 另外，与C、C+中不同，Java对数组元素要进行越界检查以保证安全性。同时，对于每个数组都有一个属性length指明它的长度，例如： intArray.length指明数组intArray的长度。 1、数组一维数组：边界检查 public class ArrayTest public static void main( String args ) int i; int a = new int5; for( i=0; i=0; i- ) System.out.println(a+i+ = +a

7、i); 该程序对数组中的每个元素赋值，然后按逆序输出。 1、数组一维数组：示例运行结果为：C:java ArrayTest a4 = 4a3 = 3 a2 = 2 a1 = 1a0 = 01、数组一维数组：示例数组作为参数/ Passing arrays and individual array elements to methods/ Java core packagesimport java.awt.Container;/ Java extension packagesimport javax.swing.*;public class PassArray extends JApplet /

8、 initialize applet public void init() JTextArea outputArea = new JTextArea(); Container container = getContentPane(); container.add( outputArea ); int array = 1, 2, 3, 4, 5 ; String output = Effects of passing entire array by reference:n + The values of the original array are:n; / append original ar

9、ray elements to String output for ( int counter = 0; counter array.length; counter+ ) output += + array counter ; modifyArray( array ); / array passed by reference output += nnThe values of the modified array are:n; / append modified array elements to String output for ( int counter = 0; counter arr

10、ay.length; counter+ ) output += + array counter ; output += nnEffects of passing array + element by value:n + a3 before modifyElement: + array 3 ; / attempt to modify array 3 modifyElement( array 3 ); output += na3 after modifyElement: + array 3 ; outputArea.setText( output ); / end method init / mu

11、ltiply each element of an array by 2 public void modifyArray( int array2 ) for ( int counter = 0; counter array2.length; counter+ ) array2 counter *= 2; / multiply argument by 2 public void modifyElement( int element ) element *= 2; / end class PassArray1、数组一维数组：示例在任何语言中，多维数组都被看作数组的数组。比如二维数组是一个特殊的一维

12、数组，其每一个元素又是一个一维数组。我们主要以二维数组为例来说明，高维数组与此类似。1、数组多维数组二维数组的定义方式 type arrayName ； 例如： int intArray ； 也可以采用另一种定义方式： type arrayName;与一维数组一样，这时对数组元素也没有分配内存空间，同样要使用运算符new来分配内存，然后才可以访问每个元素。1、数组二维数组：定义二维数组的初始化也分为静态和动态两种。 静态初始化：在定义数组的同时为数组分配空间。 int intArray =1,2,2,3,3,4;不必指出数组每一维的大小，系统会根据初始化时给出的初始值的个数自动算出数组每一维的

13、大小。1、数组二维数组：初始化动态初始化：对高维数组来说，分配内存空间有下面两种方法：1.直接为每一维分配空间，如： type arrayName =new typearraylength1arraylength2例如： int a =new int23；1、数组二维数组：初始化2.从最高维开始（而且必须从最高维开始），分别为每一维分配空间，如： String s =new String2 ; s0=new String2; s1=new String3; s00=new String(“Good”); s01=new String(“Luck”); s10=new String(“to”);

14、 s11=new String(“you”); s12=new String(“!”);1、数组二维数组：初始化二维数组的引用 对二维数组中每个元素，引用方式为： arrayNameindex1index2 其中index1和index2为数组下标，为整型常数和表达式，都是0序的。二维数组举例 两个矩阵相乘，参照参考书在课余时间上机练习。1、数组二维数组：引用及示例数组是用来表达一组同类型数据的数据结构在Java中数组是定长的，数组的大小不会动态变化数组变量的值是数组对象实例的引用在java.util包中的Arrays类提供了一些操作数组的方法在java.util包中的Vector提供了动态变

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

16、a.util.Arraysboolean equals(type a, type a2)两个数组大小相同，并且每一个元素相等两个null数组是相等的1、数组java.util.Arraysvoid sort(type a)void sort(type a, int fromIndx, int toIndex)void sort(type a, Comparatorc)void sort(type a, int fromIndx, int toIndex, Comparatorc)包括afromIndx，但不包括atoIndexfromIndx= toIndex时，范围是一个空的范围排序算法都具

17、有n*log(n)的计算复杂性，效率高排序算法都保证稳定，即排序算法不会改变相等元素的顺序对不同类型的数组，算法的实现并不完全相同可以用自己的Comparator对象声明自定义的顺序1、数组java.util.Arraysjava.lang.Systemvoid arraycopy(Objectsrc, intsrc_position, Objectdst, intdst_position, intlength)范围不能越界可对任何同类型的数组进行复制数组复制过程中做严格的类型检查更详细的内容参见JDK文档1、数组数组的复制 向量(Vector)是java.util类包提供的一个工具类。它对应

18、于类似数组的顺序存储的数据结构，但是具有比数组更强大的功能。它是允许不同类型元素共存的变长数组。每个Vector类的对象可以表达一个完整的数据序列。Vector类的对象不但可以保存顺序的一列数据，而且还提供了许多有用的方法来操作和处理这些数据。 另外，Vector类对象所表达的序列中元素的个数是可变的，即Vector实现了变长数组。2、向量 Java中的数组只能保存固定数目的元素，且必须把所有需要的内存单元一次性的申请出来，而不能先创建数组再追加数组元素数量，为了解决这个问题Java中引入了向量类Vector。Vector也是一组对象的集合，但相对于数组，Vector可以追加对象元素数量，可以

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

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

21、 index)：将新元素插 入到指定位置。2、向量向向量序列中添加元素下面是使用这两种方法的例子：Vector MyVector=new Vector()；for (int i=1;i=10;i+) MyVector.addElement(new Random();MyVector.insertElementAt(middle,5);2、向量向向量序列中添加元素使用以下方法修改或删除向量序列中的元素： 1. setElementAt(Object obj,int index) 将向量序列index位置处的对象元素设置成为obj，如果这个位置原来有元素则被覆盖。 2. removeElement

22、(Object obj) 删除向量序列中第一个与指定的obj对象相同的元素，同时将后面的元素前提，补上空位。这个方法返回的是布尔值。 3. removeElementAt(int index) 删除index指定位置处的元素，同时将后面的元素前提。2、向量修改或删除向量序列中的元素4. removeAllElements() 清除向量序列中的所有元素。下例中先创建了一个Vector，再删除掉其中的所有字符串对象“to”。Vector MyVector=new Vector(100);for (int i=0;ijava demoOfStringBuffer buffer=abclength=3

23、capacity=192. append public synchronized StringBuffer append(对象类型 对象名) append方法将指定的参数对象转化成字符串，附加在原来的字符串对象之后。3. insert public synchronized StringBuffer insert(int 插入位置，对象类型 对象名) 在指定的位置插入给出的参数对象所转化而得的字符串。3、字符串StringBuffer：基本方法4. setChatAt() public synchronized void setCharAt(int index,char ch) 用来设置指定索

24、引index位置的字符值。5. setLength public synchronized void setLength(int newLength) 如果希望明确地定义字符缓冲区的长度，则可以用此方法。如果newlength大于现在的长度，串尾将补0，如果小于，那么newlength后的字符将丢失。3、字符串StringBuffer：基本方法 1. C/C+的字符串只是简单的以零字符结尾的字符数组，而Java中，字符串是一个封装的对象，这种处理对于编程者提供了许多有利之处。 2. C/C+中可以通过指针直接对字符串所在的内存地址进行操作，并且不对越界情况进行检查，Java中只能通过类Stri

25、ng或StringBuffer所提供的接口对字符串进行操作，并且要对越界情况进行检查并报告，这样大大增加了安全性。 3. 由于类String和StringBuffer的接口都经明确说明，所以我们可以预知Java中字符串处理的功能；而在C/C+中，只有通过库函数或者自定义函数对字符串进行处理。 3、字符串Java与C/C+处理字符串的差别字符类，支持字符的相关操作作为基本数据类型char的包装类提供了一些关于char常量的定义提供了变换大小写的方法参见JDK文档3、字符串Charactor从一个字符串析取子字符串构造方法StringTokenizer(Stringstr) /缺省分隔符，为空格S

26、tringTokenizer(Stringstr, Stringdelim) /指定分隔符StringTokenizer(Stringstr,Stringdelim, booleanreturnDelims)int countTokens()：返回Token的数目boolean hasMoreTokens()：是否还有下一个TokenString nextToken()：返回下一个TokenString nextToken(Stringdelim) ：改变分隔符，从当前位置处，继续返回下一个Token。3、字符串StringTokenizerStringTokenizer st = new S

27、tringTokenizer(this is a test);while (st.hasMoreTokens() println(st.nextToken();输出结果为：thisisatest 3、字符串StringTokenizer算法指的是一种计算过程，具有以下性质： 通用性：即适用于某一类问题中的所有个体，而不只是用来解决一个具体的问题。 能行性：即应有明确的步骤一步一步地引导计算的进行。 机械性：即每个步骤都是机械的、定死的，不需要计算者临时动脑筋。 有限性：至少对某些输入数据，算法应在有限多步内结束，并给出计算结果。 离散性：算法的输入数据及输出数据都应是离散的符号。4、算法：递归

28、、排序、查找算法的基本要求： 正确 易维护（可读，易修改） 方便使用 高效 速度快 运行时间少，时间复杂度低 占用内存少 空间复杂度低 算法的效率可以测试，用大量输入数据测量运行的时间和占用的内存，通过比较判别和选择效率高的算法 更重要的是编程前的分析和估计，即理论的计算，给出事前的判断4、算法：递归、排序、查找递归一个关于递归的故事 一个没有去过北京的人问：天安门是什么样子？去过北京的人答道：天安门有个城楼，城楼上有个国徽，国徽里有个天安门，天安门有个城楼，城楼上有个国徽，国徽里有个天安门， 4、算法：递归、排序、查找递归4、算法：递归、排序、查找递归 递归是常用的编程技术，其基本思想是“自

29、己调用自己”。 数学上最常见、最简单的递归问题就是自然数的阶乘。 n=1 n! = 1; n1 n! = n * (n-1)!;适合用递归方法求解的问题 有一个初始状态 后续的情况可由前面的状态推出 如Fibonacci数列F1 = F2 = 1; Fn = Fn-1 + Fn-2 (n=3)递归与循环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

30、 ) return 1; f1 = 1; f2 = 1; for( i=3; i=n; i+) fn = f1 + f2; f1 = f2; f2 = fn; return fn;4、算法：递归、排序、查找递归递归问题欣赏河内塔（ 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、

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

32、趣的是如何寻找到一个好的办法来进行排序。 就地排序算法：不增加新的存储空间1、插入排序法（Insert Sort）将一个数插入到序列中的合适位置。2、选择排序法（Selection Sort）每次把最小（大）的元素交换到最前面。3、冒泡排序法（Bubble Sort）比较并交换相邻的元素，直到所有元素都被放到合适的位置。4、算法：递归、排序、查找排序4、算法：递归、排序、查找排序：插入排序（思想）4、算法：递归、排序、查找排序：插入排序（算法）int a = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=1; i= 0 &

33、x aj ) aj+1 = aj; j-; aj+1 = x;Worst case递增/递减Comparison = n(n-1)/2Average= n(n-1)/4SpaceNone4、算法：递归、排序、查找排序：插入排序（分析）4、算法：递归、排序、查找排序：选择排序（算法）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 n2Av

34、erage case=n2/4 - n2SpaceNone4、算法：递归、排序、查找排序：选择排序（分析）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; Worst case递增/递减Comparison = n(n-1)/2 - n2Average case=n2/4 - n2SpaceNone4、算法：递归、排序、查找排序：冒泡排序（分析）其他就地排序算法

35、： 前面三种算法的变种 快速排序算法（Quick Sort） 4、算法：递归、排序、查找排序：其他就地排序算法待排序的数据（N个）放在一个一维数组中，另设一个10*N的二维数组，设待排序数据中最大的数是4位，则排序需要4轮扫描，每轮包括分散扫描和集中扫描：分散扫描将数据分散到二维数组中。求出个待排序数据的个位数，以此个位数位行下标，保存到二维数组相应的行中。如104，24将保存到第三行中（0序），90则被保存到第一行中。如果两个数的个位数相同，则保存到同一行中，但它们列下标的先后顺序则由它们在一维数组中的先后顺序决定。集中扫描将二维数组中的数据按照行优先顺序返回到一维数组中。如上面的三个数据返

36、回到一维数组中后成为：90，104，24。第二轮扫描针对十位数做分散扫描和集中扫描，扫描后一维数组中的数据为：104，24，90。第三轮针对百位数，扫描后得到最终排序：24，90，104。4、算法：递归、排序、查找排序：桶排序（思想）009012310402445678911040240902901040243104024090402409010401041024234567890900024090110423456789用空间换时间，效率高4、算法：递归、排序、查找排序：桶排序（分析）4、算法：递归、排序、查找查找 查找是利用给出的匹配关键值，在一个数据集合或数据序列中找出符合匹配关键值的一

37、个或一组数据的过程。 顺序查找：最简单的查找算法，程序从数据序列的第一个数据开始，逐个与匹配关键值比较，直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据序列是否已经排好序。 二分查找：当待查找数据序列中数据比较多时，顺序查找的效率将十分低。二分查找可以提高查找效率，但要求待查找的数据序列已经排好序。以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这样逐步缩小范围，直到找到所需数据。 线性表堆栈（Stack）队列（Queue）列表（List）链表（Linked List）集合（Set） 树（Tree）

38、图（Graph）5、复杂数据结构线性表 数据元素（节点）的有限序列 叫线性表，数组其实也是一种线性表, 也叫顺序表。 （a1, a2, ,an-1, an） a1为首元，an为末元， n叫线性表的长度 ai的后继是ai+1, i=1, ,n-1. an没有后继。 ai的前驱是ai-1, i=2, ,n. a1没有前驱。 ai可以是基本数据类型也可以是引用数据类型。 没有数据的线性表叫空表。空表的长度n=0。 线性表是最简单的也是最基本的数据结构。不同的线性表具有不同的约束和不同的行为。5、复杂数据结构线性表堆栈（Stack）的概念 LIFO（Last In First Out，后进先出）的线性

39、表，元素的插入和删除必须在栈顶进行，不能在栈底进行。对堆栈的操作 push(x)：在栈的顶部插入元素，简称入栈； pop()：删除栈顶的元素，简称出栈。5、复杂数据结构线性表：堆栈（Stack）5、复杂数据结构线性表：堆栈（Stack）5、复杂数据结构线性表：堆栈（Stack）堆栈的应用求表达式的值 表达式的中缀表示法： 31+2*(5-3) 表达式的后缀表示法： 31 2 5 3 - * + 利用后缀表示法求表达式的值：顺序扫描表达式的后缀表示，遇到操作数则将操作数入栈，遇到运算符则将栈顶的两个操作数取出进行计算，并将计算结果入栈。 递归、例外处理等也都是利用堆栈机制来实现。5、复杂数据结构

40、线性表：堆栈（Stack） 队列（Queue）是与堆栈不同的另一类数据结构。在一个队列中，最先入列的数据最先出列（先进先出），这与先入后出的堆栈形成了对比。 在应用软件开发实践中，经常涉及到“先进先处理”的案例。比如，红绿灯下的车辆调度，飞机等候着陆时的机场跑道的指挥控制等。服务行业也有许多相同的情况，比如在一家银行或超市，顾客在服务员（出纳、收银员等）的前面排队的情况。 5、复杂数据结构线性表：队列（Queue）5、复杂数据结构线性表：链表（Linked List） 单链表 循环链表 双向链表 双向循环链表5、复杂数据结构线性表：链表 单链表单链表插入删除AH:1-10 x6+2x8+7x1

41、4BH:-x4+10 x6-3x10+8x14+4x18单链表的应用：多项式加法5、复杂数据结构线性表：链表 单链表5、复杂数据结构线性表：链表 双向链表双向链表插入删除双向链表的应用：稀疏矩阵5、复杂数据结构线性表：链表 双向链表5、复杂数据结构树（Tree）与线性表不同，每个节点的后续可能大于1个。树(Tree)的定义树是n（n=0）个节点的有限集合，有且仅有一个称为根的节点；当n1时，其余节点可以分为m个互不相交的集合，其中每个集合又是一棵树，称为树的子树递归的定义现实世界中的树家谱目录5、复杂数据结构树（Tree）树的示例ABCDE节点(Node)节点的度(Degree)叶子（终端节点

42、）非终端节点树的深度孩子(Child)双亲(Parent)兄弟(Sibling)5、复杂数据结构树（Tree）：树的相关概念InitiateRootParentChildRight_SiblingLeft_SiblingCreateTreeInsertChildDeleteChildTraverseClear5、复杂数据结构树（Tree）：树的操作二叉树(Binary Tree)每个节点最多只有两棵子树，并且子树有左右之分，不能任意互换二叉树的五种形态空只有根只有左子树只有右子树左右子树均不空5、复杂数据结构树（Tree）：二叉树第I层上最多有2I-1个节点深度为K的二叉树最多有2k - 1个

43、节点对于任意一个二叉树，如果其叶子（终端节点）数目为n0，度为2的节点数目为n2，有n0 = n2 + 1完全二叉树与满二叉树5、复杂数据结构树（Tree）：二叉树的性质完全二叉树满二叉树具有n个节点的完全二叉树的深度为log2n+1N个节点的完全二叉树，按照从顶到底，从左到右的顺序编号（1-N)如果I=1，根节点如果I1，则双亲为I/2如果2*IN，则节点I无左孩子，否则左孩子为2*I如果2*I+1N，则节点I无右孩子，否则右孩子为2*I+15、复杂数据结构树（Tree）：二叉树的性质A+B*(C-D)-E/F-/+*A-BDCFE5、复杂数据结构树（Tree）：二叉树的应用（表达式）与树和

44、线性表不同，每个元素都可能与其它元素有关系。形式化定义Graph = (V, R)顶点，V是顶点的集合R是两个顶点之间关系的集合如果属于R，则表示一条弧5、复杂数据结构图（Graph）弧头，弧尾无向图、边顶点数目、边的数目完全图、有向完全图权网络子图5、复杂数据结构图（Graph）：相关概念1243V = V1, V2, V3, V4A = , , , 5、复杂数据结构图（Graph）：例子邻接点依附相关联顶点的度出度入度5、复杂数据结构图（Graph）：其他概念路径，回路和环连通连通图 连通分量生成树生成森林顶点定位取顶点求第一个邻接点求下一个邻接点插入顶点插入弧删除顶点删除弧5、复杂数据结构图（Graph）：图的操作数据类型（数据）DataType节点（关系、自身行为）Node容器（行为）数据结构（Queue）5、复杂数据结构设计与实现5、复杂数据结构设计与实现class DataType class Node DataType data; /结点之间的关系 /Node preNode; /Node nextNode; /Node leftNode; /Node rightNode; /结点自身的行为 void setData(DataType d) DataType getData()