-
【数据结构与算法】数据结构+算法=程序
2016-02-17 23:41:43【数据结构与算法】数据结构+算法=程序 数据结构 计数机的处理能力来源于cpu, 通过计算机汇编语言(Assembly Language)进行运算工作,cpu只可以做一些简单的二进制操作. 那么问题来了 ? 计算机如何处理 视频/mp3等应用...【数据结构与算法】数据结构+算法=程序
- 数据结构
-
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为:Data_Structure=(D,R)其中D是数据元素的集合,R是该集合中所有元素之间的关系的有限集合。
- 计数机的处理能力来源于cpu, 通过计算机汇编语言(Assembly Language)进行运算工作,cpu只可以做一些简单的二进制操作. 那么问题来了 ? 计算机如何处理 视频/mp3等应用的呢?这个时候数据结构“诞生”了.将视屏mp3的二进制数据按照特定的数据结构封装 .
- 算法
-
算法的设计取决于数据(逻辑)结构,而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现,为了全面的反映一个数据的逻辑结构,它在存储器中的映象包括两方面内容,即数据元素之间的信息和数据元素之间的关系。不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法,如检索、插入、删除、更新和排序等。
- 有了数据结构计算机是完全可以 “欣赏” 视频mp3的二进制了 . 但是人是不希望看到二进制的,人们希望看到的是多媒体. 这个时候算法就应运而生了,也成为了数据以友好的方式展现在人们面前的桥梁 .
- 【数据结构与算法】= 程序
-
尼古拉斯·沃斯
他有一句在计算机领域人尽皆知的名言“算法+数据结构=程序”(Algorithm+Data Structures=Programs) -
荣誉
1984 年获得了图灵奖
图灵奖在我的上一篇文章也做了相应的介绍.
凡是学过一点计算机的人大概都知道“算法+数据结构=程序”这一著名公式。提出这一公式并以此作为其一本专著书名的瑞士计算机科学家尼克劳斯·威茨(Niklaus Wirth)于1984 年获得了图灵奖。这是瑞士学者中唯一获此殊荣的人。他是好几种编程语言的主设计师
Algol W Modula Pascal Modula-2 Oberon
他亦是Euler语言的发明者之一。1984年他因发展了这些语言而获图灵奖。他亦是Lilith电脑和Oberon系统的设计和执行队伍的重要成员。
他的文章Program Development by Stepwise Refinement视为软体工程中的经典之作。他写的一本书的书名Algorithms + Data Structures = Programs(算法+数据结构=程式)是计算机科学的名句。
欧洲人通常都将他的名字读得正确,读作“Nih-klaus Virt”;但美国人通常读成“Nickles Worth”近似的音。於是有人便说,欧洲人传址呼叫他,美国人传值呼叫他。沃斯的学术著作
主要有如下几种,其中一些是由法文译成英文的:《系统程序设计导论》(《Systematic Programming:An Introduction》,Prentice-Hall,1973。其法文版已出至第5版) ;
《算法 数据结构=程序》(《Algorithms Data Structures=Programs》,Prentice-Hall,1976)。
《算法和数据结构》(《Algorithms and Data Structures》,Prentice-Hall,1986)。
《Modula-2程序设计》(《Programming in Modula-2》, Springer,1988,第4版)。
《PASCAL用户手册和报告:ISO PASCAL标准》 (《PASCAL User Manual and Report:ISO PASCAL Standard》,Springer,1991)。
《Oberon计划:操作系统和编译器的设计》(《Project Oberon:the Design of an Operating System and Compiler》,ACM Pr.,1992)。
《Oberon程序设计:超越Pascal和Modula》(《Programming in Oberon:Steps beyond Pascal and Modula》,ACM Pr.,1922)。
《数字电路设计教材》(《Digital Circuit Design for Computer Science Students:An Introductory Textbook》,Springer,1995)。最后
通过上面一些简单的讲解,
相信朋友们已经知道其原理及特性了。
本人能力有限,
如发现错误或不合理欢迎指正…
-
程序 = 数据结构+算法 的理解(数据结构、算法、抽象数据类型)
2019-06-04 10:47:21数据结构:相互之间存在关系的数据元素的集合,描述的是数据与数据之间的结构关系,数据元素之间的存在的关系会产生不同的...数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界,首先二者表现为不可分割的关系...数据结构:相互之间存在关系的数据元素的集合,描述的是数据与数据之间的结构关系,数据元素之间的存在的关系会产生不同的结构,例如(数组、队列、树、图等结构),这个结构其实也就是相互之间存在关系数据元素的集合,因此也就是数据结构
算法:解决问题的步骤
一、总结:
1、程序 = 数据结构 + 算法 。数据是程序的中心。数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界,首先二者表现为不可分割的关系。没有数据间的有机关系,程序根本无法设计。
2、数据结构与算法关系:数据结构是底层,算法高层。数据结构为算法提供服务。算法围绕数据结构操作。
3、解决问题(算法)需要选择正确的数据结构。例如:算法中经常需要对数据进行增加和删除用链表数据结构效率高,数组数据结构因为增加和删除需要移动数字每个元素所有效率低。
4、数据结构特点:每种数据结构都具有自己的特点。例如:队列:先进先出。栈:先进后出。等等
5、算法的特性:算法具有五个基本特征:输入、输出、有穷性、确定性和可行性。
6、数据结构应用:数据结构往往同高效的检索算法、索引技术、排序算法有关
7、数据结构(逻辑数据结构)通过计算机语言来实现数据结构(存储数据结构)。例如:树型数据结构:通过计算机语言中的数组(节点)和指针(指向父节点)来实现。
8、存储结构:逻辑数据结构的实现。存储结构通过计算机语言实现。 例如:堆数据结构,堆是一棵完全二叉树,所以适宜采用顺序存储结构(顺序存储:数组),这样能够充分利用存储空间。
9、算法目的:算法是为数据结构服务。例如:数据结构通常伴随有查找算法、排序算法等
10、数据结构的优劣:一种数据结构的优劣是在实现其各种运算的算法中体现的。
二、数据结构:分为逻辑数据结构和存储数据结构两种
(1)顺序存储方法(顺序存储结构)
(2)链接存储方法(链式存储结构)
同一种逻辑结构可采用不同的存储方法(以上两种之一或组合),这主要考虑的是运算方便及算法的时空要求。参考https://www.cnblogs.com/chenweichu/p/6394026.html
三、个人理解:
数据结构:相互之间存在关系的数据元素的集合,描述的是数据与数据之间的结构关系,数据元素之间的存在的关系会产生不同的结构,例如(数组、队列、树、图等结构),这个结构其实也就是相互之间存在关系数据元素的集合,因此也就是数据结构
算法是解决特定问题的有限求解步骤。
数据结构为算法提供服务。算法围绕数据结构操作
问题的求解,需要合适的数据结构,需要合适的算法,才能完美的将一个问题解决好。
所以,某位学者将“程序 = 数据结构 + 算法” 是有道理的。
四、为什么数据元素之间的存在的关系会产生不同的结构呢?
存储结构:逻辑数据结构的实现。存储结构通过计算机语言实现。
也就是说,数据结构之间存在的关系产生逻辑数据结构,逻辑数据结构的实现进而实现了物理数据结构。因此,数据结构之间存在的关系会产生逻辑数据结构和物理数据结构。
举个例子,逻辑结构中的线性结构中的线性表,有两种表示方式:顺序表和链表,实现之后就存在顺序表示和链接表示的两种物理结构。
五、什么是抽象数据类型?
数据结构操组的对象是数据元素,即他们有相同的属性(属性也取决于观察者的角度),它们之间的存在的关系会产生不同的结构,数据元素之间的关系+操作构成了数据类型,对已有的数据类型进行抽象就构成了抽象数据类型(ADT),就是封装了值和操作的模型。
举个例子,在C语言里面,我们要用链表,栈,都会定义链表、栈、线性表的类型,这些类型具有数据元素的关系和操作,其实这些类型就是抽象数据类型。
struct Node;
typedef struct Node * PNode; //结点类型
struct Node
{
int data;
PNode next;
};
typedef struct Node * List; //链表类型 ,这个是抽象数据类型我们要使用单链表这个数据结构来解决问题的前提是首先得创建一个单链表数据结构。创建单链表数据结构,就得自定义个单链表的抽象数据类型,抽象数据类型只是对数据结构定义一组逻辑操作,没有具体的实现。在实际应用中,必须实现这个抽象数据类型,才能使用它们,而实现抽象数据类型依赖于数据存储结构。
六、抽象数据类型似乎有点像数据结构?
对,确实很像,但要在不同的角度上看,抽象数据类型角度来看,他是一个数据类型,从数据结构来看,他是一个数据元素的集合。例如,链表List,他是一个抽象数据类型,更相对于编程上面;他是链表结构,更相对于数据元素上面。
(以上仅个人理解,说的不对,请谅解并留言)
-
程序=数据结构+算法
2020-08-22 14:58:52最近重新学起了数据结构与算法。这些知识在实际工作中用的比较少,但这些是基础,掌握这些可以解决一些复杂业务,做出高性能系统。下面分享学习成果。 1 数据 , 数据结构 ,算法 的理解。 数据是抽象概念,在计算机...最近重新学起了数据结构与算法。这些知识在实际工作中用的比较少,但这些是基础,掌握这些可以解决一些复杂业务,做出高性能系统。下面分享学习成果。
1 数据 , 数据结构 ,算法 的理解。
数据是抽象概念,在计算机语言中划分为int float double long 等基础类型。数据之间存在某种特定关系,这种关系就是结构。
数据结构是指数据对象中数据元素之间的关系(也可以理解为数据以某种形式(线性或非线性)存储)。
算法是独立存在的一种解决问题的方法和思想。
2 数据结构分为线性结构和非线性结构
2.1 线性结构根据存储结构分为顺序存储(存储空间连续)和链式存储(存储空间非连续)。
顺序存储为数组。链式存储为链表 。队列 栈(可以用顺序存储也可以链式存储表示)。
2.2非线性结构
二维数组,多维数组,广义表,树结构,图结构
-
Scala数据结构和算法:数据结构(算法)介绍,稀疏数组,一个五子棋程序保存代码
2019-09-19 21:58:01数据结构(算法)的介绍 ...程序 = 数据结构 + 算法 数据结构(数组,队列,栈,链表,树,图)和算法的关系 算法是程序的灵魂,为什么有些网站能够在高并发,和海量吞吐情况下依然坚如磐石,大家可能会说...数据结构(算法)的介绍
数据结构的介绍
数据结构是一门研究算法的学科,只从有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.
程序 = 数据结构 + 算法
数据结构(数组,队列,栈,链表,树,图)和算法的关系
算法是程序的灵魂,为什么有些网站能够在高并发,和海量吞吐情况下依然坚如磐石,大家可能会说: 网站使用了服务器群集技术、数据库读写分离和缓存技术(比如Redis等),那如果我再深入的问一句,这些优化技术又是怎样被那些天才的技术高手设计出来的呢?大家请思考一个问题,是什么让不同的人写出的代码从功能看是一样的,但从效率上却有天壤之别, 拿在公司工作的实际经历来说, 我是做服务器的,环境是UNIX,功能是要支持上千万人同时在线,并保证数据传输的稳定, 在服务器上线前,做内测,一切OK,可上线后,服务器就支撑不住了, 公司的CTO对我的代码进行优化,再次上线,坚如磐石。那一瞬间,我认识到程序是有灵魂的,就是算法。如果你不想永远都是代码工人,那就花时间来研究下算法吧!
本章着重讲解算法 的基石-数据结构。看几个实际编程中遇到的问题
Scala代码:def main(args: Array[String]): Unit = { val str = "scala,scala, hello,world!" val newStr = str.replaceAll("scala", "尚硅谷") println("newStr=" + newStr) //暴力匹配=>KMP算法 }
看几个实际编程中遇到的问题
一个五子棋程序:
?如何判断游戏的输赢,并可以完成存盘退出和继续上局的功能约瑟夫问题(丢手帕问题)
Josephu 问题Josephu 问题为:设编号为1,2,… n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m 的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
提示:用一个不带头结点的循环链表来处理Josephu 问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。其它常见算法问题:
邮差问题
最短路径问题
汉诺塔
八皇后问题
稀疏sparsearray数组
先看一个实际的需求
编写的五子棋程序中,有存盘退出和续上盘的功能。
分析问题:
因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.->稀疏数组。稀疏数组
基本介绍
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
记录数组一共有几行几列,有多少个不同的值(有效值的个数)
把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
应用实例
使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)
把稀疏数组存盘,并且可以重新恢复原来的二维数组数
整体思路分析
代码实现
package datastructure import scala.collection.mutable.ArrayBuffer /** * @author cherry * @create 2019-09-16-22:33 */ object SparseArrayDemo { def main(args: Array[String]): Unit = { //先使用二维数据,映射棋盘 val rows = 11 //棋盘行数 val cols = 11 //列数 val chessMap: Array[Array[Int]] = Array.ofDim[Int](rows, cols) //初始化 chessMap(1)(2) = 1 //表示黑子 chessMap(2)(3) = 2 //表示蓝子 println("原始的棋盘") for (row <- chessMap) { for (item <- row) { printf("%d ", item) } //换行 println() } /** * 对原始的二维数据进行压缩 * 思路: * 1.创建一个ArrayBufffer,可以动态添加数据 * 2.使用Node对象,表示一行数据 */ val sparseArray: ArrayBuffer[Node] = ArrayBuffer() //先将第一行数据放入 sparseArray.append(new Node(rows, cols, 0)) //遍历chessMap,如果发现有非0的值,创建一个Node对象,并加入到spareArray for (i <- 0 until chessMap.length) { for (j <- 0 until chessMap(i).length) { if (chessMap(i)(j) != 0) { //有效数据需要保存 sparseArray.append(new Node(i, j, chessMap(i)(j))) } } } println("稀疏数组的情况是:") for (i <- 0 until sparseArray.length) { val node: Node = sparseArray(i) printf("%d %d %d\n", node.row, node.col, node.value) } /** * 将悉数数组恢复到原盘 * 思路: * 1.读取稀疏数组的第一行,创建一个二维棋盘 * 2.遍历(从悉数数组的第二行),每读取到一个node,就将对应的值恢复到chessMap2 */ val node: Node = sparseArray(0) val chessMap2: Array[Array[Int]] = Array.ofDim[Int](node.row, node.col) for (i <- 1 until sparseArray.length) { val node2: Node = sparseArray(i) chessMap2(node2.row)(node2.col) = node2.value } println("恢复的棋盘") for (row <- chessMap2) { for (item <- row) { printf("%d ", item) } //换行 println() } } } class Node(val row: Int, val col: Int, val value: Int)
控制台打印结果
-
图解数据结构与算法
2020-07-27 10:56:16数据结构和算法是程序的基础,没有系统地学习过数据结构和算法的程序员只能称作是coder,知道我们写的代码使用了什么数据结构,它的特征是什么。知道解决某些问题是用的何种算法才会从coder晋升为工程师。 另外,... -
数据结构与算法1:数据结构与算法介绍
2019-10-09 10:20:49文章目录数据结构定义逻辑结构与物理结构抽象数据类型常见的数据结构算法(Algorithm)算法设计的要求算法时空复杂度基本算法推荐书单 数据结构定义 数据结构是一门研究非数值计算的程序...程序设计=数据结构+算法 基... -
数据结构、算法、程序的关系
2020-06-02 01:14:18这里写目录标题初衷数据结构、算法、程序的联系 初衷 数据结构、算法、程序的联系 数据结构 = 数据 + 结构 算法 = 算 + 法 程序 = (流)程 + (顺)序 反爬虫措施,读者略过: 转载请标明转自:... -
关于程序=数据结构+算法
2020-04-06 17:09:50程序=数据结构+算法,这个早就看到了,很多人也说了,谭浩强的C语言里面也有。 而且我发现计算机考研里面的算法题是夹杂着数据结构的题去考的。 我现在渐渐感受到他们所说的算法和我以前所理解的算法可能不是一... -
Java数据结构与算法(一、初识数据结构与算法)
2020-01-26 11:39:481. 经典的算法面试题介绍 经典的面试题 ...解决的算法 ...(KMP算法) ...(分治算法) ...数据结构是算法的基础,算法是程序的灵魂 3. 数据结构的分类 种类 常用结构 线性 (4... -
数据结构和算法(数据结构和算法简介)
2019-04-26 08:12:35程序设计 = 数据结构 + 算法 数据结构分为逻辑结构和物理结构 逻辑结构:是指数据对象中数据元素之间的相互关系,也是我们今后最需要关注和讨论的问题 物理结构:是指数据的逻辑结构在计算机中的存储形式 逻辑... -
数据结构知识整理3算法基本概念、数据结构+算法=程序
2019-02-15 15:15:11算法是在具体存储结构上实现某个抽象运算。确切地说,算法是对特定的求解步骤的一种描述,它是指令地有限序列,其中每一条指令表示计算机的一个或多个操作。 算法五个重要的特性:1.有穷性2.确定性3.可行性4.有输入... -
数据结构与算法1——简单介绍数据结构和算法
2019-07-30 14:52:25—— 程序设计 = 数据结构 + 算法 —— 再简单的来说数据结构就是关系,没错,就是数据元素之间存在的一种或者多种特定关系的集合。 (比如说人与人之间就有剪不断理还乱的关系。) 二、逻辑结构和物理结构 逻辑结构... -
数据结构+算法=程序设计
2020-08-06 12:11:24文章目录程序设计:为计算机处理问题编制的一组指令集数据结构:问题的数学模型数据数据元素(数据结构中讨论的基本单位)数据结构数据结构的形式定义 (逻辑结构): 二元组 Data_Structure(D,S)逻辑结构在计算机中... -
【数据结构自学笔记】程序=数据结构+算法
2019-08-26 14:36:21数据结构自学笔记 -
数据结构与算法经典书籍——大话数据结构(带配套源码)
2018-10-26 00:20:03配套程序链接:https://pan.baidu.com/s/1HYka42KngWT2el7T0HO7LA 密码:i6hw 虽说数据结构以美国人Mark Allen Weiss 写的《数据结构与算法分析——C语言实现》最好,但是我发现他的书让人很不容易理解,可能我们... -
深入理解程序=数据结构+算法
2018-09-18 20:57:23程序=数据结构+算法 研究程序---研究数据对象有哪些?用什么样的存储方式去存储这些数据对象?为数据对象选择什么样的存储类型? ------需要执行的操作有哪些?这样的操作用什么样的算法好一些呢? 什么样的算法... -
图解Java数据结构和算法
2019-06-21 10:09:161.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题:1)授课方式单一,大多是照着代码念一遍,数据结构和算法... -
【Python数据结构与算法复习day44】1-08数据结构引入+程序等于算法加数据结构+数据结构的概念+算法与数据...
2020-02-08 21:09:151-08数据结构引入 文章目录1-08数据结构引入补充说明 补充说明 尽量少用加号,list+list的时候效率很低,+=符号的话和extend的效率差不多了,已经有优化了。 ... -
程序设计实践:基础数据结构与算法
2020-06-16 09:35:09算法和数据结构是程序的基石,几乎每一个程序都需要它们,但绝大多数程序都不需要发明新的算法和数据结构。 本章基本是围绕着对HTML中name-value键值对的处理,阐述了满足于绝大多数程序需求的基本算法和数据结构,... -
程序=算法+数据结构
2020-11-09 09:55:05❝程序=算法+数据结构❞这是一句非常著名的话,凭借这一句话直接获得图灵奖,可想数据结构和算法有多重要。同时,在各个大厂招聘面试时,也会提到数据结构和算法。❝你知道什么什么数据结构吗查找、... -
数据结构与算法是程序的灵魂
2016-02-24 14:51:07编程之久除了算法和数据结构,什么也不属于我们。 听到一句这样的话,为迷茫的我指明了道路。所以,要好好学习数据结构与算法。 -
数据结构与算法必知基础知识
2021-01-06 22:58:12数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低... -
数据结构与算法
2013-09-20 23:22:56数据结构和算法在计算机学科中的地位十分重要,简单来说“数据结构+算法=程序”。其他计算机科学领域及有关的应用软件都要使用到各种数据结构。几乎涉及到计算机的地方都离不开数据结构。而数据结构有助于程序员更... -
数据结构与算法—前导
2019-07-25 23:53:34数据结构与算法是程序员内功体现的重要标准之一,而数据结构的也应用在各个方面,更有程序=数据结构+算法这个被人认证的等式存在。并且数据结构与算法的应用无处不在,各个中间件开发者,架构师。他们都在努力的优化... -
python数据结构与算法 pdf_数据结构与算法:Python语言描述.pdf
2020-11-23 23:38:43本书基于Python语言介绍了数据结构与算法的基本知识,主要内容包括抽象数据类型和Python面向对象程序设计、线性表、字符串、栈和队列、二叉树和树、集合、排序以及算法的基本知识。本书延续问题求解的思路,从解决... -
数据结构 实践项目——数据结构、算法、程序设计
2015-08-29 21:17:51方便以后各章,我们就某一数据结构定义算法库,并能引用算法库进行实践。 最简单的多文件组织,一个项目中有3个文件: (1) .h 头文件:定义数据类型、声明自定义函数、定义宏等 (2).cpp 源文件1:用于... -
[数据结构与算法] 排序算法
2020-02-06 17:12:02程序= 数据结构+算法 排序算法 排序也称排序算法(Sort algorithm). 是指 将一组数据按照指定顺序进行排列的过程 主要分为内部排序和外部排序 内部排序: 指将需要处理的数据加载到内存中进行排序 外部排序...