[NEFU 数据结构] 第 2 章 线性表 知识点整理

[NEFU 数据结构] 第 2 章 线性表 知识点整理

阅读须知

• 需求指向：
  此博客用于应付NEFU数据结构考试，基于题目进行整理，不适合想深入学习数据结构与算法艺术的同学。
• 前置知识：
  C语言
• 参考资料：
  数据结构C语言版|第二版 严蔚敏
  数据结构C语言版习题解析与实验指导|第二版 严蔚敏
• 推荐博客
  [NEFU]数据结构 知识点整理和代码实现

一、思维导图

二、考点

2.1 线性表的定义和特点

• 存在唯一的一个被称作第一个的数据元素
• 存在唯一的一个被称作最后一个的数据元素
• 除第一个之外，结构中的每个数据都只有一个前驱
• 除最后一个之外，结构中的每个数据都只有一个后继

2.4 线性表的顺序表示和实现

• 逻辑上相邻的元素，其物理次序也是相邻的
• 
• 线性表的存储结构是一种随机存储结构
• 顺序表的基本操作实现

2.5 线性表的链式表示和实现

• 存储单元可以连续也可以不连续
• 结点包含数据域和指针域
• 首元结点：存储第一个数据元素的结点
• 头结点：首元结点之前附设的结点
• 头指针：指向链表中第一个结点的指针
• 单链表是非随机存取的存储结构，也称为顺序存取
• 所有结点通过指针的链接而组织成单链表
• 单链表基本操作的实现

• 循环链表中止条件：p!=L,p->next!=L
• 循环链表设立尾指针不设头指针，两个线性表合并复杂度
• 双向链表插入删除操作复杂度为

2.6 顺序表和链表的比较

• 
• 顺序表存储密度1,链表存储密度小于1
• 背下面两个表
  

2.7 线性表的应用

• 线性表的合并：
• 有序表的合并
  仍然按照原序排列：最好,最坏
  按照原序逆序排列：