基础数据结构

太过爱你忘了你带给我的痛 2022-06-06 00:48 201阅读 0赞

# 数组 #

## 解决素数问题： ##

很久以前，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。  
具体操作：先将 2~n 的各个数放入表中，然后在2（第一个素数）的上面画一个圆圈，然后划去2（这是合数了）的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。  
![这里写图片描述][SouthEast]

#define N 10000
    int main(void)
    {
        int i , j , a[N];
        for(i = 2 ; i < N ; i++){
       //第一次遍历初始化
            a[i] = 1;
        }
        for(i = 2 ; i< N ; i++){
       //第二次遍历，处理
            if(a[i]){
       //素数从2开始，接着依次判断
                for(j = i ; j*i < N ; j++)//将素数倍数全部设置为0，是非素数。
                    a[i*j] = 0;
            }
        }
        for(i = 2; i<N ; i++){
       //第三次遍历判断
            if(a[i])
                printf("%5d" , i);
        }
        printf("\n");
    }

![这里写图片描述][SouthEast 1]

2、硬币抛掷模拟

# 链表 #

> 当主要任务是按顺序逐个遍历一个项的集合，那么很适合把这些项目组合成链表。链表提供了重新排列项的能力。  
> 链表最后节点约定：指向NULL；不包含任何的哑节点；反过来指向第一个节点，构成循环链表。

//删除节点t的下一个节点
    t->next = t->next->next;//删除中间
    free(t->next);//必须释放
    
    //节点t后面插入x
    x->next = t->next;
    t->next = x;

## 循环列例子（约瑟夫问题） ##

> 假如N个人决定选出一个领导，将所有人排成一个圆周，沿着这个圆周每次数M个人就排除对应者，每当有人出列后，剩下的人靠拢，仍然保持一个完整的圆周。问题就是找出最后剩下的那个人是谁，确定领导的过程是一个N和M的函数，这就是的所谓的约瑟夫函数。 更一般地讲，我们可能希望知道出列人员的顺序。若N=9且M=5则出列顺序为5 1 7 4 3 6 9 2，8为选出的领导。

struct node{
        int item;
        struct node * next;
    };
    typedef struct node* link;
    int main(int argc  , char **argv)
    {
        if(argc != 3)
            exit(0);
        int i;
        int N = atoi(argv[1]);//总人数
        int M = atoi(argv[2]);//每次间隔数的个数
        link temp ;
        link x = (link)malloc(sizeof(struct node));//分配首节点
        x->item = 1;
        x->next = x;//循环
        temp = x;//记录首节点供后面使用
        for(i = 2 ; i <= N ; i++){
       //构建链表
          temp->next = (link)malloc(sizeof(struct node));//分配节点链接在尾部
          temp = temp->next;//记录当前节点地址
          temp->item = i;//当前节点赋值
          temp->next = x;//当前节点指向首节点
        }
        while(x != x->next){
            for(i = 1 ; i < M-1 ; i++)//找出需要移除的人，上一个人的地址
                x = x->next;
    
            temp = x->next;
            x->next = temp->next;
            printf("%3d " , temp->item);//打印踢出去的人
            free(temp);//释放删除元素的内存
            x = x->next;//重新从删除下一个人开始
        }
        printf("\n");
        printf("%3d\n" , x->item);//输出结果
        exit(0);
    }

注意课本这个上面代码有点小问题。  
![这里写图片描述][SouthEast 2]

## 表倒置 ##

link reverse(link x)//表倒置，返回尾部
    {
        link y = x;
        link temp = NULL;//保存上一个节点地址
        link t;
        while(y != NULL){
            t = y->next;//保存下一个节点
            y->next = temp;
            temp = y;//保存当前节点
            y = t;//更新y
        }
        return temp;//返回最后一个节点
    }
    int main(void)
    {
        link x = (link)malloc(sizeof(struct node));//分配首节点
        x->item = 1;
        x->next = NULL;
        link temp = x;
        for(int i =2 ; i < 20 ; i++){
            link newnode = (link)malloc(sizeof(struct node));//分配
            newnode->item = i;//分配初始化值
            newnode->next = temp->next;
            temp->next = newnode;//插入链表
            temp = temp->next;
        }
        temp = x;
        while(temp != NULL){
            printf("%d " , temp->item);
            temp = temp->next;
        }
        printf("\n");
        temp = reverse(x);
        while(temp != NULL){
            printf("%d " , temp->item);
            temp = temp->next;
        }
        printf("\n");
    }

![这里写图片描述][SouthEast 3]

# 树 #

## 树相关的概念 ##

> 对于大量的输入数据，链表的线性访问时间太长了，不宜使用，那么就需要一种多分支的访问情况，这个就是树。通过在节点里面增加链接个数，减少访问次数。树是各种算法实现的基础，很多算法都是以树作为基础的。给树再添加一些规则进行操作，从而实现高效的算法。
> 
> 树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
> 
>  *  父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
>  *  子节点：一个节点含有的子树的根节点称为该节点为子节点
>  *  叶节点：没有儿子的节点。
>  *  兄弟节点：具有相同父亲的节点。
>  *  节点的度：一个节点含有的子树的个数称为该节点的度，叶节点度为0。
>  *  树的度：一棵树中，最大的节点的度称为树的度。
>  *  节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
>  *  树的高度：树中节点的最大层次。

## 树的实现 ##

> 每一个节点除了数据外还有一些链接其他的指针。

## 树的遍历 ##

> 树的遍历全部通过递归实现。  
> \- 前根序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。  
> \- 中根序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。  
> \- 后根序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

/* * 前序遍历伪代码 */
    static void preorder(RBTree tree)
    {
         if(tree != NULL)
         {
             printf("%d ", tree->key);
             preorder(tree->left);
             preorder(tree->right);
         }
    }
    
     /* * 中序遍历伪代码 */
    static void inorder(RBTree tree)
    {
         if(tree != NULL)
         {
             inorder(tree->left);
             printf("%d ", tree->key);
             inorder(tree->right);
         }
    }
    
    /* * 后序遍历伪代码 */
     static void postorder(RBTree tree)
     {
         if(tree != NULL)
         {
             postorder(tree->left);
             postorder(tree->right);
             printf("%d ", tree->key);
         }
     }

![这里写图片描述][SouthEast 4]

## 二叉树 ##

> 每个节点都不能有多余两个儿子的树。在查找里面有用到

## 二叉搜索树 ##

> 对于节点X，其左子树的项值小于X里面项值，右子树的项值大于X里面项值。所有元素都可以通过某种方式排列，因此在查找里面广泛用到。  
> 实现见[链接][Link 1]。

## 2-3树 ##

> 一种树的概念，但是实现通过红黑树。

## 红黑树 ##

> 是实现2-3树的一种具体方式，查找里面有用到。  
> 实现见链接。

## B树 ##

[SouthEast]: /images/20220606/51727f6c0be04665aa947f8a8e128b45.png
[SouthEast 1]: /images/20220606/04d4f771447a4511ad5370a1480573cd.png
[SouthEast 2]: /images/20220606/2cb6252fc6584dc4acbcd781140f435f.png
[SouthEast 3]: /images/20220606/bcc0f7f9fe1a4f90bda9dca598c87ee8.png
[SouthEast 4]: /images/20220606/2557d3c2a43f4a1ab4878116a48c49c9.png
[Link 1]: http://blog.csdn.net/u010710458/article/details/78492890#t3