第二章线性表

1、|第第1章章 绪论绪论 第第2章章 线性表线性表 |第第3章章 栈与队列栈与队列 |第第4章章 串串 |第第5章章 数组和广义表数组和广义表 |第第6章章 树和二叉树树和二叉树 |第第7章章 图图 |第第8章章 查找查找 |第第9章章 排序排序 |2.1 线性表的概念线性表的概念 |2.2 线性链表线性链表 n2.1.1 线性表的抽象数据类型线性表的抽象数据类型 n2.1.2 线性表的顺序存储结构线性表的顺序存储结构 n2.1.3 线性表的链式存储结构线性表的链式存储结构 唯一头元素唯一头元素 唯一尾元素唯一尾元素 除头元素外，均有一个直接前驱除头元素外，均有一个直接前驱 除尾元素外，均有一个

2、直接后继除尾元素外，均有一个直接后继 线性结构特点线性结构特点: OOOOO 线性线性 头头尾尾 1 2 3 4 5 书目信息、排队、算术表达式。书目信息、排队、算术表达式。 2.1 线性表的概念线性表的概念 1. 线性表的语言定义线性表的语言定义 线性表是线性表是n个数据元素的有限序列。个数据元素的有限序列。 例，例，英文字母表英文字母表 (A，B，C，Z) 线性表中的数据元素也可以由若干个数据项构成。线性表中的数据元素也可以由若干个数据项构成。 例，例，包含大量记录的登记表包含大量记录的登记表 姓名姓名学号学号性别性别年龄年龄班级班级 王晓林王晓林790631男男25计计90 陈红陈红79

3、0632女女24计计90 2. 线性表的形式定义线性表的形式定义 其中其中a1 1是头元素，是头元素， an是尾元素，是尾元素， ai是第是第 i 个元素。个元素。 ai-1 -1是 是ai的直接前驱，的直接前驱， ai是是ai-1 -1的直接后继。 的直接后继。 线性表可以表示为线性表可以表示为 n 个数据元素的有限序列个数据元素的有限序列: (a1 1，ai-1 -1， ，ai，an) 2.1.1 线性表的抽象数据类型线性表的抽象数据类型 1. 线性表的数据元素线性表的数据元素 线性表是由线性表是由n（n0）个相同类型的数据元素）个相同类型的数据元素a1， a2，an组成的有限序列，记作：

4、组成的有限序列，记作： LinearList=a1，a2，an 其中，其中，n表示线性表的元素个数，称为线性表的长表示线性表的元素个数，称为线性表的长 度。若度。若n=0，则称为空表。若，则称为空表。若n0，对于线性表中第，对于线性表中第 i个数据元素个数据元素ai，有且仅有一个直接前驱数据元素，有且仅有一个直接前驱数据元素ai-1 和一个直接后继数据元素和一个直接后继数据元素ai+1，而，而a1没有前驱数据元没有前驱数据元 素，素，an没有后继数据元素。没有后继数据元素。 z求长度求长度：求线性表的数据元素个数。：求线性表的数据元素个数。 z访问访问：对线性表中指定位置的数据元素进行存取、替

5、换等操：对线性表中指定位置的数据元素进行存取、替换等操 作。作。 z插入插入：在线性表指定位置上，插入一个新的数据元素，插入：在线性表指定位置上，插入一个新的数据元素，插入 后仍为一个线性表。后仍为一个线性表。 z删除删除：删除线性表指定位置的数据元素，同时保证更改后的：删除线性表指定位置的数据元素，同时保证更改后的 线性表仍然具有线性表的连续性。线性表仍然具有线性表的连续性。 z复制复制：重新复制一个线性表。：重新复制一个线性表。 z合并合并：将两个或两个以上的线性表合并起来，形成一个新的：将两个或两个以上的线性表合并起来，形成一个新的 线性表。线性表。 z查找查找：在线性表中查找满足某种条

