从头学数据结构--跟随浙大陈越姥姥的步伐

1.1什么是数据结构：

数据对象在计算机中的组织方式

逻辑结构 ：线性结构（一对一），树形结构（一对多）

物理存储结构：

数据对象必定与一系列加在其上的操作相关联

完成这些操作所用的方法就是算法

描述数据结构的方法：抽象数据类型（Abstract Data Type）

抽象：

与存放数据的机器无关

与数据存储的物理结构无关

与实现操作的算法和编程语言均无关

数据类型：

数据对象集

数据集合相关联的操作集

只描述数据对象集和相关操作集”是什么“，并不涉及”如何做到“的问题

例：”矩阵“的抽象数据类型定义

类型名称：矩阵（Matrix）

数据对象集：一个MN的矩阵A（MN） = （A..........告辞！放弃了

伪代码。

）

1.2 什么是算法（Algorithm）

一个有限指令集

接收一些输入（有些情况下不需要输入）

产生输出

一定在有限步骤之后终止

每一条指令必须

有充足明确的目标，不可以有歧义

计算机处理的范围之内

描述应不依赖于任何一种计算机语言以及具体的实现手段

例一：选择排序算法的伪代码描述：

void SelectionSort (int List[],int N)
{/*将N个整数List[0]...List[N-1]进行非递减排序（可能有相同值排序，因此叫递增的话不是很确切）*/
    for(int i= 0;i<N;i++){
        
        MinPosition = ScanForMin(List,i,N-1);//ScanForMin为查找最小元所在位置函数
        /*从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition;*/
        
        Swap(List[i],List[MinPosition]);//swap为交换函数
        /*将未排序部分的最小元(List[MinPosition])换到有序部分的最后位置(List[i-1])；*/
            
    }
    
}

抽象--------

List到底是数组还是链表？（虽然看上去像数组）

Swap用函数还是用宏实现？

什么是好算法？

1：空间复杂度S（n）

2：时间复杂度T（n）

例二：递归

Void PrintN(int N){
if(N){
    printN(N-1);
    printf("%d\n",N);
    }
    return;
}

S(N) = C*N

两种复杂度：

最坏情况复杂度 T worst(n)

平均复杂度 T avg(n)

复杂度的渐进表示法

T（n） = O（f（n））表示存在常数C>0，n 0>0 使得当 n>=n 0时有T（n）<=C*f(n)

由图可知，当复杂度为log n 时为最好的算法

复杂度分析小窍门

从头学数据结构--跟随浙大陈越姥姥的步伐

原文：https://www.cnblogs.com/destiny-2015/p/13378776.html