基本概念

计算机处理的对象（数据）已经不再单纯是数值，而是研究计算机数据之间的关系，包括数据的逻辑结构和存储结构及数据的运算
研究数据结构的意义：提高编程能力、可复用，维护性好，效率高

数据（Data）

  • 数据即信息的载体，是能够输入到计算机中，且能被计算机识别、存储和处理的符号总称

数据元素（Data Element）

  • 数据元素是数据的基本单位，又称为记录（Record）

数据结构的三要素

image-20240731073132629

数据的逻辑结构

表示数据运算之间的抽象关系，按每个元素可能具有直接的前趋数和直接的后继数将逻辑结构分为 ”线性结构“ 和 ”非线性结构“ 两大类
集合：数据元素间除 ”同属一个集合外“ ，无其他关系。
线性结构：一个对一个，如线性表、栈、队列
树形结构：一对多，如树。
圆形结构：多个对多个，如图

数据的存储结构

存储结构：逻辑结构在计算机中的具体实现方法
存储结构是通过计算机语言所编制的程序来实现，依赖于计算机语言的

  • 顺序存储：将数据结构中各个元素按照其逻辑顺序存放于存储器一片连续的存储空间中，如C语言中的数组。
  • 链式存储：将数据结构中各个元素分布到存储器的不同点，用地址（或链指针）方式建立他们之间的联系，在计算机内部很大程度是通过地址或指针来建立的
  • 索引存储：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。
  • 散列存储：根据数据元素的特殊字段（称为关键字key），计算数据元素的存放地址，然后数据元素按地址存放。

数据的运算

检索、排序、插入、删除，修改。


线性结构—线性表

线性表的概念

线性表L可用二元组形式表示：L = (D, R)，其中D={ai | ai∈datatype, i=0,1,2, ……, n-1, n≥0}，R={<ai , ai+1> | ai+1∈D, 0≤i≤n-2}

表示任意相邻两个元素之间的先后次序关系，ai 是 ai+1 的直接前驱， ai+1 是 ai 的直接后驱，关系服符称为<ai , ai+1>有序对

  • 设线性表 L=(a0, a1, ……, an-1 )，对L的运算有：

  • 建立空表：list_create(L)

  • 置空表：list_clear(L)

  • 判断表是否为空：list_empty(L)

  • 求表长：length(L)

  • 取表中的某个元素：GetList(L, i)，即ai。其中 0 ≤i ≤ length(L)-1

  • 定位运算：Locate(L, x)。确定元素x在表中的位置

  • 插入运算：Insert(L, x, i)。

线性表—顺序存储

在C语言中，线性表的顺序结构可用一维数组类型来描述

1
2
3
4
5
typedef struct
{
    int data[100];
    int last;
} list;		// 如该结构体中，定义了一个一维数组成员data，其可存储大小为100的线性表，last成员用于记录元素下标
  • 优点：存储密度高及能够随机存取
  • 缺点：要求系统提供一片较大的连续存储空间，插入、删除等操作时，存在元素在存储器中成片移动的现象

线性表—单链表

存储结构：各个元素分布在存储器的不同存储块，称为结点，通过地址或者指针建立元素之间的联系

1
2
3
4
5
typedef struct node
{
    int data;				// data成员是有效数据类型，其存储数据
    struct node *Next;		// Next成员是结构体类型指针，其用于存储下一个元素的地址
} nodelist, *linklist;

优点：单链表是通过地址或指针来建立元素之间的关系的，其空间大小不固定，可动态分配内存，插入删除操作效率高。
缺点：单链表是以结点的方式存储，且其存储结构不是连续的，各个元素分布在存储器的不同存储块，不支持随机访问，查找数据时效率不高。

output

线性结构—栈（特点：后进先出）

栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），栈允许操作的一端称为“栈顶”，另一端称为“栈底”，当栈中无元素时，称为“空栈”

顺序存储的栈C结构体定义如下：

1
2
3
4
5
6
typedef struct
{
    int *data;		// data成员是栈的数据存储区
    int maxlen;		// maxlen是声明该栈的最大长度
    int top;		// top记录栈顶下标
} sqstack;

链式存储的栈C结构体定义如下：

1
2
3
4
5
typedef struct stack_t
{
    int data;
    struct stack_t * Next;
} linkstack;

线性结构—队列（特点：先进先出）

队列是限制在两端进行插入和删除操作的线性表，允许进行存入操作的一端称为队尾，允许进行删除操作的一端称为队头，当线性表中没有元素时，称为空队。

顺序存储的队列C结构体定义如下：

