小结美女 我想和你做朋友
走上开发这条不归路也有2年多的时间了,大学的时候数据结构低空飘过,那时候的自己以为这辈子或许都不会再和你见面了,哪知道最终还是要还债啊,那好吧,”小结美女,我们重新认识一下,我是小徐,我想和你做朋友.”
你的<数据结构>怎么学的
先举个例子,做一个银行客户排队的设计,用数据库设计了一个表,用一个自动递增的整型数字作为客户的编.来一个客户末尾插入一个数字,走一个客户,则把该数字删除.交给领导后,领导说:”你数据结构怎么学的!!!”
这个处理的方法估计是很多无数据结构基础的程序员的处理方法,那么正确的处理方法是什么呢?
针对这种实时的排队系统,通常用数据结构中的”队列结构”(虽然我还是对这个没印象)是比较好的,用数组虽然也可以,但是得考虑溢出,又要考虑新增和删除后数据的移动.
我想这个问题估计能筛选百分之80的菜鸟程序员,好吧,我 也是其中一个!!!
1.1 数据结构的起源
早期人们认为计算机就是数值计算工具,说白了就是一个计算器,在中国应该是算盘.但是在当代在现实生活中,我们更多的不是解决数值计算的问题,而是需要一些更科学有效的手段(比如表 树和图等数据结构)的帮助,才能更好的解决处理问题.
数据结构:是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间关系和操作等相关问题的科学.
1.2 基本概念和术语
巧妇难为无米之炊,这里巧妇可以看做是 计算机,那么米 就是数据.
关于数据的了解过程:数据->数据元素->数据项->数据对象
数据
定义:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并能输入给计算机处理的符号集合.
数据不仅仅包括整型 实型等数值类型,也包括字符 声音 图像 视频等非数值对象.
对于数值类型数据可以进行数值运算,而对于字符数据类型,就需要进行非数值的处理.而字符 声音 图像 视频等其实可以通过编码的手段变成字符数据来处理的.哈哈哈 大学的数字信号变换貌似就是说的这个问题,然并卵.不过理解起来更容易.
字符等数据的特点:
- 可以输入到计算机.
- 能被计算机程序处理.
数据元素
定义:是组成数据的有一定意义的基本单位,在计算机中常作为一个整体处理.
比如 人类 中的 张三 李四 等每个个体人都是数据元素,畜类 中的 猪马牛羊等.当然 人类中的 中国人 美国人 印度人等也是.
数据项
定义:一个数据元素可以由多个数据项组成.
比如 人 其数据项包括 五官等 以及姓名 年龄 性别等
- 数据项是数据不可分割的最小单位
数据对象
定义:性质形同的数据元素的集合,是数据的子集.
有点类似OC编程中的对象的理解,一对比,万法归一啊.
| 数据结构 | 数据元素 | 数据对象 |
|---|---|---|
| OC | 属性 | 对象 |
结构
定义:关系,比如分子结构.严格来说,结构指的是 各个组成部分相互搭配和排列的方式.
在现实世界中,不同的数据元素之间不是独立的,而是存在特定的关系,我们把这些关系称为结构.
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合.
1.3 逻辑结构和物理结构
按照切入点的不同,分为逻辑结构和物理结构
| – | 逻辑结构 | 物理结构 |
|---|---|---|
| 定义 | 指数据对象中数据元素之间的相互关系 | 数据的逻辑结构在计算机中的存储形式. |
| 分类 | 集合结构,线性结构,树形结构,图形结构 | 顺序存储结构,链式存储结构 |
逻辑结构分类:
- 集合结构:集合结构中的数据元素除了同属一个集合外,没有其他关系,各个元素之间是平等的.类比于数学中集合中元素之间的特点.
- 线性结构:线性结构中的元素是一对一的.
- 树形结构:树形……….之间存在一对多的层次关系.
- 图形结构:图形… …多对多的关系.
物理结构分类:
- 顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的.常见的例子:数组.
- 链式存储结构:是把数据元素存放在任意地址的存储单元里,这些存储单元可以是连续的,也可以不是连续的.数据元素的存储关系不能反映其逻辑关系,因此需要一个指针来存储数据元素的地址,这样通过指针就可以找到对应的数据元素的位置.
例子:比如去银行办理业务时,按照顺序存储结构的话,则每个人都排队站好,不插队.但是实际情况是,大家都会先领一个号码,不用排队,随便找个位置坐着,你可以中途离去,等很多情况,这样找个结构始终在变化,找个就是链式存储结构出马的时候,指针就是你取的那个号码,叫到你的号了,你就去办理自己的业务.
1.4 抽象数据类型
小结:
- 抽象数据类型把现实生活中的问题分解为多个规模小且容易处理的问题,然后建立一个计算机能处理的数据模型,并把每个功能模块的实现细节作为一个独立的单元,从而把具体的实现过程隐藏起来.
- 抽象数据结构类型体现了程序设计中问题分解 抽象和信息隐藏的过程.
为什么把这个放在前面,是因为这个跟之前了解的OC中对象的概念差不多,还是那句话,万法归一.
数据类型:
定义:指的是一组性质相同的值的集合及定义在此集合上的一些操作的集合.
抽象:
定义:指的是抽取事物具有的普遍性的本质.他是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括.抽象是一种思考问题的方式,他隐藏了繁杂的细节,只保留了实现目标多必须的信息.
抽象数据类型:
是指一个数学模型及定义在该模型上的一组操作.
