Java数据结构之线性表的生成与操作_java数据结构建表操作

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

我是学c++的。在学校选课，想着学完了c的数据结构来学java。结果发现，java语法忘了差不多的。如果学弟学妹要面临选择，一定要先决定自己选择的方向，先别急着学完所有的语言。学精一门语言非常地重要！！！

---

提示：以下是本篇文章正文内容，下面案例可供参考

本篇博客将提供以下功能的代码：

• 建立线性表的顺序存储结构
• 链式存储结构并实现线性表的初始化、插入等基本运算
• 实现单链表的逆转

代码

废话不多说，直接上代码
链表接口

//提供链表接口
public abstract interface LList<T> {
	//将线性表清空
	void clear();
	//判断线性表是否为空
	boolean isEmpty();
	//返回线性表的长度
	int size();
	//返回第i个元素
	T get(int i);
	//设置第i个元素值为x
	void set(int i,T x);
	//插入x作为第i个元素
	void add(int i,T x);
	//直接尾插
	void add(T x);
	//删除第i个元素并返回被删除对象
	T remove(int i);
	//查找，返回首次出现的关键字为key的元素
	int indexof(T x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

链表结点类

//创建结点类
public class Node<T> {
	 T data;
	//Java内没有指针的定义
	//Java的引用是指向一个对象，它是占一个新内存的；
	//而C++的引用则是指向同一个内存的另外一个名字，也就是常说的别名。
	 Node<T> next;
	 public Node(T data,Node next)
	 {
		 this.data=data;
		 this.next=next;
	 }
	 public Node(T data)
	 {
		 this.data=data;
		 this.next=null;
	 }
     public Node()
	 {
		 this.data=null;
		 this.next=null;
	 }
}


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

链表实现类

//创建带头节点的单向链表
public class SLinkedList<T> implements LList<T> {
	private Node<T> head=new Node<T>();
	
	//单链表怎么清空?
	@Override
	public void clear() {
		this.head.next=null;
	}

	@Override
	public boolean isEmpty() {
		return this.head.next==null;
	}

	@Override
	public int size() {
		assert(!this.isEmpty());
		int size=0;
		Node<T> tmp=this.head.next;
		while(tmp!=null)
		{
			size++;
			tmp=tmp.next;
			
		}
	
		return size;
	}

	@Override
	public T get(int i) {
		assert(!this.isEmpty());
		Node<T> ret=new Node<>();

		//判断是否合法
		if(i>=1&&i<=this.size())
		{
			Node<T> tmp=this.head;
			//找到第i个位置前的一个结点
			for(int j=1;j<=i-1;j++)
			{
				tmp=tmp.next;
			}
			ret=tmp.next;
		}
		
		return ret.data;
	}

	@Override
	public void set(int i, T x) {
		assert(!this.isEmpty());
		

		//判断是否合法
		if(i>=1&&i<=this.size())
		{
			Node<T> tmp=this.head;
			//找到第i个位置前的一个结点
			for(int j=1;j<=i-1;j++)
			{
				tmp=tmp.next;
			}
			tmp.next.data=x;
		}
		
	}

	//表示在第几位插入
	@Override
	public void add(int i, T x) {
		Node<T> newnode=new Node<>(x,null);
		//链表为空
		if(this.head.next==null)
		{
			this.head.next=newnode;
		}
		//链表不为空
		else
		{
			//判断是否合法
			if(i>=1&&i<=this.size())
			{
				Node<T> tmp=this.head;
				//找到第i个位置前的一个结点
				for(int j=1;j<=i-1;j++)
				{
					tmp=tmp.next;
				}
				newnode.next=tmp.next;
				tmp.next=newnode;
				
			}
		}
		
	}
	@Override
	public void add(T x){
		Node<T> newnode=new Node<>(x,null);
		//链表为空
		if(this.head.next==null)
		{
			this.head.next=newnode;
		}
		else
		{
			Node<T> tmp=this.head;
			while(tmp.next!=null)
			{
				tmp=tmp.next;
			}
			tmp.next=newnode;
		}
	}
	
	@Override
	public T remove(int i) {
		assert(!this.isEmpty());
		Node<T> ret=new Node<>();

		//判断是否合法
		if(i>=1&&i<=this.size())
		{
			Node<T> tmp=this.head;
			//找到第i个位置前的一个结点
			for(int j=1;j<=i-1;j++)
			{
				tmp=tmp.next;
			}
			ret=tmp.next;
			tmp.next=tmp.next.next;
		}
		
		return ret.data;
	}

	//查找，返回首次出现的关键字为key的元素
	@Override
	public int indexof(T x) {
		assert(!this.isEmpty());
		
        for(int j=1;j<=this.size();j++)
        {
        	if(this.get(j)==x)
        	{
        		return j;
        	}
        }
		return -1;
		
	}
    
	
	//实现单链表的逆转
	public void reverse()
	{
		if(!this.isEmpty())
		{
			Node<T> prev=new Node<>();
			Node<T> cur=this.head.next;
			Node<T> next=new Node<>();
			while(cur!=null)
			{
				
				next=cur.next;
				cur.next=prev;
				prev=cur;
				cur=next;
				
			}
			
			this.head.next=prev;
			
		}
		
	}

}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

顺序表的实现类

public class SeqList<T> implements LList<T> {

	private Object arr[];
	private int len=0;
	private int capacity=4;
	//构造函数
	//无参
	SeqList()
	{
		this.arr=new Object[capacity];
	}
	//有参
	SeqList(int newcapacity)
	{
		this.arr=new Object[newcapacity];
	}
	
	//清空顺序表
	@Override
	public void clear() {
		Object obj[]=new Object[4];
		this.arr=obj;
	}

	@Override
	public boolean isEmpty() {
		return this.len==0;
	}

	@Override
	public int size() {
		return this.len;
	}

	//返回第i个元素
	@Override
	public T get(int i)
	{
		assert(!this.isEmpty());
		//判断下标是否合法
		if(i>=0&&i<this.len)
			return (T) this.arr[i];
		else
			return null;
	}

	
	@Override
	public void set(int i, T x) {
		assert(!this.isEmpty());
		if(i>=0&&i<this.len)
			this.arr[i]=x;
	}

	//从某一特定位置插入元素
	@Override
	public void add(int i, T x) {
	//1.考虑增容
		if(++this.len==this.capacity)
		{
			int newcapacity=capacity*2;
			Object obj[]=new Object[newcapacity];
			for(int j=0;j<this.len;j++)
				obj[j]=this.arr[j];
			this.arr=obj;
			this.capacity=newcapacity;
		}
	//2.找到特点位置进行插入
		//从后往前地插入
		for(int j=this.len-2;j>=i;j--)
		{
			this.arr[j+1]=this.arr[j];
		}
		this.arr[i]=x;
	}

	//直接尾插
	@Override
	public void add(T x) {
		//1.考虑增容
		if(this.len==this.capacity)
		{
			int newcapacity=capacity*2;
			Object obj[]=new Object[newcapacity];
			for(int i=0;i<this.len;i++)
				obj[i]=this.arr[i];
			this.arr=obj;
			this.capacity=newcapacity;
		}
		this.arr[this.len++]=x;
	}

	//移除第i个位置的元素
	@Override
	public T remove(int i) {
		T ret=(T)this.arr[i];
		for(int j=i+1;j<this.len;j++)
		{
			this.arr[j-1]=this.arr[j];
		}
		this.len--;
		return ret;
	}

	@Override
	public int indexof(T x) {
	   for(int i=0;i<this.len;i++)
	   {
		   if((T)this.arr[i]==x)
			   return i;
	   }
	   return -1;
	}
	

}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

测试类

public class Test {
	
	public static void main(String[] args) 
	{
		/*
		SLinkedList<Integer> slinkedList=new SLinkedList<>();
		slinkedList.add(1);
		slinkedList.add(2);
		slinkedList.add(3);
		slinkedList.add(4);
		slinkedList.add(5);
		slinkedList.add(6);
		for(int i=1;i<=slinkedList.size();i++)
		{
			System.out.println("第"+i+"位置的元素是"+slinkedList.get(i));
		}
		
		boolean ie=slinkedList.isEmpty();
		if(ie==true)
			System.out.println("单链表为空");
		else
			System.out.println("单链表不为空");
		//返回线性表的长度
		int size=slinkedList.size();
		System.out.println("单链表的长度为"+size);
		//返回第i个元素
		int ret1=slinkedList.get(3);
		System.out.println("单链表第3个位置的元素为"+ret1);
		//设置第i个元素值为x
		slinkedList.set(3,7);
		ret1=slinkedList.get(3);
		System.out.println("单链表第3个位置的元素为"+ret1);
		//插入x作为第i个元素
		slinkedList.add(3,5);
	     for(int i=1;i<=slinkedList.size();i++)
			{
				System.out.println("增加元素后第"+i+"位置的元素是"+slinkedList.get(i));
			}
			
		
		//删除第i个元素并返回被删除对象
		int ret2=slinkedList.remove(4);
		 for(int i=1;i<=slinkedList.size();i++)
			{
				System.out.println("删除元素后第"+i+"位置的元素是"+slinkedList.get(i));
			}
			
		//查找，返回首次出现的关键字为key的元素
		int ret3=slinkedList.indexof(5);
		System.out.println("首次出现关键字为key的元素的位置是"+ret3);
		for(int i=1;i<=slinkedList.size();i++)
		{
			System.out.println("单链表逆转前：第"+i+"位置的元素是"+slinkedList.get(i));
		}
		
		slinkedList.reverse();
		for(int i=1;i<slinkedList.size();i++)
		{
			System.out.println("单链表逆转后：第"+i+"位置的元素是"+slinkedList.get(i));
		}
		*/
	
		System.out.println("----------------------------------");
		SeqList<Integer> seqList=new SeqList<>();
		seqList.add(1);
		seqList.add(2);
		seqList.add(3);
		seqList.add(4);
		seqList.add(5);
		seqList.add(6);
		for(int i=0;i<seqList.size();i++)
		{
			System.out.println("第"+i+"位置的元素是"+seqList.get(i));
		}
		
		boolean sie=seqList.isEmpty();
		if(sie==true)
			System.out.println("顺序表为空");
		else
			System.out.println("顺序表不为空");
		//返回线性表的长度
		int ssize=seqList.size();
		System.out.println("顺序表的长度为"+ssize);
		//返回第i个元素
		int sret1=seqList.get(3);
		System.out.println("顺序表第3个位置的元素为"+sret1);
		//设置第i个元素值为x
		seqList.set(3,7);
		sret1=seqList.get(3);
		System.out.println("顺序第3个位置的元素为"+sret1);
		//插入x作为第i个元素
		seqList.add(3,5);
	     for(int i=0;i<seqList.size();i++)
			{
				System.out.println("增加元素后第"+i+"位置的元素是"+seqList.get(i));
			}
			
		
		//删除第i个元素并返回被删除对象
		int sret2=seqList.remove(4);
		 for(int i=0;i<seqList.size();i++)
			{
				System.out.println("删除元素后第"+i+"位置的元素是"+seqList.get(i));
			}
			
		//查找，返回首次出现的关键字为key的元素
		int sret3=seqList.indexof(5);
		System.out.println("首次出现关键字为key的元素的位置是"+sret3);
		
		
		
		
	}

}

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116