数据结构 第二章教学课件 .ppt

《数据结构 第二章教学课件 .ppt》由会员分享，可在线阅读，更多相关《数据结构 第二章教学课件 .ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构 第二章教学课件 第二章第二章 线性表线性表数据结构数据结构目目录录第二章第二章第二章第二章线性表线性表线性表线性表4 41 12 23 3 线性表的逻辑结构线性表的逻辑结构线性表的顺序表示和实现线性表的顺序表示和实现线性表的链式表示和实现线性表的链式表示和实现小结小结总总体要求体要求掌握掌握线性表的逻辑结构及两种不同的存储结构；线性表的逻辑结构及两种不同的存储结构；掌握掌握两类存储结构（顺序和链式存储结构）的表示两类存储结构（顺序和链式存储结构）的表示方法，以及单链表、循环链表、双向链表的特点；方法，以及单链表、循环链表、双向链表的特点；掌握掌握线性表在顺序存储结构及链式存储结构上实

2、现线性表在顺序存储结构及链式存储结构上实现基本操作（查找、插入、删除、等）的算法及分析；基本操作（查找、插入、删除、等）的算法及分析；能够针对具体应用问题的要求和性质，选择合适的能够针对具体应用问题的要求和性质，选择合适的存储结构设计出有效算法，解决与线性表相关的实际存储结构设计出有效算法，解决与线性表相关的实际问题；问题；2.1 线线性表的性表的逻辑结逻辑结构构 线性表（线性表（Linear ListLinear List）是是n n个数据元素的有限个数据元素的有限序列，可表示为：序列，可表示为：（a1,a2,an）。u2.1.1 线性表的概念线性表的概念a ai i 是表中数据元素是表中数

3、据元素是表中数据元素是表中数据元素 称称 i 为为 ai 在线性表中的在线性表中的位序位序。称称 n 为线性表的为线性表的表长表长;称称 n=0 时的线性表为时的线性表为空表空表。例例1、26个大写英文字母组成的字母表个大写英文字母组成的字母表 (A,B,Z)例例2、某学校从、某学校从2000年开始拥有的职工数目年开始拥有的职工数目(48，64，77，93，112，136，167，235)该线性表的数据元该线性表的数据元素是一个字母素是一个字母该线性表的数据元该线性表的数据元素是一个正整数素是一个正整数例例3、图书信息表、图书信息表该线性表的数据元素是该线性表的数据元素是一本图书的基本信息一本

4、图书的基本信息线线性表的特点性表的特点a1a2a3a4a5a61 1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2 2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素”3 3除最后元素之外，均有除最后元素之外，均有 唯一的后继唯一的后继；4 4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。初始化初始化：构造一个空的线性表。：构造一个空的线性表。销毁销毁：销毁一个已存在的线性表。：销毁一个已存在的线性表。插入插入：第：第i i个位置之前插入一个新元素。个位置之前插入一个新元素。删除删除：删除线性表中的第：删除线性表中的第i i个数据元素。个

5、数据元素。更新更新：更新第：更新第i i个数据元素。个数据元素。查找查找：找出线性表中满足特定条件的元素的位置：找出线性表中满足特定条件的元素的位置获取获取：取线性表中的第：取线性表中的第i i个数据元素个数据元素判空判空：判断当前线性表是否为空：判断当前线性表是否为空求长度求长度：求出线性表中数据元素的个数：求出线性表中数据元素的个数正序遍历正序遍历：依次访问线性表中每个元素并输出：依次访问线性表中每个元素并输出u2.1.2 线性表的基本操作线性表的基本操作引引用用型型加加工工型型u2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 线性表的顺序表示线性表的顺序表示 线性表的顺序

6、表示指的是用一组线性表的顺序表示指的是用一组地址连续的存地址连续的存储单元储单元依次存储线性表的数据元素。通常称这种存依次存储线性表的数据元素。通常称这种存储结构的线性表为储结构的线性表为顺序表顺序表。LOC(ai)=LOC(a1)+(i-1)L每个元素需占每个元素需占用用L L个存储单元个存储单元2.2.2 顺序表的实现顺序表的实现顺序存储结构线性表泛型类的定义如下：顺序存储结构线性表泛型类的定义如下：public class sequenceListfinal int maxSize=10;private T listArray;private int length;public sequ

