数据结构 线性表
本文主要内容:线性表的逻辑结构和存储结构以及相应 算法 ;
由N(N>=0)个数据特性相同的元素构成的有限序列称为线性表。N为线性表长度,当N为0时就是空表。
非空线性表或是线性结构,其的 特点 是:
线性表的顺序表示和实现
线性表的顺序表:指的是用一组 地址连续 的存储单元依次存储线性表的数据元素。(这种表示又叫线性表的顺序存储结构或顺序映像)Sequential List
逻辑上相邻的元素,物理上也相邻 ;
公式:Loc(ai)=Loc(a0)+(i-1)x L
所以只要确定了一个元素的位置,表中任意元素都可以 随机存取 ,因此线性表是一种随机存取的存储结构。
存取的时间复杂度为O(1).
缺点: 插入和删除费时,需要移动大量的元素,长度固定。
线性表的链式存储结构的特点:
用一组任意的存储单元(可连续可不连续)存储线性表的数据元素,存储时需要额外的存储单元存储后继元素的信息。
每个存储的元素称为 节点 (Node),它由两部分组成:
由n个节点链结成一个链表,即为链式的线性表。
根据链表所含的指针个数,指针指向,指针连接方式,将链表分为:
其中单链表、循环链表、双向链表用于实现线性表的链式存储结构,其他链表多用于实现树和图等非线性结构。
4.1 单链表
单链表的存取必须从 头指针 开始进行,头指针指示链表的第一个节点,最后一个元素的指针为空NULL。
特点:
一般为了处理方便,会在单链表的第一个节点之前设置一个 头结点 ,该头结点的数据域可以不存储任何信息,也可以存储线性表的长度信息或其它附加信息,头结点的指针域存储指向第一个节点的指针。
示例:
指针头: H –>31,如果H指向null表示为空表;
要取得第i个数据元素必须从头指针出发顺链进行寻找,所以单链表是顺序存取的存取结构。
查找算法 :
插入算法 :
将值为e的节点插入到第一个节点的位置上即ai-1和ai之间 - 找到ai-1节点,并有指针p指向该节点;
删除算法 : 时间复杂度为O(n),主要时间在查找ai-1
单链表的创建:
链表从一个空表开始,动态的不断插入数据,形成链表;
4.2 循环链表
另一种链式存储,特点是表中的最后一个节点的指针,指向头节点,整个链表的形式形成一个环。从表中任意节点出发都可以找到其他节点。
合并两个循环链表时,只需要表1的尾->表2的第一个节点(释放表2的头节点),表2的尾指针->表1的头节点。
4.3 双向链表
修改节点的结构,之前的节点只有后继指针,现在给节点添加上前驱指针
双向链表的节点结构:
双向链表也有循环链表叫双向循环链表
两个线性表La和Lb: La长度为m,Lb 的长度为n;
假设GetElem和ListInsert与表长无关,LocateElem执行的时间与表长成正比,则时间复杂度为O(m*n)
调用
结果
时间复杂度O(m n);
需要开辟新的辅助空间,所以空间复杂度也为O(m n);
2024-06-11 广告