12.16~12.17图的存储方式（邻接矩阵，邻接表），相应定义与构建，PTA特性（要初始化），BFS抓牛，判断题

图的存储方式

邻接矩阵

#include<iostream>
using namespace std;
#define maxn;
struct tu {
	int juzhen[maxn][maxn];//行为起点，列为终点，即第一个为起点，第二个为终点
	//确定一个点的出度，就固定行，即第一个不动（即起点固定不动），然后看这一行里有多少个不为0的数
	//确定一个点的入度，就固定列，即第二个不动（固定终点不动），然后看这一列里有多少个不为0的数
	int vn, an;//节点数量为vn,边的数量为an
};
int main() {
	tu a;//定义一个图a
	cin >> a.vn >> a.an;//输入图a的节点数量以及边的数量
	for (int i = 0; i < a.an; i++) {//循环次数为边的数量，每个边连接起两个点
		int v1, v2;
		cin >> v1 >> v2;
		juzhen[v1][v2] = 1;
		juzhen[v2][v1] = 1;//这是无向图，如果为有向图，那么就只有第一行
		//即只有从起点到终点，而没有终点到起点
	}
	return 0;
}

邻接表?

这个表就是图中的节点，可以看成是一个数组，不过数组里记录的元素是以这个节点为起点的边，然后串起来的链表

创建一个大小为n的数组，其中n是图的顶点数。数组的每个元素都是链表的头指针，用来存储每个顶点的邻接点。

定义

#define maxn 100;
struct arcnode {
	int target;
	arcnode* nextarc;
};
struct vnode {
	int data;
	arcnode* firstarc;
};
struct tu {
	vnode lb[100];
	int vnum, anum;
};

边存储边的权值，以及边所连接的下一条边，对于数组中的同一个格子，起点都是相同的

节点 存储节点信息，然后有一个指针指向第一条边，通过访问这条边就可以访问到以该节点为起点的所有边

图就是把边和节点串在一起，每个数组里的元素就是一个链表，存储的是链表的头指针，然后链表元素存储指向下一个链表节点的指针

需要注意图的链表数组定义中，最好直接表明，不然会报错

struct arcnode {
	int adj;
	arcnode* nextarc;
};
struct vnode {
	int data;
	arcnode* firstarc;
};
struct tu {
	int vnum, anum;
	vnode vs[20];
};

构建

void creat(tu& g) {
	int i, k, v1, v2;
	cin >> g.vnum >> g.anum;
	for (i = 0; i < g.vnum; i++) {
		cin >> g.lb[i].data;
		g.lb[i].firstarc = nullptr;
	}
	for (k = 0; k < g.anum; k++) {
		cin >> v1 >> v2;
		arcnode* p1 = new arcnode;
		p1->target = v2;
		p1->nextarc = g.lb[v1].firstarc;
		g.lb[v1].firstarc = p1;
		arcnode* p2 = new arcnode;
		p2->target = v1;
		p2->nextarc = g.lb[v2].firstarc;
		g.lb[v2].firstarc = p2;
	}
}

构建就是先输入图的总边数以及结点数，然后初始化链表数组

接着就是输入边，为无向图时，要一次更新两个数组位置；

为有向图时，只更新一个数组位置?

方式就是链表的插入

7-1 数据结构实验三 图的深度优先搜索

采用邻接矩阵

struct tu {
	int vnum, arcnum;
	int arcs[20][20];
};
void creat(tu& a) {
	cin >> a.vnum >> a.arcnum;
	for (int i = 0; i < a.vnum; i++) {
		for (int j = 0; j < a.vnum; j++) {
			a.arcs[i][j] = 0;
		}
	}
	for (int i = 0; i < a.arcnum; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		a.arcs[v1][v2] = a.arcs[v2][v1] = 1;
	}
}

void dfs(tu a, int v) {
	cout << v << " ";
	visited[v] = 1;
	for (int i = 0; i < a.vnum; i++) {
		if (a.arcs[v][i] == 1) {
			if (visited[i] == 0) {
				dfs(a, i);
			}
		}
	}
}

PTA特性，一定需要初始化

不然的话二维数组开大了一定会保存奇怪的值导致得到错误的结果

就会导致在编译器上运行是正确的，但是在PTA上运行是错误的

7-2 抓住那头牛

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：

1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

