《数据结构 2章 线性表2》由会员分享，可在线阅读，更多相关《数据结构 2章 线性表2（41页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java版）,第1章 绪论 第2章 线性表 第3章 排序 第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 查找 第8章 图 第9章 综合应用设计,第2章 线性表,2.1 线性表的概念 2.2 线性链表,数据结构（Java版）叶核亚,2.1 线性表的概念,2.1.1 线性表的抽象数据类型 2.1.2 线性表的顺序存储结构 2.1.3 线性表的链式存储结构,数据结构（Java版）叶核亚,2.1.1 线性表的抽象数据类型,线性表的数据元素 线性表是由n（n0）个相同类型的数据元素a1，a2，an组成的有限序列，记作： LinearList=a1，a2，an 其中，n表示
2、线性表的元素个数，称为线性表的长度。若n=0，则称为空表。若n0，对于线性表中第i个数据元素ai，有且仅有一个直接前驱数据元素ai-1和一个直接后继数据元素ai+1，而a1没有前驱数据元素，an没有后继数据元素。,数据结构（Java版）叶核亚,线性表的基本操作求长度：求线性表的数据元素个数。 访问：对线性表中指定位置的数据元素进行存取、替换等操作。 插入：在线性表指定位置上，插入一个新的数据元素，插入后仍为一个线性表。 删除：删除线性表指定位置的数据元素，同时保证更改后的线性表仍然具有线性表的连续性。 复制：重新复制一个线性表。 合并：将两个或两个以上的线性表合并起来，形成一个新的线性表。 查
3、找：在线性表中查找满足某种条件的数据元素。 排序：对线性表中的数据元素按关键字值，以递增或递减的次序进行排列。 遍历：按次序访问线性表中的所有数据元素，并且每个数据元素恰好访问一次。,数据结构（Java版）叶核亚,线性表的抽象类,数据结构（Java版）叶核亚,2.1.2 线性表的顺序存储结构,线性表的顺序存储结构是用一组连续的存储单元顺序存放线性表的数据元素，数据元素在内存的物理存储次序与它们在线性表中的逻辑次序是一致的，即数据元素ai与其前驱数据元素ai-1及后继数据元素ai+1的位置相邻。,数据结构（Java版）叶核亚,图2.1 线性表的顺序存储结构,数据结构（Java版）叶核亚,1. 顺
4、序表的类定义,public class LinearList1 /线性表的顺序存储结构private int table; /私有成员private int n; /记载顺序表的长度 ,数据结构（Java版）叶核亚,2顺序表的操作,（1） 顺序表的初始化 public LinearList1(int n) /为顺序分配n个存储单元 /此时顺序表长度this.n为0table=new int n; /所占用的存储单元个数 this.table.length等于n this.n=0; ,数据结构（Java版）叶核亚,2顺序表的操作,（2） 判断顺序表的空与满状态 public boolean is
5、Empty() /判断顺序表是否为空 return n=0; public boolean isFull() /判断顺序表是否已满 return n=table.length; /table.length返回数组长度 ,数据结构（Java版）叶核亚,2顺序表的操作,（3） 返回顺序表长度 public int length() /返回顺序表的长度 return n; （4） 获得顺序表的第i个数据元素值 public int get(int i) /返回第i个元素值 if(i0 ,数据结构（Java版）叶核亚,2顺序表的操作,（5） 设置顺序表的第i个数据元素值 public void set
6、(int i,int k) /设置第i个元素值为k if(i0 ,数据结构（Java版）叶核亚,2顺序表的操作,（6） 查找 public boolean contains(int k) /查找线性表是否包含k值 /查找成功时返回true，否则返回falseint j=indexof(k);if(j!=-1)return true;elsereturn false; public int indexof(int k) /查找k值 /查找成功时返回k值首次出现位置，否则返回-1int j=0;while(j=0 ,数据结构（Java版）叶核亚,图2.2 顺序表中插入数据元素,数据结构（Java版
7、）叶核亚,（7） 在顺序表的第i个位置上插入数据元素 public void insert(int i,int k) /插入k值作为第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+;elseSystem.out.println(“数组已满，无法插入“+k+“值！“); public void insert(int k) /添加k值到顺序表最后，重载 insert(n+1,k); ,数据结构（Java版）叶核亚,图2.3 删除顺序表中的数据元素,数据结构（Java版）叶核亚,
8、2顺序表的操作,（8） 删除顺序表的第i个数据元素 public void remove(int k) /删除k值首次出现的数据元素 int i=indexof(k); /查找k值的位置if(i!=-1)for(int j=i;jn-1;j+) /删除第i个值tablej=tablej+1;tablen-1=0;n-;elseSystem.out.println(k+“值未找到，无法删除!“); ,数据结构（Java版）叶核亚,例2.1 以顺序表求解约瑟夫环问题,约瑟夫环（Josephus）问题：古代某法官要判决n个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第s个人开始数起，每数到
9、第d个犯人，就拉出来处决，然后再数d个，数到的人再处决直到剩下的最后一个可赦免。,数据结构（Java版）叶核亚,图2.4 约瑟夫环问题执行过程,数据结构（Java版）叶核亚,例2.1 以顺序表求解约瑟夫环问题,数据结构（Java版）叶核亚,2.2 线性链表,2.2.1 单向链表 2.2.2 单向循环链表 2.2.3 双向链表 2.2.4 双向循环链表,数据结构（Java版）叶核亚,2.1.3 线性表的链式存储结构,声明自引用的类 public class Node int data;Node next; 创建并使用对象 Node p,q; /声明p和q是Node类的对象 p=new Node(
10、); /创建Node类的一个对象，由p引用 q=new Node(); /创建Node类的一个对象，由q引用 p.next=q;,数据结构（Java版）叶核亚,2.2.1 单向链表,在线性链表中，如果每个结点只有一个链，则称为单向链表（singly linked list）。单向链表各结点的链通常指向其后继结点。,数据结构（Java版）叶核亚,1单向链表的结点类,package ds_java; /声明包 public class OnelinkNode /单向链表的结点类 public int data; /存放结点值public OnelinkNode next; /后继结点的引用publ
11、ic OnelinkNode(int k) /构造值为k的结点data=k;next=null;public OnelinkNode() /无参数时构造值为0的结点this(0); ,数据结构（Java版）叶核亚,2单向链表类,package ds_java; import ds_java.OnelinkNode; /引用单向链表的结点类 public class Onelink1 protected OnelinkNode head； /指向链表的第一个结点 ,数据结构（Java版）叶核亚,3单向链表的操作,数据结构（Java版）叶核亚,图2.7 建立单向链表,设rear指向原链表的最后一个
12、结点，q指向新创建的结点，则将q结点链在rear结点之后的语句是：rear.next=q；rear=q；,数据结构（Java版）叶核亚,例2.2 单向链表逆转。,front=null,数据结构（Java版）叶核亚,例2.2 单向链表逆转。,数据结构（Java版）叶核亚,（6） 插入结点,空表插入 head=new OnelinkNode(1)； 头插入 q=new OnelinkNode(2)； q.next=head； head=q；,尾插入 q=new OnelinkNode(3)； q.next=null； p.next=q； 中间插入 q=new OnelinkNode(4)； q.n
13、ext=p.next； p.next=q；,数据结构（Java版）叶核亚,例2.3 单向链表插入排序。,数据结构（Java版）叶核亚,（7）删除结点,图2.11 单向链表删除结点,数据结构（Java版）叶核亚,（7）删除结点,删除单结点链表，只要使链表的引用head为空即可。 head=null; 删除链表第1个结点，只要将head指向链表第1个结点的后继结点即可。 head=head.next; 删除链表中间（尾）结点，设p指向单向链表中的某一结点，删除p的后继结点的语句是： p.next=(p.next).next；,数据结构（Java版）叶核亚,2.2.2 单向循环链表,图2.12 单向
14、循环链表,数据结构（Java版）叶核亚,【例2.4】以单向循环链表求解约瑟夫环问题。,图2.13 以单向循环链表表示的约瑟夫环问题执行过程,数据结构（Java版）叶核亚,【例2.4】以单向循环链表求解约瑟夫环问题。,数据结构（Java版）叶核亚,2.2.3 双向链表,图2.14 双向链表,(p.prior).next=p (p.next).prior=p,数据结构（Java版）叶核亚,双向链表插入结点,q=new TwolinkNode(3)； q.prior=p； q.next=p.next； (p.next).prior=q； p.next=q；,数据结构（Java版）叶核亚,双向链表删除结点,(p.prior).next=p.next； (p.next).prior=p.prior；,数据结构（Java版）叶核亚,2.2.4 双向循环链表,
