数据结构实习

实习内容

一、马踏棋盘

问题描述

将马随机放在国际象棋的8×8棋盘[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制递归和非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。

程序代码

棋盘定义

#define ROW 8
#define COL 8
#define MAX_STEPS ROW*COL

定义每次的改变的相对坐标

int move_x[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int move_y[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

方法1：DFS（递归）

Dfs 函数是深度优先遍历函数，使用递归方式实现。

接受二维数组 path 表示棋盘，m 和 n 表示当前位置的坐标，edge 表示棋盘边长，count 表示已经访问的格子数。

函数首先判断是否已经访问了所有的格子，如果是则直接返回。

然后判断当前位置是否在棋盘范围内且未被访问过，如果是则增加已访问的格子数，将该位置标记为已访问，并进行递归调用，以便继续向下一位置探索。

//深度优先遍历（递归）
void Dfs(int path[8][8], int m, int n, int edge, int count)
{
	if (count >= edge * edge)//如果走过的格子数大于等于棋盘数
		return;
	if (m <= edge - 1 && n <= edge - 1 && m >= 0 && n >= 0 && path[m][n] == 0)//位置（m,n）在棋盘上，并且没有被走过
	{
		count++;//走过的格子数+1
		path[m][n] = count;//把该位置的值改为第几个走过的格子
		for (int i = 0; i < edge; i++)
			Dfs(path, m + move_x[i], n + move_y[i], edge, count);//进行递归，直到走过的格子数大于等于棋盘数
		return;
	}
}														

方法2：DFS+贪心算法（递归）

Dfs_tx 函数在深度优先遍历的基础上加入了贪心算法的思想，使用递归方式实现。

根据贪心算法的思想，计算每个可行方向的下一步可行方向的数量，

并选择具有最小可行方向数量的方向作为下一步的移动方向。

最后进行递归调用，继续向下一个位置探索。

void Dfs_tx(int flag[8][8], int path[8][8], int m, int n, int edge, int count, int found)
{
	if (found)return;// 如果已经找到完整路径，直接返回	
	if (count >= edge * edge)// 如果已经访问了所有方格
	{
		found += 1;// 将found标志设置为1，表示已找到完整路径
		for (int i = 0; i < edge; i++)
		{
			for (int j = 0; j < edge; j++)
				path[i][j] = flag[i][j];// 将当前路径复制到path数组中
		}
		return;
	}
	if (m > edge - 1 || n > edge - 1 || m < 0 || n < 0 || flag[m][n] != 0)return;// 如果当前位置超出边界或已被访问过，则返回

	count++;// 增加计数器(初始为0)
	flag[m][n] = count;// 标记当前位置为已访问
	//贪心部分，计算局部（两步）最优方向
	int count_next[8] = { -1,-1,-1,-1,-1,-1,-1,-1 };// 存储每个可行方向的下一步可行方向的数量
	for (int i = 0; i < edge; i++)
	{
		int m_next = m + move_x[i];// 下一步的 x坐标
		int n_next = n + move_y[i];// 下一步的 y坐标
		if (m_next < edge && n_next < edge && m_next >= 0 && n_next >= 0 && flag[m_next][n_next] == 0)//下一步的位置，未被访问则
		{
			count_next[i] ++;// 增加下一步可行方向的数量
			for (int j = 0; j < edge; j++)
			{
				int m_next_next = m_next + move_x[j];// 下一步的 下一步的 x坐标
				int n_next_next = n_next + move_y[j];// 下一步的 下一步的 y坐标
				if (m_next_next < edge && n_next_next < edge && m_next_next >= 0 && n_next_next >= 0 && flag[m_next_next][n_next_next] == 0)//下一步的下一步的位置，未被访问则
					count_next[i]++;// 增加下一步可行方向的数量*
			}
		}
	}
	int position = 0;// 选择下一步的最优方向
	for (int i = 0; i < edge; i++)//遍历count_next数组，找到具有最小可行方向数量的方向，将其存储在position变量中。
	{
		if (count_next[position] == -1)
			position = i;
		if ((count_next[i] < count_next[position]) && count_next[i] != -1)
		{
			position = i;
		}
	}
	Dfs_tx(flag, path, m + move_x[position], n + move_y[position], edge, count, found);
	flag[m][n] = 0;// 标记当前位置为未访问，以便在下一次递归中重新考虑该位置
}

方法3：DFS+贪心算法（非递归）

Dfs_tx_s 函数使用非递归方式实现的深度优先遍历算法，加入了贪心算法的思想。

该函数使用栈来保存待访问的位置，首先将起始位置入栈，然后进入一个循环，直到栈为空。

在循环中，取出栈顶的位置，判断是否已找到完整路径，如果是则直接返回。

然后判断当前位置是否超出边界或已被访问过，如果是则跳过当前位置。接下来增加已访问的格子数，并标记当前位置为已访问。

然后根据贪心算法的思想，计算每个可行方向的下一步可行方向的数量，并选择具有最小可行方向数量的方向作为下一步的移动方向，

将该位置入栈。最后继续下一轮循环，直到栈为空。

void Dfs_tx_s(int flag[8][8], int path[8][8], int m, int n, int edge, int count, int* found)
{
	if (*found)return;//// 如果已经找到完整路径，直接返回	
	//定义栈
	int stack_m[8 * 8];
	int stack_n[8 * 8];
	int top = 0;
	//将第一个元素入栈
	stack_m[top] = m;
	stack_n[top] = n;
	top++;

	while (top > 0) {
		//取出栈顶元素
		top--;
		m = stack_m[top];
		n = stack_n[top];

		if (count >= edge * edge) {//如果已经访问了所有方格
			*found = 1;// 将found标志设置为1，表示已找到完整路径
			for (int i = 0; i < edge; i++) {
				for (int j = 0; j < edge; j++)
					path[i][j] = flag[i][j];
			}// 将当前路径复制到path数组中
			return;
		}

		if (m > edge - 1 || n > edge - 1 || m < 0 || n < 0 || flag[m][n] != 0)
			continue;// 如果当前位置超出边界或已被访问过，则跳过

		count++;
		flag[m][n] = count;//// 标记当前位置为已访问
		//贪心，计算局部（两步）最优方向
		int count_next[8] = { -1, -1, -1, -1, -1, -1, -1, -1 };
		for (int i = 0; i < edge; i++) {
			int m_next = m + move_x[i];// 下一步的 x坐标
			int n_next = n + move_y[i];// 下一步的 y坐标
			if (m_next < edge && n_next < edge && m_next >= 0 && n_next >= 0 && flag[m_next][n_next] == 0) {//下一步的位置，未被访问则
				count_next[i]++;// 增加下一步可行方向的数量
				for (int j = 0; j < edge; j++) {
					int m_next_next = m_next + move_x[j];//下一步的 下一步的x坐标
					int n_next_next = n_next + move_y[j];//下一步的 下一步的y坐标
					if (m_next_next < edge && n_next_next < edge && m_next_next >= 0 && n_next_next >= 0 && flag[m_next_next][n_next_next] == 0)//下一步的下一步的位置，未被访问则
						count_next[i]++; //增加下一步可行方向的数量*
				}
			}
		}

		int position = 0;
		for (int i = 0; i < edge; i++) {//遍历count_next数组，找到具有最小可行方向数量的方向，将其存储在position变量中。
			if (count_next[position] == -1)
				position = i;
			if ((count_next[i] < count_next[position]) && count_next[i] != -1) {
				position = i;
			}
		}

		stack_m[top] = m + move_x[position];
		stack_n[top] = n + move_y[position];
		top++;
	}
}

主函数的调用：

定义了两个二维数组 path 和 flag，分别用于记录最终路径和临时路径。

初始化变量 m 和 n，表示起始位置的坐标。, edge，表示棋盘的大小（边长）,found，表示完整路径的标志，初始值为 0。

根据用户输入的序号，使用 switch 语句选择相应的解决方法。

int main() {
	int path[8][8] = { 0 };// 记录最终路径
	int flag[8][8] = { 0 };// 记录临时路径
	int m, n;
	int edge;
	int found = 0;// 完整路径标志
	int switch_on;
	m = 1;
	n = 1;
	edge = 8;// 棋盘大小
	printf("1:使用深度优先搜索（递归）\n");
	printf("2:使用深度优先搜索+贪心算法（递归）\n");
	printf("3:使用深度优先搜索+贪心算法（非递归）\n");
	printf("4:退出\n");

	while (1) {
		printf("输入序号，以选择解决方法：");
		scanf_s("%d", &switch_on);
		switch (switch_on)
		{
		case 1:
			Dfs(path, m, n, edge, 0);
			for (int i = 0; i < edge; i++) {
				for (int j = 0; j < edge; j++)
				{
					printf("%2d ", path[i][j]);
				}
				printf("\n");
			}
			;
			break;
		case 2:
			Dfs_tx(flag, path, m, n, edge, 0, found);
			for (int i = 0; i < edge; i++) {
				for (int j = 0; j < edge; j++)
				{
					printf("%2d ", path[i][j]);
				}
				printf("\n");
			}
			break;
		case 3:
			Dfs_tx_s(flag, path, m, n, edge, 0, &found);
			if (found) {
				for (int i = 0; i < edge; i++) {
					for (int j = 0; j < edge; j++)
						printf("%2d ", path[i][j]);
					printf("\n");
				}
			}
			else {
				printf("没有找到路径\n");
			}
			break;
		case 4:
			return 0;
		default:
			printf("请输入正确的序号");
			break;
		}
	}
	return 0;
}

二、迷宫问题

问题描述

以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归和非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

程序代码

初始化迷宫

// 迷宫的行列数
int M = 10, N = 10;

// 迷宫数组初始化
maze[10][10] = {
	{0, 0, 0, 1, 0, 0, 0, 1, 1, 0},
	{1, 0, 1, 1, 0, 1, 0, 1, 0, 0},
	{1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
	{1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
	{1, 0, 1, 0, 1, 0, 0, 0, 1, 1},
	{0, 1, 1, 1, 0, 0, 1, 1, 1, 0},
	{0, 0, 0, 1, 1, 0, 1, 1, 1, 0},
	{0, 1, 1, 1, 0, 0, 0, 0, 1, 0},
	{0, 1, 1, 1, 0, 1, 0, 1, 0, 0},
	{1, 1, 0, 0, 0, 1, 0, 0, 0, 0}
};

定义栈的基本结构

StackNode 节点

Stack 栈

// 栈的节点
typedef struct StackNode {
	int x, y, direction;
	struct StackNode* next;
} StackNode;

// 栈结构
typedef struct {
	StackNode* top;
} Stack;

定义栈的基本方法

initStack ( ) 初始化栈

isStackEmpty ( ) 判断栈是否为空

push ( ) 入栈

pop ( ) 出栈

top（）获取栈顶元素

// 初始化栈
void initStack(Stack* stack) {
	stack->top = NULL;
}

// 判断栈是否为空
bool isStackEmpty(Stack* stack) {
	return stack->top == NULL;
}

// 入栈
void push(Stack* stack, int x, int y, int direction) {
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->x = x;
	node->y = y;
	node->direction = direction;
	node->next = stack->top;
	stack->top = node;
}

// 出栈
void pop(Stack* stack) {
	if (isStackEmpty(stack)) {
		return;
	}
	StackNode* node = stack->top;
	stack->top = node->next;
	free(node);
}

// 获取栈顶元素
void top(Stack* stack, int* x, int* y, int* direction) {
	if (isStackEmpty(stack)) {
		return;
	}
	*x = stack->top->x;
	*y = stack->top->y;
	*direction = stack->top->direction;
}

检查坐标是否有效

(x,y)在棋盘上，并且标记为0

bool isValid(int x, int y) {
	return x >= 0 && x < M && y >= 0 && y < N && maze[x][y] == 0;
}

递归求解迷宫通路

首先检查当前坐标 (x, y) 是否为有效的路径节点，即判断是否在迷宫范围内且对应的迷宫数组值为 0（通路）。

如果当前坐标无效，返回 false，表示没有通路。

将当前坐标 (x, y) 入栈，表示已访问该节点。

将迷宫数组中的值标记为 2，表示该节点已访问过。

如果当前坐标是迷宫的出口 (M-1, N-1)，则返回 true，表示找到了通路。

递归尝试四个方向：向右 (x, y+1)、向下 (x+1, y)、向左 (x, y-1)、向上 (x-1, y)。

如果其中任意方向返回 true，表示找到了通路，直接返回 true。

如果以上四个方向都没有找到通路，说明当前节点不在通路上，将其从栈中弹出并清除标记。

返回 false，表示没有找到通路。

bool solveMazeRecursive(int x, int y, Stack* stack) {
	if (!isValid(x, y)) {
		return false;
	}

	push(stack, x, y, -1); // 入栈，初始方向为-1

	maze[x][y] = 2; // 标记已访问

	if (x == M - 1 && y == N - 1) {
		return true; // 到达出口
	}
	int direction; // 添加direction变量
	// 尝试四个方向
	if ((direction = 0, solveMazeRecursive(x, y + 1, stack)) || // 向右
		(direction = 1, solveMazeRecursive(x + 1, y, stack)) || // 向下
		(direction = 2, solveMazeRecursive(x, y - 1, stack)) || // 向左
		(direction = 3, solveMazeRecursive(x - 1, y, stack))) { // 向上
		push(stack, x, y, direction); // 入栈，保存方向
		return true;
	}
	pop(stack); // 从栈中移除
	maze[x][y] = 0; // 清除标记

	return false;
}

非递归求解迷宫通路

1. 初始化当前坐标 (x, y) 为起点 (0, 0)，并将初始方向 direction 设为 0。
2. 进入一个循环，直到找到通路或确定没有通路。
3. 检查当前坐标 (x, y) 是否为有效的路径节点，即判断是否在迷宫范围内且对应的迷宫数组值为 0（通路）。
4. 如果当前坐标有效，将其入栈，表示已访问该节点。将迷宫数组中的值标记为 2，表示该节点已访问过。
5. 如果当前坐标是迷宫的出口 (M-1, N-1)，则返回 true，表示找到了通路。
6. 设置方向 direction 为 0，表示方向。
7. 更新坐标 (x, y) 为下一个节点，根据方向 direction 的不同进行相应的移动操作。
8. 如果方向小于 3，表示还有方向未尝试，递增方向并继续进行下一次循环。
9. 如果方向大于等于 3，表示四个方向都尝试过，说明当前节点不在通路上。
10. 检查栈是否为空，如果为空，表示已经回到起点且没有找到通路，返回 false。
11. 从栈顶获取上一个节点的坐标和方向，将其作为当前节点继续进行下一次循环。
12. 根据方向进行相应的坐标更新操作。
13. 回到步骤 3，继续进行下一次循环。

bool solveMazeIterative(Stack* stack) {
	int x = 0, y = 0, direction = 0;
	while (true) {
		if (isValid(x, y)) {
			push(stack, x, y, direction); // 入栈
			maze[x][y] = 2; // 标记已访问

			if (x == M - 1 && y == N - 1) {
				return true; // 到达出口
			}
			direction = 0;
			y++;
		}
		else {
			if (direction < 3) {//如果方向小于 3，表示还有方向未尝试，递增方向并继续进行下一次循环。
				direction++;
				switch (direction) {
				case 1: // 向右
					x++;
					break;
				case 2: // 向下
					y--;
					break;
				case 3: // 向左
					x--;
					break;
				}
			}
			else {
				if (isStackEmpty(stack)) {//如果方向大于等于 3，表示四个方向都尝试过，说明当前节点不在通路上。
					return false; // 无通路
				}
				top(stack, &x, &y, &direction);//从栈顶获取上一个节点的坐标和方向，将其作为当前节点继续进行下一次循环。
				pop(stack); // 从栈中移除
				switch (direction) {
				case 0: // 向上
					y++;
					break;
				case 1: // 向右
					x++;
					break;
				case 2: // 向下
					y--;
					break;
				case 3: // 向左
					x--;
					break;
				}
			}
		}
	}
}

打印迷宫和通路

□ 表示通路

■ 表示障碍

★ 表示通路上的路径

void printMaze(Stack* stack) {
	printf("迷宫及通路：\n");

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (maze[i][j] == 0) {
				printf("□ "); // 通路
			}
			else if (maze[i][j] == 1) {
				printf("■ "); // 障碍
			}
			else if (maze[i][j] == 2) {
				printf("★ "); // 通路上的路径
			}
		}
		printf("\n");
	}

	printf("\n通路：\n");

	StackNode* node = stack->top;

	while (node != NULL) {
		switch (node->direction) {
		case 0:
			printf("(%d, %d, E)\n", node->x + 1, node->y + 1);
			break;
		case 1:
			printf("(%d, %d, S)\n", node->x + 1, node->y + 1);
			break;
		case 2:
			printf("(%d, %d, W)\n", node->x + 1, node->y + 1);
			break;
		case 3:
			printf("(%d, %d, N)\n", node->x + 1, node->y + 1);
			break;
		default:
			break;
		}
		node = node->next;
	}

}

主函数的调用

int main() {


	Stack stack;
	printf("1:递归求解迷宫通路\n");
	printf("2:非递归求解迷宫通路\n");
	printf("3:不走迷宫了\n");

	int switch_on = 0;
	printf("输入序号：");
	scanf_s("%d", &switch_on);
	switch (switch_on)
	{
	case 1:
		// 使用递归求解迷宫通路
		initStack(&stack);
		if (solveMazeRecursive(0, 0, &stack)) {
			printMaze(&stack);
		}
		else {
			printf("迷宫没有通路。\n");
		}
		break;
	case 2:
		initStack(&stack);

		// 使用非递归求解迷宫通路
		if (solveMazeIterative(&stack)) {
			printMaze(&stack);
		}
		else {
			printf("迷宫没有通路。\n");
		}
		break;
	case 3:
		return 0;
	default:printf("请输入正确的序号");
		break;
	}
	return 0;
}

查找算法比较

问题描述

1. 对以下6种常用的内部排序算法进行比较：顺序查找，折半查找，分块查找，插值查找，斐波那契查找，二叉树查找。

2. 待查找表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关关键字参加的比较次数。

3. 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。

程序代码

顺序查找

int sequentialSearch(int arr[], int size, int key) {
    int comparisons = 0;
    int i;
    for (i = 0; i < size; i++) {
        comparisons++;
        if (arr[i] == key) {
            return comparisons;
        }
    }
    return comparisons;
}

折半查找（二分查找）

int binarySearch(int arr[], int size, int key) {
    int comparisons = 0;
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        comparisons++;
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return comparisons;
        }
        if (arr[mid] < key) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return comparisons;
}

分块查找

int blockSearch(int arr[], int blockSizes[], int blockNum, int key) {
    int comparisons = 0;
    int i, j;
    for (i = 0; i < blockNum; i++) {
        comparisons++;
        if (blockSizes[i] >= key) {
            break;
        }
    }
    if (i == 0) {
        return comparisons;
    }
    int blockSize = 20;
    int start = i * blockSize - blockSize;
    int end = i * blockSize;
    for (j = start; j < end; j++) {
        comparisons++;
        if (arr[j] == key) {
            return comparisons;
        }
    }
    return comparisons;
}

插值查找

改进的二分查找算法，它通过对数组进行估算，试图根据查找键的值在数组中的分布情况来预测该键可能出现的位置。公式int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])用于计算估算的位置。

