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

2022年05月11日 阅读数:1
这篇文章主要向大家介绍数据结构篇_知识点板块_第二章线性表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 数据结构篇为本人考研时所写笔记,包括知识点和编程思想两大板块,笔记内容依据王道数据结构考研书所写,但比书本上知识更加生动形象,愿本篇章能对您有所帮助

2、线性表

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

  2. 线性表主要特征:数组

① 个数有限数据结构

② 有序设计

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

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

  2. 存储密度=(结点数据自己所占存储量)/(整个结点结构所占的存储总量)blog

  3. 链表:内存

① 链式存储设计时,结点内的存储单元地址必须连续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) 容量不可变