`
hideto
  • 浏览: 2675013 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

CLRS笔记10、基本数据结构

阅读更多
数学中的集合是不变的,而算法所操作的集合是可以增大、缩小或产生其他变化的,称这种集合为动态集合
支持插入元素、删除元素和测试元素是否属于集合操作的动态集合称为字典

栈和队列
栈为后进先出LIFO,队列为先进先出FIFO
栈的INSERT操作称为PUSH,DELETE操作成为POP
队列的INSERT操作称为ENQUEUE,DELETE操作称为DEQUEUE

链表
链表L中包含一个key域和两个指针域prev和next
prev指向链表中前驱元素,next指向链表中后继元素
如果prev[x]=NIL,则元素x没有前驱节点,即x为head
如果next[x]=NIL,则元素x没有后继节点,即x为tail
属性head[L]指向head,如果head[L]=NIL,则链表L为空

单链接的链表中每个元素没有prev指针
已排序的链表的线性顺序对应着链表中各元素的key的线性顺序
环形链表的head元素的prev指向tail,tail元素的next指向head

链表的Search时间为Θ(n),Insert时间为Θ(1),Delete时间为Θ(1)

哨兵(sentinel)可以用来简化边界条件
假设链表L和一个对象nil[L],它表示NIL,但有prev和next域
这样就可以将一个双向链表变成一个带哨兵的环形双向链表,哨兵元素介于head和tail之间

有根树
对二叉树T中的元素x,p[x]表示父亲,left[x]表示左儿子,right[x]表示右儿子
如果p[x]=NIL,则x为根
T的根用root[T]表示,如果root[T]=NIL,则树T为空

如果节点的子女数无限制,则无法事先知道多少域要分配
如果节点的最多子女数为常数k,那么用child1,child2,...,childk来代替left和right域,这样会浪费大量的存储空间,因为大多数节点只有少量子女

可以用left和right-sibling来表示这种树
left[x]表示x的最左孩子,right-sibling[x]表示x紧右边的孩子
如果x没有孩子,则left[x]=NIL
如果x是其父节点的最右孩子,则right-sibling[x]=NIL
分享到:
评论

相关推荐

    clrs-notes-solutions, 算法导论,第3版,学习笔记,习题答案.zip

    2. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL树和红黑树)、图(图的遍历、最小生成树、最短路径等)。 3. **递归与分治策略**:通过递归解决问题的方法,如快速排序、归并排序、汉诺塔问题、...

    Algorithms-Book:我所有笔记和数据结构和算法知识的集合。 正在施工:construction:

    数据结构和算法目的这本 Gitbook 原本是我在的所有笔记的集合, 是密歇根大学的数据结构和算法课程。 但是,我并不将本书的内容仅限于课程材料。 相反,本书旨在帮助理解算法中的数据结构。信息来源Cormen等人的...

    CLRS答案&课件

    对于复杂的算法问题,答案的解析可能会涉及数据结构的选择、时间复杂度和空间复杂度的分析,以及算法的证明和验证。 课件则可能是教授讲解课程时使用的PPT或者笔记,它们可能包含了对书中概念的可视化展示,更直观...

    算法导论的习题解答和教师手册(手册)Instructor's Manual of CLRS

    - **第14章:数据结构扩展** - 探讨如何通过对现有数据结构进行扩展来解决更复杂的问题。 - **第15章:动态规划** - 讲解动态规划这一优化问题求解技术的基础理论。 - **第16章:贪心算法** - 分析贪心算法的设计...

    CLRS:算法入门第3版中的一些练习和问题

    笔记本摘要我基础1算法在计算中的作用2入门3功能成长4分而治之5概率分析和随机算法II排序和订单统计6堆排序7快速排序8线性时间排序9中位数和订单统计III数据结构10种基本数据结构11哈希表12个二叉搜索树13棵红黑树14...

    CLRS:算法导论学习集

    4. **数据结构**:如链表、队列、栈、堆、树(二叉树、平衡树如AVL和红黑树)、图等,数据结构是算法的基础,选择合适的数据结构可以大大提高算法效率。 5. **递归与分治策略**:如快速排序、归并排序、Master定理...

    谷歌师兄的leetcode刷题笔记-Competitive-Programming-Library:竞争性编程的算法和数据结构

    谷歌师兄的leetcode刷题笔记竞争性编程库 用于竞争性编程的算法和数据结构的集合,以下任一资源中都缺少这些: - 算法简介第 3 版 (CLRS) - 竞争性编程 3 (Halim Brothers) - 竞争性编程 3 站点

    《算法导论》第二版中文全集,含:全世界唯一带“完整”目录的版本,代码。第3部分(共4部分)。学好核心技术,既为自己,也为天空不落下别国的炸弹

    数据结构教材 我强烈推荐Sartaj Sahni著《数据结构算法与应用 C++语言描述》 这是一部难得的好书 作者循序渐进 娓娓道来 每一种数据结构和算法都给出了详细的实现代码和运行结果 而且代码质量极高 甚至可以直接照搬...

    令人敬畏的竞争性编程:精选的令人敬畏的竞争性编程,算法和数据结构资源列表

    这个压缩包文件“awesome-competitive-programming-master”显然包含了一个精心挑选的资源列表,旨在帮助学习者提升他们在算法和数据结构方面的技能,从而在竞赛中取得优势。 首先,让我们关注“算法”这一主题。...

    算法导论 课后解答 教师用书

    - **主题讲解**:从哈希表到二叉搜索树,再到红黑树和增强数据结构,这一系列章节的讲座笔记深入介绍了高级数据结构的设计和优化策略。 - **解决方案**:课后解答提供了数据结构操作的详细步骤,以及如何在特定条件...

    leetcode手册JAVA-foo:富

    CS166(数据结构,2014 年Spring) CLRS(第一版) UIUC 算法笔记(作者:Jeff Erickson) 操作系统:三部曲(Remzi H. Arpaci-Dusseau 和 Andrea C. Arpaci-Dusseau) ALGS4 科学计算: 高斯消除:...

    算法 第四版

    也许对于数据结构的学习涉及的内容比较少,没有动态规划,图论也只是讲了很基础的东西,字符串中KMP弄的过于复杂(对比于acm)。但是瑕不掩瑜,对于绝大部分内容真的讲的超级清楚,完美的图解,就像单步调试一样,也许...

    MIT算法导论字幕

    这些搜索方法在解决实际问题中有着广泛的应用,如数据结构中的查找操作,网络路由,以及游戏AI等。 图算法部分,如最短路径问题的Dijkstra算法和Floyd-Warshall算法,最小生成树的Prim算法和Kruskal算法,都是图论...

Global site tag (gtag.js) - Google Analytics