数据结构-上机作业系列

Computer

第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
117
118
119
#include<iostream>
using namespace std;
/*
	1. 定义双链表的节点结构
*/
template<typename DataType>
struct DulNode {
	DataType data;
	DulNode<DataType> *prior, *next;
};
/*
	2. 定义外部函数初始化双链表
*/
template<typename DataType>
void newLink(DulNode<DataType> *first) {
	first->data = NULL;
	first->prior = first;
	first->next = first;
}
/*
	3. 定义外部函数实现双链表的尾插入
*/
template<typename DataType>
void TailInsert(DulNode<DataType> *first, DataType c) {
	DulNode<DataType> *p, *s;
	p = first->prior;
	s = new DulNode<DataType>;
	s->data = c;
	//p->s->first
	s->next = p->next;
	s->prior = p;
	first->prior = s;
	p->next = s;  
}
/*
	4. 定义外部函数实现将整个双链表对称
*/
template<typename DataType>
void ExchangeSentence(DulNode<DataType> *p, DulNode<DataType> *q) {
	DulNode<DataType> *p1 = p->prior;
	DulNode<DataType> *q1 = q->prior;
	DulNode<DataType> *s;
	while (p1 != p) {
		s = new DulNode<DataType>;
		s->data = p1->data;
		//插入链表时的指针调整
		s->next = q;
		s->prior = q1;
		q1->next = s;
		q->prior = s;
		//工作指针调整
		q1 = s;
		p1 = p1->prior;
	}
}
/*
	5. 临时正向打印函数
*/
template<typename DataType>
void printDulLink(DulNode<DataType> *first) {
	DulNode<DataType> *p = first->next;
	while (p != first) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
/*
	临时反向打印函数
*/
template<typename DataType>
void printRevDulLink(DulNode<DataType> *first) {
	DulNode<DataType> *p = first->prior;
	while (p != first) {
		cout << p->data << " ";
		p = p->prior;
	}
	cout << endl;
}
/*
	6. 扫描指针使得对每个单词进行反转
*/
template<typename DataType>
void ExchangeWords(DulNode<DataType> *p1) {
	DulNode<DataType> *s1 = p1->next;
	DulNode<DataType> *s2 = s1->next;
	DataType temp = NULL;
	while (s1 != p1) {
		while (s1->data != ' ') {
			//开始读单词
			s2 = s1;
			while (s2->next->data != ' ' && s2->next != p1) {
				s2 = s2->next;
			}
			//交换数据
			temp = s1->data;
			s1->data = s2->data;
			s2->data = temp;
			//调整指针位置
			s1 = s2;
			break;
		}
		//继续扫描
		s1 = s1->next;
	}
}
/*
	临时析构函数
*/
template<typename DataType>
void deleteDulLink(DulNode<DataType> *first) {
	DulNode<DataType> *p = first->next;
	DulNode<DataType> *q = p->next;
	while (q != first->next) {
		delete p;
		p = q;
		q = q->next;
	}
}

第2次上机作业

      迷宫问题，用一个二维数组表示迷宫，1表示墙壁不可走，0表示通路可走，找出起点到终点超过20条路径。
      迷宫是下面这个样子的，用(a,b)表示起点，其中a和b是数组的索引值，(c,d)表示终点值，所以要传入四个参数进搜索的路径的函数中。注意数组的索引是从0开始的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
	SeqStack st;
	int mg[10][10] = 
	{
		{1,1,1,1,1,1,1,1,1,1},
		{1,0,0,1,0,0,0,0,0,1},
		{1,0,0,1,0,0,0,1,0,1},
		{1,0,0,0,0,1,1,0,0,1},
		{1,0,1,1,1,0,0,0,0,1},
		{1,0,0,0,1,0,0,0,0,1},
		{1,0,1,1,1,0,1,1,0,1},
		{1,1,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1}
	};
	mgPath(1, 2, 5, 6, st,mg);
	system("pause");
	return 0;
}

      SeqStack.h

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
#pragma once
#include<iostream>
const int StackSize = 100;
struct currentPosition {
	//无参构造函数
	currentPosition() {};
	//有参构造函数
	currentPosition(int i, int j, int di) :m_i(i), m_j(j), m_di(di) {}
	int m_i;   //x方向
	int m_j;   //y方向
	int m_di;  //存储从其出发已经走过的方向，0,1,2,3代表四个方向
};
class SeqStack {
public:
	SeqStack() { top = -1; }
	~SeqStack() {}
	bool Empty();
	bool Full();
	void printStack();
	void Push(currentPosition x);
	currentPosition Pop();
	currentPosition GetTop();
private:
	currentPosition data[StackSize];
	int top;
};

      SeqStack.cpp

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
#include"SeqStack.h"
void SeqStack::Push(currentPosition x) {
	if (Full()) {
		throw "栈为满！";
	}
	else {
		data[++top] = x;
	}
}
currentPosition SeqStack::Pop() {
	if (Empty()) {
		throw "栈为空！";
	}
	else {
		return data[top--];
	}
}
currentPosition SeqStack::GetTop() {
	if (Empty()) {
		throw "栈为空！";
	}
	else {
		return data[top];
	}
}
bool SeqStack::Empty() {
	if (top == -1) {
		return true;
	}
	else {
		return false;
	}
}
bool SeqStack::Full() {
	if (top == StackSize - 1) {
		return true;
	}
	else {
		return false;
	}
}
void SeqStack::printStack() {
	for (int i = 0; i <= top; i++) {
		std::cout << "(" << data[i].m_i << "," << data[i].m_j << ") ";
	}
	std::cout << std::endl;
}

      mgPath.cpp

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
#include"SeqStack.h"
#include<iostream>
using namespace std;
//(xi,yi)为起点，(xe,ye)为终点
int mgPath(int xi, int yi, int xe, int ye,SeqStack &stack,int &mg[10][10]){
	int i = xi, j = yi, di=-1;   //存放当前格的信息的临时变量
	int count = 0;   //控制打印条数
	int find;	  //标志从当前结点出发是否有可行的下一站
	currentPosition start(xi, yi, -1);
	stack.Push(start);  //起始节点入栈
	mg[xi][yi] = -1;  //-1表示不重复走路
	while (!stack.Empty()) {
		currentPosition temp = stack.GetTop();
		if (temp.m_i == xe && temp.m_j == ye) {
			if (count < 10) {
				count++;
				stack.printStack();
				stack.Pop();
				//初始化记录变量
				i = stack.GetTop().m_i;
				j = stack.GetTop().m_j;
				di = stack.GetTop().m_di;
				mg[temp.m_i][temp.m_j] = 0;   //取消禁走令
			}
			else {
				return 0;
			}
		}
		find = 0; //准备测试从(i,j)出发是否可以往下走
		while (di < 4 && find == 0) {	//找下一个网格
			di++;   //试探下一种走法
			switch (di)
			{
			case 0://向上
				i = temp.m_i - 1;
				j = temp.m_j;
				break;
			case 1://向右
				i = temp.m_i;
				j = temp.m_j + 1;
				break;
			case 2://向下
				i = temp.m_i + 1;
				j = temp.m_j;
				break;
			case 3://向左
				i = temp.m_i;
				j = temp.m_j - 1;
				break;
			}
			if (mg[i][j] == 0) { find = 1; }//没被禁走找到下一站
		}
		if (find == 1) {
			currentPosition top = stack.Pop();
			top.m_di = di;
			stack.Push(top);
			currentPosition temp2(i, j, -1);
			stack.Push(temp2);
			mg[i][j] = -1;
			//初始化记录变量
			i = stack.GetTop().m_i;
			j = stack.GetTop().m_j;
			di = stack.GetTop().m_di;
		}
		else {
			mg[stack.GetTop().m_i][stack.GetTop().m_j] = 0;
			stack.Pop();
			//初始化记录变量
			i = stack.GetTop().m_i;
			j = stack.GetTop().m_j;
			di = stack.GetTop().m_di;
		}
	}
	return 0;
}