6、件的数据元素。：在线性表中查找满足某种条件的数据元素。 z排序排序：对线性表中的数据元素按关键字值，以递增或递减的：对线性表中的数据元素按关键字值，以递增或递减的 次序进行排列。次序进行排列。 z遍历遍历：按次序访问线性表中的所有数据元素，并且每个数据：按次序访问线性表中的所有数据元素，并且每个数据 元素恰好访问一次。元素恰好访问一次。 线性表的抽象类线性表的抽象类 abstract public class LinearList /线性表的抽象类 abstract public int length(); /返回线性表的长度 abstract public boolean isEmpty()

7、; /判断线性表是否为空 abstract public boolean isFull(); /判断线性表是否已满 abstract public Object get(int i); /返回指定位置数据元素 abstract public Object set(int i,Object obj);/设置指定位置数据 元素 abstract public void insert(int i,Object obj); /将数据元素插入指 定位置 abstract public int indexof(Object obj); /返回给定数据元素首次 出现位置 abstract public bo

8、olean contains(Object obj); /查找是否包含给 定数据元素 abstract public void remove(int index); /删除指定位置的 数据元素 abstract public void remove(Object obj); /删除首次出现的 2.1.2 线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储结构线性表的顺序存储结构指的是用一组地址连续的存储单指的是用一组地址连续的存储单 元依次存储线性表的数据元素。元依次存储线性表的数据元素。 数据元素在内存的物理存储次序与它们在线性表中的逻数据元素在内存的物理存储次序与它们在线性表中的逻

9、 辑次序是一致的，即数据元素辑次序是一致的，即数据元素ai与其前驱数据元素与其前驱数据元素ai-1及及 后继数据元素后继数据元素ai+1的位置相邻。的位置相邻。 a1 a2 ai an b b+l b+(i-1-1)l b+(n-1-1)l b+nl 存储地址存储地址 内存状态内存状态 设每个元素需占用设每个元素需占用 l 个存储单元个存储单元 Loc(ai)表示元素表示元素ai的存储地址的存储地址 则则Loc(a1)是第一个数据元素是第一个数据元素a1的存储地的存储地 址，也是整个线性表的起始地址址，也是整个线性表的起始地址 Loc(ai+1) = Loc(ai) + l Loc(ai) =

10、 Loc(a1) + (i - - 1 1)l 以元素在计算机内的以元素在计算机内的“物理位置相邻物理位置相邻”来表示线性表来表示线性表 中数据元素之间的中数据元素之间的“逻辑关系相邻逻辑关系相邻”。 只要确定线性表的起始地址，线性表中的任意数据元只要确定线性表的起始地址，线性表中的任意数据元 素都可随意存取，故线性表的素都可随意存取，故线性表的顺序存储结构顺序存储结构又称为又称为随随 机存取存储结构机存取存储结构。 特点特点: 解：解：地址计算通式为：地址计算通式为： LOC(ai) = LOC(a1) + L *（i-1） 公式中公式中i=1,2,n n0元素序号元素序号 数组下标数组下标

11、i=0,1,i=0,1,9,9 因此：因此：LOC(M3) = LOC(M3) = 9898+ +5 5(3-(3-0 0) =) =113113 public class LinearList1 /线性表的顺序存储结构线性表的顺序存储结构 private int n; /记载顺序表的长度记载顺序表的长度 private int table; /数据元素所占有的存储空间数据元素所占有的存储空间 LinearList1类的一个对象表示一个线性表。当我们类的一个对象表示一个线性表。当我们 需要使用一个线性表时，创建需要使用一个线性表时，创建LinearList1类的一个对类的一个对 象，通过这个对

12、象调用公有的方法进行相应的操作。象，通过这个对象调用公有的方法进行相应的操作。 线性表的顺序存储结构的线性表的顺序存储结构的优点优点 可随机存取表中任意数据元素可随机存取表中任意数据元素 直接可获取线性表的长度直接可获取线性表的长度 例，例，tablei- -1表示第表示第 i 个数据元素个数据元素 例，例，L.length()表示线性表长度表示线性表长度 （1） 顺序表的初始化顺序表的初始化 public LinearList1(int n) /为顺序表分配为顺序表分配n个存储单元个存储单元 /此时顺序表长度此时顺序表长度this.n为为0 table=new int n;/所占用的存储单元