int interSearch(int arr[], int size, int key) {
    int comparisons = 0;
    int low = 0;
    int high = size - 1;
    while (low <= high && key >= arr[low] && key <= arr[high]) {
        comparisons++;
        if (low == high) {
            if (arr[low] == key) {
                return comparisons;
            }
            return comparisons;
        }
        int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        if (arr[pos] == key) {
            return comparisons;
        }
        if (arr[pos] < key) {
            low = pos + 1;
        }
        else {
            high = pos - 1;
        }
    }
    return comparisons;
}

斐波那契查找

int fibonacciSearch(int arr[], int size, int key) {
    int comparisons = 0;  // 记录比较次数的变量
    int fib2 = 0;  // 第一个斐波那契数
    int fib1 = 1;  // 第二个斐波那契数
    int fib = fib1 + fib2;  // 当前斐波那契数

    // 找到大于等于数组大小的最小斐波那契数
    while (fib < size) {
        fib2 = fib1;
        fib1 = fib;
        fib = fib1 + fib2;
    }
    
	 //用于确定待查找数组的起始位置，它随着迭代的进行不断更新，以便逼近目标元素的位置
    int offset = -1;  // 用于索引的偏移值

    // 进行斐波那契查找
    while (fib > 1) {
        comparisons++;
        int i = (offset + fib2) < (size - 1) ? (offset + fib2) : (size - 1);

        if (arr[i] < key) {
            // 关键字比当前元素大，向下移动斐波那契数
            fib = fib1;
            fib1 = fib2;
            fib2 = fib - fib1;
            offset = i;
        } else if (arr[i] > key) {
            // 关键字比当前元素小，进一步向下移动斐波那契数
            fib = fib2;
            fib1 = fib1 - fib2;
            fib2 = fib - fib1;
        } else {
            // 关键字在索引 i 处找到
            return comparisons;
        }
    }

    // 检查数组中最后一个元素（fib1 == 1）
    if (fib1 == 1 && arr[offset + 1] == key) {
        return comparisons;
    }

    // 未在数组中找到关键字
    return comparisons;
}

