发表更新技术博客

Java 多线程学习中遇到的一个有趣的问题

今天随便写了一个线程之间相互调度的程序，代码如下：

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
class First extends Thread
{
	public First()
	{
		start();
	}
	
	synchronized public void run()
	{
		try
		{
			wait();
		}
		catch(InterruptedException e)
		{
			e.printStackTrace();
		}
		try
		{
			sleep(2000);
		}
		catch(InterruptedException e)
		{
			e.printStackTrace();
		}
		System.out.println("hello world~");
	}
}

class Second extends Thread
{
	First first;
	public Second(First first)
	{
		this.first = first;
		start();
	}
	
	synchronized public void run()
	{
		try
		{
			wait();
		}
		catch (InterruptedException e1)
		{
			e1.printStackTrace();
		}
		synchronized( first )
		{
			try
			{
				sleep(2000);
				System.out.println("I'm faster than first~");
			}
			catch(InterruptedException e)
			{
				e.printStackTrace();
			}
			first.notifyAll();
		}
	}
}

public class Main
{
	public static void main(String[] args) throws InterruptedException
	{
		First first = new First();
		Second second = new Second(first);
		synchronized( second )
		{
			System.out.println("I'm faster than second~");
			second.notifyAll();
		}
	}
}

本以为输出会很顺畅，但是出现的问题是，只输出了一行：I’m faster than second~

程序就一直处于无响应状态，纠结了好久终于想明白是这么一回事：在main函数中，对second.notifyAll()的调用早于second中的wait（）调用（因为是多线程并行，故函数响应时间与代码先后顺序无关），这样先唤醒了second，紧接着second才开始wait，因此就处于无响应状态。

改进方法：只要在second.notifyAll()调用之前空出一点时间先让second的wait调用开始即可，事实上，这段时间如此之短以至于在我电脑上只需要在之前加一行输出语句即可。为了保险起见，还是多加了个sleep，改进后代码如下：

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
class First extends Thread
{
	public First()
	{
		start();
	}
	
	synchronized public void run()
	{
		try
		{
			wait();
		}
		catch(InterruptedException e)
		{
			e.printStackTrace();
		}
		try
		{
			sleep(2000);
		}
		catch(InterruptedException e)
		{
			e.printStackTrace();
		}
		System.out.println("hello world~");
	}
}

class Second extends Thread
{
	First first;
	public Second(First first)
	{
		this.first = first;
		start();
	}
	
	synchronized public void run()
	{
		try
		{
			wait();
		}
		catch (InterruptedException e1)
		{
			e1.printStackTrace();
		}
		synchronized( first )
		{
			try
			{
				sleep(2000);
				System.out.println("I'm faster than first~");
			}
			catch(InterruptedException e)
			{
				e.printStackTrace();
			}
			first.notifyAll();
		}
	}
}

public class Main
{
	public static void main(String[] args) throws InterruptedException
	{
		First first = new First();
		Second second = new Second(first);
		System.out.println("wating for all threads prepared~");
		Thread.sleep(2000);
		synchronized( second )
		{
			System.out.println("I'm faster than second~");
			second.notifyAll();
		}
	}
}

输出结果：

1
2
3
4
wating for all threads prepared~
I’m faster than second~
I’m faster than first~
hello world~
发表更新技术博客

文件夹遍历 Java 版

Java下的File类（文件类，其实感觉文件类有点误导性，用“文件路径”会好一点）有list方法，会返回指定路径下所有文件和目录，用这个方法以及简单的递归可以写出一个简陋的文件遍历程序

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
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class test_for_team_study_2
{
	public static void traverse(String name, FileWriter wt) throws IOException
	{
		wt.write(name + "\r\n");
		File path = new File(name);
		String[] list = path.list();
		if( null == list )
			return ;
		for(int i = 0; i < list.length; i ++)
			if( -1 == list[i].indexOf(".") )
				traverse(name + "/" + list[i], wt);
	}
	
	public static void main(String[] args) throws IOException
	{
		FileWriter wt = new FileWriter("C:/Users/Administrator/Desktop/file in D.out");
		String name = "D:/";
		File path = new File(name);
		String[] list = path.list();
		for(int i = 0; i < list.length; i ++)
		{
			wt.write("now is the file#:" + i + "\r\n==========================\r\n");
			traverse(name + "/" + list[i], wt);
			wt.write("\r\n\r\n\r\n");
		}
		wt.flush();
		wt.close();
		System.out.println("finished!");
	}
}
发表更新技术学习

