2025年数据结构知识点汇总

2.1.1 线性表的逻辑构造线性表的定义线性表是 n 个类型相似的数据元素的有限序列，对 n>0,除第一种元素无直接前驱，最终一种元素无直接后继外，其他的每个数据元素只有一种直接前驱和一种直接后继。线性表的特点：1）同一性：线性表有同类元素数据构成，每一种必须属于同一数据类型。2）有穷性：线性表由有限个数据元素构成，表长就是表中数据元素的个数。3）有序性：线性表中相邻数据元素之间存在着序偶关系。抽象数据类型定义：见书本。次序存储构造的定义线性表的次序存储构造是指用一组地址持续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反应数据元素之间逻辑上的相邻关系。采用次序存储构造的线性表一般称为次序表。将线性表归纳为：关系线性化，节点次序存。假定次序表中有个元素，每个元素占个单元，第一种元素的地址为，则可通过如下公式计算出第个元素的地址：其中，称为基地址。线性存储构造的 C 语言定义#define MAXSIZE 100typedefstruct{ElemType elem[MAXSIZE]; /*ElemType 可为 int，char 等*/int last; /*记录线性表中最终一种元素在数组 elem[ ]中的位置(下标值)*/}Seqlist;上述为定义一种构造体，构造名为 Seqlist。知识延伸（typedef）（C 书本用 typedef 申明新类型名）2.2.2 线性表次序存储构造上的基本运算线性表的基本运算1、查找操作2、插入操作3、删除操作4、次序表合并算法线性表次序存储构造的优缺陷分析2.3 线性表的链式存储链表定义：采用链式存储构造的线性表称为链表。链表的分类：1）按实现角度看：链表可分为动态链表和静态链表。2）按链接方式的角度看：链表可分为单链表、循环链表和双链表。2.3.1 单链表2.3.2 单链表上的基本操作线性表的基本运算1、初始化单链表 InitList(LinkList *L){*L=(LinkList)malloc(sizeof(Node)); /*建立头结点*/ (*L)->next=NULL;/*建立空的单链表 L*/}注意：L 是指向单链表的头结点的指针，用来接受主程序中带初始化单链表的头指针变量的地址，*L 相称于主程序中带初始化单链表的头指针变量。2、建立单链表1）头插法建表算法描述：从一种空表开始，反复读入数据，生成新结点，将读入数据寄存到新节点的数据域中，然后将新节点插入到目前链表的表头节点之后，直至读入结束标志为止。单链表的存储构造：typedefstruct Node /*结点类型定义，构造...