AI 助理
备案控制台
开发者社区 人工智能 文章 正文

412数据结构学习强化——常见数据结构定义和算法总结（五）

2022-11-27 104
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 412数据结构学习强化——常见数据结构定义和算法总结

5.4.5.查找二叉树中两个结点的公共祖先结点

59da31125bff423a875a1b8ce85b8673.png

BiTNode *ans(BiTree ROOT, BiTNode *p, BiTNode *q) {
  Stack S, Sp, Sq;  //Sp和Sq分别用来保存p和q的祖先结点
  S.top = -1; //初始化队列
  BiTNode* t = ROOT, *pre = NULL;
  while (t || S.top >= 0) {
    if (t) {  //t结点非空
      S.data[++S.top] = t;  //t结点入队
      t = t->lchild;  //进入t的左子树
    }
    else {  //t结点为空
      t = S.data[S.top];  //查看栈顶元素
            //t的右子树存在，并且上一个访问的并不是其右子树
      if (t->rchild && t->rchild != pre) {  
        t = t->rchild;  //进入右子树
        S.data[++S.top] = t;  //入栈该结点
        t = t->rchild;  //进入左子树
      }
      else {  //右子树不存在，或者存在但是上一个访问的是右子树
        S.top--;  //出栈该结点，并访问
        if (t == p) { //当前结点为p，保存栈中内容，即其所有祖先结点
          for (int i = 0; i < S.top; i++) Sp.data[i] = S.data[i];
          Sp.top = S.top;
        }
        if (t == q) { //当前结点为q，保存栈中内容，即其所有祖先结点
          for (int i = 0; i < S.top; i++) Sq.data[i] = S.data[i];
          Sq.top = S.top;
        }
      }//if
    }//if
  }//while
    //自栈顶到栈顶分别遍历Sp和Sq找到最接近栈顶的相同祖先结点
  for (int i = Sp.top; i >= 0; i--) { 
    for (int j = Sq.top; i >= 0; j--) {
      if (Sp.data[i] == Sq.data[j]) return Sp.data[i];
    }
  }
  return NULL;  //无相同祖先顶点
}

5.4.6.求二叉树的宽度ccb1ae7ce764475ea764c119315612e4.png

