中北大学机械cadcam技术第二章机械cad、cam常用的数据结构

《中北大学机械cadcam技术第二章机械cad、cam常用的数据结构》由会员分享，可在线阅读，更多相关《中北大学机械cadcam技术第二章机械cad、cam常用的数据结构（106页珍藏版）》请在金锄头文库上搜索。

1、1. 理解和掌握有关数据结构的相关概念； 2. 熟练掌握线形表存储结构和相关操作方法； 3. 掌握栈、队列、树数据结构的运算方法。,第一节 基本概念 第二节 线形表 第三节 栈、队列和数组 第四节 树结构,本 章 内 容,机械CAD/CAM课程教案,教学目的,第二章 机械CAD/CAM常用的数据结构,第 1 节 基本概念,1. 数据(data),是对客观事物的符号表示，是指所有能输入到计算 机内并被计算机处理的符号的总称。,2. 数据元素(data element),是数据的基本单位，是数据这个集合中相对独立的个体。,3. 数据的逻辑结构(The logical structure of th

2、e data),是指数据之间的逻辑关系。,表 学生成绩表,第 1 节 基本概念,4.数据的物理结构(The physical structure of the data ),是数据元素和它们之间的关系在计算机中的存储表示。 计算机处理信息的最小单位叫做位(bit)，一个位表示一个二进制的数。 若干位的组合形成一个位串(string) 。用一个位串表示一个数据元素，称这样的位串为一个结点(node) 。,6. 数据运算(data operation),是指对数据进行的各种操作。,5. 数据类型(data type),是程序设计语言提供的变量类别。,7.数据结构(data structure),第

3、 1 节 基本概念,是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。,第 2 节 线形表,线性表n(n0)个数据元素按前驱后继关系排成的有限序列。 同一表中的数据元素的类型必须相同； 除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继；如工资表、学生名册。 线性表中数据元素的个数定义为线性表的长度。,线性表的顺序存储结构 顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放。 假定每个数据元素占用L个存储单元，每个数据元素第1个单元的存储位置为该数据元素的存储位置，若第1个数据元素

4、的存储化置为b，则第i个数据元素的存储位置为 Loc(ai)b十(i1)L,第 2 节 线形表,第 2 节 线形表,线性表的顺序存储结构 特点：1）有序性；2）均匀性。 操作：1）建表； 2）访问； 3）修改； 4）删除； 5）插入。,顺序表类型定义 #define ListSize 100 /表空间的大小可根据实际需要而定，这里假设为100 typedef int DataType; /DataType的类型可根据实际情况而定，这里假设为int typedef struct DataType dataListSize；/向量data用于存放表结点 int length；/当前的表长度 Seq

5、List；,顺序表上实现的基本运算 （1）表的初始化 void InitList（SeqList *L） 顺序表的初始化即将表的长度置为0 L-length=0； （2）求表长 int ListLength（SeqList *L） 求表长只需返回L-length return L-length; （3）取表中第i个结点 DataType GetNode（L，i） 取表中第i个结点只需返回和L-datai-1即可 if (i L-length-1) Error(“position error“)； return L-datai-1； ,线性表插入运算：,第 2 节 线形表,线性表的链式存储结构

6、特点：1）存储单元可以不连续、动态分配存储空间； 2）存储结点有两种域：数据域、指针域。 单向链表 双向链表 循环链表,单链表类型描述 typedef char DataType; /假设结点的数据域类型为字符 typedef struct node /结点类型定义 DataType data; /结点的数据域 struct node *next;/结点的指针域 ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head;, 生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode)

7、； /函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中 释放结点变量空间的标准函数 free(p)；/释放p所指的结点变量空间 结点分量的访问 利用结点变量的名字*p访问结点分量 方法一：(*p).data和(*p).next 方法二：p-data和p-next 指针变量p和结点变量*p的关系 指针变量p的值结点地址 结点变量*p的值结点内容 (*p).data的值p指针所指结点的data域的值 (*p).next的值*p后继结点的地址 *(*p).next)*p后继结点,第 2 节 线形表,单向链表的操作 操作：1）建表； 2）访问； 3）修改；

