首页 > 代码库 > 数据结构的基本概念
数据结构的基本概念
1、写程序实现一个函数printN,使得传入一个正整数N,顺序打印1到N的全部正整数
#include <stdio.h>
#include <time.h>
void printLoopN(int N);
void printRecursionN(int N);
int main()
{
clock_t startLoop;
clock_t finishLoop;
double durationLoop;
clock_t startRecursion;
clock_t finishRecursion;
double durationRecursion;
int N = 0;
scanf("%d",&N);//input N
//test printLoopN function
startLoop = clock();//begin time
printLoopN(N);
finishLoop = clock();//end time
durationLoop = (double)(finishLoop-startLoop)/CLOCKS_PER_SEC;
printf("%f Loop seconds\n",durationLoop);
//test printRecursionN function
//startRecursion = clock();
//printRecursionN(N);
//finishRecursion = clock();
//durationRecursion = (double)(finishRecursion-startRecursion)/CLOCKS_PER_SEC;
//printf("%f Recursion seconds\n",durationRecursion);
return 0;
}
void printLoopN(int N)
{
if(N>0)
{
int i;
for(i=0;i<=N;i++)
{
printf("%d\n",i);
}
}
else
{
printf("input number error...\n");
}
}
void printRecursionN(int N)
{
if(N>0)
{
printRecursionN(N-1);
printf("%d\n",N);
}
else
{
printf("input number error...\n");
}
}
递归非常吃内存,当N很大时,程序会崩掉
2、计算多项式在给定x点的值
#include <stdio.h>
#include <math.h>
#include <time.h>
#define MAXN 10000
double polynomialValue1(int n, double *a, double x);
double polynomialValue2(int n, double *a, double x);
int main()
{
double a[MAXN];
double value=http://www.mamicode.com/0;
clock_t start=0,stop=0;
double duartion=0;
int i=0;
double duration=0;
for(i=0;i<MAXN;i++)
{
a[i]=(double)i;
}
start=clock();
value=http://www.mamicode.com/polynomialValue1(MAXN-1,a,1.1);
stop=clock();
duration=(double)(stop-start)/CLK_TCK;
printf("polynomialValue1 time:%6.2e, %f\n",duration,value);
start=clock();
value=http://www.mamicode.com/polynomialValue2(MAXN-1,a,1.1);
stop=clock();
duration=(double)(stop-start)/CLK_TCK;
printf("polynomialValue2 time:%6.2e, %f\n",duration,value);
printf("%d,%d",CLK_TCK,CLOCKS_PER_SEC);
return 0;
}
double polynomialValue1(int n, double *a, double x)
{
int i = 0;
double p=a[0];
for(i=1; i<=n; i++)
{
p += (a[i]*pow(x,i));
}
return p;
}
double polynomialValue2(int n, double *a, double x)
{
int i = 0;
double p=a[n];
for(i=n; i>0; i--)
{
p =a[i-1]+p*x;
}
return p;
}
函数polynomialValue2运行的速度比polynomialValue1快一个数量级
数据结构:数据对象在计算机中的组织形式
数据对象必定与一系列加在其上的操作有关
实现这所用这些操作的方法叫算法
最大子列
int maxSubseqSum1(int*A, int N)
{
int thisSum,maxSum=0;
int i,j,k;
for(i=0;i<N;i++)
{
for(j=i;j<N;j++)
{
thisSum=0;
for(k=i;k<=j;k++)
{
thisSum+=A[k];
}
if(thisSum>maxSum)
{
maxSum=thisSum;
}
}
}
return maxSum;
}
int maxSubseqSum2(int*A, int N)
{
int thisSum,maxSum=0;
int i,j,k;
for(i=0;i<N;i++)
{
thisSum=0;
for(j=i;j<N;j++)
{
thisSum+=A[j];
if(thisSum>maxSum)
{
maxSum=thisSum;
}
}
}
return maxSum;
}
int maxSubseqSum4( int A[], int N )
{ int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for( i = 0; i < N; i++ ) {
ThisSum += A[i]; /* 向右累加 */
if( ThisSum > MaxSum )
MaxSum = ThisSum; /* 发现更大和则更新当前结果 */
else if( ThisSum < 0 ) /* 如果当前子列和为负 */
ThisSum = 0; /* 则不可能使后面的部分和增大,抛弃之 */
}
return MaxSum;
}
数据结构的基本概念