2. 线性表

老师强调的考点：

单链表的插入（基本语句）删除，头插尾插（有什么不同，各自的特点）。各个复杂度等。

双链表的插入删除（删除给定结点的前驱后继等等）

2.1 逻辑结构

L = (D,R)

D = {ai | 1<= i <= n , n>0 , ai为ElemType类型}

R = {r}

r = {<ai,ai+1> | 1 <= i <= n-1}

1. 图的基本概念

1.1 图的定义

G=(V,E)

V：顶点（数据元素）的有穷非空集合

E：边的有穷集合

1.2 图的基本术语

1. 无向图中：端点和邻接点

​ 有向图中：起始端点和终止端点；出边邻接点和入边邻接点

2. 顶点的度，出度和入度

1. 树的基本概念

1.1 基本术语

度：某个结点的子树的个数。树中所有结点的度的最大值称为树的度。

分支结点和叶子结点

路径和路径长度

孩子结点，双亲结点和兄弟结点

结点层次和树的高度

有序树和无序树

森林

1.2 树的性质

1. 树中的结点数等于所有结点的度数和加一。

假设度数为0,1,2,3…的结点有n0,n1,n2,n3…个

则：n0+n1+n2+n3….=0 * n0 + 1 * n1 + 2 * n2 + 3 * n3….

1. 栈

定义：先进先出

1.1 顺序栈

共享栈：

1.2 链栈

链栈的优点在于不存在栈满上溢出的情况。因为给定链栈后，已知头结点的地址，在其后面插入一个新节点和删除首节点都十分的方便，对应的算法实际复杂度都为O（1）。

1.3 表达式

1. 线性表及其逻辑结构

1.1 线性表的定义

1.1.1 基本定义

线性表是一个具有相同特性的数据元素的有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n>=0。

线性表的一般表示为：

​

一些关于线性表的定义：

线性表用二元组来表示：L = （D ，R），其中：

逻辑结构的示意图是：

1. 什么是数据结构？

1.1 数据结构的定义

基本定义：

• 数据（Data）：描述客观事物的数和字符的集合。

  • 信息的载体
  • 对客观事物符号化的表示
  • 能够被计算机识别存储和加工

• 数据元素（Data element）：作为数据的基本单位。也可以称为元素，记录，结点或定点。

  • 一个数据元素可由若干个数据项组成。
  • 如：0003 李明 男 2001/03/02是李明的基本信息，也是由若干个数据项组成的数据元素。

• 数据项（Data item)具有独立含义的数据最小单位，也称为字段和域。

  • 数据 > 数据结构 > 数据项，就像 学生表 > 个人记录 > 学号姓名…

• 数据对象（Data Object）性质相同的数据元素的集合，是数据的一个子集。\

  • 字母字符数据对象是集合C={'A','B','C'...}

• 数据结构: 数据元素不是孤立存在的，他们存在着某种关系，数据元素相互之间的关系称为结构。是指相互之间存在一种或多种特定关系的数据元素集合。或者说，数据结构是带结构的数据元素的集合。