本文共 10090 字,大约阅读时间需要 33 分钟。
简单来说,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科
随着计算机的发展,计算机不再局限于科学计算,而更多用于控制、管理、数据处理等非数值计算的处理工作
那什么是数据结构呢?
一般来说,计算机解决一个具体问题时的步骤:
例如:
数值计算问题中: 我们求物理中的应力,找的数学模型为线性方程组 预报人口增长情况的数学模型为微分方程非数值计算问题中: 我们就无法用具体的数学模型了 而是诸如表、数、图之类的数据结构 现如今这类研究归于数学分支下的离散数学所研究
我们如何把现实中大量而复杂的问题以特定的数据类型(个体)和特定的存储结构(个体的关系)保存到主存储器(内存)中,<以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作,这个相应操作也叫算法>。
数据结构 = 个体 + 个体的关系(两者的存储问题)
算法 = 对存储数据的操作
简单来说:数据结构就是研究数据的存储问题;算法就是研究数据的操作问题
解题的方法和步骤的描述
有穷性
执行的步骤要有限
确定性
每一条指令由明确的含义
可行性
算法的操作可以通过基本运算实现
输入
有零个或多个输入
输出
有一个或多个输出
正确性
正确的解决问题
可读性
容易让人理解
健壮性
输入非法数据,算法能够进行处理
效率与低存储需求
占用内存越小越好,速度越快越好
大概程序要执行的次数,而非执行的时间
一个语句的频度:指的是该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),他是该算法问题规模的n的函数。
时间复杂度主要分析T(n)的数量级
而我们算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级,因此通常采用算法中基本运算的频度f(n)来分析算法时间复杂度。记为:T(n) = O(f(n)){O的含义是T(n)的数量级} 表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同
算法的时间复杂度为O(n^2),表明该算法的执行时间与 n ^2成正比
渐进时间复杂度增长率排序:
时间复杂性的规则:
一般我们讨论的都是在算法最坏的情况下的时间复杂度,以保证算法的运行时间不会比它更长
举例:
/*计算1-1/x+1/(x*x)… 的时间复杂度为:T(n) = O(n^2) *///文件名 #include//字符串函数头文件 #include //字符函数头文件 #include //malloc()等 #include //INT_MAX等 #include //标准输入输出头文件,包括EOF(=^Z或F6),NULL等 #include //atoi(),exit() #include //eof #include //数学函数头文件,包括floor(),ceil(),ads()等 #include //ftime #include //提供宏va_start,va_arg,va_end用于存取变长参数表//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status; //status是函数的类型,其值是函数结果状态代码,如OK typedef int Boolean;//Boolean是布尔类型,其值是TRUE或FALSEint main(void){ timeb t1, t2; long t; double x, sum=1, sum1; int i, j, n; printf("请输入x n:"); scanf("%lf %d",&x, &n); ftime(&t1); // 求得当前时间 for(i=1; i<=n; i++) { sum1 = 1; for(j=1; j<=i; j++) sum1 = sum1*(-1.0/x); sum += sum1; } ftime(&t2); // 求得当前时间 t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); // 计算时间差 printf("sum=%lf,用时%ld毫秒\n",sum,t); return 0; }--------------------------------结果:请输入x n:123 10000sum=0.991935,用时160毫秒--------------------------------/*算1-1/x+1/(x*x)…的更快捷的算法 的时间复杂度为:T(n) = O(n) */ int main(void){ timeb t1, t2; long t; double x, sum1=1, sum=1; int i, n; printf("请输入x n:"); scanf("%lf%d",&x, &n); ftime(&t1); // 求得当前时间 for(i=1; i<=n; i++) { sum1 *= -1.0/x; sum += sum1; } ftime(&t2); // 求得当前时间 t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); // 计算时间差 printf("sum=%lf,用时%ld毫秒\n",sum,t); return 0;}-------------------------------- 结果: 请输入x n:123 10000sum=0.991935,用时0毫秒--------------------------------
算法执行过程中大概所占用的最大内存
空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数。记做:S(n) = O(f(n)) 随着问题规模n的增大,算法的所需存储空间的增长率和f(n)所占存储空间的函数增长率相同
一个程序在执行时除需要存储空间来存放本身的指令、常数、变量和输入的数据外,还需要一些对数据进行操作的工作单元和存储一些为实现计算机所需信息的辅助空间
算法原地工作指的是:算法所需的辅助空间为常量,即O(1)
要让别人容易理解
不易崩溃和对于异常有很好的处理
程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言
或者说
程序设计 = 数据结构 + 算法
是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称
数据是信息的载体
是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理
有时,一个数据元素可由若干个数据项组成
数据项是构成数据元素的不可分割的最小单位
例如:学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成
是性质相同的数据元素的集合,是数据的一个子集
例如:整数数据对象是集合N={0,±1,....}
数据结构包括三方面的内容:逻辑结构、存储结构、数据的运算
数据结构是一个二元组:Data_Structure = (D, S)
D:是数据元素的有限集S:是D上关系的有限集
数据的逻辑结构分为线性结构和非线性结构
物理结构(存储结构):数据结构在计算机中的表示(映像)
进而得到两种不同存储结构:
顺序存储结构
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中, 元素之间的关系可由:存储单元的邻接位置体现 优点:可以实现随机存取,每个元素占用最少的存储空间 缺点:只能使用相邻的一整块存储单元,会产生较多的外部碎片
链式存储结构
不要求逻辑上相邻的元素在物理位置上也相邻, 通过指针来表示元素之间的逻辑关系 优点:不会出现碎片现象,充分利用存储单元 缺点:每个元素因存储指针而占有额外存储空间,且只能实现顺序存取
索引存储结构
在存储元素信息的同时,建立附加的索引表 索引表中每项称为索引项,索引项的一般形式(关键字,地址) 优点:检索速度快 缺点:附加的索引表额外占有存储空间,增加和删除数据时要修改索引表
散列存储结构
根据元素的关键字直接计算出该元素存储地址,又称哈希(Hash)存储 优点:检索、增加、删除节点操作很快 缺点:若散列函数不好,则会出现元素存储单元的冲突,而解决冲突增加时间和空间开销
虽然存储结构涉及数据元素及其关系在存储器中物理位置,但我们可以借助高级语言中提供的数据类型来描述。
例如: 一维数组类型描述顺序存储结构 指针来描述链式存储结构
是一个值的集合和定义在这个值集上的一组操作的总称
例如:
C语言中的整型变量,其值集为某个区间上的整数,定义在其上的操作为加、减、乘、除和取模等算术运算
例如:C语言的基本类型(整型、实型、字符型、指针类型)
例如:数组
定义:指一个数学模型以及定义在模型上的一组操作,仅取决于它的一组逻辑特性,与在计算机内部如何表示和实现无关
表示:(D, S, P)
D:是数据对象 S:是D上的关系集 P:是对D的基本操作集
ADT 抽象数据类型名{ 数据对象: <数据对象的定义> 数据关系: <数据关系的定义> 基本操作: <基本操作的定义> }ADT 抽象数据类型名 基本操作的定义> 数据关系的定义> 数据对象的定义>
基本操作的定义格式:
基本操作名(参数表) 初始条件: <初始条件描述> 操作结果: <操作结果描述>操作结果描述> 初始条件描述>
注:
注:Triplet &T 说明参数是一个指向指针的引用。形参中的&表示该形参是一个引用类型
C语言里面没有引用的说法,是C++特有的。C++里引用就是给变量定义一个别名,操作这个别名就是操作原变量。
比如,我们定义一个引用:
int a=10; //定义一个普通变量int &ref=a; //定义一个变量a的引用ref = 20; //这里对ref进行操作其实就是对a进行操作
比如定义一个参数是引用的函数
void func(int &b){ b++;}//调用int a=100;func(a); //调用的时候直接传递参数进去上面的方式可以实现和指针一样的效果,但是更加方便
/*引用类型的变量,其值若在函数中发生变化,则变化的值会带回主调函数中以下程序说明函数中引用类型变量和非引用类型变量的区别 */ //文件名 #include//字符串函数头文件 #include //字符函数头文件 #include //malloc()等 #include //INT_MAX等 #include //标准输入输出头文件,包括EOF(=^Z或F6),NULL等 #include //atoi(),exit() #include //eof #include //数学函数头文件,包括floor(),ceil(),ads()等 #include //ftime #include //提供宏va_start,va_arg,va_end用于存取变长参数表//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status; //status是函数的类型,其值是函数结果状态代码,如OK typedef int Boolean;//Boolean是布尔类型,其值是TRUE或FALSEvoid fa(int a) //在函数fa中改变a,将不会待会主调函数(主调函数中a任是原值){ a++; printf("在函数fa中:a = %d\n", a); } void fb(int &a) //由于a为引用类型,在函数中改变a,其值将带回主调函数{ a++; printf("在函数fb中:a = %d\n", a); } int main(void){ int n = 1; printf("在主程序中,调用函数fa之前:n = %d\n", n); fa(n); printf("在主程序中,调用函数fa之后,调用fb函数之前:n = %d\n", n); fb(n); printf("在主程序中,调用函数fb之后:n = %d\n", n); return 0;}
//文件名 #include//字符串函数头文件 #include //字符函数头文件 #include //malloc()等 #include //INT_MAX等 #include //标准输入输出头文件,包括EOF(=^Z或F6),NULL等 #include //atoi(),exit() #include //eof #include //数学函数头文件,包括floor(),ceil(),ads()等 #include //ftime #include //提供宏va_start,va_arg,va_end用于存取变长参数表//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status; //status是函数的类型,其值是函数结果状态代码,如OK typedef int Boolean;//Boolean是布尔类型,其值是TRUE或FALSEtypedef int ElemType; //定义抽象数据类型ElemType在本程序中为整型typedef ElemType * Triplet; //Triplet类型是ElemType类型的指针,存放ElemType类型的地址//抽象数据类型Triplet和ElemType的基本操作函数Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //操作结果:构造三元组T,依次置T的三个元素的初值为v1,v2,v3 T = (ElemType *)malloc(3*sizeof(ElemType)); //分配三个元素的存储空间 if(!T) //如果malloc函数分配失败返回0,那么!0就是1,if条件为1就会执行下面语句 exit(OVERFLOW); T[0] = v1; T[1] = v2; T[2] = v3; return OK; }Status DestroyTriplet(Triplet &T){ //操作结果:三元组T被销毁 free(T); //释放T所指向的三元组的存储空间 T = NULL; //T不再指向任何单元 return OK; } Status Get(Triplet T, int i, ElemType &e){ //初始条件:三元组T已经存在,1<=i<=3 //操作结果:用e返回T的第i个元素的值 if(i<1 || i>3) //i不再三元组的范围 return ERROR; e = T[i-1]; //将三元组T的第i个元素的值赋给e return OK; }Status Put(Triplet T, int i, ElemType e){ //初始条件:三元组T已经存在,1<=i<=3 //操作结果:改变T的第i个元素的值为e if(i<1 || i>3) return ERROR; T[i-1] = e; //将e的值赋给三元组T的第i个元素 return OK; }Status IsAscending(Triplet T){ //初始条件:元组T已经存在 //操作结果:如果T的三个元素按升序排列,则返回1,否则返回0 return(T[0]<=T[1]&&T[1]<=T[2]); //只有在T[0]不大于T[1]且T[1]不大于T[2]时返回真 } Status IsDescending(Triplet T){ //初始条件:元组T已经存在 //操作结果:如果T的三个元素按降序排列,则返回1,否则返回0 return(T[0]>=T[1]&&T[1]>=T[2]); //只有在T[0]不小于T[1]且T[1]不小于T[2]时返回真 } Status Max(Triplet T, ElemType &e){ //初始条件:元组T已经存在 //操作结果:用e返回指向T的最大元素的值 e = (T[0]>=T[1]) ? (T[0]>=T[2] ? T[0]:T[2]) : (T[1]>=T[2] ? T[1]:T[2]); //嵌套的条件运算符 return OK; } Status Min(Triplet T, ElemType &e){ //初始条件:元组T已经存在 //操作结果:用e返回指向T的最小元素的值 e = (T[0]<=T[1]) ? (T[0]<=T[2] ? T[0]:T[2]) : (T[1]<=T[2] ? T[1]:T[2]); //嵌套的条件运算符 return OK; } //输出函数void PrintE(ElemType e) //输出元素的值{ printf("%d\n", e); //定义ElemType为整型 } void PrintT(Triplet T) //依次输出三元组的值{ printf("%d, %d, %d\n", T[0], T[1], T[2]); //定义ElemType为整型 } //主函数int main(void){ Triplet T; ElemType m; Status i; i = InitTriplet(T, 5, 7, 9); //初始化三元组T,其三个元素依次为5,7,9 printf("调用初始化函数后,i = %d(1:成功)。T的三个值为", i); PrintT(T); //输出T的3个值 i = Get(T, 2, m); //将三元组T的第二个值赋给m if(i == OK) //调用Get成功 { printf("T的第二个值为:"); PrintE(m); //输出m } i = Put(T, 2, 6); //将三元组T的第二值改为6 if(i == OK) //调用Put成功 { printf("将T的第二个值改为6后,T的3个值为:"); PrintT(T); } i = IsAscending(T); //测试升序的函数 printf("调用升序的函数后,i = %d(0:否 1:是)\n", i); i = IsDescending(T); //测试降序的函数 printf("调用降序的函数后,i = %d(0:否 1:是)\n", i); if((i = Max(T, m)) == OK) //先赋值再比较 { printf("T中的最大值为:"); PrintE(m); } if((i = Min(T, m)) == OK) //先赋值再比较 { printf("T中的最小值为:"); PrintE(m); } DestroyTriplet(T); //函数也可以不带返回值 printf("销毁T后,T = %u\n", T); //%u表示无符号十进制数 return 0; } 输出结果:调用初始化函数后,i = 1(1:成功)。T的三个值为5, 7, 9T的第二个值为:7将T的第二个值改为6后,T的3个值为:5, 6, 9调用升序的函数后,i = 1(0:否 1:是)调用降序的函数后,i = 0(0:否 1:是)T中的最大值为:9T中的最小值为:5销毁T后,T = 0--------------------------------
转载地址:http://poxzi.baihongyu.com/