初始数据结构（c语言版本）

目录

基本概念和专业术语

数据结构概念

数据结构的结构类型

1.逻辑结构

（1）集合结构

（2）线性结构

（3）树结构

（4）图结构或网状结构

2.存储结构

（1）顺序储存结构

 (2)链式储存结构

 数据类型和抽象数据类型

抽象数据类型的表示与实现

 算法的定义及特性

评价算法的优劣的基本标准 

 算法的时间复杂度

问题规模和语句频度

算法时间复杂度定义

算法的时间度量：

关于数学符号“O”的严格定义：

 算法的时间复杂度分析举例

最好，最坏和平均时间复杂度

算法的空间复杂度

基本概念和专业术语

1. 数据（Data）：它是客观事物的符号表示，它能输入到计算机里并被计算机所处理的所有客观符号的统称。如：数学里的实数和整数，文本编辑中用到的字符串，多媒体程序处理的图像，图像，声音及动画等等通过特殊编码定义后的数据。
2. 数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素，记录等等。数据元素用于完整地描述一个对象。如学校里关于学生信息表格中一名学生记录。
3. 数据项（Data Item）是组成数据元素的，有独立含义的，不可分割的最小单位。如：学生基本信息这张表里的学号，姓名等等这些都属于数据项。
4. 数据对象（Data Object）是性质相同的数据元素的集合，它是数据的一个子集。如：字母字符数据对象是集合C={’a‘，’b',···,'z','A','B',···,'z'}，学生基本信息表也可以是一个数据对象。由此不难看出，不管是无限集合，还是有限集合，还是由多个数据项组成的复合数据元素的集合。

数据结构概念

     数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。也就是说，数据结构是存在关系的数据元素的集合。

数据结构的结构类型

逻辑结构可以看做是具体问题抽象出来的数学模型，他是用逻辑关系来描写数据的，所以数据的存储也就和他无关了。

数据结构的两个要素：一是数据元素，它的含义就如上述，二是关系，它是指数据元素之间的逻辑关系。对于不同的数据元素之间的关系，通常有四类基本的结构：

数据元素之间只有“属于一个集合”这一种关系。如：把班级看做一个集合，那这个学生与班级之间只有属于和不属于的关系。

数据元素之间有着一对一的线性关系。如：把一张学生信息表按照报道的顺序来排列，那么前后的学生就是一种线性结构。

数据元素之间有着一对多的关系。如：班长管理多个组长，一个组长管理着一些学生。

数据元素之间有着多对多的关系。如：多个同学之间可以有不同朋友关系，任何两位同学都可以是朋友。

数据对象在计算机里存储表示称为数据的存储结构，或称物理结构。

计算机在存储数据对象时，不仅仅要储存每一个数据元素的数据，还有它们之间的逻辑关系，数据元素在计算机中用一个节点来表示。在存储结构中有两种基本的存储结构：

顺序储存结构是借助元素在储存器中的相对位置来表示数据之间的逻辑关系，一般是借用程序设计语言的数组类型来描述。

如：这个学生信息表，每一个学生信息的储存单位是50个储存单元，数据的储存从低地址向高地址的方向储存,下图：

上面一种的储存结构其中所有的元素都是放在一片连续的储存空间之中的，而链式储存结构，不用一片连续的空间，他是不同结点（数据元素）用指针的方式把他们链接到一起（每一个结点都需要附加指针字段来连接）

再用上一个学生信息表来举例子，为了方便理解，用如下方式表示：

 数据类型和抽象数据类型

1.数据类型

数据类型（Data Type）：在程序设计语言中，每一个数据都属于一种数据类型，而这种数据类型规定了这种数据的取值范围，储存方式以及允许进行的运算，一个值的集合和定义在这个值集上的一组 *** 作的总称叫做数据类型。数据类型反映了程序设计语言的数据描述和处理能力。

2.抽象数据类型

抽象数据类型通常情况下是指有用户定义的，表示应用问题的数学模型，以及定义在这个模型上的的一组 *** 作的总称，具体包括三个部分：数据对象，数据对象上的关系的集合以及对数据对象的基本 *** 作的集合。

其定义格式如下：

ADT 抽象数据类型名
{
Data:
数据元素之间逻辑关系的定义；
Operation:
 *** 作1；
 *** 作2；
...
}

抽象数据类型主要有两大特点：属性和方法。如：拿“Student”学生类型来说，姓名，性别，年级，班级，成绩等就是学生类型的“属性”，可以由各种变量表示；努力学习，升学，考试，翘课，挂科，被加分，被表扬，被扣分，被处分等就是学生类型的“方法”，可以由各种函数表示。方法可以对属性进行 *** 作，而封装就是把属性和方法进行整合，让他在形式上看着是一个整体，封装还可以把部分属性和方法给隐藏起来，实现“信息隐藏”的效果。

另外,在引用参数前面加上“&“，不仅可以提供输入值，还可以返回 *** 作结果。也就是说，引用类型的变量，其值若在函数中发生变化，则变化的值会带回主调函数中。

抽象数据类型的表示与实现

 （1）定义部分：

ADT Complex {  
数据对象：D={e1,e2|e1,e2∈R,R是实数集}  
数据关系：S={|e1是复数的实部，e2 是复数的虚部}  
基本 *** 作：  
Creat(&C,x,y)  
 *** 作结果：构造复数C，其实部和虚部分别被赋以参数x和y的值。  
GetReal(C)  
  初始条件：复数C已存在。  
   *** 作结果：返回复数C的实部值。  
GetImag(C)  
  初始条件：复数C已存在。  
   *** 作结果：返回复数C的虚部值。  
Add(C1,C2)  
  初始条件：C1，C2是复数。  
   *** 作结果：返回两个复数C1和C2的和。  
Sub(C1,C2)  
  初始条件：C1，C2是复数。  
   *** 作结果：返回两个复数C1和C2的差。 
} ADT Complex

 （2）表示部分：

typedef struct
 //复数类型 
{  
float Realpart; 
//实部  
float Imagepart; 
//虚部 
}Complex;

 （3）实现部分：

void Create( &Complex C, float x, float y) 
{ //构造一个复数  
C.Realpart=x;  
C.Imagepart=y; 
} 
float GetReal(Complex C) 
{ //取复数C=x+yi的实部  
return C.Realpart; 
} 
float GetImag(Complex C) 
{ //取复数C=x+yi的虚部  
return C.Imagepart; 
}
Complex Add(Complex C1, Complex C2) 
{ //求两个复数C1和C2的和sum  
Complex sum;  
sum.Realpart=C1.Realpart+C2.Realpart;  
sum.Imagepart=C1.Imagepart+C2.Imagepart;  
return sum; 
} 
Complex Sub(Complex C1, Complex C2) 
{ //求两个复数C1和C2的差difference  
Complex difference;  
difference.Realpart=C1.Realpart-C2.Realpart;  
difference.Imagepart=C1.Imagepart-C2.Imagepart;  
return difference; 
}

 算法的定义及特性

 算法必须满足的五个重要特性:

• 有穷性。一个算法必须是在执行有限步之后结束，且每一步都是在有限时间里面完成。
• 确定性。对于每一种情况所执行的相应 *** 作，在算法里面都有确切的规定，不会产生歧义，使得算法的执行者或者是阅读者都能知道这个的含义以及算法执行方式。
• 可行性。算法里面的所有 *** 作都可以通过已经实现的基本 *** 作运算执行有限次来实现。
• 输入。有0个或者是多个输出。在函数表述算法的时候，输入往往是形参的方式表示的，在他们被调用的时候，从主函数获得输入值。
• 输出。有一个或者多个输出。其是算法进行信息加工之后得到的结果，无输出的算法没有任何意义。在函数描述算法的时候，输出多以返回值或者应用类型的形参表示。

评价算法的优劣的基本标准 

•  正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
• 可读性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且很难调试和修改。 （可读性>机器可执行性）
• 健壮性。当输入的数据非法时，能适当地做出正确反应或者进行相应处理，而不会产生一些奇怪的输出结果。
• 高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

 算法的时间复杂度

衡量算法效率的方法主要有两类：

1.事后统计法

需要先将算法实现，然后从时间和空间两个方面来衡量好坏。缺点：（1）必须把算法转换成可执行的程序，二是时间花费的多少还要看计算机的好坏，编译器的使用等等环境因素，很容易造成误差。所以一般采用事前分析法。

2.事前分析法

通过计算算法的渐进复杂度来衡量算法的效率。

问题规模是指算法求解问题的输入量的多少，一般用整数n表示，问题规模n对不同问题含义不同。如：矩阵运算中n为矩阵阶数，多项式表示多项式的项数。

算法的执行时间是语句执行时间的总和，语句执行时间则为该条语句的重复执行次数和执行一次所需要的时间的乘机。

语句频度是指一条语句的重复执行的次数

for(i=1;i<=n;i++)                //频度为n+1
for(j=1,j<=n;j++)                //频度为n*（n+1）
{                                //频度为n^2
c[i][j]=0;                       //频度为n^2*(n+1)
for(k=1;k<=n;k++)                //频度为n^3
c[i][j]= [i][j]+a[i][k]*b[k][j];
}

该算法中所有语句频度之和，是矩阵阶数n的函数，用f(n)表示，如下：
f(n)=2n^3+3n^2+2n+1

基本语句的含义：

指的是算法中重复执行的次数和算法的执行时间成正比的语句，他的作用最大。

 基本语句可以客观的反映一个算法的执行时间，可以用只在算法中的“基本语句”的执行次数来度量算法的工作量。

当问题规模非常大时算法中基本语句的执行次数在渐进意义下的阶。如上述例子中，当n无穷大时，有：

 易知：当n无穷大时f(n)与n^3是同阶的，一个数量级的

一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作：

                                                              T(n)=O(f(n))   ， 其中O表示数量级。

这个式子表示随问题规模n的增大没算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。

关于数学符号“O”的严格定义：

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n'，使得当n>=n'时都满足0<=T(n)<=Cf(n)。

有了上述的定义就有T函数和f函数有相同的增长趋势，并且T函数的增长至多趋向于函数f的增长。符号“O”就是用来描述增长率的上限，“O”表示当问题规模n>n'时，算法的执行时间不会超过f(n)，如下图：

分析算法时间复杂度的基本方法：找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)，取其数量级用符号“O"表示就可以。在计算数量级时，可以遵循一下定理。

 注：在计算算法时间复杂度时，可以忽略所有低次幂项和最高次幂的系数。

最好，最坏和平均时间复杂度

 算法的基本语句频度不仅仅与问题的规模有关，如下例：

for(i=0;i

for(i=0;i