数据结构篇_知识点板块_第二章线性表

• 数据结构篇为本人考研时所写笔记，包括知识点和编程思想两大板块，笔记内容依据王道数据结构考研书所写，但比书本上知识更加生动形象，愿本篇章能对您有所帮助

2、线性表

1. 

2. 对于删除和插入后须要移动几个元素实在记不清带值进去数编程

3. 线性表主要特征：数组

①　个数有限数据结构

②　有序设计

③　数据元素的类型都相同指针

4. 线性表中元素位序是从1开始，数组从0开始code

5. 存储密度=（结点数据自己所占存储量）/（整个结点结构所占的存储总量）blog

6. 链表：内存

①　链式存储设计时，结点内的存储单元地址必须连续io

②　设置头指针的做用：方便了单链表的操做效率

③　单链表：

(1) 单链表的长度是不包括头结点的

(2) 有n个元素的一维数组，创建一个有序单链表最低时间复杂度是O(nlog_2(n))

④　双链表：

(1) 对于双链表由于能够方便的找到前驱结点，故插入、删除操做时间复杂度为O(1)

⑤　循环链表特色：无需增长存储量，仅对表的连接方式修改使表的处理灵活方便

⑥　不带头结点的单链表head为空的断定条件是：head=NULL

带头结点的单链表head为空的断定条件是：head->next==head

⑦　循环单链表：

(1) 判空条件：是否等于头结点

(2) 不设头指针仅设尾指针操做效率更高

⑧　循环双链表：

(1) 判空条件：L头结点的prior域和next域都等于L

⑨　静态链表：

(1) 静态链表的指针又称游标，指示下一个元素在数组中的下标

(2) 连接地址指的是结点next所指的内存地址

(3) 以next=-1做为其结束标志

(4) next指针的含义表示下一个元素在数组中的位置

(5) 容量不可变