机械CAD中常用的数据结构

《机械CAD中常用的数据结构》由会员分享，可在线阅读，更多相关《机械CAD中常用的数据结构（77页珍藏版）》请在金锄头文库上搜索。

1、 4 机械CAD中常用的数据结构 本章目标 掌握机械CAD中常用的数据结构 本章学习要点 线性表的存储结构以及对线性表的建立、访问、修改、删除和插入的运算 栈的存储结构以及对栈的建立、进栈和出栈的运算 树的存储结构 二叉树的存储结构以及对二叉树的遍历运算4 机械CAD中常用的数据结构4 4.1.1 基本概念4 4.3.3 栈4 4.2.2线性表4 4. .4 4 树4 4. .5 5 二叉树数据是对客观事物的符号表示，是指所有能输入计算机内并被计算机处理的符号的总称。4.1 基本概念数值、字符是数据，图形、图像也是数据。数据元素是数据的基本单位，是数据这个集合中相对独立的个体。零件可以作为产品

2、或部件的数据元素，圆柱体、长方体可以作为零件形体的数据元素，直线、圆弧可以作为图形的数据元素。4.1 基本概念数据的逻辑结构是只考虑数据之间的逻辑关系，独立于数据的存储介质。通常所说的数据结构就是指数据的逻辑结构。4.1 基本概念数据的逻辑结构是只考虑数据之间的逻辑关系，独立于数据的存储介质。通常所说的数据结构就是指数据的逻辑结构。4.1 基本概念数据的物理结构也称为数据的存储结构，是数据元素和它们之间的关系在计算机中的表示。4.1 基本概念结点用一个位串表示一个数据元素，称这样的位串为一个结 点结点是数据元素在计算机中的映像4.1 基本概念机械CAD中常用的数据结构线性表线性表栈树二叉树线性

3、表是一种最常用且最简单的数据结构，是n个数据元素的有限序列（a1、a2、an）。数据元素ai可以是一个数、一个符号，也可以是一个线性表，甚至是更复杂的数据结构。4.2 线性表例如：六角头螺栓(GB/T 5780-2000)的螺纹规格 d 可以构成一个简单的线性表（3，4，5，6，8，10，12，16，20，24，30，36，42）4.2 线性表例如：减速箱明细表，表中的数据元素是由序号、名称、数量和材料4个简单数据组成的一个记录。序号名称数量材料1箱体1HT1002箱盖1HT1003齿轮轴1454端盖145减速箱明细表4.2 线性表例如：六角头螺栓螺纹规格 d 可以构成一个简单的线性表（3，4

4、，5，6，8，10，12，16，20，24，30，36，42）例如：减速箱明细表HT100箱盖2HT100箱体1材料名称序号例如：减速箱明细表，表中的数据元素是由序号、名称、数量和材料4个简单数据组成的一个记录。从上面两个实例中可以看出，尽管线性表中的数据元 素可能是各种各样的，但同一表中数据元素的类型必须 是相同的。4.2 线性表例如：六角头螺栓螺纹规格 d 可以构成一个简单的线性表（3，4，5，6，8，10，12，16，20，24，30，36，42）例如：减速箱明细表HT100箱盖2HT100箱体1材料名称序号除了第一个和最后一个数据元素外，每个数据元素有 且只有一个直接前趋，有且只有一个

5、直接后继。4.2 线性表4.2.1 线性表的顺序存储结构用一组连续的存储单元按线性表数据元素的逻辑结构依次存放表中所有数据元素。4.2 线性表特点：（1） 有序性：各数据元素之间的存储顺序与逻辑顺序一致（2） 均匀性：每个数据元素所占存储空间的长度相等4.2.1 线性表的顺序存储结构4.2 线性表操作：建表访问修改删除插入4.2.1 线性表的顺序存储结构4.2 线性表操作：static char listc =A, B, C, D, E;线性表listc有5个数据（A,B,C,D,E）,用C语言编写程序实现此类操作建表访问修改删除插入64.2.1 线性表的顺序存储结构4.2 线性表操作：cha

6、r c; c=listc2;线性表listc有5个数据（A,B,C,D,E）,用C语言编写程序实现此类操作建表访问修改删除插入4.2.1 线性表的顺序存储结构4.2 线性表操作：Listc2=T;线性表listc有5个数据（A,B,C,D,E）,用C语言编写程序实现此类操作建表访问修改删除插入4.2.1 线性表的顺序存储结构4.2 线性表操作：线性表listc有5个数据（A,B,C,D,E）,用C语言编写程序实现此类操作建表访问修改删除插入4.2.1 线性表的顺序存储结构4.2 线性表从线性表中删除一个数据元素后还必须保持这个线性表的均匀性和有序性，因 此被删除元素之后的所有元素均应向前移动，

7、移动距离为一个数据元素所占存 储空间的长度。操作：#define LEN 6 main() static char listcLEN=(A, B, C, D, E;int i,j;printf(“删除第几个数据元素？“）;scanf(“%d”,for(j=i;ji;j-)listcj=listcj-1;listcj=c1;线性表listc有5个数据（A,B,C,D,E）,用C语言编写程序实现此类操作建表访问修改删除插入建表访问修改删除插入优缺点:1）线性表在顺序结构中对数 据元素的访问（读取）、修改 快而方便，但在删除和插入运 算时，需要对数据元素作大量 的移动。2）由于线性表是一个静态表 ，

