链式存储结构

链表

简介

格式

案例 开头是头指针H 指向第一个数据元素的数据域，之后第一个数据元素的指针域指向第二个元素的数据域，由此连接成一个链表，最后末端是一个空指针，记作“^”

分类

头结点

位置

头指针只是一个指针域，没有数据域，头结点有数据域和指针域

示意图

与不带头结点的区别

数据域任意存放数据，可以用来存放线性表的长度等信息，但是头结点不计入链表的长度值

链表的特点

单链表

定义

链表的代码实现

简介

首先，对于一个结点来说，包含两个东西，一个是数据域，一个是指针域，用代码实现一个结点的时候，要用结构体， 第二，结构体里面，对于数据域的定义，使用表中的数据类型对应即可，对于指针域，因为其指向的是下一个结点，而每个结点都是一个结构体，所以，指针的类型是结构体类型，与自己所在的结构体一模一样 第三，typedef 是对后面圈起来的结构体起别名，相当于Java中对一个类起了一个别名，后面的Lnode 以及 *LinkList都是结构体的别名，二者是两种不同的形式

对于Lnode，可以直接利用它来定义一个对象，之后利用该对象调用结构体中的数据，这样这个对象就是结点本身 也可以，定义一个该类型的指针，用指针来操作结构体中的数据，这样指针就是指向结点的，如下图 而对于定义指针可以有更简便的方法，因为还定义了一个别名 是 *LinkList，所以可以直接，LinkList p 如下图

实操

定义链表，以及定义结点时，通常采用图中黄色部分

注意别忘了，头指针表示整个链表

右边为统一的定义方式，将所有数据打包为一个结构体，之后直接定义结构体类型的数据域

基本操作的实现

初始化单链表

销毁单链表

首先将头指针的值赋值给结点指针p，之后要把第一个结点的指针域赋值给头指针L，以便L可以下移，找到下一个结点

之后销毁第一个结点，再把L的值赋给p，L再下移，这样循环，就可以销毁单链表

清空单链表

思路与销毁差不多，只不过新定义了一个指针，用来代替销毁时的L，这时L保持不动，用于保留头指针和头结点，最后将头结点的指针域置空即可 循环顺序与销毁有所不同，这里顺序不同，一定程度上影响着循环条件的判断，具体问题具体分析即可

求单链表表长

注意，p所指向的是一个结点，所以，p有值，那么就表示有结点，最后p指向空的时候，就会跳出循环 注意 头结点不计入长度，长度从首元结点算起

取值

算法分析 注意第15个元素不存在，这里有异常情况的处理 计数器很重要，用来记录当前的结点位置

算法设计

查找

算法思路 算法实现 注意，&&是逻辑与的意思，假：一假全假，真：全真才为真 ||是逻辑或的意思，真：一真全真，假：全假才为假

当返回当前位置时，加个计数器即可

插入

注意执行的先后顺序，可能会导致数据的丢失 这里循环条件判断，p不为空，并且要j<i-1，注意 相对于 j !=i-1，j<i-1 更为严谨，因为i-1的值是直接输入，可能初值就比j要大 之后做一个条件判断，处理异常情况

之后创建一个新结点，创建时，利用指针创建，也就是创建指针形式的新结点，这样，新结点的地址也就有了

二级目录

二级目录

二级目录