数据结构 - 图文

（3）健壮性(Robustness）：是指当输入非法数据时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果，更不会死机和死循环。

（4）效率和低存储量需求：所谓效率，指的是执行时间，即对于同规模的问题，哪种算法所用的时间少,哪种算法效率就越高。存储量需求，是指解决相同规模的问题，所需的最大存储空间，哪种算法所用的空间少，就相对来说越好。

1．1．4 算法的复杂度

算法的性能评价是对问题规模与该算法在运行时所占用的空间与所耗费的时间给出一个数量关系的评价，用时间复杂度和空间复杂度来度量算法的复杂度. 1． 算法的渐近时间复杂度

算法的渐近时间复杂度不是一个算法执行时间的精确度量，而是用来评估算法的时间增长趋势, 只与问题规模有关，应当抛弃具体机器条件，仅考虑算法本身的效率高低。为便于比较解决同一问题的不同算法的性能，通常以算法中基本操作重复执行的频度作为算法的时间度量标准。

算法的基本运算是指对算法运行时间影响最大的运算。通常应选择算法内重复执行次数最多的基本语句，作为算法执行时间量度。一般情况下是最深层循环内的基本语句。如线性表的查找算法，是把要查找的数据与表中的元素进行比较作为基本运算；两个实数矩阵相乘的算法，是把两个实数相乘作为基本运算。

下面的例子是两个n阶矩阵相乘的算法，第6条语句是基本运算语句，其执行次数是n3次。即T(n)=n3，其中T(n)是对于规模是n的问题的基本运算的执行次数。

随着问题规模n的增大，T(n)的增长趋势是什么?

我们以两个矩阵相乘的算法为例，由此引出算法时间复杂度的概念： 1. for i=1 to n // n+1 次 2. for j=1 to n // n(n+1) 次 3. {

4. b[i,j]=0; // n2 次

5. for k=1 to n // n2(n+1) 次 6. b[i,j]=b[i,j]+a[i,k]*a[k,j]; // n3 次 7. }

设T(n)和g(n)是定义在正数集上的正函数。如果存在正的常数C和自然数n,使得当 n≥n0时有T(n)≤Cg(n)，则称函数T(n)当n充分大时有上界，且g(n)是它的一个上界，g(n)是T(n)的同数量级函数。并把 T(n)表示成数量级的形式为： T(n)=O(g(n)) 。这时也称T(n)的阶不高于g(n)的阶。

我们把O(g(n))称为算法的渐近时间复杂度，时间复杂度表示T(n)变化时呈现的趋势，g(n)是算法的时间增长率的上界。

针对矩阵相乘的算法，T(n)=n3，则有T(n)≤2n3(当n≥1时)，所以T(n)=O(n3)。即矩阵相乘算法的时间复杂度反映出算法的执行时间与问题规模n的三次方同阶。一般情况下，随着n的增大，T(n)增长较慢的算法为最优算法。

不同算法在基本操作重复执行的频度不同时，时间复杂度有可能相同，如T(n)=n2+3n+4 与T(n)=4n2+2n+1它们的基本运算次数不同，但时间复杂度都是O(n2)。

常见的时间复杂度有常数时间复杂度O(1)，多项式级时间复杂度O(n)、O(n2)、O(n3)，对数时间复杂度O(log2n)、O(nlog2n)，指数时间复杂度O(2n)、O(3n)等。 2．空间复杂度

算法的空间复杂度是指算法中所需的辅助空间单元，并不包括原始输入数据所占的单元，因为它们只与问题本身有关，而与算法无关。上述例子中的辅助空间为变量i,j,k。因为它们与问题的规模n无关，所以上述算法的空间复杂度S(n)=O(1)。

1．2 线性表

1．2．1线性表的基本概念

线性表（LinearList）是最常用且最简单的一种数据结构，它和后要讲到的栈及队列都属于线性结构，这种结构的特点是，在数据元素的非空有限集中，数据元素都是相同的数据类型，除第一个和最后一个元素外，其他数据元素有且仅有一个前趋元素和一个后继元素，第一个元素无前趋，最后一个元素无后继。在线性表中，数据元素之间是一个对应一个的线性关系，数据元素在线性表中的逻辑位置只取决于它们自己的序号。 简单地说，线性表是n个数据元素的有限序列。如：（a１，a2，?，ai，?，an），其中表中元素的个数n(n≥0)称为表的长度，n=0时称为空表。如用26个英文字母组成的线性表为（A,B,C,?，Z），由一组有意义的数字可组成的线性表是：(23，45，78，110，134) 。

线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的元素不仅可以进行访问，还可以进行插入和删除等操作。 对线性表进行的基本操作主要有如下几种。 （1）初始化：设定一个空的线性表。 （2）求长度：求出表中有多少个元素。 （3）取元素：求出表中某位置的元素。

（4) 修 改：修改表中给定元素的值。

