iloveflag-blog

数据结构

字数统计: 681阅读时长: 3 min
2020/06/13 Share

基本概念

什么是数据结构


试一下在机器上运行的结果

source:

1.9.c

1.10.c


递归的空间占用大

source:1.11.c

bug:

CLK_TCK问题

pow问题

运行结果:

source:1.12.c

2020-06-26_13-09-55

什么是算法


1
2
3
4
5
6
void PrintN(int N){
if(N){
PrintN(N-1);
printf("%d\n",N);
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
double f1(int n,double a[],double x)
{
int i;
double p = a[0];
for (i=1;i<=n;i++){
p+=(a[i]*pow(x,i));
}
return p;
}
double f2(int n,double a[],double x){
int i;
double p = a[n];
for (i=n;i>0;i--){
p=a[i-1]+x*p;
}
return p;
}

f1复杂度

f2复杂度

最大子列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MaxSubseqSum1( int A[], int N )  
{ int ThisSum, MaxSum = 0;
int i, j, k;
for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
for( j = i; j < N; j++ ) { /* j是子列右端位置 */
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( k = i; k <= j; k++ )
ThisSum += A[k];
if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j循环结束 */
} /* i循环结束 */
return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSubseqSum2( int A[], int N )  
{ int ThisSum, MaxSum = 0;
int i, j;
for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( j = i; j < N; j++ ) { /* j是子列右端位置 */
ThisSum += A[j]; /*对于相同的i,不同的j,只要在j-1次循环的基础上累加1项即可*/
if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j循环结束 */
} /* i循环结束 */
return MaxSum;
}

分而治之算法


$T(N)=2T(N/2)+C*N$
$T(1)=O(1)$

在线处理算法

1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSubseqSum4( int A[], int N )  
{ int ThisSum, MaxSum;
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;
}

线性结构

线性表及其实现

引子-多项式表示:

方法1:顺序存储结构直接表示

$f(x)=4x^5-3x^2+1$
20200714164452.png

方法2:顺序存储结构表示非零项

image-20200722101518799

方法3:链表结构储存非零项

image-20200722101912735

线性表的顺序存储实现:

image-20200722102912028

image-20200722103111856

image-20200722103432460

线性表的链式存储实现

image-20200722104009649

image-20200722104253400

CATALOG
  1. 1. 基本概念
    1. 1.1. 什么是数据结构
    2. 1.2. 什么是算法
    3. 1.3. 最大子列问题
  2. 2. 线性结构
    1. 2.1. 线性表及其实现
      1. 2.1.1. 引子-多项式表示:
        1. 2.1.1.1. 方法1:顺序存储结构直接表示
        2. 2.1.1.2. 方法2:顺序存储结构表示非零项
        3. 2.1.1.3. 方法3:链表结构储存非零项
      2. 2.1.2. 线性表的顺序存储实现:
      3. 2.1.3. 线性表的链式存储实现