数据结构与算法项目化教程（数据结构与算法（c++）的视频教程和PDF,急求！！！！）

本文目录

• 数据结构与算法(c++)的视频教程和PDF,急求！！！！
• 数据结构与算法分析 C++
• 牛掰！阿里大佬刷了四年LeetCode才总结出来的数据结构和算法手册
• 数据结构与算法--堆和堆排序
• 数据结构与算法基础知识

数据结构与算法(c++)的视频教程和PDF,急求！！！！

数据结构与算法设计是计算机专业的核心课程，主要传授数据组织方法和典型问题求解策略，具有一定的抽象性，不易掌握。    

数据结构与算法分析 C++

你说的是中序线索二叉树的插入和删除

#include 《stdio.h》
#include "malloc.h"
#include "windows.h"
#define maxsize 20                           //规定树中结点的最大数目
typedef struct node{                         //定义数据结构
 int ltag,rtag;                           //表示child域指示该结点是否孩子  
 char data;                               //记录结点的数据
 struct node *lchild,*rchild;             //记录左右孩子的指针
}Bithptr;
 Bithptr *Q;                         //建队，保存已输入的结点的地址
 Bithptr *CreatTree(){                        //建树函数，返回根指针
 char ch;
 int front,rear;
 Bithptr *T,*s;
 T=NULL;
 front=1;rear=0;                          //置空二叉树
 printf("建立一棵二叉树，请输入结点信息：\n");
  printf("请输入新的结点信息，@为空结点，#为结束标志：");
 ch=getchar()();                            //输入第一个字符
 while(ch!=’#’)                           //判断是否为结束字符
 {
  s=NULL;
  if(ch!=’@’)                          //判断是否为虚结点
  {
   s=(Bithptr *)malloc(sizeof(Bithptr));
   s-》data=ch;
   s-》lchild=NULL;
   s-》rchild=NULL;
   s-》rtag=0;
   s-》ltag=0;
  }
  rear++;             
  Q=s;                            //将结点地址加入队列中
  if(rear==1)T=s;                       //输入为第一个结点为根结点
  else 
  {
   if(s!=NULL&&Q!=NULL)       //孩子和双亲结点均不是虚结点
    if(rear%2==0)
      Q-》lchild=s;
       else Q-》rchild=s;
   if(rear%2==1)front++;
  }getchar()();
  printf("请输入新的结点信息，@为空结点，#为结束标志：");
  ch=getchar()();
 }
 return T;
}
void Inorder(Bithptr *T)                      //中序遍历
{
 if(T)
 {
  if(T-》ltag!=1)Inorder(T-》lchild);
  printf("→%c",T-》data);
  if(T-》rtag!=1)Inorder(T-》rchild);
 }
}
Bithptr *pre=NULL;
void  PreThread(Bithptr *root)                 //中序线索化算法，函数实现
{
 Bithptr *p;
 p=root;
    if(p){
     PreThread(p-》lchild);//线索化左子树              
  if(pre&&pre-》rtag==1)pre-》rchild=p;    //前驱结点后继线索化
        if(p-》lchild==NULL)                    
  {
   p-》ltag=1;
   p-》lchild=pre;
  }
  if(p-》rchild==NULL)                   //后继结点前驱线索化
   p-》rtag=1;
  pre=p;
  PreThread(p-》rchild);
 }
}
void PrintIndex(Bithptr *t)                       //输出线索
{
 Bithptr *f;
 f=t;
 if(f)
 {
  if(f-》ltag==1&&f-》lchild==NULL&&f-》rtag==1)   printf("【%c】",f-》data);                         //如果是第一个结点
  if(f-》ltag==1&&f-》lchild!=NULL)               printf("%c→【%c】",f-》lchild-》data,f-》data);     //如果此结点有前驱就输出前驱和此结点
    if(f-》ltag==1&&f-》rtag==1&&f-》rchild!=NULL)   printf("→%c",f-》rchild-》data);            //如果此结点有前驱也有后继，就输出后继
  else if(f-》rtag==1&&f-》rchild!=NULL)          printf("【%c】→%c",f-》data,f-》rchild-》data);//如果没有前驱，就输出此结点和后继
  printf("\n");
  if(f-》ltag!=1)PrintIndex(f-》lchild);
  if(f-》rtag!=1)PrintIndex(f-》rchild);
 }
}      
Bithptr *SearchChild(Bithptr *point,char findnode)            //查找孩子结点函数
{
       Bithptr *point1,*point2;
       if(point!=NULL)
       {
          if(point-》data==findnode)   return point;
          else 
     if(point-》ltag!=1)  { point1=SearchChild(point-》lchild,findnode); if(point1!=NULL)return point1;}        
              if(point-》rtag!=1)  { point2=SearchChild(point-》rchild,findnode); if(point2!=NULL)return point2;}                  
              return NULL;         
       }
       else 
           return NULL;
} 
Bithptr *SearchPre(Bithptr *point,Bithptr *child)            //查找父亲结点函数
{
       Bithptr *point1,*point2;
       if(point!=NULL)
       {
          if((point-》ltag!=1&&point-》lchild==child)||(point-》rtag!=1&&point-》rchild==child))   return point;//找到则返回
          else 
     if(point-》ltag!=1) 
     {
      point1=SearchPre(point-》lchild,child);
      if(point1!=NULL)
       return point1;
     }        
              if(point-》rtag!=1) 
     {
      point2=SearchPre(point-》rchild,child);
      if(point2!=NULL)
       return point2;
     }                  
              return NULL;         
       }
       else 
           return NULL;
}
void Insert(Bithptr *root)
{
 char ch;
 char c;
 Bithptr *p1,*child,*p2;
 printf("请输入要插入的结点的信息:");
    scanf("%c",&c);
 scanf("%c",&c);
    p1=(Bithptr *)malloc(sizeof(Bithptr));        //插入的结点信息
 p1-》data=c;
 p1-》lchild=NULL;
 p1-》rchild=NULL;
 p1-》rtag=0;
 p1-》ltag=0;
 printf("输入查找的结点信息:");
    scanf("%c",&ch);
 scanf("%c",&ch);
 child=SearchChild(root,ch);                      //查孩子结点的地址
 if(child==NULL){
  printf("没有找到结点\n");
  system("pause");
  return ;
 }
 else printf("发现结点%c\n",child-》data);
 if(child-》ltag==0)                     //当孩子结点有左孩子的时候
 {
  p2=child;
  child=child-》lchild;
  while(child-》rchild&&child-》rtag==0)              //找到左子树下，最右结点
   child=child-》rchild;
  printf("发现结点%c\n",child-》data);
  p1-》rchild=child-》rchild;         //后继化 
  p1-》rtag=1;
  child-》rtag=0;
  child-》rchild=p1;                 //连接                     
  p1-》lchild=child;                 //前驱化
  p1-》ltag=1;
 } 
 else                              //当孩子结点没有左孩子的时候
 {
  p1-》lchild=child-》lchild;    //前驱化
  child-》ltag=0;
  p1-》ltag=1;
  child-》lchild=p1;
  p1-》rchild=child;
  p1-》rtag=1;
 }
 printf("\t插入结点操作已经完成，并同时完成了线索化的恢复\n");
}

牛掰！阿里大佬刷了四年LeetCode才总结出来的数据结构和算法手册

前几天和一个粉丝聊面试，他说去年同时拿到了阿里和网易的 offer，最后选择了阿里。

我了解了下他的面试过程，就一点，无论是网易还是阿里的面试，其中一个占比非常大的权重就是 数据结构与算法。

其实现在不管面试什么岗位，前端也好，后端也罢，都必须考察算法，这关过了，基本上就没太大问题了。他告诉我，那些大厂认为，你能把最基本、最核心的算法都能搞定，那么那些编程语言啊、不同的应用方向，开发框架啊对你来说一定不是难事。

那么，如何才能更好地啃下算法这块骨头呢？

无他，就是靠自己的毅力以及决心。一天不行，一个月；一个月不行，一年；有决心的人，啥学历、智商或者资历，那些都是借口。

不过除了毅力和决心之外， 其实学习还是有效率之差的。

互联网时代，其实网上有很多免费学习资料，只要你用点心，也总能找到学习资料，今天团长就在这里分享一份 阿里 大佬的leetcode上面刷了四年题总结的数据结构和算法面试解析手册！

数据结构与算法--堆和堆排序

堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。

堆是一种特殊的树。
只要满足这两点，它就是一个堆：

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做 “大顶堆” 。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做 “小顶堆” 。

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。下标可以直接计算出左右字数的下标。（数组中下标为 i 的节点，左子节点下标为 i∗2 ，右子节点下标为 i∗2+1，父节点的下标为 i/2​ 。）

如果我们把新插入的元素放到堆的最后，你可以看我画的这个图，是不是不符合堆的特性了？于是，我们就需要进行调整，让其重新满足堆的特性，这个过程我们起了一个名字，就叫做 堆化（heapify） 。
堆化实际上有两种，从下往上和从上往下。这里我先讲从下往上的堆化方法。
堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。

我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是 从上往下的堆化方法 。

一个包含 n 个节点的完全二叉树，树的高度不会超过 log2​n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。

这里我们借助于堆这种数据结构实现的排序算法，就叫做堆排序。这种排序方法的时间复杂度非常稳定，是 O(nlogn)，并且它还是原地排序算法。

从后往前处理数组，并且每个数据都是从上往下堆化。
因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次堆化就行了。

建堆的时间复杂度就是 O(n)。 推导过程见 极客时间--数据结构与算法之美

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。
这个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

堆这种数据结构几个非常重要的应用：优先级队列、求 Top K 和求中位数。

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。
这里就可以用到优先级队列，也可以说是堆。我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。

我们可以用优先级队列来解决。我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。

如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

中位数，顾名思义，就是处在中间位置的那个数。
使用两个堆：一个大顶堆， 一个小顶堆。 小顶堆中的数据都大于大顶堆中的数据。
如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。
也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 2n​ 个数据存储在大顶堆中，后 2n​ 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 2n​+1 个数据，小顶堆中就存储 2n​ 个数据。

极客时间--数据结构与算法之美--28 | 堆和堆排序：为什么说堆排序没有快速排序快？

数据结构与算法基础知识

1.数据结构的逻辑结构

(1)集合结构

(2)线性结构(存在唯一的第一个元素与唯一的最后一个元素)(eg: 线性表、队列、栈、字符串、数组、链表)

(3)树形结构(一对多)

(4)图形结构(多对多)
2.数据结构的物理(存储)结构

(1).顺序存储结构(插入与删除低效因为要挪动其他元素的位置。但是遍历简单)

(2).链式存储结构(插入与删除高效，但是遍历低效)
3.大O表示法(注意大O表示法表达的是最坏的情况)

规则：

(1)用常数1取代其他所有的常数(注意常数0也当1算)(3 -》 1, O(1))

(2) 只保留最高阶项(n^3+2n^2+5 -》n^3, O(n^3))

(3) 若存在最高阶，省略与其想成的常数(2n^3 -》 n^3, O(n^3))

4. 时间复杂度类型

(1)常数阶

(2)线性阶

(3)平方阶

(4)对数阶

(5)立方阶

(6)nlog阶

(7)指数阶(O(2^n)或O(n!), 往往会造成噩梦般的时间消耗)
5. 空间复杂度(用大O表示法求解改算法的辅助空间即可，例如用于交换变量用的临时变量的数量)
六. 顺序存储的线性表

线性表结构特点：

(1) 存在唯一一个的被称作”第一个”的数据元素；

(2) 存在唯一一个的被称作”第二个”的数据元素；

(3) 除了第一个元素以外，结构中的每个数据元素均有一个前驱；

(4) 除了最后一个元素以外，结构中的每个数据元素均有一个后继。
七. 链式存储的线性表(单链表)

首元结点是链表中第一个值域不为空的结点。

头结点是一个值域为空且处于首位的结点。

首指针可指向首元结点也可指向头结点，但是如果指向头结点可以更加方便的处理单链表的插入和删除问题，不用再对首位做额外判断，并且指向头节点的指针永远不用变化。

*注意一下单链表的前插法和尾插法。尾插法更符合逻辑