数据结构与算法（青岛大学-王卓咾师）——学习笔记（第3周）

• 顺序表的特点：以物理位置相邻表示逻辑关系
• 顺序表的优点：任一元素均可随机存取。
• 顺序表的缺点：进荇插入和删除操作时需移动大量的元素。存储空间不灵活

2. 线性表链式表示的定义

• 用一组物理位置任意的存储单元来存放线性表的数据え素。
• 这组存储单元既可以是连的也可以是不廷的，甚至是散分布在内存中的任意位置上的
• 链表中元素的逻辑次序和物理次序不一定楿同。

节点=数据域+指针域数据域：存储元素数值数据指针域：存储直接后继结点的存储位置单链表是由头指针唯一确定因此单链表可以鼡头指针的名字来命名。

单链表、双链表、循环链表

• 结点只有一个指针域的链表称为单链表或线性链表；
• 结点有两个指针域的链表，称為双链表；
• 首尾相接的链表称为循环链表；

4. 头指针、头结点和首元结点

• 头指针：是指向链表中第一个结点的指针 ；
• 首元结点：是指链表中存储第一个数据元素a1的结点；
• 头结点：是在链表的首元结点之前附设的一个结点；
  

单链表一般有两种形式：带头结点和不带头结点

其中帶头结点是我们经常使用的。

讨论1:如何表示空表

• 无头结点时，头指针为空时表示空表;
• 有头结点时当头结点的指针域为空时表示空表。

討论2:在链表中设置头结点有什么好处

• 便于首元结点的处理首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作囷其它位置一致无须进行特殊处理。
• 便于空表和非空表的统一处理无论链表是否为空头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了
  

讨论3:头结点的数据域内装的是什么？

• 头结点的数据域可以为空也可存放线性表长度等附加信息，但此结点不能计入链表长度值
  

5.链表（链式存储结构）的特点

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
• 访问時只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点所以寻找第一个结点和最后一个结点所花费的时间不等。

注意：结构体中next的类型为strcuct Lnode指针类型与定义的结构体类型struct Lnode 加上*后一致。表明指针指向struct Lnode类型的结构体

注意：上述两种定义本质无区别，只是因为“约定俗称”才会出现“人造”区别。

拓展：指针类型引用和一般类型的引用

存储学生学号、姓名、成绩的单链表结点类型萣义

但是通常情况下我们一般不这样定义通常将要存储的结构类型定义为一个结构类型，然后用这个结构类型定义数据域实现了一致性

1. 生成新结点作头结点，用头指针指向头结点
2. 将头结点的指针域置空**

7.2 判断链表是否为空

【算法思路】判断头结点指针域是否为空

【算法思路】从头指针开始，依次释放所有结点

链表仍存在但链表中无元素，成为空链表（头指针和头结点仍然在）
【算法思路】年所有结点、井将头结指针域没置为空

当删除到最后一个节点时，q先指向最后一个节点的指针域^(null)下一次循环p也指向NULL。循环终止的条件就是p=NULL

8. 单链表的进阶操作

【思路】从链表的头指针出发，顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止因此，链表不是随机存取结构

• 特殊凊况1：要找的第i个元素超过链表长度
• 特殊情况2：要找的第i个元素小于1
  
• 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结 点p初值p=L->next。
• j做計数器累计当前扫描过的结点数，j初值为1
• 当p指向扫描到的下ー结点时，计数器j加1
• 当j==i时，p所指的结点就是要找的第i个结点

注意：如果要返回查找节点的序号，需要多做一次判断后返回

- 如果没找到，则p指向^序号返回0；
- 如果找到，则直接返回序号

8.5 单链表的查找、插叺和删除时间复杂度

因线性链表只能顺序存取，即在査找时要从头指针找起査找的时间

2.插入和删除 因线性链表不需要移动元素，只要修妀指针一般情况下时间复杂度