数据结构与算法

点击打开在线编译器,边学边练

请牢记:程序=数据结构+算法

1. 数据结构发展史

1) 起源:

1968年美国唐•欧•克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构语其操作的著作。我们一般认为本书开创了数据结构的系统概念。

70年代初,数据结构作为一门独立的课程开始进入大学课堂。

数据结构的发展经历三个阶段:无结构阶段,结构化阶段和面向对象阶段(和程序发展的三个阶段不谋而合了)

2) 无结构阶段

40~60年代见,计算机的主要应用还没有如此普及,当时计算机主要是正对科学计算,程序设计技术以机器语言和汇编语言为主,程序处理的是存粹的数值,数据之间的关系主要是以来数学公式或者数学模型,此时数据结构概念并没有明确形成。

3)结构化阶段

60~80年代,计算机开始广泛应用于非数值处理领域,数据表示成为程序设计的重要问题,人们认识到程序设计规范化的重要性,提出了程序结构模块化,并开始注意数据表示与操作的结构化。数据结构及抽象数据类型就是在这种情况下形成的,随着数据规模的加大,程序的设计越来越依附于数据结构的设计,此时数据结构开始广泛普及。

此间也有非常多的数据结构相关的文献产出,最为著名的是图灵奖获得者沃斯的一个著名公式:程序=数据结构+算法。

4)面向对象阶段

80年代初期到现在,随着计算机不断普及,计算机性能以及需求不断增加,面向对象的程序设计被逐步提出,在对象的世界中 ,程序设计中大大减少了重复设计的部分,数据结构在这个阶段逐渐变得丰富,大量的封装类出现,减少了程序设计者的负担,数据结构因此变得更加友好。


2.何为算法

请你回答一下如何使用计算机C语言编程计算1到100的和(1+2+3+……+100),相信大多数人会直接给出以下答案:

#include <stdio.h>
int main() {
    int ans=0,i;
    for(i=1;i<=100;i++){
        ans+=i;
    }
    printf("%d",ans);
    return 0;
}

这几乎是计算机中最为简单的程序了,但是,这样去完成这个功能真的好么?早在300年前的小学生高斯在课堂上被老师要求去计算这个结果,在同班同学还在手推写结果的时候,高斯早就已经做完了,他利用等差数列求和的算法,轻易打败了同班同学。

相关代码如下:

#include <stdio.h>
int main() {
    int ans=(1+100)*100/2;
    printf("%d",ans);
    return 0;
}

相比第一份答案,我们进行了100次的运算,才得出我们想要的结果,而对于第二份答案,我们仅进行了1次运算就得到了想要的结果,而在实际中计算机的计算远远不止这点计算量,以此如果我们去计算1到1000000的和呢?使用了等差数列还是一步算好,而这就是算法的魅力。



本文固定URL:https://www.dotcpp.com/course/88

上一课:数学基础 下一课:算法基础
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)