精华内容
下载资源
问答
  • 数据结构学习路线

    千次阅读 2019-10-24 10:32:01
    Treap Splay树 划分树 左偏树 线段树 树链剖分 动态树 主席树 Trie树 RMQ 二分查找 树状数组 滚动数组 逆序数 带权值的并查集 Chtholly Tree (珂朵莉树) ODT SBT算法 AVL树 ......
    1. Treap
    2. Splay树
    3. 划分树
    4. 左偏树
    5. 线段树
    6. 树链剖分
    7. 动态树
    8. 主席树
    9. Trie树
    10. RMQ
    11. 二分查找
    12. 树状数组
    13. 滚动数组
    14. 逆序数
    15. 带权值的并查集
    16. Chtholly Tree (珂朵莉树) ODT
    17. SBT算法
    18. AVL树
    19. 替罪羊树
    20. 莫队算法
    展开全文
  • 数据结构学习路线+笔记

    千次阅读 多人点赞 2016-03-22 17:14:24
    在学校学习过后感觉数据结构学完之后还是迷迷糊糊的,而数据结构已经有很多位前辈说过其重要性,于是下决心再来一遍“复习”。代码会陆续贴上来,轻喷,都是些简单的基础知识。 ————学习来源为郝斌老师的视频 ...

    在学校学习过后感觉数据结构学完之后还是迷迷糊糊的,而数据结构已经有很多位前辈说过其重要性,于是下决心再来一遍“复习”。代码会陆续贴上来,轻喷,都是些简单的基础知识。

    ————学习来源为郝斌老师的视频

    数据结构:数据结构是研究数据存储的问题(狭义)数据结构既包含数据的存储,也包含对存储数据的操作即算法(广义)

    数据存储包含两个方面: 个体的存储 + 个体关系的存储。

     

    算法:

    狭义的算法是与数据的存储方式密切相关的

    广义的算法是与数据的存储方式无关,

    泛型:利用某种技术达到的效果就是不同的存储方式执行操作是一样的。

     

    数据的存储结构:线性和非线性

     

    线性结构:任何一个节点只能对应一个节点,即所有节点都由一根“线”连接。

    连续存储【数组】

    优点:存取速度快,

    缺点:必须先知道数组长度,插入删除元素操作速度慢,空间通常是有限制的,需要极大的连续内存块。

     

    离散存储【链表】

    定义:N个节点离散分配,彼此通过指针指向下一个节点,每个节点只有一个前驱节点和一个后继节点,首节点没有前驱,尾节点没有后继节点。

     

    优点:插入删除速度快,空间没有限制(容量)

    缺点:存取速度慢

     

    专业术语:

    首节点

    尾节点

    头节点:在首节点(有效节点)的前面添加的节点为头节点,其没有实际含义,没有有效数据,其存在的意义是简便对链表的操作(算法)。

    头指针:指向头节点的指针变量,存放头节点的指针地址

    尾指针:指向尾节点的指针

    如果希望通过函数来对一个链表进行处理,我们至少需要接收一个参数:头指针,通过头指针可以推算出链表的所有信息

     

    分类:

    单链表:每个节点只有一个指针域,指向下一个节点

    双链表:每一个节点有两个指针域,分别指向前驱和后继

    循环链表:任何一个节点都可以找到其他所有节点,最后一个节点指向第一个指针域。

    非循环链表

     

    相关算法:

    遍历:

    查找:

    清空:

    销毁:

    求长度:

    排序:

    删除节点:

    插入节点:

     

    
    #define _CRT_SECURE_NO_DEPRECATE
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    
    typedef struct Node
    {
        int data;
        struct Node * pNext;
    }NODE, *PNODE;
    
    
    
    
    PNODE create_list(void);//创建一个单链表
    void traverse_list(PNODE pHead);//遍历一个链表
    bool is_empty(PNODE pHead);
    int getLength_lsit(PNODE pHead);
    bool insert_list(PNODE pHead, int pos, int value);
    bool delete_list(PNODE pHead, int pos, int *pValue);
    void sort_list(PNODE pHead);
    
    
    int main()
    {
        PNODE pHead = NULL;
        pHead = create_list();
        getchar();
        traverse_list(pHead);
        int len = getLength_lsit(pHead);
        printf("长度:%d\n", len);
    
    
        sort_list(pHead);
        traverse_list(pHead);
        system("pause");
        return 0;
    }
    
    
    PNODE create_list(void)
    {
        int len;//有效节点个数
        int i;
        int value;//临时数据
    
    
        //不存放有效数据的头节点
        PNODE pHead = (PNODE)malloc(sizeof(NODE)); //为生成的节点动态分配内存
        if (NULL == pHead)
        {
            printf("节点生成失败,程序终止!");
            exit(-1);
        }
        PNODE pTail = pHead;
        pTail->pNext = NULL;//清空,指向最后一个节点
    
    
        printf("输入有效节点个数len:");
        scanf("%d", &len);
    
    
        for (i = 0; i < len; i++)
        {
            printf("请输入第%d个几点值:",i+1);
            scanf("%d", &value);
    
    
            PNODE pNew = (PNODE)malloc(sizeof(NODE));
            if (NULL == pNew)
                {
                    printf("节点生成失败,程序终止!");
                    exit(-1);
                }
            pNew->data = value;
            pTail->pNext = pNew;
            pNew->pNext = NULL;//最后一个节点的指针域为空
            pTail = pNew;
        }
    return pHead;
    
    }
    
    
    void traverse_list(PNODE pHead)
    {
    
        PNODE p = pHead->pNext;
        while (NULL != p)
        {
            printf("%d ",p->data);
            p = p->pNext;
        }
        printf("\n");
        return;
    }
    
    
    bool is_empty(PNODE pHead)
    {
        if (pHead->pNext == NULL)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    
    int getLength_lsit(PNODE pHead)
    {
        int cnt = 0;
        PNODE p = pHead->pNext;
        while (NULL != p)
        {
            ++cnt;
            p = p->pNext;
        }
        return cnt;
    }
    
    
    void sort_list(PNODE pHead) //冒排
    {
        int i, j, t;
        int len = getLength_lsit(pHead);
        PNODE p, q;
        for (i=0, p = pHead->pNext; i<len-1; i++,p = p->pNext)
        {
            for (j=i+1, q = p->pNext; j<len; j++,q=q->pNext)
            {
                if (p->data > q->data)
                {
                    t = p->data;
                    p->data = q->data;
                    q->data = t;
                }
            }
        }
    return;
    }
    
    
    //在pHead所指向链表的第pos节点的前面插入一个新节点,pos从1开始
    bool insert_list(PNODE pHead, int pos, int value)
    {
        int i = 0;
        PNODE p = pHead;
    
    
        while (NULL != p && i < pos - 1)
        {
            p = p->pNext;
            ++i;
        }
    
    
        if (i>pos - 1 || NULL == p )
        {
            return false;
        }
    
    
        PNODE pNew = (PNODE)malloc(sizeof(NODE));//开辟空间
        if (NULL == pNew)
        {
            printf("动态分配内存失败!");
            exit(-1);
        }
        pNew->data = value;
        PNODE q = p->pNext;
        p->pNext = pNew;
        pNew->pNext = q;
    
    
        return true;
    }
    
    
    bool delete_list(PNODE pHead, int pos, int *pValue)
    {
        int i = 0;
        PNODE p = pHead;
    
    
        while (NULL != p->pNext && i < pos - 1)
        {
            p = p->pNext;
            ++i;
        }
    
    
        if (i>pos - 1 || NULL == p->pNext)
        {
            return false;
        }
    
    
    
    
        PNODE q = p->pNext;
        *pValue = q->data; //删除前把当前值保存
        p->pNext = p->pNext->pNext;
        free(q);
        q = NULL;
    
    
        return true;
    }
    
    
    

     

    静态分配内存处于栈中, 动态分配内存处于堆中

     

     

    头:Top       尾:Bottom

    线性结构的应用--栈

    定义:一种可以实现先进后出的存储结构。

     

    分类:

    静态栈

    动态栈

     

    算法:出栈,压栈(入栈)

     

    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    
    typedef struct Node
    {
        int data;
        struct Node * pNext;
    }NODE, *PNODE;
    
    typedef struct Stack
    {
        PNODE pTop;
        PNODE pBottom;
    }STACK, *PSTACK;
    
    void init(PSTACK pSTACK);//初始化栈
    void push(PSTACK pSTACK, int value);
    void traverse(PSTACK pSTACK);
    bool pop(PSTACK pSTACK, int *pTemp);
    void clear(PSTACK pSTACK);
    
    int main(void)
    {
        int temp;
        STACK S;
        init(&S); //初始化一个栈,空栈
        push(&S, 100);//压栈
        push(&S, 200);
        push(&S, 300);
        push(&S, 400);
        push(&S, 500);
        traverse(&S);//遍历输出
    
        if (pop(&S, &temp))
        {
            printf("出栈成功,元素是:%d\n",temp);
        }
        else
        {
            printf("出栈失败");
        }
    
        traverse(&S);
        clear(&S);
        printf("清空后:");
        traverse(&S);
    
        system("pause");
    
    
        return 0;
    }
    
    void init(PSTACK pSTACK)
    {
        pSTACK->pTop = (PNODE)malloc(sizeof(NODE));
        if (NULL == pSTACK->pTop)
        {
            printf("动态内存分配失败");
            exit(-1);
        }
        else
        {
            pSTACK->pBottom = pSTACK->pTop;
            pSTACK->pTop->pNext = NULL;
        }
    
    }
    
    
    void push(PSTACK pSTACK, int value)
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->data = value;
        pNew->pNext = pSTACK->pTop;
        pSTACK->pTop = pNew;
    
    
        return;
    }
    
    
    void traverse(PSTACK pSTACK)
    {
        PNODE p = pSTACK->pTop;
    
    
        while (p != pSTACK->pBottom)
        {
            printf(" %d", p->data);
            p = p->pNext;
        }
        printf("\n");
        return;
    }
    
    
    bool empty(PSTACK pSTACK) //判断栈是否为空
    {
        if (pSTACK->pTop == pSTACK->pBottom)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    
    //将pStack栈执行一次出栈,并把出栈的值存入形参pTemp所指向的变量中,成功true,失败false
    bool pop(PSTACK pSTACK, int *pTemp)
    {
        if (empty(pSTACK))  //pSTACK本身存放的就是S的地址
        {
            return false;
        }
        else
        {
            PNODE r = pSTACK->pTop;
            *pTemp = r->data;
            pSTACK->pTop = r->pNext;
            free(r);
            r = NULL;
    
    
            return true;
        }
    }
    
    
    void clear(PSTACK pSTACK)  //清空
    {
        if (empty(pSTACK))
        {
            printf("栈已空");
        }
        else
        {
            PNODE p = pSTACK->pTop;
            PNODE q = NULL;
            while (p != pSTACK->pBottom)
            {
                q = p->pNext;
                free(p);
                p = q;
            }
        pSTACK->pTop = pSTACK->pBottom;
    
        }
    }


     

     

    应用:

    函数调用

    中断

    表达式求值(通过两个栈求值,一个栈存放值,一个栈存放运算符)

    内存分配

    缓冲处理

    迷宫

     

    线性结构的应用--队列

    定义:一种可以实现“先进先出”的存储结构

     

    头:front        尾:rear

     

    分类:

    链式队列(链表实现的队列)

    静态队列(数组实现的队列)

    静态队列通常必须是循环队列

     

    循环队列:

    1、静态队列为什么必须是循环队列

    防止指针溢出,在队列中,无论是添加还是删除元素,front指针和rear指针都是向上加一位,所以设置循环,在指针达到峰值后循环到最低位继续加。

     

    2、循环队列需要几个参数来确定及其含义

        需要两个参数来确定,两个参数在不同场合有不同的定义

        分别是front和rear

     

    3、循环队列各个参数的含义

        1)初始化

            front和rear的值都是零

        2)队列非空

            front代表队列的第一个元素,rear代表队列的最后一个有效元素的下一个元素

        3)队列空

            front和rear的值相等,但不一定为零

     

    4、循环队列入队伪算法

        1)将值存入rear指向的位置

        2)rear指针不能直接加一(后移),应该写成rear = (r+1)%数组长度

     

    5、循环队列出队伪算法

        1)front = (front+1)%数组长度

        2)(原front指向的值可以存,也可以不存)

     

    6、如何判断循环队列是否为空

        两个参数值相等时,队列为空,即front = rear

     

    7、如何判断循环队列已满

        front和rear的值是不确定的,大小关系也是不确定的,毫无规律可循。

        

        两种方式:1、多增加一个标志位参数(此方式相对麻烦,每次都需要更改参数)

                          2、少用一个元素,如果front和rear相邻,则队列已满

        通常使用第二种方式 (伪算法表示)

            if (   (r+1) %数组长度 == f   )

                队列满

            else

                队列不满

     

     

     

    算法:出队、入队

    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    
    typedef struct Queue //队列的结构体
    {
        int *pBase;
        int front;
        int rear;
    }QUEUE;
    
    
    void init(QUEUE *pQ);
    bool en_queue(QUEUE *pQ, int value);
    void traverse_queue(QUEUE *pQ);
    bool full_queue(QUEUE *pQ);
    bool out_queue(QUEUE *pQ, int *pValue);
    bool empty_queue(QUEUE *pQ);
    
    
    int main(void)
    {
        QUEUE Q;
        int value;
    
    
        init(&Q);
        en_queue(&Q, 1);
        en_queue(&Q, 2);
        en_queue(&Q, 3);
        en_queue(&Q, 4);
        en_queue(&Q, 5);
        en_queue(&Q, 6);
    
    
        traverse_queue(&Q);
    
    
        if (out_queue(&Q, &value))
        {
            printf("出队成功,元素:%d\n",value);
        }
        else
        {
            printf("出队失败");
        }
        traverse_queue(&Q);
    
    
        system("pause");
        return 0;
    }
    
    
    /*
    初始化队列
    front和rear都初始化为0,初始化数据域
    */
    void init(QUEUE *pQ) 
    {
        pQ->pBase = (int *)malloc(sizeof(int) * 6);
        pQ->front = 0;
        pQ->rear = 0;
    }
    
    
    /*
    入队
    */
    bool en_queue(QUEUE *pQ, int value)
    {
        if (full_queue(pQ))
        {
            return false;
        }
        else
        {
            pQ->pBase[pQ->rear] = value;//将值存入队列顶部即rear所指向的地方
            pQ->rear = (pQ->rear + 1) % 6; //rear向后移位(循环队列)
            return true;
        }
    }
    
    
    
    
    
    
    bool full_queue(QUEUE *pQ)
    {
        if ((pQ->rear + 1) % 6 == pQ->front)
        return true;
        else
        return false;
    }
    
    
    void traverse_queue(QUEUE *pQ)
    {
        int i = pQ->front;
        while (i != pQ->rear)
        {
            printf("%d ",pQ->pBase[i]);
            i = (i + 1) % 6;
        }
        printf("\n");
    
    
        return;
    }
    
    
    bool empty_queue(QUEUE *pQ)
    {
        if (pQ->front == pQ->rear)
        return true;
        else
        return false;
    }
    
    
    bool out_queue(QUEUE *pQ, int *pValue)
    {
        if (empty_queue(pQ))
        {
            return false;
        }
        else
        {
            *pValue = pQ->pBase[pQ->front];
            pQ->front = (pQ->front + 1) % 6;
            return true;
        }
    }

     

     

    队列的应用----所有和时间有关的操作都与队列有关

     

     

    专题:递归

    定义:一个函数自己直接或间接调用自己

     

    递归要满足的三个条件:

    1、递归必须有一个明确的终止条件

    2、该函数处理的数据规模必须在递减

    3、这个转化必须是可解的

     

    举例:

    1、求阶乘

    2、1+2+。。。+100的和

    3、汉诺塔

    4、走迷宫

     

    循环和递归

            所有的循环都可以用递归实现,但是所有的递归不一定能用循环实现。

     

        递归:

               易于理解,

                速度慢,存储空间大

     

        循环:

                不易理解

                速度快,存储空间小

     

     

    当一个函数的运行期间调用另一个函数时,在运行被调函数之前,系统需要完成三件事:

    1、将所有的实际参数,返回地址等信息传递给被调函数保存。

    2、为被调函数的局部变量(也包括形参)分配存储空间。

    3、将控制转移到被调函数入口。

     

    从被调函数返回主函数之前,系统需要完成三件事:

    1、保存被调函数的返回结果

    2、释放被调函数所占存储空间

    3、依照被调函数保存的返回地址将控制转移到调用函数

     

    当有多个函数相互调用时,按照“后调用先返回”的原则,上述函数之间信息传递和控制转移必须借助“栈”来实现,即系统将整个程序运行时所需的数据控件安排在一个栈中,每当调用一个函数时,就在栈顶分配一个存储区,进行压栈操作,每当一个函数退出时,就释放他的存储区,进行出栈操作,当前运行的函数永远在栈顶位置。

     

    汉诺塔

    if(n>1)

    {

        先把A柱子上的前n-1个盘子从A借助C移到B

        将A柱子上的第n个盘子直接移到C

        再将B柱子上的n-1个盘子借助A移到C

    }

     

    #include <stdio.h>
    #include <stdlib.h>
    void hanor(int n, char x, char y, char z);
    int main(void)
    {
        char ch1 = 'A'; //ABC分别代表柱子
        char ch2 = 'B';
        char ch3 = 'C';
        int n; 
        printf("请输入要移动的盘子数量");
        scanf("%d", &n);
        hanor(n,'A','B','C');
        system("pause");
        return 0;
    }
    
    /*n个盘子,从A借助B移到C*/
    void hanor(int n, char a, char b, char c)
    {
        if (1 == n)
        {
            printf("将编号为%d的盘子直接从%c柱子移到%c柱子上\n", n, a, c);
        }
        else
        {
            hanor(n - 1, a, c, b);
            printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n,a,c);
            hanor(n - 1, b, a, c);
        }
    }

     

    递归的应用:

    树和森林就是以递归的方式定义的

    树和图的很多算法都是以递归的方式来实现的

    很多数学公式就是以递归的方式定义的

     

     

    逻辑结构

        线性

            数组

            链表

                栈和队列是一种特殊的线性结构    

     

        非线性

            树

            图

     

    物理结构

      

     

    非线性结构:

        

            定义:有且只有一个根节点,有若干个互不相交的子树,子树本身也是一颗               树。

                       树是由节点和边组成,边就是指针域,存放着下一个节点的地址,每一个节点只有一个父节点,但可以有很多个子节点。 有一个节点没有父节点,为根节点。

     

        专业名词:节点、父节点、子节点、子孙、堂兄弟(父节点是兄弟节点)、深度(从根节点到最底层节点的层数,根节点是第一层)、叶子节点(没有子节点)、非终端节点(非叶子节点)、度(子节点个数)

     

            分类:

                    一般树:任意一个节点的子节点个数都不受限制

                    二叉树:任意一个节点的子节点个数最多有两个,且子节点的位置不可更改

                        分类:一般二叉树、满二叉树(在不增加二叉树深度的时候,节点数目饱和)、完全二叉树(满二叉树是完全二叉树的一个特例)

                    森林:N个互不相交的树的集合

     

     

            存储:

                    二叉树存储

                            连续存储(完全二叉树)

     

                            链式存储

     

     

                    一般树的存储

     

                    森林的存储

            操作:

       遍历

                    先序遍历(先访问根节点)

                            先访问根节点

                            再先序访问左子树

                            再先序访问右子树    

     

                    中序遍历(中间访问根节点)

                            中序遍历左子树

                            再访问根节点

                            再中序遍历右子树

     

                    后序遍历(最后访问根节点)

                            中序遍历左子树

                            中序遍历右子树

                            最后访问根节点

     

                    已知两种遍历求原始二叉树

                            通过先序和中序 或者 中序和后序 可以推算出原始二叉树

                            先序和后序无法还原原始二叉树    

     

            应用: 1、树是数据库中数据组织一种重要形式

                        2、操作系统子父进程的关系本身就是一棵树

                        3、面向对象语言中类的继承关系

                        4、赫夫曼树

     

    二叉树例程

    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    /*下图为本程序静态二叉树
    -----------A-------------
    ---------/---\-----------
    --------B-----C----------
    -------------/-----------
    ------------D------------
    -------------\-----------
    --------------E----------
    */
    struct BTNode
    {
        char data;
        struct BTNode *pLchild; //左右孩子节点
        struct BTNode *pRchild;
    };
    
    
    struct BTNode * CreateBTree(void);//创建节点
    void PreTraverseBTree(struct BTNode *pT);//先序遍历
    void InTraverseBTree(struct BTNode *pT);//中序遍历
    void PostTraverseBTree(struct BTNode *pT);//后序遍历
    
    
    int main(void)
    {
        struct BTNode *pT = CreateBTree();
        //printf("%c\n",pT->data);
        //PreTraverseBTree(pT);
        //InTraverseBTree(pT);
        PostTraverseBTree(pT);
    
    
    
        system("pause");
        return 0;
    }
    
    
    struct BTNode * CreateBTree(void)
    {
        struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
        struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
        struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
        struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
        struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));
    
    
        pA->data = 'A';
        pB->data = 'B';
        pC->data = 'C';
        pD->data = 'D';
        pE->data = 'E';
    
    
        pA->pLchild = pB;
        pA->pRchild = pC;
        pB->pLchild = pB->pRchild = NULL;
        pC->pLchild = pD;
        pC->pRchild = NULL;
        pD->pLchild = NULL;
        pD->pRchild = pE;
        pE->pRchild = pE->pRchild = NULL;
    
    
        return pA;
    }
    /*
    顺序:根节点->先序左子树->先序右子树
    pT->pLchild代表左子树
    pT->pRchild代表右子树
    */
    void PreTraverseBTree(struct BTNode * pT)
    {
        if (NULL != pT)
        {
            printf("%c\n", pT->data);
    
    
            if (NULL != pT->pLchild)
            {
                PreTraverseBTree(pT->pLchild);
            }
            if (NULL != pT->pRchild)
            {
                PreTraverseBTree(pT->pRchild);
            }
        }
    
    }
    
    //顺序:先序左子树->根节点->先序右子树
    void InTraverseBTree(struct BTNode *pT)
    {
        if (NULL != pT)
        {
    
    
            if (NULL != pT->pLchild)
            {
                InTraverseBTree(pT->pLchild);
            }
    
    
            printf("%c\n", pT->data);
    
    
            if (NULL != pT->pRchild)
            {
                InTraverseBTree(pT->pRchild);
            }
        }
    }
    
    
    //顺序:左子树->右子树->根节点
    void PostTraverseBTree(struct BTNode *pT)
    {
        if (NULL != pT)
        {
            if (NULL != pT->pLchild)
            {
                PostTraverseBTree(pT->pLchild);
            }
            if (NULL != pT->pRchild)
            {
                PostTraverseBTree(pT->pRchild);
            }
            printf("%c\n", pT->data);
        }
    }
    
    

     

     

    查找和排序

     

    折半查找

     

    排序:

            冒泡

            插入

            选择

            快速排序

            归并排序

     

     

    快速排序例程

    排序和查找的关系:排序是查找的前提,排序是重点

    #include <stdio.h>
    #include <stdlib.h>
    
    
    void QuickSort(int * a, int low, int high);
    int FindPos(int *a, int low, int high);
    
    
    int main(void)
    {
        int a[6] = {3,6,2,7,1,4};
        int i;
        QuickSort(a,0,5);
    
    
        for (i = 0; i < 6; ++i)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
    
    
        system("pause");
    
    
        return 0;
    }
    
    
    /*
    * a:存放值
    low:第一个元素下标
    high:最后一个元素下标
    */
    void QuickSort(int * a, int low, int high)
    {
        int pos;//位置
    
    
        if (low < high)
        {
            pos = FindPos(a, low, high);
            QuickSort(a, low, pos - 1);
            QuickSort(a, pos + 1, high);
        }
    }
    
    
    //查找确定元素的位置
    int FindPos(int *a, int low, int high)
    {
        int val = a[low];
        while (low < high)
        {
            while (low < high && a[high] >= val)
            {
                --high;
            }
        a[low] = a[high];
        while (low < high && a[low] <= val)
        {
            ++low;
        }
        a[high] = a[low];
    }
    //终止while循环之后,low和high是相等的
    
    
        a[low] = val;
    
    
        return low;//返回位置信息
    }
    
    

    结论:数据结构是研究数据的存储和数据的操作的一门学问

                数据的存储分为两部分:

                        个体的存储

                        个体关系的存储

                        从某个角度而言,数据的存储最核心的就是个体关系的存储,个体存储可以忽略不计

     

     

     

    展开全文
  • http://open.163.com/newview/movie/courseintro?newurl=%2Fspecial%2Fopencourse%2Fcs50.html cs50
    http://open.163.com/newview/movie/courseintro?newurl=%2Fspecial%2Fopencourse%2Fcs50.html
    

    cs50

    展开全文
  • ,整理了一下算法的课件、书籍、论文、习题、OJ网站,总结了学习路线。 不管是准备面试,进BAT????; 还是自学算法竞赛????; 或者单纯的课外拓展????; 不管你算法能力如何,这个仓库里总有适合你的算法学习宝藏✈...

    Algorithm All in ONE🎄

    Let Everyone Study Algorithm Easier😊


    仓库在这里
    因为准备实习👔,整理了一下算法的课件、书籍、论文、习题、OJ网站,总结了学习路线。

    • 不管是准备面试,进BAT🚀;
    • 还是自学算法竞赛💼;
    • 或者单纯的课外拓展🤷;
    • 不管你算法能力如何,这个仓库里总有适合你的算法学习宝藏✈️!

    对Coder🧑‍💻而言,算法学习都是有必要的,只是不同领域可能要求深浅不同

    所以,咱们开始学起来吧🌈~

    全面收集、整理了从高中参加竞赛到现在的算法竞赛课件论文集书籍OJ网站习题,并总结了学习路线👀:

    文件很多,目录很长,所以分为文件夹目录和文件树,点击文件目录进入对应详细文件树查阅👀

    如果对你有所帮助,请 star✨ 支持一下

    出乎意料🙀进了GitHub Trending,感谢陌生的你们😊,这是对我很大的鼓励🔥

    我是个在读软件工程大二学生,一个AI选手,主攻NLP,偶尔可以做做前后端开发。

    可以follow一下我啊🌞。以后会分享相关的知识和我的研究成果,努力带来更多优质项目~


    文件导图👀

    文件夹目录👀

    👇点击进入对应详细目录🌈

    算法套件 数据结构套件 C++套件 基础算法 数据结构 动态规划 C++ 字符串 数学 计算几何 书籍 习题 论文
    🌲 🚀 🍟 🤹🏼‍♀️ ❄️ 🎮 🌈 ☂️ 🎱 🧠 🍟 ⛄️ 🎄 🍀

    Let`s Start Our Trip 🚀

    🌱🌱

    算法、数据结构、C++入门👀:

    算法入门套件🌲 || 数据结构入门套件🚀 || C++入门套件🍟

    基础算法🤹🏼‍♀️

    复杂度分析🌟 || 高精度🌟 || 暴力🌟 || 二分🌟 || 分治 🌟 || 搜索🌟 || 贪心🌟

    基础数据结构❄️

    基础数据结构💫


    🌲🌲🌲🌲

    算法进阶

    动态规划🎮 || 分块算法💫 || 计算几何🧠

    语言进阶

    C++🌈

    数据结构进阶

    🎄 || 字符串☂️ || 🛸

    数学进阶

    数学🎱


    🎄🎄🎄🎄🎄🎄

    阅读书籍📚

    算法🔥

    算法竞赛👑 || 数学之美👑 || 数据结构与算法(Java)👑 || 算法👑 || 算法模版👑

    语言🔥

    C🔥

    CPrimerPlus👑

    C++🔥

    C++PrimerPlus👑 || C++Primer👑 || Effective C++👑 || Effective STL👑

    Python🔥

    从入门到实践👑 || 流畅的Python👑 || Effective Python👑 || PythonCookbook👑

    练习题🚀

    习题⛄️

    👀 更有效的方式训练是直接在OJ上刷题


    🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄

    研究性论文集🎄

    这一阶段因人而异,多练习多刷OJ才是王道!

    1999论文集🧳 || 2000论文集🧳 || 2001论文集🧳 || 2002论文集🧳 ||2003论文集🧳

    2004论文集🧳 || 2005论文集🧳 || 2006论文集🧳 || 2007论文集🧳 || 2008论文集🧳

    2009论文集🧳 || 2013论文集🧳 || 2014论文集🧳 || 2015论文集🧳|| 2018论文集🧳

    🍀


    OJ网站汇总🚀

    🚀国内Online Judge

    🌲三大OJ🌲

    1. 🎄浙江大学 http://acm.zju.edu.cn 超过2000题,支持C/C++/Pascal/Java/Python/Perl/Scheme/PHP
    2. 🎄北京大学 http://poj.org 超过2000题,支持C/C++/Pascal/Java/Fortran
    3. 🎄哈尔滨工业大学 http://acm.hit.edu.cn 超过2000题,支持C/C++/Pascal/Java/Fortran

    🌲非常🔥的hdu🌲

    • 🎄杭州电子科技大学 http://acm.hdu.edu.cn 超过2000题,支持C/C++/Pascal/Java杭电OJ是国内最为活跃的OJ
    • 🎄每周都会举办bestcoder比赛,相当于国内的codeforce:http://bestcoder.hdu.edu.cn/

    🌲Set of OJ:vjudge🌲

    • 🎄虚拟OJ:https://vjudge.net/ 这个网站的特色就是用户可以自己举办比赛,vjudge支持数十个OJ网站,用户可以从这些OJ网站上选择题目,可以选择一些同类型题目形成一个题集。

    🚀国外Online Judge

    1. 🎄CF:CodeForce:http://codeforces.com/problemset 世界顶级OJ

      🎄CodeForce还提供了API接口:http://codeforces.com/api/help

    2. 🎄Saratov State University http://acm.sgu.ru 超过400题,支持C/C++/C#/Java/Delphi

    3. 🎄UVA:University of Valladolid http://uva.onlinejudge.org 超过800题,支持C/C++/Pascal/Java

    4. 🎄Ural State University http://acm.timus.ru 超过800题,支持C/C++/C#/Pascal/Java

    5. 🎄Sphere Research Labs http://www.spoj.pl 超过1000题,支持几乎所有常见语言


    🚀入门到进阶的Online Judge

    1. 🎄vijos:大部分题目是NOI题目 https://vijos.org/
    2. 🎄洛谷:https://www.luogu.org/problemnew/lists
    3. 🎄RQNOJ:和vijos很像,适合NOI刷题 http://www.rqnoj.cn/problem

    🚀招聘面试Online Judge

    1. 🎄牛客网:https://www.nowcoder.com/
    2. 🎄leetcode:https://leetcode.com/problemset/all/
    3. 🎄LintCode:https://www.lintcode.com/zh-cn/
    4. 🎄51nod:http://www.51nod.com/Challenge/ProblemList.html#!#isAsc=false
    5. 🎄hackerrank:https://www.hackerrank.com/


    如果对你有帮助希望你不吝啬手中的star哦、如果能follow就更好啦,我们一起进步🔥!

    算法路上加油⛽️

    欢迎大家贡献你的资料,丰富这个Repo

    如有侵权,麻烦提 Issues 或联系 981242367@qq.com 删改

    展开全文
  • 数据结构算法学习路线So You’re interested in software engineering, Full-Stack web development, or any computer related field, but you don’t know where to start? Maybe you even went to a coding Web-...
  • 如何学习算法和数据结构?时间复杂度和空间复杂度到底是关于什么的度量标准?数组、链表、树、图,这些数据结构分别有什么作用?
  • 后来很多学弟私聊我说能不能写一个专业课的学习路线或者心得,想了想,该写!算是top学长对你们扬帆起航的路上助一把力。西交专业课是数据结构+程序设计。首先讲下程序设计,其实西交的程序设计题目不是很难(大概pat...
  • Python学习教程_Python学习路线:Python数据结构概述 数据结构是组织数据的方式,以便能够更好的存储和获取数据。数据结构定义数据之间的关系和对这些数据的操作方式。数据结构屏蔽了数据存储和操作的细节,让程序员...
  • Python学习教程(Python学习视频_Python学习路线):Python数据结构 概述 数据结构是组织数据的方式,以便能够更好的存储和获取数据。数据结构定义数据之间的关系和对这些数据的操作方式。数据结构屏蔽了数据存储和...
  • Python学习教程:数据结构前言 数据结构是组织数据的方式,以便能够更好的存储和获取数据。数据结构定义数据之间的关系和对这些数据的操作方式。数据结构屏蔽了数据存储和操作的细节,让程序员能更好的处理业务逻辑...
  • 最新Python学习教程(Python学习路线+Python学习视频):数据结构 前言: 数据结构是组织数据的方式,以便能够更好的存储和获取数据。数据结构定义数据之间的关系和对这些数据的操作方式。数据结构屏蔽了数据存储和...
  • Java数据结构与算法之学习路线

    万次阅读 多人点赞 2016-09-28 17:19:21
    2.数据结构与算法学习大纲(粗糙) 3.线性结构分类 4.各个线性类型数据结构的特点以及使用场景 5.数组与队列的区别 1.前言: 昨天去面试了一家我觉得薪资和公司文化都不错的公司,也不知道是天真还是没得自知之明,一...
  • 下面是数据结构学习路线图。然后大家可以不停地百度,然后对每一部分进行学习。 基本上把每一部分的概念百度学习一下,然后自己敲击相关代码进行多次练习,即可基本掌握数据结构。 今天母亲节,还是要打电话给...
  • 下面是工作中或者面试中经常用到的数据结构与算法相关的知识点,也是我曾经用到过的,如果想要XMind格式的,那就请在下方评论,我会在第一时间回复并发给你,下面是给大家罗列出来的: ...
  • Python学习教程(Python学习路线):数据结构精讲前言 数据结构是组织数据的方式,以便能够更好的存储和获取数据。数据结构定义数据之间的关系和对这些数据的操作方式。数据结构屏蔽了数据存储和操作的细节,让...
  • 努力打工,争取每天3个 更新进度:■■■■■■■■■■□□□□□□□□□□|50% 目前在更新:排序算法 学习内容: 基本算法:枚举、排序、搜索、递归、分治、优先搜索、贪心、双指针、动态规划等… 数据结构:字符...
  • 虽然是用python搞机器学习的大项目,还是要从零开始学习数据结构那一套理论。不知不觉数据结构及算法系列的学习及LeetCode刷题已经一大堆,现对此汇总。 如下是一套比较合理的完整的学习路径: 1)数据结构与算法...
  • 随着科学技术的发展,人工智能已经逐渐渗透到各个行业,这是一个相当有前景的专业领域。 其中,算法工程师这一职位更是非常火爆,在急缺大量人才的同时,也吸引了众多求职...熟练运用各种常用算法和数据结构,有...
  • 这里面包含一份java的学习路线。 另外包含 1 树的基本概念 2 红黑树的实现 3 一种新型的树以及相关分析 这份资料主要是对树的学习和分析,也是在网络上找到的。
  • 文章目录推荐阅读前言Lua 特性应用场景示例脚本注释关键词全局变量Lua数据特性独特地方tablefunctionthread(线程)userdata(自定义类型)Lua...机制C包协同程序coroutine生产者、消费者问题I/O错误处理常见数据结构1....
  • 废话不多说,直接上路线,分阶段进行的,从简单基础入手,喜欢的可以关注我的公众号:java的架构师技术栈阶段一:数据结构一、基础1、基本的数据结构 (1)基础概念 (2)数组 (3)链表 (4)栈 (5)队列2、树 (1...
  • Python基础学习教程(Python学习路线):使用字符串 第二次世界大战促使了现代电子计算机的诞生,当初的想法很简单,就是用计算机来计算导弹的弹道,因此在计算机刚刚诞生的那个年代,计算机处理的信息主要是数值,...
  • 数据结构(数据存储的方式):是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。数据结构大体包括:数组(Array).栈...
  • 我们如何把显示中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作,这个相应的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,469
精华内容 587
关键字:

数据结构学习路线

数据结构 订阅