7、enceList()public sequenceList(int n)public boolean add(T obj,int pos)public T delete(int pos)public int find(T obj)public T value(int pos)./此处省略部分成员方法此处省略部分成员方法 顺序表中一维数组顺序表中一维数组的初始长度的初始长度存储元素的数组对象存储元素的数组对象保存顺序表的当前长度保存顺序表的当前长度【算法算法2-2-1】顺序表的初始化顺序表的初始化无参构造方法无参构造方法public sequenceList()length=0;/线性表初始为空

8、线性表初始为空listArray=(T)new ObjectmaxSize;由于不能实例化一个泛型对由于不能实例化一个泛型对象，所以在构造器中可以先象，所以在构造器中可以先实例化一个实例化一个ObjectObject数组，然数组，然后把它转换为一个泛型数组。后把它转换为一个泛型数组。有参构造方法有参构造方法public sequenceList(int n)if(n=0)System.out.println(error);System.exit(1);length=0;/线性表初始为空线性表初始为空 listArray=(T)new Objectn;顺序表的插入顺序表的插入O(n)【算法算法2

9、-2-2】顺序表的插入顺序表的插入public boolean add(T obj,int pos)if(poslength+1)System.out.println(pos值不合法值不合法);return false;.如果顺序表数组空间已经存满，见下一页如果顺序表数组空间已经存满，见下一页 for(int i=length;i=pos;i-)listArrayi=listArrayi-1;listArraypos-1=obj;length+;return true;将插入位置之后的数据元素将插入位置之后的数据元素组，按照从后到前的次序依组，按照从后到前的次序依次后移一个位置。次后移一个位置

10、。/如果顺序表数组空间已经存满，如果顺序表数组空间已经存满，重新分配存储空间重新分配存储空间if(length=listArray.length)T p=(T)new Objectlength*2;for(int i=0;ilength;i+)pi=listArrayi;listArray=p;把原数组中的元素复把原数组中的元素复制到新的存储空间制到新的存储空间更改更改listArray所所引用的地址引用的地址顺序表的删除顺序表的删除O(n)删除删除顺序表顺序表一个数据元素，平均约移动表一个数据元素，平均约移动表中一半元素中一半元素，时间复杂度为，时间复杂度为【算法算法2-2-3】顺序表的删除

