第2章线性表数据结构与算法Java版

1、第二章第二章 线性表线性表第二章第二章 线线 性性 表表2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.4 顺序表与链表的比较顺序表与链表的比较2.1 线性表及其基本操作线性表及其基本操作2.5 线性表的应用举例线性表的应用举例第二章第二章 线线 性性 表表重点：重点：u顺序表与链表类的描述方法；顺序表与链表类的描述方法；u在两种存储结构上实现线性表的基在两种存储结构上实现线性表的基 本操作的算法。本操作的算法。难点：难点：u线性表在两种存储结构上的插入、线性表在两种存储结构上的插入、删除算法及动态链表的创建算法。删除算法及动

2、态链表的创建算法。第二章第二章 线线 性性 表表课前思考课前思考u按数据元素之间的逻辑关系不同，数按数据元素之间的逻辑关系不同，数 据结构有哪几类？据结构有哪几类？u你能举出几个你熟悉的你能举出几个你熟悉的“序列序列”的例子来的例子来 吗？吗？ 线性结构、树型结构、图型结构和线性结构、树型结构、图型结构和集合四类。集合四类。 如：如：00，1 1，2 2，9,A9,A，B B，C C，ZZ。2.1 线性表及其基本操作线性表及其基本操作1.1.线性表的定义：线性表的定义： 一个线性表（一个线性表（Linear ListLinear List）是由）是由n(n0)n(n0)个数据元素（结点）所构成

3、的有个数据元素（结点）所构成的有限限序列序列。线性表逻辑地表示为：。线性表逻辑地表示为：（a a0 0,a,a1 1, ,a,an-1n-1) )。其中，。其中，n n为线性表的为线性表的长长度度，n=0n=0时为时为空表空表。称。称i i为为aiai在线性表中在线性表中的的位序号。位序号。2.1 线性表及其基本操作线性表及其基本操作 2. 2. 线性表的结构（逻辑结构）特点：线性表的结构（逻辑结构）特点： c.c. 每个元素除第一个元素和最后一个元素每个元素除第一个元素和最后一个元素之外之外, ,有且仅有一个有且仅有一个前驱前驱和一个和一个后继后继。学号姓名大学英语高等数学计算机文化基础总分

4、200853174101王一608178219200853174102刘二947682252200853174103张三907872240200853174104李四857371229开始结点开始结点终端结点终端结点a. a. 它由它由n n个个同类型同类型的元素组成；的元素组成； b. b. 有且仅有一个有且仅有一个第一个元素第一个元素和和最后一个元素；最后一个元素；2.1 线性表及其基本操作线性表及其基本操作 1. 1.基本操作基本操作 clear( )1 1）线性表的置空操作：）线性表的置空操作： isEmpty( )2 2）线性表判空操作：）线性表判空操作： length( )3）求线

5、性表的长度：）求线性表的长度：4）取元素操作：）取元素操作：5）插入操作：）插入操作：get( i )insert( i, x )6）删除操作：）删除操作：remove( i)7）查找操作：）查找操作：indexOf(x )8）输出操作：）输出操作：display()2.1 线性表及其基本操作线性表及其基本操作 2. 2.线性表抽象数据类型的线性表抽象数据类型的JavaJava接口描述接口描述public interface IList public void clear(); public boolean isEmpty();public int length(); public Objec

6、t get(int i); public void insert(int i, Object x); public void remove(int i); public int indexOf(Object x);public void display();2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现线性表的线性表的起始地址起始地址称作线性表的称作线性表的基地址基地址 a0 a1 ai-2 ai-1 an-11.概念概念 (1) 顺序存储：顺序存储：(2) 顺序表：顺序表： 用顺序存储的线性表就称为顺序表用顺序存储的线性表就称为顺序表n为表的长度为表的长度 用一组用一组地址连续地址

7、连续的存储单元的存储单元 依依次存放次存放 线性表中的数据元素的存储结构。线性表中的数据元素的存储结构。0 1 i-2 i-1 n-12.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2.地址计算公式地址计算公式以以“存储位置相邻存储位置相邻”表示有序对表示有序对 即：即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占的存储量一个数据元素所占的存储量 所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置LOC(ai) = LOC(a0) + iC 基地址基地址2.2 线性表的顺序存储及其实现线性表的顺序存储及其实

