数据结构与算法之第二章线性表

104 阅读 0 评论 69 点赞

我是靠谱客的博主清爽雪碧，这篇文章主要介绍数据结构与算法之第二章线性表，现在分享给大家，希望可以做个参考。

一、线性表及其基本操作
1、线性表的特点：
1）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱
2）除最后一个元素外，其他每一个元素有一个且仅有一个直接后继
3）原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制

2、线性表的抽象数据类型

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package 线性表;
public interface IList {
//清空线性表
public void clear();
//判断线性表是否为空
public boolean isEmpty();
//返回线性表的长度
public int length();
//返回第i个元素
public Object getObject(int index) throws Exception;
//插入x作为第i个元素
public void insert(int index, Object o) throws Exception;
//删除第i个元素并返回被删除对象
public Object delete(int index) throws Exception;
//返回x对应的元素位置
public int getIndex(Object o);
//输出线性表
public void print();
}

二、线性表的顺序存储及其实现
1、基本知识点

定义：将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组作为其存储结构。
限制：所有的数据类型都应该相同
特点：
1）在线性表上逻辑上相邻的数据元素，在物理存储位置上也是相邻的
2）便于随机存取
3）不便于在顺序表上插入和删除，因为插入和删除回事大量数据元素产生位置的移动（两个特点都是因为索引带来的方便之处和不便之处）
4）存储密度高，存储密度=（数据元素本身需要的存储空间）/（该数据元素实际所占用的空间）

2、顺序表类的描述

基本方法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package 线性表;
//顺序表类的描述
public class SqList implements IList{
private Object[] ListElem;
//线性表的存储空间
private int length;
//线性表的长度
//构造函数
public SqList(int maxsize) {
//maxsize在这里指的是线性表的最大容量
length = 0;
//初始化线性表的长度为0
ListElem = new Object[maxsize];
//为线性表分配存储单元
}
@Override
public void clear() {
//清除就是把当前顺序表的长度定义为0
length = 0;
}
@Override
public boolean isEmpty() {
//通过判断顺序表的长度是否为0
return length == 0;
}
@Override
public int length() {
return length;
}
@Override
public void print() {
for(int i = 0 ; i <length ; i++) {
System.out.print(ListElem[i]+" ");
}
}}

插入操作

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Override
/*
* 先判断线性表是否已满
* 后判断插入的位置是否合理
* 再将插入位置后面的元素往后移动
* 插入位置
* 让线性表当前的长度自增
*/
public void insert(int index, Object o) throws Exception {
if (length == ListElem.length) {
throw new Exception("顺序表已满");
}
if(index < 0 || index > length) {
throw new Exception("index无效");
}
for(int i = length; i > index ; i--) {
ListElem[i] = ListElem[i-1];
}
ListElem[index] = o;
length++;
}

删除操作

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Override
/*
* 首先判断删除的位置是否合理
* 然后将删除的元素位置后的元素往前挪
* 最后将list当前的长度减去1
*/
public Object delete(int index) throws Exception {
if(index < 0 || index >= length) {
throw new Exception("index无效");
}
Object s = ListElem[index];
for(int i = index; i < length-1 ; i++) {
ListElem[index] = ListElem[index+1];
}
length--;
return s;
}

某个元素的位置

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

@Override
/*
* 首先从位置0开始进行元素的比较，同时不断让位置自增实现自动往后查找
* 查找完毕之后，对最后的那个位置进行检验，如果位置小于length则已经找到
* 如果最后的位置大小等于位置那就是没找到
*/
public int getIndex(Object o) {
int j = 0;
while(j<length && !ListElem[j].equals(o)) {
j++;
}
if(j < length) {
return j;
}else
return -1;
}

某个位置上的元素

复制代码

1
2
3
4
5
6
7
8
9
@Override
public Object getObject(int index) throws Exception{
//首先要判断输入的index是否有效
if(index < 0 || index > length) {
throw new Exception("index无效");
}
return ListElem[index];
}

3、顺序表的优缺点

优点：算法简单、可读性好、开发代价低
缺点：
（1）插入、删除操作时需要移动大量元素，效率较低；
（2）最大表长（maxSize）难以估计，太大了浪费空间，太小了容易溢出。

4、 maxsize、.length()、Curlen之间的关系：
Maxsize和.length()应相等，curlen和.length()是不一样的，curlen指的是当前的长度是多少，而不是整个数组的最大空间是多少

三、线性表的链式存储以及实现
1、单链表