（5）前 插：在指定位置的元素之前插入一个元素，插入后表中长度加1。

（6）删 除：删除指定位置的元素，删除后表中长度减1。 (7) 检 索：找出表中给定特征的数据元素 (8) 排 序：按给定要求对表中元素重新排序。

1．2．2线性表的存储结构及其运算 1. 线性表的顺序存储结构

线性表的顺序存储结构就是把线性表中的数据元素按照逻辑顺序依次存放到一组连续的存储单元中。我们规定存储单元是由一定大小的字节构成的，每个数据元素对应一个存储单元。由于线性表中数据元素类型一致，所以每个数据元素所占的存储单元的大小是一样的。

假定这组连续存储单元的首地址为b，每个数据元素所占的字节个数都为m，即每个单元由m个字节组成，这组连续的内存空间是由maxlen个单元构成，表中元素为n个，那么线性表的顺序存储结构如图1-6所示。通常把首地址又叫做起始位置或基地址。我们称具有顺序存储结构的线性表为顺序表。

由上所述，我们很容易得到线性表的第i个元素ai的存储地址为： LOC（ai）=LOC（a1）＋（i-1）*m

所以顺序表适用于快速频繁存取数据元素的操作。

图1-6线性表的顺序存储结构示意图

顺序存储结构也称为向量式存储结构，可用高级语言中的一维数组来描述。通常情况下，开辟的数组大小要考虑具体的问题要求，因为向量式的存储结构是静态分配的，是不能在程序运行时动态扩展存储空间的。若问题中数据元素的个数事先无法确定，特别是存在对线性表的插入操作，数组的大小就应按最大的规模定义，以满足追加空间的要求。这也带来了风险：预留空间过多，可能造成存储空间的浪费，预留空间不够，导致插入操作失败。

C语言中定义一定大小的一维数组的方法为：

#define M 100 /* 定义M为常数100， M的值作为数组的最大容量 */

int V[M］; /* V是数组的名字，假设数组元素是整型类型 */ 线性表中的数据元素在一维数组中的存储方式如图1-7所示。

V[0] a1

a2 V[1] n个元素 …

an V[n-1] …

V[M-1]

图1-7 数组作为存储线性表元素的手段

2.顺序表插入和删除运算 （1） 顺序表插入运算

在顺序存储结构中，线性表的插入操作是指在线性表的第i个数据元素之前插入一个新的数据元素，首先从最后一个元素开始，直到第i个元素（共n-i+1个元素）依次向后移动

一个位置，把要插入的元素插入到空出的位置处，结果使长度为n的线性表

（a1，a2，?，ai-1，ai，?，an）

变成长度为n＋1的线性表

（a1，a2 ，?，ai-1 ，x，ai ，? ，an)

合理的插入位置是：a1之前、an之后、a1到an之间，即（1≤i≤n+1）。 （2） 顺序表删除运算

在顺序存储结构中，线性表的删除操作是指删除线性表中第i个元素，则需从第i+1个元素开始，直到最后一个元素（共n-i个元素）依次向前移动一个位置。线性表的删除操作是使长度为n的线性表

（a1，a2，?，ai-1，ai，ai+1 ，?，an）

变成长度为n-1的线性表

（a1，a2，?，ai-1，ai+1 ，?，an）

删除结束后，线性表的长度减1。合理的删除位置是（1≤i≤n）。

（3）顺序表插入和删除运算的效率

在顺序表的表头前插入一个元素，需要移动表中所有的元素，若删除表头元素，也需要移动所有的元素。在平均情况下，在顺序表插入或删除一个元素，几乎表中一半的元素需要移动，因此在顺序表中插入或删除一个元素的效率是很低的，特别是在顺序表很长的情况下尤其突出。

（4）顺序表插入操作的算法

int insq(int i, int x, int V[ ],int M, int *p)

{/* M是存储空间大小，p 是指针变量，指向存储了表长的变量 */ int n,j;

n=*p; /* 获取表长 */ if( n==M) {

printf(\ return (0); }

if((i<1)||(i>n+1)) {

printf(\ return(0); } else {

for(j=n; j>=i; j--) V[j]=V[j-1]; V[j]=x;

*p=++n; /* 表长加1，由p返回到函数调用处 */ return(1); } }