数据结构（Java语言描述）
第一章 概述
四个问题（为什么要学习数据结构）：
1. 计算机如何高效且方便地表示和组织是数据？
2. 计算机如何存储数据？
3. 我们如何操作数据？可以实现哪一些操作？对待同一问题的解决办法的评判标准？
4. 如何选择某一问题的最优解？
- 数据结构的作用和意义
优秀的数据结构与算法是无数计算机前辈在不断实践中总结出来处理问题的经验，学习数据结构与算法，会让我们站在巨人的肩膀上，更快更好的处理相应的问题。
计算机处理问题时，我们必须为其设定好程序，必须告诉计算机如何去做。
接下来给出数据结构的定义：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系及操作的学科。 下面我们通过两个例子解释一下什么是非数值计算。
思考 我们把一个参赛项表示为图中的一个顶点，两个顶点中间有连线代表两个项目之间不能同时举行。
1.1数据结构的基本概念（数据、数据元素、数据对象、数据结构、数据类型）
数据：信息的载体，是对客观事物的符号表示。
数据元素：数据的基本单位，由一个或者多个数据项组成。
数据对象：具有相同特征的数据元素的集合。
数据结构：Data Structure，是数据及数据元素的组织形式。（集合，线性结构，树形结构，图形[网状]结构）。
数据的逻辑结构：Logic Structure，是从具体问题抽象出来的数学模型。独立于计算机，是数据本身固有的特性。
从逻辑上可以分为线性结构和非线性结构。
数据的物理结构：Physical Structure，又称数据的存储结构，分为顺序结构和链式结构。
1.2面向对象的数据结构表示
Java面向对象基础
1. 类的声明与实例化
2. 类成员的定义与使用
3. 抽象类
4. 泛型类
5. 面向对象的抽象数据类型
数据结构研究的是数据对象内部个数据元素之间逻辑关系问题，他不关心数据的具体类型，因此数据结构本身是
抽象的。
传统抽象数据类型定义
ADT 抽象数据类型名{
数据对象D：<数据对象的定义>
数据关系S：<数据关系的定义>
基本操作P：<基本操作的定义>
}
eg：一个集合的抽象数据类型
ADT Set{
数据元素： ai 属于同一数据对象，i= 1，2，3，4，...... n（n >= 0）
逻辑结构： <ai,ai-1> | i=1,2,3,4, ...... ，n（n >= 0）,a1无前驱，an无后继
基本操作： InitSet（）
Length()
Insert(i,x)
Delete()
......
}ADT Set
Java泛型类表示的抽象数据类型格式
[访问修饰符] class抽象数据类型名<类型参数列表>
{
[访问修饰符] 数据类型 数据对象；// 数据对象定义
[访问修饰符] 返回值类型 基本操作1（参数列表）{
// 基本操作1的定义
}
// 其他基本操作
}
eg：一个字典的抽象数据类型
public class Dictionary<K,V>{
// 数据对象的定义：词典由原文词汇表和译文词汇表组成
public K[] keys;
public V[] values;
public int n;
// 基本操作： 词典提供初始化，添加新词，删除词条，翻译等操作
public Dictionary (int max){
// 初始化操作的定义
}
public void append(K k, V v){
// 添加新词的定义
}
public boolean delete(K k){
// 删除词条的定义
}
public V translate(K k){
// 翻译操作的定义
}
// 其他操作定义
}
1.3算法和算法分析
算法 + 数据结构 = 程序
算法其实就是为了解决某一问题而采取的方法和步骤的准确完整描述，他是一个有穷的规则序列，这些规则决定了
解决某一特定问题的一系列运算。
算法的特征
1. 有穷性
2. 确定性
3. 可行性
4. 输入
5. 输出
评价一个算法优劣的标准
1. 正确性
2. 可读性
3. 健壮性
4. 运行时间
5. 占用空间
算法效率的度量
1. 时间复杂度
一个程序的运行时间是指程序从开始到结束所需要的时间。影响程序运行时间的因素是多方面的（机器运行速
度、编译程序产生的目标代码质量、数据的输入等）。【选中最基本的一条语句，看他执行了多少次】
2. 空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。
一． 填空题
1.数据的物理结构包括 顺序结构 的表示和存储和 链式结构 的表示和存储。
2.对于给定的n个元素,可以构造出的逻辑结构有（集合结构）,(线性结构)，(树型结构)，(图型结构)四种。
3.一个算法具有5个特性：(有穷性)、（确定性）、（可行性），有零个或多个输入、有一个或多个输出。
4.抽象数据类型被形式地定义为（D，S，P），其中D是（数据元素）的有限集合，S是D上的（关系）有限集合， P是对D的（基本操作）集合。
5.数据结构主要包括数据的（逻辑结构）、数据的（存储结构）和数据的（操作）这三个方面的内容。
6.一个算法的效率可分为（时间）效率和（空间）效率。
二．单项选择题
1.线性结构是数据元素之间存在一种（ D ）。
A．一对多关系 B．多对多关系 C．多对一关系 D．一对一关系
2.数据结构中，与所使用的计算机无关的是数据的（ C ）结构。
A．存储 B．物理 C．逻辑 D．物理和存储
3.算法分析的目的是（ B ）。
A．找出数据结构的合理性 B．分析算法的效率以求改进
C．研究算法中的输入和输出的关系 D．分析算法的易懂性和文档性
4.算法分析的两个主要方面是（ A ）。
A．空间复杂性和时间复杂性 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
5.计算机算法指的是（ C ）。
A．计算方法 B．排序方法
C．解决问题的有限运算序列 D．调度方法
6.从逻辑上可以把数据结构分为（ A ）。
A．线性结构和非线性结构 B．紧凑结构和非紧凑结构
C．动态结构和静态结构 D．内部结构和外部结构
第二章 线性表
4.1 线性表的逻辑结构
什么是线性表？
线性表（Linear List）是n个元素的有限序列，可以表示成（a1,a2,a3,,,,ai,,,,an）。我们称n为线性表的长度，
n=0时，线性表为空表。ai是数据表中的元素，i是元素ai在线性表中的位序。
线性表有那些特点？
1. 线性表中必存在 第一元素
2. 线性表中必存在 最后元素
3. 除第一元素之外 均有前驱元素
4. 除最后元素之外 均有后继元素
线性表的基本操作
初始化： 构造一个空的线性表
销毁： 销毁一个已经存在的线性表
（对数据 加工性操作）
插入： 在第i个位置之前插入一个新元素
删除： 删除第i个位置上的元素
更新： 更新或修改第i个位置上的元素
（引用型操作）
查找： 找出线性表中满足特定条件的元素的下标或位置
获取： 获取指定位置或者下标上的数据元素
判空： 判断线性表是否为空
求长度： 求出线性表里边个元素个数
遍历输出： 一次打印输出线性表中的内容
4.2 线性表的顺序表示和实现
线性表中存储的数据元素的数据类型是一样的，每个元素在内存中占用的内存空间也都是一样的。我们只需要知道
线性表的首地址，那么我们就是能直接拿到线性表中任意元素的内存地址。
LOC(ai) = LOC(a1) + (i-1) * L
LOC(ai) 第i个元素的内存地址
LOC(a1) 第一个元素的内存地址
L L是每个元素占用的内存空间，比如说int类型 每个元素占用四个字节
/**
* \* Created with IntelliJ IDEA.
* \* User: maomao
* \* Date: 2022/9/25
* \* Time: 9:24
* \* Description: 演示线性表的顺序结构以及其中方法的实现
* \
*/
public class SequenceList<T> {
// 顺序表中一维数组的初始长度
final int MAXSIZE = 10;
// 存储数据元素的数组对象
private T[] listArray;
// 用于保存当前数组的长度
private int length;
public int getMAXSIZE() {
return MAXSIZE;
}
public T[] getListArray() {
return listArray;
}
// 默认初始化方法
public SequenceList() {
// 去内存里申请内存空间 按照默认的MAXSIZE去申请内存空间
length = 0; // 线性表初始为空
listArray =(T[]) new Object[MAXSIZE];
}
/**
* 初始化方法
* @param n 数组初始化的长度
*/
public SequenceList(int n) {
// 去内存里申请内存空间 按照参数n去申请内存空间
if (n < 0) {
System.out.println("eroor");
System.exit(0);
}
length = 0; // 线性表初始为空
listArray =(T[]) new Object[n];
}
/**
* 向顺序表中添加数据
* @param pos 添加元素的下标或者位置
* @param obj 添加元素的值
* @return
*/
public boolean add(int pos, T obj) {
if(pos < 0||pos >length-1){
System.out.println("pos不合法");
return false;
}
if(length==listArray.length){
// 要么扩容 要么报错
T[] p =(T[]) new Object[length * 2];
for(int i = 0;i<length;i++){
p[i]=listArray[i];
}
listArray=p;
}
for(int i = length;i>pos;i--){
listArray[i] = listArray[i-1];
}
listArray[pos] = obj;
length++;
return true;
}
/**
* 删除顺序表中pos位置或者下标上的元素
* @param pos 要删除元素的位置或者下标
* @return
*/
public T delete(int pos) {
if(pos < 0||pos >length-1){
System.out.println("pos不合法");
return null;
}
if(length<=0){
System.out.println("顺序表为空表");
return null;
}
T t = listArray[pos];
for(int i = pos;i<length-1;i++){
listArray[i] = listArray[i+1];
}
length--;
return t;
}
/**
* 找出线性表中满足特定条件的元素的下标或位置
* @param obj 特定元素
* @return
*/
public int find(T obj) {
if(isEmpty()){
System.out.println("顺序表为空");
return -1;
}
for(int i = 0;i<length;i++){
if(listArray[i].equals(obj)){
return i;
}
}
return -1;
}
/**
* 获取指定位置或者下标上的数据元素
* @param pos 指定位置或者下标
* @return
*/
public T getValue(int pos) {
if (isEmpty()) {
System.out.println("顺序表为空");
return null;
}
if (pos < 0 || pos >= length) {
System.out.println("pos不合法");
return null;
}
return listArray[pos];
}
/**
* 更新或修改第i个位置上的元素
* @param pos 更新或修改元素的位置
* @param obj 替换的值
* @return
*/
public boolean update(int pos, T obj) {
if (isEmpty()) {
System.out.println("顺序表为空");
return false;
}
if (pos < 0 || pos >= length) {
System.out.println("pos不合法");
return false;
}
listArray[pos] = obj;
return true;
}
/**
* 判断线性表是否为空
* @return
*/
public boolean isEmpty() {
return length==0;
}
/**
* 求出线性表里边个元素个数
* @return
*/
public int getLength() {
return length;
}
/**
* 遍历输出
*/
public void getSequenceList() {
for (int i = 0; i < length; i++) {
System.out.println(listArray[i]);
}
}
/**
* 合并两个顺表中的元素，按升序排列
* @param LA 顺序表LA
* @param LB 顺序表LB
* @return 顺序表LC
*/
public SequenceList<T> Merge_list(SequenceList<T> LA,SequenceList<T> LB) {
SequenceList<T> LC = new SequenceList<>();
// 分别指向la，lb，lc元素的位置
int i =1, j=1 ,k=1;
while(i<=LA.getLength()&&j<= LB.getLength()){
if ((int)LA.getValue(i) <= (int)LB.getValue(j)) {
LC.add(k,LA.getValue(i));
j++;
} else {
LC.add(k,LB.getValue(j));
i++;
}
k++;
}
while(i<=LA.getLength()){
LC.add(k,LA.getValue(i));
k++;
i++;
}
while(j<=LB.getLength()){
LC.add(k,LB.getValue(j));
k++;
j++;
}
return LC;
}
}
顺序表的初始化
// 默认初始化方法 public SequenceList() { // 去内存里申请内存空间 按照默认的MAXSIZE去申请内存空间 length = 0; // 线性表初始为空 listArray =(T[]) new Object[MAXSIZE]; } /** * 初始化方法 * @param n 数组初始化的长度 */ public SequenceList(int n) { // 去内存里申请内存空间 按照参数n去申请内存空间 if (n < 0) { System.out.println("eroor"); System.exit(0); } length = 0; // 线性表初始为空 listArray =(T[]) new Object[n]; }
数据插入
/** * 向顺序表中添加数据 * @param pos 添加元素的下标或者位置 * @param obj 添加元素的值 * @return */ public boolean add(int pos, T obj) { if(pos < 0||pos >length-1){ System.out.println("pos不合法"); return false; } if(length==listArray.length){ // 要么扩容 要么报错 T[] p =(T[]) new Object[length * 2]; for(int i = 0;i<length;i++){ p[i]=listArray[i]; } listArray=p; } for(int i = length;i>pos;i--){ listArray[i] = listArray[i-1]; } listArray[pos] = obj; length++; return true; }
注意：
- pos指的是元素下标 pos的范围是 0<= pos <=length-1,length指的是原表长，或者listArray它的长度
- listArray一共可以存储listArray.length个元素，插入数据的时候一定要先判断listArray有没有存满
- 插入数据移动元素的时候，一定是从后往前移动元素
- 插入元素之后，顺序表长度记得+1
数据删除
/** * 删除顺序表中pos位置或者下标上的元素 * @param pos 要删除元素的位置或者下标 * @return */ public T delete(int pos) { if(pos < 0||pos >length-1){ System.out.println("pos不合法"); return null; } if(length<=0){ System.out.println("顺序表为空表"); return null; } T t = listArray[pos]; for(int i = pos;i<length-1;i++){ listArray[i] = listArray[i+1]; } length--; return t; }
顺序表的查找
/** * 找出线性表中满足特定条件的元素的下标或位置 * @param obj 特定元素 * @return */ public int find(T obj) { if(isEmpty()){ System.out.println("顺序表为空"); return -1; } for(int i = 0;i<length;i++){ if(listArray[i].equals(obj)){ return i; } } return -1; }
获取元素
/** * 获取指定位置或者下标上的数据元素 * @param pos 指定位置或者下标 * @return */ public T get(int pos) { if (isEmpty()) { System.out.println("顺序表为空"); return null; } if (pos < 0 || pos >= length) { System.out.println("pos不合法"); return null; } return listArray[pos]; }
修改元素
/** * 更新或修改第i个位置上的元素 * @param pos 更新或修改元素的位置 * @param obj 替换的值 * @return */ public boolean update(int pos, T obj) { if (isEmpty()) { System.out.println("顺序表为空"); return false; } if (pos < 0 || pos >= length) { System.out.println("pos不合法"); return false; } listArray[pos] = obj; return true; }
判空
/** * 判断线性表是否为空 * @return */ public boolean isEmpty() { return length==0; }
求顺序表的长度
/** * 求出线性表里边个元素个数 * @return */ public int getLength() { return length; }
遍历输出所有的元素
/** * 遍历输出 */ public void getSequenceList() { for (int i = 0; i < length; i++) { System.out.println(listArray[i]); } }顺序表的应用
例： 有顺序表LA和LB，其元素均按照从小到大的升序排列，编写一个算法，将他们合并成一个顺序表LC，要求LC的元素也是从小到大 的升序。/** * 合并两个顺表中的元素，按升序排列 * @param LA 顺序表LA * @param LB 顺序表LB * @return 顺序表LC */ public SequenceList<T> Merge_list(SequenceList<T> LA,SequenceList<T> LB) { SequenceList<T> LC = new SequenceList<>(); // 分别指向la，lb，lc元素的位置 int i =1, j=1 ,k=1; while(i<=LA.getLength()&&j<= LB.getLength()){ if ((int)LA.getValue(i) <= (int)LB.getValue(j)) { LC.add(k,LA.getValue(i)); j++; } else { LC.add(k,LB.getValue(j)); i++; } k++; } while(i<=LA.getLength()){ LC.add(k,LA.getValue(i)); k++; i++; } while(j<=LB.getLength()){ LC.add(k,LB.getValue(j)); k++; j++; } return LC; }
线性表的链式表示和实现
线性表的链式存储结构使用一组任意的存储单元来存放线性表的数据元素，这组存储单元可以是连续的，也可以是不连续
的。
那么，同学们请思考一下，对于其中的某一元素，如何找到他的下一个元素呢？
思考：顺序表怎么获取元素的直接后继元素的内存地址？链表又如何获取直接后继元素的内存地址？
单链表节点（单链表结点）：单链表节点由两部分信息，第一部分是数据域（存储数据元素），第二部分是指针域（直接后
继元素的内存地址）。
~~~java
// 节点类定义
public class Node<T> {
T data; //数据域
Node<T> next;//指针域
// 构造器
public Node(Node<T> next) {
this.next = next;
}
// 构造器
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
linkList类，要有两成员变量，一个是指向头节点的指针，一个是length单链表的长度。
public class LinkList<T> {
private Node<T> head;// 头指针
private int length; // 单链表长度
// 构造器
public LinkList() {
}
// 获取表头结点的地址
public Node<T> getHead() {
return head;
}
// 在链表中插入一个元素
public boolean add(T obj, int pos) {}
// 删除一个元素
public T remove(int pos) {}
// 获取一个元素
public T value(int pos) {}
// 查找一个元素
public int find(T obj) {}
// 更新一个节点的值
public boolean modify(T obj, int pos) {}
// 判空
public boolean isEmpty(){}
// 求链表的长度
public int size() {}
// 遍历输出链表
public void nextOrder() {}
// 销毁一个链表
public void clear() {}
}
假设存在一个链表：(a1,a2,a3,a4,s5,a6)，那么它在内存中是怎样存储的？
添加新节点
1. 向尾部添加新节点
创建一个新的节点a7
让a6的指针域指向a7的内存地址
a7的指针域置为null
2. 向中间添加新节点
创建一个新的节点a7
让a7的指针域指向a4的内存地址把a3的指针域赋值给a7的指针域
把a3的指针域赋值成a7的地址
// 在链表中插入一个元素
public boolean add(T obj, int pos) {
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return false;
}
// 标记 目前查找到了第几个位置
int num = 1;
// 拿到头节点
Node<T> p = head;
// 通过头节点，拿到链表的第一个节点
Node<T> q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
p.next = new Node<T>(obj, q);
length++;
return true;
}
删除元素
1. 在链表的尾部删除元素
2. 删除中间元素
// 删除一个元素
public T remove(int pos) {
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return null;
}
int num = 1;
// 拿到头节点
Node<T> p = head;
// 通过头节点，拿到链表的第一个节点
Node<T> q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
p.next = q.next;
length--;
return q.data;
}
单链表查找值
1. 判断链表是否为空
2. 引入头节点，保存节点p中
3. 循环判断p.data.equals(obj)，如果为true，返回pos，否则，返回-1.
// 获取一个元素
public T value(int pos) {
// 判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return null;
}
int num = 1;
Node<T> p = head.next;
while (num < pos) {
p = p.next;
num++;
}
return p.data;
}
单链表查找第pos个节点的值
1. 判断链表是否为空
2. 判断pos是否合法输入
3. 循环并返回p.data
// 查找一个元素
public int find(T obj) {
// 判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
int num = 1;
Node<T> p = head.next;
while (p != null) {
if (p.data.equals(obj) == false) {
p = p.next;
num++;
}
break;
}
if (p == null) {
return -1;
}
return num;
}
单链表更新第pos个节点的值
1. 判断链表是否为空
2. 判断pos是否合法输入
3. 循环并修改p.data = obj
// 更新一个节点的值
public boolean modify(T obj, int pos) {
// 判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return false;
}
int num = 1;
Node<T> p = head.next;
while (num < pos) {
p = p.next;
num++;
}
p.data = obj;
return true;
}
完整实现：
public class LinkList<T> {
private Node<T> head;// 头指针
private int length; // 单链表长度
// 构造器
public LinkList() {
length = 0;
head = new Node<T>(null);
}
// 获取表头结点的地址
public Node<T> getHead() {
return head;
}
// 在链表中插入一个元素
public boolean add(T obj, int pos) {
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return false;
}
// 标记 目前查找到了第几个位置
int num = 1;
// 拿到头节点
Node<T> p = head;
// 通过头节点，拿到链表的第一个节点
Node<T> q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
p.next = new Node<T>(obj, q);
length++;
return true;
}
// 删除一个元素
public T remove(int pos) {
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return null;
}
int num = 1;
// 拿到头节点
Node<T> p = head;
// 通过头节点，拿到链表的第一个节点
Node<T> q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
p.next = q.next;
length--;
return q.data;
}
// 获取一个元素
public T value(int pos) {
// 判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return null;
}
int num = 1;
Node<T> p = head.next;
while (num < pos) {
p = p.next;
num++;
}
return p.data;
}
// 查找一个元素
public int find(T obj) {
// 判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
int num = 1;
Node<T> p = head.next;
while (p != null) {
if (p.data.equals(obj) == false) {
p = p.next;
num++;
}
break;
}
if (p == null) {
return -1;
}
return num;
}
// 更新一个节点的值
public boolean modify(T obj, int pos) {
// 判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空，请先插入元素");
}
// 判断pos是否合法，pos不能小于1 并且不能大于 length+1
if (pos < 1 || pos > length + 1) {
System.out.println("pos不合法输入");
return false;
}
int num = 1;
Node<T> p = head.next;
while (num < pos) {
p = p.next;
num++;
}
p.data = obj;
return true;
}
// 判空
public boolean isEmpty(){
return this.length==0;
}
// 求链表的长度
public int size() {
return this.length;
}
// 遍历输出链表
public void nextOrder() {
Node<T> p = this.head.next;
while (p != null) {
System.out.println(p.data);
p = p.next;
}
}
// 销毁一个链表
public void clear() {
this.head = null;
this.length = 0;
}
public static void main(String[] args) {
LinkList<Integer> L = new LinkList<>();
int i;
int[] a = {23, 34, 45, 56, 67, 78};
for (i = 0; i < a.length; i++) {
L.add(a[i], i + 1);
}
System.out.print("单链表的数据为：");
// 向链表里边添加一个数据
L.add(89, 7);
L.add(89, 5);
// 向链表里边删除一个数据
L.remove(3);
// 打印输出链表
L.nextOrder();
}
}
2.4 循环链表
循环单链表：
最后一个节点的指针域指向head节点
循环双链表：
最后一个节点的指针域2指向head节点
head节点的指针域1指向最后一个节点
2.5 链表的应用
链表的应用：将两个有序链表合并成一个有序链表。
思路： 设LC是合并后的链表，我们无需为LC申请新的内存空间，可以直接利用两个链表里原有的节点链接成一个新表即可。
设三个链表LA，LB，LC，再来三个指针pa，pb，pc，其中pa，pb分表代表LA、LB中当前带比较插入的节点，pc指向的是当前LC中最后一个节点。然后一次比较pa和pb指向的两个节点，把小的放入pc指向的节点中。
练习题：
一．填空题
1.线性表的两种存储结构分别为（顺序存储）和（链式存储）。
2.顺序表中，逻辑上相邻的元素，其物理位置 一定 相邻。在单链表中，逻辑上相邻的元素，其物理位置 不
一定 相邻。
3.若经常需要对线性表进行插入和删除操作，则最好采用（链式）存储结构，若线性表的元素总数基本稳定，且很少进行插
入和删除操作，但要求以最快的速度存取线性表中的元素，则最好采用（顺序）存储结构。
4.在顺序表中等概率下插入或删除一个元素，需要平均移动 (n/2) 元素，具体移动的元素个数与 (插入或删除位置)
有关。
5.在带头结点的非空单链表中，头结点的存储位置由 (head头指针) 指示，首元素结点的存储位置由 (head.next)
指示，除首元素结点外，其它任一元素结点的存储位置由 (其直接前驱) 指示。
6.已知L是带头结点的单链表，且p结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。
a. 在p结点后插入s结点的语句序列是： 。
s.next=p.next; p.next=s;
b. 在p结点前插入s结点的语句序列是： 。
q=head; while(q.next!=p) q=q.next; s.next=p; q.next=s;
c. 在表首插入s结点的语句序列是： 。
s.next=head.next; head.next=s;
d. 在表尾插入s结点的语句序列是： 。
while(p.next!=null) p=p.next; s.next=null; p.next=s;
二．单项选择题
1.线性表是（ A ）。
A．一个有限序列，可以为空 B．一个有限序列，不能为空
C．一个无限序列，可以为空 D．一个无限序列，不能为空
2.带头结点的单链表L为空的判定条件是（ B ）。
A．head==null B．head .next==null
C．head .next==L D．head!=null
3.在表长为n的单链表中，算法时间复杂度为O(n)的操作为（ D ）。
A．删除p结点的直接后继结点 B．在p结点之后插入一个结点
C．删除表中第一个结点 D．查找单链表中第i个结点
4.在表长为n的顺序表中，算法时间复杂度为O(1)的操作为（ C ）。
A．在第i个元素前插入一个元素 B．删除第i个元素
C．在表尾插入一个元素 D．查找其值与给定值相等的一个元素
5.设单链表中指针p指向结点ai，若要删除ai之后的结点，则需修改指针的操作为（ B ）。
A．p=p.next B．p.next=p.next.next
C．p=p.next.next D．next=p
第三章 栈和队列
3.1 顺序栈
栈：栈是限定仅在表尾部进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶（top），另一端则称为栈底
（bottom），不含任何数据元素的栈为空栈。
栗子：有一座独木桥，在桥上，一次只允许一个人通过，当后面有人时，前面的人不能转身返回，只能走到底。那么我们假
设，桥的另一端没有路（或者说是不能通过），只能原路返回，那么这一行人返回的顺序是怎样的？
最后一个先下桥，然后倒数第二个，最后才是第一个上桥的人。
对于这样的过程，我们把这一行人，当作数据元素，并且元素之间存在序偶关系，这种先进后出的线性表结构我们称为栈。
a1 为栈底元素，an为栈顶元素。
栈中元素的进栈顺序为 a1，a2，a3，...，an
栈中元素的出栈顺序为an，...，a3，a2，a1
所以，栈被称为后进先出(LIFO)的线性表（Last in First out）
栈有两个操作：入栈和出栈。入栈和出栈操作的都是栈顶元素。所以栈顶的位置随着元素的插入和删除而变化，为此我们需
要一个指向栈顶的指针来指示栈顶的当前位置。
元素入栈和出栈过程
栈的基本操作
1. 初始化----头造一个空的栈
2. 入栈----在栈顶位置插入一个新元素
3. 出栈----删除栈顶元素
4. 获取----取栈顶元素
5. 判空----判断当前栈是否为空
6. 求长度----求出栈中元素的个数
7. 正序遍历----一次访问栈中每个元素并输出
8. 销毁----销毁一个已存在的栈
栈的分类：顺序栈和链栈
顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。把数组中下标为0的一端作为栈底，为了指示栈
中元素的位置，我们定义变量top来指示栈顶元素在顺序栈中的位置，top为整型。
顺序栈的泛型类定义如下：
public class SequenceStack<T> {
final int MaxSize = 10; //默认申请数组的初始化容量
private T[] stackArray;
private int top;
public SequenceStack() {
}
public SequenceStack(int n) {
}
//在栈顶插入一个新元素
public void push(T obj) {
}
// 删除栈顶元素
public T pop() {
return null;
}
//取栈顶数据元素
public T getHead() {
return null;
}
//判断当前栈是否为空
public boolean isEmpty() {
return false;
}
//求出栈中数据元素的个数
public int size() {
return this.top;
}
//依次访问栈中的每个元素
public void nextOrder() {
}
//销毁一个栈
public void clear() {
}
}
1.top：为指针，指向栈顶元素的位置
top的初始值为-1，指向栈底，而这个top=-1也可以作为栈空的标志。
2.顺序栈的基本操作（栈的初始化，入栈，出栈，取栈顶元素，判栈空操作，求栈长度，遍历栈，清空栈）
栈的初始化：为栈分配一个数组，初始化栈的长度以及栈顶指针。
public SequenceStack() {
top = -1;
stackArray = (T[]) new Object[MaxSize];
}
public SequenceStack(int n) {
if (n < 0) {
System.out.println("数组初始化长度要大于零");
System.exit(1);
}
top = -1;
stackArray = (T[]) new Object[n];
}
入栈：栈顶指针上移一位，插入数据元素。
//在栈顶插入一个新元素
public void push(T obj) {
// 判断是否满栈，如果是满栈，则将栈扩容到当前容量的2倍
if (top == stackArray.length - 1) {
T[] p =(T[]) new Object[top * 2 + 2];
for (int i = 0; i <= top; i++) {
p[i] = stackArray[i];
}
stackArray = p;
}
top++;
stackArray[top] = obj;
}
出栈：栈顶指针下移一位。
// 删除栈顶元素
public T pop() {
// 判断栈是否为空
if (top == -1) {
System.out.println("当前栈中数据已空，无需删除");
return null;
}
top--;
return stackArray[top+1];
}
//取栈顶数据元素
public T getHead() {
// 判断栈是否为空
if (top == -1) {
System.out.println("当前栈中数据已空，无需删除");
return null;
}
return stackArray[top];
}
完整实现
public class SequenceStack<T> {
final int MaxSize = 10; //默认申请数组的初始化容量
private T[] stackArray;
private int top;
public SequenceStack() {
top = -1;
stackArray = (T[]) new Object[MaxSize];
}
public SequenceStack(int n) {
if (n < 0) {
System.out.println("数组初始化长度要大于零");
System.exit(1);
}
top = -1;
stackArray = (T[]) new Object[n];
}
//在栈顶插入一个新元素
public void push(T obj) {
// 判断是否满栈，如果是满栈，则将栈扩容到当前容量的2倍
if (top == stackArray.length - 1) {
T[] p =(T[]) new Object[top * 2 + 2];
for (int i = 0; i <= top; i++) {
p[i] = stackArray[i];
}
stackArray = p;
}
top++;
stackArray[top] = obj;
}
// 删除栈顶元素
public T pop() {
// 判断栈是否为空
if (top == -1) {
System.out.println("当前栈中数据已空，无需删除");
return null;
}
top--;
return stackArray[top+1];
}
//取栈顶数据元素
public T getHead() {
// 判断栈是否为空
if (top == -1) {
System.out.println("当前栈中数据已空，无需删除");
return null;
}
return stackArray[top];
}
//判断当前栈是否为空
public boolean isEmpty() {
return top==-1;
}
//求出栈中数据元素的个数
public int size() {
return this.top+1;
}
//依次访问栈中的每个元素
public void nextOrder() {
for (int i = 0; i < top+1; i++) {
System.out.println(stackArray[i]);
}
}
//销毁一个栈
public void clear() {
top = -1;
}
}