当前位置: 首页 > news >正文

软件设计师笔记-数据结构

数据结构

数据元素的集合及元素间的相互关系和构造方法。

线性表的存储结构

  • 顺序存储
  • 链式存储

单链表节点

typedef struct node { int data; struct node *link; 
}NODE, *LinkList; 

双向链表

每个节点有两个指针,分别指出直接前驱和直接后继。

循环链表

尾节点指针指向第一个节点。

静态链表

借助数组来描述线性表的链式存储结构。

  • 特点:后进先出
  • 初始化栈: InitStack(S)
  • 判栈空:StackEmpty(S)
  • 入栈:Push(S,x)
  • 出栈:Pop(S)
  • 读取栈顶元素:Top(S)-----顺序存储+链式存储

队列

  • 特点:先进先出,尾入头出
  • 初始化队列:InitQueue(Q)
  • 判队空:Empty(Q)
  • 入队:EnQueue(Q,x)
  • 出队:DeQueue(Q)
  • 读队头元素:FrontQue(Q)-----顺序存储+链式存储

仅由字符构成的有限序列,是取值范围受限的线性表。

数组

定长线性表在维数上的扩张,一般不做插入删除运算。

矩阵

  • 特殊矩阵:元素分布有一定的规律(对称矩阵、三角矩阵、对角矩阵)
  • 稀疏矩阵:非零元素远少于零元素且分布无规律,用三元组存储(行号,列号,值)

广义表

  • 表中有表
  • 表头:表中第一个元素
  • 表尾:表中除去表头剩下的部分

  • 递归的,元素之间有明显的层次关系。
  • 完全二叉树应采用顺序存储结构,一般二叉树则应采用链式存储结构
  • 二 叉 树 的 链 式 存 储 结 构:
    typedef struct BiTnode {int data; struct BiTnode *lchild, *rchild; }BiTnode, *BiTree; 
    

二叉树的遍历

  • 先序遍历(先访问根节点)
  • 中序遍历(第二访问根节点)
  • 后序遍历(最后访问根节点)
  • 层序遍历(利用队列、每次出同一层的节点时进他们的子节点层)

线索二叉树

加上线索(直接前驱和直接后继)的二叉树。

最优二叉树(哈夫曼树)

一类带权路径长度最短的树。

树的存储结构

  • 双亲表示法:顺序存储
  • 孩子表示:链式存储
  • 孩子兄弟表示:链式存储,两个指针分别为第一个孩子和下一个兄弟

一个节点的前驱节点和后继节点数目没有任何限制。

图的表示

  • G=(V,E);
  • V:顶点的集合;

边带权值的图。

图的相关概念

在这里插入图片描述

图的存储结构

  • 邻接矩阵表示法
  • 邻接链表表示法

图的遍历

  • 深度优先搜索
  • 广度优先搜索

生成树

极小连通子图,针对连通图。

最小生成树(权值和最小的生成树)算法

  • 普尼姆算法:在相邻边的基础上求最小,与边数无关,适于边稠密的网。
  • 克鲁斯科尔算法:在不构成环的基础上找最小边直至连通,与顶点数无关,适于边稀疏的网。

AOV 网

有向图中顶点表示活动,有向边表示活动间的优先关系。

拓扑排序

将 AOV 网中所有顶点按优先顺序排成一个线性序列的过程。

AOE 网

有向图中有向边表示活动,边上的权值表示该活动持续的时间。

关键路径

从源点到汇点的路径中长度最长的。

最短路径

从源点到其余各顶点的最短路径-----迪杰斯克拉算法。

平均查找长度

关键字和给定值进行过比较的记录个数的平均值。

静态查找方法

  • 顺序查找
  • 折半查找
  • 分块查找

动态查找

表结构本身在查找过程中是动态生成的。

二叉排序树

左子树上所有节点的值小于根节点的值,右子树上所有节点的值大于根节
点的值。

平衡二叉树(AVL 树)

左子树和右子树高度之差的绝对值不超过1 。

B_树(m 阶)

每个节点子树个数<=m,根节点子树个数=0 或>=2,其他节点子树个数=0
或>=m/2。

哈希表

  • 通过哈希函数(以记录的关键字为自变量)得到记录的存储地址
  • 定长按一定函数规律存放数据
  • 哈希地址+关键字

哈希表的重点

  • 构造哈希函数:直接定址法,数字分析法,平方取中法,折叠法,随机
    数法,除留余数法
    解决冲突:开放定址法,链地址法,再哈希法

简单排序

  • 时间复杂度 O( n 2 n^2 n2),空间复杂度 O( 1 1 1))
  • 直接插入排序:插入第 i 个时,前 i-1 个已经排序好
  • 冒泡排序:相邻两个比较排序,每次循环确定一个极值
  • 简单选择排序:第 i个依次与后面每个元素比较排序,每次循环确定一个极值,不稳定

高端内部排序

  • 希尔排序:先将整个序列分割成若干序列分别进行直接插入排序,再对整个序列进行一次直接插入排序,不稳定
  • 快速排序:将整个记录分割成独立的两部分,两个指针分别指向对应部分的两端,往中间移动比较排序,递归,不稳定
  • 堆排序:建立初始堆输出并删除堆顶关键字,再建立新堆得到新的关键字依次输出,不稳定
  • 归并排序:将若干个有序序列合并为新的有序序列
  • 基数排序:按组成关键字的各个数位的值进行排序

http://www.mrgr.cn/news/64203.html

相关文章:

  • 空间异质性数据分析不再复杂:地理加权回归分析、主成分分析、判别分析、分位数回归分析、线性回归等
  • Redis常见问题总结
  • 编程范式 详解
  • 墨者学院-登录密码重置漏洞分析
  • 标题安装依赖库报错 Microsoft Visual C++ 14.0 Microsoft Visual C++ 14.0编译软件包下载
  • 介绍在centos7.6使用docker安装sonarqube
  • 技术周总结10.28~11.03 周日
  • 动态规划-回文串系列——1312.让字符串变成回文串的最小插入次数
  • 祖鲁法则精要
  • 实习冲刺Day11
  • 如何利用8款工具辅助建立需求管理体系
  • CAN协议
  • 【P2-1】ESP8266 WIFI模块STA、AP、STA+AP、TCP/UDP透传工作模式介绍与AT指令介绍
  • Aicbo:解锁AI创意新纪元,一键生成视频、绘画与文字!
  • gesp的python二级题目
  • python 调用shell 脚本
  • 【机器学习】机器学习算法-线性回归算法
  • springboot河南旅游推荐系统-计算机毕业设计源码33358
  • DNS域名解析服务器--RHCE
  • Git本地分支更新推送到远程主分支上
  • 1231243545347ikih
  • 江协科技STM32学习- P33 实验-软件I2C读写MPU6050
  • 裸金属服务器和普通服务器的不同之处
  • 决策树算法
  • Java实战项目-基于 SpringBoot+Vue 的医院管理系统
  • Qt的程序如何打包详细教学