陈越《数据结构》第一讲 基本概念
陈越《数据结构》第一讲 基本概念1什么是数据结构1.1 引子例子:如何在书架上摆放图书?
例2:写程序实现一个函数PrintN,使得传入一个正整数为N的参数后,能顺序打印从1到N的全部正整数。
例3:写程序计算给定多项式在给定点x处的值。
即:解决问题方法的效率,跟数据的组织方式、跟空间的利用效率和跟算法的巧妙程度有关。
1.2 抽象数据类型
抽象数据类型
2. 什么是算法
2.1什么是好的算法?
在例3中,第一种方法的时间复杂度是
2.2 一些基本概念
3.应用实例:最大子列和问题应用实例:最大子列和问题 //01 - 复杂度1 最大子列和问题(20分)
//例如给定序列{ -2,11,-4,13,-5,-2 },其连续子列{ 11,13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。
//
//本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下:
//
//数据1:与样例等价,测试基本正确性;
//数据2:10^2个随机整数;
//数据3:10^3个随机整数;
//数据4:10^4个随机整数;
//数据5:10^5个随机整数;
//输入格式 :
//
//输入第1行给出正整数KK(le 100000≤100000);第2行给出KK个整数,其间以空格分隔。
//
//输出格式 :
//
//在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。
//
//输入样例 :
//
//6
//- 2 11 - 4 13 - 5 - 2
//输出样例 :
//
// 20
分而治之的代码: #include<stdio.h>
#include<iostream>
#define MAXN 100000
int arr[MAXN + 10];
int maxThree(int a,int b,int c);
int maxSubSeq(int arr[],int low,int height);
int maxSubSeq1(int arr[],int n);
int main()
{
int i,n;
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%d",&arr[i]);
printf("%dn",maxSubSeq(arr,n-1));
system("pause");
return 0;
}
int maxSubSeq1(int arr[],int n)
{
int i = 0,iThisSum = 0,iMaxSum = 0;
for(i = 0; i < n; i++)
{
iThisSum += arr[i];
if(iThisSum > iMaxSum) iMaxSum = iThisSum;
else if(iThisSum < 0) iThisSum = 0;
}
return iMaxSum;
}
int maxSubSeq(int arr[],int height)
{
int i = 0,iMid = 0,iLeftMax = 0,iRightMax = 0,iLeftMaxSum = 0,iRightMaxSum = 0;
if(low >= height) return arr[low];
iMid = (low + height)/2;
iLeftMax = maxSubSeq(arr,low,iMid);//左边最大
iRightMax = maxSubSeq(arr,(iMid+1),height);//右边最大
//中间(跨越)最大
iThisSum = iLeftMaxSum = 0;
for(i = iMid ; i >low ; i-- )
{
iThisSum += arr[i];
if(iThisSum > iLeftMaxSum) iLeftMaxSum = iThisSum;
}
iThisSum = iRightMaxSum = 0;
for(i = iMid ; i <height ; i++)
{
iThisSum += arr[i];
if(iThisSum > iRightMaxSum) iRightMaxSum = iThisSum;
}
return maxThree(iLeftMax,iRightMax,(iRightMaxSum + iLeftMaxSum));
}
int maxThree(int a,int c)
{
int max = a;
if(b > max) max = b;
if(c > max) max = c;
return max;
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |