狠狠撸

第 2 章线性表
? 2.1 线性表抽象数据类型
? 2.2 线性表的顺序表示和实现
? 2.3 线性表的链式表示和实现
? 2.4
线性表的应用：多项式的表示及运算

目的和要求
? 目的：实现线性表抽象数据类型。
? 内容：将线性表的顺序存储结构和链式存储结构
实现分别封装成顺序表类、单链表类
、循环双链表类等，比较这两种实现的
特点以及各种基本操作算法的效率。
? 要求：理解线性表抽象数据类型，掌握顺序和链
式存储结构实现线性表的方法。
? 重点：顺序表、单链表、循环双链表等线性表的
设计训练。
? 难点：使用指针实现链式存储结构，通过指针操
作改变结点间的链接关系。
? 实验：掌握单链表的遍历、插入、删除、复制等
操作算法，熟悉循环单链表、双链表和
循环双链表的结构和基本操作。掌握
MyEclipse 集成开发环境的程序调试技

《数据结构（ Java 版）（第 3 版）》
2.1 线性表的抽象数据类
型
LinearList=(a0 ， a1 ，…， an － 1)
public interface LList<T>
{ // 线性表接口，泛型参数 T 表示数据元素的数据类型
boolean isEmpty(); // 判断线性表是否空
int length(); // 返回线性表长度
T get(int i); // 返回第 i （ i≥0 ）个元素
void set(int i, T x); // 设置第 i 个元素值为 x
void insert(int i, T x); // 插入 x 作为第 i 个元素
void append(T x); // 在线性表最后插入 x 元素
T remove(int i); // 删除第 i 个元素并返回被删除对象
void removeAll(); // 删除线性表所有元素
T search(T key); // 查找，返回首次出现的关键字为 key
元素
}
public class SeqList<T> implements LList<T> // 顺序表
类