第3次上机作业

      利用队列来找两点之间的最短距离，这是我写CPP代码以来最不舒服的一次，完全没有CPP的规范可言。
      Cirqueue.cpp

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
const int QueueSize = 15;
template<typename T>
class CirQueue {
public:
	CirQueue();
	~CirQueue() {};
	void EnQueue(T x);
	T DeQueue();
	T GetQueue();
	bool Full();
	bool Empty();
	int getfront();
	int getrear();
	T getData();
	T data[QueueSize];
	int front, rear;
};
template<typename T>
CirQueue<T>::CirQueue() {
	rear = front = QueueSize - 1;
}
template<typename T>
void CirQueue<T>::EnQueue(T x) {
	if ((rear + 1) % QueueSize == front) {
		throw "队列已满！";
	}
	else {
		rear = (rear + 1) % QueueSize;
		data[rear] = x;
	}
}
template<typename T>
T CirQueue<T>::DeQueue() {
	if (rear == front) {
		throw "队列已空！";
	}
	else {
		front = (front + 1) % QueueSize;
		return data[front];
	}
}
template<typename T>
T CirQueue<T>::GetQueue() {
	if (rear == front) {
		throw "队列已空！";
	}
	else {
		int i = (front + 1) % QueueSize;
		return data[i];
	}
}
template<typename T>
bool CirQueue<T>::Full() {
	if ((rear + 1) % QueueSize == front) {
		return true;
	}
	else {
		return false;
	}
}
template<typename T>
bool CirQueue<T>::Empty() {
	if (rear == front) {
		return true;
	}
	else {
		return false;
	}
}
template<typename T>
int CirQueue<T>::getfront() {
	return front;
}
template<typename T>
int CirQueue<T>::getrear() {
	return rear;
}
template<typename T>
T CirQueue<T>::getData() {
	return data;
}

      main.cpp

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
#include<iostream>
using namespace std;
#include"CirQueue.cpp"
struct QNode {
	int j;	//顶点编号
	int f;	//当前顶点在该路径上的父结点在队列中的位置
};
void print(int &Martix[5]) {
	for (int i = 0; i < 5; i++) {
		cout << Martix[i] << " ";
	}
	cout << endl;
}
int main() {
	int A[5][5] = {
		{-1,1,-1,3,10},
		{-1,-1,5,-1,-1},
		{-1,-1,-1,-1,1},
		{-1,-1,2,-1,6},
		{-1,-1,-1,-1,-1}
	};	//图结构
	int R[5] = { 1000,1000,1000,1000,1000 };	//存储源点到各其他点的距离值(动态更新)
	int P[5] = { -1,-1,-1,-1,-1 };	//当前路径终点在队列中的位置
	CirQueue<QNode> Q;	//定义队列
	QNode W;			//定义队列中的当前结点
	W.j = 0;			//结点编号为0
	W.f = -1;			//结点没有父结点
	R[0] = 0;			//结点到0的距离为0
	Q.EnQueue(W);		//第一个结点入队
	while (!Q.Empty()) {
		W = Q.DeQueue();
		int s = W.j;	//拿到当前结点的编号
		int f = Q.getfront();	//拿到头节点在队列中的位置
		for (int i = 0; i < 5; i++) {
			if (A[s][i] != -1) {
				if (R[s] + A[s][i] <= R[i]) {//比较新路径的存储距离
					W.j = i;
					W.f = f;
					Q.EnQueue(W);
					R[i] = R[s] + A[s][i];
					P[i] = Q.getrear();
				}
			}
		}
	}
	for (int i = 1; i < 5; i++) {
		cout << "0到" << i << "的最短距离为：" << R[i] << endl;
		int shortest = R[i];
		int j = P[i];
		int Path[5] = { 0 };
		int k = 4;
		Path[k] = Q.data[j].j;
		k--;
		while (Q.data[j].f != -1) {
			j = Q.data[j].f;
			Path[k] = Q.data[j].j;
			k--;
		}
		print(Path);
	}
	system("pause");
	return 0;
}

