Scott's world.

第一讲 基本概念

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)…))$

    1
    2
    3
    4
    5
    6
    7
    8
    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;
    }

    计时函数模板:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #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)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    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)

作业

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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);
}
CATALOG
  1. 1. 第一讲 基本概念
    1. 1.1. 1.1 什么是数据结构
      1. 1.1.1. 总结
    2. 1.2. 1.2 什么是算法
    3. 1.3. 1.3 应用实例:最大子列的问题
    4. 1.4. 作业
      1. 1.4.1. 二分法
      2. 1.4.2. Maximum Subsequence Sum