的数据结构第一章绪论

第一章绪论基本概念和术语

数据:

所有能被输入到计算机中，且能被计算机处理的符号的集合数据项：数据结构中讨论的最小单位,数据元素是数据项的集合，数据是数据元素的集合数据元素:

是数据(一个集合)中的一个“个体”，是数据结构中讨论的基本单位001高等数学华罗庚S01……002线性代数銮汝书L01……003高等数学郑杭生

S01……004离散数学耿素云S02………………………………序号书名作者书名……数据元素数据项001002003004……数据元素数据结构

：数据以及数据之间的关系基本概念和术语

集合线性结构树形结构图状结构

数据结构：带结构的数据元素的集合，这里的结构是指数据元素之间存在的一种约束关系例1.一个含12位数的十进制数可以用三个4位的十进制数表示3214,6587,9345─

a1(3214),a2(6587),a3(9345)在a1、a2和a3之间存在“次序”关系

<a1,a2>，<a2,a3>3214，6587，9345≠6587，3214，9345

a1

a2

a3

a2

a1

a3例2.由6个数组成一个2行3列的二维数组{a1,a2,a3,a4,a5,a6}行的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序关系:col={<a1,a4>,<a2,a5>,<a3,a6>}a1a2a3a4a5a6例3，一维数组{a1,a2,a3,a4,a5,a6}中存在次序关系:ai可见：不同的关系构成不同的结构，而数据结构就是带结构的数据元素的集合{<ai,ai+1>|i=1,2,3,4,5}

数据结构的形式定义为:

数据结构是一个二元组Data_Structures=(D,S)

其中:D是数据元素的有限集，

S是D上关系的有限集。抽象数据类型

(AbstractDataType简称ADT)

ADT是指一个数学模型以及定义在此数学模型上的一组操作,可用三元组表示,其中，D是数据对象，S是D上的关系集，P是对D的基本操作集ADT

抽象数据类型名{

数据对象D：〈数据对象的定义〉

数据关系S：〈数据关系的定义〉

基本操作P：〈基本操作的定义〉}ADT

抽象数据类型名（D，S，P)例.抽象数据类型复数的定义：(两个实数的有序偶对3+7i2+5i5+8iADTComplex{

数据对象：D={e1,e2｜e1,e2∈RealSet}

数据关系：R1={<e1,e2>|e1是实数部分,e2是虚数部分}

基本操作：

InitComplex(&Z,v1,v2)

操作结果：构造复数Z,实部和虚部分别被赋以参数v1和v2的值。

GetReal(Z,&realPart)

操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImagPart)

操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)

操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex时间复杂度

看执行的代码和N之间的关系,把N看作无穷大假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=o(f(n))称T(n)为算法的(渐近)时间复杂度如何估算算法的时间复杂度？即如何求f(n)从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则

for(i=0;i<n;++i)a=0;for(j=0;j<n;++j)printf(“hello!”);T(n)=O(n)例一

for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];}基本操作:乘法操作时间复杂度:O(n3)例二voidselect_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列

for(i=0;i<n-1;++i){j=i;for(k=i-1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}//select_sort}基本操作:比较(数据元素)操作时间复杂度:O(n2)

例三

voidbubble_sort(inta[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列

for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<i;++j)if(a[j]>a