数据结构第一讲

数据结构定义

算法的定义

什么是好算法？

空间复杂度

时间复杂度

例子1

打印1到N之间的正整数
有递归和循环两种方法实现。
但是在数字变大后，递归的方法会导致内存占用过多而崩溃。
而循环则不会

例子2 写程序给定多项式在X处的值

从里往外算的算法，不断提出一个X，然后从里往外算。

ElementType Max( ElementType S[], int N )
{
    int i = 0;
    float max = S[0];
    for (i = 1; i < N; i++)
    {
        if (max < S[i])
        {
            max = S[i];
        }
    }
    return max;
}

从里往外算的思路

从外往里算，复杂度高o(n的平方)。

例子3 给定N个整数的序列，求连续的最大子序列的值

1.三层for循环暴力

int MaxSubsequSum(int A[], int N)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int ThisSum = 0;
	int MaxSum = 0;
	for (i = 0; i < N; i++)
	{
		for (j = i; j < N; j++)
		{
			ThisSum = 0;
			for (k = j; k < j; k++)
			{
				ThisSum += A[i];
				if (ThisSum > MaxSum)
				{
					MaxSum = ThisSum;
				}
			}
		}
	}
}

2.两层for循环暴力

int MaxSubseqSum(int A[], int N)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int ThisSum = 0;
	int MaxSum = 0;
	for (i = 0; i < N; i++)
	{
		ThisSum = 0;

		for (j = i; j < N; j++)
		{
			ThisSum += A[i];
			if (ThisSum > MaxSum)
			{
				MaxSum = ThisSum;
			}

		}
	}
}

3.分而治之，递归解决

4.在线处理

每输入一个数据都能即时处理，在任何一个地方中止输入，都能正确给出当前的解。

int MaxSubseqSum(int A[], int N)
{
	int i = 0;
	int MaxSum = 0;
	int ThisSum = 0;
	for (i = 0; i < N; i++)
	{
		ThisSum += A[i];
		if (ThisSum > MaxSum)
		{
			MaxSum = ThisSum;
		}
		else if (ThisSum < 0)
		{
			ThisSum = 0;
		}
	}
	return MaxSum;
}