首页 > 代码库 > 数据结构- 基本概念[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 ]