第4次上机作业

      建立一棵二叉树，并完成所有的遍历方式。
      BiTree.cpp

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
#include<iostream>
using namespace std;
template<class DataType>
struct BiNode 
{
	DataType data;
	BiNode<DataType> *lchild, *rchild;
};
template<class DataType>
struct QuNode
{
	BiNode<DataType> *curNode;
	int level;
};
template<class DataType>
class BiTree 
{
public:
	BiTree() { root = Create(root); }
	~BiTree() { Release(root); }
	void PreOrder() { PreOrder(root); }
	void InOrder() { InOrder(root); }
	void PostOrder() { PostOrder(root); }
	void LeverOrder();
	void LeverOrderh();
private:
	BiNode<DataType> *root;							//指向根结点的头指针
	BiNode<DataType> *Create(BiNode<DataType> *bt);	//调用构造函数
	void Release(BiNode<DataType> *bt);				//析构函数调用
	void PreOrder(BiNode<DataType> *bt);			//前序遍历
	void InOrder(BiNode<DataType> *bt);				//中序遍历
	void PostOrder(BiNode<DataType> *bt);			//后序遍历
};
template<class DataType>
BiNode<DataType> *BiTree<DataType>::Create(BiNode<DataType> *bt)
{
	char ch;		//字符编号
	cin >> ch;
	if (ch == '#')
	{
		bt = NULL;
	}
	else
	{
		bt = new BiNode<DataType>;
		bt->data = ch;
		bt->lchild = Create(bt->lchild);
		bt->rchild = Create(bt->rchild);
	}
	return bt;
}
template<class DataType>
void BiTree<DataType>::Release(BiNode<DataType> *bt)
{
	if (bt != NULL)
	{
		Release(bt->lchild);
		Release(bt->rchild);
		delete bt;
	}
}
template<class DataType>
void BiTree<DataType>::PreOrder(BiNode<DataType> *bt)
{
	if(bt==NULL)
	{ 
		return;
	}
	else
	{
		cout << bt->data;
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}
template<class DataType>
void BiTree<DataType>::InOrder(BiNode<DataType> *bt)
{
	if (bt == NULL)
	{
		return;
	}
	else
	{
		InOrder(bt->lchild);
		cout << bt->data;
		InOrder(bt->rchild);
	}
}
template<class DataType>
void BiTree<DataType>::PostOrder(BiNode<DataType> *bt)
{
	if (bt == NULL)
	{
		return;
	}
	else
	{
		PostOrder(bt->lchild);
		PostOrder(bt->rchild);
		cout << bt->data;
	}
}
template<class DataType>
void BiTree<DataType>::LeverOrder()
{
	BiNode<DataType> *Q[100];
	BiNode<DataType> *q;
	int front = -1;
	int rear = -1;
	if (root == NULL)
	{
		return;
	}
	Q[++rear] = root;
	while (front != rear)
	{
		q = Q[++front];
		cout << q->data;
		if (q->lchild != NULL)
		{
			Q[++rear] = q->lchild;
		}
		if (q->rchild != NULL)
		{
			Q[++rear] = q->rchild;
		}
	}
}
template<class DataType>
void BiTree<DataType>::LeverOrderh()
{
	QuNode<DataType> Q[100];
	QuNode<DataType> q;
	int front = -1;
	int rear = -1;
	if (root == NULL)
	{
		return;
	}
	Q[++rear].curNode = root;	//根结点入队
	Q[rear].level = 1;			//根结点的层数
	while (front != rear)
	{
		q = Q[++front];
		cout << "结点"<<q.curNode->data<<"的层数为：" << q.level << endl;
		if (q.curNode->lchild != NULL)
		{
			Q[++rear].curNode = q.curNode->lchild;
			Q[rear].level = q.level + 1;
		}
		if (q.curNode->rchild != NULL)
		{
			Q[++rear].curNode = q.curNode->rchild;
			Q[rear].level = q.level + 1;
		}
	}
}

      main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
#include"BiTree.cpp"
int main() {
	BiTree<char> tree;
	cout << "前序遍历为：";
	tree.PreOrder();
	cout << endl;
	cout << "中序遍历为：";
	tree.InOrder();
	cout << endl;
	cout << "后序遍历为：";
	tree.PostOrder();
	cout << endl;
	cout << "层序遍历为：";
	tree.LeverOrder();
	cout << endl;
	cout << "层序(带层数)遍历为："<<endl;
	tree.LeverOrderh();
	cout << endl;
	system("pause");
	return 0;
}

文章目录
  1. 1. 第1次上机作业
  2. 2. 第2次上机作业
  3. 3. 第3次上机作业
  4. 4. 第4次上机作业
|