数据结构

数据结构

数据结构概述及线性表
数组
栈
队
树
树（续）
图
图（续）
线索
排序

第一讲数据结构概述及线性表

1 数据结构概述

1.1 概述

60年代初期，还没有独立的“数据结构”课程，有关内容散见于操作系统、编译原理和表处理语言等课程中。

自1968年，美国计算机科学D.E.Knuth教授著“计算机程序设计技巧”（The Art of Computer Programming）问世以后，把数据的逻辑结构、存储结构及对每种结构所定义的运算组成了“数据结构”的主要内容。以后，各大学纷纷开设“数据结构”课程。我国高校在70年代后期开始陆续开设这门课程。

“数据结构”是计算机专业的一门核心课程，是“编译原理”、“操作系统”、“数据库”等课程的基础，也是设计和实现系统程序及大型应用程序的重要基础。

计算机是通过执行人们所编制的程序来完成预定的任务。在广义上说，计算机按照程序所描述的算法对某种结构的数据进行加工处理，因此，有人给程序下了一个定义：

程序=算法+数据结构

非数值型问题越来越引起关注：如文献检索、MIS、CAD等等。

数据结构与其他学科的关系

数据结构举例

（1）图书馆书目检索

（2）人机对弈

（3）多叉路口交通灯管理

1.2 基本概念和术语

数据：是对客观事物的符号表示，能被输入到计算机中被程序处理的符号的总称。
数据元素（也称为结点或记录）：数据的基本单位，可由几个数据项组成。
数据对象：性质相同的数据元素的集合。
数据结构：Data_Structure = (D,S)。

数据结构举例
Complex = （C，R）
其中：C是含两个实数的集合{c1，c2}；R={P}，而P是定义在集合C上的一种关系{<c1,c2>}，其中有序偶<c1,c2>表示c1是复数的实部，c2是复数的虚部。

数据结构分类：逻辑结构和物理结构。
逻辑结构：线性表、栈和队、数组、树、图。
物理结构：顺序存储结构、链式存储结构。
为避免混淆，通常我们将数据的逻辑结构简称为数据结构。

1.3 算法的描述及算法分析

1.3.1 算法的概念

算法是由若干条指令组成的有限序列，它必须满足下列性质：

输入性
输出性
有穷性
确定性
可行性

算法与程序是有区别的，一个程序不一定满足有穷性。

1.3.2 算法分析

衡量一个算法的好坏，除其“正确性”外，还应考虑：

执行算法所消耗的时间
执行算法所耗费的存储空间，其中主要考虑辅存量的大小
其他诸如：算法是否易读，是否易于调试、测试等

例1，求两个n阶方阵的乘积C = A x B, 其算法描述如下：

#define n 自然数
MATRIXMLT(A,B,C)
Float A[][n], B[][n], C[][n]
    {int i, j, k;
(1)     for(i=0; i<n; i++)                             n+1
(2)     for(j=0; j<n; j++)                             n(n+1)
(3)     {C[i][j]=0;                                    n²
(4)     for(k=0; k<n; k++)                             n²(n+1)
(5)     C[i][j]=C[i][j]+A[i][k]*B[k][j]; }}   n³

引入频度概念：语句的频度即为语句重复执行的次数（上算法右边列出的是各语句的频度）。

该算法所有语句频度之和（即算法的时间耗费）为：
T(n)=2n³+3n²+2n+1
T(n)称为算法的时间复杂度(Time Complexity)。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐进时间复杂度。

即T(n)和n³是同阶的，记作T(n)=O(n³)。称T(n)=O(n³)是算法MATRIXMLT的渐进时间复杂度。

当评价一个算法的时间性能时，主要标准是算法时间复杂度的数量级，即算法的渐进时间复杂度，常常简称为算法的时间复杂度。通常我们可以通过判定程序段中重复次数最多的语句的频度来估算算法的时间复杂度。对于较复杂的算法，可将它分隔成容易估算的几个部分，然后再利用“O”的求和原则得到整个算法的时间复杂度。
例，若算法的两个部分的时间复杂度分别为T₁(n)=O(f(n))和T₂(n)=O(g(n))，则总的时间复杂度为
T(n)=T₁(n)+T₂(n)=O(max(f(n),g(n)))

2 线性表

2.1 线性表的逻辑结构

计算机所处理的数据，大都是表格的形式。线性表(linear list)是一种最简单也是最常用的数据结构。一个线性表是数据元素的有限序列，如

(a₁,a₂,...,a_i,...,a_n)

所谓线性表是指表中的每个元素，除第一个外，都只有一个直接前趋(predecessor)，同时除最后一个外，都仅有一个直接后继(successor)。

例：

2.2 线性表的运算

运算均是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行。对于线性表的基本运算，常见的有以下几种：

置空表SETNULL(L)
求长度LENGTH(L)
取结点GET(L,i)
定位LOCATE(L,x)
插入INSERT(L,x,i)
删除DELETE(L,I)
取直接前趋PRIOR(L,a_i)
取直接后继NEXT(L,a_i)

2.3 线性表的顺序存储结构

2.3.1 顺序表

在计算机内，可以用不同方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表的元素。

图中设每个元素占l个存储单元。数据的这种顺序存储结构叫做向量。

LOC(a_i+1) = LOC(a_i) + l
LOC(a_i) = LOC(a₁) + (i-1)*l

C语言描述的数据类型：

typedef in datatype； /* datatype 可为任何类型，这里假设为 int */
#define maxsize 1024 /* 线性表可能的最大长度，这里假设为1024 */
typedef struct
{ datatype data[maxsize]； /* 数据域data是存放线性表结点的向量空间，下标从0开始 */
int last；/* 数据域last指示线性表的终端结点在向量空间中的位置 */
}seuqenlist；

2.3.1 顺序表的基本运算

(1) 插入运算

    在线性表中插入一个新结点x，使长度为n的线性表
                        (a₁,a₂,...,a_i-1,a_i,...,a_n)
变成长度为n+1的线性表
                        (a₁,a₂,...,a_i-1,x,a_i,...,a_n)

具体算法描述如下：

(2) 删除运算

    在长度为n的线性表中删除第i个结点，使长度为n的线性表
                        (a₁,a₂,...,a_i-1,a_i,...,a_n)
变成长度为n-1的线性表
                        (a₁,a₂,...,a_i-1,a_i+1,...,a_n)