《数据结构》课程授课教案（讲稿）第二章 线性表 第三节 单链表

课程名称：数据结构第3周，第_3讲次摘要第二章线性表授课题目（章、节）第三节单链表【目的要求】通过本讲课程的学习，理解链式存储方式的特点，掌握结点类和单链表类的设计方法，通过对单链表的效率分析，进一步明确顺序表和单链表的优缺点。【重点】理解链式存储方式的特点，掌握单链表类的各种操作。【难点】单链表的插入和删除操作。内容【本讲课程的引入】上一次课程我们学习了顺序表，了解到顺序表在进行插入和删除操作时将要移动大量的数据元素，既然它存在着这样的不足，我们就需要寻找另外一种解决方法，这就是我们将要学习的线性表的另外一种存储方法一一链式存储，这种存储方式可以避免顺序存储带来的问题。而这一次课我们主要讲解线性表链式存储中最简单的一种一一单链表。【本讲课程的内容】2.3单链表链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为一个结点。链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。指针表示一个数据元素逻辑意义上的存储位置。在计算机中，不同的高级程序设计语言实现指针的方法不同。Java语言用对象引用来表示指针。通过把新创建对象赋值给一个对象引用，即是让该对象的引用表示（或指向）了所创建的对象。在本章以后的讨论中，一般我们用术语指针表示逻辑概念上的数据元素存储位置，用对象引用表示Java语言实现的指针。在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素序列，这样任意两个在逻辑上相邻的数据元素在物理存储位置上也必然是相邻的。但在链式存储结构中由于链式存储结构是初始为空链，每当有新的数据元素需要存储时，用户才将向系统动态申请的结点插入链中，而这些在不同时刻向系统动态申请的结点，一般情况下其存储位置并不连续。链式存储结构的线性表称为链表。根据结点构造链的方法不同，链表主要有单链表、单循环链表和循环双向链表三种。这样，一个数据元素集就可以用链式存储结构来存储。2.3.1单链表的结构单链表是构成链表的每个结点只有一个指向直接后继结点的指针。1单链表的表示方法单链表中每个结点的结构：指针域数据元素域或elementnext单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点

课程名称：数据结构 第 3 周，第 3 讲次 摘 要 授课题目（章、节） 第二章 线性表 第三节 单链表 【目的要求】通过本讲课程的学习，理解链式存储方式的特点，掌握结点类和单链表类的设计方法，通过对 单链表的效率分析，进一步明确顺序表和单链表的优缺点。 【重 点】 理解链式存储方式的特点，掌握单链表类的各种操作。 【难 点】 单链表的插入和删除操作。 内 容 【本讲课程的引入】上一次课程我们学习了顺序表，了解到顺序表在进行插入和删除操作时 将要移动大量的数据元素，既然它存在着这样的不足，我们就需要寻找另外一种解决方法， 这就是我们将要学习的线性表的另外一种存储方法——链式存储，这种存储方式可以避免顺 序存储带来的问题。而这一次课我们主要讲解线性表链式存储中最简单的一种——单链表。 【本讲课程的内容】 2.3 单链表 链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为一个结点。 链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接 起来。 指针表示一个数据元素逻辑意义上的存储位置。 在计算机中，不同的高级程序设计语言实现指针的方法不同。Java 语言用对象引用来表 示指针。通过把新创建对象赋值给一个对象引用，即是让该对象的引用表示（或指向）了所 创建的对象。在本章以后的讨论中，一般我们用术语指针表示逻辑概念上的数据元素存储位 置，用对象引用表示 Java 语言实现的指针。 在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素序列， 这样任意两个在逻辑上相邻的数据元素在物理存储位置上也必然是相邻的。但在链式存储结 构中由于链式存储结构是初始为空链，每当有新的数据元素需要存储时，用户才将向系统动 态申请的结点插入链中，而这些在不同时刻向系统动态申请的结点，一般情况下其存储位置 并不连续。 链式存储结构的线性表称为链表。 根据结点构造链的方法不同，链表主要有单链表、单循环链表和循环双向链表三种。这 样，一个数据元素集就可以用链式存储结构来存储。 2.3.1 单链表的结构 单链表是构成链表的每个结点只有一个指向直接后继结点的指针。 1 单链表的表示方法 单链表中每个结点的结构： 单链表有带头结点结构和不带头结点结构两种。 我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个 结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。 数据元素域 指针域 或 element next