1
2
3
4
5
6
typedef struct
{
    int data[100];		// data成员存储队列数据
    int front;			// front表示队列的队头
    int rear;			// rear表示队列的队尾
} queue;

链式存储的队列C结构体定义如下：

1
2
3
4
5
6
7
8
9
10
11
typedef struct queue_t
{
    int data;
    struct queue_t * Next;
} queue, *linkqueue;

typedef struct
{
    linkqueue front;	// front成员用于指向队列链表的头节点
    linkqueue rear;		// rear成员用于指向队列链表的尾节点
} ht_queue;

非线性结构—树

树的概念

树是 n（n ≥ 0）个节点的有限集合 T ，它满足两个条件：

  • 有且只有一个特定的称为根（root）的节点；
  • 其余的节点可以分为 m（m ≥ 0）个互不相交的有限集合T1、T2、……、 Tm，其中每一个集合又是一棵树，并称为其根的子树。

表示方法：树形表示、目录表示

image-20240803010538454

从 k1 到 kj 的路径：存在k1, k2, ……, ki, ki+1, ……, kj，并满足 ki 是 ki+1 的父节点，路径长度为 j-1，即路径中的边数，如上图：1-2-5-10为一条路径，其长度为3，即边数为3。

节点的度数：一个节点的子树的个数，如上图：A的度数为3，B的度数为2
一棵树的度数：是指该树中节点的最大度数，如上图：所有节点中最大的度数为3，所以该树的度数为3
树叶或终端节点：度数为0的节点，如上图：J、K、F、G、L、I都是树叶
分支节点：度数不为0的节点
内部节点：除根节点外的分支节点
节点的层数：父节点的层数加1，根节点的层数定义为1，如上图：A的层数为1，J的层数为4。
树的高度或深度：树中的节点层数的最大值，如上图：该树所有节点的最大层数，即为4。
有序树：每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的。
森林：m（m ≥ 0）棵互不相交的树的集合称为森林，树去掉根节点就称为森林，森林加上一个根节点就称为树
树的逻辑结构：树中的任何节点都可以有0个或多个直接后继节点（子节点），但至多只有一个直接前趋节点（父节点），根节点没有前趋节点，叶节点没有后继节点


二叉树

二叉树是 n（n ≥ 0）个节点的有限集合，或者是n=0时的空集，或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树严格区分左右节点，即使只有一个字节点

image-20240803095201171

二叉树的性质

  • 其第 i 层上的节点最多为 2i-1 个。
  • 深度为 k 的二叉树最多有 2k-1 个节点。
  • 满二叉树：深度为 k 时有 2k-1 个节点的二叉树
  • 完全二叉树：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。
  • 具有n个节点的完全二叉树的深度为 (log2n) + 1 或 log2(n+1)。

顺序存储结构

完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点，下标为0处位置不使用。
不完全二叉树使用顺序存储时，可通过添加虚拟节点构成完全二叉树进行存储，但会浪费一定的存储空间。

设完全二叉树的节点数为n，

  • 某节点编号为 i (i>1)（不是根节点）时，有父节点，其编号为 i/2；
  • 当 2i ≤ n 时，有左孩子，其编号为 2i ，否则没有左孩子，本身是叶节点；
  • 当 2i＋1 ≤ n时，有右孩子，其编号为 2i+1 ，否则没有右孩子；
  • 当i为奇数且不为1时，有左兄弟，其编号为i-1，否则没有左兄弟；
  • 当i为偶数且小于n时，有右兄弟，其编号为i+1，否则没有右兄弟；
    链式存储的二叉树的C结构体定义
1
2
3
4
5
6
typedef struct node_t
{
    int data;
    struct node_t *lchild, *rchild;	
} bitree_t;
bitree_t * root;

二叉树遍历

先序遍历：先访问根节点，再访问左节点，接着访问右节点。
中序遍历：先访问左节点，再访问根节点，接着访问右节点。
后序遍历：先访问左节点，再访问右节点，接着访问根节点。
层次遍历：使用队列，访问到的节点先入队，出队时访问其子节点。

image-20240803095806679

根据遍历结果还原二叉树
已知先序遍历和中序遍历，可以还原二叉树；
已知中序遍历和后序遍历，可以还原二叉树；
已知先序遍历和后序遍历，不可以还原二叉树。

思路： 已知先序遍历和中序遍历还原二叉树
1）、根据先序遍历结果确定根节点。 先序遍历的第一个节点为根节点。
2）、在中序遍历结果中找到根节点，根节点左侧的部分为左子树节点，根节点右侧的部分为右子树节点。
3）、将中序遍历的结果按根节点分为两部分，迭代的执行第一步和第二步，直到还原整个二叉树。