asunquan.com

不忘初心 不止于行

职场新人 iOS菜鸟 就职于搜狐畅游 从事iOS/tvOS的SDK开发 对于游戏市场有点点了解 平日和一只小Corgi同吃同睡


数据结构学习笔记(一)--绪论

[TOC]

绪论

什么是数据结构

一般来说, 用计算机解决一个具体问题时, 大致需要经过下列几个步骤: 首先要从具体问题抽象出一个适当的数学模型, 然后设计一个解此数学模型的算法, 最后编出程序, 进行测试, 调整直至得到最终解答. 需求数学模型的实质是分析问题, 从中提取操作的对象, 并找出这些操作对象之间含有的关系, 然后用数学的语言加以描述.

数据结构在计算机科学中是一门综合行的专业基础课, 数据结构的研究不仅涉及到计算机硬件(特别是编码理论, 存储装置和存取方法等)的研究范围, 而且和计算机软件的研究有着更密切的关系, 无论是编译程序还是操作系统, 都涉及到数据元素在存储器中的分配问题. 在研究信息检索时也必须考虑如何组织数据, 一遍查找和存取数据元素更方便. 因此, 可以认为数据结构是结余数学, 计算机硬件和计算机软件三者之间的一门核心课程. 在计算机科学中, 数据结构不尽是一般程序设计(特别是非数值计算的程序设计)的基础, 而且是设计和实现编译程序, 操作系统, 数据库系统及其他系统程序和大型应用程序的重要基础.

基本概念和术语

数据 是对客观事物的符号表示, 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称.

数据元素 是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理.

数据对象 是性质相同的数据元素的集合, 是数据的一个子集.

数据结构 是相互之间存在一种或多种特定关系的数据元素的集合. 在任何问题中, 数据元素都不是孤立存在的, 而是他们之间存在着某种关系, 这种数据元素之间的关系称为结构, 根据数据元素之间关系的不同特性, 通常有下列4类基本结构 :

  • 集合 结构中的数据元素之间除了同属于一个集合的关系外, 别无其他关系
  • 线性结构 结构中的数据元素之间存在一个对一个的关系
  • 树形结构 机构中的数据元素之间存在一个对多个的关系
  • 图状结构网状结构 结构中的数据元素之间存在多个对多个的关系

数据结构的形式定义 数据结构是一个二元组 Data_Structure = (D, S), 其中D是数据元素的有限集, S是D上关系的有限集.

逻辑结构 数据结构定义中的关系描述的是数据元素之间的逻辑关系

物理结构 数据结构在计算机中的表示(又称映像), 又称存储结构, 包括数据元素的表示和关系的表示

在计算机中表示信息的最小单位是二进制数的一位, 叫做位(bit). 在计算机中, 我们可以用一个由若干位组合起来行程的一个位串表示一个数据元素, 通常称这个位串为元素(element)结点(node). 当数据元素由若干数据项组成时, 位串中对应于各个数据项的子位串成为数据域, 因此, 元素或结点可看成是数据元素在计算机中的映像.

数据元素之间的关系在计算机中有两种不同的表示方法: 顺序映像非顺序映像, 并由此得到两种不同的存储结构: 顺序存储结构链式存储结构

顺序映像 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系

非顺序映像 借助指示元素存储地址的指针(pointer)表示数据元素之间的逻辑关系

最近的文章

数据结构学习笔记(二)—线性表

[TOC]线性表线性结构的特点是: 在数据元素的非空有限集中, 存在唯一的一个被称作第一个的数据元素, 存在唯一的一个被称作最后一个的数据 元素, 除第一个之外, 集合中的每个数据元素均只有一个前驱, 除最后一个之外, 集合中每个数据元素均只有一个后继.线性表的类型定义线性表 是最常用且最简单的一种数据结构, 简言之, 一个线性表是n个数据元素的有限序列.在稍复杂的线性表中, 一个数据元素可以由若干个数据项组成, 在这种情况下, 常把数据元素称为记录, 含有大量记录的线性表又称文件线性表是...…

数据结构继续阅读
更早的文章

[转改]面试题: 按层遍历二叉树的节点(Objective-C版)

题目**给你一棵二叉树, 请按层输出其的节点值, 即: 从上到下, 从左到右的顺序. 例如, 如果给你如下一棵二叉树: ** 3 / \ 9 20 / \ 15 7输出结果应该是:[ [3], [9, 20], [15, 7] ]分析及答案 二叉树节点定义 采用单链表的形式, 只从根节点指向子节点, 不保存父节点 @interface BinaryTreeNode : NSObject/** 该节点的值 */@proper...…

iOS开发面试题继续阅读