数据结构 引言

什么是IT？（测重技术）

1.信息技术（英语：Information Technology，缩写：IT）也称信息和通信技术（Information and Communications Technology，ICT），是主要用于管理和处理信息所采用的各种技术总称，主要是应用计算器科学和通信技术来设计、开发、安装和部属信息系统及应用软件。

2.在商业领域中，美国信息技术协会（ITAA）定义信息技术为“对于以计算器为基础之信息系统的研究、设计、开发、实现、维护或应用。”此领域相关的任务包括网络管理、软件开发及安装、针对组织内信息技术生命周期的计划及管理，包括软硬件的维护、升级和更新。

IT技术的前景

1.物联网 物物相连的互联网

2.丰富多彩的WEB应用

3.海量又有效率的大数据

4.计算与服务的分离--云计算 （超级计算机）

5.区块链技术--比特币与新人民币

6.人工智能开启智慧2.0时代

现代计算机的祖先

1.计算机的英文原词“computer”是指从事数据计算的人。而他们往往都需要借助某些机械计算设备或模拟计算机。例如算筹、算盘。623年德国博学家Wilhelm Schickard率先研制出了欧洲第一部计算设备，这是一个能进行六位以内数加减法，并能通过铃声输出答案的“计算钟”。使用转动齿轮来进行操作。

2.查尔斯·巴贝奇于1820年构想和设计了第一部完全可程序化计算机。但由于技术条件、经费限制，以及无法忍耐对设计不停的修补，这部计算机在他有生之年始终未能问世。约到19世纪晚期，许多后来被证明对计算机科学有着重大意义的技术相继出现，包括打孔卡片以及真空管。德裔美籍统计学家赫尔曼·何乐礼设计了一部制表用的机器，其中便应用打孔卡片来进行大规模自动数据处理。

在20世纪前半叶，为了迎合科学计算的需要，许多专门用途的、复杂度不断增长的模拟计算机被研制出来。这些计算机都是用它们所针对的特定问题的机械或电子模型作为计算基础。1930－1940年代，计算机的性能逐渐强大并且通用性得到提升，现代计算机的关键特色被不断地加入进来。

3.1941年夏天诞生的阿塔纳索夫-贝瑞计算机是世界上第一部电子计算机，它使用了真空管计算器，二进制数值，可复用内存；在英国于1943年被展示的神秘的巨像计算机（Colossus computer），尽管程序化能力极为有限，但是它使人们确信使用真空管既值得信赖，又能实现电气化的再编程；哈佛大学的马克一号；以及基于二进制的ENIAC，全名为电子数值积分计算器，这是第一部通用意图的计算机，但由于其结构设计不够弹性化，导致对它的每一次再编程都要重新连接电子线路。

 

现代计算机--冯·诺依曼式计算机

存储程序计算机在体系结构上主要特点有：

1. 以运算单元为中心：CPU中央处理器
2. 采用存储程序原理：所有的指令与数据均存放与内存中，在内存中的性质相同
3. 存储器是按地址访问、线性编址的空间：按地址访问、线性编址指的是地址是连续存储的，并且每个单元位数是固定的。
4. 控制流由指令流产生：通过执行指令直接发出控制信号控制计算机的操作。指令在存储器中按其执行顺序存放，由指令计数器指明要执行的指令所在的单元地址。指令计数器只有一个，一般按顺序递增，但执行顺序可按运算结果或当时的外界条件而改变。
5. 指令由操作码和地址码组成：操作码指明本指令的操作类型,地址码指明操作数和地址。操作数本身无数据类型的标志，它的数据类型由操作码确定。
6. 数据以二进制编码

未来计算机

1.能识别自然语言的计算机

2.高速超导计算机

3.激光计算机

4.分子计算机

5.量子计算机

6.DNA计算机

 

计算机科学的范围（测重理论）

1.计算机科学（英语：computer science，有时缩写为CS）是系统性研究信息与计算的理论基础以及它们在计算机系统中如何实现（英语：implementation）与应用的实用技术的学科。它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。

2.数据结构和算法：算法指定义良好的计算过程，它取一个或一组值作为输入，经过一系列定义好的计算过程，得到一个或一组输出。算法是计算机科学研究的一个重要领域，也是许多其他计算机科学技术的基础。算法主要包括数据结构、计算几何、图论等。除此之外，算法还包括许多杂项，如模式匹配、部分数论等。

3.计算理论:按照Peter J. Denning的说法，计算机科学的最根本问题是“什么能够被有效地自动化？”计算理论的研究就是专注于回答这个根本问题，关于什么能够被计算，去实施这些计算又需要用到多少资源。为了试图回答第一个问题，递归论检验在多种理论计算模型中哪个计算问题是可解的。而计算复杂性理论则被用于回答第二个问题，研究解决一个不同目的的计算问题的时间与空间消耗。

著名的“P=NP?”（组合爆炸）问题，千禧年大奖难题之一,是计算理论的一个开放问题。

