数据结构上机实验

Posted on |

01 约瑟夫环问题

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
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
	int data;
	struct node *next;
}node;
node *creat(node *head, int n)
{
	int i = 1;
	node *s, *p = head;
	while (i <= n) {
		s = (node *)malloc(sizeof(node));
		s->data = i++;
		p->next = s;
		p = p->next;
	}
	p->next = head->next;
	free(head);
	return p->next;
}
int main()
{
	int i, n, m;
	node *head, *newstart, *h, *t;
	head = (node *)malloc(sizeof(node));
	printf("请输入数据长度n，数据间隔m\n");
	scanf("%d %d", &n, &m);
	newstart = creat(head, n);
	h = newstart;
	while (h != h->next)
	{
		for (i = 1; i<m; i++) {
			h = h->next;
		}
		t = h->next;
		printf("%d->\n", h->next->data);
		h->next = t->next;
		h = t->next;
		free(t);
	}
	printf("%d\n", h->data);
	return 0;
}


Markdown
02 一元多项式相加

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
#include<iostream>
using namespace std;
 struct Node
{
	double coe;//系数
	int exp;//指数
	Node *next;
};
//创建链表，节点数为一元多项式的项数
void CreatPoly(Node *&head,int n)//写成*head报错 为什么？
{
	head=(Node *)new Node;
	head->coe=0;
	head->exp=0;
	head->next=NULL;//初始化头节点
	Node *p=head;
	for(int i=0;i<n;i++){
		p->next=(Node *)new Node;//尾插法建表
		p=p->next;
		cin>>p->coe>>p->exp;
		p->next=NULL;
	}
}
//打印表
void ShowPoly(Node *head)
{
	if(head->next == NULL)
	putchar('0');
	else{
		for(Node *p=head->next;p!=NULL;p=p->next){//遍历所有节点
			if(p!=head->next&&p->coe>0)putchar('+');
			if(p->coe==1){
				if(p->exp==0)putchar('1');
			}
			if(p->coe==1&&p->exp==0)putchar('1');
			else if(p->coe==-1)putchar('-');
			else  cout<<p->coe;
			//指数为0，1时特殊处理
			switch(p->exp){
				case 0:break;
				case 1:putchar('X');break;
				default:
				p->exp<0?printf("x^(%d)",p->exp):printf("x^%d",p->exp);break;//看不懂
				break;
			}

		}
	}
	cout<<endl;
}
char comp(int a,int b)
{
	if(a>b)return '>';
	if(a<b)return '<';
	return '=';
}
//相加
void AddPoly(Node *&pA, Node *&pB) // 传进两个链表的头指针
{
Node *ha = pA;
Node *hb = pB;
Node *qa = ha->next; // ha, hb分别跟在qa, qb的后一位置
Node *qb = hb->next; // qa, qb分别指向Pa, Pb中当前比较元素
while(qa && qb)
{
double sum = 0;
int a = qa->exp;
int b = qb->exp;
switch( comp(a, b) ) {
case '<':
ha = qa;
qa = qa->next; // 非ha = ha->next;
break;
case '=':
sum = qa->coe + qb->coe;
if(sum != 0.0) {
qa->coe = sum;
ha = qa;
}
else {
if(ha->next != qa)
cout << "Error: ha->next != qa" << endl;
ha->next = ha->next->next; // 删除和为0的结点，ha不变，还在qa后一位置

}
if(hb->next != qb)
cout << "Error: hb->next != qb" << endl;
hb->next = hb->next->next;

qb = hb->next;
qa = ha->next;
break;
case '>':
hb->next = hb->next->next; // 删除qb指向的结点
qb->next = ha->next; // 将qb插入ha后qa前
ha->next = qb;
qb = hb->next; // not qb = ha->next
ha = ha->next;
break;
default:
cout << "Error!" << endl;
break;
}
}
if(qb)
ha->next = qb;

}

int  main()
{
	Node *A=NULL;
	Node *B=NULL;
	int countA;
	int countB;
	cout<<"输入A的项数"<<endl;cin>>countA;
	cout<<"输入B的项数"<<endl;cin>>countB;
	CreatPoly(A,countA);
	CreatPoly(B,countB);
	cout<<"A="<<endl;
	ShowPoly(A);
	cout<<"B="<<endl;
	ShowPoly(B);
	AddPoly(A,B);
	cout<<"A+B="<<endl;
	ShowPoly(A);
	delete(A);

}