JAVA 设置 JTable 表格的可编辑性

有时候，我们需要设置JTable表格某些行某些列不可编辑以保证数据准确，用DefaultTableModel初始化的话，需要重写它的public boolean isCellEditable(int, int)方法，写法简单呈现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DefaultTableModel myModel = new DefaultTableModel(dataOfOrder, headOfOrder)	//实例化表格模式
{
    /**
     * 
     */
    private static final long serialVersionUID = 1L;

    public boolean isCellEditable(int rowIndex, int columnIndex) 	//重写方法改编可编辑性
    {
        if( columnIndex == getColumnCount() - 1 )
            return true;
        return false;
    }
};

上述写法是设置只有表格的最后一列可编辑，其他列不可编辑。有了rowIndex和columnIndex这两个参数，可以随意的设置可编辑范围。

注意要达到目的，定义另一个类继承DefaultTableModel，之后在类中重写方法是不可行的！

发表更新技术学习

Java 窗体中按钮布局问题

在Java窗体中，有时需要对按钮的设置进行布局，这时使用GridLayout(x, y)会很方便，意思是把窗口划分为x行y列的小格子，在add的时候就是一行一行的填充，这样可以是按钮得到标准化布局

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
import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.Toolkit;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class test_for_blog  extends JFrame
{
	/**
	 * 
	 */
	private static final long serialVersionUID = 5136083409273453255L;
	
	private static int JFwidth = 450;
	private static int JFheight = 350;
	
	JPanel panel = null;
	
	JButton btnAdd = null;
	JButton btnDelete = null;
	
	public test_for_blog()
	{
		super("按钮添加测试");
		
		panel = new JPanel();
		
		btnAdd = new JButton("Add");
		btnDelete = new JButton("Delete");
		
		panel.setLayout( new GridLayout(1, 2) );
		panel.add(btnAdd);
		panel.add(btnDelete);
		this.getContentPane().add(panel, BorderLayout.SOUTH);
	}
	
	public static void main(String[] args)
	{
		test_for_blog test = new test_for_blog();
		Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();	//获取显示屏尺寸
		test.setBounds((screenSize.width - JFwidth) / 2, (screenSize.height - JFheight) / 2, JFwidth, JFheight);	//使程序窗口居中
		test.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);	//窗口设为可关闭
		test.setResizable(false);	//窗口设为不可调节大小
		test.setVisible(true);	//窗口设为可见
	}
}
发表更新算法设计

POJ 3255 Roadblocks （次短路问题）

解法有很多奇葩的地方，比如可以到达终点再跳回去再跳回来（比如有两个点）。。。。反正就是不能有最短路，不过没关系，算法都能给出正确结果

思想：和求最短路上的点套路一样，spfa先正着求一次，再反着求一次最短路，然后枚举每条边<i,j>找dist_zheng[i] + len<i,j> + dist_fan[j]的第二小值即可！注意不能用邻接矩阵，那样会MLE，应该用邻接表

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
/*
poj    3255
3808K	266MS
*/

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>

#define MAXN 200005
#define MAX_INT 2147483647

using namespace std;

int last[5005], dist_1[5005], dist_2[5005], n, m, gra[5005][5005];
bool mark[MAXN];

struct node
{
	int u;
	int v;
	int w;
	int next;
	node()
	{
		u = v = w = next = 0;
	}
}edge[MAXN];

