首页 > 代码库 > 数据结构- 基本概念[Chapter1 ]
数据结构- 基本概念[Chapter1 ]
数据结构
- 并无明确定义 - 不过有一个我很喜欢的
数据结构是ADT（抽象数据类型Abstract Data Type）的物理实现。
- 与算法相关
解决问题方法的效率与：
- 数据的组织方式有关 → 书架问题
- 空间的利用效率有关
循环解决PrintN
void PrintN(int N){ int i; for (i = 1 ;i<N ;i++) printf("%d\n", i); return ;}
递归解决
void PrintN(int N){ if(N){ printN(N-1); printf("%d\n",N); } return ;}
这里递归的原理是当 N >=1 时候会不断的调用PrintN(N-1),比如在一个stack上一直堆积...
直到调用到PrintN（1），此时会执行最PrintN（0）PrintN（0）不满足if（N）的条件，会直接return，然后每一个调用的stack上的逐个return回来，形成从1打印到N....
过程应该如图
PrintN(N) print N
|
PrintN(N-1) print N -1
|
.......
|
PrintN(0) return
而如果N太大就会把stack内存用完，递归算法就无法执行
注意因为Stack是一层传递到上一层到上一层，所以打印顺序就是1，2，....N
- 跟算法的巧妙程度有关
算多项式的值
定义式算法
f(x) = a0 + a1x +...+an-1xn-1 + anxn
double f(int n, double a[], double x){ int i; double p[0] = a[0]; for (int i = 1; i <= n; i++) p += ( a[i] * pow(x,i)) return p;}
巧妙一点的算法
f(x) = a0 + x(a1 +x(...+(an-1 + x(an))...))
double f(int n, double a[], double x){ int i; double p = a[n]; for (int i = n; i > 0; i--) p = a[i-1] + x*p; return p;}
抽象数据类型
关心数据对象集和相关操作“是什么”，不那么关心如何实现
例子
类型名称： 矩阵（Matrix）
对象集：AM,N = (aij)(i = 1,....M;j=1,....N)
操作集：
Matrix Create(int M, int N)
int GetMaxRow(Matrix A)
int GetMaxCol(Matrix B)
ElementType GetEntry(Matrix, int i, int j)
Matrix Add(Matrix A, Matrix B)
Matrix Multiply(Matrix A, Matrix B)
....
实际上我觉得如果有学过一门面向对象的语言会更容易理解,类也是抽象出来的,是被我们封装好了,然后留有接口给外部用
抽象数据类型的抽象就有一点面向对象的感觉,同一种数据类型,比如Stack，我们可以在python中写，也可以在C中写（C的对象性没有那么强），但我们调用pop函数，返回的都是stack顶上的那个element，而Elementtype正是告诉了我们这个Stack中可以装int，float,甚至struct，搞懂了一种数据类型，之后此种的implement，使用就会呈现一劳永逸的状态
在学的过程中，我觉得首先要抽象化，比如queue，比如stack，比如linked list先明白针对这种数据类型一些特有的操作和带来的结果
抽象化之后再来代码化，美化，优化，同时把这种数据类型的代码好好自己留下来，因为自己写的总顺手嘛，而且以后用的机会可多了.....
算法
算法顾名思义：计算方法
void SelectionSort( int List[], int N ){
/*将N个整数List[0]...List[N-1]进行非递减排序 */ for (i = 0 ; i < N; i++){ MinPosition = ScanForMin(List, i, N-1);
/*从List[i]到List[N–1]中找最小元,并将其位置赋给MinPosition */ Swap(List[i], List[MinPosition]);
/*将未排序部分的最小元换到有序部分的最后位置 */ }}
算法复杂度
空间复杂度 S(n)
时间复杂度 T(n)
最大子列和问题
给定N个整数的序列｛A1,A2,...AN} , 求函数 f(i,j) = max(0,∑jk = i的最大值Ak）的最大值
算法一：
int MaxSubseqSum1( int A[], int N){ int ThisSum, MaxSum = 0; int i, j, k; for( i = 0; i < N; i++){ for( j = i; j < N; j++){ ThisSum = 0; for( k = i ; k<= j ; k++) ThisSum += A[k]; if(ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum;}容易理解
但是 T(N) = O(N3)
算法二：
int MaxSubseqSum2( int A[], int N){ int ThisSum, MaxSum = 0; int i, j; for( i = 0; i < N; i++){ ThisSum = 0; for(j = i; j < N; j++){ ThisSum += A[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum;}T(N) = O(N2)
算法三
分而治之
....
算法四
int MaxSubseqSum4( int A[], int N){ int ThisSum, MaxSum = 0; int i; ThisSum = MaxSum = 0; for(i = 0 ; i < N; i++){ ThisSum += A[i]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if(ThisSum < 0) ThisSum = 0; } } return MaxSum;}
T( N ) = O( N )
数据结构- 基本概念[Chapter1 ]