数据结构复习笔记.doc

数据结构复****笔记
===李成松 1/11/2012 6:02:00 PM
一、课程概述:
发展背景:为了编出一个构好、效率高的处理程序就必须分析处理对象的特性以及各处理对象之间存在的关系。
学****目的:为了了解计算机处理对象的特称,将现实世界中实际问题所涉及的处理对象在计算机中表示出来并对他们进行处理。
基本术语:
数据(data):是信息的载体,它能够被计算机识别、存储和加工处理。
数据元素(data element):是数据的基本单位(又可称为元素、节点、顶点、记录)。数据项(最小单位)∈数据元素
数据元素类(data element class):具有相同特性的仙宫元素的集合。
数据结构:
含义:是指相互之间存在着一种或多种关系的数据元素的集合。
基本类型:集合:数据元素间的关系:“属于同一个集合”,是元素关系极为松散的结构。
线性结构:数据元素间的关系:一个对一个的关系
树形结构:数据元素间的关系:一个对多个的关系
图状结构:数据元素间的关系:多个对多个的关系(亦称网状结构)
2, 3
22,33
1
5
4
3
0
11
2
3
11
3
集合
线性
树形
图形
逻辑结构:具体问题中抽象出来的
数学模型,与数据存储无关
物理结构:
数据结构
顺序存储:元素间的逻辑关系: 由存储单元的的相邻关系体现(数组)
链式存储:元素间的逻辑关系:通过附设的指针字段来表示,不要求相邻(指针类型)
为了查找方便采用:索引存储方法和散列存储方法

形式定义: Data Structure=(D,R)
D:数据元素的有限集,R是D上关系的有限集(数据结构有两个元素:一个是元素的集合,一个是关系的集合)
例如:用二元组表示线性结构:
Linear---List=(D,R)
D={01,02,,03,04,05,06,07,08,09,10}
R={<01,02>,<02,03>,…..,<06,10>}
算法及算法分析:
特性:又穷性
确定性
可行性
输入
输出
有人说“算法+数据结构=程序”
算法的设计要求:
正确:正确是设计和评价一个算法的首要条件
可读:
健壮:指算法对各种可能的情形都考虑的非常完善。例如:输入非法
高效:算法的执行效率要高。算法的效率包括:时间效率和空间效率
算法分析:从时间复杂度和空间复杂度评价该算法的优劣
时间复杂度:
算法运行时间取决于:
硬件的速度
书写程序的语言:实现的语言级别越高执行效率越低。
编译程序所生成的质量
问题的规模
做法:从算法中选取一种对于所研究的问题来说是基本运算的原操作(基本语气),
该原操作执行的次数作为算法的时间度量
平均时间复杂度:
二、线性表
定义:由具有相同特性的n个元素所组成的有限序列,相邻元素间存在序偶关系(前驱、后继)
存储方式:顺序表、单链表
顺序表:
定义:采用顺序的存储方式存储的线性表(数组)
属性:存储空间的起始位置(例如:设a[i]中的i为第一个位置)
顺序表的容量(即数组的长度n)
顺序表的当前长度
存储结构:存储结构是数据及其逻辑结构在计算机中的表示
存取结构:在一个数据结构上对查找操作的时间性能的一种描述
“顺序表是一种随机存取的存储结构”的含义为:在顺序表这种存储结构上进行的查找操作,其时间性能为O(1)。
类的定义:存储空间,长度,当前长度,相应功能
template<class Telem>
class SqList:public List<Telem>
{
private:
Telem*elem; //存储空间
int curlrn; //当前长度
int maxlen; //长度
public:
SqList(int maxsz=100):maxlen(maxsz)//构造函数
{
curlen=0;
elem=new Telem[maxlen];
};
SqList(Telem[],int n,int maxsz=100):maxlen(maxsz)
{ //创建链表
curlen=n;
elem =new Telem[maxlen];
for(int i=0;i<n;i++) elem[i]=a[i];
};
~SqList(){delete[]elem;}; //析构函数(一个类只能有
void clear(){curlen=0;}; //一个析构函数)
…………………
};
类的实现:
查找
按值求位序:
Templ