8、只有运行前进行定义，定义 完成后，大小不能改变。4.2.1 线性表的顺序存储结构4.2 线性表建表访问修改删除插入应用:多用于查找频繁、很少增删的场合，例如工程手册中的数据表。4.2.1 线性表的顺序存储结构4.2 线性表链式存储结构的特点4.2.2 线性表的链式存储结构4.2 线性表 单向链表:单向链表结点的指针域只有一个,通常存放直接后继的地址。4.2.2 线性表的链式存储结构4.2 线性表 单向链表:假定线性表(A,B,C,D,E)，将其按单向链表存储数据操作：访问、修改、删除、插入4.2.2 线性表的链式存储结构4.2 线性表删 除建 立访 问查 找修 改首先定义结点的数据类型，它有两

9、个成员：data和next。 data用来存放数据元素本身，本例是字符型的；next存放该结点直接后继的地址，所以它必须是指针型的，而且是指向字符型变量的指针。链表不必指出它的长度，而是根据需要动态的申请存储空间。删 除建 立访 问查 找修 改/*定义结点的数据结构*/struct link char data; /*数据域*/structure link *next; /*指向直接后继的指针*/ *head; /*链头结点指针，是全局变量*/删 除建 立访 问查 找修 改/*建立一个单向链表*/void create(void)int i, LEN=5; /*链表初始长度为5*/struct

10、 link *node,*temp;for(i=0;idata=A+i;node-next=NULL;if(i=0) head=temp=node;else temp-next=node;temp=node; 删 除访 问查 找修 改链表的逻辑顺序与存储顺序无关，如果访问第i个元素，首先通过链头结点head找到第1个结点的地址，再根据这个结点的指针域找到下一个结点的地址，直至找到第i个结点的地址，再访问这个结点的数据域。删 除访 问查 找修 改输入i开始node为空？node=head,j=0j=j+1node=node-nexti=j?”没有找到“结束访问node结束删 除访 问查 找修 改

11、/*访问第 i 个数据元素*/char visit ( int i )int j=1;struct link *temp;temp=head;while(temp) if(j+=i) return(temp-data);temp=temp-next;printf(“序号超出链表的范围！”);return(0); 删 除修 改查 找在链表中查找是否有指定的数据元素，若有就输出第一次出现这个数据元素的逻辑位置，否则输出没有这个数据元素的信息。删 除修 改查 找/*查找特定数据元素的结点*/int search (char c) int i=1;struct link *temp;temp=head

12、;while(temp) if(temp-data=c) return(i);i+;temp=temp-next;printf(“没有找到这个数据！”);return(0); 删 除修 改查 找修改第i个数据元素的值时,首先找到这个数据元素的结点。若修改指定数据元素的值，同样先找到这个数据元素的结点，再修改这个结点的数据域即可。删 除查 找若要删除第i个数据元素，需找到第 i-1和第 i 个数据元素的结点，然后将第i-1个结点的指针指向第i+1个结点，再释放第i个结点的存储空间即可。删 除查 找/*删除第 i 个结点*/void delete(int i)int j=1;struct link

13、 *node,*temp;node=temp=head;if(i=1) head=temp-next;free(temp);return; 删 除查 找while(node) if(+j=i) temp=node-next;if(temp=NULL) pritnf(“序号超出链表的范围”); return; node-next=temp-next;free(temp); return; node=node-next; printf(“序号超出链表的范围”); 查 找访 问查 找删除插入在第 i 个数据元素之后插入一个新的数据元素时,首先为该数据元素申请存储空间,得到一个新结点。在新节点的数据域

14、存放数据元素的值，然后找到第i个结点。令结点指针域的指针等于第i个结点指针域的指针，第i个结点的指针域存放新结点的地址即可。查 找访 问查 找修 改插入/*在第 i 个数据元素后插入一个新的数据元素*/void insert(char c,int i)int j=1;struct link *node,*temp;temp=(struct link *)malloc(sizeof(struct link);temp-data=c;if(inext=head;head=temp;elsenode=head;查 找访 问查 找修 改插入while(node-next) if(j+=i) break

15、;node=node-next;if(node!=NULL) temp-next=node-next;node-next=temp; else node=temp;temp-next-NULL; 双向链表:4.2.2 线性表的链式存储结构4.2 线性表数据操作：访问、修改、删除、插入 双向链表:4.2.2 线性表的链式存储结构4.2 线性表 循环链表:4.2.2 线性表的链式存储结构4.2 线性表链表与线性表相比，其特点：（1）删除或插入运算，数据元素不需要移动；（2）不需要事先分配存储空间；（3）表的容量根据需要动态申请和动态释放。4.2.2 线性表的链式存储结构4.2 线性表链式存储结构的应用链表较适合用于表容量大小不定、且增删操作频繁的场合。4.2.2 线性表的链式存储结构4.2 线性表1什么是栈 后进先出4.3 栈三、栈2. 栈的运算深度优先搜索问题4.3 栈三、栈3.栈的应用0 149526378某齿轮传动箱的传动关系图，其中0号轴为输入轴，6、7、8、9号轴为输出轴，其余各轴为中间传动轴。编写程序，输入指定的轴号，打印从0号轴到指定轴的传动路线。4.3 栈#include #include