03 栈 正则表达式运算

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
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define maxsize 1000
//中则表达式str转换为后缀表达式
void trans(char str[], char exp[])
{
	struct
	{
		char data[maxsize];
		int top;
	}op;
	char ch;
	int i = 0, t = 0;
	op.top = -1;
	ch = str[i];
	i++;
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':
			op.top++;
			op.data[op.top] = ch;
			break;
		case ')':
			while (op.data[op.top] != '(')
			{
				exp[t] = op.data[op.top];
				op.top--;
				t++;

			}
			op.top--;
			break;
		case '+':
		case '-':
			while (op.top != -1 && op.data[op.top] != '(')
			{
				exp[t] = op.data[op.top];
				op.top--;
				t++;
			}
			op.top--;
			op.data[op.top] = ch;
			break;
		case '*':
		case '/':
			while (op.data[op.top] == '*' || op.data[op.top] == '/')
			{
				exp[t] = op.data[op.top];
				op.top--;
				t++;
			}
			op.top++;
			op.data[op.top] = ch;
			break;
		case ' ':
			break;
		default:
			while (ch >= '0'&&ch <= '9')
			{
				exp[t] = ch;
				t++;
				ch = str[i];
				i++;
			}
			i--;
			exp[t] = '#';
			t++;
		}
		ch = str[i];
		i++;
	}
	while (op.top != -1)
	{
		exp[t] = op.data[op.top];
		t++;
		op.top--;
	}
	exp[t] = '\0';
}
//后缀表达式的求值
float compvalue(char exp[])
{
	struct
	{
		float data[maxsize];
		int top;
	}st;
	float d;
	char ch;
	int t = 0;
	st.top = -1;
	ch = exp[t];
	t++;
	while (ch != '\0')
	{
		switch (ch)
		{
		case '+':
			st.data[st.top - 1] = st.data[st.top - 1] + st.data[st.top];
			st.top--;
			break;
		case '-':
			st.data[st.top - 1] = st.data[st.top - 1] - st.data[st.top];
			st.top--;
			break;
		case '*':
			st.data[st.top - 1] = st.data[st.top - 1] * st.data[st.top];
			st.top--;
			break;
		case '/':
			if (st.data[st.top] != 0)
				st.data[st.top - 1] = st.data[st.top - 1] / st.data[st.top];
			else
			{
				printf("\nerror! \n");
				exit(0);
			}
			st.top--;
			break;
		default: d = 0;
			while (ch >= '0'&&ch <= '9')
			{
				d = 10 * d + ch - '0';
				ch = exp[t];
				t++;
			}
			st.top++;
			st.data[st.top] = d;
		}
		ch = exp[t];
		t++;
	}
	return st.data[st.top];
}

int main()
{
	char str[maxsize], exps[maxsize];

	printf("please input a expressions,just include +,-,*,/and integers:");
	cin >> str;//输入一个中缀表达式
	printf("old is: %s\n", str);  trans(str, exps);//转换
	printf("after is: %s\n", exps);
	printf("the result is: %g\n", compvalue(exps)); //求值并输出
	return 0;
}