2.2 线性表的顺序表示和
实现
1. 线性表的顺序存储结构
ciaLocaLoc i ×+= )()( 0

public class SeqList<T> implements LList<T>
{ // 顺序表类，实现线性
表接口
protected Object[] element; // 对象数组
protected int len; // 顺序表长度，记载元素个
数
}
2. 顺序表类

4. 顺序表的删除操
作
3. 顺序表的插入操
作

【例 2.1 】使用顺序表类求解
约瑟夫环问题。

顺序表的静态特性很好，动态特性很差，具体说明如
下。
① 顺序表元素的物理存储顺序直接反映线性表元素
的逻辑顺序，顺序表是一种随机存取结
构。 get() 、 set() 方法时间复杂度是 O(1) 。
② 插入和删除操作效率很低。如果在各位置插入元
素的概率相同，则有
5. 顺序表操作的效率分析
∑∑ ==
==
+
×
+
=?
+
=×?
n
i
n
i
i nO
nnn
n
in
n
pin
00
)(
22
)1(
1
1
)(
1
1
)(

6. 顺序表的浅拷贝与深拷贝
一个类的拷贝构造方法声明格式如下：
类 ( 类对象 )
（ 1 ）顺序表的浅拷贝
public SeqList(SeqList<T> list)// 浅拷贝构造方
法
{
this.element = list.element;
// 数组引用赋值，两个变量共用一个数组，
错误

执行拷贝构造方法
SeqList<String> listb = new
SeqList<String>(lista);

（ 2 ）顺序表的深拷贝

7. 顺序表比较相等
两个顺序表相等是指，它们各对应元素相
等并且长度相同。

2.3 线性表的链式表示和
实现
2.3.1 线性表的链式存储结构
2.3.2 单链表
2.3.3 双链表

2.3.1 线性表的链式存储
结构

1. 单链表结点类
public class Node<T> // 单链表结点类
{ public T data; // 数据域，保存数
据元素
public Node<T> next; // 地址域，引用后继
结点
}
Node<String> p,q;
p=new Node<String>("A", null );
q=new Node<String>("B", null );
2.3.2 单链表

2. 单链表的遍历操作
Node<T> p = head;
while (p!=null)
{System.out.print(p.data.toString()+" ");
// 执行访问 p 结点的相关操作
p = p.next;
}

如果语句 p=p.next 写成
p.next=p

3. 单链表的插入操作
（ 1 ）空表插入 / 头插入
if (head == null) // 空表插入
head = new Node<T>(x, null);
else // 头插入
{ Node<T> q = new Node<T>(x, null);
q.next = head;
head = q;
} 即 head = new Node<T>(x, head);

（ 2 ）中间插入 / 尾插入
Node<T> q = new Node<T>(x, null);
q.next = p.next;//q 的后继结点应是 p 的原后继结
点
p.next = q; //q 作为 p 的后继结点
即 p.next = new Node<T>(x, p.next);

如果上述后两条语句次序颠倒
，则产生错误
Node<T> q = new Node<T>(x, null);
p.next = q;
q.next = p.next;

4. 单链表的删除操作
a. 头删除
head = head.next;
b. 中间 / 尾删除
if (p.next!=null)
p.next = p.next.next;

5. 带头结点的单链表

【例 2.2 】采用单链表求解约
瑟夫环问题。

6. 单链表操作的效率分析
1. isEmpty() 方法的时间复杂度是 O(1) 。
2. length() 方法要遍历单链表，时间复杂度
是 O(n) 。
3. get(i) 和 set(i) 方法的时间复杂度是
O(n) ，不是随机存取结构。
4. insert(i,x) 和 remove(i) 时间复杂度是
O(n) 。

1. 在 p 结点之前插入结点 q
2. 删除结点 p 要寻找其前驱结点 front

7. 提高单链表操作效率的措
施
public boolean append(T x)
{
return insert(this.length(), x);
// 需遍历单链表两次，效率较
低
}
return insert(Integer.MAX_VALUE, x);
// 遍历一次

作用于顺序表的时间复杂度是
O(n) ，但作用于单链表的时间复杂
度则是
public String toString()
{
String str="(";
if (this.length()!=0)
{ for(int i=0; i<this.length()-1; i++)
str += this.get(i).toString()+", ";
str += this.get(this.length()-1).toString();
}
return str+")";
}
)( 2
nO

例 2.3 求整数单链表的平均值
。

【例 2.4 】单链表逆转。

8. 单链表的浅拷贝与深拷
贝
public
SinglyLinkedList(SinglyLinkedList<T>
list) // 拷贝构造函数，浅拷贝
{ this.head = list.head;
// 导致两个引用变量指向同一个结点
}

8. 单链表的深拷贝

9. 单链表比较相等
两条单链表相等是指，它们各对应元素
相等并且长度相同。

10. 排序单链表

11. 循环单链表

2.3.3 双链表
1. 双链表结构
p = p.next.pred = p.pred.next

2. 双链表的插入和删除操作
(1)插入
在 p 结点之前插入值为 x 结点
q = new DLinkNode<T>(x, p.pred,
p);
p.pred.next = q;
p.pred = q;

在 p 结点之后插入值为 x 结
点
q = new DLinkNode<T>(x, p, p.next);
// 当 p.next==null 时，尾插
入
if (p.next!=null)
p.next.pred = q; // 中间插入时执行

（ 2 ）双链表的删除操作
p.pred.next = p.next; // 有 p.pred!
=null
if (p.next!=null)
p.next.pred = p.pred;

3. 循环双链表

4. 排序循环双链表

2.4 线性表的应用：多项式的
表示及运算
2.4.1 一元多项式的表示及运算
2.4.2 二元多项式的表示及运算

2.4.1 一元多项式的表示及运
算
∑=
=++++=
m
i
i
i
m
mm xaxaxaxaaxA
0
2
210)( ?
∑=
=++++=
n
i
i
i
n
nn xbxbxbxbbxB
0
2
210)( ?
∑=
+=+
),max(
0
)()()(
nm
i
i
iinm xbaxBxA

1. 一元多项式的顺序存储结
构
9742
7292)( xxxxxxAn ?+?+?=

2. 一元多项式的链式存储结
构
9742
7292)( xxxxxxAn ?+?+?=
（ 1 ）一元多项式的项类
（ 2 ）多项式单链表

（ 3 ）多项式类
① 多项式类 Polynomial 声明及相加运算

【例 2.6 】一元多项式的表示
及相加运算。

② 多项式深度拷贝及应用

③ 比较两个多项式是否相
等
public boolean equals(Object obj)
// 比较两个多项式是否相等
{
return this==obj || obj instanceof
Polynomial &&
this.list.equals(((Polynomial)obj).list)
;

2.4.2 二元多项式的表示及运
算
（ 1 ）二元多项式的项类 TermXY
（ 2 ） Polynomial 可表示二元多项式
（ 3 ） PolySLinkedList<T> 类的作
用
3224
9263),( yxyyxxxyxP ++?+?=
2156362),,( 43342352362310
++++?+= yzzyxzyxzyxzyxzyxzyxP

线性表接口和类的层次关
系

狠狠撸

第02章线性表(java版)

More Related Content

第02章线性表(java版)

狠狠撸

第02章 线性表(java版)

More Related Content

第02章 线性表(java版)

第02章线性表(java版)

第02章线性表(java版)