二叉树查找节点

// 二叉树节点
typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建二叉树节点
TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 二叉树插入节点
TreeNode* insertNode(TreeNode* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->value) {
        root->left = insertNode(root->left, value);
    }
    else if (value > root->value) {
        root->right = insertNode(root->right, value);
    }
    return root;
}

// 二叉树查找节点
int searchNode(TreeNode* root, int key) {
    int comparisons = 0;

    while (root != NULL) {
        comparisons++;

        if (root->value == key) {
            return comparisons;
        }
        else if (key < root->value) {
            root = root->left;
        }
        else {
            root = root->right;
        }
    }

    return comparisons;
}

生成顺序数据集

void getSequen(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = i + 1;
    }
}

主函数调用

int main() {
    // 生成顺序数据集
    int dataset[200];
    getSequen(dataset, 200);

    // 统计每种算法的比较次数
    int seqComp = 0;
    int binComp = 0;
    int blockComp = 0;
    int inteComp = 0;
    int fibComp = 0;
    int binTreeComp = 0;

    // 进行10次随机数的查找
    int i;
    for (i = 0; i < 10; i++) {
        srand(time(NULL));
        int key = rand() % 200 + 1;

        // 顺序查找
        int comparisons = sequentialSearch(dataset, 200, key);
        seqComp += comparisons;

        // 折半查找
        comparisons = binarySearch(dataset, 200, key);
        binComp += comparisons;

        // 分块查找
        int blockSizes[10] = { 20, 40, 60, 80, 100, 120, 140, 160, 180, 200 };
        comparisons = blockSearch(dataset, blockSizes, 10, key);
        blockComp += comparisons;

        // 插值查找
        comparisons = interSearch(dataset, 200, key);
        inteComp += comparisons;

        // 斐波那契查找
        comparisons = fibonacciSearch(dataset, 200, key);
        fibComp += comparisons;

        // 二叉树查找
        TreeNode* root = NULL;
        for (int j = 0; j < 200; j++) {
            root = insertNode(root, dataset[j]);
        }
        comparisons = searchNode(root, key);
        binTreeComp += comparisons;
    }

    // 计算平均比较次数
    float avgSequential = seqComp / 10.0;
    float avgBinary = binComp / 10.0;
    float avgBlock = blockComp / 10.0;
    float avgInterpolation = inteComp / 10.0;
    float avgFibonacci = fibComp / 10.0;
    float avgBinaryTree = binTreeComp / 10.0;

    // 打印结果
    printf("顺序查找平均比较次数：%.2f\n", avgSequential);
    printf("折半查找平均比较次数：%.2f\n", avgBinary);
    printf("分块查找平均比较次数：%.2f\n", avgBlock);
    printf("插值查找平均比较次数：%.2f\n", avgInterpolation);
    printf("斐波那契查找平均比较次数：%.2f\n", avgFibonacci);
    printf("二叉树查找平均比较次数：%.2f\n", avgBinaryTree);

    return 0;
}

