1.1 什么是数据结构

例1-如何在书架上摆放图书

图书的摆放要使得2个相关操作方便实现：

操作1：新书怎么插入？

操作2：怎么找到某本指定的书？

方法1：随便放

​ 操作1–哪里有空放哪里，一步到位！

​ 操作2–累死

方法2：按照书名的拼音字母顺序排放

​ 操作1：

​ 操作2：二分查找！

方法3：把书架划分成几块区域，每块区域指定摆放某种类别的图书；在某种类别内，按照书名的拼音字母顺序排放。

​ 操作1：先定类别，二分查找确定位置，移出空位

​ 操作2：先定类别，再二分查找

问题：空间如何分配？类别应该分多细？

解决问题方法的效率，跟数据的组织方式有关

例2-写程序实现一个函数PrintN，使得传入一个正整数N为参数后，能顺序打印从1到N的全部正整数

case 1：循环实现

void PrintN ( int N )
{
int i;
for ( i=1 ; i<=N ; i++ )
{
printf("%dn",i);
}
return ;
}

case 2：递归实现

void PrintN ( int N )
{
if（ N ）
{
PrintN( N-1 );
printf( "%dn",N );
}
return ;
}

递归方法占用的空间大

例3：写程序计算给定多项式在给定点x处的值

f(x)=a0 + a1x + … +a(n-1)x^(n-1) + a(n)x^n

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;
}

f(x)=a0 + x(a1 + 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<stdio.h>
#include<time.h>
clock_t start , stop ;
//clock_t 是 clock() 函数返回的变量类型
double duration;
//记录被测函数运行时间，以秒为单位
int main()
{//不在测试范围内的准备 工作写在clock()调用之前
start = clock();	//开始计时
MyFunction();
//把被测函数加在这里
stop = clock();
//停止计时
duration = ((double)(stop - start))/CLK_TCK;
//计算运行时间
//其他不在测试范围的处理写在后面，例如输出duration的值
return 0;
}

例3：写程序计算给定多项式

$$f(x)=\sum _{i=0}^{9}i{x}^i$$

在给定点x=1.1处的值f(1.1)

double f1( 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;
}

double f2( 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;
}

#include<stdio.h>
#include<time.h>
#include<math.h>
clock_t start , stop ;
double duration;
#define MAXK 1e7	//被测函数最大重复调用次数 
#define MAXN 10
//多项式最大项数，即多项式阶数+1
double f1( int n, double a[], double x );
double f2( int n, double a[], double x );
int main()
{
int i;
double a[MAXN];
//储存多项式的系数
for ( i=0 ; i<MAXN ; i++ )
a[i] = (double) i ;
start = clock();
for ( i=0 ; i<=MAXK ; i++ )
f1( MAXN-1 , a , 1.1 );
stop = clock();
duration = ((double)(stop - start))/CLK_TCK/MAXK;
printf("ticks1 = %fn" ,(double) ( stop - start ));
printf("duration1 = %6.2en", duration);
start = clock();
for ( i=0 ; i<=MAXK ; i++ )
f2( MAXN-1 , a , 1.1 );
stop = clock();
duration = ((double)(stop - start))/CLK_TCK/MAXK;
printf("ticks2 = %fn" ,(double) ( stop - start ));
printf("duration2 = %6.2en", duration);
return 0;
}
double f1( 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;
}
double f2( 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;
}

让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可！

什么是数据结构？？？

数据对象在计算机中的组织方式

​ 逻辑结构

​ 物理存储结构

数据对象必定与一系列加在其上的操作相关联

完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）

数据类型

​ 数据对象集

​ 数据集合相关联的操作

抽象：描述数据类型的方法不依赖于具体实现

​ 与存放数据的机器无关

​ 与数据存储的物理结构无关

​ 与实现操作的算法和编程语言均无关

​ 只描述数据对象集合相关操作集“是什么”，并不涉及“如何做到”的问题

例4 ：“矩阵”的抽象数据类型定义

类型名称：

矩阵（Matrix）

数据对象集：

一个MM的矩阵
$$A_{m\ast n}=(a_{ij})(i=1,\cdots ,N)$$
由MN个三元组< a , i , j >构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号

操作集：

对任意矩阵 A , B , C 属于Matrix，以及整数 i , j , M , N

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

最后

以上就是帅气钢笔为你收集整理的数据结构 1.1 什么是数据结构1.1 什么是数据结构什么是数据结构？？？的全部内容，希望文章能够帮你解决数据结构 1.1 什么是数据结构1.1 什么是数据结构什么是数据结构？？？所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。