关键词：bfs,队列元素为数对

#include<iostream>
#include<queue>
using namespace std;
int n, k;
const int N = 1e5 + 5;
int arr[N];
bool visited[N];
int capture(int n, int k) {
    queue<pair<int, int>>q;
    q.push(make_pair(n, 0));
    visited[n] = 1;
    while (!q.empty()) {
        int cur = q.front().first;
        int t = q.front().second;
        q.pop();
        if (cur == k) {
            return t;
        }
        int nextpos[3] = { cur - 1,cur + 1,cur * 2 };
        for (int i = 0; i < 3; i++) {
            if (nextpos[i] >= 0 && nextpos[i] <= N && !visited[nextpos[i]]) {
                q.push(make_pair(nextpos[i], t + 1));
                visited[nextpos[i]] = 1;
            }
        }
    }
    return -1;
}
int main() {
    cin >> n >> k;
    cout << capture(n, k);
    return 0;
}

判断题

For a sequentially stored linear list of length N, the time complexities for query and insertion are O(1) and O(N), respectively. 对于长度为N的顺序存储线性列表，查询和插入的时间复杂度分别为O(1)和O(N)。 T
The sum of the degrees of all the vertices in a connected graph must be an even number. 连通图中所有顶点的度数之和必须是偶数。 T

If a graph is represented by an adjacency matrix, then the space taken depends only on the number of vertices, not the number of edges. 如果一个图是用邻接矩阵表示的，那么所占用的空间只取决于顶点的数量，而不是边的数量。 T

In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. 在有向图中，所有顶点的入度和出度之和是总边数的两倍。 T

In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. 在有向图中，入度之和必须等于所有顶点出度之和。 T

?The best “worst-case time complexity” for any algorithm that sorts by comparisons only must be O(NlogN). 对于任何只通过比较排序的算法来说，最好的“最坏情况时间复杂度”必须是O(NlogN)。 T

To sort N records by simple selection sort, the numbers of comparisons and record movements are O(N^2) and O(N), respectively. 对N个记录进行简单选择排序，比较次数和记录移动次数分别为O(N2)和O(N)。T

?

?An AVL tree that all the balance factors of non-leaf nodes are 0 must be a perfect binary tree. 所有非叶节点的平衡因子均为0的AVL树必定是一棵完美二叉树。T

?

归并排序是稳定的

?就是树高，树高为LOGN

For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. 对于一个图，如果每个顶点都是偶数度，我们可以找到一个欧拉回路，它恰好访问每个顶点一次。 F
对于一个连通的图，如果每个顶点的度数都是偶数，那么该图一定存在一个欧拉回路（Euler circuit）。欧拉回路是一条经过图中每条边一次且仅一次的回路，它可以从任意顶点开始并回到该顶点。

注意欧拉回路是1.每个顶点的度数都是偶数2.经过每个边一次，而不是每个顶点一次

If a linear list is represented by a 1-dimensional array, the addresses of the elements in the memory must be consecutive. 如果线性列表用一维数组表示，那么内存中元素的地址必须是连续的。T

It is always possible to represent a tree by a one-dimensional integer array. 总是可以用一维整数数组来表示树。 T
The number of leaf nodes in a binary tree is only related to the number of 2-degree nodes , i.e it has nothing to do with the number of 1-degree nodes. 二叉树的叶节点数只与2度节点数相关，与1度节点数无关。 T

In a binary tree, if node A is a descendant of node B, A may precede B in the inorder traversal sequence. 在一棵二叉树中，如果节点a是节点B的后代，则在中序遍历序列中，a可以在B之前。 T

There must be a collision if we insert a new element into a hash table with the loading density being 1. 如果我们在加载密度为1的哈希表中插入一个新元素，就一定会发生碰撞。 T

如果有向图为强连通或弱连通，都至少需要V-1条边，弱连通就是类似于树状；强连通就是连成一个闭合的圆圈?

For the extra space taken by an internal sorting algorithm, we have: heap sort < quick sort < merge sort. 对于内部排序算法占用的额外空间，我们有:堆排序<快速排序<归并排序。 T

NlogN^2 and NlogN^3 have the same speed of growth. T

To sort N records by quick sort, the worst-case time complexity is Ω(NlogN). 对N条记录进行快速排序，最坏情况下时间复杂度为Ω(NlogN)。 T