内部排序算法比较

问题描述

1. 对以下6种常用的内部排序算法进行比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。

2. 待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

3. 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。

程序代码

冒泡排序

void bubbleSort(int arr[], int n, int* comparisons, int* moves) {
	int i, j;
	for (i = 0; i < n - 1; i++) {
		for (j = 0; j < n - i - 1; j++) {
			(*comparisons)++;
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				(*moves) += 3;
			}
		}
	}
}

直接插入排序

待排序的数组分为已排序和未排序两部分。初始时，将数组的第一个元素视为已排序部分，其余元素为未排序部分。然后，依次从未排序部分取出一个元素，插入到已排序部分的正确位置，使得已排序部分仍然保持有序。

void insertionSort(int arr[], int n, int* comparisons, int* moves) {
	int i, j;
	for (i = 1; i < n; i++) {
		int key = arr[i]; // 当前要插入的元素
		j = i - 1; // 从当前元素的前一个元素开始比较
		(*moves)++;
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j]; // 将大于当前元素的元素后移
			j = j - 1; // 继续向前比较
			(*comparisons)++;
			(*moves) += 2;
		}
		arr[j + 1] = key; // 插入当前元素到正确的位置
		(*moves)++;
	}
}

简单选择排序

算法每次从未排序的部分选择最小的元素，并将其放到已排序部分的末尾。

