文档介绍：精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 1 页
数据结构学习总结
壹、研究对象及基本概念
首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。
从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。
线性表、栈、队列、串、数组
线性结构:
树结构
图结构
逻辑结构
非线性结构
从存储结构划分
顺序结构
链式结构
索引结构
物理结构
散列结构
各自的定义及特点：
顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。
优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。
链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。
它没有顺序存储结构所具有的弱点,、删除灵活 (不必移动节点，只要改变节点中的指针)。查找结点时链式存储要比顺序存储慢。
3、索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。索引项的一般形式一般是关键字、地址。
4、散列存储：又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。特点：散列是能一种快速实现访问的存储方式。
三、操作算法
1、算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
2、五个重要特性：
（1）有穷性；（2）确定性；（3）可行性；（4）输入；（5）输出。
3、算法设计要求：
（1）正确性；（2）可读性；（3）健壮性；（4）效率与低存储量需求。
精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 2 页
效率的度量：
算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
存储空间度量：
一个程序的空间复杂度是指运行完一个程序所需内存的大小。一个算法所需的存储空间用f(n)表示。
S(n)=O(f(n))
其中n为问题的规模，S(n)表示空间复杂度。
一些基本概念
数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。
数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。
是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。
性质相同的元素的集合叫做数据对象。
贰、线性结构
线性表
[定义] 线性表是由n(n≥0)个相同类型的元素组成的有序集合。
记为：
( a1,a2,a3,……ai-1,ai,ai+1,…… an )
其中：① n为线性表中元素个数，称为线性表的长度；
当n=0时，为空表，记为（ ）。
② ai为线性表中的元素，类型定义为elemtype
③ a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1<i<n)，称ai-1为ai的直接前驱，ai+1为ai的直接后继。
④ 线性表是有限的，也是有序的。
抽象数据型线性表：
线性表 LIST = ( D , R)
D = { ai | ai ∈Elementset , i = 1, 2, …, n, n ≥ 0 }
R = { H }
H = { <ai-1, ai> | ai-1, ai ∈ D , i = 2 , … , n }
操作：设L的型为LIST线性表实例，x 的型为elemtype的元素
精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 3 页
实例，p 为位置变量。所有操作描述为：
① Insert(x, p, L)