浙大《数据结构》学习&练习（一）算法初步

1.数据结构是数据在计算机中的组织方式，类比图书在图书馆中的存储，应该如何分类，如何在书架上存取。

2.抽象数据结构是对一类的数据的一种组织方式的通用（抽象）描述，包括类型的名称，数据对象集和操作集。数据对象集定义了是什么样类型的数据，操作集定义了数据的处理方式。

3.评价算法的优劣使用时间复杂度T(N)和空间复杂度S(n)。前者体现了算法占用的时间，后者体现了算法占用的存储空间，都和数据的规模有关。

4.测试程序运行时间的一个传统方法。

#include <time.h>

//clock()会返回程序开始运行到clock()被调用时的时间

//CLK_TCK是个常数，为机器时钟每秒走的打点数

//clock_t是函数clock()的返回类型，即时钟打点clock tick

clock_t start, stop;

double duration;

int main()

{

    //把要测试的内容放在clock()调用的地方

    start = clock();    //start为程序运行到第一次调用的时间

    anyFunction(); //某个函数

    stop = clock();    //stop为程序运行到第二次调用的时间

    duration = ((double)(stop - start)) / CLK_TCK;

}

5.应用实例：求最大子列和问题

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；
数据2：102个随机整数；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；

输入格式:

输入第1行给出正整数K (≤)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6

-2 11 -4 13 -5 -2

输出样例:

第四种算法精妙就精妙在它的处理思路是一个一个数字处理，简单推导一下，只要当前子列与新加入的数的和是负数，那么新加入的数必定是大于现在的最大和的，那当前子列的结果就可以抛弃，最大的子列直接变成新加入的数本身，然后从该数开始重新累加即可。

测试代码（C++）：

#include<iostream>

using std::cout;

using std::cin;

int MaxSubSeqSum2(int A[], int N);

int MaxSubSeqSum4(int A[], int N);

int main()

{

    int Numbers;

    //cout << "How many integer numbers in total?\n";

    cin >> Numbers;

    int *A = new int [Numbers];

    //cout << "Enter the numbers:\n";

    for (int i = 0; i < Numbers; i++)

    {

        cin >> A[i];

    }

    cout << MaxSubSeqSum4(A, Numbers) << "\n";

    delete []A;

    system("pause");

    return 0;

}

/* tranditional algorithm */

int MaxSubSeqSum2(int A[], int N)

{

    int ThisSum;

    int MaxSum = 0;

    /* head begin from 0,1,...,n */

    for (int n = 0; n < N; n++)

    {

        /* ThisSum stores results of every subquene for current head */

        ThisSum = 0;

        for (int j = n; j < N; j++)

        {

            ThisSum += A[j];

            if (ThisSum > MaxSum)

            {

                MaxSum = ThisSum;    /* update MaxSum */

            }

            else

            {

                /* do nothing */

            }

        }

    }

    return (MaxSum > 0 ? MaxSum:0);

}

/* better algorithm */

int MaxSubSeqSum4(int A[], int N)

{

    int ThisSum = 0;

    int MaxSum = 0;

    /* handle one number each time */

    for (int i = 0; i < N; i++)

    {

        ThisSum += A[i];

        if (ThisSum > MaxSum)

        {

            MaxSum = ThisSum;    /* update MaxSum */

        }

        else if (ThisSum < 0)    /* the next number must be larger than MaxSum */

        {

            ThisSum = 0;    /* so current subseq is meaning less */

        }

        else

        {

            /* do nothing */

        }

    }

    return MaxSum;

}

巴特西

浙大《数据结构》学习&练习（一）算法初步

输入格式:

输出格式:

输入样例:

输出样例:

最新文章

热门文章