第一讲基本概念

数据结构浙江大学

Word count: 827Reading time: 4 min

 2019/06/23   Share

第一讲基本概念

1.1 什么是数据结构

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

解决问题方法的效率,跟数据的组织方式有关
例2:实现一个函数PrinN,使得传入一个正整数为N的参数后,能顺序打印从1到N的全部正整数

方法1:循环实现

方法2:递归实现

递归对空间的占用花销很大,以至于计算机内存有限无法拥有足够的空间运行该程序
1
2
3
4
5
6
7
8
9
void PrintN(int n)
{
if(n)
{
PrintN(n-1);
printf("%d\n",N);
}
return ;
}
解决问题方法的效率,跟空间的利用效率有关

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

$f(x)=a0+a_1x+….+a{n-1}x^{n-1}+a_nx^n$

$f(x)=a0+x(a_1+x(…(a{n-1}+xa_n)…))$

double f(int n,double a[],double x)
{
    int i;
    double p=a[n];
    //for(i=1;i<=n;i++) p+=(a[i]*pow(x,i));
    //for(i=n;i>0;i--) p=a[i-1]+x*p;
    return p;
}

计时函数模板:

#include<stdio.h>
#include<time.h>

clock_t start,stop;

double duration;

int main()
{
    start = clock();
    MyFunction();
    stop = clock();
    duratio= ((double)(stop-start))/CLK_TCK;
    return 0;
}

解决方法的效率与算法的方法有关

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

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

1.2 什么是算法

定义
例1:选择排序算法的伪代码描述
算法优劣判断指标
例2:递归函数的空间复杂度
例3:循环函数的时间复杂度
复杂度的渐进表示法
常用函数复杂度:
复杂度常用分析:

1.3 应用实例:最大子列的问题

算法1&2:复杂度(N^2,N^3)

循环嵌套

算法3:复杂度(NlogN)

int Max3(int a,int b,int c)
{
    return a>b?a>c?a:c:b>c?b:c;
}

int DivideAndConquer(int list[],int left,int right)
{
    int RightBoderSum,LeftBoderSum;
    int MaxRightBoderSum,MaxLeftBoderSum;
    int MaxleftSum,MaxRightSum;
    int center,i;

    if(left==right)
    {
        if(list[left]>0) return list[left];
        else return 0;
    }

    center=(left+right)/2;
    MaxleftSum=DivideAndConquer(list,left,center);
    MaxRightSum=DivideAndConquer(list,center+1,right);

    MaxRightBoderSum=0;RightBoderSum=0;
    for(i=center+1;i<=right;i++)
    {
        RightBoderSum+=list[i];
        if(RightBoderSum>MaxRightBoderSum)
        {
            MaxRightBoderSum=RightBoderSum;
        }
    }

    LeftBoderSum=0;MaxLeftBoderSum=0;
    for(i=center;i>=left;i--)
    {
        LeftBoderSum+=list[i];
        if(LeftBoderSum>MaxLeftBoderSum)
        {
            MaxLeftBoderSum=LeftBoderSum;
        }
    }

    return Max3(MaxleftSum,MaxRightSum,MaxLeftBoderSum+MaxRightBoderSum);
}

算法4:复杂度(N)

作业

二分法

  Position BinarySearch( List L, ElementType X )
  {
      
   if(L==NULL)
return NotFound;
      int left=1;
      int right=L->Last;
      //若是left=0;right=L->Last-1;开始会出现边界错误问题
      while(left<=right)
      {
          int center=(left+right)/2;
          if(L->Data[center]>X)
          {
              right=center-1;
          }
          else if(L->Data[center]<X)
          {
              left=center+1;
          }
          else
              return center;
      }
      return NotFound;
  }

Maximum Subsequence Sum

#include <stdio.h>
#include <stdlib.h>
#define Max 100000

int maxSum(int list[],int n,int *start,int *end)
{
    int i;
    int max=list[0];
    int sum=0;
    int j=0;
    *start=0;
    *end=0;
    for(i=0;i<n;i++)
    {
        sum+=list[i];
        if(sum>max)
        {
            max=sum;
            *end=i;
            *start=j;
        }
        else if(sum<0)
        {
            sum=0;
            j=i+1;
        }
    }
    *start=list[*start];
    *end=list[*end];
    if(max<0)
    {
        *start=list[0];
        *end=list[n-1];
        max=0;
    }
    return max;
}
int main()
{
   int list[Max];
   int n;
   int i;
   int start,end;
   int max;
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
       scanf("%d",&list[i]);
   }
   max=maxSum(list,n,&start,&end);
   printf("%d %d %d\n",max,start,end);
}

Next Post

Week1-Week5总结
Previous Post

week_5

CATALOG

1. 第一讲基本概念



第一讲 基本概念

第一讲 基本概念

1.1 什么是数据结构

总结

1.2 什么是算法

1.3 应用实例:最大子列的问题

作业

二分法

Maximum Subsequence Sum

第一讲基本概念

第一讲基本概念