中北大学机械CADCAM技术第二章机械CAD、CAM常用的数据结构.ppt

第二章 机械CAD/CAM常用的数据结构 第 1 节 基本概念 第 1 节 基本概念 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 第 2 节 线形表 线性表顺序存储与链式存储结构比较 第 3 节 栈、队列和数组 空栈：没有元素的栈 栈的特性： 先进后出（LIFO），即只能在末端（栈顶）进行插、删的操作 第 3 节 栈、队列和数组 第 3 节 栈、队列和数组 第 3 节 栈、队列和数组 栈的存储结构 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，一般用一维数组表示 必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置 链栈 采用链表作为存储结构实现的 必须设置一个栈顶指针永远指向栈顶 为两个栈申请一个共享的一维数组空间S[M] 将两个栈的栈底分别放在一维数组的两端，分别是0，M－1 共享栈的结构定义 共享栈的进栈操作 共享栈的出栈操作 第 3 节 栈、队列和数组 第 3 节 栈、队列和数组 队列的主要运算 设置一个空队列； 插入一个新的队尾元素，称为进队； 删除队头元素，称为出队； 读取队头元素；等 队列的存储结构 （1）顺序存储结构 队列的类型定义： #define MAXSIZE 50 typedef struct {QueueElementType elem [MAXSIZE]; int front;int rear; }SeqQueue; 和栈类似，队列中亦有上溢和下溢现象。 此外，顺序队列中还存在“假上溢”（假溢出） 现象。因为在入队和出队的操作中，头尾指针 只增加不减小，致使被删除元素的空间永远无 法重新利用。因此，尽管队列中实际的元素个 数远远小于向量空间的规模，但也可能由于尾 指针巳超出向量空间的上界而不能做入队操作 。该现象称为假上溢。 区分队列空与满另一种方法 少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满（注意：rear所指的单元始终为空）； 第 3 节 栈、队列和数组 temp a1 a2 ∧ an base top 出栈算法 int Pop(LinkStack top, StackElementType *x) {Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp); } x a1 二、链栈 temp a1 a2 ∧ an base top 出栈算法 int Pop(LinkStack top, StackElementType *x) {Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp); } x a1 二、链栈 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 例如：排队购物。操作系统中的作业排队。 先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 　　当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。 2.3 队列的定义 队列（Queue）：限定在表一端插入，在另一端删除的“先进先出”线性表。 an an-1 …… ak …… a2 a1 入队 出队 队列数据结构 循环 队列 第 3 节 栈、队列和数组 队列 队列 尾追头为满 头追尾为空 尾指‘+1’判断 下图是队列的示意图： 出队 入队 队头 队尾 　 a1　a2　…　an　　　　　 队尾：在队列中，允许插入的一端 队头：在队列中，允许删除的一端 2.3 队列的定义 (a) 线性队列 (b) 循环队列 （2）链式存储结构 队列的表示和实现 e1,e2出队， e4入队队满 e1 e2 e3 (b) rear front e1,e2,e3入队