11、顺序表的删除public T remove(int pos).顺序表为空顺序表为空/删除位置不合法均无法执行删除位置不合法均无法执行 T x=listArraypos-1;for(int i=pos;i=length;i+)listArrayi-1=listArrayi;length-;return x;将删除位置之后的数据元将删除位置之后的数据元素组，按照从前到后的次素组，按照从前到后的次序依次前移一个位置。序依次前移一个位置。【算法算法2-2-4】顺序表的查找顺序表的查找public int find(T obj)if(isEmpty()System.out.println(顺序表为空顺序

12、表为空);return-1;elsefor(int i=0;ilength;i+)if(listArrayi.equals(obj)return i+1;return-1;【算法算法2-2-5】顺序表的获取元素顺序表的获取元素public T value(int pos)if(isEmpty()System.out.println(顺序表为空顺序表为空);return null;else if(poslength)System.out.println(pos值不合法值不合法);return null;return listArraypos-1;【算法算法2-2-6】顺序表的更新元素顺序表的更新

13、元素public boolean modify(T obj,int pos)if(isEmpty()System.out.println(顺序表为空顺序表为空);return false;else if(poslength)System.out.println(error);return false;listArraypos-1=obj;return true;【算法算法2-2-7】顺序表的判空顺序表的判空public boolean isEmpty()return length=0;【算法算法2-2-8】顺序表求长度顺序表求长度public int size()return length;【

14、算法算法2-2-9】顺序表正序输出顺序表正序输出public void nextOrder()for(int i=0;ilength;i+)System.out.println(listArrayi);u2.2.3 顺序表的应用顺序表的应用【例例2-1】有顺序表有顺序表LA和和LB，其元素均按从小到大的，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表升序排列，编写一个算法将它们合并成一个顺序表LC，要求，要求LC的元素也是从小到大的升序排列。的元素也是从小到大的升序排列。算法思路：算法思路：依次扫描依次扫描LA和和LB的元素，比较线性表的元素，比较线性表LA和和LB当前元素的

15、值，将较小值的元素赋给当前元素的值，将较小值的元素赋给LC，如此直到一个线性表扫描完毕，然后将未完的那个如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给顺序表中余下部分赋给LC即可。因此线性表即可。因此线性表LC的的容量应不小于线性表容量应不小于线性表LA和和LB长度之和。长度之和。2.3 线线性表的性表的链链式表示和式表示和实现实现u2.3.1 线性表的链式表示线性表的链式表示 线性表的线性表的链式存储链式存储结构是用一组结构是用一组任意的存储单任意的存储单元元来存放线性表的数据元素，来存放线性表的数据元素，这组存储单元可以是这组存储单元可以是连续的，也可以是不连续的。连续的

16、，也可以是不连续的。图图2.6 单链表结点结构单链表结点结构结点结点对每个数据元素对每个数据元素a ai i，除了存储其本身的信息之外，除了存储其本身的信息之外，还需存储一个指示其直接后继存放位置的指针。还需存储一个指示其直接后继存放位置的指针。结点类的泛型定义如下：结点类的泛型定义如下：public class Node T data;Node next;public Node(Node n)next=n;public Node(T obj,Node n)data=obj;next=n;public T getData()return data;public Node getNext()re

17、turn next;两个参数的两个参数的构造方法构造方法一个参数的一个参数的构造方法构造方法u2.3.2 单链表的实现单链表的实现图图2.7 2.7 单链表示意图单链表示意图头指针头指针头结点头结点public class linkList private Node head;private int length;public linkList()public Node getHead()public boolean add(T obj,int pos)public T remove(int pos)public T value(int pos)./此处省略部分成员方法此处省略部分成员方法 存

18、放单链表的长度存放单链表的长度【算法算法2-3-1】单链表的初始化单链表的初始化public linkList()length=0;head=new Node(null);【算法算法2-3-2】获取单链表头结点的地址获取单链表头结点的地址public Node getHead()return head;单链表的插入单链表的插入【算法算法2-3-3】单链表的插入单链表的插入public boolean add(T obj,int pos)if(poslength+1)System.out.println(pos值不合法值不合法);return false;int num=1;Node p=hea

19、d,q=head.next;while(numpos)p=q;q=q.next;num+;p.next=new Node(obj,q);length+;return true;【算法算法2-3-4】单链表的删除单链表的删除图图2.10 删除删除q所引用结点所引用结点public T delete(int pos)若链表为空无法执行删除操作若链表为空无法执行删除操作 若参数若参数pos取值范围不合法无法执行删除取值范围不合法无法执行删除int num=1;Node p=head,q=head.next;while(numpos)p=q;q=q.next;num+;p.next=q.next;le

20、ngth-;return q.data;【算法算法2-3-5】单链表的查找单链表的查找public int find(T obj).若链表为空返回若链表为空返回-1int num=1;Node p=head.next;while(p!=null)/单链表的判空条件单链表的判空条件if(p.data.equals(obj)=false)p=p.next;num+;else break;if(p=null)return-1;return num;【算法算法2-3-6】获取单链表第获取单链表第pos个结点的值个结点的值public T value(int pos).如果链表为空返回如果链表为空返回n

21、ullif(poslength+1)System.out.println(pos值不合法值不合法);return null;int num=1;Node q=head.next;while(numpos)q=q.next;num+;return q.data;【算法算法2-3-7】更新单链表第更新单链表第pos个结点的值个结点的值public boolean modify(T obj,int pos).如果链表为空返回如果链表为空返回falseif(poslength+1)System.out.println(pos值不合法值不合法);return false;int num=1;Node q

22、=head.next;while(numpos)q=q.next;num+;q.data=obj;return true;u2.3.3 循环链表循环链表（a a）单循环链表非空表）单循环链表非空表（b b）单循环链表空表）单循环链表空表 循环链表是另一种形式的链表，它的特点是循环链表是另一种形式的链表，它的特点是表中最后一个结点的指针域不再为空，而是指向表中最后一个结点的指针域不再为空，而是指向表头结点，整个链表形成一个环。表头结点，整个链表形成一个环。从表中任一结点从表中任一结点出发均可找到链出发均可找到链表中其它结点表中其它结点u2.3.4 双向链表双向链表图图2.14 双向链表的结点结构

23、双向链表的结点结构指向前驱结点指向前驱结点指向后继结点指向后继结点public class DuNode T data;DuNode prior;DuNode next;public DuNode(DuNode n)next=n;prior=null;public DuNode(T obj,DuNode n,DuNode p)data=obj;next=n;（a）非空的双向循环链表）非空的双向循环链表（b）空的双向循环链表）空的双向循环链表在双向链表中，若变量在双向链表中，若变量p引用某个结点，则显引用某个结点，则显然有：然有：p.next.prior=p.prior.next=p1.双向链表

24、中结点的插入双向链表中结点的插入 s.prior=p.prior;p.prior.next=s;s.next=p;p.prior=s;2.双向链表中结点的删除双向链表中结点的删除 p.prior.next=p.next;p.next.prior=p.prior;u2.3.5（单）链表的应用（单）链表的应用【例例2-2】将两个有序链表】将两个有序链表La和和Lb合并为一个有序链表合并为一个有序链表算法思路：算法思路：1）设立设立3个指针个指针pa、pb和和pc，其中，其中pa和和pb分别指向分别指向La和和Lb中当前待比较插入的结点，而中当前待比较插入的结点，而pc指向指向Lc表中当前最后一个结

25、点，若表中当前最后一个结点，若pa.datapb.data，则将，则将pa所指结点链接到所指结点链接到pc所指结点之后，否则将所指结点之后，否则将pb所指结点链接到所指结点链接到pc所指结点之后。所指结点之后。2）当其中一个为空时，说明有一个表的元素已归并当其中一个为空时，说明有一个表的元素已归并完，则只需要将另一个表的剩余段链接在完，则只需要将另一个表的剩余段链接在pc所指结所指结点之后即可。点之后即可。【例例2-3】一元多项式相加一元多项式相加可将一元可将一元n项式写为以下形式：项式写为以下形式：其中其中pi是指数为是指数为ei的项的非零系数，且满足的项的非零系数，且满足0e1e2emn若

26、用一个长度为若用一个长度为m且每个元素有两个数据项（系且每个元素有两个数据项（系数项和指数项）的线性表数项和指数项）的线性表(p1,e1),(p2,e2),(pm,em)便可唯一确定多项式便可唯一确定多项式Pn(x)。图图2.19 多项式的单链表表示多项式的单链表表示图图2.20 多项式相加得到的和多项式多项式相加得到的和多项式 图图2.20为两个多项式相加的结果，相加后原来为两个多项式相加的结果，相加后原来的两个多项式链表仍然存在，而的两个多项式链表仍然存在，而“和多项式和多项式”中的结中的结点重新分配空间。点重新分配空间。本章小结本章小结 答：线性表逻辑结构特点：只有一个首结点和尾结点；除

27、首尾答：线性表逻辑结构特点：只有一个首结点和尾结点；除首尾 结点外其他结点只有一个直接前驱和一个直接后继。简言结点外其他结点只有一个直接前驱和一个直接后继。简言 之，线性结构的逻辑关系是之，线性结构的逻辑关系是一对一一对一一对一一对一（1:11:1）的。的。问：线性表的逻辑结构特点是什么？问：线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？其顺序存储结构和链式存储结构的特点是什么？顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物 理统一）；要求内存中可用存储单元的地址必须连续。理统一）；要求内存中可用存储单元的地址必须连

28、续。链式存储时，数据元素可随意存放，但所占存储空间分两链式存储时，数据元素可随意存放，但所占存储空间分两 部分，一部分存放结点值，另一部分存放表示结点间关系部分，一部分存放结点值，另一部分存放表示结点间关系 的指针。的指针。答：顺序存储：答：顺序存储：优点：存储密度大，存储空间利用率高，可优点：存储密度大，存储空间利用率高，可随机存取随机存取。缺点：缺点：插入或删除插入或删除插入或删除插入或删除元素时元素时不方便不方便不方便不方便。链式存储：链式存储：优点：优点：插入或删除插入或删除元素时很元素时很方便方便，使用灵活。，使用灵活。结点空间结点空间可以可以动态申请和释放动态申请和释放；缺点：存储

29、密度小，存储空间利用率低，缺点：存储密度小，存储空间利用率低，非随机存取非随机存取非随机存取非随机存取。事实上，链表插入、删除运算的事实上，链表插入、删除运算的 快捷是以空间代价来换取时间。快捷是以空间代价来换取时间。问：顺序存储和链式存储各有哪些优缺点？问：顺序存储和链式存储各有哪些优缺点？问：在什么情况下用顺序表比链表好？问：在什么情况下用顺序表比链表好？答：顺序表适宜于做答：顺序表适宜于做查找查找查找查找这样的静态操作；这样的静态操作；链表宜于做链表宜于做插入、删除插入、删除插入、删除插入、删除这样的动态操作。这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。删除操作，则采用链表。