定义：线性表的n个元素所对应的n个结点通过引用链接成一个链表，每个元素关联一个链接（引用），表示后继关系（没有表示前驱关系）
特点
1）每个元素(表项)由结点构成；
2）线性结构；
3）结点之间可以连续存储，也可以不连续存储；
4）结点的逻辑顺序与物理顺序可以不一致；
5）表可扩充，无容量限制；
设置表头结点的好处
1）设置头结点的目的是为了简化对空表的特殊处理，使得算法更简单、更有效。
2）对于带头结点的单链表，可以很容易地表示空链表：
节点类的描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package 线性表;
//单链表的节点类
public class SingleNode {
private Object o; //数据域
private SingleNode next;//地址域
public SingleNode() {
}
public SingleNode(Object o) {
this.o = o;
}
public SingleNode(Object o,SingleNode next) {
this.o = o;
this.next = next;
}
public Object getO() {
return o;
}
public void setO(Object o) {
this.o = o;
}
public SingleNode getNext() {
return next;
}
public void setNext(SingleNode next) {
this.next = next;
}
}

单链表的描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package 线性表;
public class LinkList implements IList{
private SingleNode head; //单链表的头节点
//头结点是不储存数据的，但是头结点的下一个节点是存储数据的
//所以我们通过判断头结点的下一个节点是否为空来判断该链表是否为空
//构造函数
public LinkList() {
head = new SingleNode();
}
public SingleNode getHead() {
return head;
}
public void setHead(SingleNode head) {
this.head = head;
}
@Override
public void clear() {
head.setO(null);
head.setNext(null);
}
@Override
public boolean isEmpty() {
return head.getNext() == null;
}
@Override
public int length() {
SingleNode p = head.getNext();
int length = 0;
while(p != null) {
length++;
}
return length;
}
@Override
public void print() {
SingleNode p = head.getNext();
while(p != null) {
System.out.print(p.getO()+" ");
p = p.getNext();
}
}}

插入

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
@Override
/*
* 初始化p为头结点，定义计时器
* 用循环寻找第i个节点的前驱
* 判断输入的i是否合理
* 合理的话则将值插入，并将先驱的后继进行修改
*/
//插入数据元素
public void insert(int i , Object o)throws Exception{
//判断插入值是否合理
if(o == null) {
throw new Exception("请插入合理的值");
}
SingleNode p = head;//初始化p头结点（头结点与首节点不同）
int j = -1;//计数器
while(p!= null && j <i-1) {//前者为该节点不为空（链表的长度），后者为计数器小于插入位置,目的是查找i节点的前驱
p = p.getNext();
j++;
}
if(j > i-1 || p== null) {
//(前者代表计数器)
throw new Exception("请选择正确的位置插入");
}
SingleNode s = new SingleNode(o);//生成新节点
s.setNext(p.getNext());//修改新节点，使新节点插入单链表中
p.setNext(s);
}

删除

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
@Override
/*
* 初始化p指向头节点，定义计数器
* 寻找第i个节点的前驱
* 判断输入的i值是否合理
* 如果合理的话 修改删除节点的前驱的后继指向
*/
public Object delete(int index) throws Exception {
SingleNode p = head; //因为可能在第一个位置上就进行删除，而他要定位到删除位置的前驱，所以要初始化为头结点
int j =0;
while(p.getNext() != null && j < index-1) {
//这里之所以需要是p.getNext()!=null的原因是在进行删除时，定位到删除元素的前驱时，需要保证这个前驱的后继不能为空
//如果为空的话，那么则删除操作将没有意义
//在插入操作中也需要定位到插入位置的前驱，但是这时候不管这个前驱的后继是否为空都没有关系，对插入操作都没有影响
p = p.getNext();
j++;
}
if(p.getNext() == null || j > index-1) {
throw new Exception("i值不合理");
}
Object del = p.getNext().getO();
SingleNode s = new SingleNode(p.getNext().getNext());
p.setNext(s);
return del;
}

查找某个值的位置

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Override
/*
* 首先，定义首节点和计数器
* 其次，通过while循环来找值
* 最后通过判断该节点是否存在
* 来判断找到值了吗
*/
public int getIndex(Object x) {
// 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1
SingleNode p = head.getNext();//定义首节点
int j = 0; //计数器
while(p != null && !p.getO().equals(x)) {//前者是节点是否存在，后者是未找到值
p = p.getNext();
j++;
}
if(p == null)
return -1;
else
return j;
}

查找某个位置上的元素

@Override
/*

首先，定义首节点和计数器
其次利用while循环开始寻找
然后寻找过程结束后通过判断计数器j是否合理
来判断该单链表上是否包含i节点
*/
public Object getObject(int index) throws Exception {
SingleNode p = head.getNext();
int j = 0;
while(p != null && j < index) {
//p != null保证了查找的范围在链表的长度内，j<index保证了该循环可以在index的位置停下来
p = p.getNext();
j ++;
}
if(j > index || p == null) {
throw new Exception(“位置index上的元素不存在”);
}
return p.getO();
}

2、循环链表

循环链表是单链表的变形。
循环链表最后一个结点的next不为NULL，而是链表前端第一个结点的引用。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其它的结点。
和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。
在两个表合并修改中，语句序列为

复制代码

