基本数据结构

2019-05-28  本文已影响0人  宙斯YY

一.图
二.树

一.图

1.图的遍历：

通过深度优先遍历DFS和广度优先遍历BFS两种方式。
深度优先遍历
0 1 2 3 4 5 6 7 8


1.png 
/*图深度遍历*/
-(void)graph_DFS
{
    int point[9]={0,1,2,3,4,5,6,7,8};
    int path[9][9]={
        {0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,MaxPath,MaxPath},
        {1,0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,1},
        {MaxPath,1,0,1,MaxPath,MaxPath,MaxPath,MaxPath,1},
        {MaxPath,MaxPath,1,0,1,MaxPath,1,1,1},
        {MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,1,MaxPath},
        {1,MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,MaxPath},
        {MaxPath,1,MaxPath,1,MaxPath,1,0,1,MaxPath},
        {MaxPath,MaxPath,MaxPath,1,1,MaxPath,1,0,MaxPath},
        {MaxPath,1,1,1,MaxPath,MaxPath,MaxPath,MaxPath,0},
    };
    
    BOOL visited[9]={FALSE};
    visited[0]=TRUE;
    printf("%d ",point[0]);
    [self dfs:point andPath:path andvisited:visited andIndex:0];
    
}
/*
 用visited[]记录找过的点；从开始节点，不断向一边找，直到访问到记录过的点，那么回退到上个节点继续。
 类似树的中序遍历
 */
-(void)dfs:(int[])point andPath:(int[9][9])path andvisited:(BOOL[])visited andIndex:(int)index
{
    for(int i=0;i<9;i++)
    {
        if(path[index][i]==1&&!visited[i])
        {
            visited[i]=TRUE;
            printf("%d ",point[i]);
            [self dfs:point andPath:path andvisited:visited andIndex:i];
        }
    }
}

广度优先遍历
0 1 5 2 6 8 4 3 7


2.png 
/*
 图广度遍历
 借助一个队列保存访问过的节点，类似树的层序遍历
 */
-(void)graph_BFS
{
    int point[9]={0,1,2,3,4,5,6,7,8};
    int path[9][9]={
        {0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,MaxPath,MaxPath},
        {1,0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,1},
        {MaxPath,1,0,1,MaxPath,MaxPath,MaxPath,MaxPath,1},
        {MaxPath,MaxPath,1,0,1,MaxPath,1,1,1},
        {MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,1,MaxPath},
        {1,MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,MaxPath},
        {MaxPath,1,MaxPath,1,MaxPath,1,0,1,MaxPath},
        {MaxPath,MaxPath,MaxPath,1,1,MaxPath,1,0,MaxPath},
        {MaxPath,1,1,1,MaxPath,MaxPath,MaxPath,MaxPath,0},
    };
    BOOL visited[9]={FALSE};
    NSMutableArray * queue=[NSMutableArray array];
    for (int i=0;i<9;i++) {
        if(!visited[i])
        {
            visited[i]=TRUE;
            [queue addObject:[NSNumber numberWithInt:i]];
            while(queue.count>0)
            {
                int index=[queue.firstObject intValue];
                printf("%d ",point[index]);
                for (int j=0;j<9;j++) {
                    if(path[index][j]==1&&!visited[j])
                    {
                        visited[j]=TRUE;
                        [queue addObject:[NSNumber numberWithInt:j]];
                    }
                }
                [queue removeObjectAtIndex:0];
            }
        }
    }
}

二.树

1.特殊的二叉树结构
2.二叉树的性质
3.二叉树的遍历
-(TreeNode*)buildTree
{
    TreeNode * node1=[[TreeNode alloc]initWithData:37 andLeft:nil andRight:nil];
    TreeNode * node2=[[TreeNode alloc]initWithData:35 andLeft:nil andRight:node1];
    TreeNode * node3=[[TreeNode alloc]initWithData:51 andLeft:nil andRight:nil];
    TreeNode * node4=[[TreeNode alloc]initWithData:47 andLeft:node2 andRight:node3];
    TreeNode * node5=[[TreeNode alloc]initWithData:58 andLeft:node4 andRight:nil];
    TreeNode * node6=[[TreeNode alloc]initWithData:93 andLeft:nil andRight:nil];
    TreeNode * node7=[[TreeNode alloc]initWithData:99 andLeft:node6 andRight:nil];
    TreeNode * node8=[[TreeNode alloc]initWithData:73 andLeft:nil andRight:nil];
    TreeNode * node9=[[TreeNode alloc]initWithData:88 andLeft:node8 andRight:node7];
    TreeNode * tree=[[TreeNode alloc]initWithData:62 andLeft:node5 andRight:node9];
    return tree;
}

/*二叉查找树前序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    printf("%d ",tree.data);
    [self traverseTree:tree.leftNode];
    [self traverseTree:tree.rightNode];
}

/*二叉查找树中序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    [self traverseTree:tree.leftNode];
    printf("%d ",tree.data);
    [self traverseTree:tree.rightNode];
}

二叉查找树的中序遍历就是让数据顺序排列的过程。

/*二叉查找树后序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    [self traverseTree:tree.leftNode];
    [self traverseTree:tree.rightNode];
    printf("%d ",tree.data);
}
4.线索二叉树
5.树转换成二叉树

树：


1.png

步骤1.给兄弟加线：


2.png
步骤2.给除长子外的孩子去线：
3.png

步骤3.层次调整


4.png
6.霍夫曼树和霍夫曼编码

所以这颗树霍夫曼树，最短带权路径是205。

一般地，设需要编码的字符集为{d1,d2,...dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,...wn}，以d1,d2...dn作为叶子节点，以w1,w2,...wn作为相应叶子节点的权值来构造一颗霍夫曼树。规定霍夫曼树的左分支代表0，右分支代表1，则从根节点到叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，这就是霍夫曼编码。

上一篇 下一篇

猜你喜欢

热点阅读