i 控制已排序部分的末尾位置，初始值为 0。min_idx 存储未排序部分的最小元素的索引。

内层循环从 i+1 开始遍历未排序部分，找到最小元素的索引。

如果当前元素比已记录的最小元素小，则更新最小元素的索引。比较过程中。

外层循环中，将找到的最小元素与已排序部分的末尾元素进行交换。。这样每一次外层循环都会将未排序部分的最小元素放到已排序部分的末尾。

void selectionSort(int arr[], int n, int* comparisons, int* moves) {
	int i, j, min_idx;
	for (i = 0; i < n - 1; i++) {
		min_idx = i; // 假设当前位置为最小值的索引
		for (j = i + 1; j < n; j++) {
			(*comparisons)++;
			if (arr[j] < arr[min_idx]) {
				min_idx = j; // 更新最小值的索引
			}
		}
		int temp = arr[min_idx];
		arr[min_idx] = arr[i];
		arr[i] = temp;
		(*moves) += 3; // 交换最小值和当前位置的元素，并增加移动计数
	}
}

快速排序

基于分治的思想，通过将数组分割为较小的子数组，然后递归地对子数组进行排序，最终将整个数组排序完成。

1. 选择一个基准元素（pivot），通常可以选择数组的最后一个元素作为基准。
2. 设置两个指针 i 和 j，初始时分别指向数组的第一个元素和最后一个元素。
3. 从左边开始，找到第一个大于等于基准元素的元素，记为 arr[i]。从右边开始，找到第一个小于等于基准元素的元素，记为 arr[j]。
4. 如果 i 小于 j，交换 arr[i] 和 arr[j]。
5. 重复步骤 3 和步骤 4，直到 i 不再小于 j。
6. 将基准元素 arr[high]（初始选择的最后一个元素）与 arr[i]（当前 i 指向的元素）交换位置，将基准元素放置在最终的位置上。
7. 现在，基准元素左边的元素都小于它，右边的元素都大于它。
8. 递归地对基准元素左边的子数组（arr[low] 到 arr[i-1]）和右边的子数组（arr[i+1] 到 arr[high]）进行快速排序。
9. 重复上述步骤，直到每个子数组的大小为 1 或者为空。

