绪论

数据结构

  1. 逻辑结构

    1. 线性结构：线性表，栈，队列
    2. 非线性结构：树、图、集合

  2. 存储结构（物理结构）

    1. 顺序存储

    2. 链式存储

    3. 索引存储

      一般存储形式是（关键字，地址）

    4. 散列存储

  1. 数据的运算

运算的定义是针对逻辑结构的、运算的实现是针对存储结构的

抽象数据结构定义了数据的取值范围和其结构形式，以及对数据操作的集合

五个特征

  1. 算法定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列
  2. 有穷性、确定性、可行性、输入、输出

一个好的算法应该考虑达到下面的目标

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 高效率与低存储量需求

一般总是考虑一个在最坏情况下的时间复杂度，来保证算法运行时间不会比它更长

易错题

  1. 可以用抽象数据类型来定义一个完整的数据结构

  2. 以下属于逻辑结构的是：有序表

  3. 在存储数据的过程中，通常不仅要存储各数据元素的值，而且要存储 数据元素之间的关系

  4. 要注意算时间复杂度的时候那个算法循环条件，不要把变量看错了

  5. 下面程序段的时间复杂度：

1
2
3
4
5
int sum=0;
for(int i=1;i<n;i++){
    for(int j=1;j<i;j++)
        sum++;
}

这里我们假设 是最后一次循环，那么就有

一共有q次循环，这样该题的时间复杂度为 $O(n)$

  1. 注意循环条件,这里循环条件是 i，所以时间复杂度为 $O(n)$
1
2
3
4
5
i=1,k=0;
while(i<n-1){
	k=k+10*i;
	i++;
}

拓展斐波那契数列

递归

1
2
3
4
5
6
7
int f1(int n)
{
	if(n <= 2)
		return 1;
	else
		return f1(n-1) + f1(n-2);
}

时间复杂度为 $ O(2^n) $

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
int f2(int n)
{
	int t,first = 1,second = 1;
	if(n == 1 || n == 2)
		return 1;
	for( ; n>=3; n--)
	{
		t = first+second;
		first = second;
		second = t;
	}
	return t;
}

时间复杂度 $ O(n) $