漳州网站建设哪家最权威,淘宝做导航网站有哪些功能吗,中国网站建设新闻,什么是seo推广数据结构入门级
第二章 线性表 一、线性表的定义和基本操作 线性表的定义#xff1a;具有相同属性数据类型的数据元素组成的一个有限序列#xff1b;除第一个元素外的元素都有直接前驱#xff0c;除最后一个元素外的元素都有直接后继#xff1b;存在一个唯一被称为“第一个…数据结构入门级
第二章 线性表 一、线性表的定义和基本操作 线性表的定义具有相同属性数据类型的数据元素组成的一个有限序列除第一个元素外的元素都有直接前驱除最后一个元素外的元素都有直接后继存在一个唯一被称为“第一个”的元素和唯一被称为“最后一个”的元素。 n为元素的个数当n0时为空表n0时非空线性表记为a1a2…a1是首结点an是尾结点。 基本操作一维数组可以静态分配也可以动态分配 静态分配数组大小和空间是固定的满了后再加新数据会奔溃动态分配可按照实际的储存数据大小动态分配空间。 线性表特点 表中元素个数有限表中元素具有相同逻辑上的顺序性有先后次序表中元素都是单个数据元素表中元素数据类型相同占的存储空间大小也一样表中元素具有抽象性只考虑逻辑关系不需要考虑存储地址的关系物理顺序。
二、线性表的顺序操作
线性表的顺序存储又称为顺序表它是一组地址连续的存储单位顺序表特点逻辑顺序元素间的关系上相邻的两元素和物理顺序内存地址存储地址上也相邻随机访问通过首地址和元素序号可以在O(1)的时间内找到指定元素存储密度高每个结点只存储数据元素线性表操作 1.插入将插入元素的位置后面的元素整体后移从最后一个元素开始表长L顺序表插入操作的时间复杂度为O(n) 2.删除将元素删除后该元素后面的元素会依次向前移动表长L–时间复杂度为O(n) 3.查找在表中查元素值等于对应元素的位置序号并返回其序号时间复杂度为O(n)
三、线性表的链式表示
链表概念是动态分配存储空间的链式存储结构顺序存取又称为单链表是通过一组任意的存储单位来存储线性表中的数据元素通过指针来建立各数据元素之间的线性关系特点从表中任何一个结点出发都能扫描到整个链表表中元素散列的分布在存储空间中head头结点放第一个结点地址头结点的作用是方便运算。 1.单链表的基本操作 1.1.在链表的表头插入时间复杂度O(1) 1.2.在链表中间插入时间复杂度O(1) 1.3.删除链表第一个结点时间复杂度O(1) 1.4.删除链表的其他结点时间复杂度O(1) 2.单链表创建方法 2.1.头插法时间复杂度O(n) 2.2.尾插法时间复杂度O(n)
结论
单链表按序号查找结点值的时间复杂度为O(n);单链表按值找表结点的时间复杂度为O(n);求表长的时间复杂度为O(n)。
四、双链表
定义每个数据结点中有两个指针分别指向直接后继和直接前驱双链表的基本操作 插入 删除
五、循环链表 1.概念与单链表的区别就是循环链表最后一个节点的指针不是NULL改为指向头节点整个链表成环而循环双链表不同于循环单链表的是双链表的头节点的prior指针还要指向表尾节点。 六、静态链表 1.借助数组来表示指针是节点相对地址数组下标又称游标以next1作为结束的标志操作时不需要移动元素只用修改指针。
七、顺序存储和链表的比较 1.顺序存储链式存储
空间性能 存储密度1更优1容量分配事先确定动态改变更为优 时间性能 查找运算O(n)O(n)读运算更优O(1)O(n)插入运算O(n)O(1)更优删除运算O(n)O(1)更优
2.顺序存储
优点空间利用率高存取速度高缺点删除和插入较慢不可增长长度有空间限制时间性能查找O(1)插入和删除O(n)。
3.链表存储
优点插入和删除快无空间限制只和内存有关缺点需要额外空间存指针查找速度慢时间性能查找O(n),插入和删除O(1)。
PS可由一个尾指针唯一确定的链表有循环链表、循环双链表、双链表