讨论1.在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。讨论2.如何表示空表？不带头结点时，当头指针的值为空时表示空表：带头结点时，当头结点的指针域为空时表示空表。2带头结点单链表和不带头结点单链表的比较从线性表的定义可知，线性表要求允许在任意位置进行插入和删除。当选用带头结点的单链表时，插入和删除操作的实现方法比不用带头结点单链表的实现方法简单。设头指针用head表示，在单链表中任意结点（但不是第一个数据元素结点）前插入一个新结点的方法如下图所示。算法实现时，首先把插入位置定位在要插入结点的前一个结点位置，然后把s表示的新结点插入单链表中。head-Aobj要在第一个数据元素结点前插入一个新结点，若采用不带头结点的单链表结构，则结点插入后，头指针head就要等于新插入结点s，这和在非第一个数据元素结点前插入结点时的情况不同。另外，还有一些不同情况需要考虑。因此，算法对这两种情况就要分别设计实现方法。而如果采用带头结点的单链表结构，算法实现时，p指向头结点，改变的是p指针的next指针的值，而头指针head的值不变。因此，算法实现方法比较简单。在带头结点单链表中第一个数据元素结点前插入一个新结点的过程如下图所示。pdatanextheadaoAan-1(a)P★head一a。(b)2.3.2结点类单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）

讨论 1. 在链表中设置头结点有什么好处？ 头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放 表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首 元结点进行统一处理，编程更方便。 讨论 2. 如何表示空表？ 不带头结点时，当头指针的值为空时表示空表；带头结点时，当头结点的指针域为空时 表示空表。 2 带头结点单链表和不带头结点单链表的比较 从线性表的定义可知，线性表要求允许在任意位置进行插入和删除。当选用带头结点的 单链表时，插入和删除操作的实现方法比不用带头结点单链表的实现方法简单。 设头指针用 head 表示，在单链表中任意结点（但不是第一个数据元素结点）前插入一个 新结点的方法如下图所示。算法实现时，首先把插入位置定位在要插入结点的前一个结点位 置，然后把 s 表示的新结点插入单链表中。 0 head a . i a n−1 a ∧ s obj . i−1 a p data next 要在第一个数据元素结点前插入一个新结点，若采用不带头结点的单链表结构，则结点 插入后，头指针 head 就要等于新插入结点 s，这和在非第一个数据元素结点前插入结点时的 情况不同。另外，还有一些不同情况需要考虑。因此，算法对这两种情况就要分别设计实现 方法。 而如果采用带头结点的单链表结构，算法实现时，p 指向头结点，改变的是 p 指针的 next 指针的值，而头指针 head 的值不变。因此，算法实现方法比较简单。在带头结点单链表中第 一个数据元素结点前插入一个新结点的过程如下图所示。 2.3.2 结点类 单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点 类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。 head (b) . 0 a 1 a n−1 a ∧ s obj ∧ head . 0 a 1 a n−1 a ∧ obj (a) s data next p p

public class Nodel1/数据元素Object element;1表示下一个结点的对象引用Node next;1/用于头结点的构造函数1Node(Nodenextval)next = nextval;Node(Objectobj,Nodenextval)/用于其他结点的构造函数2element = obj;next = nextval;//取nextpublic NodegetNextOreturn next,/置nextpublic void setNext(Node nextval)next = nextval;//取elementpublic Object getElement()return element;3//置elementpublic void setElement(Object obj)element=obj;2.3.3单链表类单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个数。但是，如果再增加一个表示单链表当前结点位置的成员变量，则有些成员函数的设计将更加方便。publicclassLinListimplementsList(Node head;Node current:int size;LinListO(head = current = new Node(null);publicvoidindex(inti)throwsExceptionif(i size-l)throw newException("参数错误！")；1if(i == -1) return;current = head.next:

