机械CAD CAM第二版课件教学课件 ppt 作者 明兴祖 姚建民 主编第二章 数据结构与数据库技术.ppt

顺序队列 将队列中元素全部存入一个一维数组中,数组的低下标一端为队头,高下标一端为队尾，将这样的队列看成是顺序队列 ，如图所示： 若一维数组中所有位置上都被元素装满，称为队满，即尾指针rear指向一维数组最后,而头指针指向一维数组开头，称为队满。 但有可能出现这样情况，尾指针指向一维数组最后，但前面有很多元素已经出队，即空出很多位置，这时要插入元素，仍然会发生溢出。例如，在下图中，若队列的最大容量maxsize=8，此时，rear=8，再进队时将发生溢出。我们将这种溢出称为“假溢出”。 要克服“假溢出”，可 以将整个队列中元素向 前移动，直到头指针 front为零，或者每次 出队时，都将队列中元素前移一个位置。因此，顺序队列的队满判定条件为rear=maxsize。但是，在顺序队列中，这些克服假溢出的方法都会引起大量元素的移动，花费大量的时间，所以在实际应用中很少采用，一般采用循环队列形式。 循环队列 为了克服顺序队列中假溢出，通常将一维数组queue[0]到q[maxsize-1]看成是一个首尾相接的圆环，即queue[0]与queue[maxsize-1]相接在一起。将这种形式的顺序队列称为循环队列，见下图。 循环 队列 队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它。 第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。 第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。 四、数组 1．一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 2．二维数组 二维数组可以看成是向量的推广。 可将一行（或一列）数据元素视为一个数组元素，而这些数据元素又组成一个一维数组；二维数组的行号（或列号）便成为新的一维数组各数组元素的下标号，这就相当于一个新的线性表。 数组与线性表的区别： 数组一旦定义之后，其数组元素的个数是一定的，即其长度是不变的，没有插入和删除操作，只有存取和修改数组元素的运算。 数组的物理结构： 数组与线性表的存储方式相同，用顺序存储结构存放数组时，在存储器中都是按一维顺序排列存储的。但在存放二维以上数组时，存储方式有所差异。如对一个二维数组A（2，3）： 它共有六个元素，存储时，有按行顺序存放（如BASIC、PASCAL、COBOL和C语言），如下图左；也有按列顺序存放（如FORTRAN语言），如下图右。 a11 a12 a13 a21 a22 a23 按行顺序存放 a11 a21 a12 a22 a13 a23 按列顺序存放 对数组元素的访问： 数组中各元素存储的特点是顺序的、连续的和均匀的。这样在访问数组（查找）时，根据第一数组元素的存储地址和每个数组元素所占的存储单元长度，就可以计算出每个数组元素的地址，以便计算机可以对其进行随机访问。 对于按列顺序存放的数组，其数组元素地址的计算公式，对二维数组为： L（aij）=L（a11）+m（j-1）l +（i-1）l 式中，L（a11）为二维数组第一列第一个元素的存储地址，m为二维数组的行数，l为每一个数组元素所需要的存储单元数（长度）。 对于三维数组为： L（aijk）=L（a111）+m n（k-1）l +m（j-1）l+（i-1）l 式中，n为三维数组的列数，k为三维数组的层数，其它符号的含义同上述二维数组。 五、树 （一）基本概念和术语： 树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…， Tm-1，每个集合Ti（i=0,1, …,m-1）又是一棵树，称为根的 子树，每棵子树的根结点有且仅 有一个直接前驱，但可以有0