Go转型——数据结构初级(一)

yinshidaoshi · · 1484 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

**1**.数据结构基本概念 在计算机中,我们可以用一个由若干“位”组合起来形成的一个位串来表示一个数据元素,比如,用一个字长的位串来表示一个整数,用八位二进制数字来表示一个字符,我们管这种位串叫**元素**或**节点**。当数据元素由若干数据项组成时,位串对应数据项的子位串称为**数据域**。 数据元素之间的关系可以分为两种不同的表示方式:**顺序映象**和**非顺序映象**。并且得到了两种存储结构:**顺序存储结构**和**链式存储结构**。 顺序映象的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系,而非顺序映象利用指示数据元素存储地址的指针来表示数据元素之间的逻辑关系,日常一图顶千言: ![image.png](https://static.studygolang.com/180119/f784c747076724bfe443af8d7c245692.png) 如果用着两种存储结构表示z=3.0-2.3i, 结果应为 a :0300 0302 b :0611 0415 **2**.如何描述存储结构 我们可以借助高级语言中都有的一维数组来描述**顺序存储结构**,借助C语言中的指针来描述**链式存储结构**, **3**.简述数据类型 **数据类型**最早出现在高级程序语言中,用以刻画操作对象的特性,因此数据类型是一个值的集合和定义在这个集合上的一组操作的总称。例如:C语言中的整型变量,值的集合为某个区间上的整数(区间由机器决定),定义在七上的操作为,加、减、乘、除和取模等算数操作。 根据“值”的不同特性,高级编程语言中的分为两类: (1).**非结构的原子类型**:原子类型值都是不可分解的,例如C语言中的基本类型(整型、实型、字符型和枚举型)、指针类型和空类型。 (2).**结构类型**:结构类型的值是由若干成分按某种结构组成的,换而言之,值是可分解的。而且它的成分可以是结构的,也可以是非结构的。 **4**.简述抽象数据类型,并说明它与数据类型的关系。 **抽象数据类型**.是指一个一个数学模型以及定义在该模型上的操作,抽象数据类型的定义仅取决于它的一组逻辑特性,而与他在计算机内部如何表示和实现无关,即无论其内部结构不发生变化,只要他的数学特性不发生变化,都不影响其外部的使用。 抽象数据类型与数据类型本质上是一个概念,抽象的意义在于数据类型的数学抽象特性,另一方面抽象数据类型范畴更广,不再局限于各大处理器已经定义并实现的数据类型(也可以称之为固有数据类型) 抽象数据类型 根据值的不同可以分为三种, (1).**原子类型**:属于原子类型的变量的值都是不可分的, (2).**固定聚合类型**:属于该类型的变量值由数目确定的成分按一定结构组成, (3).**可变聚合类型**:与固定聚合类型相比,组成其值的成分数目不确定, 日常一图胜千言 ![image.png](https://static.studygolang.com/180120/50787e823bdfecef25fbbb9a4882587a.png) **5**.如何描述算法,浅谈对算法设计的基础理解 **算法**:是指令的有限序列,其中每条指令都是表示一个或多个操作,一个算法应包含如下特性: **(1)**:**有穷性**:一个算法应在执行有穷步后结束,且每一步都在有穷时间内完成 **(2)**:**确定性**:算法中每一条指令的含义都必须是确定的,读者阅读不会产生歧义,任何情况下,算法只有唯一的一条执行路径,即对相同的输入值只能得出相同的输出 **(3)**:**可行性**:即算法是可以通过已经实现的基本操作执行有限次数来实现的 **(4)**:**输入**:一个算法有多个或零个输入,这些输入取自某个特定的集合 **(5)**:**输出**:一个算法有一个或多个输出,这些输出与输入一样,具有某些相同的关系 **算法设计**:衡量一个算法设计是否达到“好”的标准有以下这些: **(1)**:正确性:即算法应当满足当前需求,这个正确性不同于我们日常所说的“正确”,这个正确性大致分为四层: **a**.程序不包含语法错误 **b**.程序对于几组输入数据能够给出满足要求的结果 **c**.程序对于精心挑选、苛刻带有刁难性的几组数据能够给出满足要求的结果 **d**.程序对于任何合法输入的数据能够给出满足要求的结果 显然,一个算法达到d级是相当困难的,所以一般达到c级就被认为是合格的 **(2)**:可读性:算法首先是为了人之间的交流,其次才是机器执行,可读性意味着更易于阅读理解,更容易调试和修改 **(3)**:健壮性:当输入数据非法时,算法也能进行适当的反应,不会产生莫名其妙的结果 **(4)**:效率和低存储量需求:效率是指算法执行的时间,对于一个问题如果有多个算法能够解决问题,那么执行时间最短的算法效率最高。存储量需求指的是算法执行需要的最大存储空间,这两个因素都与问题规模有关,例如,求1000人的平均分和10000人的平均分 **6**.算法效率的度量 算法执行时间由机器执行算法运行消耗的时间来度量,衡量一个算法执行时间通常有两种方式: **(1)**.事后统计的方法,不同的算法可以通过相同的数据输入来测试执行时间,但这种方法一,必须先运行算法程序,二,主要依赖计算机的硬件软件等因素,对结果影响较大,所以通常使用另一种方式; **(2)**.事前分析估算的方法。高级程序语言编写的程序在计算机上运行所消耗的时间主要取决于以下几个因素: **1**.依据的算法根据何种策略略 **2**.问题的规模,例如上文提到的求平均分的人数,是1000还是100 **3**.书写程序的语言,对于同一个算法来说,语言等级越高,执行效率越低 **4**.编译程序所产生的机器代码质量 **5**.机器执行指令的速度。 由此可见,根据执行时间来衡量算法效率绝对不是可靠的,因为他们或多或少都依赖于机器、语言,这些外界因素对于我们的结果影响过大,所以我们需要一个没有外界因素干扰,撇开这些因素,可以认定一个特定算法运行工作量的大小,单纯的依赖问题的规模,或者说他是问题规模的函数。 一个算法是由控制结构(顺序、分支和循环)和固有数据类型的操作构成的,算法的时间取决于这两者的综合效果, ![image.png](https://static.studygolang.com/180120/916f89312104326aa14a2889f9f7917d.png) 例如: **(a)**.{x++} **(b)**.for i:=0;i<n;i++{x++} **(c)**.for i:=0;i<n;i++{ for j:=0;j<n;j++{x++}} (a)中x++语句重复执行的次数(即频度)为1, 所以时间复杂度为O(1),这种类型也被称为常量阶; (b)中x++语句重复执行的次数(即频度)为n, 所以时间复杂度为O(n),这种类型也被称为线性阶; (c)中x++语句重复执行的次数(即频度)为n*n, 所以时间复杂度为O(n²),这种类型也被称为平方阶; 除上述三种情况,时间复杂度还可能为对数阶O(log n),指数阶O(n²),各时间复杂度性状如下图所示, ![image.png](https://static.studygolang.com/180120/52420c6ce5f79d77a590e4f43719b38c.png) 由此可知,我们应该多用多项式阶O(nⁿ k次方打不出来,用n代替)算法,而不希望使用指数阶的算法。 **7**.空间复杂度的度量 类似于时间复杂度,我们用空间复杂度来作为算法所需存储空间的度量,也就是: ![image.png](https://static.studygolang.com/180120/9f05c8d281dcdb8d0fafc13c5496b53e.png) n为问题的规模,一个上机执行的程序除了需要存储空间来寄存本身所用的输入数据,也需要一些对数据操作的工作单元和存储一些为实现计算所需的信息的辅助空间。

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1484 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传