public class Node{ Object element; //数据元素 Node next; //表示下一个结点的对象引用 Node(Node nextval){ //用于头结点的构造函数 1 next = nextval; } Node(Object obj,Node nextval){ //用于其他结点的构造函数 2 element = obj; next = nextval; } public Node getNext(){ //取 next return next; } public void setNext(Node nextval){ //置 next next = nextval; } public Object getElement(){ //取 element return element; } public void setElement(Object obj){ //置 element element = obj; } } 2.3.3 单链表类 单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个 数。但是，如果再增加一个表示单链表当前结点位置的成员变量，则有些成员函数的设计将 更加方便。 public class LinList implements List { Node head; Node current; int size; LinList(){ head = current = new Node(null); } public void index(int i) throws Exception{ if(i size - 1){ throw new Exception("参数错误！"); } if(i == -1) return; current = head.next;

int j = O;while((current !=null)&& jsize){thrownewException("参数错误！");1index(i - 1) ;current.setNext(new Node(obj,current.next)):size ++:1public Objectdelete(int i)throws Exception(if(size == 0)(thrownewException（"链表已空无元素可删！"）；子if(isize-1)thrownewException（"参数错误！"）：1index(i - 1);Object obj = current.next.getElement O;current.next=current.next.next:size --;return obj:public int sizeO(return size;1public boolean isEmptyO(return size -- O:1public ObjectgetData(inti)throws Exceptiontif(isize-l){thrownewException("参数错误！"）：1index(i) :return current.getElementO;寻

int j = 0; while((current != null) && j size){ throw new Exception("参数错误！"); } index(i - 1); current.setNext(new Node(obj,current.next)); size ++; } public Object delete(int i) throws Exception{ if(size == 0){ throw new Exception("链表已空无元素可删！"); } if(i size - 1){ throw new Exception("参数错误！"); } index(i - 1); Object obj = current.next.getElement(); current.next=current.next.next; size -; return obj; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } public Object getData(int i) throws Exception{ if(i size - 1){ throw new Exception("参数错误！"); } index(i); return current.getElement(); } }

2.3.4单链表的效率分析在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：nZ(n-i)=nEi=Zp,(n-i)=2n+10i=0删除单链表的一个数据元素时比较数据元素的平均次数为：H1n-1Z(n-i)="Ea=q(n-i)=-2ni=0i=0因此，单链表插入和删除操作的时间复杂度均为0（n）。另外，单链表取数据元素操作的时间复杂度也为0（n)。2.3.55顺序表和单链表的比较顺序表的主要优点是支持随机读取，以及内存空间利用效率高：顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n)；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为0（1）。顺序表适于做查找这样的静态操作：链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2.3.6单链表应用举例例1：建立一个线性表，首先依次输入数据元素1,2,3，，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。public class LinListTest(public static void main(Stringargs[)tLinList linList =newLinListO;int n=10:try(for(inti=O:i<n;i++)tlinList.insert(i,newInteger(i+1l)):亨linList.delete(4):for(int i=O;i<linList.size;i++)System.out.print(linList.getData(i)+"");门1catch(Exception e)(System.out.println(e.getMessage (O);1

2.3.4 单链表的效率分析 在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比 较数据元素的平均次数为： 删除单链表的一个数据元素时比较数据元素的平均次数为： 因此，单链表插入和删除操作的时间复杂度均为 O（n）。另外，单链表取数据元素操作 的时间复杂度也为 O（n）。 2.3.5 顺序表和单链表的比较 顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需 要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过 了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。 和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链 表插入和删除操作时不需要移动数据元素。 单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表 的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为 O（n）；而顺序 表支持随机读取，顺序表取数据元素操作的时间复杂度为 O（1）。 顺序表适于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表 的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主 要操作是插入、删除操作，则采用链表。 2.3.6 单链表应用举例 例 1：建立一个线性表，首先依次输入数据元素 1,2,3,.,10，然后删除数据元素 5，最后依 次显示当前线性表中的数据元素。 public class LinListTest{ public static void main(String args[]){ LinList linList = new LinList(); int n = 10; try{ for(int i = 0; i < n; i++){ linList.insert(i,new Integer(i+1)); } linList.delete(4); for(int i = 0; i < linList.size; i++){ System.out.print(linList.getData(i)+" "); } } catch(Exception e){ System.out.println(e.getMessage()); } 0 0 1 ( ) ( ) 1 2 n n is i i i n E p n i n i = = n = − = − = +   1 1 0 0 1 1 ( ) ( ) 2 n n dl i i i n E q n i n i n − − = = − = − = − =  

宁例2：编写一个函数，要求把带头结点单链表A中的数据元素序列就地逆置。public void converse(Node head) (Node p,q;p = head, next;head. next = null;while(p!=null)(q = p;p = p.next;q.next = head.next;head.next = q;亨【本讲课程的小结】在这一讲中我们学习了单链表的各种操作，其中要重点掌握单链表的定位、插入和删除操作，另外比较了单链表和顺序表各自的优缺点，我们应该能够根据实际应用的特点适当的选择线性表的存储方式。【本讲课程的作业】编写删除函数，删除单链表中数据元素等于x的第一个结点。删除成功返回被删除元素的位置，删除不成功返回-1。要求该函数不设计在单链表类中，假设数据元素为int型变量

} } 例 2：编写一个函数，要求把带头结点单链表 A 中的数据元素序列就地逆置。 public void converse(Node head){ Node p,q; p = head.next; head.next = null; while(p != null){ q = p; p = p.next; q.next = head.next; head.next = q; } } 【本讲课程的小结】在这一讲中我们学习了单链表的各种操作，其中要重点掌握单链表的定 位、插入和删除操作，另外比较了单链表和顺序表各自的优缺点，我们应该能够根据实际应 用的特点适当的选择线性表的存储方式。 【本讲课程的作业】 编写删除函数，删除单链表中数据元素等于 x 的第一个结点。删除成功返回被删除元素的位 置，删除不成功返回-1。要求该函数不设计在单链表类中，假设数据元素为 int 型变量