《数据结构》--线性表的链式存储结构v1.1.pptx

计科系：王丹丹;知识回顾;9.1 定义和使用结构体变量;声明一个结构体类型的一般形式： struct 结构体名 {成员表列}； 例如;9.1.2 定义结构体类型变量的方法;在声明类型的同时定义变量 不指定类型名而直接定义结构体类型变量 ;9.1.3 结构体变量的初始化和引用;9.1.3 结构体变量的初始化和引用;9.2 使用结构体数组;定义结构体数组一般形式 ① struct 结构体名 {成员表列} 数组名[数组长度]; ②先声明一个结构体类型，然后再用此类型定义结构体数组： 结构体类型 数组名[数组长度]; 如： struct Person leader[3]; 对结构体数组初始化的形式是在定义数组后面加上 ＝｛初值表列｝; ;9.3 结构体指针;9.3.1 指向结构体变量的指针;9.3.2 指向结构体数组的指针;本章主要内容;知识回顾;根据实际需求动态地申请空间，并通过一定方法将申请的多个空间联系起来。即：逻辑上相邻未必在物理上相邻。;3.6.2 线性表链式存储结构定义;;基本概念;单链表的物理状态示意图;头结点 在单链表的第一个结点前附设的一个结点。 头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。 例;3.6.3 头指针与头结点的异同;例6：建立简单的静态链表，要求输出各结点中的数据。 解题思路 声明一个结构体类型，其成员包括num,score,next； 将第一个结点的起始地址赋给头指针head，将第2个结点的起始地址赋给第1个结点的next成员，将第3个结点的起始地址赋给第2个结点的next成员； 第3个结点的next成员赋予NULL。;思考：各结点是怎样构成链表的？ 没有头指针head行不行？ p起什么作用，没有它行不行？ 课堂练习：建立如下图所示的简单静态链表，要求输出各结点中的数据。 ;链表结点的结构体定义 ;/************************************************** * 线性表的单链表存储结构 ***************************************************/ typedef struct Node { ElemType data; //定义数据域 struct Node *next; //定义指针域 }Node; typedef struct Node *LinkList; //定义LinkList为结构体指针类型;生成一个node型新结点： 系统回收p结点：;单链表示??( a1 , a2 , …, … , an ) ;3.9 单链表的整表创建; 假设线性表中结点的数据类型是整型，动态地建立链表的常用方法有如下两种：头插法和尾插法。 （1）头插法建表 基本思路 ;头插法建立单链表图示;代码实现;（2）尾插法建表 头插法建立链表头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。 基本思路;尾插法建立单链表图示 ;代码实现;;（3）单链表的输出 基本思路 先将一个指针变量p指向第一个结点，输出结点数据域； 再将p指向下一个结点，输出数据域； 直到p指针指向NULL。;代码实现;（4）求表长;（5）判断单链表是否为空;3.7 单链表的读取;查找范围：p=L-next … p=NULL 查找方法： 找第1个p 找第2个p=p-next; 找第3个p=p-next; p=p-next; 找第i个p=p-next; …p=p-next;（循环i-1次）;代码实现;按内容查找;代码实现;3.8 单链表的插入与删除;代码实现;单链表的删除 设存储元素ai的结点为q，要实现将结点q删除单链表的操作。;代码实现;3.10 单链表的整表删除;代码实现;3.11 单链表结构与顺序存储结构优缺点;;