数据结构叶核亚线性表幻灯片.ppt
数据结构叶核亚线性数据结构叶核亚线性表表数据结构（Java版）（第2版）第1页，共25页，编辑于2022年，星期六数据结构（Java版）（第2版）第第2章章 线性表线性表2.1 线性表的抽象数据类型线性表的抽象数据类型2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现 目的：目的：实现线性表抽象数据类型。实现线性表抽象数据类型。要求：要求：掌握两种存储结构实现线性表。掌握两种存储结构实现线性表。重点：重点：顺序表类，单链表类。顺序表类，单链表类。难点：难点：单链表，双链表。单链表，双链表。第2页，共25页，编辑于2022年，星期六2.1 线性表的抽象数据类型线性表的抽象数据类型LinearList=(a0，a1，an1)public interface LList /线性表接口 boolean isEmpty();/判断线性表是否为空 int length();/返回线性表长度 E get(int index);/返回序号为index的对象 E set(int index,E element);/设置序号为index对象为 boolean add(int index,E element);/在index处插入element对象 boolean add(E element);/在顺序表最后插入element对象 E remove(int index);/移去序号为index的对象并返回 void clear();/清空线性表第3页，共25页，编辑于2022年，星期六2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序存储结构线性表的顺序存储结构 第4页，共25页，编辑于2022年，星期六2.顺序表的插入和删除操作顺序表的插入和删除操作 第5页，共25页，编辑于2022年，星期六public class SeqList implements LList /顺序表类，实现线性表接口顺序表类，实现线性表接口 private Object table;/对象数组，私有成员对象数组，私有成员 private int n;/顺序表长度顺序表长度顺序表操作的效率分析顺序表操作的效率分析 如果在各位置插入元素的概率相同，则有如果在各位置插入元素的概率相同，则有3.顺序表类顺序表类第6页，共25页，编辑于2022年，星期六【例例2.1】使用顺序表类求解约瑟夫环问题。使用顺序表类求解约瑟夫环问题。第7页，共25页，编辑于2022年，星期六2.3 线性表的链式表示和实现线性表的链式表示和实现n2.3.1 线性表的链式存储结构线性表的链式存储结构n2.3.2 单链表单链表n2.3.3 双链表双链表第8页，共25页，编辑于2022年，星期六2.3.1 线性表的链式存储结构线性表的链式存储结构第9页，共25页，编辑于2022年，星期六单链表结点类单链表结点类 public class Node /单链表结点类单链表结点类 public E data;/数据域，保存数据元素数据域，保存数据元素 public Node next;/地址域，引用后继结点地址域，引用后继结点Node p,q;p=new Node(A);q=new Node(B);p.next=q;2.3.2 单链表单链表第10页，共25页，编辑于2022年，星期六2.单链表的遍历操作单链表的遍历操作 Node p=head;while(p!=null)访问访问p结点结点;p=p.next;第11页，共25页，编辑于2022年，星期六3.单链表的插入操作单链表的插入操作 第12页，共25页，编辑于2022年，星期六4.单链表的删除操作单链表的删除操作 头删除头删除head=head.next;中间中间/尾删除尾删除if(p.next!=null)p.next=p.next.next;第13页，共25页，编辑于2022年，星期六5.单链表类单链表类 public class SinglyLinkedList implements LList /单链表类，实现线性表接口单链表类，实现线性表接口 protected Node head;/头指针头指针 public SinglyLinkedList()/构造空单链表构造空单链表 this.head=null;（P59）单链表操作的效率分析单链表操作的效率分析 第14页，共25页，编辑于2022年，星期六【例例2.2】采用单链表求解约瑟夫环问题。采用单链表求解约瑟夫环问题。第15页，共25页，编辑于2022年，星期六7.单链表是递归结构单链表是递归结构 public String toString()return(+this.toString(this.head)+);public String toString(Node p)/递归算法递归算法 if(p!=null)return p.data.toString()+,+this.toString(p.next);return;第16页，共25页，编辑于2022年，星期六【例2.3】单链表逆转。第17页，共25页，编辑于2022年，星期六8.带头结点的单链表带头结点的单链表【例2.4】建立排序的单链表。第18页，共25页，编辑于2022年，星期六9.循环单链表循环单链表 第19页，共25页，编辑于2022年，星期六2.3.3 双链表双链表双链表结构双链表结构p=p.next.prev=p.prev.next第20页，共25页，编辑于2022年，星期六2.双链表的插入和删除操作双链表的插入和删除操作(1)插入q=new DLinkNode(x);q.prev=p.prev;q.next=p;p.prev.next=q;p.prev=q;第21页，共25页，编辑于2022年，星期六（2）删除）删除 p.prev.next=p.next;if(p.next!=null)(p.next).prev=p.prev;第22页，共25页，编辑于2022年，星期六3.循环双链表循环双链表 第23页，共25页，编辑于2022年，星期六4.双链表类双链表类 public class DLinkNode /双链表结点类双链表结点类 public E data;/数据元素数据元素 public DLinkNode prev,next;/前驱、后继结点前驱、后继结点public class CHDoublyLinkedList /带头结点的循环双链表类带头结点的循环双链表类 protected DLinkNode head;/头指针头指针第24页，共25页，编辑于2022年，星期六*2.4 迭代器（略）迭代器（略）第25页，共25页，编辑于2022年，星期六
