数据结构没有官方统一定义,可以理解为计算机中存储,组织数据的方式.

例1.如何在书架上摆放图书?
其实这个问题很不科学,因为不知道数据的规模,数据如何组织与数据的规模有关系,不一样规模的问题处理起来的难度不一样.

结论:解决问题方法的效率,跟数据的组织方式有关.

例2.写程序实现一个函数PrintN,使得传入一个正整数N的参数后,能顺序打印从1到N的全部正整数.
方法一:循环实现

void PrintN(int N)

{

    int i;

    for(i=1; i <= N; i++)

    {

        printf("%d\n",i);

    }

}

方法二:递归实现

void PrintN(int N)

{

    if(N)

    {

        PrintN(N-1);

        printf("%d\n",N);

    }

}

随着数据规模的增大,循环可以正常输出,而递归就会罢工,因为递归消耗内存太多,内存不够时会非正常终止.

结论:解决问题方法的效率跟空间的利用效率有关.

例3:写程序计算给定多项式f(x)=a₀+a₁x+...+a_n-1x^n-1+a_nxⁿ在给定x处的值.
方法一:正常做法

double f(int n,double a[],double x)

{

    int i;

    double p = a[0];

    for(i=1; i <= n; i++)

    {

        p += (a[i] * pow(x,i));

    }

    return p;

}

方法二:化简
按照秦九韶的做法,根据结合律把公因子x提取出来化为:f(x)=a₀+x(a₁+x(...(a_n-1+x(a_n))...)),这样程序的复杂度就降下来了.

double f(int n,double a[],double x)

{

    int i;

    double p = a[n];

    for(i=n; i > 0; i--)

    {

        p = a[i-1] + x*p;

    }

    return p;

}

计算程序运行时间(秒):
clock():捕捉从程序开始运行到clock()被调用时所耗费的时间.这个时间单位是clock tick,即"时钟打点".
常数CLK_TCK:机器时钟每秒所走的时钟打点数(不同电脑可能不同).
模板:

#include &ltstdio.h>

#include &lttime.h>



clock_t start, stop;



double duration;



int main()

{

    start = clock();

    MyFunction();//被测函数

    stop = clock();

    duration = ((double)(stop - start))/CLK_TCK;

    printf("%lf\n",duration);

}

当两个函数被同时调用10⁷时,所差的时间大约是一个数量级.

结论:解决问题方法的效率,跟算法的巧妙程度有关.

所以到底什么是数据结构?

• 数据对象在计算机中的组织方式
• 数据对象必定与一系列加在其上的操作相关
• 完成这些操作所用的方法就是算法

抽象数据类型(Abstract Data Type)
数据类型

• 数据对象集
• 数据集合相关联的操作集

抽象

• 与存放数据的机器无关
• 与数据存储的物理结构无关
• 与实现操作的算法和编程语言均无关

只描述数据对象集合和相关操作集"是什么",并不涉及"如何做到"的问题.

例4."矩阵"的抽象数据类型定义
数据名称:矩阵(Matrix)
数据对象集:一个MxN的矩阵A_MxN=(a)(i=1,...,M;j=1,...,N)由MxN个三元组<a,i,j>构成,其中

,i是元素所在的行号,j是元素所在的列号.
操作集:对于任意矩阵A,B,C∈Matrix,以及整数i,j,M,N

• Matrix Create(int M,int N):返回一个MxN的空矩阵
• int GetMaxRow(Matrix A):返回矩阵A的总行数
• int GetMaxCol(Matrix A):返回矩阵A的总列数
• ElementType GetEntry(Matrix A, int i, int j):返回矩阵A的第i行,第j列的元素
• Matrix Add(Matrix A, Matrix B):如果A和B的行,列数一致,则返回矩阵C=A+B,否则返回错误标志
• Matrix Multiply(Matrix A, Matrix B):如果A的列数等于B的行数,则返回矩阵C=AB,否则返回错误标志
• ......

ElementType和a的类型并没有确定所以可以根据需要更改,这就是抽象类型.