数据结构|Chapter1:绪论

摘要:今天《数据结构》开课,本文是第一章绪论的笔记。

什么是数据结构

  • 计算机中存储和组织数据的方式,意味着接口或封装:一个数据结构可被视为两个函数之间的接口,或者是由数据类型联合组成的存储内容的访问方法封装。
  • 相互之间存在一种或多种特定关系的数据元素的集合,数据元素间的关系为结构。
  • 程序设计 = 数据结构 + 算法

基本概念和术语

  • 数据data:所有能输入到计算机中并被计算机程序加工、处理的符号的总称;如整数、实数、字符串、图像、声音等。
  • 数据元素data element:数据的基本单位(元素、记录、结点、顶点),在计算机程序中通常作为一个整体进行考虑和处理。
  • 数据项data item:一个数据元素可由若干个数据项组成,数据项是数据的不可分割的最小单位。如:姓名、年龄等;一个数据元素可由一个或多个数据项组成。如: (姓名、年龄)
    数据对象data object:由性质/类型相同的数据元素组成的集合;是数据的一个子集。
  • 数据结构data structure:相互之间存在一种或多种特定关系的数据元素的集合。数据元素间的关系为结构。四类基本结构:集合(元素同属于一个集合的关系),线性结构(一个对一个的关系),树状结构(一个对多个的关系)和图状结构(多个对多个的关系)。
  • 数据的逻辑结构:各元素间的逻辑关系
  • 物理结构:指数据的逻辑结构在计算机中的存储形式;逻辑结构面向问题,物理结构面向计算机,其基本目标是将数据及其逻辑关系存储到计算机的内存中。逻辑和物理结构
  • 数据的存储结构:数据结构在计算机存储器中的映象(mapping);存储结构也称为:存储表示,物理结构,物理表示。
    结点/元素:计算机中由若干位bit组成的一个位串表示一个元素,这个位串即元素或结点(node)。

    1.顺序存储结构:用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
    .非顺序/链式存储结构:用指示元素存储地址的指针表示数据元素间的逻辑关系;把数据元素存放在任意的存储单元里,这组存储单元可以是连续的也可以是不连续的。数据元素的存储关系不反映其逻辑关系,用指针存放数据元素的地址,我们通过地址可以找到相关联数据元素的位置。如:链式

  • 数据类型data type:是一个值的集合和定义在这个值上的一组操作的总称。
    抽象数据类型(Abstract Data Type):与计算机的实现无关的数据类型,指一个数学模型以及定义在该模型上的一组操作,其定义只取决于它的一组逻辑特性,与其在计算机内部如何表示和实现无关。一个抽象数据类型定义了一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。

抽象数据类型(Abstract Data Type, ADT)可用三元组表示(D,S,T):
ADT抽象数据类型名{
数据对象:(数据对象的定义)
数据关系:(数据关系的定义)
基本操作:(基本操作的定义)

基本操作的定义格式:
基本操作名(参数表)
初始条件:(初始条件描述)
操作结果:(操作结果描述)

  • 数据结构的层次:layer

C语言核心子集

  • 预定义变量和类型:#define
  • typedef表示数据结构,元素类型为ElemType
  • 基本操作语句
  • 赋值
  • 选择:if …else; switch…case…default
  • 循环:for;while;do…while
  • 结束:return (函数结束语句);break(case结束);exit(异常结束)
  • 输入输出:scanf([格式串],变量1,…,变量n);printf
  • 注释://
  • 基本函数:max;min;abs;floor;ceil;eof;eoln
  • 逻辑运算约定:&&;||

算法Algorithm和算法分析

定义:对特定问题求解步骤地描述。

算法的描述工具:自然语言;程序设计语言(C);流程图;伪码语言;类C;

算法的时间复杂度:算法中基本操作重复执行的次数的总和

  • 语句频度:所有语句的执行次数f(n)
  • 时间复杂度:T(n)=O(f(n))
  • 根据时间复杂度衡量算法效率的前提是:针对同一问题

冒泡排序的C语言算法

  • 算法的存储空间需求:空间复杂度S(n) = O(f(n));
  • 算法改进
Thanks!