void spfa( int dist[5005], int s )
{
	queue<int>myQueue;
	dist[s] = 0;
	memset(mark, false, sizeof(mark));
	mark[s] = true;
	myQueue.push(s);
	while( !myQueue.empty() )
	{
		int x = myQueue.front();
		myQueue.pop();
		mark[x] = false;
		int t = last[x];
		while( t )
		{
			if( dist[ edge[t].v ] > dist[x] + edge[t].w  )
			{
				dist[ edge[t].v ] = dist[x] + edge[t].w;
				if( !mark[ edge[t].v ] )
					myQueue.push( edge[t].v );
			}
			t = edge[t].next;
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		edge[i].u = edge[i + m].v = a;
		edge[i].v = edge[i + m].u = b;
		edge[i].w = edge[i + m].w = c;
		edge[i].next = last[a];
		last[a] = i;
		edge[i + m].next = last[b];
		last[b] = i + m;
	}
	memset( dist_1, 1, sizeof(dist_1) );
	spfa( dist_1, 1 );
	memset( dist_2, 1, sizeof(dist_2) );
	spfa( dist_2, n );
	int ans = MAX_INT, tmp = MAX_INT;
	for(int i = 1;i <= n;i ++)
	{
		int t = last[i];
		while( t )
		{
			if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < tmp )
			{
				ans = tmp;
				tmp = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
			}
			else if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < ans 
					&& dist_1[i] + dist_2[ edge[t].v ] + edge[t].w != tmp )
				ans = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
			t = edge[t].next;
		}
	}
	cout << ans << endl;
	return 0;
}
发表更新算法设计

POJ 3093 Margaritas on the River Walk（0-1背包变形）

这题目的思路很巧妙，什么情况下剩下的所有物品都放不下呢？就是当前剩余物品中最小的那个也放不下。所以，先把物品按照容量从小到大排序，依次枚举当前背包为放不下的最小物品的情况。

对于当前物品i，必有1到i-1的所有物品都放进去，这时候比i大的物品谁放谁不放是不确定的。转换成0-1背包问题：把前i-1个物品都放进去以后，得到空间为tsum – sum[i-1]（前缀和）的包，只要从第i+1到第n个物品中拿出一个方案填充这个包使得剩余体积小于第i个物品的体积就可以了，把总方案数累加就是结果！

注意特殊情况：当排序后最小的物品也无法放入时，直接返回0，因为dp[0]初始化为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
/*
poj     3093
232K	0MS
*/
#include<cstdio>
#include<algorithm>
#include<iostream>

#define MAXN 1005

using namespace std;

int n, m, wei[35], dp[MAXN], sum[MAXN];

__int64 Bag()
{
	memset(sum, 0, sizeof(sum));
	sort( wei + 1, wei + n + 1 );
	if(wei[1] > m)	//因为很可能有最小的也放不下这种情况，而dp【0】是初始化为1的，会输出1 
		return 0;
	for(int i = 1;i <= n;i ++)
		sum[i] = sum[i-1] + wei[i];
	__int64 ans = 0;
	for(int i = 1;i <= n;i ++)
	{
		if(sum[i - 1] > m)
			break;
		memset(dp, 0, sizeof(dp));
		dp[sum[i-1]] = 1;
		for(int j = i + 1;j <= n;j ++)
			for(int k = m; k >= sum[i - 1] + wei[j]; k --)
				dp[k] += dp[k - wei[j]];

		for(int j = m - wei[i] + 1;j <= m;j ++)
			ans += dp[j];
	}
	return ans;
}

int main()
{
	int Cases;
	cin>>Cases;
	for(int cnt = 1; cnt <= Cases; cnt ++)
	{
		cin >> n >> m;
		for(int i = 1;i <= n;i ++)
			cin>> wei[i];
		cout << cnt << " " << Bag() <<endl;
	}
	return 0;
}
发表更新随笔杂谈

要开始编程了

6月准备期末考试，除了考试没有再编过程。今天院内ACM培训选拔赛，虽然手生，还是顺利通过了。这两周不用去听水课了，通过这两周找找感觉，巩固一下算法把，不要放下c++和Java的学习。一月不编程感觉水平有点下滑，很简单的题目竟然选择了很复杂的算法，还是错的，其实暴搜就可以，哎，好好练习吧

发表更新算法设计

POJ 2676 Sudoku（数独）

经典搜索问题，主要是时间上的优化，我用了三个辅助数组记录信息 row[i][k] = 1表示第i行数字k已经被使用，col[j][k] = 1表第j列数字k已经被使用，blo[i][k]表示第i个小九宫格中数字k已经被使用

还有很重要的一个优化（没有优化的话可能会超时，或者非常慢，像POJ讨论区里有很多说正着搜超时，倒着搜0ms，这的确是一个可以用的方法，但是有一定的随机性），每次填数字时，先扫描一遍整个矩阵，找出可选数字情况最少的那个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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/*
poj    2676
236K	0MS
*/ 

