数据结构

1.数据结构与算法相关术语

• 数据: 程序的操作对象,用于描述客观事物。

  • 可以输入到计算机
  • 可以被计算机处理

• 数据项: 一个数据元素由若干数据项组成。

//声明一个结构体类型
struct Doctor {     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
};

struct Doctor t1;     //数据元素;
struct Doctor tArray[10]; //数据对象;

• 数据元素: 组成数据的对象的基本单位。
• 数据对象: 性质相同的数据元素的集合(类似于数组)。
• 结构: 数据元素之间不是独立的,存在特定的关系.这些关系即是结构。
• 数据结构:指的数据对象中的数据元素之间的关系。

2.数据结构分类

• 逻辑结构
  • 集合结构
    集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是"平等"的。
  • 线性结构
    线性结构中的数据元素之间是一对一的关系。
    常用的线性结构有：线性表、栈、队列、双队列、数组、串。
  • 树形结构
    树型结构中的数据元素之间存在一种一对多的层次关系。
    常见的树形结构：二叉树、B树、哈夫曼树、红黑树等。
  • 图形结构
    图形结构的数据元素是多对多的关系。
    常见的图形结构：邻近矩阵、邻接表。
• 物理结构
  
  物理结构：又称“存储结构”，指的是数据的逻辑结构在计算机的存储形式。
  
  数据存储结构应该正确反映数据元素之间的逻辑关系。如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。
  • 顺序存储结构
    把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
  • 链式存储结构
    把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

数据元素的存储关系并不能直接反映逻辑关系，因此需要用一个指针存放数据元素的地址，通过地址找到相关关联数据元素的位置。

算法

• 算法: 解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
• 算法特性
  • 输⼊输出: 输入提供已知条件，输出产生结果。
  • 有穷性: 执行有限的步骤之后，会自动结束。不会死循环。
  • 确定性: 相同输入执行后，只有对应唯一的结果，不能有二义性。
  • 可⾏性: 每一步都是可行的。每一步都能通过有限次数完成。
• 算法设计要求
  • 正确性: 能够得到正确答案。错误答案对于解决问题是没有意义的。
  • 可读性: 能够在有限的时间内让人看出算法逻辑。
  • 健壮性: 能对输入数据的不合法的情况做出合适的处理。
  • 时间效率高和存储量低: 花最少的时间，用最少的存储空间，得到相同的结果。
• 复杂度
  • 时间复杂度: 算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

执⾏次数函数	阶	术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n2+2n+1	O(n2)	平⽅阶
5log2n+ 20	O(log n)	对数阶
2n+3nlog2n+19	O(nlog n)	nlogn阶
6n3+2n2+3n+4	O(n3)	⽴⽅阶
2n	O(2n)	指数阶

复杂度排序

O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

• 空间复杂度: 通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记做：，其中，为问题的规模，为语句关于所占存储空间的函数。

除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。
考量空间复杂度是，主要考虑算法执行时所需要的辅助空间。