【数据结构与算法】概述

什么是数据结构

简单点就是 程序设计 = 数据结构 + 算法

逻辑结构 & 物理结构

传统上把数据结构分为逻辑结构&物理结构

逻辑结构：是指数据对象中数据元素之间的相互关系，是需要着重关注和讨论的问题。

四大逻辑结构：

• 集合结构：数据元素之间相互没有关系。
• 线性结构：数据元素之间是一对一的关系。
• 树性结构：数据元素之间有一对多的层级关系。
• 图形结构：数据元素是多对多的关系。

物理结构：指数据的 逻辑结构在计算机中的存储形式。

根据物理结构的定义，我们实际上研究的就是如何把数据元素 存储到 计算器的存储器中。

数据元素的存储形式有两种：

• 顺序存储：
  • 把数据元素存放在地址连续的存储单元里，其数据之间的逻辑关系和物理关系是一致的。就如：一些编程语言的数组就是这样。
• 链式存储：
  • 把数据元素存放在任意的 存储单元里，这组储存单元可以是连续的，也可以是不连续。就如单链表，只要知道下一个数据元素 指向的地址就行`。

什么是算法

引入

计算 1+2+3+4+ … +99+100 的值

常规算法（使用循环一个一个加）：

int i, sum = 0, n = 100;
for(i = 1; i<100; i++){
    sum = sum + i;
}
printf("sum = %d", sum);

使用高斯算法：

int i, sum = 0, n = 100;
sum = (1 + n)*n/2;
printf("sum = %d",sum);

这样是不是效率高很多。

算法的特征

算法有五大特征

解决问题并不只有一种算法

• 输入
  • 算法具有零个或者多个输入。
  • 尽管大多数时候算法来说，输入参数是必要的，但是就像打印bigdataboy.cn，就不需要参数。

void print(){
    printf("bigdataboy.cn");
}

• 输出：
  • 算法需要至少一个或者多个输出。
• 有穷性
  • 是指在执行有限的 步骤后，自动结束，并且每一步都是在可接受的 时间范围内完成。
• 确定性：
  • 算法的每一步都具有确定的含义，不会出现二义性。
  • 相同的输入只能有唯一的输出结果。
• 可行性：
  • 算法的每一步都必须是可行的，就是说，每一步都能通过执行有限的 次数完成。

算法设计的要求

• 正确性：
  • 是指算法至少应该具有输入、输出和加工处理无歧义，能得到正确的结果。
  • 大致分为以下四个层次
    • 算法程序没有语法错误
    • 算法程序对于合法的输入能得到满足要求的输出
    • 算法程序对于非法输入能产生相应的说明
    • 算法程序对于故意刁难的 测试输入都有满足要求的输出结果
• 可读性
  • 算法需要便于阅读、理解和交流，方便日后他人和自己的阅读和修改。
• 健壮性
  • 当输入不合法时，算法也能做出相关的处理，而不是产生异常、崩溃或莫名其妙的结果
• 时间效率高和存储量低
  • 在生活中大家都想找一个漂亮乖巧懂事，懂分寸的女朋友。
  • 好的算法就像好的女朋友，应该同时具备时间效率高和存储量低的特点，设计算法时，因尽量考虑这两方面的问题!!!