#include<cstdio>
#include<iostream>

#define MAXN 10
#define MAX_INT 2147483647

using namespace std;

bool flag = false;
int matrix[MAXN][MAXN], row[MAXN][MAXN], col[MAXN][MAXN], blo[MAXN][MAXN];
//用int判断比bool判断要快！ 
int area[MAXN][MAXN] = {
						{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
						{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
						{0, 7, 7 ,7, 8, 8, 8, 9, 9, 9}
						};

void solve(int cnt)
{
	if(flag)
		return ;
	if( !cnt )
	{
		flag = true;
		for(int i = 1;i <= 9;i ++)
		{
			for(int j = 1;j <= 9;j ++)
				cout<<matrix[i][j];
			cout<<endl;
		}
		return ;
	}
	int tx, ty, Min = MAX_INT;
	for(int i = 1;i <= 9;i ++)	//扫描矩阵，找到可选数字情况最少的那个0 
	{
		for(int j = 1;j <= 9;j ++)
		{
			if( !matrix[i][j] )
			{
				int times = 0;
				for(int k = 1;k <= 9;k ++)
					if( !row[i][k] && !col[j][k] && !blo[area[i][j]][k] )
						times ++;
				if(times < Min)
				{
					Min = times ;
					tx = i;
					ty = j;
				}
			}
		}
	}
	for(int k = 1;k <= 9;k ++)
	{
		if( !row[tx][k] && !col[ty][k] && !blo[area[tx][ty]][k] )
		{
			row[tx][k] = col[ty][k] = blo[area[tx][ty]][k] = 1;
			matrix[tx][ty] = k;
			solve(cnt - 1);
			matrix[tx][ty] = 0;
			row[tx][k] = col[ty][k] = blo[area[tx][ty]][k] = 0;
		}
	}
}

int main()
{
	int cases = 0, cnt = 0;
	cin>>cases;
	while(cases --)
	{
		memset(row, 0, sizeof(row));
		memset(col, 0, sizeof(col));
		memset(blo, 0, sizeof(blo));
		memset(matrix, 0, sizeof(matrix));
		flag = false;
		cnt = 0;
		for(int i = 1;i <= 9;i ++)
		{
			for(int j = 1;j <= 9;j ++)
			{
				char ch;
				cin>>ch;
				matrix[i][j] = ch - '0';
				row[i][matrix[i][j]] = 1;
				col[j][matrix[i][j]] = 1;
				blo[area[i][j]][matrix[i][j]] = 1;
				if( !matrix[i][j] )
					cnt ++;
			}
		}
		solve(cnt);
	}
	return 0;
}
发表更新技术博客

Windows 编程之文件夹遍历

利用windows的API，FindFirstFile和FileNextFile，采用递归遍历指定文件夹中的所有文件及文件夹，第一次windows编程，代码写的很臃肿难看，请大家多多包涵！

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<windows.h>

#define MAXN 100005

using namespace std;

void surf(WIN32_FIND_DATA myData)
{
	cout<<myData.ftCreationTime.dwLowDateTime<<endl;
	cout<<myData.ftLastAccessTime.dwLowDateTime<<endl;
	cout<<myData.ftLastWriteTime.dwLowDateTime<<endl;
	SYSTEMTIME ctime , atime , wtime;
	FileTimeToSystemTime(&myData.ftCreationTime , &ctime);
	FileTimeToSystemTime(&myData.ftLastAccessTime , &atime);
	FileTimeToSystemTime(&myData.ftLastWriteTime , &wtime);
	printf("%d年%d月%d日%d时%d分%d秒\n"
		 , ctime.wYear , ctime.wMonth , ctime.wDay , ctime.wHour , ctime.wMinute , ctime.wSecond);
	printf("%d年%d月%d日%d时%d分%d秒\n"
		 , atime.wYear , atime.wMonth , atime.wDay , atime.wHour , atime.wMinute , atime.wSecond);
	printf("%d年%d月%d日%d时%d分%d秒\n"
		 , wtime.wYear , wtime.wMonth , wtime.wDay , wtime.wHour , wtime.wMinute , wtime.wSecond);
	cout<<endl<<endl;
}

void traverse(char *Str)
{
	WIN32_FIND_DATA myData;
	HANDLE hFind = INVALID_HANDLE_VALUE;
	char str[MAX_PATH] = {0};
	strcpy(str , Str);
	strcat(str , "/*");		//使用通配符进行匹配 
	hFind = FindFirstFile(str , &myData);
	if(INVALID_HANDLE_VALUE == hFind)
		return ;
	while(FindNextFile(hFind , &myData))
	{
		if(myData.cFileName[0] != '.')		//非返回目录时进行下一步 
		{
			cout<<"========="<<myData.cFileName<<"=========="<<endl; 
			surf(myData);
			if(myData.dwFileAttributes == FILE_ATTRIBUTE_DIRECTORY)		//判断是否为文件夹 
			{
				char dir[MAX_PATH] = {0};
				snprintf(dir , MAX_PATH, "%s/%s" , Str , myData.cFileName);	//构造路径 
				traverse(dir);
			}
		}
	}
	FindClose(hFind);	//关闭句柄 
}

int main()
{
	char *str = "./test";
	traverse(str);
}

我的当前目录下的test文件夹有“haha”文件夹以及test.1 , test , 2 , test , 3三个文件,”haha”文件夹里又含有“ai”文件夹以及haha.1 , haha.2 , haha.3三个文件，“ai”文件夹里又含有“wo”文件夹以及ai.1 , ai.2 , ai.3三个文件，”wo”文件夹里有wo.1 , wo.2 , wo.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
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
=========haha==========
1556376338
2156419021
2156419021
2014年5月31日10时16分18秒
2014年5月31日10时24分27秒
2014年5月31日10时24分27秒


=========ai==========
2147248496
772195107
772195107
2014年5月31日10时24分27秒
2014年5月31日11时26分34秒
2014年5月31日11时26分34秒


=========ai.1==========
2197291359
2197291359
2197291359
2014年5月31日10时24分32秒
2014年5月31日10时24分32秒
2014年5月31日10时24分32秒


=========ai.2==========
2197291359
2328198846
2328198846
2014年5月31日10时24分32秒
2014年5月31日10时24分45秒
2014年5月31日10时24分45秒


=========ai.3==========
2197291359
2387262224
2387262224
2014年5月31日10时24分32秒
2014年5月31日10时24分51秒
2014年5月31日10时24分51秒


=========wo==========
752914004
2835575798
2835575798
2014年5月31日11时26分33秒
2014年5月31日15时40分33秒
2014年5月31日15时40分33秒


=========wo.1==========
806557072
806557072
806557072
2014年5月31日11时26分38秒
2014年5月31日11时26分38秒
2014年5月31日11时26分38秒


=========wo.2==========
870010701
870010701
870010701
2014年5月31日11时26分44秒
2014年5月31日11时26分44秒
2014年5月31日11时26分44秒


=========wo.3==========
870010701
923383754
923383754
2014年5月31日11时26分44秒
2014年5月31日11时26分50秒
2014年5月31日11时26分50秒


=========haha.1==========
1601118898
1601118898
1601118898
2014年5月31日10时16分22秒
2014年5月31日10时16分22秒
2014年5月31日10时16分22秒


=========haha.2==========
1601118898
1678113301
1678113301
2014年5月31日10时16分22秒
2014年5月31日10时16分30秒
2014年5月31日10时16分30秒


=========haha.3==========
1601118898
1742136963
1742136963
2014年5月31日10时16分22秒
2014年5月31日10时16分36秒
2014年5月31日10时16分36秒


=========test.1==========
1835930690
1835930690
1601118898
2014年5月31日10时23分55秒
2014年5月31日10时23分55秒
2014年5月31日10时16分22秒


=========test.2==========
1924505756
1924505756
1678113301
2014年5月31日10时24分4秒
2014年5月31日10时24分4秒
2014年5月31日10时16分30秒


=========test.3==========
1924535758
1924535758
1742136963
2014年5月31日10时24分4秒
2014年5月31日10时24分4秒
2014年5月31日10时16分36秒
发表更新技术学习

数据结构学习之二叉排序树

介绍：二叉排序树是以一定的规则排列树中元素，因而可以进行快速的排序和查询的树状数据结构，一般规则是：对于树中任意一个节点，左孩子严格小于根，根严格小于右孩子，有点像大根堆。（只是大根堆中左右孩子关系并不确定，且和根的关系是统一的，而且有上浮和下沉操作使得大根堆总是一棵完全二叉树，其不断弹出堆顶形成有序列的过程叫做堆排序。虽然二叉排序树中也有旋转操作使得树尽量平衡，但是由于数值大小分明的左右孩子，在进行平衡操作时远不如大根堆方便快捷。）对于一棵已经构造完成的排序二叉树，它的中序遍历序列即为升序排列的有序列，这就是二叉排序树的排序方法。

基本操作：二叉排序树的基本操作为查找、插入和删除。查找操作以及插入操作过程同二分查找类似，用待处理节点和当前节点进行数值比较，如果待处理节点的值小于当前节点的值，则进入当前节点的左子树进行操作，否则进入当前节点的右子树进行操作，直到到达叶子节点或者操作完成。删除操作有好几种实现方法，我是用的是“替罪羊节点法”，即从待删除节点的左子树中找到最大的一个节点（即“替罪羊节点”），用它的值覆盖待删除节点的值，然后删除替罪羊节点即可。在具体操作中还有许多需要注意的细节，在代码注释中有详细介绍。

一些想法：在最初的代码实现中，曾使用静态树，因为考虑到在处理大型数据时，重复的new或者malloc操作会使得程序慢的令人发指（并不是说指针慢，只是申请空间的过程耗费时间），所以一开始就开一段长度合适的空间，另外设置一个指针指示当前数组中可以用的节点，然后new操作在这里的实现就可以这样写：tmp->lc = &Tree[++index]，如果当前序列空间不够时，再用malloc或new申请另一段空间，有点类似内存池的概念。这样的静态操作经在线评测系统（POJ）测试，在进行最基本的操作来处理100，000左右的数据量时会快上两个甚至更多的数量级。静态树的查找和插入操作都可以正常进行，但是在进行删除操作时，我自己写的回收空间算法（为了节省空间，删除的节点重新归到可用空间中，想法是把待删除节点和当前排序树二叉树用的最后一个节点进行交换，再把上文提到的指针前移一位即可，代码实现可以写成：swap(*tmp , Tree[index–])。）总是不能正确执行，调了一段时间未果就先放在一边，写现在这个用指针操作实现的排序二叉树。

代码：（内置测试数据，并对于测试数据保证代码正确）

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<iostream>
#include<algorithm>

#define MAXN 10005
#define MAX_INT 2147483647
#define LC(x) (x << 1)
#define RC(x) ((x << 1) | 1)
#define MID(x,y) ( (x + y) >> 1 )
#define TIME_BEGIN double t1 = clock()
#define TIME_END double t2 = clock();printf("\n%.2fms\n",t2-t1)

using namespace std;

struct node	//结构体定义
{
	int data;
	node *lc , *rc , *fa;
	node()//初始化 
	{
		data = -1;
		lc = rc = fa = NULL;
	}
};
node *root = new node;;

int ary[15] = {0,213,5,12,45,65,2,1,4,8,6,554,52,-1},n = 12;

void myFind(int now , node *&tmp)//查询函数（从参数节点返回信息） 
{
	tmp = root;
	while(tmp)
	{
		if(now > tmp->data)	//查询值大于当前节点值，进入右子树 
			tmp = tmp->rc;
		else if(now < tmp->data)//查询值小于当前值，进入左子树 
			tmp = tmp->lc;
		else	//找到查询值，返回 
			return ;
	}
}

void myInsert(int now)//插入函数 
{
	node *tmp = root;
	while(1)
	{
		if(now > tmp->data)	//若待插入节点大于当前节点的值，则进入右子树 
		{
			if(!tmp->rc)//当前节点右子树为空，则将待插入节点插入到此位置 
			{
				tmp->rc = new node;
				tmp->rc->data = now;
				tmp->rc->fa = tmp;
				return ;
			}
			tmp = tmp->rc;
		}
		else if(now < tmp->data)//若待插入节点小于当前节点的值，则进入左子树 
		{
			if(!tmp->lc)//当前节点左子树为空，则将待插入节点插入到此位置 
			{
				tmp->lc = new node;
				tmp->lc->data = now;
				tmp->lc->fa = tmp;
				return ;
			}
			tmp = tmp->lc;
		}
		else	//树中已有待插入节点，则直接返回 
			return ;
	}
}

void myDelete(node *&tmp)//删除函数  （通过节点） 
/*
若想通过数值删除，则只需先调用一次myFind函数 
*/ 
/*
删除函数的思想是“替罪羊节点”思想：即在待删除节点左子树中
找到最大的节点p（即替罪羊），用它的值覆盖待删除节点的值，然后删除
p即可，其中有很多细节需要注意 
*/ 
{
	node *ano = tmp->lc;
	if(!ano)//若待删除节点没有左子树 
	{
		if(tmp == tmp->fa->lc)//若带删除节点是其父节点的左子树 
			tmp->fa->lc = tmp->rc;
		else					//若带删除节点是其父节点的右子树 
			tmp->fa->rc = tmp->rc;
		if(tmp->rc)	//不能直接访问tmp->rc的父节点，需要先判断tmp->rc是否为空 
			tmp->rc->fa = tmp->fa;
		free(tmp);
	}
	else
	{
		while(ano->rc)	//寻找左子树中的最大节点 
			ano = ano->rc;
		tmp->data = ano->data;//值覆盖 
		if(ano->lc)	//若“替罪羊”有左孩子 
		{
			if(ano->fa->data < ano->lc->data)	
			//判断“替罪羊”的左孩子和替罪羊父亲节点的大小关系 
				ano->fa->rc = ano->lc;
			else
				ano->fa->lc = ano->lc;
			ano->lc->fa = ano->fa;
		}
		else
		{
			if(ano->fa == tmp)	//判断替罪羊是左子树根还是左子树的其他节点 
				ano->fa->lc = NULL;
			else
				ano->fa->rc = NULL;
		}
		free(ano);
	}
}

void myInit()//初始化整棵树 
{
	root->data = MAX_INT;
	for(int i = 1;i <= n;i ++)
		myInsert(ary[i]);
}

void myPrint(node *tmp)//中序遍历方式输出整棵树，形成有序列 
{
	if(!tmp)
		return ;
	myPrint(tmp->lc);
	cout<<tmp->data<<" ";
	myPrint(tmp->rc);
}

void myInit_test()	//myInit测试函数
{
	cout<<endl; 
	cout<<"====myInit函数测试开始==========="<<endl;
	cout<<endl;
	myInit();
	cout<<endl;
	cout<<"====myInit函数测试结束==========="<<endl;
	cout<<endl;
}

void myPrint_test() //myPrint测试函数 
{
	cout<<endl;
	cout<<"====myPrint函数测试开始==========="<<endl;
	cout<<endl;
	myPrint(root->lc);
	cout<<endl;
	cout<<endl;
	cout<<"====myPrint函数测试结束==========="<<endl;
	cout<<endl;
}

void myFind_test() //myFind测试函数 
{
	cout<<endl;
	cout<<"====myFind函数测试开始==========="<<endl;
	cout<<endl;
	for(int i = 1;i <= n;i ++)
	{
		node *tmp;
		myFind(ary[i] , tmp);
		cout<<tmp->data<<" ";
	}
	cout<<endl;
	cout<<endl;
	cout<<"====myFind函数测试结束==========="<<endl;
	cout<<endl;
}

void myDelete_test() //myDelete测试函数 
{
	cout<<endl;
	cout<<"====myDelete函数测试开始==========="<<endl;
	cout<<endl;
	for(int i = 1;i <= n;i ++)
	{
		node *tmp;
		myFind(ary[i] , tmp);
		myDelete(tmp);
		myPrint(root->lc);
		cout<<endl;
		myInsert(ary[i]);
	}
	cout<<endl;
	cout<<"====myDelete函数测试结束==========="<<endl;
	cout<<endl;
}

int main()
{
	TIME_BEGIN; 
	myInit_test();			//myInit函数测试 
	myPrint_test();			//myFind函数测试
	myFind_test();			//myFind函数测试
	myDelete_test();		//myDelete函数测试 
	TIME_END;
}
关注我

最新文章

分类

标签

三体1
不吐不快4
书单30
分布式1
历史2
同人随笔1
图灵完备1
子夜自话1
容器1
影视评论2
数据库1
算法17
胡思乱想13
计算机学习57
读书笔记133
随笔1

归档

链接

×