数据结构与算法:教程简介与基本概述

数据结构是一种存储数据的方式,以便数据能够被高效利用,重点在于高效二字。几乎每一个企业应用都会或多或少地使用到多种数据结构。本教程旨在帮助你掌握构建复杂企业级应用所需的数据结构与算法。

适用对象

本教程是为计算机专业的学生以及有意愿学习数据结构的相关人士准备的,完成本教程后,你将具有中级水平的专业知识,为以后达到更高水平打下基础,这也决定了这份教程不会过度关注基本概念(认定你已经有了一定掌握),将更加强调相关思想的理解

先决条件

学习本教程之前,你需要对C语言或者C++编程,以及IDE的使用有基本的掌握。

概述

数据结构是一种组织数据的系统的方式,使得数据能够被高效地使用。接口与实现是数据结构的两个基本概念。

  • 接口。每种数据结构都有一个接口,接口表示数据结构支持的操作集合。一个接口只提供支持的操作列表、可接受的参数类型、以及这些操作的返回值类型。
  • 实现。实现提供了数据结构的内部表示以及所使用的算法的定义。

数据结构的特征

  • 正确性—数据结构应正确实现其接口。
  • 时间复杂度—操作执行的时间应当尽可能小
  • 空间复杂度—操作所需内存应当尽可能小

需求

随着程序复杂程度的提升以及数据量的增大,应用程序常会面临三个问题。

  • 数据搜索—假如有一百万个数据,应用程序就必须在一百万个数据中进行搜索,难度可想而知,随着数据的增长,搜索会越来越慢。
  • 处理器速度—尽管处理器的速度已经相当快了,但面对十亿级的数据增长量依然显得十分有限。
  • 多个请求—如果成千上万的用户同时在一个web服务器上搜索数据,那么即使很快的服务器也会崩溃。

数据结构就是用来解决这些问题的,按照数据结构方式组织的数据,在进行搜索时可能无需对所有数据进行搜索,需要的数据能够在短时间内呈现在用户面前。

执行时的不同情况

评判数据结构的执行时间通常有三种情况。

  • 最坏情况—在此情况下执行相关操作所需时间ƒ(n)达到最大。
  • 平均情况—描述操作执行的平均时间,如果一个操作花费ƒ(n)时间,那么m个操作花费mƒ(n)时间。
  • 最好情况—这种情况下执行所需时间达到最小。

基本术语

  • 数据—输入到计算机中并能被程序处理的符号集合
  • 数据项—表示基本数据单元
  • 属性和实体—实体拥有若干可能被赋值的属性或特性
  • 实体集—拥有相似属性的实体集合
  • 字段—代表一个实体属性的信息基本单位
  • 记录—一个给定实体的字段值的集合
  • 文件—一个给定实体集中实体记录的集合

转载请参看关于博客页面相关要求。