1
2
3
4
5
6
7
Node p = tailb.next;
//p指向第2个表的头结点
tailb.next = taila.next;
//第2个表的表尾与第一个表的表头相连
taila.next = p.next;
//第一个表的表尾与第2个表的首结点相连

3、双向链表

双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。
双向链表通常采用带表头结点的循环链表形式。
双向链表节点类

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package 线性表;
public class DuLNode {
private Object data;
private DuLNode prior;
private DuLNode next;
public DuLNode() {
this(null);
}
public DuLNode(Object data) {
this.data = data;
this.next = null;
this.prior = null;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public DuLNode getPrior() {
return prior;
}
public void setPrior(DuLNode prior) {
this.prior = prior;
}
public DuLNode getNext() {
return next;
}
public void setNext(DuLNode next) {
this.next = next;
}
}

双向链表的基本操作方法

复制代码

package 线性表;
//双向循环链表
public class DuLinkList implements IList{
public DuLNode head;
public DuLinkList() {
head = new DuLNode();
head.setPrior(head);
head.setNext(head);
}
@Override
public void clear() {
head.setNext(head);
head.setPrior(head);
}
@Override
public boolean isEmpty() {
return head.getNext() == head ;
}
@Override
public int length() {
DuLNode p = head.getNext();
int length = 0;
while(p != head) {
length ++;
}
return length;
}
@Override
public Object getObject(int index) throws Exception {
DuLNode p = head.getNext();
int i = 0;
while(!p.equals(head)&& i < index) {
i++;
p.getNext();
}
if(i != index || p.equals(head)) {
throw new Exception("输入的位置不合理");
}
return p.getData();
}
@Override
public void insert(int index, Object o) throws Exception {
DuLNode p = head.getNext();
int i = 0;
while(!p.equals(head)&& i < index) {
p.getNext();
i++;
}
if(i != index && p.equals(head)) {
throw new Exception("插入位置i不正确");
}
DuLNode s = new DuLNode(o);
p.getPrior().setNext(s);
s.setPrior(p.getPrior());
s.setNext(p);
p.setPrior(s);
}
@Override
public Object delete(int index) throws Exception {
DuLNode p = head.getNext();
int i = 0;
while(i < index && !p.equals(head)) {
i++;
p.getNext();
}
if(i != index) {
throw new Exception("输入的位置不合理");
}
Object data = p.getData();
p.getPrior().setNext(p.getNext());
p.getNext().setPrior(p.getPrior());
return data;
}
@Override
public int getIndex(Object o) {
DuLNode p = head.getNext();
int i = 0;
while(!p.getData().equals(o) && !p.getNext().equals(head)) {
i++;
p.getNext();
}
if(p.getNext().equals(head)) {
return -1;
}else
return 1;
}
@Override
public void print() {
DuLNode node = head.getNext();
while(!node.equals(head)) {
System.out.print(node.getData()+" ");
node.getNext();
}
System.out.println();
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package 线性表;
//双向循环链表
public class DuLinkList implements IList{
public DuLNode head;
public DuLinkList() {
head = new DuLNode();
head.setPrior(head);
head.setNext(head);
}
@Override
public void clear() {
head.setNext(head);
head.setPrior(head);
}
@Override
public boolean isEmpty() {
return head.getNext() == head ;
}
@Override
public int length() {
DuLNode p = head.getNext();
int length = 0;
while(p != head) {
length ++;
}
return length;
}
@Override
public Object getObject(int index) throws Exception {
DuLNode p = head.getNext();
int i = 0;
while(!p.equals(head)&& i < index) {
i++;
p.getNext();
}
if(i != index || p.equals(head)) {
throw new Exception("输入的位置不合理");
}
return p.getData();
}
@Override
public void insert(int index, Object o) throws Exception {
DuLNode p = head.getNext();
int i = 0;
while(!p.equals(head)&& i < index) {
p.getNext();
i++;
}
if(i != index && p.equals(head)) {
throw new Exception("插入位置i不正确");
}
DuLNode s = new DuLNode(o);
p.getPrior().setNext(s);
s.setPrior(p.getPrior());
s.setNext(p);
p.setPrior(s);
}
@Override
public Object delete(int index) throws Exception {
DuLNode p = head.getNext();
int i = 0;
while(i < index && !p.equals(head)) {
i++;
p.getNext();
}
if(i != index) {
throw new Exception("输入的位置不合理");
}
Object data = p.getData();
p.getPrior().setNext(p.getNext());
p.getNext().setPrior(p.getPrior());
return data;
}
@Override
public int getIndex(Object o) {
DuLNode p = head.getNext();
int i = 0;
while(!p.getData().equals(o) && !p.getNext().equals(head)) {
i++;
p.getNext();
}
if(p.getNext().equals(head)) {
return -1;
}else
return 1;
}
@Override
public void print() {
DuLNode node = head.getNext();
while(!node.equals(head)) {
System.out.print(node.getData()+" ");
node.getNext();
}
System.out.println();
}
}
}