![])(http://i1.piimg.com/567571/a11fae0ace0176df.png)

04 车厢排序问题

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

#include <iostream>  
using namespace std;

template<class T>
class My_queue;

template<class T>
class Node
{
private:
	T data;
	Node<T> *next;
public:
	Node()
	{
		next = 0;
	}
	Node(T d)
	{
		data = d;
		next = 0;
	}
	friend My_queue<T>;
};

template<class T>
class My_queue
{
private:
	Node<T> *tail;
public:
	My_queue()
	{
		tail = new Node<T>();
		tail->next = tail;
	}

	bool empty()
	{
		return (tail->next == tail);
	}

	void push(T d)
	{
		Node<T> *p = new Node<T>(d);
		p->next = tail->next;
		tail->next = p;
		tail = p;
	}

	T front()
	{
		if (empty())
		{
			cout << "queue is empty!" << endl;
			exit(0);
		}
		Node<T> *p = tail->next;
		T data = p->next->data;
		return data;
	}

	T back()
	{
		if (empty())
		{
			cout << "queue is empty!" << endl;
			exit(0);
		}
		T data = tail->data;
		return data;
	}

	void pop()
	{
		Node<T> *p = tail->next;
		Node<T> *q = p->next;
		p->next = q->next;
		if (q == tail)
			tail = p;
		delete q;
	}

};

void OutPut(int& minH, int& minQ, My_queue<int> H[], int k, int n);
bool Hold(int c, int& minH, int& minQ, My_queue<int> H[], int k);

bool Rail_Road(int p[], int n, int k)
{
	//k个缓冲轨，车厢初始排序为p[1...n]  

	//创建与缓冲轨对应的队列  
	My_queue<int> *H;
	H = new My_queue<int>[k];

	int NowOut = 1; //下一次要出轨的车厢  
	int minH = n + 1; //缓冲轨中编号最小的车厢  
	int minQ = k; //编号最小的车厢所在缓冲轨的编号  

				  //车厢重排序  
	for (int i = 0; i<n; i++)
	{
		if (p[i] == NowOut)
		{
			cout << "Move car " << p[i] << " from input to output" << endl;
			NowOut++;

			//从缓冲轨中输出  
			while (minH == NowOut)
			{
				OutPut(minH, minQ, H, k, n);
				NowOut++;
				if (NowOut == n + 1) //输出全部车厢后返回  
					return true;
			}
		}
		else
		{
			//将p[i]放入某个缓冲轨  
			if (!Hold(p[i], minH, minQ, H, k))
				return false;
		}
	}
	return true;
}

void OutPut(int& minH, int& minQ, My_queue<int> H[], int k, int n)
{
	//该函数实现把一节车厢从缓冲轨送至出轨处  
	//同时修改minH minQ的值  

	int c;

	//从队列中pop掉编号最小的车厢minH  
	c = H[minQ].front();
	H[minQ].pop();

	cout << "Move car " << c << " from holding queue " << minQ + 1 << " to output " << endl;

	//检查所有队列，搜索新的minH minQ  
	minH = n + 1;

	for (int i = 0; i<k; i++)
		if ((!H[i].empty()) && (H[i].front()<minH))
		{
			minH = H[i].front();
			minQ = i;
		}

}

bool Hold(int c, int& minH, int& minQ, My_queue<int> H[], int k)
{
	//该函数是将车厢c放入缓冲轨中  

	//为车厢c寻找最优缓冲轨  
	int BestQueue = k;//初始化缓冲轨的编号  
	int BestLast = 0; //最优缓冲轨的队尾车厢编号  

	int x;

	//扫描缓冲轨  
	for (int i = 0; i<k; i++)
	{
		if (!H[i].empty())
		{
			x = H[i].back();
			if (c>x && x>BestLast)
			{
				BestLast = x;
				BestQueue = i;
			}
		}
		else
		{
			//H[i]为空时  
			if (BestQueue == k)
				BestQueue = i;
		}
	}

	if (BestQueue == k) //没有可用的缓冲轨  
		return false;

	H[BestQueue].push(c);
	cout << "Move car " << c << " from input to holding queue " << BestQueue + 1 << endl;

	//必要时修改minH和minS  
	if (c<minH)
	{
		minH = c;
		minQ = BestQueue;
	}

	return true;
}
int main()
{
	int p[9] = { 3,6,9,2,4,7,1,8,5 };
	if (Rail_Road(p, 9, 3))
		cout << "车厢重排序成功" << endl;
	else
		cout << "车厢重排序失败" << endl;
	getchar();



}


05 三元组实现稀疏矩阵的转置

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
#include<iostream>
using namespace std;

struct node{
	int r;//行标
	int c;//列标
	double dat;//数据

};
class triple
{
private:
	int row;//行数
	int col;//列数
	int num;//非零个数
	node *ptr;//存放数组的首地址
public:
	triple(int co,int ro,int nu):col(co),row(ro),num(nu)
	{
		ptr=new node[num];//分配num，盛放num个元素
		cout<<"请输入"<<num<<"个三元组元素\n"<<"格式为：2 3 6.7\n其中2为行标，3为列标，6.7为数据元素"<<endl;
		for(int i=0;i<num;i++)
		{
			cin>>ptr[i].r;
			cin>>ptr[i].c;
			cin>>ptr[i].dat;

		}
	}
	~triple(){delete[]ptr;}

void print()
{
	int flag=ptr[0].r;
	cout<<"第"<<flag<<"行元素为：";
	for(int i=0;i<num;i++)
	{
		if(ptr[i].r!=flag)
		{
			cout<<"\n";
			flag=ptr[i].r;
			cout<<endl;
			cout<<"第"<<flag<<"行元素为：";
		}
		cout<<"("<<ptr[i].r<<","<<ptr[i].c<<","<<ptr[i].dat<<")";
	}
}

void transpose()
{
	int flag=0;
	for(int i=1;i<=col;i++)
	{
		for(int j=0;j<num;j++)
		{
			if(ptr[j].c==i)
			{
				if(flag!=ptr[j].c)
				{
					flag=ptr[j].c;
					cout<<"\n第"<<ptr[j].c<<"行为：";
				}
      cout<<"("<<ptr[j].c<<","<<ptr[j].r<<","<<ptr[j].dat<<")";
			}
		}
	}
}
};



int main()
{
   cout<<"请输入数组的行列和元素个数:\n";
	 int a[3];
	 for(int i=0;i<3;i++)
	 {
		 cin>>a[i];
	 }
	 triple t(a[0],a[1],a[2]);
	 t.print();//输出原矩阵
	 cout<<"转制后的矩阵为:\n";
	 t.transpose();
}

06 二叉树后序遍历的非递归算法

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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
#define _CRT_SECURE_NO_DEPRECATE
//转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/6583988
#include<iostream>  
#include<queue>  
#include<stack>  
using namespace std;

//二叉树结点的描述  
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild, *rchild;      //左右孩子  
}BiTNode, *BiTree;

//按先序遍历创建二叉树  
//BiTree *CreateBiTree()     //返回结点指针类型  
//void CreateBiTree(BiTree &root)      //引用类型的参数  
void CreateBiTree(BiTNode **root)    //二级指针作为函数参数  
{
	char ch; //要插入的数据  
	scanf("\n%c", &ch);
	//cin>>ch;  
	if (ch == '#')
		*root = NULL;
	else
	{
		*root = (BiTNode *)malloc(sizeof(BiTNode));
		(*root)->data = ch;
		printf("请输入%c的左孩子：", ch);
		CreateBiTree(&((*root)->lchild));
		printf("请输入%c的右孩子：", ch);
		CreateBiTree(&((*root)->rchild));
	}
}

//前序遍历的算法程序  
void PreOrder(BiTNode *root)
{
	if (root == NULL)
		return;
	printf("%c ", root->data); //输出数据  
	PreOrder(root->lchild); //递归调用，前序遍历左子树  
	PreOrder(root->rchild); //递归调用，前序遍历右子树  
}