8、现 存储地址存储地址 内在状态内在状态 元素在线性表的元素在线性表的位序号位序号a0a1aian-1b(基地址基地址）b+Cb+i*Cb+(n-1)*Cb+(maxSize-1)*C01in-1空闲空闲2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现3. 特点特点(1) 逻辑上相邻的数据元素，赋以相邻的逻辑上相邻的数据元素，赋以相邻的 存储位置；存储位置；(2) 存储密度高；存储密度高；存储密度存储密度 ： 数据元素的值所需的存储空间数据元素的值所需的存储空间d= 该元素实际所需的存储空间该元素实际所需的存储空间(4) 不便于不便于插入、删除操作。插入、删除操作。 （会引起大量结点的移

9、动）（会引起大量结点的移动）(3) 便于便于随机存取；随机存取；2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现4. 顺序存储结构的描述顺序存储结构的描述public class SqList implements IList 线性表的顺序存储结构在线性表Java接口的实现类中描述如下：listElemcurLen=621 32 11 24 57 44 0 1 2 3 4 5 maxSize-1线性表线性表21,32,11,24,57,44顺序存储结构图顺序存储结构图 private Object listElem; / 线性表线性表存储空间存储空间private int curLen

10、; ; /线性表的线性表的当前长度当前长度2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现5. 顺序表类的描述顺序表类的描述 （见书（见书P33）public class SqList implements IList private Object listElem; private int curLen; /构造一个容量为构造一个容量为maxSize的空顺序表函数的空顺序表函数 public SqList (int maxSize) / 顺序表置空函数顺序表置空函数 public void clear( ) curLen = 0; listElem = new ObjectmaxSi

11、ze;curLen = 0; 2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现5. 顺序表类的描述顺序表类的描述 return curLen; / / 判判空函数空函数public boolean isEmpty( ) / / 求顺序表长度函数求顺序表长度函数 public int length( ) / / 读取顺序表中第读取顺序表中第i i个元素的函数个元素的函数 public Object get (int i) throws Exception return curLen = 0;if (i curLen 1) throw new Exception(第第 + i + 个元素不

12、存在个元素不存在); public class SqList implements IList return listElemi; 2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现5. 顺序表类的描述顺序表类的描述public class SqList implements IList / / 插入操作的函数插入操作的函数public void insert (int i, Object x) / / 删除操作的函数删除操作的函数public void remove (int i) / / 查找操作的函数查找操作的函数public int indexOf (Object x) 2.2

13、线性表的顺序存储及其实现线性表的顺序存储及其实现2.2.2 2.2.2 顺序表上基本操作的实现顺序表上基本操作的实现1. 插入操作插入操作 insert(i, x)的实现（书中算法的实现（书中算法 2.1) 在第在第i个元素个元素ai之前插入一个值为之前插入一个值为x的元素的元素 问题：问题： 插入元素时，线性表的插入元素时，线性表的 逻辑结构发生什么变化？逻辑结构发生什么变化？2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现1. 插入操作插入操作 insert(i, x)的实现（书中算法的实现（书中算法 2.1) (a0, , ai-1, ai, , an-1) 改变为改变为 (a0

14、, , ai-1, x , ai, , an-1)a0 a1 ai-1 ai an-1a0 a1 ai-1 aixan-1, 当前表的长度增加当前表的长度增加12.2 线性表的顺序存储及其实现线性表的顺序存储及其实现1. 插入操作插入操作 insert(i, x)的实现（书中算法的实现（书中算法 2.1)21 18 30 75 42 56 8721 18 30 75例如：例如：insert (4, 66), 顺序表顺序表listElem如下如下: curLen-1087564266curLen-10for (int j = curLen; j i; j-) listElemj = listEl

15、emj - 1; /后移后移 listElemi = x; / 插入插入xlistElemmaxSize-12.2 线性表的顺序存储及其实现线性表的顺序存储及其实现1. 插入操作插入操作 insert(i, x)的实现（书中算法的实现（书中算法 2.1) a.检测空间是否足够及参数检测空间是否足够及参数i是否合法是否合法 b.插入位置及之后的所有元素后移一个位置插入位置及之后的所有元素后移一个位置 c.插入插入 d.修正表长：表长加修正表长：表长加1for (int j = curLen; j i; j-) listElemj = listElemj - 1;)若若curLen= listEl