快速排序的核心操作是分区（partition）和递归排序。分区操作根据基准元素将数组划分为两个部分，其中一部分的元素都小于基准元素，另一部分的元素都大于基准元素。递归排序对分区后的子数组进行递归调用，直到数组被完全排序

int partition(int arr[], int low, int high, int* comparisons, int* moves) {
	int pivot = arr[high]; // 选择最后一个元素作为基准值
	int i = low - 1;
	int j;
	for (j = low; j <= high - 1; j++) {
		(*comparisons)++;
		if (arr[j] < pivot) {
			i++;
			// 交换 arr[i] 和 arr[j]
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			(*moves) += 3;
		}
	}
	// 将基准值放置到正确的位置
	int temp = arr[i + 1];
	arr[i + 1] = arr[high];
	arr[high] = temp;
	(*moves) += 3;
	return (i + 1); // 返回基准值的索引
}

// 快速排序算法
void quickSort(int arr[], int low, int high, int* comparisons, int* moves) {
	if (low < high) {
		// 找到基准值的索引
		int pivot = partition(arr, low, high, comparisons, moves);
		// 递归地对基准元素左边的子数组进行排序
		quickSort(arr, low, pivot - 1, comparisons, moves);
		// 递归地对基准元素右边的子数组进行排序
		quickSort(arr, pivot + 1, high, comparisons, moves);
	}
}

希尔排序

是插入排序的一种改进算法，通过将待排序的数组按一定间隔分组，对每个分组进行插入排序，然后逐渐缩小间隔，最终完成整个数组的排序。

void shellSort(int arr[], int n, int* comparisons, int* moves) {
	int gap, i, j;

	// 使用希尔增量，初始间隔为数组长度的一半，逐渐缩小间隔
	for (gap = n / 2; gap > 0; gap /= 2) {
		// 对每个分组进行插入排序
		for (i = gap; i < n; i++) {
			int temp = arr[i];

			// 在当前分组内进行插入排序
			for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
				arr[j] = arr[j - gap];
				(*comparisons)++;
				(*moves)++;
			}

			arr[j] = temp;
			(*moves)++;
		}
	}
}

堆排序

堆排序通过构建最大堆和逐步调整堆实现排序

void heapify(int arr[], int n, int i, int* comparisons, int* moves) {
	int largest = i;
	int l = 2 * i + 1;
	int r = 2 * i + 2;

	// 比较左子节点和根节点的值，找出较大的节点
	if (l < n) {
		(*comparisons)++;
		if (arr[l] > arr[largest]) {
			largest = l;
		}
	}

	// 比较右子节点和当前最大节点的值，找出最大的节点
	if (r < n) {
		(*comparisons)++;
		if (arr[r] > arr[largest]) {
			largest = r;
		}
	}

	// 如果最大节点不是当前节点，进行交换并继续调整子树
	if (largest != i) {
		int temp = arr[i];
		arr[i] = arr[largest];
		arr[largest] = temp;
		(*moves) += 3;
		heapify(arr, n, largest, comparisons, moves);
	}
}

void heapSort(int arr[], int n, int* comparisons, int* moves) {
	int i;

	// 构建初始最大堆
	for (i = n / 2 - 1; i >= 0; i--) {
		heapify(arr, n, i, comparisons, moves);
	}

	// 逐步将最大元素移到数组末尾并调整堆
	for (i = n - 1; i > 0; i--) {
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		(*moves) += 3;
		heapify(arr, i, 0, comparisons, moves);
	}
}

