1,理解和掌握有关数据结构的相关概念；
2,熟练掌握线形表存储结构和相关操作方法；
3,掌握栈、队列、树数据结构的运算方法。
第一节 基本概念第二节 线形表第三节 栈、队列和数组第四节 树结构本章内容
《机械 CAD/CAM》课程教案教学目的第二章第二章机械机械
CAD/CAM常用的数据结构常用的数据结构第第
1 节节基本概念基本概念
1,数据，是对客观事物的符号表示，是指所有能输入到计算机内并被计算机处理的符号的总称。
2,数据元素，是数据的基本单位，是数据这个集合中相对独立的个体。
3,数据的逻辑结构，是指数据之间的逻辑关系。
4,数据的物理结构，是数据元素和它们之间的关系在计算机中的存储表示。
计算机处理信息的最小单位叫做位 (bit)，一个位表示 一 个二进制的数。
若干位的组合形成一个位串 。用一个位串表示一个数据元素，称这样的位串为一个结点。
5,数据运算，是指对数据进行的各种操作。
6,数据类型，是程序设计语言提供的变量类别。
2.1.1 数据结构的概念数据结构,是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。
数据结构非线性结构数据存储结构数据运算数据逻辑结构线性结构线性表队列栈网状结构树结构链式存储顺序存储插入，删除，更新，检索，排序第第
2 节节线形表线形表
?线性表 ——n(n≥ 0)个数据元素按前驱后继关系排成的有限序列。
9同一表中的数据元素的类型必须相同；
9除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继； 如工资表、学生名册。
9线性表中数据元素的个数定义为线性表的长度。
第第
2 节节线形表线形表
?线性表的顺序存储结构顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放 。
假定每个数据元素占用L个存储单元，每个数据元素第 1个单元的存储位置为该数据元素的存储位置，第1 个数据元素的存储化置为 b，则第i 个数据元素的存储位置为
Loc(a
i
)＝ b十 (i—1)× L
第第
2 节节线形表线形表
?线性表的顺序存储结构特点：1 ）有序性；2 ）均匀性。
操作：1 ）建表；
2）访问；
3）修改；
4）删除；
5）插入。
删除或插入运算时，数据移动量大，运算时间长。
线性表插入运算,
第第
2 节节线形表线形表
?线性表的链式存储结构特点：1 ）存储单元可以不连续、动态分配存储空间；
2）存储结点有两种域：数据域、指针域。
9单向链表
9双向链表
9循环链表第第
2 节节线形表线形表
?单向链表的操作操作：1 ）建表；
2）访问；
3）修改；
4）删除；
5）插入。
第第
2 节节线形表线形表
?建表
链表插入操作运算步骤：①申请新结点存储空间；②将待插入元素M存放在新增结点数据域；③新增结点指针链接。
第第
2 节节线形表线形表
?访问第第
2 节节线形表线形表
?查找
?修改
?删除
?插入第第
2 节节线形表线形表
?双向链表第第
2 节节线形表线形表
?双向链表的操作
1）建表第第
2 节节线形表线形表
?建表第第
2 节节线形表线形表
?查找
?修改
?删除
?插入第第
2 节节线形表线形表
?链式存储相对于顺序存储的特点：
(1)删除或插入运算速度快，因为删除或插入运算过程中数据并不移动；
(2)无需事先分配存储空间，以免有些空间不能充分利用；
(3)表的容量易于扩充；
(4)按逻辑顺序进行查找的速度慢；
(5)比相等长度的顺序存储多占用作为指针域的存储空间。
线性表顺序存储与链式存储结构比较
{ 顺序存储：
优点：结构均匀，便于数据元素访问和修改操作；
不足：删除插入大量数据元素需移动，运算效率低。
应用：多用于查找频繁、很少增删的场合。
{ 链式存储：
优点：删除插入效率高，不需数据元素移动，不需事先分配存储空间，存储空间利用充分。
不足：搜索效率低，需从头结点顺次搜寻。
应用－多用于事先难以确定容量，频繁增、删场合。
第第
3 节节栈、队列和数组栈、队列和数组
1.栈
?栈的结构
(1)栈的逻辑结构
——线形表：后进先出
(2)栈的存储结构
——一般采用顺序存储结构
?栈的运算
(1)建栈
(2)进栈
(3)出栈第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组栈（ Stack）,限定在表尾进行插入或删除操作，且为,后进先出” 的线性表。
队列（ Queue）,限定在表一端插入，在另一端删除的,先进先出” 线性表。
a
1
a
2
…
…
a
k
…
…
a
n-1
a
n
入队出队队列数据结构循环队列第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组队列第第
3 节节栈、队列和数组栈、队列和数组队列第第
3 节节栈、队列和数组栈、队列和数组数组树结构（层次结构）,除根结点之外，所有结点仅有一个直接前驱。
第第
4 节节树树结结构构
结点
结点度
树的度
叶结点
分支结点
子结点与父结点
结点层数 ；
树的深度
森林树结构相关术语,
结点 树的基本单元，包含一个数据元素及若干指向其子树的指针；
结点度 一个结点具有的子树个数；
树的度 树中最大结点的度，图示树的度为4；
叶结点 度为0的结点或终端结点，如图中C、E、K、G、H、I、L等；
分支结点 度不为0的结点或非终端结点；
子结点与父结点 如图中结点B的子结点为E、F、G、H；B父结点A；
结点层数,根结点为第一层，根的子结点为第二层，其余类推；
树的深度 树的最大层数，图示深度为4；
森林 森林是n棵互不相交树的集合。
二叉树,各结点仅有左子树和右子树的特殊树结构。
若深度为k，其结点数最多是2
k
-1个。
满二叉树：拥有2
k
-1个结点的二叉树，所有结点都有左右子树，
所有叶结点都在同一层上。
完全二叉树,深度为k，结点数为n的二叉树，从1至n每一结点编号都与满二叉树编号一致。
二叉树的存储结构顺序存储,仅适合于完全二叉树，若用于一般二叉树，
将有许多空存储单元。
链式存储：每结点除数据域外，还包含左右子树指针。
二叉树的应用举例二叉树的遍历遍历：按一定规律每一节点被访问一次。
二叉树常用遍历算法,先序遍历；中序遍历；后序遍历。
先序遍历,先访问根结点，然后先序遍历左子树，再先序遍历右子树。如上图先后顺序为A→B→D→G→H→C→E→I→F。
preorder(struct btree *node)
{ if(!node) return；
printf(“%d,，node->data)；
preorder(node->lchild)；
preorder(node->rchild)；
}
inorder(struct btree *node)
{ if(!node) return；
inorder(node->lchild)；
printf(“%d,，node->data)；
inorder(node->rchild)；
}
postorder(struct btree *node)
{ if(!node) return；
postorder(node->lchild)；
postorder(node->rchild)；
printf(“%d,，node->data)；
}
中序遍历,先中序遍历左子树，然后访问根结点，再中序遍历右子树。访问顺序为G→D→H→B→A→E→I→C→F。
后序遍历,先后序遍历左子树、后序遍历右子树，再访问根结点。结点访问顺序为G→H→D→B→I→E→F→C→A。
树的二叉树表示的转换方法（一）：
①将各层兄弟结点用线连起来；
②除最左子结点外，去掉各结点与其子结点连线；
③以根为中心，将整棵树顺时针旋转45 °，最终得到所需二叉树。
(a)
(b)
(c)
树的二叉树表示的转换方法（二）：
①保留左分支，删除其它；
②第一个孩子位于结点下方，兄弟位于右。
(c)
(b)
(a)
2,熟练掌握线形表存储结构和相关操作方法；
3,掌握栈、队列、树数据结构的运算方法。
第一节 基本概念第二节 线形表第三节 栈、队列和数组第四节 树结构本章内容
《机械 CAD/CAM》课程教案教学目的第二章第二章机械机械
CAD/CAM常用的数据结构常用的数据结构第第
1 节节基本概念基本概念
1,数据，是对客观事物的符号表示，是指所有能输入到计算机内并被计算机处理的符号的总称。
2,数据元素，是数据的基本单位，是数据这个集合中相对独立的个体。
3,数据的逻辑结构，是指数据之间的逻辑关系。
4,数据的物理结构，是数据元素和它们之间的关系在计算机中的存储表示。
计算机处理信息的最小单位叫做位 (bit)，一个位表示 一 个二进制的数。
若干位的组合形成一个位串 。用一个位串表示一个数据元素，称这样的位串为一个结点。
5,数据运算，是指对数据进行的各种操作。
6,数据类型，是程序设计语言提供的变量类别。
2.1.1 数据结构的概念数据结构,是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。
数据结构非线性结构数据存储结构数据运算数据逻辑结构线性结构线性表队列栈网状结构树结构链式存储顺序存储插入，删除，更新，检索，排序第第
2 节节线形表线形表
?线性表 ——n(n≥ 0)个数据元素按前驱后继关系排成的有限序列。
9同一表中的数据元素的类型必须相同；
9除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继； 如工资表、学生名册。
9线性表中数据元素的个数定义为线性表的长度。
第第
2 节节线形表线形表
?线性表的顺序存储结构顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放 。
假定每个数据元素占用L个存储单元，每个数据元素第 1个单元的存储位置为该数据元素的存储位置，第1 个数据元素的存储化置为 b，则第i 个数据元素的存储位置为
Loc(a
i
)＝ b十 (i—1)× L
第第
2 节节线形表线形表
?线性表的顺序存储结构特点：1 ）有序性；2 ）均匀性。
操作：1 ）建表；
2）访问；
3）修改；
4）删除；
5）插入。
删除或插入运算时，数据移动量大，运算时间长。
线性表插入运算,
第第
2 节节线形表线形表
?线性表的链式存储结构特点：1 ）存储单元可以不连续、动态分配存储空间；
2）存储结点有两种域：数据域、指针域。
9单向链表
9双向链表
9循环链表第第
2 节节线形表线形表
?单向链表的操作操作：1 ）建表；
2）访问；
3）修改；
4）删除；
5）插入。
第第
2 节节线形表线形表
?建表
链表插入操作运算步骤：①申请新结点存储空间；②将待插入元素M存放在新增结点数据域；③新增结点指针链接。
第第
2 节节线形表线形表
?访问第第
2 节节线形表线形表
?查找
?修改
?删除
?插入第第
2 节节线形表线形表
?双向链表第第
2 节节线形表线形表
?双向链表的操作
1）建表第第
2 节节线形表线形表
?建表第第
2 节节线形表线形表
?查找
?修改
?删除
?插入第第
2 节节线形表线形表
?链式存储相对于顺序存储的特点：
(1)删除或插入运算速度快，因为删除或插入运算过程中数据并不移动；
(2)无需事先分配存储空间，以免有些空间不能充分利用；
(3)表的容量易于扩充；
(4)按逻辑顺序进行查找的速度慢；
(5)比相等长度的顺序存储多占用作为指针域的存储空间。
线性表顺序存储与链式存储结构比较
{ 顺序存储：
优点：结构均匀，便于数据元素访问和修改操作；
不足：删除插入大量数据元素需移动，运算效率低。
应用：多用于查找频繁、很少增删的场合。
{ 链式存储：
优点：删除插入效率高，不需数据元素移动，不需事先分配存储空间，存储空间利用充分。
不足：搜索效率低，需从头结点顺次搜寻。
应用－多用于事先难以确定容量，频繁增、删场合。
第第
3 节节栈、队列和数组栈、队列和数组
1.栈
?栈的结构
(1)栈的逻辑结构
——线形表：后进先出
(2)栈的存储结构
——一般采用顺序存储结构
?栈的运算
(1)建栈
(2)进栈
(3)出栈第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组栈（ Stack）,限定在表尾进行插入或删除操作，且为,后进先出” 的线性表。
队列（ Queue）,限定在表一端插入，在另一端删除的,先进先出” 线性表。
a
1
a
2
…
…
a
k
…
…
a
n-1
a
n
入队出队队列数据结构循环队列第第
3 节节栈、队列和数组栈、队列和数组第第
3 节节栈、队列和数组栈、队列和数组队列第第
3 节节栈、队列和数组栈、队列和数组队列第第
3 节节栈、队列和数组栈、队列和数组数组树结构（层次结构）,除根结点之外，所有结点仅有一个直接前驱。
第第
4 节节树树结结构构
结点
结点度
树的度
叶结点
分支结点
子结点与父结点
结点层数 ；
树的深度
森林树结构相关术语,
结点 树的基本单元，包含一个数据元素及若干指向其子树的指针；
结点度 一个结点具有的子树个数；
树的度 树中最大结点的度，图示树的度为4；
叶结点 度为0的结点或终端结点，如图中C、E、K、G、H、I、L等；
分支结点 度不为0的结点或非终端结点；
子结点与父结点 如图中结点B的子结点为E、F、G、H；B父结点A；
结点层数,根结点为第一层，根的子结点为第二层，其余类推；
树的深度 树的最大层数，图示深度为4；
森林 森林是n棵互不相交树的集合。
二叉树,各结点仅有左子树和右子树的特殊树结构。
若深度为k，其结点数最多是2
k
-1个。
满二叉树：拥有2
k
-1个结点的二叉树，所有结点都有左右子树，
所有叶结点都在同一层上。
完全二叉树,深度为k，结点数为n的二叉树，从1至n每一结点编号都与满二叉树编号一致。
二叉树的存储结构顺序存储,仅适合于完全二叉树，若用于一般二叉树，
将有许多空存储单元。
链式存储：每结点除数据域外，还包含左右子树指针。
二叉树的应用举例二叉树的遍历遍历：按一定规律每一节点被访问一次。
二叉树常用遍历算法,先序遍历；中序遍历；后序遍历。
先序遍历,先访问根结点，然后先序遍历左子树，再先序遍历右子树。如上图先后顺序为A→B→D→G→H→C→E→I→F。
preorder(struct btree *node)
{ if(!node) return；
printf(“%d,，node->data)；
preorder(node->lchild)；
preorder(node->rchild)；
}
inorder(struct btree *node)
{ if(!node) return；
inorder(node->lchild)；
printf(“%d,，node->data)；
inorder(node->rchild)；
}
postorder(struct btree *node)
{ if(!node) return；
postorder(node->lchild)；
postorder(node->rchild)；
printf(“%d,，node->data)；
}
中序遍历,先中序遍历左子树，然后访问根结点，再中序遍历右子树。访问顺序为G→D→H→B→A→E→I→C→F。
后序遍历,先后序遍历左子树、后序遍历右子树，再访问根结点。结点访问顺序为G→H→D→B→I→E→F→C→A。
树的二叉树表示的转换方法（一）：
①将各层兄弟结点用线连起来；
②除最左子结点外，去掉各结点与其子结点连线；
③以根为中心，将整棵树顺时针旋转45 °，最终得到所需二叉树。
(a)
(b)
(c)
树的二叉树表示的转换方法（二）：
①保留左分支，删除其它；
②第一个孩子位于结点下方，兄弟位于右。
(c)
(b)
(a)
