文档介绍：第1章绪论
第2章线性表
第3章栈和队列
第4章串
第5章数组和稀疏矩阵
第6章树和二叉树
第8章图
数据结构总复习
第9章查找
第10章内排序
第7章广义表
第1章绪论

数据->数据元素->数据项
数据结构是指数据以及相互之间的联系。包括:
(1)数据的逻辑结构。
(2)数据的存储结构(物理结构)。
(3)施加在该数据上的运算。
数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象),它是依赖于计算机语言的。
数据的运算是定义在数据的逻辑结构上的,每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。
逻辑结构主要有两大类:
(1)线性结构
(2)非线性结构:
1)树形结构
2)图形结构
存储结构分为如下四种:
(1)顺序存储方法
(2)链式存储方法
(3)索引存储方法
(4)散列存储方法

抽象数据类型(Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。

算法是对特定问题求解步骤的一种描述,它是指令的有限序列。
算法的五个重要的特性:
(1)有穷性
(2)确定性
(3)可行性
(4)有输入
(5)有输出

(1)算法的时间复杂度:是指其基本运算在算法中重复执行的次数。
算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作:
T(n)=O(f(n))
记号“O”读作“大O”,它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。
(2)算法空间复杂度:是对一个算法在运行过程中临时占用的存储空间大小的量度。
对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。
第2章线性表

线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素。