第六讲--其他形式链表.ppt

* * 1、线性表的基本特点 是由n(n=0)个结点组成的有穷序列. (直接)前驱 (直接)后继 通常要求同一个线性结构中的所有结点所代表的数据元素具有相同的属性(比如:数据项个数相同;对应数据项的类型相同) 所含结点的个数称为线性表的长度(表长)，表长为0的线性表称为空表。 * * 2、线性表的顺序实现----顺序表 基本思想：按逻辑关系来决定排列顺序，实际就是一维数组，数组的下标可以看成是元素的相对地址。逻辑上相邻的元素的物理位置必紧邻。 存储特点： 优点：可随机存取(访问)； 缺点：插入和删除操作时，需移动大量元素 需事先确定表的容量 容易产生“碎片” * * 长度为 n 的顺序表中，等概率情况下，插入一个元素的平均移动元素次数为 n/2，删除一个元素的平均移动元素次数为 (n-1)/2，其时间复杂度都为O( n ) * * 线性表的链式存储----单链表 基本思想：用一个指针表示结点间的逻辑关系。每个结点的存储单元都分为两部分：一部分存放结点的数据，另一部分存放指向结点后继结点的指针。 存储特点： 优点：对任何位置进行插入和删除操作只需修改指针；不需要预先分配空间； 缺点：顺序存取（访问）的结构（不能从当前结点出发访问到任一结点） * * 带头结点的单链表sq为空的条件： sq-next == NULL 不带头结点的单链表sq为空的条件 sq == NULL 在单链表中,删除某一指定结点时,需找到该结点的前驱结点。 在单链表中设置头结点的作用： 不管单链表是否为空表，头结点指针均不空，并使得对单链表的操作在各种情况下统一。 * * 在单循环链表中通常设置尾指针（指向最后一个结点）比设置头指针好 从一个具有n 个结点的单链表中查找其值等于x的结点时，在查找成功情况下平均需比较 个结点 思考：对于一个有n个结点的单链表，在已知 p所指结点后插入一个结点的时间复杂度是？在给定值为x的结点后插入一个结点的时间复杂度是？ （n+1）/2 使得查找开始结点和终端结点都很方便，其查找时间都是O(1)； 信息工程系 数据结构 数据结构 数据结构 * * 第二章 线性表 单链表的其他操作、其他链表、静态链表 * * 本节内容 一、单链表的其他操作 二、其他链表 三、静态链表（自学） * * 单链表的逆置 算法思路分析： 将一个单链表逆置，意味着所有结点的指针都要改变，其实是生成了一个新的链表，只是该链表的所有结点无需再进行申请空间分配而已。 算法主要思路就是创建一个新的单链表，结点是原链表中的结点，因此只需要进行链的重接，即指针的赋值。 一、单链表的其他操作 * * void reverse(LinkList L) { //将带头结点的单链表L的结点逆序链接 p = L-next; //工作指针 L-next = NULL; //创建空链表（头结点） while( p-next ) { //头插法建立链表 q = p; p = p-next; q-next = L-next; L-next = q; } } * * 最后一个结点的指针域的指针又指回头结点（第一个结点）的链表，整个链表形成一个环。 a1 a2 … ... an 1. 循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 二、其它形式的链表 * * 循环链表小结 特点：最后一个结点的指针指向头结点。 类型定义：同单链表。 基本形态： 空表：L - next = = L 非空表 与单链表的联系： 判断表尾的方法不同： 单链表用p==NULL；循环链表用p==L。 其余操作相同 * * 2. 双向链表 ( 用两个指针表示元素间的逻辑关系 ) typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; /