数据结构笔记

基本概念和术语

数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构包括逻辑结构和存储结构两个层次。

逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

链式存储结构：顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

数据类型和抽象数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，从而实现了信息隐藏。

抽象数据类型相当于在概念层上描述问题，而类相当于在实现层上描述问题。

算法和算法分析

算法(Algorithm)是为了解决某些问题而规定的一个有限长的操作序列。

一个算法必须满足以下五个重要特性：1.有穷性。2.确定性。3.可行性。4.输入。5.输出。

一个算法的优劣应该从以下几方面来评价：1.正确性。2.可读性。3.健壮性。4.高校性。

算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。算法执行时间的数量级称为算法的渐进时间复杂度，T(n)=O(f(n)),它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。

线性表

线性表的定义和特点

由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表。

线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表。

对于非空的线性表或线性结构，其特点是：

1.存在唯一的一个被称作“第一个”的数据元素。
2.存在唯一的一个被称作“最后一个”的数据元素。
3.除第一个之外，结构中的每个数据元素均只有一个前驱。
4.除最后一个之外，结构中的每个数据元素均只有一个后继。

线性表的类型定义

ADT List{
  数据对象：D={ai|ai∈ElemSet,i=1,2...,n.n>=0}
  数据关系: R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
  基本操作:
    InitList(&L)
      操作结果:构造一个空的线性表L。
    DestroyList(&L)
      初始条件：线性表L已存在。
      操作结果：销毁线性表L。
    ClearList(&L)
    ListEmpty(L)
    ListLength(L)
    GetElem(L,i,&e)
    LocateElem(L,e)
    PriorElem(L,cur_e,&pre_e)
    NestElem(L,cur_e,&next_e)
    ListInsert(&L,i,e)
    ListDelete(&L,i)
    TraverseList(L)
  }ADT List

线性表的顺序表示和实现

线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常称这种顺序存储结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。