4.信息论与编码理论:信息论与信息量化相关，由克劳德·香农创建，用于寻找信号处理操作的根本极限，比如压缩数据和可靠的数据存储与通讯。编码理论是对编码以及它们适用的特定应用性质的研究。编码（code）被用于数据压缩，密码学，前向纠错，近期也被用于网络编码。研究编码的目的在于设计更高效、可靠的数据传输方法。

5.编程语言和编译器和形式化方法等等

计算机系统层次与结构

1.硬件层

 真实存在于与冯 诺依曼体系架构当中

2.汇编层

 低级语言（机器语言），也称为汇编语言，用来与硬件层沟通。

3.操作系统层

 相当于管家，管理汇编语言，使其形成体系，用来屏蔽CPU的差距

4.虚拟机层

 屏蔽操作系统的差异，实现跨平台语言

5.软件应用层

各结构的相关关系：

硬件层为底层系统，软件应用层为最高层系统。低层系统为高层系统提供基础，而高层系统依赖于低层系统。

操作系统

1.操作系统（英语：operating system，缩写作 OS）是管理计算机硬件与软件资源的计算机程序，同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。

2.常见的操作系统：

DOS,MS-Windows,Unix,Linux，BSD，Android，IOS

虚拟机与汇编技术

1.汇编技术

编译型语言：一般需要通过编译（compile）、链接（linker）两个步骤。

编译：源码--->编译器（compiler）--->机器码

链接：把各个模块的机器码串联起来形成可执行文件。

代表语言：C、C++、Pascal、Object-C以及最近很火的苹果新语言swift。

解释型语言：不需要编译，只需将字节码（二进制）（只有虚拟机VM能识别）转换为能让CPU识别的机器码。

代表语言：JavaScript、Python、Erlang、PHP、Perl、Ruby等

注意：C语言也是解释型语言，但99.999%都是编译型语言。

按编译可分为动态语言和静态语言。

动态语言：依赖于VM，在运行时可根据某些条件改变自身结构。主要在于代码结构的变化。

代表语言：Java、Python、C#、Object-C等

静态语言：不依赖VM，直接编译，具有编译型语言的特性。

代表语言：C、C++等

按类型可分为动态类型语言和静态类型语言。

动态类型语言：是指在运行期间做类型检查的语言，说的是数据类型。它不是在编译阶段决定，是将类型绑定延后到运行阶段。

代表语言：Python、JavaScript、Ruby、PHP等

静态类型语言：是在编译期间确定的，即运行之前，编写代码时要明确确定变量的数据类型。（数据类型不可变）

代表语言：C、Java、C++、C#等

了解以上各类语言的同时，也需区分跨语言的平台和跨平台的语言。

跨语言的平台：.NET

　　.NET是微软为了抗衡Java做出的对策，它与Windows系统密切相关，包括了很多以前的语言，比如C#、C++，而这些语言都可以在.NET平台上使用。

跨平台的语言：以Python、Java为例。Python与Java都是直接面向虚拟机，而不是面向CPU；并且Python与Java均是先编译在执行的语言，它们可在所有安装了Python与Java的虚拟机电子设备上运行。

2.虚拟机

人机交互的基本工具--程序设计语言

1.语言的定义

2.程序设计语言

人与机器约定（规定）好的一套符号规则，在符号规则中有一定确定的信息，这些信息包括控制信息与数据信息。所谓的符号规则类似于数字、音频、视频等。

3.常用的程序设计语言

4.程序语言的发展历史，非结构化到结构化的跃迁

结构可分为顺序结构、分支结构、循环结构

程序的概念，离散思想与所基于的数学基础

1.程序的定义 软件  应用  

2.离散思想与数学基础

 

算法与数据结构概述

前世今身

人们在日常生活与生产的过程中，总是会遇到各种各样不理解的事物与难以理顺过程的问题。如何解决这两者，是摆在人面前的一个障碍。为了解决前者，我们会用各种各样的概念去描述一个事物，在描述的过程中，我们会对它的性质加以研究，从而区分出它的特点；而对于后者，我们则会在充分认识事物对象的基础上去找一个流程模型以解决过程的问题。这两者是很自然相关的。同样，信息技术的处理对象是信息，而在计算机与通讯的各种元件上，信息表示为各种各样的数据，无论是模拟的还是数字的。在处理数据的时候，如何描述数据与设计过程就是我们主人公————数据结构与算法要做的事情。简而言之，数据结构描述数据，而算法则是解决数据问题的过程。

定位应用

1.数据结构

数据结构解决数据的描述问题。也就是说，任何待处理的数据对象必须先找到合适的结构去描述，然后才能在计算机系统里处理它。在流行的高级语言中，如Java、python等都提供了很常用的数据结构，例如各种数据与集合框架。

2.算法

数据得以描述，目的是为了解决问题。如何针对各种各样的数据结构与问题规模去设计不同的过程解决特定的问题，这就是算法的艺术。鉴于在一个计算系统中计算资源的稀缺性，我们要设计不同的算法并且加以比较，从而选取最合适问题的算法方案去提升程序的经济性。算法如此重要，从最基本的对数据的排序问题，以及最近流行的AI技术，算法的活力从未停滞。

3.编程之禅

问题 —> 数据结构+算法 == 程序 —> 解决问题