沈阳模板建站定制,电子商务有什么岗位,全国二级建造师查询官网,网站关键词排名100文章目录 数据结构—线性表1.线性表的定义和基本操作线性表的定义线性表的特点线性表的基本操作 2.线性表的顺序存储和链式存储表示顺序存储链式存储单链表循环链表双向链表 数据结构—线性表
1.线性表的定义和基本操作
线性表的定义
定义#xff1a;线性表是具有相同数据类… 文章目录 数据结构—线性表1.线性表的定义和基本操作线性表的定义线性表的特点线性表的基本操作 2.线性表的顺序存储和链式存储表示顺序存储链式存储单链表循环链表双向链表 数据结构—线性表
1.线性表的定义和基本操作
线性表的定义
定义线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。n0时称为空表
线性表的特点
表中元素的个数有限。表中元素具有逻辑上的顺序性表中元素有其先后次序。表中元素都是数据元素每个元素都是单个元素。表中元素的数据类型都相同这意味着每个元素占用相同大小的存储空间。表中元素具有抽象性即讨论元素间的逻辑关系而不考虑元素元素的内容。
注意线性表是一种逻辑结构表示元素之间一对一的相邻关系。顺序表和链表是指存储结构两者属于不同层面的概念因此不要将其混淆。
线性表的基本操作
InitList(L) 初始化表。操作结果构造一个空的线性表L。GetElem(Lie) 线性表的取值。初始条件线性表L已存在且1≤i≤ListLength(L)。操作结果用e返回L中第i个数据元素的值。LocateElem(Le) 线性表的查找。初始条件线性表L已存在。操作结果返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在则返回值为0。ListInsert(Lie) 线性表的插入。初始条件线性表L已存在且1≤i≤ListLength(L)1。操作结果在L的第i个位置之前插入新的数据元素eL的长度加1。ListDelete(Li) 线性表的删除。初始条件线性表L已存在且非空且1≤i≤ListLength(L)。操作结果删除L的第i个数据元素L的长度加1。
注意符号“”表示C语言中的引用调用。
2.线性表的顺序存储和链式存储表示
顺序存储
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素这种表示也称为线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表(Sequential List)。特点逻辑上相邻的数据元素其物理次序也是相邻的。顺序存储结构是一种随机存取的存储结构。假设线性表L存储的起始位置为LOC(A)sizeof(ElemType)是每个数据元素所占用存储空间的大小。
数组下标内存状态内存地址位序0a1LOC(A)11a2LOC(A)sizeof(ElemType)2i-1aiLOC(A)(i-1)sizeof(ElemType)in-1anLOC(A)(n-1)sizeof(ElemType)n
注意要区分清楚位序和下标线性表中元素的位序是从1开始的而数组中元素的下标是从0开始的。
链式存储
单链表
线性表的链式存储又称单链表它是指通过一组任意的的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系对每个链表结点除存放元素自身的信息外还需要存放一个指向其后继结点的指针 其中存储数据元素信息的域称为数据域(data)存放直接后继存储位置的域称为指针域(next)。首元结点是指链表中存储第一个元素a1的结点。头结点是在首元结点之前附设一个结点其指针域指向首元结点。头结点的数据域可以不存储任何信息也可以存储与数据元素类型相同的其他附加信息。链表增加头结点的作用 便于首元结点的处理增加了头结点后首元结点的地址保存在头结点的指针域中则对链表的第一个数据元素的操作与其他数据元素相同无需进行特殊处理。便于空表与非空表的统一处理当不设头结点时假设L为单链表的头指针它应该指向首元结点则当链表长度为0时L指针为空(判定空表的条件记为LNULL);增加头结点后无论链表是否为空头指针都是指向头结点的非空指针。若为空表则头结点的指针域为空(判定空表的条件可记为L-nextNULL)。 特点逻辑上相邻的数据元素其物理次序不一定相邻单链表为顺序存取结构。
循环链表 循环链表(Circular Linked List)是一种头尾相接的链表即表中最后一个结点的指针域指向头结点整个链表形成一个环。 优点从表中任意一结点出发均可找到表中其他结点。 注意由于循环链表中没有NULL指针故涉及遍历操作时其终止条件就不再像非循环链表那样判断P或P-next是否为空而是判断它们是否等于头指针。
双向链表 双向链表(Double Linked List)在单链表的每个节点里增加一个指向其直接前驱的指针域prior这样链表中就形成了有两个方向不同的链故称为双向链表。 在单链表中查找直接后继结点的执行时间为O(1)而查找直接前驱的执行时间为O(n)。为了克服单链表这种单向性的缺点可利用双向链表。
