第二章-线性表 1.线性表的定义和基本操作

定义

具有相关数据类型的n个数据元素的有限序列叫做线性表.
术语:
位序,表头元素,表尾元素,直接前驱,直接后继.

线性表的基本操作
基本记忆思路: 创建销毁,增删改查.

知识回顾

两种存储结构

顺序表(顺序存储)

顺序存储方式实现的线性表.

1 使用静态数组,实现顺序表
初始化时,顺序表长度设置为0

c++共有三种传递值的方式:
1.值传递
2.引用传递(c++独有,c没有)
3.指针或地址传递

2 动态分配
malloc和free函数搭配使用.

顺序表的特点:

• 随机访问,O(1)时间内就可以找到第i个元素.
• 存储密度高,只存储数据元素(不存储指针数据)
• 宽展容量不方便,(即使采用动态分配方式实现,扩展长度的时间复杂度较高)

插入的时间复杂度
问题规模n=l.length(表长)
最好O(1)
最坏O(n),在第一个位置插入,全部元素都要后移.

删除的时间复杂度
最好情况O(1)
最坏情况O(n)
平均情况O(n)

顺序表的查找
最好情况O(1)
最坏情况O(n)
平均时间复杂度(N+1)/2即O(n)
需要注意位置和数组下标的关系

链表(链式存储)

是否带头结点

某结点之前插入数据
思路是交换数据(偷天换日的行为!)
指定节点的删除,思路也是交换数据.
数据结构常见时间复杂度

双向链表

初始化 prior,next都指向null
p后插q结点的操作
简易记法:
出发去p的后继节点->从p的原后继节点回来(需要判空,是否有后继节点)
->去p->从p回来

循环链表

静态链表

操作系统FAT表,会用到静态链表

线性表和链表的比较

基本操作