【算法设计zxd】第一章 算法基础 5.基本数据结构

致命小学期 2022-06-23 17:51:04 阅读数:353

算法设计第一第一章zxd

目录

思考题:学过的数据结构及其特点

(1)线性数据结构

(2) 树

(2) 树—二叉树

(3) 图

(3) 图—表示方法.邻接矩阵法

(3) 图—表示方法.邻接表


思考题:学过的数据结构及其特点

线性是一种结构。

线性表里还有分类。

实现:数组,链表(单链表,)

非线性结构:树:(特点:只有一个双亲)

(1)线性数据结构

线性表、栈(LIFO)、队列(FIFO)

(2) 树

树(Tree)是n(n≥0)个结点的有限集。在任意一棵非空树中:

有且仅有一个特定的称为根的结点;

②当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…Tm,其中每一个集合本身又是一棵树,并且称为根的子树;

③T1,T2,…Tm也可能会有若干不相交的子树T1,1,T1,2……Tm,k,依次类推。

(2) 树—二叉树

性质1】 在二叉树的第i层至多有2^(i-1)个结点(i≥1)。

【性质2】 深度为k的二叉树至多2^(k) - 1个结点(k≥1)

【性质3】 具有n个结点的完全二叉树的深度为⌊log_2 n⌋+1

由这一性质可知,任意具有n个结点的二叉树,其高度h满足下列不等式。

⌊log_2 n⌋ ≤ h ≤n−1

二叉树的表示方法:

typedef struct BiTNode{
TElemtype data; //结点信息
Struct BiTNode *lchild, *rchild; //左孩子,右孩子
}BiTNode, *BiTree;

(3) 图

G=(V, E)

如果(v, u)∈VR,则(v, u)表示从v到u的一条弧,v为弧尾,u为弧头,此时称图G为有向图

 v弧尾->u弧头

如果(v, u)∈VR必有(u, v)∈VR,即VR是对称的,以无序对(v, u)代替两个有序对(v, u)和(u, v),则(u, v)表示一条边,称图G为无向图

边、弧、邻接、关联、度(Degree)、入度(InDegree)、出度(OutDegree)

(3) 图—表示方法.邻接矩阵法

V: VNode v[n]; //顶点
VR: weight vr[n][n]; //邻接矩阵
typedef struct VNode{
elementtype vertex; //顶点数据
}VNode, v[4];
weight vr[4][4]= { 0, 1, 1, 1,
1, 0, 1, 1,
1, 1, 0, 1,
1, 1, 1, 0 };

(3) 图—表示方法.邻接表

 顶点

V:
typedef struct VNode{ //顶点结构
vertextype data;
struct adjvex * firstedge; //边链表
}VNode, v[n];

 邻接表

VR:
struct adjvex{
int seqNo;
struct adjvex *next;
};

版权声明:本文为[致命小学期]所创,转载请带上原文链接,感谢。 https://blog.csdn.net/iivan_cpp/article/details/122632249