16、em.length，则无空的存，则无空的存 储空间，抛出异常。储空间，抛出异常。)若若i curLen，插入位置不合法，插入位置不合法， 抛出异常；抛出异常； listElemi = x;curLen+;2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现1. 插入操作插入操作 insert(i, x)的实现（书中算法的实现（书中算法 2.1)public void insert (int i, Object x) throws Exception /算法2.1结束if (curLen = listElem.length) throw new Exception(“顺序表已满”); if

17、(i curLen) / i不合法 throw new Exception(“插入位置不合法”);for (int j = curLen; j i; j-) /后移后移 listElemj = listElemj - 1;listElemi = x; /插入插入 curLen+; /表长加表长加1 2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现1. 插入操作插入操作 insert(i, x)的实现（书中算法的实现（书中算法 2.1)（考虑移动元素的（考虑移动元素的平均情况平均情况） 在顺序表的第i（0in）个数据元素之前插入一个新的数据元素，会引起n-i个数据元素向后移动向后移动一个

18、存储位置。 假设在第 i 个元素之前插入的概率为 pi ，则在等概率的情况下，移动元素的平均次数移动元素的平均次数为niiinp0)(niinn0)(112n时间复杂度为：时间复杂度为：O(n)2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2. 删除操作删除操作 remove ( i )的实现（书中算法的实现（书中算法 2.2)问题问题：删除元素时，线性表的逻辑删除元素时，线性表的逻辑 结构发生什么变化？结构发生什么变化？ 将第将第i i个位置上的数据元素从顺序表中删个位置上的数据元素从顺序表中删除。除。2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2. 删除操作删除操作

19、remove ( i )的实现（书中算法的实现（书中算法 2.2) (a0, , ai-1, ai, ai+1, , an-1) 改变为改变为 (a1, , ai-1, ai+1, , an)ai+1an-1, 当前表的长度减少1a0 a1 ai-1 ai ai+1 an-1a0 a1 ai-1 2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2. 删除操作删除操作 remove ( i )的实现（书中算法的实现（书中算法 2.2)例如：例如：remove(3)，顺序表顺序表listElem如下如下:for (int j = i; j curLen - 1; j+) listElemj

20、 = listElem j + 1; /前移前移21 18 30 75 42 56 8721 18 30 75 42 56 87 curLen-1005687curLen-142listElem2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2. 删除操作删除操作 remove ( i )的实现（书中算法的实现（书中算法 2.2) a.检测参数检测参数i是否合法是否合法 b.插入之后的所有元素前移一个位置插入之后的所有元素前移一个位置 c.修正表长：表长减修正表长：表长减1for (int j = i; j curLen - 1; j+) listElemj = listElem j

21、+ 1; 若若i curLen-1，删除位置不合法，删除位置不合法，抛出异常；抛出异常；curLen-;2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2. 删除操作删除操作 remove ( i )的实现（书中算法的实现（书中算法 2.2)public void remove(int i) throws Exception /算法算法2.2结束结束if (i curLen - 1) throw new Exception(删除位置不合法);for (int j = i; j curLen - 1; j+) /前移前移 listElemj = listElemj + 1;curLen-

22、; /表长减表长减12.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2. 删除操作删除操作 remove ( i )的实现（书中算法的实现（书中算法 2.2)（考虑移动元素的（考虑移动元素的平均情况平均情况） 在长度为n的顺序表上删除第i i（0in-1）个数据元素会引起n-i-1n-i-1个数据元素向前移向前移动动一个存储位置。假设删除第i个元素的概率为 pi ，则在等概率的情况下，移动元素的平移动元素的平均次数均次数为：10)1(niiinp10) 1(1niinn21n时间复杂度为：时间复杂度为：O(n)2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现3. 查找操作查找操

23、作 indexOf( x )的实现（书中算法的实现（书中算法 2.3) 查找数据元素查找数据元素x x在顺序表中是否存在顺序表中是否存在在, ,若存在则函数返回若存在则函数返回x x初次出现的位初次出现的位置置, ,否则返回否则返回-1-1。2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现3. 查找操作查找操作 indexOf( x )的实现（书中算法的实现（书中算法 2.3)例如：顺序表例如：顺序表curLen=7maxSizex =38jjjjjj0 1 2 3 0 750j可见，可见，基本操作基本操作是：将顺序是：将顺序表中的元素逐个和给定值表中的元素逐个和给定值 x x相比较。