//中序遍历的算法程序  
void InOrder(BiTNode *root)
{
	if (root == NULL)
		return;
	InOrder(root->lchild); //递归调用，前序遍历左子树  
	printf("%c ", root->data); //输出数据  
	InOrder(root->rchild); //递归调用，前序遍历右子树  
}

//后序遍历的算法程序  
void PostOrder(BiTNode *root)
{
	if (root == NULL)
		return;
	PostOrder(root->lchild);      //递归调用，前序遍历左子树  
	PostOrder(root->rchild);      //递归调用，前序遍历右子树  
	printf("%c ", root->data);    //输出数据    
}

/*
二叉树的非递归前序遍历，前序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作，
每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。
*/
void PreOrder_Nonrecursive(BiTree T)     //先序遍历的非递归    
{
	if (!T)
		return;

	stack<BiTree> s;
	s.push(T);

	while (!s.empty())
	{
		BiTree temp = s.top();
		cout << temp->data << " ";
		s.pop();
		if (temp->rchild)
			s.push(temp->rchild);
		if (temp->lchild)
			s.push(temp->lchild);
	}
}

void PreOrder_Nonrecursive1(BiTree T)     //先序遍历的非递归
{
	if (!T)
		return;
	stack<BiTree> s;
	BiTree curr = T;
	while (curr != NULL || !s.empty())
	{
		while (curr != NULL)
		{
			cout << curr->data << "  ";
			s.push(curr);
			curr = curr->lchild;
		}
		if (!s.empty())
		{
			curr = s.top();
			s.pop();
			curr = curr->rchild;
		}
	}
}

void PreOrder_Nonrecursive2(BiTree T)     //先序遍历的非递归  
{
	if (!T)
		return;

	stack<BiTree> s;
	while (T)          // 左子树上的节点全部压入到栈中  
	{
		s.push(T);
		cout << T->data << "  ";
		T = T->lchild;
	}

	while (!s.empty())
	{
		BiTree temp = s.top()->rchild;  // 栈顶元素的右子树  
		s.pop();                        // 弹出栈顶元素  
		while (temp)          // 栈顶元素存在右子树，则对右子树同样遍历到最下方  
		{
			cout << temp->data << "  ";
			s.push(temp);
			temp = temp->lchild;
		}
	}
}

void InOrderTraverse1(BiTree T)   // 中序遍历的非递归  
{
	if (!T)
		return;
	BiTree curr = T;    // 指向当前要检查的节点  
	stack<BiTree> s;
	while (curr != NULL || !s.empty())
	{
		while (curr != NULL)
		{
			s.push(curr);
			curr = curr->lchild;
		}//while
		if (!s.empty())
		{
			curr = s.top();
			s.pop();
			cout << curr->data << "  ";
			curr = curr->rchild;
		}
	}
}

void InOrderTraverse(BiTree T)   // 中序遍历的非递归  
{
	if (!T)
		return;
	stack<BiTree> s;
	BiTree curr = T->lchild;    // 指向当前要检查的节点  
	s.push(T);
	while (curr != NULL || !s.empty())
	{
		while (curr != NULL)    // 一直向左走  
		{
			s.push(curr);
			curr = curr->lchild;
		}
		curr = s.top();
		s.pop();
		cout << curr->data << "  ";
		curr = curr->rchild;
	}
}

void PostOrder_Nonrecursive1(BiTree T)  // 后序遍历的非递归    
{
	stack<BiTree> S;
	BiTree curr = T;           // 指向当前要检查的节点  
	BiTree previsited = NULL;    // 指向前一个被访问的节点  
	while (curr != NULL || !S.empty())  // 栈空时结束    
	{
		while (curr != NULL)            // 一直向左走直到为空  
		{
			S.push(curr);
			curr = curr->lchild;
		}
		curr = S.top();
		// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点  
		if (curr->rchild == NULL || curr->rchild == previsited)
		{
			cout << curr->data << "  ";
			previsited = curr;
			S.pop();
			curr = NULL;
		}
		else
			curr = curr->rchild;      // 否则访问右孩子  
	}
}

void PostOrder_Nonrecursive(BiTree T)  // 后序遍历的非递归     双栈法  
{
	stack<BiTree> s1, s2;
	BiTree curr;           // 指向当前要检查的节点  
	s1.push(T);
	while (!s1.empty())  // 栈空时结束    
	{
		curr = s1.top();
		s1.pop();
		s2.push(curr);
		if (curr->lchild)
			s1.push(curr->lchild);
		if (curr->rchild)
			s1.push(curr->rchild);
	}
	while (!s2.empty())
	{
		printf("%c ", s2.top()->data);
		s2.pop();
	}
}


int visit(BiTree T)
{
	if (T)
	{
		printf("%c ", T->data);
		return 1;
	}
	else
		return 0;
}

