数据结构第一第二章总结

                                                                            第一章 绪论

1.1 数据结构的基本概念

1.1.1 基本概念和术语

数据
数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据对象
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。例如整数数据对象是集合N={0，±1，±2……}。

数据类型
数据类型是一个值的集合和定义在此集合上的一组 *** 作的总称。
（1）原子类型
其值不可再分的数据类型。
（2）结构类型
其值可以再分解为若干成分（分量）的数据类型。
（3）抽象数据类型
抽象数据组织及与之相关的 *** 作。

数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，他们之间存在某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。

        数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的时效件依赖于所采用的存储结构。

1.1.2 数据结构三要素

数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合、树和图是典型的非线性结构。数据的逻辑结构分类如图所示：

集合。结构中的数据元素之间除“同属一个集合”外，别无其他关系。
线性结构。结构中的数据元素之间只存在一对一的关系。
树形结构。结构中的数据元素之间只存在一对多的关系。
图状结构或网状结构。结构中的数据元素之间存在多对多的关系。

数据的存储结构
存储结构是指数据结果互在计算机中的表示（又称映像），也称物理结构。它包含数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。

（1）顺序存储
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
优点： 可以实现随机存取，每个元素占用最少的存储空间。
缺点： 只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

（2）链式存储
不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
优点： 不会出现碎片现象，能充分利用所有存储单元。
缺点： 每个元素因存储指针而占用额外的存储空间，且只能实现顺序存储。

（3）索引存储
在存储信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项一般形式是（关键字，地址）。
优点： 检索速度快。
缺点： 附加的索引表额外占用存储空间，增加和删除数据时也要修改索引表，因此话费更多的时间。

（4）散列存储
根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
优点： 检索、增加和删除结点的 *** 作都很快。
缺点： 若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

数据的运算
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能，运算的实现是针对存储结构的，指出运算的具体 *** 作步骤。
1.2 算法和算法评价

1.2.1 算法的基本概念

算法（Alogorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个 *** 作。因此，算法具有以下五个重要的特性：
（1）有穷性。一个算法必总在执行又穷步之后结束，且每一步都可在有穷时间内完成。
（2）确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
（3）可行性。算法中描述的 *** 作都可以通过已经是实现的基本运算执行有限次来实现。
（4）输入。一个算法有零个或多个输入，这些输入曲子某个特定的对象的集合。
（5）输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

设计一个好的算法应达到以下目标：
（1）正确性。算法能够正确地解决求解问题。
（2）可读性。算法应该具有良好的可读性，以帮助人们理解。
（3）健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会莫名其妙的输出结果。
（4）效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程所需要的的最大存储空间，这两个都与问题的规模有关。

1.2.2 算法效率的度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有的语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为：
                                        T(n)=O(f(n))
O的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n0，使得当n>=n0时，都满足0<=T(n)<=Cf(n).
算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态）。
最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好的情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

在分析一个程序的时间复杂性时，有以下两条规则：
（1）加法规则
          T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

（2）乘法规则
          T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

常见的渐进时间复杂度为：
          O(1)

空间复杂度
算法的空间复杂度S(n)定义为算法所耗费的存储空间，它是问题规模的函数。记为：
                                        S(n)=O(g(n))
一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行 *** 作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间为常亮，即O(1).
 

                                                                     第二张 线性表

2.1 线性表的定义和 *** 作

2.1.1 线性表的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。若用L命名线性表，则其一般表示为
                               L=(a1 , a2,a3,……,ai,ai+1,……,an,)

a1是唯一的“第一个”元素，又称表头元素；an是唯一的“最后一个元素”，又称表尾元素。 除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且只有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正式线性表的名字由来。

线性表的特点如下：
（1）表中元素个数有限。
（2）表中元素具有逻辑上的顺序性，表中元素有其先后次序。
（3）表中元素都是数据元素，每个元素都是单个元素。
（4）表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
（5）表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注： 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。

2.1.2 线性表的基本 *** 作

一个数据结构的基本 *** 作是指最核心、最基本的 *** 作。其他较复杂的 *** 作可以通过调用其基本 *** 作来实现。线性表的主要 *** 作如下：

InitList(&L)：初始化表。构造一个空的线性表。
Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e)：按值查找 *** 作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找 *** 作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e):插入 *** 作，在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e):删除 *** 作，删除表L中的第i个位置的元素，并用e返回删除元素的值。
PrintList(L)：输出 *** 作。按前后顺序输出线性表L的所有元素值。
Empty(L):判空 *** 作。若L为空表，则返回true，否则返回false。
DestroyList(&L):销毁 *** 作。销毁线性表，并释放线性表L所占用的空间。b

2.2线性表的顺序表示

2.2.1 顺序表的定义

线性表的顺序存储又称为顺序表。

它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻。

第一个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素ai在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

2.3 线性表的链式表示

顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除的 *** 作需要移动大量元素。

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除 *** 作不需要移动元素，而只需要修改指针，但也会失去顺序表可随机存取的优点。

2.3.1 单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

2.3.2 单链表上基本 *** 作的实现

1. 采用头插法建立单链表
   该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后

   2.3.6 顺序表与链表的比较

   存取（读写）方式
   顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第i个位置上执行或存取的 *** 作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次。

   逻辑结构与物理结构
   采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。

   查找和删除 *** 作
   对于按值查找，顺序表无序时，两者的时间复杂度均为O(n)；顺续表有序时，可采用折半查找，此时的时间复杂度为O(log2n)。
   对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。顺序表的插入、删除 *** 作，平津需要移动半个表长的元素。链表的插入、删除 *** 作，只需修改相关结点的指针域即可。由于链表的而每个结点都带有指针域，故而存储密度不够大。

   空间分配
   顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量元素闲置；预先分配过小，又会造成溢出。
   动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致 *** 作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。
   链式存储的结点空间只在需要时申请分配，只要内存中有空间就可以分配， *** 作灵活、高效。

   2.3.7实际中应怎样选取存储结构

   基于存储的考虑
   难以估计线性表的长度或存储规模时，不宜采用顺序表，链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。

   基于运算的考虑
   在顺序表中按序号访问ai的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，因此，若经常做的运算时按序号访问数据元素，则显然顺序表优于链表。
   在顺序表中进行插入、删除 *** 作时，平均移动表中一般的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中进行插入、删除 *** 作时，虽然也要找插入位置，但 *** 作主要是比较 *** 作，从这个角度考虑显然后者优于前者。

   基于环境的考虑
   顺序表容易实现，任何高级语言中都有数组类型；链表的 *** 作是基于指针的，相对来说，前者实现较为简单。
   总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入、删除 *** 作的线性表（即动态性较强）宜选择链式存储。