13、个数所占用的存储单元个数this.table.length等于等于n this.n=0; （2） 判断顺序表的空与满状态判断顺序表的空与满状态 public boolean isEmpty() /判断顺序表是否为空判断顺序表是否为空 return n=0; public boolean isFull() /判断顺序表是否已满判断顺序表是否已满 return n=table.length; /table.length返回数组长度返回数组长度 （3） 返回顺序表长度返回顺序表长度 public int length() /返回顺序表的长度返回顺序表的长度 return n; （4） 获得顺序表的第

14、获得顺序表的第i个数据元素值个数据元素值 public int get(int i) /返回第返回第i个元素值个元素值 if(i0 if(i=n+1) n+; （6） 查找查找 public boolean contains(int k)/查找线性表是否包含查找线性表是否包含k值值 /查找成功时返回查找成功时返回true，否则返回，否则返回false int j=indexof(k); if(j!=-1) return true; else return false; public int indexof(int k) /查找查找k值值 /查找成功时返回查找成功时返回k值首次出现位置，否则返回

15、值首次出现位置，否则返回-1 int j=0; while(j=0 else return -1; （7） 在顺序表的第在顺序表的第 i 个位置前插入一个新的元素个位置前插入一个新的元素 思想思想: 1. 找到第找到第 i 个元素的位置。个元素的位置。 3. 将新元素放置在第将新元素放置在第 i 个位置。个位置。 a1ai-1 -1 aian 例，在第例，在第 i 个元素前插入个元素前插入 b a1ai-1 -1 aian b 2. 将第将第 n 到到 i 个元素均向后移动一个位置。个元素均向后移动一个位置。 public void insert(int i,int k) /插入插入k值作为第

16、值作为第i个值。个值。 int j; if(!isFull() if(in) i=n+1; for(j=n-1;j=i-1;j-) tablej+1=tablej; / 后移元素后移元素 tablei-1=k; /插入新元素插入新元素 n+; else System.out.println(数组已满，无法插入数组已满，无法插入+k+值！值！); public void insert(int k) /添加添加k值到顺序表最后，重载值到顺序表最后，重载 insert(n+1,k); 例，例，在第在第4个元素之前插入元素个元素之前插入元素25。 45 12 9 33 69 5 1 2 3 4 5 6

17、 57 69 33 25 插入插入25 时间复时间复 杂度杂度 平均时间复杂度平均时间复杂度:O(n) （8） 删除顺序表的第删除顺序表的第 i 个数据元素个数据元素 思想思想: a1ai-1 -1 ai+1an a1ai-1 -1 ai+1an ai 1. 找到第找到第 i 个数据元素。个数据元素。 3. 将第将第 i+1 到到 n 个元素均向前移动一个位置。个元素均向前移动一个位置。 2. 取出第取出第 i 个数据元素。个数据元素。 public void remove(int k) /删除删除k值首次出现的数据元素值首次出现的数据元素 int i=indexof(k); /查找查找k值的

18、位置值的位置 if(i!=-1) for(int j=i;jn-1;j+) /删除第删除第i个值个值 tablej=tablej+1; /前移前移 tablen-1=0; n-; else System.out.println(k+值未找到，无法删除值未找到，无法删除!); 例，例，删除第删除第4个元素个元素25。 删除删除25 45 12 9 25 33 69 1 2 3 4 5 6 75 33 69 5 时间复时间复 杂度杂度 平均时间复杂度平均时间复杂度:O(n) 线性表的顺序存线性表的顺序存 储结构的储结构的缺点缺点 数据元素的数据元素的插入插入、 删除删除相对麻烦相对麻烦 例例2.1

19、 以顺序表求解约瑟夫环问题以顺序表求解约瑟夫环问题 约瑟夫环（约瑟夫环（Josephus）问题：古代某法官要判决）问题：古代某法官要判决n个犯个犯 人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈， 从第从第s个人开始数起，每数到第个人开始数起，每数到第d个犯人，就拉出来处决，个犯人，就拉出来处决， 然后再数然后再数d个，数到的人再处决个，数到的人再处决直到剩下的最后一个直到剩下的最后一个 可赦免。可赦免。 图图2.4 约瑟夫环问题执行过程约瑟夫环问题执行过程 n=5, s=1, d=2 算法描述如下：算法描述如下： | 建立一个具有建立一个具

20、有n个数据元素的线性表对象个数据元素的线性表对象ring1。 | 从第从第s个数据元素开始，依次计数，每数到个数据元素开始，依次计数，每数到d，就将该数据，就将该数据 元素设置为空。元素设置为空。 | 重复上一步，依次选中重复上一步，依次选中n-1个数据元素出环。个数据元素出环。 | 输出环中所剩的最后一个数据元素。输出环中所剩的最后一个数据元素。 从逻辑结构上看，该算法应该多次使用删除操作，即当从逻辑结构上看，该算法应该多次使用删除操作，即当 每次一个人出环时，删除线性表相应位置的数据元素，这时每次一个人出环时，删除线性表相应位置的数据元素，这时 必须移动其他元素。下面程序中，为减少数据移动

21、次数，没必须移动其他元素。下面程序中，为减少数据移动次数，没 有使用删除操作，采取的是一种变通办法，将相应位置的数有使用删除操作，采取的是一种变通办法，将相应位置的数 据元素值设为空，这就使得计数时必须跳过值为空的数据元据元素值设为空，这就使得计数时必须跳过值为空的数据元 素。素。 例例2.1 2.1 以顺序表求解约瑟夫环问题以顺序表求解约瑟夫环问题 运行运行 import ds_java.LinearList1;/声明引用ds_java包中的LinearList1类 public class Josephus1 public static void main(String args) (ne

22、w Josephus1().display(5,1,2); public void display(int N,int S,int D) final int NULL=0; LinearList1 ring1=new LinearList1(N); int i,j,k,m; for(i=1;i0) int k=(int)(Math.random()*100); /产生随机数产生随机数 head=new OnelinkNode(k); rear=head; /rear指向链表尾结点指向链表尾结点 for(int i=1;i ); System.out.println(); 设已建立一条单向链表，

23、现欲将各结点的设已建立一条单向链表，现欲将各结点的next链改为链改为 指向其前驱结点，使得单向链表逆转过来。指向其前驱结点，使得单向链表逆转过来。 设设p指向链表的某一结点，指向链表的某一结点，front和和q分别指向分别指向p的前驱的前驱 和后继结点，则使和后继结点，则使p.next指向其前驱结点的语句是：指向其前驱结点的语句是： p.next=front; 算法描述如下：算法描述如下： 第第1次循环时，次循环时，front=null，p指向链表的第一个结点，指向链表的第一个结点， 执行上述语句。执行上述语句。 1 2 4 head q 3 p front=null 以以p!=null为循

24、环条件，为循环条件，front、p和和q沿链表方向依次前沿链表方向依次前 进，对于进，对于p指向的每一个结点，执行上述语句。指向的每一个结点，执行上述语句。 1 2 4 head q 3 pfront q=p.next; p.next=front; front=p; p=q; 循环结束后，循环结束后，front指向原链表的最后一个结点，该结点指向原链表的最后一个结点，该结点 应成为新链表的第应成为新链表的第1个结点，由个结点，由head指向，语句为：指向，语句为： head=front; 1 2 4 head q=null 3 p=nullfront 运行运行 import ds_java.O

25、nelinkNode; import ds_java.Onelink1; public class Onelink2 extends Onelink1 /单向链表逆转 public Onelink2() /构造空的单向链表 super();/执行超类的构造方法 public Onelink2(int n) /以n个随机值建立单向链表 super(n); public void reverse() /将单向链表逆转 OnelinkNode p=this.head,q=null,front=null; while(p!=null) q=p.next; p.next=front; /p.next指向

26、p结点的前驱结点 线性表的链式存储结构的特点线性表的链式存储结构的特点 不可随机存取表中任意数据元素不可随机存取表中任意数据元素缺点缺点: 不可直接获取线性表的长度不可直接获取线性表的长度 算法算法: 取出线性单链表第取出线性单链表第 i 个元素。个元素。 思想思想: 1. 从头遍历找到第从头遍历找到第 i 个元素；个元素； 2. 取出元素；取出元素； a1ai an head public int get(int i) OnelinkNode p; int j=1; p=head; while(p!=null return p.data; /p指向第一个元素，指向第一个元素，j计数计数 头元

27、素头元素 例，例，取出第取出第i=3个元素。个元素。 p = head j = 1 p = p. .next j = 2 p = p. .next j = 3 e = p. .data = Sun 平均时间复杂度平均时间复杂度:O(n) ZhaoQianLiSun head 优点优点: 数据元素的数据元素的插入、删除插入、删除相对方便相对方便 在在b之前插入元素之前插入元素x : xs s. .next = p. .next p ab p. .next = s 1. 找到找到b结点的前驱结点结点的前驱结点 2. 构造将要插入的结点构造将要插入的结点 3. 指针变换指针变换 怎么做？怎么做？ 1

28、. p. .next = s 2. n空表插入空表插入 head=new OnelinkNode(1)； n头插入头插入 q=new OnelinkNode(2)； q.next=head； head=q； n尾插入尾插入 q=new OnelinkNode(3)； q.next=null； p.next=q； n中间插入中间插入 q=new OnelinkNode(4)； q.next=p.next； p.next=q； 运行运行 import ds_java.OnelinkNode; import ds_java.Onelink1; public class Onelink3 extend

29、s Onelink1 /单向链表插入排序 Onelink3() /建立空链表 super(); Onelink3(int n) /n个随机值插入单向链表 System.out.print(insert: ); for(int i=0;in;i+) int k=(int)(Math.random()*100); System.out.print(k+ ); insert(k); System.out.println(); 例，例，在第在第3个元素之前插入一个新元素。个元素之前插入一个新元素。 ZhaoQianLi head p = head j = 1 p = p.next j = 2 Sunq

30、 平均时间复杂度平均时间复杂度:O(n) 删除元素删除元素b : p p . .next = (p . .next) . .next 1. 找到找到b结点的前驱结点结点的前驱结点 2. 指针指针变换变换 怎么做？怎么做？ acb 图图2.11 单向链表删除结点单向链表删除结点 head=null; head=head.next; p.next=(p.next).next； 4 4两种存储结构性能的比较两种存储结构性能的比较 （1）直接访问元素的性能）直接访问元素的性能 （2）存储空间的利用）存储空间的利用 （3）存储密度）存储密度 （4）插入和删除操作）插入和删除操作 （5）查找和排序）查找和

31、排序 顺序表能够直接访问数据元素，顺序表能够直接访问数据元素， 只要给出数组的下标就可以引用只要给出数组的下标就可以引用 数组中的任何一个数据元素；链数组中的任何一个数据元素；链 式结构不能直接访问任意一个数式结构不能直接访问任意一个数 据元素，从链表的第一个结点开据元素，从链表的第一个结点开 始，依次查找后继结点。始，依次查找后继结点。 顺序表存在使用空间的浪费与溢顺序表存在使用空间的浪费与溢 出问题。顺序表进行插入删除时，出问题。顺序表进行插入删除时， 要判断顺序表是否为空，或是否要判断顺序表是否为空，或是否 为满。而链表只要判断是否为空为满。而链表只要判断是否为空 就可以了，每插入一个结

32、点，申就可以了，每插入一个结点，申 请一个存储单元。请一个存储单元。 顺序表的全部空间都用来存放数顺序表的全部空间都用来存放数 据元素，因此存储密度高；而链据元素，因此存储密度高；而链 表中每个结点都要包含其后继结表中每个结点都要包含其后继结 点的地址，因此存储密度较低。点的地址，因此存储密度较低。 顺序表的插入和删除操作很不方顺序表的插入和删除操作很不方 便，插入和删除有时需要移动大便，插入和删除有时需要移动大 量元素；而链表则容易进行插入量元素；而链表则容易进行插入 和删除操作，只要简单地改动相和删除操作，只要简单地改动相 关结点的链即可，不需移动元素关结点的链即可，不需移动元素 两者都可

33、以采用查找和排序的一些两者都可以采用查找和排序的一些 简单算法，包括顺序查找、插入排简单算法，包括顺序查找、插入排 序、选择排序等。此外，顺序表还序、选择排序等。此外，顺序表还 可以采用复杂查找和排序算法，包可以采用复杂查找和排序算法，包 括折半查找、快速排序、堆排序等括折半查找、快速排序、堆排序等 作业作业: 1. 设计算法，删除单向链表中给定位置的结点。要设计算法，删除单向链表中给定位置的结点。要 求分三种情况讨论。求分三种情况讨论。 2. 设计算法，将单链表中的第设计算法，将单链表中的第 i 个结点和其后继结个结点和其后继结 点交换位置，要求只修改指针。点交换位置，要求只修改指针。 表中

34、最后一个结点的链设置为指向链表的第一个结点，表中最后一个结点的链设置为指向链表的第一个结点， 则该链表成为环状，称为单向循环链表。则该链表成为环状，称为单向循环链表。 a1 anhead 单结点的循环链表单结点的循环链表: head 1 从表的任意结点出发均可以找到表中的任意其他结点。从表的任意结点出发均可以找到表中的任意其他结点。 优点优点: 从某个结点出发寻找直接前驱从某个结点出发寻找直接前驱? 从某个结点出发寻找直接后继从某个结点出发寻找直接后继? 空表：空表： head=null 操作与线性单链表基本一致，差别只是在于算法中操作与线性单链表基本一致，差别只是在于算法中 的循环结束条件不

35、是的循环结束条件不是p是否为空是否为空，而是，而是p是否等于头指针是否等于头指针。 为了对循环链表进行操作，必须定义一个首次访问为了对循环链表进行操作，必须定义一个首次访问 的结点，习惯上仍用的结点，习惯上仍用head指向。设尾指针指向。设尾指针rear指向循环指向循环 链表的最后一个结点（相对于链表的最后一个结点（相对于head而言），则有而言），则有 rear.next=head; 在循环链表中寻找结点的在循环链表中寻找结点的直接后继直接后继很简单，只需要很简单，只需要O(1)； 但要寻找结点的但要寻找结点的直接前趋直接前趋需要循环一遍，需要需要循环一遍，需要O(n)。 2.2.3 双向链

36、表双向链表 双向链表的结点有双向链表的结点有两个指针域两个指针域: 一个指向直接后继，一个一个指向直接后继，一个 指向直接前趋。指向直接前趋。 priordatanext 1 head 234 prear a. 结点结构结点结构 b. 双向链表双向链表 package ds_java; public class TwolinkNode /双向链表的结点类双向链表的结点类 public int data; /存放结点值存放结点值 public TwolinkNode prior,next; /前驱、后继结点的引用前驱、后继结点的引用 public TwolinkNode(int k) /构造值为

37、构造值为k的结点的结点 data=k; prior=next=null; public TwolinkNode() /构造方法，重载构造方法，重载 this(0); import ds_java.TwolinkNode; /引用双向链表的结点类引用双向链表的结点类 public class Twolink1 /双向链表类双向链表类 protected TwolinkNode head; public Twolink1() /构造空的双链表构造空的双链表 head=null; /指向链表的第一个结点指向链表的第一个结点 设设rear指向双向链表的最后一个结点，由于线性表的第指向双向链表的最后一个

38、结点，由于线性表的第 一个数据元素没有前驱数据元素，最后一个数据元素没有一个数据元素没有前驱数据元素，最后一个数据元素没有 后继数据元素，所以有：后继数据元素，所以有： 说明说明 head.prior=null rear.next=null 再设再设p指向双向链表中的某一个结点（除首结点和最后指向双向链表中的某一个结点（除首结点和最后 一个结点），则双向链表的本质特征如下：一个结点），则双向链表的本质特征如下： (p.prior).next=p (p.next).prior=p 操作操作: 插入、删除插入、删除操作将会处理两个方向。操作将会处理两个方向。 1）判断双向链表是否为空）判断双向链表

39、是否为空 public boolean isEmpty() /判断双向链表是否为空判断双向链表是否为空 return head=null； 双向链表的其他基本操作与单向链表类似，在此不重复双向链表的其他基本操作与单向链表类似，在此不重复 讨论。讨论。 |根据插入位置的不同，分根据插入位置的不同，分3种情况讨论：种情况讨论： 空表插入。假定原链表为空（空表插入。假定原链表为空（head=nullhead=null），插入结），插入结 点后，链表只有一个结点，由点后，链表只有一个结点，由headhead指向。语句如下：指向。语句如下： head=new TwolinkNode(1); 头插入。在非

40、空链表的第一个结点之前插入头插入。在非空链表的第一个结点之前插入q q结点，结点， 插入后插入后q q结点作为链表的第一个结点，由结点作为链表的第一个结点，由headhead指向。语指向。语 句如下：句如下： 1 head 1 head 2 q head q=new TwolinkNode(2); q.next=head; head.prior=q; head=q; 中间（尾）插入中间（尾）插入 AB X q p 1. 找到要在之前插入的结点，找到要在之前插入的结点，p记录。记录。 2. q. .prior = p. .prior ； 3. (p. .prior). .next = q ； 4

41、. q. .next = p ； 5. p. .prior = q ； |在非空链表的在非空链表的p结点之后插入结点之后插入q结点，形成新的链表。结点，形成新的链表。 语句如下：语句如下： 中间（尾）插入中间（尾）插入 q=new TwolinkNode(3); q.prior=p; q.next=p.next; (p.next).prior=q; p.next=q; AB X q p 插入前，当插入前，当p指向最后一个结点时，指向最后一个结点时，p.next=null， 因此尾插入是中间插入的特例。因此尾插入是中间插入的特例。 删除单结点链表，只要使链表的引用删除单结点链表，只要使链表的引用

42、headhead为空即可。为空即可。 语句如下：语句如下： head=null; head=null; 删除链表第删除链表第1 1个结点，将个结点，将headhead指向链表第指向链表第1 1个结点的后个结点的后 继结点，并设置继结点，并设置headhead指向结点的指向结点的priorprior链为空值。语句链为空值。语句 如下：如下： head=head.next; head=head.next; head.prior=null; head.prior=null; 删除链表中间（尾）结点删除链表中间（尾）结点 ACB 1. 找到要删除的结点，找到要删除的结点，p记录。记录。 p 2. (p

43、. .prior).next = p. .next ； 3. (p. .next).).prior = p. .prior ； 在双向链表中可以沿在双向链表中可以沿priorprior和和nextnext移动，这使得查移动，这使得查 找操作很方便。找操作很方便。 假设某双向链表的结点值是按递增次序排列的，假设某双向链表的结点值是按递增次序排列的， 查找给定值查找给定值k k的过程为：的过程为： 从双向链表中的任何一个结点从双向链表中的任何一个结点p开始，如果结点开始，如果结点p 的值等于的值等于k，则查找成功。如果结点，则查找成功。如果结点p的值小于的值小于k，则，则p 向前移动；否则向前移动

44、；否则p向后移动，直至找到向后移动，直至找到k值；或走到链值；或走到链 表两端时仍未找到表两端时仍未找到k值，查找不成功。值，查找不成功。 双向链表中，如果最后一个结点双向链表中，如果最后一个结点rear的的next链指向链表的第链指向链表的第 1个结点个结点head，而链表第，而链表第1个结点个结点head的的prior链指向最后一个结链指向最后一个结 点，便形成双向循环链表，此时有下式成立：点，便形成双向循环链表，此时有下式成立： rear.next=head且且head.prior=rear 当当head=null时，为空链表。时，为空链表。 当当head.next=head且且head.prior=head时，为单结点链表。时，为单结点链表。 双向循环链表的查找、插入和删除操作类似双向链表。双向循环链表的查找、插入和删除操作类似双向链表。 顺序存储时，相邻数据元素的存放地址也相邻顺序存储时，相邻数据元素的存放地址也相邻( (逻辑与逻辑与 物理统一物理统一) )；要求内存中可用存储单元的地址必须是连续的。；要求内存中可用存储单元的地址必须是连续的。