typedef struct Queue{
    BiTNode *data[MAXSIZE];    //足够大的数组
    int front, rear;
}Queue;
int ans(BiTree T){
    if (!T) return 0;    //空树，返回0
    BiTNode *p = T;
    Queue Q;
    InitQueue(Q);    //初始化队列
    EnQueue(Q, p);    //将p入队
    //rear指向当前层的最后一个结点，count记录当前层的结点数，max记录最大结点数
    int last = Q.rear, count = 0, max = INT_MIN;    
    while (!IsEmpty(Q) {
        DeQueue(Q, p);
        count++;    //结点数+1
        if (p->lchild) EnQueue(Q, p->lchild);    //p的左子树存在，左子树入队
        if (p->rchild) EnQueue(Q, p->rchild);    //p的右孩子存在，右孩子入队
        if (last == Q.front) {    //当前结点是本层的最后一个节点
            last = Q.rear;    //last指向下一层的最后一个结点
            if (count > max) max = temp;    //更新最大结点数
            count = 0;    //结点数归零
        }
    }//while
    return max;
}
typedef struct Queue {  //足够大的非循环数组
  BiTNode *data[MAXSIZE]; //结点数组，保存每个结点
  int level[MAXSIZE]; //层数数组，记录每个结点的层数
  int front, rear;  //头尾指针
}Queue;
int ans(BiTree T) {
  BiTNode* p = T;
  Queue Q;
  Q.rear = Q.front = 0; //初始化队列
  if (T) {
    Q.data[Q.rear] = T; //根节点入队
    Q.level[Q.rear] = 1;
    Q.rear++;
    while (Q.front < Q.rear) {
      p = Q.data[Q.front];  //出队队首元素
      int level = Q.level[Q.front]; //保存当前结点的层数
      Q.front++;
      if (p->lchild) {  //左孩子入队
        Q.data[Q.rear] = p->lchild;
        Q.level[Q.rear] = level + 1;
        Q.rear++;
      }
      if (p->rchild) {  //右孩子入队
        Q.data[Q.rear] = p->rchild;
        Q.level[Q.rear] = level + 1;
        Q.rear++;
      }
    }//while
    int max = INT_MIN, i = 0, level = 1;
    while (i <= Q.rear) {
      int count = 0;  //记录当前层的结点数
      while (i <= Q.rear && level == Q.level[i]) {
        count++;
        i++;
      }
      if (count > max) max = count; //更新每层的最大结点数
      level = Q.level[i]; //更新层数，while循环结束时，i指向下一层的第一个结点
    }//while
    return max; //返回最大结点数
  }
  else return 0;  //空树，返回0
}

5.4.7.求二叉树的高度 

int Get_Heigh(BiTree T) {
  int front = 0, rear = 0;  //前后指针
  BiTNode* p = T;
  BiTNode *data[MAXSIZE]; //足够大的队列，元素是二叉树结点
  data[rear++] = p; //根节点入队
  int last = rear, level = 0; //rear标记本层最后一个结点, level记录当前层数
  while (front < rear) {  //循环直到队空
    p = data[front++];  //出队队首结点
    if (p->lchild) data[Q.rear++] = p->lchild;  //左右孩子入队
    if (p->rchild) data[Q.rear++] = p->rchild;
    if (last == front) {  //当前结点为本层的最后一个结点
      last = rear;  //标记下层的最后一个结点
      level++;  //层数+1
    }
  }//while
  return level;
}
int Get_High(BiTree T){
    if (!T) return 0;    //空树返回0
    else {
        int hl = Get_High(T->lchild);    //递归求左右子树高度
        int hr = Get_High(T->rchild);
        int maxH = max(hl, hr) + 1;    //树高等于左右子树更高的那个+1
        return maxH;
    }
}

5.4.8.排序二叉树的判定

int pre = INT_MIN;  //标记上一个结点的值，初始值为INT类型的最小值
int JudgeBST(BiTree T) {
  if (!T) return 1; //空树，是排序二叉树
  else {
    int l = JudgeBST(T->lchild);  //判断左子树
        //当前值小于等于pre的值，或左子树不满足排序二叉树定义，返回0
    if (T->data <= pre|| l == 0) return 0;
    pre = T->data;  //更新pre为当前结点值
    int r = JudgeBST(T->rchild);  //判断右子树
    return r;
  }
}
int A[n]; //足够大的数组，保存每个节点的值
int count = 0;  //记录结点个数
void InOrder(BiTree T) {
  if (T) {
    InOrder(T->lchild); 
    A[count++] = T->data; //记录当前结点值，并且count+1
    InOrder(T->rchild);
  }
}
bool ans(BiTree T) {
  if (!T) return true;  //空树为排序二叉树
  else if (!T->lchild && !T->rchild) return true; //只有根节点，是排序二叉树
  else {
    InOrder(T); //中序遍历二叉树，并且记录每个结点的值
    for (int i = 0; i < count - 1; i++) {
      if (A[i] >= A[i + 1]) return false; //非排序二叉树
    }
    return true;  //排序二叉树
  }
}

5.4.9.平衡二叉树的判定

int Get_Height(BiTree T) {
  if (!T) return 0;
  else {
    int hl = Get_Height(T->lchild); //递归求左子树高度
    int hr = Get_Height(T->rchild); //递归求右子树高度
    int maxH = max(hl, hr) + 1; //树高为左右子树更高的那个 + 1
    return maxH;  
  }
}
bool JudgeBalance(BiTree T) {
  if (!T) return true;  //空树为平衡二叉树
  else {
    int hl = Get_Height(T->lchild); //左子树高度
    int hr = Get_Height(T->rchild); //右子树高度
    //当前结点的左右平衡因子小于等于1，递归判断其左右子树是否满足平衡二叉树
    if (abs(hl - hr) <= 1) {
            return JudgeBalance(T->lchild) && JudgeBalance(T->rchild);
        }
    //当前节点左右平衡因子大于1，则已不满足平衡二叉树，无需判断左右子树，返回false
    else return false;
  }
}

5.4.10.完全二叉树的判定

bool JudgeComplete(BiTree T) {
  BiTNode* data[MAXSIZE]; //足够大的队列
  int front = 0, rear = 0;  //头尾指针
  BiTNode* p = T; 
  data[rear++] = T; //根节点入队
  while (front < rear) {  //循环直到队空
    p = data[front++];  //出队队首元素
    if (p) {  //p结点存在，入队左右孩子
      data[rear++] = p->lchild;
      data[rear++] = p->rchild;
    }
    else {  //p结点不存在，出队剩余元素
      while (front < rear) {
        p = data[front++];
        if p == NULL return false;  //当前元素为空，则为非完全二叉树
      }
    }
  }
  return true;
}

5.4.11.真题6f2f5d0118df435db4b92a0872d5d5ce.png

int WPL = 0;
void InOrder(BiTree T, int deep){
    if (T) {
        if (!T->left && !T->right) {    //叶子结点
            WPL = WPL + T.weight * deep;    //更新WPL
        }
        if (T->left) InOrder(T->left, deep + 1);
        if (T->right) InOrder(T->right, deep + 1);
    }
}
int ans(BiTree T){
    InOrder(T, 0);
    return WPL;
}
int Get_WPL(BiTree root) {
  BiTNode* data[MAXSIZE]; //足够大的非循环数组
  BiTNode* p = root;
  int f = 0, r = 0, level = 0, WPL = 0, last = 0; 
  data[r++] = p;  //根节点入队
  last = r; //last标记本层的最后一个元素
  while (f < r) {
    p = data[f++];  //队首元素出队
        //该结点为叶子结点，计算WPL
    if (!p->lchild && !p->rchild) WPL = WPL + level * p->weight;
    if (p->lchild) data[r++] = p->left; //左右孩子入队
    if (p->rchild) data[r++] = p->right;
    if (last == f) {  //该结点为本层的最后一个结点
      last = r; //更新last和level
      level++;
    }
  }
    return WPL;
}
f184da9060ed4f348f5a5207d442c7f6.png 
void InOrder(BiTree T, int deep){
    if (T) {
        if (deep > 1 && (T->lchild || T->rchild)) cout << '(';    //分支节点打印左括号
        if (T->lchild) InOrder(T->lchild, deep + 1);
        cout << T->data;
        if (T->rchild) InOrder(T->rchild, deep + 1);
        if (deep > 1 && (T->lchild || T->rchild)) cout << ')';    //分支节点打印右括号
    }
}
void ans(BiTree T){
    InOrder(T, 1);
}

6.图

6.1.图的数据结构定义

6.1.1.邻接矩阵

#define MAXVEX 100
typedef struct Graph {
    int data[MAXVEX];    //一维数组，存放顶点数据
    int edge[MAXVEX][MAXVEX];    //二维数组，存放边数据（权值）
    int vexNum, edgeNum;    //顶点总数和边总数
}Graph;

6.1.2.邻接表

#define MAXVEX 100
typedef struct edgeNode {    //边
    struct edgeNode *next;    //指向下一条邻接边的指针
    int weight;    //该邻接边权值
    int adjVex;    //该邻接边指向的顶点编号
}edgeNode;
typedef struct vexNode {    //顶点
    edgeNode *firstEdge;    ///指向该顶点的第一条邻接边
    int vexData;    //该顶点数据
}vexNode;
typedef struct Graph {    //图
    int vexNum, edgeNum;    //顶点数，边数
    vexNode vex[MAXVEX];    //vexNode类型的一维数组vex
}Graph;

6.2.图的遍历

6.2.1.深度优先遍历

#define MAXVEX 100
bool visited[MAXVEX];    //visited数组记录该顶点是否被访问过
void DFSTraverse (Graph G) {
    for (int i = 0; i < G.vexNum; i++) {
        visited[i] = false;    //初始化visited数组
    }
    for (int i = 0; i < G.vexNum; i++) {
        if (!visited[i]) DFS (G, i);    //当前顶点未被访问过，则访问
    }
}
void DFS (Graph G, int v) {
    visit (v);    //访问顶点v（具体操作）
    visited[v] = true;    //更新visited数组
    for (int w = FirstNeighbor (G, v); w >= 0; w = NextNeighbor (G, v, w)){
        if (!visited[w]) DFS(G, w);    //递归调用DFS
    }
}

6.2.2.广度优先遍历

#define MAXVEX 100
Queue Q;
bool visited[MAXVEX];
void BFSTraverse (Graph G) {
    for (int i = 0; i < G.vexNum; i++) {    //初始化visited数组
        visited[i] = false;    
    }
    InitQueue Q;    //初始化队列Q
    for (int i = 0; i < G.vexNum; i++) {    //遍历图
        if (!visited[i]) BFS(G, i);
    }
}
void BFS (Graph G, int v) {
    visit(v);    //访问该顶点（具体操作）
    visited[v] = true;    //更新visited数组
    EnQueue(Q, v);    //将v结点入队
    int w;
    while(!IsEmpty(Q)) {
        DeQueue(Q, v);    //队首元素出队
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {    //顶点未被访问过
                visit(w);
                visited[w] = true;
                EnQueue(Q, w);
            }
        }//for
    }//while
}

