儿童教育 php模板 网站,网站建设技术方面论文,网页定制多少钱,阳泉集团网站建设文章目录 线性表的定义和基本操作顺序表线性表的链式表示 线性表的定义和基本操作
线性表是具有相同数据类型的(n≥0)个数据元素的有限序列#xff0c;其中n为表长#xff0c;当n0时线性表是一个空表。若用L命名线性表#xff0c;则其中一般表示为#xff1a;L(a1,a2,a3, … 文章目录 线性表的定义和基本操作顺序表线性表的链式表示 线性表的定义和基本操作
线性表是具有相同数据类型的(n≥0)个数据元素的有限序列其中n为表长当n0时线性表是一个空表。若用L命名线性表则其中一般表示为L(a1,a2,a3,··· ,an)。除第一个元素外每个元素有且仅有一个直接前驱。除最后一个元素外每个元素有且仅有一个直接后继。 注意 线性表是一种逻辑结构表示元素之间一对一的相邻关系。顺序表和链表是指存储结构
顺序表
顺序表的定义 线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同
特点 顺序表最主要的特点是随机访问即通过首地址和元素序号可在时间O(1)内找到指定的元素顺序表的 存储密度高 每个结点只存储数据元素顺序表逻辑上相邻的元素物理上也相邻所以插入和删除操作需要移动大量元素 顺序表的基本操作
插入操作 最好情况在表尾插入元素后移语句将不执行时间复杂度为O(1)最坏情况在表头插入元素后移语句将执行n次时间复杂度为O(n)平均情况在长度为n的线性表中插入一个结点时所需要移动结点的平均次数为n/2时间复杂度为O(n) 删除操作 最好情况删除表尾元素无须移动元素时间复杂度为O(1)最坏情况删除表头元素需移动除表头元素外的所有元素时间复杂度为O(n)平均情况在长度为n的线性表中删除一个结点时所需要移动结点的平均次数为(n-1)/2线性表删除算法的平均时间复杂度为O(n) 按值查找 最好情况查找的元素就在表头仅需比较一次时间复杂度为O(1)最坏情况查找的元素在表尾或不存在时需要比较n次时间复杂度为O(n)平均情况在长度为n的线性表中查找e元素的平均比较次数为(n1)/2时间复杂度为O(n) 线性表的链式表示 顺序表可以随时存取表中的任意一个元素但插入和删除操作需要移动大量元素。链式存储线性表时不需要使用地址连续的存储单元即不要求逻辑上相邻的元素在物理位置上也相邻他通过“链”建立起数据元素之间的逻辑关系因此插入和删除操作不需要移动元素而只修改指针但也会失去顺序表可随机存储取的有优点 单链表的定义 线性表的链式存储又称为单链表它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系对每个链表结点除存放元素自身的信息外还需要存放一个指向后继的指针
其中data为数据域存放数据元素。为指针域存放其后后继结点的地址利用单链表可以解决顺序表需要大量连续存储单元的缺点但单链表附加指针域也存在浪费存储空间的缺点由于单链表的元素离散地分布在存储空间中所以 单链表是非随机存取的存储结构 不能直接找到表中某个特点的节点。查找某个特定的结点时需要从表头开始遍历依次查找通常用头指针来标识一个单链表单链表L头指针为NULL时表示一个空表。为了操作上的方便在单链表第一个结点之前附加一个结点称为头结点。头结点的数据域可以不设任何信息也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点
判断单链表是否为空的判断条件
带头结点L—nextNULL不带头结点LNULL
