数据结构总结（一）

约定不等于承诺〃 2023-01-09 03:45 76阅读 0赞

**数据结构总结（一）**  
本篇数据结构与算法学习笔记，感觉也不是笔记，像是栽抄知识点。  
绪论：  
数据结构的意义：数据结构+算法=程序  
数据结构基本概念：  
1、 逻辑结构

1.  线性结构：结构中的数据元素之间存在一对一的线性关系。
2.  数结构：结构中的数据元素之间存在一对多的层次关系。
3.  图结构：结构中的数据元素之间存在多对多的任意关系。  
    2、 逻辑结构的延伸及基本算法  
    3、 物理结构  
    4、 运算集合（基本操作）  
    算法及其描述：  
    （算法是描述求解问题方法的操作步骤集合，它是有限序列，每条指令表示一个或多个操作）  
    算法具有的重要特性：  
    1、 有穷性：有限操作  
    2、 确定性：不能含有二义性  
    3、 可行性：每个操作能够顺利执行，并含有结果。  
    4、 输入：从外界取得必要的数据。（一个算法可以0个或多个输入）  
    5、 输出：（一个算法有1个或多个输出）  
    算法设计必须满足的要求：  
    1、 正确性：输入数据都能有满足的结果  
    2、 可读性：  
    3、 健壮性：非法的输入数据，算法能给出相应的反应。  
    4、 效率与低存储量需求：执行时间越少效率就越高，越少存储量越好。  
    算法分析：  
    （用算法语句的执行次数度量一个算法的效率。）  
    时间复杂度（O），。。。。。。（？？？感觉学了个寂寞，都是在PDF的知识点总结下来）  
    还是不明白  
    线性表：  
    线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。  
    定义：  
    由n个相同类型数据元素（结点）a1、a2…组成的有限序列。n：数据元素的个数，也称表分长度；空表：n=0，记为（）。  
    举例：英文26个字母构成的表是一个线性表。  
    线性表的特征：

1.  在非空的线性表，有且仅有一个开始结点a/1，它没有直接前趋，而仅有一个直接后继a/2；
2.  有且仅有一个终端结点a/n，它没有直接后继，而仅有一个直接前趋a/n-1；
3.  其余的内部结点a/i（2＜/＝i＜/＝n-1）都有仅有一个直接前趋a/i-1和一个直接后继a/i+1。
4.  数组元素的个数不能小于或等于1.
5.  线性表的第一个元素没有直接前驱最后一个元素没有直接后继。
6.  链表元素的地址可以是不连续的。
7.  数组元素的地址不可以是不连续的。  
    线性表的基本运算：
8.  求表长——求线性表中元素的个数。
9.  遍历——从左到右（或从右到左）扫描（或读取）表中的各元素。
10. 按编号查找——找出表中第i个元素。
11. 按特征查找——按某个特定值查找线性表。
12. 插入——在第i个位置上（即原第i个元素前）插入一新元素。
13. 删除——删除原表中的第i个元素。
14. 排序——按元素某特征值得递增（或递减）排序，重排表中各元素。  
    顺序表：（每个元素都前后有序、整整齐齐/紧密联系）  
    线性表两种存储方式：
15. 顺序表的形式（按顺序存放、地址连续）
16. 链表的形式  
    顺序表元素的插入：InsertList（L，X，3），L：原元素；X：要插入的字符；3：要插入的位置i。  
    调皮的链表：  
    链表不是地址连续的空间，他的插入和删除不需要移动元素，它看到内存有空余地址就可以毫无顾忌地挤进去，所以我们叫它”调皮的链表“  
    单链表结点的插入和删除：  
    线性表的链式表示和实现：  
    单链表的结构：  
    单链表中构成链表的结点只有一个指向直接后继结点的指针域。  
    其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。  
    顺序存储结构和链式存储结构有所不同。  
    静态链表  
    对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。用数组描述的链表，即称为静态链表。  
    关于静态链表：  
    • 我们对数组的第一个和最后一个元素做特殊处理，他们的data不存放数据。  
    • 我们通常把未使用的数组元素称为备用链表。  
    • 数组的第一个元素，即下标为0的哪个元素的cur（游标）就存放备用链表的第一个结点的下标。  
    • 数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用。