【数据结构与算法】数据结构+算法=程序

数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：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）。

最后

通过上面一些简单的讲解，  

相信朋友们已经知道其原理及特性了。  

本人能力有限,  

如发现错误或不合理欢迎指正…

数据结构：相互之间存在关系的数据元素的集合，描述的是数据与数据之间的结构关系，数据元素之间的存在的关系会产生不同的结构，例如（数组、队列、树、图等结构），这个结构其实也就是相互之间存在关系数据元素的集合，因此也就是数据结构

算法：解决问题的步骤

一、总结：

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，他是一个抽象数据类型，更相对于编程上面；他是链表结构，更相对于数据元素上面。

（以上仅个人理解，说的不对，请谅解并留言）

最近重新学起了数据结构与算法。这些知识在实际工作中用的比较少，但这些是基础，掌握这些可以解决一些复杂业务，做出高性能系统。下面分享学习成果。

1 数据 , 数据结构 ,算法 的理解。

数据是抽象概念,在计算机语言中划分为int float double long 等基础类型。数据之间存在某种特定关系，这种关系就是结构。

数据结构是指数据对象中数据元素之间的关系(也可以理解为数据以某种形式(线性或非线性)存储)。

算法是独立存在的一种解决问题的方法和思想。

2 数据结构分为线性结构和非线性结构

2.1 线性结构根据存储结构分为顺序存储(存储空间连续)和链式存储(存储空间非连续)。

顺序存储为数组。链式存储为链表 。队列 栈(可以用顺序存储也可以链式存储表示)。

2.2非线性结构

二维数组，多维数组，广义表，树结构，图结构

 

数据结构(算法)的介绍
数据结构的介绍

数据结构是一门研究算法的学科，只从有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.
程序 = 数据结构 + 算法
数据结构(数组,队列,栈，链表,树，图)和算法的关系

算法是程序的灵魂，为什么有些网站能够在高并发，和海量吞吐情况下依然坚如磐石,大家可能会说: 网站使用了服务器群集技术、数据库读写分离和缓存技术(比如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, 因此记录了很多没有意义的数据.->稀疏数组。
稀疏数组
基本介绍
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:

记录数组一共有几行几列，有多少个不同的值(有效值的个数)

把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模



应用实例

使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)

把稀疏数组存盘，并且可以重新恢复原来的二维数组数

整体思路分析


代码实现
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)

控制台打印结果