24、主要实现语句如下：相比较。主要实现语句如下：23 75 41 38 54 62 17listElemwhile (j curLen & !listElemj.equals(x)j+;2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2）算法）算法 public int indexOf (Object x) /算法算法2.3结束结束int j = 0;while (j curLen & !listElemj.equals(x)j+; if (j curLen) return j; else return -1; 3. 查找操作查找操作 indexOf( x )的实现（书中算

25、法的实现（书中算法 2.3)2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现3 3）算法的性能分析）算法的性能分析 如果待查找的数据元素x在顺序表中第第 i i 个位置个位置上，则需比较比较i+1i+1次次，所以在等概率条件下，数据元素的平均比较次数为：10) 1(1niin2n3. 查找操作查找操作 indexOf( x )的实现（书中算法的实现（书中算法 2.3)10) 1(niiip时间复杂度为：时间复杂度为：O(n)2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2.2.3 2.2.3 顺序表应用举例顺序表应用举例【例【例1 1】 编程实现：建立一个顺序表（编程实现：建

26、立一个顺序表（a, a, z, d, m, zz, d, m, z），然后查找顺序表中），然后查找顺序表中第一次出现的值为字母第一次出现的值为字母zz的数据元素，并输的数据元素，并输出其在顺序表中的位置。出其在顺序表中的位置。 先利用顺序表SqList类创建一个顺序表对象L，然后引用顺序表对象中的insert方法（函数）依次将顺序表中的字母插入到表中，从而完成顺序表的建立。再引用顺序表对象中的indexOf方法来实现查找操作。2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2.2.3 2.2.3 顺序表应用举例顺序表应用举例public class Example2_1 public

27、static void main (String args) throws Exception SqList L = new SqList(10); L.insert(0, a); L.insert(1, z); L.insert(2, d); L.insert(3, m); L.insert(4, z); int order = L.indexOf(z); if (order != -1)System.out.println(顺序表中第一次出现的值为顺序表中第一次出现的值为z的数据元素的位置为：的数据元素的位置为： + order); elseSystem.out.println(此顺序表中

28、不包含值为此顺序表中不包含值为z的数的数据元素！据元素！);2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2.2.3 2.2.3 顺序表应用举例顺序表应用举例【例【例2 2】编程实现查找线性表（编程实现查找线性表（0 0，1 1，2 2，n-1n-1）中第）中第i i（1 1i in n）个数据元素的直接前）个数据元素的直接前驱，并输出其值。要求在顺序表上实现。驱，并输出其值。要求在顺序表上实现。 先利用顺序表SqList类创建一个顺序表对象L，然后引用顺序表对象中的insert方法（函数）依次将顺序表中的数据值插入到表中,从而完成顺序表的创建。再引用顺序表对象中的get方法来完成指

29、定操作。2.2 线性表的顺序存储及其实现线性表的顺序存储及其实现2.2.3 2.2.3 顺序表应用举例顺序表应用举例public class Example2_2 请学生作为上机实验题完成！请学生作为上机实验题完成！2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.1 2.3.1 单链表的表示单链表的表示 用一组用一组 地址任意地址任意的存储单元存放线性表的存储单元存放线性表中的数据元素。中的数据元素。以以元素元素(数据元素的映象数据元素的映象) + 指针指针(指示后继元素存储位置指示后继元素存储位置) = 结点结点 (表示数据元素表示数据元素 或或 数据元素的映象数据元素的映象

30、)以以“结点的序列结点的序列”表示线性表表示线性表 称作称作链表链表2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.1 2.3.1 单链表的表示单链表的表示头结点头结点 a0 a1 . an-1 头指针头指针头指针头指针 有时为了操作方便，在第一个结点（首结有时为了操作方便，在第一个结点（首结点）之前虚加一个点）之前虚加一个“头结点头结点”，以指向头结点，以指向头结点的指针为链表的的指针为链表的头指针头指针。空指针空指针 首结点首结点尾结点尾结点 以线性表中第一个数据元素以线性表中第一个数据元素a0的存储地址的存储地址作为线性表的地址，称作线性表的作为线性表的地址，称作线性表的

31、头指针头指针。线性表为空表时，线性表为空表时，头结点的指针域为空头结点的指针域为空2.3 线性表的链式存储及其实现线性表的链式存储及其实现1. 结点类的描述结点类的描述（P39-40）public class Node private Object data; / 存放结点值存放结点值private Node next; / 后继结点的引用后继结点的引用public Node( ) / 无参数时的构造函数无参数时的构造函数 this(null, null);public Node(Object data) /带一个参数时的构造函数带一个参数时的构造函数 this(data, null);pub

32、lic Node(Object data, Node next) /带两个参数时带两个参数时 /的构造函数的构造函数 this.data = data; this.next = next;2.3 线性表的链式存储及其实现线性表的链式存储及其实现1. 结点类的描述结点类的描述（P39-40）public class Node public Object getData( ) return data;public Node getNext() return next;public void setData(Object data) this.data = data;public void setN

33、ext(Node next) this.next = next;2.3 线性表的链式存储及其实现线性表的链式存储及其实现2. 单链表类的描述单链表类的描述（P40-41）import java.util.Scanner;public class LinkList implements IList private Node head; / / 单链表的头指针单链表的头指针public LinkList( ) / / 单链表的构造函数单链表的构造函数 head = new Node(); / / 初始化头结点初始化头结点 public LinkList (int n, boolean Order)

34、 throws Exception this(); / / 初始化头结点初始化头结点 if (Order) / / 用尾插法顺序建立单链表用尾插法顺序建立单链表 create1(n); else / / 用头插法逆位序建立单链表用头插法逆位序建立单链表 create2(n);2.3 线性表的链式存储及其实现线性表的链式存储及其实现2. 单链表类的描述单链表类的描述（P40-41）import java.util.Scanner;public class LinkList implements IList public void create1(int n) throws Exception p

35、ublic void create2(int n) throws Exception public void clear() public boolean isEmpty() /判空函数判空函数 head.setData(null);head.setNext(null);return head.getNext() = null; 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2. 单链表类的描述单链表类的描述（P40-41？）？）import java.util.Scanner;public class LinkList implements IList public int len

36、gth( ) /求单链表的长度求单链表的长度 Node p = head.getNext();/ 初始化初始化int length = 0;p = p.getNext();/ 指向后移指向后移+length; / 长度增长度增1while (p != null) return length;2.3 线性表的链式存储及其实现线性表的链式存储及其实现2. 单链表类的描述单链表类的描述（P40-41？）？）import java.util.Scanner;public class LinkList implements IList public Object get (int i) throws E

37、xception public void insert (int i, Object x) throws Exception public void remove (int i) throws Exception public int indexOf (Object x) 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2. 单链表类的描述单链表类的描述（P40-41？）？）import java.util.Scanner;public class LinkList implements IList public void display( ) Node node = head.get

38、Next(); while (node != null) System.out.print(node.getData( )+ );node = node.getNext(); / / 取下一取下一个结点个结点 System.out.println();/ 换行换行 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2.3.2 单链表上基本操作的实现单链表上基本操作的实现1. 查找操作查找操作1) 1) 按按位序号位序号查找操作查找操作 get(iget(i）的实现的实现 单链表是一种单链表是一种 顺序存取顺序存取 的结构，的结构，即：为取第即：为取第 i i 元素，首先必须先

39、找到元素，首先必须先找到第第 i-1 i-1 个元素。因此不论个元素。因此不论 i i 值为多少，值为多少，都必须都必须从头结点开始起从头结点开始起 点数点数 ，直数到直数到第第 i i 个为止。头结点可看成是第个为止。头结点可看成是第-1-1个个结点。结点。 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2.3.2 单链表上基本操作的实现单链表上基本操作的实现1. 查找操作查找操作1) 1) 按按位序号位序号查找操作查找操作 get(iget(i）的实现的实现L211830754256 pppj0 1 2 下面为操作下面为操作get(2)get(2)的动态演示过程：的动

40、态演示过程：2.3 线性表的链式存储及其实现线性表的链式存储及其实现按按位序号位序号查找操作查找操作 get(iget(i）的算法的算法public Object get(int i) throws Exception /算法算法2.42.4结束结束Node p = head.getNext(); int j = 0;while (p != null & j i | p = null) / i小于小于0或者大于表长减或者大于表长减1 throw new Exception(第第 + i + 个元素不存在个元素不存在);return p.getData(); 问：问： 能否将变量初始化改

41、为能否将变量初始化改为p=head; j=-1;? 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2.3.2 单链表上基本操作的实现单链表上基本操作的实现1. 查找操作查找操作2) 2) 按按值值查找操作查找操作 indexOf(xindexOf(x）的实现的实现 从单链表的从单链表的首结点开始首结点开始沿着后继沿着后继指针依次对各结点的数据域值指针依次对各结点的数据域值与与x x值值进行比较进行比较，直到找到数据域值为，直到找到数据域值为x x的的结点或到达单链表的表尾为止结点或到达单链表的表尾为止 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2

42、.3.2 单链表上基本操作的实现单链表上基本操作的实现1. 查找操作查找操作2)2)按按值值查找操作查找操作 indexOf(xindexOf(x）的实现的实现L211830754256pppX= 30 下面为操作下面为操作indexOf( )indexOf( )的动态演示过程：的动态演示过程：40pp2.3 线性表的链式存储及其实现线性表的链式存储及其实现按按值值查找操作查找操作 indexOf(x）的）的算法算法public int indexOf(Object x) /算法算法2.52.5结束结束Node p = head.getNext(); int j = 0;while (p !=

43、 null & !p.getData().equals(x) ) p = p.getNext(); +j; if (p ！= null) return j;else return -1时间复杂度：时间复杂度：O O（n)n)2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2.3.2 单链表上基本操作的实现单链表上基本操作的实现2. 插入操作插入操作insert(i,x)实现实现 在带头结点的单链表的第在带头结点的单链表的第i i个结点之前插个结点之前插入一个数据域值为入一个数据域值为x x的新结点，其中的新结点，其中 0in0in 。ai-1 有序对有序对 a 改变

44、为改变为 a 和和 xaiai-12.3 线性表的链式存储及其实现线性表的链式存储及其实现 a. a. 查找第查找第i i个结点的前驱结点个结点的前驱结点( (或确定待插入的位置或确定待插入的位置) ) b.b.产生新结点产生新结点S S c. c.修改链指针，将修改链指针，将S S插入到链表指定的位置插入到链表指定的位置 单链表上单链表上 插入操作算法的基本步骤：插入操作算法的基本步骤：Node s=new Node( x); p = head ; j = -1;while (p!=null & j i-1) p = p.getNext(); +j; s.setNext( p.get

45、Next(); p.setNext( s); xai-1aiai-1sp(能否改为能否改为:p=head.getNext(); j=0; )2.3 线性表的链式存储及其实现线性表的链式存储及其实现单链表上插入操作单链表上插入操作insert(i,x)的算法的算法public void insert (int i, Object x) throws Exception /算法算法2.62.6结束结束Node p = head; int j = -1;while (p != null & j i-1 | p = null) / i不合法 throw new Exception(插入位置不合

46、法); 时间复杂度：时间复杂度：O O（n)n)Node s = new Node(x); s.setNext(p.getNext(); p.setNext(s); 2.3 线性表的链式存储及其实现线性表的链式存储及其实现 在在不带表头结点不带表头结点的单链表上实现的单链表上实现插入操作的算法应该如何缩写？插入操作的算法应该如何缩写？思考思考2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2.3.2 单链表上基本操作的实现单链表上基本操作的实现3. 删除操作删除操作remove(i)实现实现 删除带头结点单链表中的第删除带头结点单链表中的第i i个结点，其个结点，其中中 0

47、in-10in-1。 有序对有序对 a 和和 改变为改变为a ai-1aiai+1ai-12.3 线性表的链式存储及其实现线性表的链式存储及其实现 a. a. 查找待删除结点的前驱结点查找待删除结点的前驱结点( (即第即第i-1i-1个结点）个结点） b.b.修改链指针，使待删结点从单链表中脱离出来修改链指针，使待删结点从单链表中脱离出来 单链表上删除操作算法的基本步骤：单链表上删除操作算法的基本步骤：p = head ; j = -1;while ( & j i-1) p = p.getNext(); +j; ai-1aiai+1ai-1p.setNext(p.getNext().g

48、etNext()p2.3 线性表的链式存储及其实现线性表的链式存储及其实现单链表上删除操作单链表上删除操作remove(i)的算法的算法public void remove(int i) throws Exception /算法算法2.62.6结束结束Node p = head; int j = -1;while (p.getNext()!= null & j i-1 | p.getNext() = null ) / i不合法 throw new Exception(“删除位置不合法); 时间复杂度：时间复杂度：O O（n)n) p.setNext(p.getNext().getNex

49、t(); 问：如果单链表不带头结点，问：如果单链表不带头结点，应如何修改此算法？应如何修改此算法？ 问：如果是删除带头结点的单问：如果是删除带头结点的单链表中值为链表中值为x x的结点，应如何修改此的结点，应如何修改此算法？算法？2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.2 2.3.2 单链表上基本操作的实现单链表上基本操作的实现4. 单链表的建立操作单链表的建立操作creat(n)的实现的实现如何从线性表得到单链表？如何从线性表得到单链表？ 链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一是一个

50、结点个结点“逐个插入逐个插入” ” 的过程。的过程。 方法：方法： 头插法头插法 尾插法尾插法2.3 线性表的链式存储及其实现线性表的链式存储及其实现方法一、方法一、头插法（逆位序法）头插法（逆位序法）操作步骤操作步骤当前链表是一个当前链表是一个“空表空表”；1 1、输入数据元素、输入数据元素an-1， 建立结点并插入在表头；建立结点并插入在表头；2 2、输入数据元素、输入数据元素an-2， 建立结点并插入在表头；建立结点并插入在表头；an-1an-1an-23 3、依次类推，直至插入、依次类推，直至插入a a0 0为止。为止。P47/算法算法2.9 头插法创建单链表每次都是将创头插法创建单链

51、表每次都是将创建的建的新结点插入到新结点插入到当前形成的单链表当前形成的单链表的的表头表头。 2.3 线性表的链式存储及其实现线性表的链式存储及其实现头插法创建单链表头插法创建单链表creat2(n)的算法的算法public void create2(int n) throws Exception /算法算法2.92.9结束结束Scanner sc = new Scanner(System.in); / 构造用于输入的对象 for (int j = 0; j n; j+) /从键盘读入n个数依次插入到表头insert(0, sc.next() ); 时间复杂度：时间复杂度：O O（n)n)2.

52、3 线性表的链式存储及其实现线性表的链式存储及其实现方法二、方法二、尾插法（顺序法）尾插法（顺序法）操作步骤操作步骤当前链表仍是一个当前链表仍是一个“空表空表”；1 1、输入数据元素、输入数据元素a0， 建立结点并插入在表尾；建立结点并插入在表尾；2 2、输入数据元素、输入数据元素a1， 建立结点并插入在表尾；建立结点并插入在表尾；3 3、依次类推，直至插入、依次类推，直至插入a an-1n-1为止。为止。P47/算法算法2.10 尾插法创建单链表每次都是将创尾插法创建单链表每次都是将创建的建的新结点插入到新结点插入到当前形成的单链表当前形成的单链表的的表尾表尾 。a0a0a12.3 线性表的

53、链式存储及其实现线性表的链式存储及其实现尾插法创建单链表尾插法创建单链表creat1(n)的算法的算法public void create1(int n) throws Exception /算法算法2.102.10结束结束Scanner sc = new Scanner(System.in); / 构造用于输入的对象 for (int j = 0; j n; j+) /从键盘读入n个数依次插入到表尾insert( length() , sc.next() ); 时间复杂度：时间复杂度：O O（n)n)2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.3 2.3.3 单链表的应用

54、举例单链表的应用举例【例【例1 1】编写程序实现：建立一个单链表，然编写程序实现：建立一个单链表，然后删除单链表中后删除单链表中“多余多余”的结点，即使操作的结点，即使操作之后的单链表中只留下不相同的结点，最后之后的单链表中只留下不相同的结点，最后输出删除后的单链表中所有结点。输出删除后的单链表中所有结点。 要删除单链表中相同的结点，只要从单链要删除单链表中相同的结点，只要从单链表的首结点开始依次将单链表中每一个结点与表的首结点开始依次将单链表中每一个结点与它后面的所有结点进行比较，若遇到相等的，它后面的所有结点进行比较，若遇到相等的，则将此结点从链表中删除。当对单链表中的每则将此结点从链表中

55、删除。当对单链表中的每一个结点都做完处理后，算法结束。一个结点都做完处理后，算法结束。2.3 线性表的链式存储及其实现线性表的链式存储及其实现2）程序代码）程序代码 （P49）public class Example2_4 public static void main(String args) throws Exception System.out.println(请输入单链表中的请输入单链表中的10个结点值：个结点值：); LinkList L = new LinkList(10, true); / 尾插法建链表尾插法建链表 System.out.println(删除重复结点前单链表中的各

56、个结点删除重复结点前单链表中的各个结点值为：值为：); L.display(); removeRepeatElem(L); / 删除单链表中删除单链表中多余多余的结点的结点 System.out.println(删除重复结点后单链表中的各个删除重复结点后单链表中的各个结点值为：结点值为：); L.display(); 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2）程序代码）程序代码 （P49）public class Example2_4 private static void removeRepeatElem(LinkList L) throws Exception Node

57、p = L.getHead().getNext(), q; / p/ p指向首结点指向首结点int order = L.indexOf(p.getData();q = p.getNext();while (q != null) / / 与与p p的所有后继结点进行比较的所有后继结点进行比较if (p.getData().equals(q.getData() elseL.remove(order + 1);+order;q = q.getNext();p = p.getNext();whilewhile (p != null) (p != null)/ / 从首结点向后查找，直到从首结点向后查找

58、，直到p p为空为空 2.3 线性表的链式存储及其实现线性表的链式存储及其实现2.3.3 2.3.3 单链表的应用举例单链表的应用举例【例【例2 2】编程实现将两个有序的单链表编程实现将两个有序的单链表LALA（含有（含有m m个结点）和个结点）和LBLB（含有（含有n n个结点）合并成一个新个结点）合并成一个新的有序的单链表的有序的单链表LALA，原有单链表，原有单链表LALA和和LBLB中的结中的结点都按数据域值以非递减排列。点都按数据域值以非递减排列。 a0 . am-1 LALB b0 . bn-1 Pa（初始位置）（初始位置）pb（初始位置）（初始位置）pc（初始位置）（初始位置）2

59、.3 线性表的链式存储及其实现线性表的链式存储及其实现 引进引进3 3个指针个指针pa,pbpa,pb和和pcpc，其中，其中pa,pbpa,pb分别指向分别指向LaLa和和LbLb表中当前待比较插入的表中当前待比较插入的结点，而结点，而pcpc指向指向LcLc表当前最后一个结点。表当前最后一个结点。 若若pa.getData()=pb.getData(),pa.getData()=pb.getData(),则将则将papa所指结点链接到所指结点链接到pcpc所指结点之后，所指结点之后，否则将否则将pbpb所指结点链接到所指结点链接到pcpc所指结点之所指结点之后。当其中一个表为空时，则只要将

60、另后。当其中一个表为空时，则只要将另一个表的剩余段链接在一个表的剩余段链接在pcpc所指的结点之所指的结点之后即可后即可. .2.3 线性表的链式存储及其实现线性表的链式存储及其实现1.置初值：置初值：2.当当pa和和pb皆为非空时，重复执行：皆为非空时，重复执行：否则，将否则，将pb所指结点插入到所指结点插入到pc 所指结之后，所指结之后，pc后移，后移，再再pb后移；后移；3.当当pa或或pb非空时，将非空时，将LA或或LB中的剩余段链接到中的剩余段链接到pc所指所指的结点之后的结点之后若若pa.getData()=pb.getData(),则将则将pa所指结点插入到所指结点插入到pc 所指结点之后，再所指结点之后，再pc后移，后移，pa后移；后移；pc