6.3.单源最短路径

#define MAXVEX 100
bool visited[MAXVEX];
int dis[MAXVEX];
Queue Q;
void Min_Dis (Graph G, int v) {
    for (int i = 0; i < G.vexNum; i++) {    //初始化visited数组和dis数组
        visited[i] = false;
        dis[i] = INT_MAX;
    }
    visited[v] = true;
    dis[v] = 0;
    InitQueue(Q);
    EnQueue(Q, v);
    int w;
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FisrtNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w) {
            if (!visited[w]) {
                visited[w] = true;
                dis[w] = dis[v] + 1;
            }
        }//for
    }//while
}

6.4.真题

fa4a011572674952bb92acaee9c519c5.png

int IsExistEL(MGraph G){
    int count = 0;    //记录该图中度为奇数的顶点个数
    int i, j;
    for (i = 0; i < G.numVertices; i++){    //行遍历邻接矩阵
        int degree = 0;
        for (j = 0; j < G.numVertices; j++){    //列遍历当前行
            if (Edge[i][j] > 0) degree++;    //当前数组元素不为0，则度+1
        }
        if (degree % 2) count++;    //当前顶点的度为奇数，count++
    }
    if (count == 0 || count == 2) return 1;    //奇数顶点个数为0或者2，有EL路径
    else return 0;    //奇数顶点个数不为0或者2，没有EL路径
}

