思维导图--数据结构导论(3)
第二章 线性表
线性表设计到了插入的算法和C语言的基本语法,看的过程中看得比较仔细,用了3个番茄的时间,并做了一下本章的思维导图,如下所示:
主要涉及到的内容
线性表的概念、特征和两种存储结构顺序存储结构和链式存储结构的基本运算实现
从三个方面理解线性表:
1、基本认识
(1)线性表(Linear List)是一种线性结构,是由n(n>=0)个数据元素组成的有穷序列,数据元素又称结点。结点个数n成为表长;
(2)它的基本特征:线性表中结点具有一对一的关系,如果结点数不为零,则除起始节点没有直接前驱外,其他每个结点有且仅有一个直接前驱:除终端结点没有直接后继外,其他每个结点有且仅有一个直接后继。
2、两种存储结构
(1)顺序存储结构:用顺序存储实现的线性表称为顺序表,一般用数组来表示顺序表;
它的实现:将表中的结点依次存放在计算机内存中一组连续地存储单元中,数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置。
(2)链式存储结构:指它的存储结构是链式的。线性表中常见的链式存储结构有单链表、循环链表和双向循环链表。
单链表是线性表的数据元素(火车车厢)用指针(车钩)连接起来的存储结构,一个数据元素和一个指针组成单链表的一个结点;
在单链表中让最后一个结点的指针域指向第一个结点,构成循环链表;
在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior,构成双向循环链表。
3、两种存储结构的基本运算和算法分析
①顺序结构:
优点:易于查询,索引快 list[n]这样的操作,O(1)复杂度
缺点:扩展性弱,不易删除、添加。
②链表结构:
优点:扩展性强,易于删除、添加
缺点:不易于查询,索引慢,list[n]这样的操作,复杂度为O(n)
补充内容【O(1)和O(n)】
1、结合这个具体问题进行的分析:
O(1)和O(n)是一种大O表示法,第一个与问题规模n没有关系,第二个表示当n充分大时,查询的速度和所占的空间与n 成正比。
2、具体的含义来自百度百科:
大O表示法:称一个函数g(n)是O(f(n)),当且仅当存在常数c>0和n0>=1,对一切n>n0均有|g(n)|<=c|f(n)|成立,也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。
定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时,时间复杂度的极限情形称为算法的“渐近时间复杂度”。