8、4）删除； 5）插入。,第 2 节 线形表,建表,链表插入操作运算步骤：申请新结点存储空间；将待插入元素M存放在新增结点数据域；新增结点指针链接。,第 2 节 线形表,访问,第 2 节 线形表,查找 修改 删除 插入,第 2 节 线形表,双向链表,第 2 节 线形表,双向链表的操作 1）建表,第 2 节 线形表,建表,第 2 节 线形表,查找 修改 删除 插入,第 2 节 线形表,链式存储相对于顺序存储的特点： (1)删除或插入运算速度快，因为删除或插入运算过程中数据并不移动； (2)无需事先分配存储空间，以免有些空间不能充分利用； (3)表的容量易于扩充； (4)按逻辑顺序进行查找的速度慢；

9、 (5)比相等长度的顺序存储多占用作为指针域的存储空间。,线性表顺序存储与链式存储结构比较,顺序存储： 优点：结构均匀，便于数据元素访问和修改操作； 不足：删除插入大量数据元素需移动，运算效率低。 应用：多用于查找频繁、很少增删的场合。 链式存储： 优点：删除插入效率高，不需数据元素移动，不需 事先分配存储空间，存储空间利用充分。 不足：搜索效率低，需从头结点顺次搜寻。 应用多用于事先难以确定容量，频繁增、删场合。,第 3 节 栈、队列和数组,栈 栈的结构 (1)栈的逻辑结构 线形表：后进先出 (2)栈的存储结构 一般采用顺序存储结构,栈的定义 栈(Stack)是限制在表的一端进行插入和删除运

10、算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom).当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,栈：限定只能在表的一端进行插入和删除的特殊的线性表. 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 栈顶（top)：允许插入和删除的一端； 栈顶的当前位置由栈顶指针的位置指示器指示。 栈底（bott

11、om):不允许插入和删除的一端。 进栈或入栈：栈的插入操作。 出栈或退栈：栈的删除操作。,栈的定义,空栈：没有元素的栈 栈的特性： 先进后出（LIFO），即只能在末端（栈顶）进行插、删的操作,栈的定义,栈中的几种基本操作： 1.设置空栈 初始化：initStack(S); 清空：emptyStack (S); 2.插入一个新的栈顶元素（进栈）:push(S,x); 3.删除栈顶元素（出栈）: pop(S); 4.读取栈顶元素:getTop(S); 5.判空栈:stackEmpty(S); 6.判满栈:stackFull(S); 7.显示栈中元素：stackTraverse(S);,第 3 节

12、栈、队列和数组,第 3 节 栈、队列和数组,第 3 节 栈、队列和数组,栈的存储结构,顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，一般用一维数组表示 必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置 链栈 采用链表作为存储结构实现的 必须设置一个栈顶指针永远指向栈顶,栈的表示和实现,一、顺序栈 栈的顺序存储结构简称为顺序栈，它 是运算受限的线性表。因此，可用数组来 实现顺序栈。因为栈底位置是固定不变的, 所以可以将栈底位置设置在数组的两端的 任何一个端点；栈顶位置是随着进栈和退 栈操作而变化的。,栈的表示和实现,需用一个整型变量top来指示当前栈

13、顶的位 置，通常称top为栈顶指针。因此，顺序栈的 类型定义只需将顺序表的类型定义中的长度 属性改为top即可。,一、顺序栈,顺序栈的结构 #define Stack_Size 50 typedef struct StackElemType elemStack_Size; /*用一维数组存放自栈底到栈顶的数据元素*/ int top; /*附设一个位置指针top*/ SeqStack;,一、顺序栈,设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即selem0是栈底元素. 那么： 进栈：stop加1；退栈：stop 减1； 空栈：stoptop =stacksize-1。 上溢：

14、当栈满时再做进栈运算必定产生的空间溢出;下溢：当栈空时再做退栈运算产生的溢出。 上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。,一、顺序栈,设数组S是一个顺序栈 栈S的最大容量stacksize=4 ，初始状态top=1,栈空,10进栈,30出栈,栈满,top=stacksize-1,进栈算法 #define Statck_Size 100 int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return 0; S-top+; S-elemS-to

15、p=x; return(1); ,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,一、顺序栈,进栈算法 #define Statck_Size 100 int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return(0); S-top+; S-elemS-top=x; return(1); ,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,一、顺序栈,进栈算法 #define Statck_Size 100 int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return(0); S-top+; S-elemS-top=x; return(1); ,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,x,一、顺序栈,出栈算法： int pop(SeqStack *S, StackElementType *x), if(S-top= =1) printf(“stack empty”); return(0);