生成不同的随机数

// 生成大体上升序的随机数
void getAscRandom(int arr[], int size) {
	srand(time(NULL));
	arr[0] = rand() % 100; // 随机生成第一个数
	for (int i = 1; i < size; i++) {
		int range = rand() % 10 + 1; // 生成随机的增加范围
		if (rand() % 10 < 3) {
			arr[i] = arr[i - 1] - range; // 基于前一个数减少范围得到当前数
		}
		else {
			arr[i] = arr[i - 1] + range; // 基于前一个数增加范围得到当前数
		}

	}
}

// 生成大体上降序的随机数
void getDescRandom(int arr[], int size) {
	srand(time(NULL));
	arr[0] = rand() % 100; // 随机生成第一个数
	for (int i = 1; i < size; i++) {
		int range = rand() % 10 + 1; // 生成随机的增加范围
		if (rand() % 10 > 3) {
			arr[i] = arr[i - 1] - range; // 基于前一个数减少范围得到当前数
		}
		else {
			arr[i] = arr[i - 1] + range; // 基于前一个数增加范围得到当前数
		}

	}
}

// 生成随机数
void getRandom(int arr[], int size) {
	srand(time(NULL));
	for (int i = 0; i < size; i++) {
		arr[i] = rand() % 500;
	}
}

针对不同的随机数编写不同的比较次数和关键字的移动次数的统计方法

void comp_Random(void(*searchFunction)())
{
	int input_data[200] = { 0 };
	int comparisons, moves;
	comparisons = 0; moves = 0;
	for (int i = 0; i < 5; i++) {
		getRandom(input_data, 200);
		searchFunction(input_data, 200, &comparisons, &moves);
	}
	printf("比较次数: %d\n", comparisons/5);
	printf("移动次数: %d\n\n", moves/5);
}
void comp_q_Random(void(*searchFunction)())//因为快速排序的参数传输和其他函数不同，额外编写的。
{
	int input_data[200] = { 0 };
	int comparisons, moves;
	comparisons = 0; moves = 0;
	for (int i = 0; i < 5; i++) {
		getRandom(input_data, 200);
		searchFunction(input_data, 0,199, &comparisons, &moves);
	}
	printf("比较次数: %d\n", comparisons / 5);
	printf("移动次数: %d\n\n", moves / 5);
}

void comp_AscRandom(void(*searchFunction)())
{
	int input_data[200] = { 0 };
	int comparisons, moves;
	comparisons = 0; moves = 0;
	for (int i = 0; i < 5; i++) {
		getAscRandom(input_data, 200);
		searchFunction(input_data, 200, &comparisons, &moves);
	}
	printf("比较次数: %d\n", comparisons / 5);
	printf("移动次数: %d\n\n", moves / 5);
}
void comp_q_AscRandom(void(*searchFunction)())
{
	int input_data[200] = { 0 };
	int comparisons, moves;
	comparisons = 0; moves = 0;
	for (int i = 0; i < 5; i++) {
		getAscRandom(input_data, 200);
		searchFunction(input_data, 0, 199, &comparisons, &moves);
	}
	printf("比较次数: %d\n", comparisons / 5);
	printf("移动次数: %d\n\n", moves / 5);
}

void comp_DescRandom(void(*searchFunction)())
{
	int input_data[200] = { 0 };
	int comparisons, moves;
	comparisons = 0; moves = 0;
	for (int i = 0; i < 5; i++) {
		getRandom(input_data, 200);
		searchFunction(input_data, 200, &comparisons, &moves);
	}
	printf("比较次数: %d\n", comparisons / 5);
	printf("移动次数: %d\n\n", moves / 5);
}
void comp_q_DescRandom(void(*searchFunction)())
{
	int input_data[200] = { 0 };
	int comparisons, moves;
	comparisons = 0; moves = 0;
	for (int i = 0; i < 5; i++) {
		getRandom(input_data, 200);
		searchFunction(input_data, 0, 199, &comparisons, &moves);
	}
	printf("比较次数: %d\n", comparisons / 5);
	printf("移动次数: %d\n\n", moves / 5);
}

主函数实现

主要为程序的调用

int main(){
	printf("数据集为随机数据：\n");
	printf("冒泡排序:\n");
	comp_Random(bubbleSort);
	printf("直接插入排序:\n");
	comp_Random(insertionSort);
	printf("简单选择排序:\n");
	comp_Random(selectionSort);
	printf("快速排序:\n");
	comp_q_Random(quickSort);
	printf("希尔排序:\n");
	comp_Random(shellSort);
	printf("堆排序:\n");
	comp_Random(heapSort);
	printf("\n");

	printf("数据集为大体上升序的随机数：\n");
	printf("冒泡排序:\n");
	comp_AscRandom(bubbleSort);
	printf("直接插入排序:\n");
	comp_AscRandom(insertionSort);
	printf("简单选择排序:\n");
	comp_AscRandom(selectionSort);
	printf("快速排序:\n");
	comp_q_AscRandom(quickSort);
	printf("希尔排序:\n");
	comp_AscRandom(shellSort);
	printf("堆排序:\n");
	comp_AscRandom(heapSort);
	printf("\n");

	printf("数据集为大体上降序的随机数：\n");
	printf("冒泡排序:\n");
	comp_DescRandom(bubbleSort);
	printf("直接插入排序:\n");
	comp_DescRandom(insertionSort);
	printf("简单选择排序:\n");
	comp_DescRandom(selectionSort);
	printf("快速排序:\n");
	comp_q_DescRandom(quickSort);
	printf("希尔排序:\n");
	comp_DescRandom(shellSort);
	printf("堆排序:\n");
	comp_DescRandom(heapSort);
	printf("\n");
	return 0;
}

