数据结构-线性表-顺序存储
数据结构
4 分钟 读完 (大约 647 个字)

数据结构-线性表-顺序存储

概述

　　线性表的顺序存储的基本方法是定义一个数组类型的对象来存储集合元素，同时还要定义一个整型对象来存储集合的长度，以及定义一个整型常量对象来保存待定义数组的初始长度。

1
2
3
final int maxSize=20; //假定存储集合的数组的初始长度为20
private Object setArray[]; //定义存储集合的数组的引用对象
private int length;//定义数组中所保存集合的当前长度

操作实现

1.初始化

　　通过构造函数，初始化集合为空，并保存集合的数组setArray定义对象。构造函数有两个，一个无参构造函数，另一个为带有数组初始长度参数的构造函数。定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public Set(){ //无参构造函数
	length=0;
	setArray=new Object[maxSize];
}

public Set(int n){//带初始长度参数的构造函数
	if(n<=0){
		System.out.println("数组长度必须大于0!");
		System.exit(1);
	}
	length=0;
	setArray=new Object[n];
}

2.向集合插入一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean add(Object ob,int n){ //向线性表给定位置插入一个元素
		if(n<1||n>length+1){
			System.out.println("参数不合法！");
			return false;
		}
		if(length==setArray.length){//数组空间已经用完
			Object b[]=new Object[length*2];  //扩充
			for(int i=0;i<length;i++) b[i]=setArray[i]; //复制
			setArray=b;
		}
		for(int i=length;i>=n;i--)
			setArray[i]=setArray[i-1];
		setArray[n-1]=ob;
		length++;
		return true;
	}

3.从集合里删除一个元素

1
2
3
4
5
6
7
8
9
10
public boolean remove(Object ob){
		int i;
		for(i=0;i<length;i++)  //查找待删除的元素
			if(setArray[i].equals(ob)) break;
		if(i<length){
			setArray[i]=setArray[length-1];//把集合最后一个元素赋给被删元素的位置
			length--;
			return true;
		}else return false;
	}

4.判断一个元素是否属于集合

1
2
3
4
5
public boolean contains(Object ob){
		for(int i=0;i<length;i++)
			if(setArray[i].equals(ob)) return true;
		return false;
	}

5.返回集合第i个元素的值

1
2
3
4
5
6
7
public Object value(int i){
		if(i<=0||i>length){
			System.out.println("i应该在1和"+length+"之间");
			return null;
		}
		return setArray[i-1];//第i个元素对应下标为i-1
	}

6.从集合中按值查找元素

1
2
3
4
5
public Object find(Object ob){//从集合中按值查找元素
		for(int i=0;i<length;i++)
			if(setArray[i].equals(ob)) return setArray[i];
		return null;
	}

7.返回集合的长度

1
public int size(){return length;}

8.判断集合是否为空

1
public boolean isEmpty(){return length==0;}

9.输出集合中所有元素

1
2
3
4
5
public void output(){//输出集合中所有元素
		for(int i=0;i<length;i++)
			System.out.print(setArray[i].toString()+" ");
		System.out.println();
	}

10.求两个集合的并集

1
2
3
4
5
6
7
8
9
10
public Set union(Set set){// 求两个集合的并集
		Set setTemp=new Set(setArray.length);
		int i;
		for(i=0;i<length;i++)
			setTemp.setArray[i]=setArray;
		setTemp.length=length;
		for(i=0;i<set.length;i++)
			setTemp.add(set.setArray[i]);
		return setTemp;
	}

11.求两个集合的交集

1
2
3
4
5
6
7
8
9
public Set intersection(Set set){//求两个集合的交集
		int x;
		if(length<set.length) x=length;else x=set.length;
		Set setTemp=new Set(x);
		for(int i=0;i<set.length;i++)
			if(contains(set.setArray[i])) 
				setTemp.setArray[setTemp.length++]=set.setArray[i];
		return setTemp;
	}

12.清除集合中所有元素

1
public void clear(){length=0;} //清除集合所有元素

实现代码

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
public class Set {
	final int maxSize=20; //假定存储集合的数组的初始长度为20
	private Object setArray[]; //定义存储集合的数组的引用对象
	private int length;//定义数组中所保存集合的当前长度
	public Set(){
		length=0;
		setArray=new Object[maxSize];
	}
	public Set(int n){
		if(n<=0){
			System.out.println("数组长度必须大于0!");
			System.exit(1);
		}
		length=0;
		setArray=new Object[n];
	}
	public boolean add(Object ob){
		for(int i=0;i<length;i++)
			if(setArray[i].equals(ob)) return false; //元素已经存在
		
		if(length==setArray.length){//数组空间已经用完
			Object b[]=new Object[length*2];  //扩充
			for(int i=0;i<length;i++) b[i]=setArray[i]; //复制
			setArray=b;
		}
		setArray[length]=ob;
		length++;
		return true;
	}
	public boolean remove(Object ob){
		int i;
		for(i=0;i<length;i++)  //查找待删除的元素
			if(setArray[i].equals(ob)) break;
		if(i<length){
			setArray[i]=setArray[length-1];//把集合最后一个元素赋给被删元素的位置
			length--;
			return true;
		}else return false;
	}
	public boolean contains(Object ob){ //判断一个元素是否属于集合
		for(int i=0;i<length;i++)
			if(setArray[i].equals(ob)) return true;
		return false;
	}
	public Object value(int i){ //返回集合中第i个元素
		if(i<=0||i>length){
			System.out.println("i应该在1和"+length+"之间");
			System.exit(1);
		}
		return setArray[i-1];//第i个元素对应下标为i-1
	}
	public Object find(Object ob){//从集合中按值查找元素
		for(int i=0;i<length;i++)
			if(setArray[i].equals(ob)) return setArray[i];
		return null;
	}
	public int size(){return length;}//返回集合的长度
	
	public boolean isEmpty(){return length==0;}//判断集合是否为空
	
	public void output(){//输出集合中所有元素
		for(int i=0;i<length;i++)
			System.out.print(setArray[i].toString()+" ");
		System.out.println();
	}
	
	public Set union(Set set){// 求两个集合的并集
		Set setTemp=new Set(setArray.length);
		int i;
		for(i=0;i<length;i++)
			setTemp.setArray[i]=setArray[i];
		setTemp.length=length;
		for(i=0;i<set.length;i++)
			setTemp.add(set.setArray[i]);
		return setTemp;
	}
	public Set intersection(Set set){//求两个集合的交集
		int x;
		if(length<set.length) x=length;else x=set.length;
		Set setTemp=new Set(x);
		for(int i=0;i<set.length;i++)
			if(contains(set.setArray[i])) 
				setTemp.setArray[setTemp.length++]=set.setArray[i];
		return setTemp;
	}
	public void clear(){length=0;} //清除集合所有元素
	
}

喜欢这篇文章？打赏一下作者吧

数据结构-线性表-链接存储
算法-递推
关注我

链接

分类

标签云

C++ Python 爬虫

最新文章

归档

标签

C++ 4
Python 1
爬虫 1

最新文章

归档

标签

C++ 4
Python 1
爬虫 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×