7.快速排序

void QSort(int A[], L, R) {    //快速排序
    if (L >= R) return;    //当前数组长度 <= 1，返回
    随机选择数组中一元素和A[L]互换    //快排优化，使得基准元素的选取随机
    int key = A[L], i = L, j = R;
    while (i < j) {
        while (i < j && key < A[j]) j--;
        while (i < j && A[i] <= key) i++;
        if (i < j) swap (A[i], A[j]);    //交换A[i]和A[j]
    }
    swap (A[i], A[L]);
    Qsort (A, L, i - 1);    //递归处理左区间
    Qsort (A, i + 1, R);    //递归处理右区间
}

8.折半查找

int Binary_Search (int A, L, R, key) {
    int mid;
    while (L < R) {    //L >= R时，范围错误
        mid = (L + R) / 2;    //选择中间数，向下取整
        if (key <= A[mid]) R = mid;    //更新范围
        else L = mid + 1;
    }
    if (A[mid] == key) return mid;    //查找成功，返回数组下标
    else return -1;    //查找失败，返回-1
}


文章标签：
算法
关键词：
数据结构算法
算法学习
算法数据结构
数据结构学习
算法强化
gbip7sii3jwms
目录
相关文章
BetterBench
|
11天前
|
机器学习/深度学习 人工智能 资源调度
【博士每天一篇文献-算法】连续学习算法之HAT： Overcoming catastrophic forgetting with hard attention to the task
本文介绍了一种名为Hard Attention to the Task (HAT)的连续学习算法，通过学习几乎二值的注意力向量来克服灾难性遗忘问题，同时不影响当前任务的学习，并通过实验验证了其在减少遗忘方面的有效性。
BetterBench
28 12
AI之家
|
2天前
|
机器学习/深度学习 人工智能 算法
【人工智能】线性回归模型：数据结构、算法详解与人工智能应用，附代码实现
线性回归是一种预测性建模技术，它研究的是因变量（目标）和自变量（特征）之间的关系。这种关系可以表示为一个线性方程，其中因变量是自变量的线性组合。
AI之家
11 2
服务端技术栈
|
4天前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法，特别是通过双指针法来实现字符串的反转操作，并提供了LeetCode上相关题目的Java代码实现，强调了掌握这些技巧对于提升算法思维的重要性。
服务端技术栈
12 1
落雨便归尘
|
6天前
|
算法 NoSQL 中间件
go语言后端开发学习(六) ——基于雪花算法生成用户ID
本文介绍了分布式ID生成中的Snowflake（雪花）算法。为解决用户ID安全性与唯一性问题，Snowflake算法生成的ID具备全局唯一性、递增性、高可用性和高性能性等特点。64位ID由符号位（固定为0）、41位时间戳、10位标识位（含数据中心与机器ID）及12位序列号组成。面对ID重复风险，可通过预分配、动态或统一分配标识位解决。Go语言实现示例展示了如何使用第三方包`sonyflake`生成ID，确保不同节点产生的ID始终唯一。
落雨便归尘
18 0
go语言后端开发学习(六) ——基于雪花算法生成用户ID
BetterBench
|
11天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之RWalk：Riemannian Walk for Incremental Learning Understanding
RWalk算法是一种增量学习框架，通过结合EWC++和修改版的Path Integral算法，并采用不同的采样策略存储先前任务的代表性子集，以量化和平衡遗忘和固执，实现在学习新任务的同时保留旧任务的知识。
BetterBench
50 3
aliyun6365824167
|
1天前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称，即左右子树是否对称.
aliyun6365824167
7 0
aliyun6365824167
|
1天前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
6 0
william.zhang(张)
|
3天前
|
存储 缓存 算法
深入解析B树：数据结构、存储结构与算法优势
深入解析B树：数据结构、存储结构与算法优势
william.zhang(张)
5 0
可编程芯片开发
|
6天前
|
算法
基于模糊控制算法的倒立摆控制系统matlab仿真
本项目构建了一个基于模糊控制算法的倒立摆控制系统，利用MATLAB 2022a实现了从不稳定到稳定状态的转变，并输出了相应的动画和收敛过程。模糊控制器通过对小车位置与摆的角度误差及其变化量进行模糊化处理，依据预设的模糊规则库进行模糊推理并最终去模糊化为精确的控制量，成功地使倒立摆维持在直立位置。该方法无需精确数学模型，适用于处理系统的非线性和不确定性。
可编程芯片开发
22 7
基于模糊控制算法的倒立摆控制系统matlab仿真
我爱matlab
|
1天前
|
算法 数据安全/隐私保护
基于LS算法的OFDM+QPSK系统信道估计均衡matlab性能仿真
基于MATLAB 2022a的仿真展示了OFDM+QPSK系统中最小二乘（LS）算法的信道估计与均衡效果。OFDM利用多个低速率子载波提高频谱效率，通过循环前缀克服多径衰落。LS算法依据导频符号估计信道参数，进而设计均衡器以恢复数据符号。核心程序实现了OFDM信号处理流程，包括加性高斯白噪声的加入、保护间隔去除、快速傅立叶变换及信道估计与均衡等步骤，并最终计算误码率，验证了算法的有效性。
我爱matlab
9 2

