数据结构63798.ppt

数据结构 1.1 何谓数据结构 数据的逻辑结构 线性结构：一对一 树形结构：一对多 图形结构：多对多 数据的存储结构 顺序存储 链式存储 索引 散列 1.2 算法与伪码 算法（Algorithms） 有穷性：一个算法必须总是在执行有限步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确定的含义，无二义性。 可行性：算法中描述的操作都是可以通过已经实现的基本操作执行有限次来实现。 输入：零个或多个输入。 输出：有一个或多个输出。 算法的表示 条列式的步骤（自然语言） 流程图 传统流程图 N—S流程图 伪码：以夹杂程序语法和自然语言来描述解决问题的方法 程序：直接以程序语法来描述解决问题的方法 1．3 时间复杂度分析 2.程序分析 程序中可能的查找次数： 最佳情况：当查找的是第一个数据时，一次成功。记作B(n)=1∈Ο(1) 最坏情况: 当数据不存在时，需要n次比较。记作W(n)=n∈Ο(n) 平均情况：（n+1）/2。记作A(n)=(n+1)/2∈Ο(n)一般情况的时间复杂度存在时:E(n)= B(n)= W(n)= A(n) 2．1 线性表 线性表的定义如果一个数据元素序列满足： （1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素； （2）第一个数据元素没有前驱数据元素； （3）最后一个数据元素没有后继数据元素。 则称这样的数据结构为线性结构。线性表是相同类型的数据元素的有限序列。是一种可以在任意位置进行插入和删除数据元素操作的线性结构。一个有n个数据元素a0, a1, a2, ..., an-1的线性表通常用符号（a0, a1, a2, ..., an-1）表示，其中符号ai（0≤i≤n-1）表示第i个抽象数据元素。其中n为表的长度，n=0为空表。 2．1．1 线性表的顺序存储 线性表的顺序存储，就是把线性表的数据元素存储在一块连续地址空间的内存单元中。这样线性表中，逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。其中，a0,a1,a2等表示顺序表中存储的数据元素，listArray表示存储数据元素的数组，maxSize表示数组的最大允许数据元素个数，size表示数组的当前数据元素个数。2．1．2 线性表的操作 顺序表的算法分析插入和删除是顺序表中时间复杂度最高的成员函数。插入时，主要的耗时部分是循环移动数据元素部分。循环移动数据元素的效率和插入的位置i有关，最坏情况是i = 0，需移动size个数据元素；最好情况是i = size，需移动0个数据元素。平均次数为： 2．1．2 线性表的操作顺序表中的其余操作都和数据元素个数n无关，因此在顺序表中插入和删除一个数据元素成员函数的时间复杂度为O（n）。顺序表支持随机读取，因此，顺序表取数据元素的时间复杂度为O（1）。顺序表的主要优点是：支持随机读取，以及内存空间利用效率高。顺序表的主要缺点是：需要预先给出（很难准确）数组的最大数据元素个数，另外，插入和删除操作时需要移动较多的数据元素。 2．2 线性链表 Java语言虽然删除了Pointer类型，但是还可以运用数组来模拟出链表。不仅如此，Java语言中还有一个Java.utility的类库供了链表的类供程序设计者使用，读者如果对于这个链表的类有兴趣可在JDK的目录下，找到一个叫src.jar的文件，使用解压缩软件来打开这个文件，就可以在\src\java\util的目录下找到一个叫LinkedList.java的文件，其中就是链表的相关程序代码。 本书的重点在于帮助读者建立数据结构概念，而非面向对象程序技术，所以本章有时不使用Java所提供的LinkedList类，而采用数组来模拟链表。LinkedList类的使用方法比较简单，有关Java.utility中Linkedlist类的使用方法及其方法的功能可以略见一二。 2.2.1 线性链表链表是线性表的链式存储结构，是把线性表的数据元素存放在结点中，结点是有数据域和一个或几个指针域组成，指针指向后继或其他结点的地址。以动态内存配置的链表，在插入或删除元素时，只需将指针改变指向即可。单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。 2．2．2 单链表的操作 (3)插入点在链表中间 2．2．2 单链表的操作 (3)删除链表中间结点删除的结点在链表的中间，如果我们找到Pointer结点，则需要