《数据结构四次课-线性表B》由会员分享，可在线阅读，更多相关《数据结构四次课-线性表B（31页珍藏版）》请在金锄头文库上搜索。
1、每课一贴：有一位表演大师上场前，他的弟子告诉他鞋带松了。 大师点头致谢，蹲下来仔细系好。等到弟子转身后，又 蹲下来将鞋带解松。有个旁观者看到了这一切，不解地 问：“大师，您为什么又要将鞋带解松呢？”大师回答道 ：“因为我饰演的是一位劳累的旅者，长景涉让他的鞋事 松开，可以通过这个细节表现他的劳累憔悴.”“那你为什 么不直接告诉你的弟子呢？”“他能细心地发现我的鞋带 松了，并且热心地告诉我，我一定要保护他这种热情的 积极性，及时地给他鼓励，至于为什么要将鞋带解开， 将来会有更多的机会教他表演，可以下一次再说啊。”人 一个时间只能做一件事，懂抓重点，才是真正的人才. 1上堂课要点回顾1. 线性结构
2、(包括表、栈、队、数组）的定义和特点： 2. 仅一个首、尾结点，其余元素仅一个直接前驱和 一个直接后继。2. 线性表逻辑结构：“一对一” 或 1:1 存储结构：顺序、链式 运 算：修改、插入、删除3.顺序存储特征：逻辑上相邻，物理上也相邻； 优点：随机查找快 O(1) 缺点：插入、删除慢 O(n)22.3 线性表的链式表示和实现2.3.1 链表的表示2.3.2 链表的实现2.3.3 链表的运算效率分析链表小结32.3.1 链表的表示链式存储结构特点：其结点在存储器中的 位置是随意的，即逻辑上相邻的数据元素 在物理上不一定相邻。如何实现？通过指针指针来实现注意：每个存储结点都包含两部分：数据域和
3、指针域4与链式存储有关的术语：1、结点：数据元素的存储映像。由数据域和指针域两部分组成；2、链表： n 个结点由指针链组成一个链表。它是线性表的链式 存储映像，称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表； 有两个指针域的链表，称为双链表； 有多个指针域的链表，称为多链表； 首尾相接的链表称为循环链表。a1heada2anhead循环链表示意图：54、头指针、头结点和首元结点 示意图如下：头指针头结点首元结点a1heada2infoan头指针是指向链表中第一个结点（或为头结点或为首元结点 ）的指针；头结点是在链表的首元结点之前
4、附设的一个结点；数据域内 只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。 6一个线性表的逻辑结构为：（ ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储 结构用单链表表示如下，请问其头指针的值是多少？存储储地址数据域指针针域 1LI43 7QIAN13 13SUN1 19WANGNULL 25WU37 31ZHAO7 37ZHENG19 43ZHOU25例：答：头指针是指向 链表中第一个结点 的指针，因此关键 是要寻找第一个结 点的地址。7ZHAOH 31头指针的值是317上例链表的逻辑结构示意图有以下两种形式： ZHAOQIA
5、NLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别： 无头结点 有头结点 8答：讨论1. 在链表中设置头结点有什么好处？讨论2. 如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结 点的数据域中不存储线性表的数据元素，其作用是为了对链表 进行操作时，可以对空表、非空表的情况以及对首元结点进行 统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表； 有头结点时，当头结点的指针域为空时表示空表 。头指针 头指针头结点无头结点有头结点 9讨论2. 头结点的数据域内装的是什么？头结点的数据域可以为空，也可存放线性表长度
6、 等附加信息，但此结点不能计入链表长度值。答：讨论3. 链表的数据元素有两个域，不再是简单数据 类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数 据类型。答：什么是结构类型？如何书写表达？ 头结点的数据域H10 实现 结点接口 Public interface Node public Object getData( ); /获取结点数据域 Public void setData(Object object); /设置结点数据域 3. 线性链表的实现 定义：结点中只含一个指针域的链表叫，也叫 单链表Public class SLNode implements Nodepriva
7、te Object element;private SLNode next;public SLNode this(null,null);public SLNode(Object ele, SLnode next)this.element=ele; this.next=next; public SLNode getNext( ) return next;public void setNext(SLNode next) this.next =next;public Object getData( ) return element;public void setData(Object obj) el
8、ement=obj; 11 用一组任意的存储单元存储线性表的数据 元素 利用指针实现了用不相邻的存储单元存放 逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还 需存储其直接后继的地址 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置数据域 指针域结点简单总结：线性表的链式表示的基本特征：124. 单链表的基本运算While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n算法评价v 查找：查找单链表中是否存在结点X查找、插入、删除、创建、原地逆序算法描述类似算法：清空、求长度等，举一反三p=head; /p是头结点的引用while(p.getNext( )!=nul
9、l)if(x=p.getData( ) return true;else p= p.getNext( );return false;13pabxs插入: 在线性表两个数据元素a和b间插入x，已 知p指向a算法描述算法评价注意前插入和后插入的 区别s.setNext(p.getNext( );p.setNext(s);14算法描述pabc算法评价删除：单链表中删除b，设p指向 ap.setNext(p.getNext( ).getNext( );15 动态建立单链表算法：设线性表n个 元素已存放在数组a中，建立一个单链表，h为 头指针h头结点 an 0h头结点 an-10an a2.h头结点 a
10、n-10an ha1a2头结点an .0h头结点 0h.setData(0); h.setNext(NULL);/依次在链表头部插入结点，次序是先插入最后一个，然 后再插入前面元素for(i=n;i0;i-) /注意i的变化 s=new SLNode( );s.setData(ai-1); s.setNext(h.getNext( );h.setNext(s);算法描述算法评价 16单链表原地逆序算法：设线性表n个 元素已存放在链表a中，要求在不改变其元素位 置的条件下将链表逆序排列，h为头指针ha1a2头结点an .0hanan-1头结点a1 .017单链表原地逆序算法：设线性表n个 元素已
11、存放在链表a中，要求在不改变其元素位 置的条件下将链表逆序排列，h为头指针算法描述算法评价prv=NULL; /prv指示新链表的首元结点/pt是变化的未逆序部分链表的第一个结点pt=h.getNext( );while(pt!=NULL) tmp=pt.getNext( ); /取下一个结点pt.setNext(prv); /当前结点指针指向自己前 一个结点prv=pt; /prv保存当前结点指针 pt=tmp; /pt指向下个结点h.setNex(prv); /头指针指向新链表18答：能。只要定义一个结构类型（含数据域和指示 域）数组，就可以完全描述链表，这种链表称为静 态链表。 注：数据
12、域含义与前面相同，指示域相当于前面的 指针域。讨论1： 用一维数组也能存放链表吗？怎样实现？静态链表的插入与删除操作与普通链表一样， 不需要移动元素，只需修改指示器就可以了。19讨论2： 链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结 点即可 (P.setNext(head);) 。这种形成环路的链表 称为循环链表。讨论3： 单链表只能查找结点的直接后继，能不能 查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可(例 如用next和pre;) 。双向链表在非线性结构（如树结构）中将大量使用。predatanext这种有两个指针的链表称为双向链表。其特
13、点是 可以双向查找表中结点。20循环链表是表中最后一个结点p的指针指 向头结点，使链表构成环状 p.setNext(head); 特点：从表中任一结点出发均可找到表 中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p=h.getNext( ); p!=NULL 循环链表p=h.getNext( ); p!=hhh空表 循环链表(circular linked list)21双向链表（double linked list） 单链表具有单向性的缺点Public class DLNode implements Node private Object element;private
14、 DLNode pre;private DLNode next;public DLNode( ) this(null,null,null);public DLNode( Object ele, DLNode pre, DLNode next) this.element=ele; this.pre=pre; this.next=next; public DLNode getNext( ) return next;public void setNext(DLNode next) this.next=next;public DLNode getPre( ) return pre;public voi
15、d setPre(DLNode pre) this.pre=pre;public Object getData( ) return element;public void setData(Object obj ) element=obj; preelementnextv结点定义22双向链表（double linked list） 单链表具有单向性的缺点preelementnextL空双向循环链表：v结点定义非空双向循环链表： LABbcap(p.getPre( ).getNext( )= p= (p.getNext( ).getPre( );23bcaP(p.getPre( ).setNext(p.getNext( ); (p.getNext( ).setPre(p.getPre( ); 删除算法描述算法评价：T(n)=O(1)(p.getPre( ).setNext(p.getNext( );(p.getNext( ).setPre(p.getP