在数据集大小为200的情况下：

1. 冒泡排序（Bubble Sort）：
   • 平均时间复杂度：O(n^2)
   • 最坏时间复杂度：O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：稳定
   • 适用于小规模数据排序
   • 比较次数：最好情况为0，最坏情况为19900
   • 移动次数：最好情况为0，最坏情况为59700
2. 直接插入排序（Insertion Sort）：
   • 平均时间复杂度：O(n^2)
   • 最坏时间复杂度：O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：稳定
   • 适用于基本有序的数据排序
   • 比较次数：最好情况为199，最坏情况为19900
   • 移动次数：最好情况为199，最坏情况为59700
3. 简单选择排序（Selection Sort）：
   • 平均时间复杂度：O(n^2)
   • 最坏时间复杂度：O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：不稳定
   • 适用于数据量较小的排序
   • 比较次数：最好情况为19900，最坏情况为19900
   • 移动次数：最好情况为0，最坏情况为59700
4. 快速排序（Quick Sort）：
   • 平均时间复杂度：O(nlogn)
   • 最坏时间复杂度：O(n^2)
   • 空间复杂度：O(logn)~O(n)
   • 稳定性：不稳定
   • 适用于大规模数据排序
   • 比较次数：最好情况为1526，最坏情况为19900
   • 移动次数：最好情况为0，最坏情况为59700
5. 希尔排序（Shell Sort）：
   • 平均时间复杂度：取决于增量序列的选择
   • 最坏时间复杂度：取决于增量序列的选择
   • 空间复杂度：O(1)
   • 稳定性：不稳定
   • 适用于中等规模数据排序
   • 比较次数：最好情况为1247，最坏情况为19900
   • 移动次数：最好情况为0，最坏情况为59700
6. 堆排序（Heap Sort）：
   • 平均时间复杂度：O(nlogn)
   • 最坏时间复杂度：O(nlogn)
   • 空间复杂度：O(1)
   • 稳定性：不稳定
   • 适用于大规模数据排序
   • 比较次数：最好情况为1296，最坏情况为19900
   • 移动次数：最好情况为0，最坏情况为59700

不同数据集的影响

1. 冒泡排序（Bubble Sort）：
   • 随机数据：由于每次比较只交换相邻元素，随机数据的冒泡排序性能较差，需要较多的比较和交换操作，波动较大。
   • 大体上升序的随机数：冒泡排序在大体上升序的随机数上性能较好，因为大部分元素已经有序，只需要少量的比较和交换操作，波动较小。
   • 大体下降序的随机数：冒泡排序在大体下降序的随机数上性能较差，需要较多的比较和交换操作来逆转递减序列，波动较大。
2. 插入排序（Insertion Sort）：
   • 随机数据：插入排序在随机数据上的性能较好，因为每个元素都与前面有序的部分进行比较，插入到正确的位置，波动较小。
   • 大体上升序的随机数：插入排序在大体上升序的随机数上性能较好，只需要少量的比较操作就可以找到正确位置，波动较小。
   • 大体下降序的随机数：插入排序在大体下降序的随机数上性能较差，需要较多的比较和移动操作来逆转递减序列，波动较大。
3. 快速排序（Quick Sort）：
   • 随机数据：快速排序在随机数据上的性能通常较好，它通过选择一个基准值并分区来排序，波动较小。
   • 大体上升序的随机数：快速排序在大体上升序的随机数上的性能可能会略好一些，因为它能快速划分已经有序的部分，波动较小。
   • 大体下降序的随机数：快速排序在大体下降序的随机数上的性能较差，需要较多的比较和划分操作，波动较大。
4. 希尔排序（Shell Sort）：
   • 随机数据：希尔排序在随机数据上的性能通常较好，它通过将数组分成多个子序列进行插入排序，逐渐缩小子序列的间隔，最终完成排序，波动较小。
   • 大体上升序的随机数：希尔排序在大体上升序的随机数上的性能较好，由于大部分元素已经有序，插入排序的次数会减少，波动较小。
   • 大体下降序的随机数：希尔排序在大体下降序的随机数上的性能较差，需要较多的比较和移动操作来逆转递减序列，波动较大。
5. 堆排序（Heap Sort）：
   • 随机数据：堆排序在随机数据上的性能通常较好，它通过构建最大堆（或最小堆）来进行排序，具有较好的稳定性和较少的波动。
   • 大体上升序的随机数：堆排序在大体上升序的随机数上的性能较好，最大堆的构建过程较快，而排序过程中的比较和交换操作相对较少，波动较小。
   • 大体下降序的随机数：堆排序在大体下降序的随机数上的性能较好，最小堆的构建过程较快，而排序过程中的比较和交换操作相对较少，波动较小。