maxn在手机数据线里面的结构结构里面叫什么

来源：蜘蛛抓取(WebSpider) 时间：2016-03-27 13:12 标签： 3d max 核壳结构
浙江大学远程教育2015数据结构与算法离线作业答案_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
浙江大学远程教育2015数据结构与算法离线作业答案
上传于||文档简介
&&浙​江​大​学​远​程​教​育05​数​据​结​构​与​算​法​离​线​作​业​答​案
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩50页未读，继续阅读
你可能喜欢数据结构 图_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构 图
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩38页未读，继续阅读
你可能喜欢2478人阅读
算法（35）
不相交集合数据结构的概念和操作：
& & 不相交集合数据结构（disjoing-set data structure)保持一组不相交的动态集合S={S1，S2，S3，……Sk}。每个集合通过一个代表来识别，代表即集合中的某个成员。
我们希望不相交集合数据结构支持如下操作：
1 . MAKE_SET(x)： 建立一个新的集合，其唯一成员就是x，所以其代表也就是自己。因为各集合是不相交的，故要求x没有在其他集合中出现过。
2 . UNION(x，y)： 将包含x和y的动态集合（比如说Sx和Sy）合并为一个新的集合（即这两个集合的并集）。假定这个操作之前是不相交的。在经过此操作后，所得集合的代表可以是Sx U Sy中的任何一个成员，但在UNION的很多实现细节中，都选择Sx或Sy的代表作为新的代表。由于要求各集合是不相交的，故我们“消除”集合Sx和Sy，把它们从S中删去。
3 . FIND_SET(x)：返回一个指针，指向包含x的（唯一）集合的代表。
不相交数据集合一般用链表或森林（有根树，如下图）来实现，有根树的速度更快。用有根树来表示集合，树中的每个节点都包含集合的一个成员，每棵树都表示一个集合。从下图中可知，不相交森林中，每个成员仅指向其父节点。每个树的根包含了代表，并且是它自己的父节点。尽管采用了这种表示的直观算法并不比采用链表表示的直观算法并不比采用链表表示的算法更快，但是，通过引入两种启发式策略（“按秩合并”和“路径压缩”），就可以获得目前已知的，渐进意义上最快的不相交集合的数据结构。
改进运行时间的启发式策略：
1.按秩合并，其思想是是5包含较少节点的树的根指向包含较多节点的树的根。我们并不显示的记录以每个节点为根的子树大小，而是采用了一种能够简化分析的方法。对每个节点，用秩表示节点高度的一个上届。在按秩合并中具有较小秩的根在UNION操作中要指向具有较大秩的根。
2.路径压缩，它非常简单而有效。如下图所示，在FIND_SET操作中，利用这种启发式策略，来使查找路径上的每个节点都直接指向根节点。路径压缩并不改变节点的秩。
不相交集合森林的伪代码：
带路径压缩的FIND_SET过程也是相当简单的：
过程FIND_SET是一种两趟方法，也就是说它干了两件事：
1.沿着路径上升，找到代表。
2.修改路径上的元素的p域，使其指向代表。
代码示例：
#include &stdio.h&
const int MAXN = 100;
int pa[MAXN];
int rank[MAXN];
void make_set(int x)
{//create a set
rand[x] = 0;
int find_set( int x)
{/*带压缩路径的查找 */
if( x != pa[x] )
pa[x] = find_set(pa[x]);
return pa[x];
void link( int x, int y)
if( rank[x] & rank[y])
if( rank[x] == rank[y])
rank[y]++;
void union_set(int x, int y)
link(find_set(x),find_set(y));
不相交集合数据结构的一个应用：
& & 不相交集合数据结构有多种应用，其中之一是用于确定一个无向图中连通子图的个数。在下面给出的过程CONNECTED_COMPONENTS中，利用了不相交集合操作来计算一个图的连通子图。一旦CONNECTED_COMPONENTS作为预处理步骤执行后，过程SAME_COMPONENT回答两个顶点是否在同一连通子图的查询。
SAME_COMPONENT(u, v)
1 &if FIND_SET(u) = FIND_SET(v)
2 & & & &then return TRUE
3 & & & &else return FALSE
代码示例：
#include &stdio.h&
#include &string.h&
#include &iostream&
const int MAXN = 100;
const int NODE_NUM = 10;
int pa[MAXN];
int rank[MAXN];
void make_set(int x)
{//create a set
rank[x] = 0;
int find_set( int x)
{/*带压缩路径的查找 */
if( x != pa[x] )
pa[x] = find_set(pa[x]);
return pa[x];
void link( int x, int y)
if( rank[x] & rank[y])
if( rank[x] == rank[y])
rank[y]++;
void union_set(int x, int y)
link(find_set(x),find_set(y));
bool same_components( int u, int v)
if( find_set(u) == find_set(v))
int connected_components(const int node,const
int adj[][NODE_NUM])
int i = 0;
int j = 0;
int count = 0;
for( i = 0; i & i++)
make_set(i);
for( i = 0; i & i++)
for( j = i + 1; j & j++ )
if( adj[i][j] != 0 && find_set(i) != find_set(j) )
union_set(i, j);
int *p = new int[node];
memset(p, 0, sizeof(int) * node );
for( i = 0; i & i++)
for( j = 0; j & j++)
if( find_set(i) == find_set(p[j]))
if( j &= count )
p[count++] =
int main(int argc, char* argv[])
const int adj[NODE_NUM][NODE_NUM] = {
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
cout && &连通子图的个数：& && connected_components( NODE_NUM, adj) &&
参考资料：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：457696次
积分：5939
积分：5939
排名：第2454名
原创：135篇
转载：35篇
评论：100条
本博客乃学习笔记，没有纯粹无意义的转载。作者除了对自己负责，不对任何读者负责。欢迎指出文章错误，如果原意交朋友，可以通过Gmail联系我（），博客基本不再更新，欢迎访问我的独立博客
(5)(2)(1)(1)(14)(22)(11)(48)(30)(17)(22)(4) 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
数据结构-图-练习题（附答案）
下载积分：739
内容提示：数据结构-图-练习题（附答案）
文档格式：DOC|
浏览次数：124|
上传日期： 11:45:33|
文档星级：
该用户还上传了这些文档
数据结构-图-练习题（附答案）
官方公共微信

我要回帖

更多关于 3d max 核壳结构 的文章

 

随机推荐