首页 > 代码库 > 数据结构的基本概念

数据结构的基本概念

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

 

数据结构的基本概念