文章 47
评论 4
浏览 11474
AVL树的创建与重构

AVL树的创建与重构

定义: 二叉搜索树: 他或是一棵空树,或是具有以下性质的树 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉搜索树。 平衡二叉树(AVL): 平衡二叉树是在二叉搜索树的基础上发展而来的,他在节点元素的大小关系上同二叉搜索树。同时左右子树的高度的差值的绝对值小于等于 1,并且左右子树都是一棵平衡二叉树。 AVL 树的基本操作: AVL 树节点定义如下 1typedef struct node 2{ 3 int data; 4 int height; 5 struct node *left, *right; 6 node(int data, int height) : data(data), height(height), left(NULL), right(NULL) {} 7} node; 插入元素(需要调整) 查找元素 删除元素 AVL 插入元素与调整 插入元素是一个递归的过程 若节点为空,则根据元素值新建节点。 否则判断插入元素的值,若大于当前节点元素值,....

最小生成树算法

最小生成树算法

引入问题 首先来看这样一个问题 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数 N(≤1000)和候选道路数目 M(≤3N);随后的 M 行对应 M 条道路,每行给出 3 个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从 1 到 N 编号。 输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出 −1,表示需要建设更多公路。 根据题目的描述,我们可以得知这是一道图论的题目,图为带权无向图,边上的权值即为题中描述的道路修建成本。 现在需要我们根据已有的图,求该图的最小(权值和最小)生成树。 这时候就需要引入解决问题的最小生成树算法了。 Prim 算法思路 首先读入所有的边,边的数据结构是一个结构体,主要包括:起点、终点、权值。 读入边之后按照边的权值由小到大排序。初始化一个数组记录边加入生成树的状态,初始时全部边为未加入。再初始化一个数组记录结点加入生成树的情况。 将某一个结点加入生成树(改变状态标志),因为所....

数据结构:线性表(番外)

数据结构:线性表(番外)

静态链表: 有时可以借助一维数组来表示线性链表 //------线性表的静态单链表存储结构------- #define MAXSIZE 1000 typedef struct { ElemType data; int cur; }component,Slinklist[MAXSIZE] 数组的一个分量表示一个结点,同时用游标(cur)代替指针指示结点在数组中的位置。在线性表的删除和插入操作时不需要移动元素,仅需要修改游标。 多项式计算: 简单的我们可以想到,用一维数组表示一个多项式,用数组的下标表示多项式中每一项的指数,用数组中每个位置上的值表示对应的系数。 但是这样存在一个问题:形如S(x) = 1 + 3x10000 – 2x20000这样的多项式,指数项的值非常大,但非零项却非常少,导致一维数组浪费的空间很大。 为此我们可以用单链表来实现。在单链表中每个结点有两个数据项(系数项和指数项)。 typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType; //多项式相加 void Add....

数据结构:线性表(2)

数据结构:线性表(2)

顺序存储: 以元素在计算机内的“物理位置”相邻来表示线性表中的数据元素的逻辑关系。 并以表中第一个元素的存储位置作为线性表的基地址。 LOC(ai ) = LOC(ai-1 ) + C LOC(ai ) = LOC(a1 ) + (i-1)×C 线性表顺序存储结构的特点 1.逻辑上相邻的元素,其物理位置也相邻; 2.可随机存取表中任一元素; 3.必须按最大可能长度预分存储空间,存储空间利用率低,表的容量难以扩充,是一种静态存储结构; 4.插入删除时,需移动大量元素,平均移动元素为n/2。 操作: 插入: Status listinsert (List &L,int i,ElenType e) { if (i<1||i>L.lenght) return error; if (L.lenght>=L.maxsize) { newbase=(ElemType*)realloc(sizeof(maxsize+newsize)*sizeof(ElemType)); if (!newbase) exit(1); L.elem=newbase; L.maxsixe+=n....

数据结构:线性表(1)

数据结构:线性表(1)

线性结构特点: 1.存在唯一的第一个“数据元素”。 2.存在唯一的最后一个“数据元素”。 3.除第一个元素外,集合中元素存在唯一后继,除最后一个元素外,集合中元素存在唯一前驱。 线性表: 1.一个线性表是n个数据结构的有序集合 2.线性表中数据元素的个数称为线性表的个数,n=0时称为空表 线性表基本操作: 结构初始化 InitList(*L) 操作结果:构造一个空的线性表 L 销毁结构 DestroyList(*L) 初始条件:线性表 L 已存在 操作结果:销毁线性表 L PriorElem( L, cur_e, *pre_e ) 初始条件:线性表 L 已存在 操作结果:若 cur_e 是 L 中的数据元素,则用 pre_e 返回它的前驱,否则操作失败,pre_e 无定义 NextElem( L, cur_e, *next_e ) 初始条件:线性表 L 已存在 操作结果:若 cur_e 是 L 中的数据元素,则用 next_e 返回它的后继,否则操作失败,next_e 无定义 ListEmpty( L ) 初始条件:线性表L已存在 操作结果:若 L 为空表,则返回 TRUE,否则返回 ....

数据结构:基础部分

数据结构:基础部分

算法: 算法是规则的有限集合,是为了解决特定问题的方法 特性: 1.有穷性、2.确定性、3.可行性、4.零或多个输入、5.一或多个输出 设计要求: 1.正确、2.可读、3.健硕、4.效率与空间 算法效率的度量: 算法中基本操作重复执行的次数记作:T(n)=O(f(n)),称为时间复杂度 一般来说他是最深层循环语句的执行次数的近似。 例如: for (i=2;i<=n;i++) { for (j=2;j<=i-1;i++) { x++; } } x++;这条语句的频度表达式为(n-1)(n-2)/2,所以该代码块的时间复杂度为O(n*n) 例外: 有些问题中,基本语句的重复执行次数还与问题的输入有关,这种情况下,一种方法是计算时间复杂度的平均值,另一种更常用的方法是讨论算法在最坏情况下的时间复杂度。

闻道