离散数学和数据结构_数据结构和离散数学 - CSDN
  • 对于一个经常计算机打交道的程序员来说 有两门知识及其重要一个是离散数学一个是数据结构离散数学让我们可以用最接近计算机运行的方式去处理编写代码 对思路有着及其重要的指导作用 数据结构则可以让我们了解计算机...

    对于一个经常计算机打交道的程序员来说 有两门知识及其重要一个是离散数学一个是数据结构

    离散数学让我们可以用最接近计算机运行的方式去处理编写代码 对思路有着及其重要的指导作用
    数据结构则可以让我们了解计算机运行时数据的结构 更好的处理问题等

    最近这段时间正好有空就把《离散数学及其应用这本书》打算看几遍 看的是中文版对比英文版有很大删减

    在接触离散数学前对 或与非 已经有很多的接触 但并未正式的系统学习 所以今年计划把一些基础性的知识补习一下 为以后发展做好基础知识储备

    命题逻辑

    命题
    命题:是一个或真或假的陈述句只有一种状态
    用字母代表命题元(命题变量)

    析取 合取 非 (或与非)
    可以简单的记忆为(具体真值可以参考真值表):
    合取:当两者同真时才为真(真1)符号:∧(当初记忆时为了和∨区别 合字 上面的的人正好和∧相似 这样就很容易记住了)
    析取:有一者为真即为真(真3)符号:∨
    非:非真为假 非假为真(取反)(真2)符号:¬
    异或:两者相反即为真(真2 =析取-合取)符号:¬

    条件运算
    可以简单的记忆为(具体真值可以参考真值表):
    单条件运算:p→q时 只有p为真q为假时为假 其余为真(真3) 符号:→(读作:若…则 …)
    p→q:逆 倒置 反 (包含)
    逆: q→p (pq位置互换(逆)),
    倒置 : ┐q →┐p(先pq位置互换在取反(与p→q总是相同的真值))
    反:┐q→┐p(取反)

    双条件运算:p↔q是 当两者状态相同时为真 其余为假 亦p,q等价(真2)符号:⇔(读作:当且仅当)

    逻辑运算优先级(从高往低)
    非 合取 析取 单条件 双条件 (建议用括号包围)

    命题等价

    定义1:复合命题称为永真式(或重言式) 真值永远为假的复合命题称为矛盾
    定义2:(等价的符号<=>)
    各种逻辑等价的关系推导及罗列
    逻辑等价的关系
    对与各种逻辑等价不建议死记 学过命题逻辑后会很容易的推导出来
    这里对吸收律做证明

    1.p<=>p∨F
    2.F<=>(q∧┐q)
    3.p<=>p∨F<=>p∨(q∧┐q)<=>(p∨q)∧(p∨┐q)
    4.p∧(p∨q)<=>(p∨q)∧(p∨┐q)∧(p∨q)<=>(p∨q)∧(p∨┐q)<=>p

    逻辑等价:在所有可能的情况下都有相同真值的两个复合命题称为逻辑等价(一个简单的例子:p→q和┐p∨q逻辑等价)
    析取范式,合取范式的定义

    谓词和量词

    量词用来定义在域内取值范围 (可看做作用 变量 的范围;量词描述范围可以理解为程序中的数据类型等描述范围的概念)
    谓词用来描述(可看做方法)

    量词的分类:
    全称量词 即所有 (符号表示:∀)
    存在量词 即存在 (符号表示:∃)(唯一量词 不常用: 符号表示: ∃!)
    量词的优先级:比逻辑运算具有更高的优先级
    量词的德摩根定律
    量词的语义化翻译
    量词的嵌套

    推理规则

    定义1:命题逻辑中的一个论证是一连串的命题 除了论证中最后一个命题外都叫前提 最后的那个命题叫做结论 当它所有的前提为真意味着结论为真时 一个论证是有效的

    推理规则表
    推理规则表

    带量词的推理规则:
    全称例示:从全部得出任意个体(由大见小)
    全称生成:从任意个体得出全部(由小见大)
    存在例示:从存在得出某个个体(部分得出个体)
    存在生成:从某个个体得出存在(个体得出部分)

    一些证明及推理规则的展示

    这里就不在赘述

    展开全文
  • //图结构则头结点数组和边数结点数构成的 //头结点表结点是不一样结构的,头结点包含了一个指针域表结点 void DFS(ALGraph *G,int v)//v表示结点位置 { visited[v]=1;//置已访问标记 ArcNode *p=G->adjlist[v...
    内容太多,直接从图开始:

    //图结构则头结点数组和边数和结点数构成的
    //头结点和表结点是不一样结构的,头结点包含了一个指针域表结点
    void DFS(ALGraph *G,int v)//v表示结点位置
    {
    visited[v]=1;//置已访问标记
    ArcNode *p=G->adjlist[v].firstarc;//得到头结点的第一指针域
    while (p!=NULL)
    {
    if (visited[p->adjvex]==0)//若p->adjvex顶点未访问,递归访问它
    {
    printf("<%d,%d> ",v,p->adjvex);//输出生成树的一条边
    DFS(G,p->adjvex);//遍历的边的另一顶点作为起点,遍历与他相关且没遍历过的边,把顶点其压入栈中。
    }
    p=p->nextarc;//已遍历了则下一个表结点
    }
    }

    存储结构:

    领接矩阵:

    点元素数组

    边二位矩阵描述边是否连接信息,【下标表示元素在数组中的位置】

    点个数和边个数

    【个人说明】

    这时边的创建时由输入两个元素,

    有了点个数和边个数就可以在对图进行大小设置,只要不超过最大值

    邻接表:

    表结点:结点在数组中的位置【信息域基本不用】【又拉了一个,看十字链表知道的】指向弧头的指针域,

    头结点:元素,表结点指针域

    图:头结点数组,边数,点数

    十字链表:

    弧结点:

    该弧的尾头位置

    弧头弧尾指针域

    顶点结点:

    元素【这是肯定的O(∩_∩)O哈哈~】

    第一条入弧,出弧

    图:头结点数组,边数,点数

    图创建:

    构造头结点数组【元素数组】根据点数

    构造对应存储结构,两个元素确定一条边【十字链表是与头结点相关的,是最后进来的表结点与头结点连接的在存储结构上】

    深度优先遍历:
    先遍历与他相关的一条边,并把起点压入栈中。
    遍历的边的另一顶点作为起点,遍历与他相关且没遍历过的边,把顶点其压入栈中。
    依次循环下去。直到一个顶点与其相关的边都遍历过了。这时出栈。【出栈不是那么早的】
    遍历出栈顶点相关联的没遍历的边。循环操作。
    (简单就是遍历的顶点加入栈中,直到一个顶点所有边访问了,在出栈,在遍历出栈的顶点的其他边)。

    广度优先遍历:
    选一个顶点为起点,先遍历与他相关联的所有顶点,并把它们加入队列中。
    遍历完相关顶点后,出队,在遍历出对顶点相关联的顶点,在把它们入队。在出队,循环以上操作。
    直到队列为空。

     

    求得关结点的方式:

    其中的low的次序就是树的先根遍历得到元素的次序

    low(元素)=low[v]=Min{visited[v],low[w],visited[k]},第一个根low(根)=1

    凡是有回边都和他一样【其中w是顶点v在深度优先生成树上的孩子节点;k是顶点v在深度优先生成树上由回边联结的祖先节点】

    然后叶子几点的low[叶子]

    再根据公式基本可求得这些值了【指向双亲的树边也看成是回边】

    这些都是没有人指导下琢磨出来的

    无向图17条边,就输入17个点就行了!

    第3章 栈和队列
     3.1 栈
     3.2 栈的应有和举例
     3.3 栈与递归的实现
     3.4 队列
     3.5 离散事件模拟
    第4章 串
     4.1 串类型的定义
     4.2 串的表示和实现
     4.3 串的模式匹配算法
     4.4 串操作应用举例
    第5章 数组和广义表
     5.1 数组的定义
     5.2 数组的顺序表现和实现
     5.3 矩阵的压缩存储
     5.4 广义表的定义
     5.5 广义表的储存结构
     5.6 m元多项式的表示
     5.7 广义表的递归算法第6章 树和二叉树
    6.1 树的定义和基本术语
    6.2 二叉树
      6.2.1 二叉树的定义
      6.2.2 二叉树的性质
      6.2.3 二叉树的存储结构
     6.3 遍历二叉树和线索二叉树
      6.3.1 遍历二叉树
      6.3.2 线索二叉树
     6.4 树和森林
      6.4.1 树的存储结构
      6.4.2 森林与二叉树的转换
      6.4.3 树和森林的遍历
     6.5 树与等价问题
     6.6 赫夫曼树及其应用
      6.6.1 最优二叉树(赫夫曼树)
      6.6.2 赫夫曼编码
     6.7 回溯法与树的遍历
     6.8 树的计数
    第7章 图
     7.1 图的定义和术语
     7.2 图的存储结构
      7.2.1 数组表示法
      7.2.2 邻接表
      7.2.3 十字链表
      7.2.4 邻接多重表
     7.3 图的遍历
      7.3.1 深度优先搜索
      7.3.2 广度优先搜索
     7.4 图的连通性问题
      7.4.1 无向图的连通分量和生成树
      7.4.2 有向图的强连通分量
      7.4.3 最小生成树
      7.4.4 关节点和重连通分量
     7.5 有向无环图及其应用
      7.5.1 拓扑排序
      7.5.2 关键路径
     7.6 最短路径
      7.6.1 从某个源点到其余各顶点的最短路径
      7.6.2 每一对顶点之间的最短路径
    第9章 查找
     9.1 静态查找表
      9.1.1 顺序表的查找
      9.1.2 有序表的查找
      9.1.3 静态树表的查找
      9.1.4 索引顺序表的查找
     9.2 动态查找表
      9.2.1 二叉排序树和平衡二叉树
      9.2.2 B树和B+树
      9.2.3 键树
     9.3 哈希表
      9.3.1 什么是哈希表
      9.3.2 哈希函数的构造方法
      9.3.3 处理冲突的方法
      9.3.4 哈希表的查找及其分析
    第10章 内部排序
     10.1 概述
     10.2 插入排序
      10.2.1 直接插入排序
      10.2.2 其他插入排序
      10.2.3 希尔排序
     10.3 快速排序
     10.4 选择排序
      10.4.1 简单选择排序
      10.4.2 树形选择排序
      10.4.3 堆排序
     10.5 归并排序
     10.6 基数排序
      10.6.1 多关键字的排序
      10.6.2 链式基数排序
     10.7 各种内部排序方法的比较讨论
    第11章 外部排序
     11.1 外存信息的存取
     11.2 外部排序的方法
     11.3 多路平衡归并的实现
     11.4 置换一选择排序
     11.5 最佳归并树

    第1章 命题逻辑
    1.1 命题符号化及联结词
    1.2 命题公式及分类
    1.3 等值演算
    1.4 联结词全功能集
    1.5 对偶与范式
    1.6 推理理论
    1.7 题例分析
    习题
    第2章 一阶逻辑
    2.1 一阶逻辑基本概念
    2.2 一阶逻辑合式公式及解释
    2.3 一阶逻辑等值式
    2.4 题例分析
    习题
    第3章 集合的基本概念和运算
    3.1 集合的基本概念
    3.2 集合的基本运算
    3.3 集合中元素的计数
    3.4 题例分析
    习题
    第4章 二元关系和函数
     4.1 集合的笛卡儿积与二元关系
     4.2 关系的运算
     4.3 关系的性质
     4.4 关系的闭包
     4.5 等价关系和偏序关系
     4.6 函数的定义和性质
     4.7 函数的复合和反函数
     4.8 题例分析
     习题
    第5章 代数系统的一般性质
    5.1 二元运算及其性质
     5.2 代数系统及其子代数和积代数
     5.3 代数系统的同态与同构
     5.4 题例分析
     习题
    第6章 几个典型的代数系统
     6.1 半群与群
     6.2 环与域
     6.3 格与布尔代数
     6.4 题例分析
     习题
    第7章 图的基本概念
     7.1 无向图及有向图
     7.2 通路、回路、图的连通性
     7.3 图的矩阵表示
     7.4 最短路径及关键路径
     7.5 题例分析
     习题
    第8章 一些特殊的图
     8.1 二部图
     8.2 欧拉图
     8.3 哈密顿图
     8.4 平面图
     8.5 题例分析
     习题
    第9章 树
    9.1 无向树及生成树
    9.2 根树及其应用
    9.3 题例分析
    习题
    第10章 组合分析初步
     10.1 加法法则和乘法法则
     10.2 基本排列组合的计数方法
     10.3 递推方程的求解与应用
     10.4 题例分析
     习题
    第11章 形式语言和自动机初步
     11.1 形式语言和形式文法

    转载于:https://www.cnblogs.com/chenxuezhouLearnProgram/p/5727509.html

    展开全文
  • 我来一本推荐: 离散数学导学 http://book.jqcq.com/product/408873.html 离散数学的基本概念与基础知识,并把理论知识与一系列实际应用联系起来。主要内容包括:命题逻辑谓词逻辑、类型集合论、布尔代数、关系、...

    我来一本推荐:

    离散数学导学
    http://book.jqcq.com/product/408873.html
    离散数学的基本概念与基础知识,并把理论知识与一系列实际应用联系起来。主要内容包括:命题逻辑和谓词逻辑、类型集合论、布尔代数、关系、函数、序列、归纳法、图论、组合数学等。通过适当的教学方法,可以加深学生对离散数学的理解。本书适合所有学习离散数学的学生,并可作为相关专业的教材。

    离散数学及其应用(英文版,第4版) 离散数学及其应用(英文版,第4版)
    http://book.jqcq.com/product/303083.html
    离散数学所获得的经验基础上写出的,其目的是为学生提供准确而可读的教材,使离散数学的概念和技术得以清晰地介绍和演示。向爱怀疑的学生们展示离散数学的实用性。为计算机科学专业的学生提供一切必需的数学基矗使数学专业的学生理解数学概念的重要性以及这些概念为什么对应用而言是重要的。为教师(指导者)设计一个灵 ...

    离散数学与组合数学(第5版) 离散数学与组合数学(第5版)
    http://book.jqcq.com/product/586647.html
    离散数学是大学计算机专业最重要的必修课程之一,是许多计算机专业课程的基矗组合数学是研究图论、密码学、编码理论、算法复杂性的基本数学工具。本书是一个优秀的离散数学与组合数学的入门教材,包括计数、数理逻辑、集合论、图论、应用代数等基本内容,还有与计算技术密切相关的许多算法。作者Grimaldi教授具有极其极其 ...

    离散数学及其应用(原书第5版)
    http://book.jqcq.com/product/620737.html
    离散数学教材,为全球多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法,内容涉及数学推理、组合分析、离散结构和算法设计。全书取材广泛,除包括定义、定理的严密陈述外,还配备大量的实例和图表的说明,各种练习和题目,以及丰富的历史资料和网站资源。第5版在前四版的基础上做了大量的改进,使其成为? ...

    离散数学(第四版)
    http://book.jqcq.com/product/583297.html
    离散数学的入门教材,充分考虑到了初学者的需要,内容、例题、习题都作了精心的挑选和组织,讲解细致,叙述浅显易懂,循序渐进,用例贴近日常生活或计算机应用,并注重算法。主要内容包括集合、关系、函数、图论、组合数学、组合电路设计、有限自动机、算法、逻辑等。本书可作为计算机专业或其他相关专业的离散数学教 ...

    数据结构与STL(英文版) 数据结构与STL(英文版)
    http://book.jqcq.com/product/345529.html
    数据结构及其实现的基础知识。书中引导学生通过对方法接口、示例和应用的学习,逐渐理解和掌握如何高效地使用数据结构。适合课堂教学和自学参考。 本书特色大多数数据结构用STL(标准模板库)提供,并详细探究了STL数据结构的规范实现,同时讨论了一些数据结构的其他实现方式,可以使学生尽早接触工程实践,为未来 ...

    数据结构 C++语言描述(英文影印版)
    http://book.jqcq.com/product/306107.html
    数据结构。内容从数据结构的基本原理到面向对象程序设计的方法。书内使用适应面极广的C++语言。全书14章分别为:1.绪论;2.基本数据类型;3.抽象数据类型与类;4.集合类;5.栈与队列;6.抽象运算符;7.类属数据类型;8.类与动态存储;9.链表;10.递归;11.树;12.继承与抽象类;13.先进的非线性结构;14.构建集合。书后 ...

    计算机算法(C++版)
    http://book.jqcq.com/product/413600.html
    算法在设计与分析文献的一本经典著作。书中介绍了算法和算法性能的基本知识,基本的数据结构知识,重点讨论了不同的算法设计策略,研究了下界理论等,提供了计算机算法的设计技术和有效的算法分析,以及大量的详细实例和实际应用。同时,对NP难和NP完全问题能否有效求解进行了分析。本书还汇聚了各种随机算法与并行算法 ...

    数据结构与算法分析:C++描述(第3版) 数据结构与算法分析:C++描述(第3版)
    http://book.jqcq.com/product/431801.html
    算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析课程的教材。本科生的数据结构 ...
    参考资料:http://www.jqcq.com/forum

    (摘自 http://zhidao.baidu.com/question/35635271.html?si=5

    展开全文
  •  学数据结构之前是不是一定要学离散数学【答复】  你问了一个非常好的问题,不少初学计算机的同学该会产生这个疑问(大多数有疑问不提而已,这不是好习惯),更深层地,这里可能包含着我们的学习路线的问题,尤其...
  • 分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!&nbsp;&nbsp;&nbsp;...&a
  • 离散数学数据结构中的应用 数据结构中将操作对象间的关系分为四类:集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构,物理存储结构以及基本运算操作。其中逻辑结构和基本...
  • Java编程精选点击右侧关注,免费入门到精通!网友评论 @你是单身狗:有人数据结构好,有人离散数学好,有人计算机网络好,有人编译原理好,有人操作系统好,有人数据库原理好,...
  • 它在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等...
  • 离散数学是计算机专业的一门重要基础课。它所研究的对象是离散数量关系离散结构数学结构模型。 由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系, 因此,无论计算机科学本身,还是与...
  • JAVA数据结构——图

    2020-03-20 12:57:38
    图: 与线性结构和树形结构相比,图是一种更为复杂的数据结构,因为复杂所以也更...我们在离散数学数据结构中都接触了图的概念,但是图在生活中应用在那边呢?图的应用处于我们生活的处处面面,如:我们去超市...
  • 离散数学——树

    2016-12-22 09:43:29
    离散数学——树的概念
  • 离散数学是计算机学科中许多专业课程的先行课程,离散数学和后续课程的关系密切,它是计算机科学与技术应用与研究的有力工具,在计算机科学中应用非常广泛。 离散数学是计算机科学与技术专业许多课程,如《数据结构...
  • 它在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等...
  • 离散数学中Warshall算法简析最近学了离散数学的图论,突然感觉离散数学的作用十分强大,相信学好离散数学中的算法,编程的魅力也不言而喻。闲话不多说,这篇博客中记录的是Warshall算法的简单解析及C++代码实现。 ...
  • 离散数学是计算机专业很重要的基础课程,是后续数据结构,算法的基础。在学习数据结构的时候,接触到图论算法的时候,遇到了困难。于是决定回来学习离散数学离散数学(课本)包括了数理逻辑、集合论、计数技术、...
  •  离散数学是算法和数据结构的基础,而算法和数据结构又是什么的基础?不解释了。 1.《离散数学及其应用》作者: (美)Kenneth H. R出版社: 机械工业出版社出版年: 2007-6页数: 804定价: 79.00元丛书: 计算机科学丛书...
  • 离散数学重点概念

    2011-12-10 12:07:05
    最近数据结构学到图论了,感觉以前上的离散数学终于有提到了,于是乎,从网上拉了份离散数学的重点下来     离散数学重点概念与公式总结 命题:称能判断真假的陈述句为命题。 命题公式:若在复合命题中,p、q...
  • 其次需要把数据结构和算法好好学一下。离散数学对于算法设计非常重要,更深更难的内容建议随着编程水平的提高一步步学,而不是把这门课学精通了再回头搞编程。有些理论的东西,没有足够的实践经验是很难感受奥妙的,...
  • 数据结构部分2.离散数学部分2.1 图的基本概念2.2 图的连通性2.3 图的矩阵表示2.4 几种特殊的图2.4.1 二部图2.4.2 欧拉图2.4.3 哈密顿图2.4.4 平面图2.5 无向树2.6 生成树 1.数据结构部分 2.离散数学部分 2.1 图的...
1 2 3 4 5 ... 20
收藏数 35,202
精华内容 14,080
关键字:

离散数学和数据结构