数据结构
第一章 概论
一、算法+数据结构=程序 二、数据结构 逻辑结构 物理结构 三、术语
1、数据(Data)：数字、字符、图像、声音。------单元格
2、数据元素(Data Element)：是数据的基本单位，又称结点（用一组连续的位串表示）或记录。------行 3、数据项(Data ltem)：数据元素由若干个数据项组成，是数据的不可分割的最小单位。又称字段或域。------列
4、数据对象(Data Object)：是性质相同的数据元素的集合。------表
5、数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素之间关系的不同特性，通常有下列四类基本结构：
线性结构
非线性结构 顺序存储 链式存储 索引存储 散列存储
(1)集合结构：数据元素之间除了“同属于一个集合”的关系外，别无其它关系； (2)线性结构：一对一关系； (3)树形结构：一对多关系；
(4)图状结构或网状结构：多对多关系。
6、数据类型：原子类型（只有一个数据项）、结构类型（由多个不同类型数据项组成）。 7、抽象数据类型（Abstract Data Type）：数据对象、数据关系、基本操作 四、数据运算
查找、插入、删除、修改、排序 五、算法和算法分析 1.4.1 算法
- 1 -
数据结构
1、算法(Algorithm)：是对特定问题求解步骤的一种描述 2、五个重要特性：
(1)有穷性：执行有穷步之后结束，每一步在有穷时间内完成。
(2)确定性：无二义性。唯一的一条执行路径，相同的输入只能得出相同的输出。 (3)可行性：基本运算执行有限次次。 (4)输入：零个或多个输入。 (5)输出：一个或多个输出。
3、设计目标：正确性、可读性、健壮性、效率与低存储量需求。 六、算法分析
1、度量一个程序的执行时间： (1)事后统计的方法
(2)事前分析估算的方法（常用）
高级语言编写的程序运行时间取决于下列因素： a．依据的算法选用何种策略；
b．问题的规模，例如求100以内还是1000以内的素数；
c．书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低； d．编译程序所产生的机器代码的质量； e．机器执行指令的速度。
一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的，则算法时间取决于两者的综合效果。从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 2、时间复杂度
（1）算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n)=O(f(n))。 （2）语句的频度(Frequency Count)：该语句重复执行的次数。
（3）时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 3、空间复杂度(SpaceComplexity)：算法所需辅助存储空间的量度，记作：S(n) = O(g(n))。
- 2 -
数据结构
第二章 线性表
一、线性表的类型定义
1、线性表(Linear_List)：n个数据元素的有限序列，(a1, …, ai-1, ai, ai+1, …, an) (2—1)，ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1，2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。
2、线性表的长度：线性表中元素的个数n(n≥0)，n=0时称为空表。
3、位序：a1是第一个数据元素。an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
4、同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。 二、线性表的顺序表示和实现
1、顺序存储或顺序映象（顺序表）：用一组地址连续的存储单元依次存储线性表的数据元素。 2、存储位置计算：LOC(ai) = LOC(a1)+(i-1) * L 式中LOC(a1)是a1的存储位置，称基地址。（假设每个元素占l个存储单元）
3、特点：以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系，逻辑关系上相邻的两个元素在物理位置上也相邻。通常用数组来描述数据结构中的顺序存储结构。
4、优点：是一种随机存取的存储结构。
5、缺点：要求占用连续的存储空间，并预先分配；插入和删除操作时需要移动大量的元素，平均移动次数为n/2。
三、线性表的链式表示和实现
1、特点：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。
2、结点(Node)：
数据域：存储数据元素信息。
指针域：存储直接后继存储位置。指针域中存储的信息称做指针或链。 四、单链表：
1、每个结点中只包含一个指针域的链表，称线性链表或单链表。
- 3 -
数据结构
例，线性表(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)的链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点(即第一个数据元素的存储映象)的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”(NULL)。
2、在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。
3、头指针：单链表可由头指针唯一确定，它指向表中第一个结点。若L为“空”(L==NULL)，则所表示的线性表为“空”表，其长度n为“零”。有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。
4、查找
5、插入：s—>next = p—>next；p—>next = s； 6、删除：s—>next = p—>next；p—>next = s；
特点：插入或删除结点时，仅需修改指针而不需要移动元素。是一种动态结构，每个链表占用的空间不需预先分配划定，可由系统应需求即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。
五、静态链表
对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。
这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
六、循环链表（Circular linked List)
1、特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此从表中任一结点出发均可找到表中其它结点。
2、循环条件：不是p或者p—>next是否为空，而是它们是否等于头指针。
3、尾指针：设置尾指针而不设头指针可使某些操作简化。例如将两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相接。
- 4 -
数据结构
七、双向链表（Double Linked List）
1、特点：结点中有两个指针域，其一指向直接后继，另一指向直接前驱。
2、在双向链表中，若p为指向表中某结点的指针，则：p->next->prior = p->prior->next = p。 3、带头结点的双链循环线性表的插入和删除：
插入：s ->data = e; s ->prior = p->prior; p ->prior ->next = s; s ->next = p; p->prior = s;
删除：e=p—>data； p—>prior—>next = p—>next; p—>next—>prior = p—>prior; free(p)； 八、内容精要 1、概念和术语
线性表 前趋和后继 线性表的长度 空表 表头元素 表尾元素 结点 首元结点 2、线性表的特点
(1)存在唯一的一个称“第一个”的数据元素；(2)存在唯一的一个称“最后一个”的数据元素；(3)除第一个之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个之外，集合中每个数据元素均只有一个后继。
3、线性表的顺序存储结构（顺序表）
用一组地址连续的存储单元依次存储线性表的各个元素，可借助一维数组实现。
在顺序存储中，每个存储结点只含有所存数据元素本身的信息，元素之间的逻辑关系是通过数组下标反映出来的。
假设线性表中每个元素占用c个存储单元，则线性表中第i个数据元素的存储地址为LOC(ai)=LOC(a1)+(i-1)*c。
4、C语言中线性表顺序存储空间的两种分配方法 1.静态分配
在类定义中用一维数组来定义线性表的存储空间。这种方式在程序开始运行前，系统按数组大小事先分配出相应的空间，因此向量空间的大小应慎重选择，使它既能标元素数目动态增加的需求，又不至于过
- 5 -