void LeverTraverse(BiTree T)   //方法一、非递归层次遍历二叉树   
{
	queue <BiTree> Q;
	BiTree p;
	p = T;
	if (visit(p) == 1)
		Q.push(p);
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		if (visit(p->lchild) == 1)
			Q.push(p->lchild);
		if (visit(p->rchild) == 1)
			Q.push(p->rchild);
	}
}
void LevelOrder(BiTree BT)     //方法二、非递归层次遍历二叉树   
{
	BiTNode *queue[10];//定义队列有十个空间  
	if (BT == NULL)
		return;
	int front, rear;
	front = rear = 0;
	queue[rear++] = BT;
	while (front != rear)//如果队尾指针不等于对头指针时  
	{
		cout << queue[front]->data << "  ";  //输出遍历结果  
		if (queue[front]->lchild != NULL)  //将队首结点的左孩子指针入队列  
		{
			queue[rear] = queue[front]->lchild;
			rear++;    //队尾指针后移一位  
		}
		if (queue[front]->rchild != NULL)
		{
			queue[rear] = queue[front]->rchild;    //将队首结点的右孩子指针入队列  
			rear++;   //队尾指针后移一位  
		}
		front++;    //对头指针后移一位  
	}
}

int depth(BiTNode *T)   //树的深度  
{
	if (!T)
		return 0;
	int d1, d2;
	d1 = depth(T->lchild);
	d2 = depth(T->rchild);
	return (d1>d2 ? d1 : d2) + 1;
	//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;  
}
int CountNode(BiTNode *T)
{
	if (T == NULL)
		return 0;
	return 1 + CountNode(T->lchild) + CountNode(T->rchild);
}

