《数据结构(Java)第2章》由会员分享，可在线阅读，更多相关《数据结构(Java)第2章（38页珍藏版）》请在金锄头文库上搜索。
1、,基本内容,第2章 线性表,一.线性表的定义与运算,1、线性表的定义 简单来说，一个线性表（Linear List）是由n个数据元素组成的有限序列。在同一线性表中的元素具有相同特性，即属同一数据对象。一个线性表通常记作： （a1，a2，ai-1，ai，ai+1，an） （1）有且仅有一个开始结点a1，它没有直接前驱； （2）有且仅有一个终端结点an，它没有直接后继； （3）除了开始结点a1和终端结点an外，其余结点都有且仅有一个直接前驱和一个直接后继。 简言之，线性表的特点是数据元素之间存在“一对一”的关系。,2、线性表举例 【例2.1】：某大学计算机科学系软件工程专业08级1班数据结构课程考
2、试成绩汇总，如下所示： （895，66,90，77.5,45，79,80） 【例2.2】26个大写英文字母表： （A，B，C，D，E，F，X，Y，Z） 也是一个线性表。在Java语言中我们可以将其中的元素定义为字符类型char。,【例2.3】 “东软集团新员工入职情况登记表”,3、线性表的运算 （1）求线性表的长度：length() 初始条件：线性表已存在 操作结果：返回线性表中含有的数据元素个数。 （2）按值查找操作：search(x) 初始条件：线性表已存在 操作结果：在线性表中查找值为x的数据元素，如果存在则返回该元素的序号；如果不存在则返回-1，表示查找失败。 （3）按序号查找操作：g
3、etElement(i) 初始条件：线性表已存在 操作结果：在线性表中查找第i个数据元素。假设线性表的长度为length，则i的取值范围是，返回该元素的引用。,（4）插入操作：insert(i,x) 初始条件：线性表已存在 操作结果：将新的数据元素x插入到线性表的第i个位置。 （5）删除操作：remove(i) 初始条件：线性表已存在 操作结果：删除并返回线性表中的第i个数据元素，同时将线性表的长度减1。 （6）判断空表：isEmpty() 初始条件：线性表已存在 操作结果：判断线性表是否为空，如果为空则返回true，否则返回false。,（7）判断线性表是否已满：isFull() 初始条件：
4、线性表已存在 操作结果：判断线性表是否已满，如果已满则返回true，否则返回false。（仅适用于顺序存储时） （8）遍历线性表：showList() 初始条件：线性表已存在，且非空。 操作结果：显示线性表中的所有数据元素值。 （9）清空线性表：clear() 初始条件：线性表已存在，且非空。 操作结果：将线性表重置为一个空表。,/* * 线性表接口 */ public interface LinearList int length(); /计算线性表的长度 int search(E x); /按值查找操作 E getElement(int i) throws Exception; /按序号查
5、找操作 void insert(int i,E x)throws Exception; /插入操作 E remove(int i) throws Exception; /删除操作 boolean isEmpty(); /判空表 boolean isFull(); /判断线性表是否已满 void showList(); /遍历线性表 void clear(); /清空线性表 ,二、线性表的顺序存储结构,1、顺序表 线性表的顺序存储结构指的是用一组地址连续的存储单元依次存储线性表中的数据元素。元素在内存中的物理存储次序与它们在线性表中的逻辑次序相同，即元素ai与其直接前驱ai-1及直接后继ai+1
6、的存储位置相邻。采用顺序存储结构的线性表也称为顺序表（Sequential List）。 线性表中的数据元素都属于同一种数据对象。假设线性表中的每个元素占用d个存储单元，并以所占第一个单元的存储地址作为数据元素的存储位置。同时假设线性表中第一个数据元素a1的存储地址为Loc（a1），则线性表的第i个数据元素ai的存储位置为： Loc（ai）=Loc（a1）+（i-1）*d,/* * 顺序表 */ public class SequentialList implements LinearList private Object data; /顺序表存储空间 private int length;
7、/保存顺序表长度 /构造一个存储容量为capacity的空表 public SequentialList(int capacity) data=new Objectcapacity; length=0; ,下面是顺序表类的Java语言描述：,2、顺序表上基本操作的实现 （1）插入操作 线性表的插入操作是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的线性表（a1，a2，ai-1，ai，ai+1，an），成为表长为n+1的表（a1，a2，ai-1，x，ai，ai+1，an）。插入操作需要移动数据元素。,/* * 顺序表的插入操作 */ public void insert(int
8、 i, Object x) throws Exception if(isFull() throw new Exception(“顺序表已满“); if(ilength) throw new Exception(“插入位置非法“); for(int k=length;ki;k-) datak=datak-1; datai=x; length+; ,（2）删除操作 线性表的删除操作是指将表中第i个元素从线性表中除去，原线性表（a1，a2，ai-1，ai，ai+1，an）删除ai元素后，成为（a1，a2，ai-1，ai+1，an），表长度减少1,为n-1。删除操作也需要移动数据元素。,/* * 顺序
9、表的删除操作 */ public Object remove(int i) throws Exception if(isEmpty() throw new Exception(“顺序表为空表“); if(ilength-1) throw new Exception(“删除位置非法“); Object tmp=datai; for(int k=i;klength-1;k+) datak=datak+1; length-; return tmp; ,（3）按值查找操作 在线性表中查找值为x的数据元素。 /* * 顺序表的按值查找操作 */ public int search(Object x) i
10、nt k=0; while(klength ,（4）顺序表上其他基本操作的实现 /清空顺序表 public void clear() length=0; /取第i个数据元素 public Object getElement(int i) throws Exception if(ilength-1) throw new Exception(“第“+i+“个元素不存在“); return datai; /判断顺序表是否为空 public boolean isEmpty() return length=0; ,/判断顺序表是否已满 public boolean isFull() return len
11、gth=data.length; /返回顺序表的长度 public int length() return length; /显示顺序表的所有元素 public void showList() for(int i=0;ilength;i+) System.out.print(datai+“ “); ,三、线性表的链式存储结构,与顺序表不同，线性表的链式存储结构是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。 单链表中的每个结点由2个域（又称字段）构成，一个数据域（Data）和一个指针域（next），指针域又称为地址域。
12、数据域存储该数据元素本身的值，指针域存放其后继元素的地址信息。,线性表L1 =（a1，a2，a3，a4，a5，a6，a7，a8）,/* * 单链表结点类 */ public class Node private Object data; /数据域 private Node next; /地址域 public Node(Object data, Node next) this.data = data; this.next = next; public Node(Object data) this(data, null); public Node() this(null, null); ,publ
13、ic Object getData() return data; public void setData(Object data) this.data = data; public Node getNext() return next; public void setNext(Node next) this.next = next; ,1、单链表的创建,/* * 创建单链表 */ Node head=null; /头指针 Node a1=new Node(“a“); /声明并实例化结点对象a1 head=a1; /将结点对象a1插入单链表 Node a2=new Node(“b“); /声明并
14、实例化结点对象a2 a1.setNext(a2); /将结点对象a2插入单链表 Node a3=new Node(“c“); /声明并实例化结点对象a3 a2.setNext(a3); /将结点对象a3插入单链表,2、单链表的遍历 /* * 遍历并显示单链表中的所有数据元素 */ Node p=head.getNext(); while(p!=null) System.out.println(p.getData()+“ “); p=p.getNext(); ,3、单链表的插入（1）后插结点 Node s=new Node(“x“); s.setNext(p.getNext(); p.setNe
15、xt(s);,(2)前插结点 Node s=new Node(“x“); Node q=head; while(q.getNext()!=p) q=q.getNext(); s.setNext(q.getNext(); q.setNext(s);,4、单链表的删除 Node q=head; while(q.getNext()!=p) q=q.getNext(); q.setNext(p.getNext);,5、单链表的按值查找操作 public int search(Object x) Node p=head.getNext(); int k=0; while(p!=null ,单链表操作的效率分析 （1）单链表是一种顺序存取结构，不是随机存取结构。要访问任意一个结点ai（1in），必须从头指针head开始，沿着“链”的方向逐个查找，执行i-1次p=p.getNext()操作，平均进行n/2次。 （2）单链表的插入和删除操作，必须知道其直接前驱结点。 （3）与顺序表相比，单链表中结点的存
