什么是数据结构
“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出”——SartajSahni,《数据结构、算法与应用》
“数据结构是ADT(抽象数据类型AbstractDataType)的物理实现。”——CliffordA.Shaffer,《数据结构与算法分析》
“数据结构(datastructtu)是计算机中存储、组织数据的方式。通常情况下，经i想你选择的数据结构可以带来最优效率的算法。”——中文维基百科
目前没有官方的定义。
思考：解决问题方法的效率，跟什么有关呢？
①解决问题方法的效率，跟数据的组织方式有关
例1：如何在书架上摆放书籍？
首先这个问题是不科学的，没有告诉书架的是什么样子的。
图书的摆放要使得2个相关操作方便实现：
操作1：新书怎么插入？
操作2：怎么找到某本指定的书？
解决方法：
方法1：随便放
累死......
哪里有空放哪里，一步到位
操作1：新书怎么插入？
操作2：怎么找到某本指定的书？
方法2：按照书名的拼音字母顺序排放
二分查找
操作1：新书怎么插入？
操作2：怎么找到某本指定的书？
方法3：把书架划分成几块区域，每块区域指定摆放某种类别的图书，在每种类别内，按照书名的拼音字母顺序排放
先定类别，再二分查找
先定类别，二分查找确定位置，移出空位
操作1：新书怎么插入？
操作2：怎么找到某本指定的书？
问题来了：空间如何分配？类别应该分多细？
②解决问题方法的效率，跟空间的利用效率有关。
例2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。
两种不同的实现方式：
循环实现的函数：递归实现的函数：voidPrintN(intN){voidPrintN(intN){inti;if(N){for(i=1;i=N;i++){PrintN(N-1);printf("%d",i);Printf("%d",i);}}}}
如何比较这两个函数的执行效率呢？不妨将N=，0，00，000，......
测试程序：
#includestdio.hvoidPrintN(intN);intmain(){intN;scanf("%d",N);PrintN(N);turn0;}
当N=时：(经测试，N=10，，0，两个函数的显示都是正常的)
当N=000时，显示出问题：循环实现的函数运行正常，但是递归实现的函数无法运行。
递归函数虽然简单、容易理解，但是对空间的占用率大，一般电脑不会选择执行递归的程序，当它将所有能利用的空间占用后，就直接爆掉，所以在N等于000时，没有任何输出。
③解决问题方法的效率，跟算法的巧妙程度有关
例3：写程序计算给定多项式在给定点x处的值。f(x)=a0+a1x+...+an-1xn-1+anxn
最傻最直接的算法：对标准多项式的一个直接翻译
1doublef(intn,doublea[],doublex){2inti;3doublep=a[0];4for(i=1;i=n;i++){5p+=(a[i]*pow(x,i));//累加求和6}7turnp;8}
这种写法比较low，专业处理方式：利用结合律，将函数的形式改成：f(x)=a0+x(a1+x(...(an-1+x(an))))
处理这个问题的标准程序：
1doublef(intn,doublea[],doublex){2inti;3doublep=a[n];4for(i=n;i0;i--){5p=a[i-1]+x*p;6}7turnp;8}
凭什么说第二个函数比第一个函数要好呢？——当然是因为第二个函数的执行效率高啦！C语言里面提供了clock()这个函数用于测试。
clock()：捕捉从程序开始运行到clock()被调用所耗费的时间。这个时间单位是clocktick,即“时钟打点”。
配套的常数CLK_TCK：机器时钟每秒所走的时钟打点数。
常用的测试模板
#includestdio.h#includetime.h//需要引入这个头文件clock_tstart,stop;/*clock_t是clock()函数返回的变量类型*/doubleduration;/*记录被测函数运行时间，以秒为单位*/intmain(){/*不在测试范围内的准备工作写在clock()调用之前*/start=clock();//开始计时MyFunction();//被测函数写在这里stop=clock();//停止计时duration=((double)(stop-start))/CLK_TCK;//换算成以秒为单位 /*其他不在测试范围内的处理写在后面，例如输出duration的值*/turn0;}
下面我们写程序计算多项式在给定点x=1.1处的值f(1.1)
测试程序：
1#includestdio.h2#includemath.h3#includetime.h4clock_tstart,stop;5doubleduration;6#defineMAXN10//多项式最大项数，即多项式阶数+17doublef1(intn,doublea[],doublex);8doublef2(intn,doublea[],doublex);9intmain(){10inti;11doublea[MAXN];//存储多项式的系数12for(i=0;iMAXN;i++)13a[i]=(double)i;14start=clock();f1(MAXN-1,a,1.1);17stop=clock();18duration=((double)(stop-start))/CLK_TCK;19printf("ticks1=%f\n",(double)(stop-start));20printf("duration1=%6.2fe\n",duration);start=clock();23f2(MAXN-1,a,1.1);24stop=clock();25duration=((double)(stop-start))/CLK_TCK;26printf("ticks2=%f\n",(double)(stop-start));27printf("duration2=%6.2fe\n",duration);turn0;30}doublef1(intn,doublea[],doublex){34inti;35doublep=a[0];36for(i=1;i=n;i++){37p+=(a[i]*pow(x,i));//累加求和38}39turnp;40}41doublef2(intn,doublea[],doublex){42inti;43doublep=a[n];44for(i=n;i0;i--){45p=a[i-1]+x*p;46}47turnp;48}
结果：
原因：两个函数的运行速度太快，都不满足一个tick，clock函数根本捕捉不到两个函数的区别
解决方案：让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可！
1......2#defineMAXK1e7//被测函数最大重复次数3......4intmain(){5......6start=clock();7for(i=0;iMAXK;i++)8f1(MAXN-1,a,1.1);9stop=clock();10duration=((double)(stop-start))/CLK_TCK/MAXK;//计算单次运行时间11printf("ticks1=%f\n",(double)(stop-start));12printf("duration1=%6.2fe\n",duration);13......14turn0;15}16......
结果：第一个比第二个函数慢了接近一个数量级
所以到底什么是数据结构？
它是数据对象在计算机中的组织方式
逻辑结构：一对一的线性结构，一对多的树结构，多对多的图结构
物理存储结构：连续和非连续
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
描述数据结构：抽象数据类型(ADT)
数据类型
数据对象集
数据集合相关联的操作集
抽象：描述数据类型的方法不依赖与具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关
只描述数据对象集和相关擦做集“是什么”，并不涉及“如何做到”的问题。
例4：“矩阵”的抽象数据类型定义
类型名称：矩阵(Matrix)
数据对象集：一个M×N的矩阵AM×N=(aij)(i=1,...,M;j=1,...,N)由M×N个三元组a,i,j构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。
操作集：对于任意矩阵A、B、C数据MAtrix，以及整数i,j,M,N
MatrixCate(intM,intN):返回一个M×N的空矩阵；
intGetMaxRow(MatrixA):返回矩阵A的总行数；
intGetMaxCol(MatrixA):返回矩阵A的总列数；
ElementTypeGetEntry(MatrixA,inti,intj):返回矩阵A的第i行、第j列的元素；
MatrixAdd(MatrixA,MatrixB):如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志；
MatrixMultiply(MatrixA,MatrixB):如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；
......
第一个抽象点：ElementType:这样数据在进行各种处理时可以不必考虑数据的具体类型，可用一个通用的返回类型
第二个抽象点：定义的Matrix，可以不用关心数据的存储结构是二维数组还是一维数组还是十字链表
第三个抽象点：进行矩阵加法时，不关心按行加还是按列加，具体用什么语言实现也不用考虑
赞赏