int main(void)
{
	BiTNode *root = NULL; //定义一个根结点  
	int flag = 1, k;
	printf("                     本程序实现二叉树的基本操作。\n");
	printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n");

	while (flag)
	{
		printf("\n");
		printf("|--------------------------------------------------------------|\n");
		printf("|                    二叉树的基本操作如下:                     |\n");
		printf("|                        0.创建二叉树                          |\n");
		printf("|                        1.递归先序遍历                        |\n");
		printf("|                        2.递归中序遍历                        |\n");
		printf("|                        3.递归后序遍历                        |\n");
		printf("|                        4.非递归先序遍历                      |\n");
		printf("|                        5.非递归中序遍历                      |\n");
		printf("|                        6.非递归后序遍历                      |\n");
		printf("|                        7.非递归层序遍历                      |\n");
		printf("|                        8.二叉树的深度                        |\n");
		printf("|                        9.二叉树的结点个数                    |\n");
		printf("|                        10.退出程序                            |\n");
		printf("|--------------------------------------------------------------|\n");
		printf("                        请选择功能：");
		scanf("%d", &k);
		switch (k)
		{
		case 0:
			printf("请建立二叉树并输入二叉树的根节点：");
			CreateBiTree(&root);
			break;
		case 1:
			if (root)
			{
				printf("递归先序遍历二叉树的结果为：");
				PreOrder(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 2:
			if (root)
			{
				printf("递归中序遍历二叉树的结果为：");
				InOrder(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 3:
			if (root)
			{
				printf("递归后序遍历二叉树的结果为：");
				PostOrder(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 4:
			if (root)
			{
				printf("非递归先序遍历二叉树：");
				PreOrder_Nonrecursive1(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 5:
			if (root)
			{
				printf("非递归中序遍历二叉树：");
				InOrderTraverse1(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 6:
			if (root)
			{
				printf("非递归后序遍历二叉树：");
				PostOrder_Nonrecursive(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 7:
			if (root)
			{
				printf("非递归层序遍历二叉树：");
				//LeverTraverse(root);  
				LevelOrder(root);
				printf("\n");
			}
			else
				printf("          二叉树为空！\n");
			break;
		case 8:
			if (root)
				printf("这棵二叉树的深度为：%d\n", depth(root));
			else
				printf("          二叉树为空！\n");
			break;
		case 9:
			if (root)
				printf("这棵二叉树的结点个数为：%d\n", CountNode(root));
			else
				printf("          二叉树为空！\n");
			break;
		default:
			flag = 0;
			printf("程序运行结束，按任意键退出！\n");
		}
	}
	system("pause");
	return 0;
}

07 图的两种遍历方法及对应的生成树

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
#define _CRT_SECURE_NO_WARNINGS
//图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，程序如下：
#include <iostream>
#include<stdio.h>
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool *visited;  //访问标志数组
				//图的邻接矩阵存储结构
typedef struct {
	char *vexs; //顶点向量
	int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
	int vexnum, arcnum; //图的当前顶点数和弧数
}Graph;


//队列类
class Queue {
public:
	void InitQueue() {
		base = (int *)malloc(QUEUE_SIZE * sizeof(int));
		front = rear = 0;
	}
	void EnQueue(int e) {
		base[rear] = e;
		rear = (rear + 1) % QUEUE_SIZE;
	}
	void DeQueue(int &e) {
		e = base[front];
		front = (front + 1) % QUEUE_SIZE;
	}
public:
	int *base;
	int front;
	int rear;
};


//图G中查找元素c的位置
int Locate(Graph G, char c) {
	for (int i = 0; i<G.vexnum; i++)
		if (G.vexs[i] == c) return i;
	return -1;
}


//创建无向网
void CreateUDN(Graph &G) {
	int i, j, w, s1, s2;
	char a, b, temp;
	printf("输入顶点数和弧数:");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	temp = getchar(); //接收回车
	G.vexs = (char *)malloc(G.vexnum * sizeof(char)); //分配顶点数目
	printf("输入%d个顶点.\n", G.vexnum);
	for (i = 0; i<G.vexnum; i++) { //初始化顶点
		printf("输入顶点%d:", i);
		scanf("%c", &G.vexs[i]);
		temp = getchar(); //接收回车
	}
	for (i = 0; i<G.vexnum; i++) //初始化邻接矩阵
		for (j = 0; j<G.vexnum; j++)
			G.arcs[i][j] = INFINITY;
	printf("输入%d条弧.\n", G.arcnum);
	for (i = 0; i<G.arcnum; i++) { //初始化弧
		printf("输入弧%d:", i);
		scanf("%c %c %d", &a, &b, &w); //输入一条边依附的顶点和权值
		temp = getchar(); //接收回车
		s1 = Locate(G, a);
		s2 = Locate(G, b);
		G.arcs[s1][s2] = G.arcs[s2][s1] = w;
	}
}


//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G, int k) {
	if (k >= 0 && k<G.vexnum) { //k合理
		for (int i = 0; i<G.vexnum; i++)
			if (G.arcs[k][i] != INFINITY) return i;
	}
	return -1;
}


//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G, int i, int j) {
	if (i >= 0 && i<G.vexnum && j >= 0 && j<G.vexnum) { //i,j合理
		for (int k = j + 1; k<G.vexnum; k++)
			if (G.arcs[i][k] != INFINITY) return k;
	}
	return -1;
}


//深度优先遍历
void DFS(Graph G, int k) {
	int i;
	if (k == -1) { //第一次执行DFS时,k为-1
		for (i = 0; i<G.vexnum; i++)
			if (!visited[i]) DFS(G, i); //对尚未访问的顶点调用DFS
	}
	else {
		visited[k] = true;
		printf("%c ", G.vexs[k]); //访问第k个顶点
		for (i = FirstVex(G, k); i >= 0; i = NextVex(G, k, i))
			if (!visited[i]) DFS(G, i); //对k的尚未访问的邻接顶点i递归调用DFS
	}
}


//广度优先遍历
void BFS(Graph G) {
	int k;
	Queue Q; //辅助队列Q
	Q.InitQueue();
	for (int i = 0; i<G.vexnum; i++)
		if (!visited[i]) { //i尚未访问
			visited[i] = true;
			printf("%c ", G.vexs[i]);
			Q.EnQueue(i); //i入列
			while (Q.front != Q.rear) {
				Q.DeQueue(k); //队头元素出列并置为k
				for (int w = FirstVex(G, k); w >= 0; w = NextVex(G, k, w))
					if (!visited[w]) { //w为k的尚未访问的邻接顶点
						visited[w] = true;
						printf("%c ", G.vexs[w]);
						Q.EnQueue(w);
					}
			}
		}
}


//主函数
void main() {
	int i;
	Graph G;
	CreateUDN(G);
	visited = (bool *)malloc(G.vexnum * sizeof(bool));
	printf("\n深度优先遍历: ");
	for (i = 0; i<G.vexnum; i++)
		visited[i] = false;
	DFS(G, -1);
	printf("\n广度优先遍历: ");
	for (i = 0; i<G.vexnum; i++)
		visited[i] = false;
	BFS(G);
	printf("\n程序结束.\n");
	getchar();
}

08 给定一个有向图，对其拓扑排序

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
#include <cstdlib>
#include <iostream>
#include <stack>
#define Maxsize 30
#define INFINITY 99999
using namespace std;
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct adjlist
{
	char name[10];
	int indegree;
	ArcNode *firstarc;
}adjlist;
typedef struct
{
	int vexnum, arcnum;
	adjlist ver[Maxsize];
}ALGraph;
int Locatecity(ALGraph G, char v[]);
void createGraph();
void output(ALGraph G);
void FindInDegree(ALGraph &G);
void TopologicalSort(ALGraph &G);

void TopologicalSort(ALGraph &G)
{
	int i, j, e, count;
	stack<int> s;
	ArcNode *p;
	FindInDegree(G);
	for (i = 0; i<G.vexnum; i++)
		if (!G.ver[i].indegree)
			s.push(i);
	count = 0;  //对顶点进行计数
	cout << "拓扑排序的结果如下: \n";
	while (!s.empty())
	{
		e = s.top();
		cout << G.ver[e].name << " ";
		count++;
		s.pop();
		for (p = G.ver[e].firstarc; p; p = p->nextarc)
		{
			if (!(--G.ver[p->adjvex].indegree))
				s.push(p->adjvex);
		}//for
	}//while
	cout << endl;
	if (count<G.vexnum)
	{
		cout << "该有向图有回路\n";
		return;
	}//if
}
void FindInDegree(ALGraph &G)
{
	int indeg, i, j;
	ArcNode *p;
	for (i = 0; i<G.vexnum; i++)
	{
		indeg = 0;
		for (j = 0; j<G.vexnum; j++)
		{
			if (G.ver[j].firstarc != NULL)
			{
				p = G.ver[j].firstarc;
				while (p)
				{
					if (p->adjvex == i)
						indeg++;
					p = p->nextarc;
				}//while
			}//if
		}//for
		G.ver[i].indegree = indeg;
	}//for
}
void createGraph()
{
	ALGraph G;
	cout << "请输入图的顶点个数: \n";
	cin >> G.vexnum;
	cout << "请输入弧数:\n";
	cin >> G.arcnum;
	for (int i = 0; i<G.vexnum; i++)
	{
		cout << "第 " << i + 1 << " 个顶点的名称\n";
		cin >> G.ver[i].name;
		G.ver[i].indegree = 0;  //都初始化为零
		G.ver[i].firstarc = NULL;
	}//for
	int n, m;
	char v1[10], v2[10];
	for (int j = 0; j<G.arcnum; j++)
	{
		cout << "请输入第 " << j + 1 << " 条弧的弧尾与弧头" << endl;
		cin >> v1 >> v2;
		n = Locatecity(G, v1); m = Locatecity(G, v2);
		ArcNode *p, *q, *t;
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = m;
		p->nextarc = NULL;
		if (G.ver[n].firstarc == NULL)
			G.ver[n].firstarc = p;
		else
		{
			q = G.ver[n].firstarc;
			while (q->nextarc)
				q = q->nextarc;
			q->nextarc = p;
		}//else
	}//for
	output(G);
	TopologicalSort(G);
}
void output(ALGraph G)
{
	int i, j;
	ArcNode *p;
	cout << "有向图的邻接边的对应关系为:\n";
	for (i = 0; i<G.vexnum; i++)
	{

		if (G.ver[i].firstarc != NULL)
		{
			p = G.ver[i].firstarc;
			while (p)
			{
				cout << p->adjvex << "  ";
				p = p->nextarc;
			}//while
		}//if
		cout << endl;
	}//for
}
int Locatecity(ALGraph G, char v[])  //定位v在G中的位置的函数
{
	int i;
	for (i = 0; i<G.vexnum; i++)
		if (!strcmp(G.ver[i].name, v))
			break;
	return i;
}
int main()
{

	createGraph();
	system("PAUSE");
	return 0;
}


09 二叉排序树的建立，删除，插入节点，查找

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



#include<iostream>
#include<stdio.h>
using namespace std;
#include<malloc.h>
#define MaxSize 100
typedef int KeyType;
typedef char InfoType;
typedef struct node
{
	KeyType key;
	InfoType data;
	struct node *lchild, *rchild;
}BSTNode;
int path[MaxSize];
void DispBST(BSTNode *b);
int InsetBST(BSTNode *&p, KeyType k)
{
	if (p == NULL)
	{
		p = (BSTNode *)malloc(sizeof(BSTNode));
		p->key = k; p->lchild = p->rchild = NULL;
		return 1;
	}
	else if (k == p->key)
		return 0;
	else if (k < p->key)
		return InsetBST(p->lchild, k);
	else
		return InsetBST(p->rchild, k);
}
BSTNode *CreatBST(KeyType A[], int n)
{
	BSTNode *bt = NULL;
	int i = 0;
	while (i<n)
	{
		if (InsetBST(bt, A[i]) == 1)
		{
			printf("第%d步 插入%d:", i + 1, A[i]);
			DispBST(bt); i++;
		}
	}
	return bt;
}
void Delete1(BSTNode *p, BSTNode *&r)
{
	BSTNode *q;
	if (r->rchild != NULL)
		Delete1(p, r->rchild);
	else
	{
		p->key = r->key;
		q = r;
		r = r->lchild;
		free(q);
	}
}
void Delete(BSTNode *&p)
{
	BSTNode *q;
	if (p->rchild == NULL)
	{
		q = p;
		p = p->lchild;
		free(q);
	}
	else if (p->lchild == NULL)
	{
		q = p;
		p = p->rchild;
		free(q);
	}
	else
		Delete1(p, p->lchild);
}
int DeleteBST(BSTNode *&bt, KeyType k)
{
	if (bt == NULL)
		return 0;
	else
	{
		if (k < bt->key)
			return DeleteBST(bt->lchild, k);
		else if (k > bt->key)
			return DeleteBST(bt->rchild, k);
		else
		{
			Delete(bt);
			return 1;
		}
	}
}
void SearchBST(BSTNode *bt, KeyType k, KeyType path[], int i)
{
	int j;
	if (bt == NULL)
		return;
	else if (k == bt->data)
	{
		path[i + 1] = bt->key;
		for (j = 0; j <= i + 1; j++)
		{
			printf("%3d", path[j]);
		}
	}
	else
	{
		path[i + 1] = bt->key;
		if (k < bt->key)
			SearchBST(bt->lchild, k, path, i + 1);
		else
			SearchBST(bt->rchild, k, path, i + 1);
	}
}
int SearchBST2(BSTNode *bt, KeyType k)
{
	if (bt == NULL)
		return 0;
	else if (k == bt->key)
	{
		printf("%3d", bt->data);
		return 1;
	}
	else if (k < bt->key)
		SearchBST2(bt->lchild, k);
	else
		SearchBST2(bt->rchild, k);
	printf("%3d", bt->key);
}
void DispBST(BSTNode *bt)
{
	if (bt != NULL)
	{
		printf("%d", bt->key);
		if (bt->lchild != NULL || bt->rchild != NULL)
		{
			printf("(");
			DispBST(bt->lchild);
			if (bt->rchild != NULL)
				printf(",");
			DispBST(bt->rchild);
			printf(")");
		}
	}
}
KeyType predt = -32767;
int JundgBST(BSTNode *bt)
{
	int b1, b2;
	if (bt == NULL)
		return 1;
	else
	{
		b1 = JundgBST(bt->lchild);
		if (b1 == 0 || predt >= bt->key)
			return 0;
		predt = bt->key;
		b2 = JundgBST(bt->rchild);
		return b2;
	}
}
void main()
{
	BSTNode *bt;
	KeyType k = 6;
	int a[] = { 4,9,3,8,7,0,1,2,5,6 }, n = 10;
	printf("创建一颗BST树");
	bt = CreatBST(a, n);
	printf("BST："); DispBST(bt);
	printf("bt%s\n", (JundgBST(bt) ? "是一颗树" : "不是一颗树"));
	printf("查找%d关键字(递归，顺序)", k); SearchBST(bt, k, path, -1);
	printf("查找%d关键字(非递归，逆序)", k); SearchBST2(bt, k);
	printf("删除操作：\n");
	printf("原BST："); DispBST(bt); printf("\n");
	printf("删除节点4");
	DeleteBST(bt, 4);
	DispBST(bt);
	getchar();

}

Markdown

10 希尔排序 与 快速排序的比较

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

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#define Max 30
typedef struct
{
	int key;

}RecType;
RecType R[Max], S[Max];
void ShellSort(RecType R[], int n)
{
	int i, j, gap;
	RecType tmp;
	gap = n / 2;
	while (gap>0)
	{
		for (i = gap; i < n; i++)
		{
			tmp = R[i];
			j = i - gap;
			while (j >= 0 && tmp.key<R[j].key)
			{
				R[j + gap] = R[j];
				j = j - gap;
			}
			R[j + gap] = tmp;
		}
		gap = gap / 2;
	}
}
void QuickSort(RecType R[], int s, int t)
{
	int i = s, j = t;
	RecType tmp;
	if (s < j)
	{
		tmp = R[s];
		while (i != j)
		{
			while (j > i&&R[j].key > tmp.key)
				j--;
			R[i] = R[j];
			while (i < j&&R[i].key < tmp.key)
				i++;
			R[j] = R[i];
		}
		R[i] = tmp;
		QuickSort(R, s, i - 1);
		QuickSort(R, i + 1, t);
	}
}

void main()
{
	int n, i;
	printf("请输入关键字个数：\n");
	scanf("%d", &n);
	printf("请输入关键字序列：\n");
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &R[i].key);
		S[i].key = R[i].key;
	}
	ShellSort(R, n);
	printf("希尔排序结果为：");
	for (i = 0; i < n; i++)
		printf("%d", R[i].key);
	printf("\n");
	QuickSort(S, 0, n - 1);
	printf("快速排序结果为：");
	for (i = 0; i < n; i++)
		printf("%d", S[i].key);

}

Markdown

11

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
#include<stdio.h>
int tile = 0;//L型骨牌数量
int Matrix[100][100];//定义数据结构
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
	//tr tc 行号 列号
	if (size == 1) return;
	int t = tile++;//L型骨牌号
	int s = size / 2;//分割棋盘
	if (dr < tr + s&&dc < tc + s)//用L型骨牌覆盖左上角棋盘
		ChessBoard(tr, tc, dr, dc, s);//特殊方格在此棋盘中
	else
	{
		//特殊方格不在此棋盘中，t号L型骨牌覆盖右下角
		Matrix[tr + s - 1][tc + s - 1];//覆盖本子棋盘其余方格
		ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
	}
	if (dr < tr + s&&dc >= tc + s)//用L型骨牌号覆盖右上角棋盘
		ChessBoard(tr, tc, dr, dc, s);
	else
	{
		//特殊方格不在此棋盘中，t号L型骨牌覆盖左下角
		Matrix[tr + s - 1][tc + s] = t;//覆盖本子棋盘其余方格
		ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
	}
	if (dr >= tr + s&&dc<tc + s)//用L型骨牌覆盖左下角子棋盘
		ChessBoard(tr + s, tc, dr, dc, s);
	else
	{
		//特殊方格不在此棋盘中，t号L型骨牌覆盖右上角
		Matrix[tr + s][tc + s] = t;//覆盖本子棋盘其余方格
		ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
	}
	if (dr >= tr + s&&dc >= tc + s)//用L骨牌覆盖右上角子棋盘
		ChessBoard(tr + s, tc + s, dr, dc, s);
	else
	{
		//特殊方格不在此棋盘中，t号L型骨牌覆盖右上角
		Matrix[tr + s][tc + s] = t;//覆盖本子棋盘其余方格
		ChessBoard(tr, tc + s, tr + s, tc + s, s);
	}
}