热门文章

最新文章

  • 1
    一文让你了解AI产品的测试 评价人工智能算法模型的几个重要指标
  • 2
    经典算法题--求对策字符串的最大长度(第二版)
  • 3
    [算法题] 人民币大小写转换（阿拉伯数字和汉字转换）
  • 4
    “SRTT” DNS服务器选择算法介绍
  • 5
    字符串匹配算法之BF(Brute-Force)算法
  • 6
    一个从四秒到10毫秒，花了1年的算法问题？
  • 7
    JavaScript的6个算法实用小技巧
  • 8
    经典算法题每日演练——第二十五题 块状链表
  • 9
    如何让用户找到想要的内容？阿里文娱搜索算法实践
  • 10
    当年参加飞思卡尔自己写的双线识别算法
  • 1
    操作数栈的字节码指令执行分析
    29
  • 2
    D1. Range Sorting (Easy Version)(单调栈+思维)
    26
  • 3
    InfluxDB数据模型与数据结构设计详解
    322
  • 4
    数据结构面试常见问题
    51
  • 5
    22个常用数据结构实现与原理分析
    41
  • 6
    数据结构——二叉树的遍历【前序、中序、后序】
    32
  • 7
    数据结构奇妙旅程之红黑树
    22
  • 8
    数据结构奇妙旅程之二叉平衡树进阶---AVL树
    18
  • 9
    数据结构奇妙旅程之二叉平衡树
    14
  • 10
    数据结构奇妙旅程之七大排序
    16

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 【云栖精选7月刊】抛开晦涩的算法、模型，让我们来谈谈互联网架构
  • 聚星台—客户运营核心大数据 与算法技术
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    通义千问API入门教程