数据结构知识点汇总VIP专享

精品文档---下载后可任意编辑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）头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头节点之后，直至读入结束标志为止。单链...