数据结构与算法-入门

引言:

记得在大一上学期开设的C语言课程中,老师主要讲的就是一些关于算法的知识,让那时候年幼的我对算法就有了一点恐惧。本身我数学就不好,关于数学这一块的东西也是蛮抗拒的,但是也没办法,这种东西总得去克服嘛,所以就硬着头皮往前冲! 尽力把数据结构和算法掌握扎实,为以后的路铺好基础吧~~

当然作为一名学生,这篇博客文章也只是一个学习的笔记,也是一个分享,并不会很深入的研究,希望可以帮助到大家吧。

一、逻辑结构和物理结构

传统上,我们把数据结构分为逻辑结构和物理结构

(一)逻辑结构:

逻辑结构是指数据对象中数据元素之间的互相关系

四大逻辑结构

  • 集合结构

集合结构中的数据元素除了属于同一类集合外,之间没有其他关系

  • 线性结构

线性结构中的元素只存在一对一的结构

  • 树形结构

树形结构中的元素之间存在一对多的关系

  • 图形结构

图形结构中的元素之间存在多对多的关系

(二)物理结构:

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

存储器主要指内存

数据的存储顺序

  • 顺序存储结构

把元素存放在地址相连的存储单元中,器数据间的逻辑关系和物理关系是一致的,比如 编程语言中的数组

  • 链式存储结构

面对时常发生变化的存储,适用于链式存储结构

比如去银行取号: 默认情况下是按照从1号、2号、3号……递增的叫号,但是如果你途中正好出去上厕所或者干些其他的事情而误号了,就得重新排队取号

这就相当于数据存储结构中的链式存储

链式存储结构:就是把数据元素存放在任意的存储单元里,这组存储元素可以是连续的,也可以是不连续的。

链式存储结构中的数据元素存储关系并不能反映其逻辑关系,故需要一个指针来存放数据元素的地址,这样就可以通过地址找到其关联的数据元素的位置。

二、初始算法

在很久以前, 有一位德国的科学家叫做高斯,有一天老师让学生算出1+2+3+…+100的和,小高斯没一会就算出了答案5050 老师表示很惊讶,高斯解释道1+100=101、2+99=101、……50+51=101, 101*50 = 5050 就这样著名的等差数列算法,被一名小学生给发明了


放在编程语言中,如果使用迭代的方式算1到100的和

1
2
3
4
5
6
int sum = 0
for(int i = 1 ; i< 100 ; i++)
{
sum += i;
}
Console.WriteLine(sum);

如果我们使用Mr.高斯的等差数列算法,我们也可以这样写:

1
2
3
4
int sum = 0;
int n = 100;
sum = (1+n)*n/2;
Console.WriteLine(sum);

运用传统的迭代方式相加得到和需要在for循环中循环100次,而使用等差数列算法的方式则只需要运行一次就能得到我们想要的结果。虽然现在计算机的处理速度是相当快的,但是运行一百次消耗的时间肯定要比运行一次消耗的时间长吧。所以这时候算法的优势就体现出来了。


算法就是解决特定问题的特定解决方式,我们可以通过无数种方式解决同一个问题,这无数种方式都被称为算法

(一)算法的特性

  • 输入
    • 算法具有零个或者多个输入
  • 输出
    • 算法至少有一个或者多个输出
    • 输出可以是返回一个值或多个值,可以是打印形式输出,看具体的情况而定
  • 有穷性
    • 算法在执行有限的步骤后,会结束而不会无限循环,并且每一个步骤都在可接受的时间内完成
  • 确定性
    • 算法的每一个步骤都具有明确的含义,不会出现二义性
    • 算法在一定条件下,只有一套执行路径,相同的输入只能有唯一的输出结果
    • 算法的每个步骤都应该被明确定义而无歧义
  • 可行性
    • 算法的每一步都必须是可行的,也就是说,每一步都能通过执行有限次数完成

(二)算法设计的要求

算法的设计没有最好只有更好!

  • 正确性
    • 算法的正确性是指算法至少应该具有输入、输出和加工处理的无歧义性、能正确地反映问题的需求、嫩够得到正确的答案
    • 大体分为以下四个层次
      1. 算法程序没有语法错误
      2. 算法程序对于合法输入能够产生满足要求的输出
      3. 输出程序对于非法输入能够产生满足规格的说明
      4. 算法程序对于故意刁难的测试输入都有满足要求的输出结果

To Be Continue…