【C实战经验】C语言基础算法归纳总结

  • 时间:
  • 浏览:
  • 来源:互联网

—— 归纳总结 ——

  • 序 & 纲要
  • ◉ 排序 & 查找
    • —① 冒泡排序
    • —② 选择排序
    • —③ 快速排序
    • —④ 二分查找法
  • ◉ 链表
    • —① 插入结点(四种方法)
    • —② 删除结点
  • ◉ 数学算法
    • —① 判断素数
    • —② 两数交换(三种方法)
    • —② 最大公约数
    • —③ 最小公倍数
    • —④ 其他进制转十进制
    • —⑤ 十进制转其他进制
  • ◉ 其他算法
    • —① 统计单词数


序 & 纲要

以下的所有算法全部以函数的形式出现,可以直接单独拿出来用

  1. 冒泡排序选择排序快速排序 的实现方法和原理
  2. 链表增加结点的四种方式:头插法尾插法随机插法下标插法
  3. 两数交换的三种方法:中间量法加减乘除法异或法
  4. 判断素数最大公约数最小公倍数进制转换

◉ 排序 & 查找

—① 冒泡排序

void sort1(int array[], int len)
{
	int temp;	// 交换两数

	for (int i = len - 1; i > 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (array[j] > array[j + 1])
			{
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
}

解释:

  • i 的初始值:len - 1 ,表示 i 从数组的最后一项开始,往前缩。
  • i 的临界值:0 ,表示直到缩至数组的第二项排序完毕
  • j 的初始值:0 ,表示每次都从第一项开始与下一项进行比较
  • j 的临界值:i ,表示走到数组的倒数第二项停下,因为有 j+1 存在,不能走到最后一项停,倒数第二项就覆盖整个数组了

—② 选择排序

void sort2(int array[], int len)
{
	int temp;	// 交换两数
	int min;	// 记录当前最小值

	for (int i = 0; i < len - 1; i++)
	{
		min = i;  // 把最小值置为当前值

		for (int j = i + 1; j < len; j++)
		{
			if (array[j] < array[min]) min = j;  // 保证 min 是当前最小
		}

		//  如果找到新的最小值,则交换
		if (min != i)
		{
			temp = array[i];
			array[i] = array[min];
			array[min] = temp;
		}
	}
}

解释:

  • i 的初始值:0 ,表示 从第一项开始,找出后面的最小值与其交换
  • i 的临界值:len - 1 ,表示这种交换持续到倒数第二个数
  • j 的初始值:i + 1 ,表示每次都从 i 的下一项开始遍历,找到比 i 小的值中最小的值(由 min 确定该最小值)
  • j 的临界值:len ,表示每次都遍历到数组的最后一个数

—③ 快速排序

void sort3(int array[], int left, int right)
{
	if (right - left <= 1) return;	// 剩下的少于一个数的话就不用再排序了

	int i = left, j = right;  // 设置左下标和右下标的位置
	int pivot = array[i];	// 把第一个设置为基准

	while (i < j)
	{
		while (i < j && array[j] >= pivot) j--;  // 向左检索,直到找到比基准小的值
		array[i] = array[j];

		while (i < j && array[i] <= pivot) i++;  // 向右检索,直至找到比基准大的值
		array[j] = array[i];
	}

	array[i] = pivot;  // 将基准放到中间位置,此时 i==j ,使用哪个都可以

	// 递归再次排序,直到 len 为 1,注意除去中间的基准
	sort3(array, left, i - 1);  // 左边的继续排
	sort3(array, i + 1, right);  // 右边的继续排
}

解释:

  • 定义一个基准 pivot ,选为第一个元素
  • 然后定义两个下标分别从前往后和从后往前遍历
  • 后面的下标先动起来向前检索,(以升序为例)找到比基准小的值后,将该值赋给前下标所指的元素
  • 然后前下标向后检索,找到比基准大的值后,将该值赋给后下标所指的元素
  • 重复以上两步,直到两个下标相遇,将基准的值赋给该下标所指的元素
  • 现在得到的就是被基准分割的左右两堆数,左边的数都比基准小,右边的数都比基准大
  • 然后进行 递归 ,将左右两边的两堆数分别再进行快速排序,不断递归,直到数堆被分得只剩下一个,表示排序完毕
  • 得到的数组中,每一个数的左边都是比它小的,右边都是比它大的,这就实现了升序排序

—④ 二分查找法

// 算法4 :二分查找法
int binarySearch(int array[], int len, int data)
{
	int low = 0, high = len - 1;
	int mid = (low + high) / 2;

	while (low <= high)
	{
		if (data < array[mid]) high = mid - 1;
		else if (data > array[mid]) low = mid + 1;
		else return mid;

		mid = (low + high) / 2;
	}

	return -1;
}

解释:

  • 该查找方法生效的 前提是数组已排序完毕 ,升序降序都可以
  • 首先将 low 下标和 high 下标指向数组的两头,由此得到 mid 下标
  • 将要查找的数与 mid 对应的数比较,(以升序为例)比 mid 指向的数大则往右查找,小则往左查找
  • 直到 low 大于 high 则表示查找完毕

注意点:
每次缩小范围时,往右缩需要 mid+1,往左缩需要 mid-1,后面的 +1 或 -1 如果漏了将导致死循环。之所以这样做是因为 mid 已经查找过了在比较相等的时候,此时可以忽略它


◉ 链表

—① 插入结点(四种方法)

共有四种插入方法:头插法尾插法随机插法下标插法 (仅个人划分习惯)

新建一个结点

struct link* newNode(int data)
{
	struct link* node = (struct link*)malloc(sizeof(struct link));
	node->data = data;
	node->next = NULL;

	return node;
}

—— 1、头插法

void insertHead(struct link **head, int data)
{
	struct link* node = newNode(data);  // 新建一个结点

	if (*head == NULL) *head = node;  // 如果链表为空,则将新节点置为头结点
	else
	{
		node->next = *head;
		*head = node;  // 顺序不能倒
	}
}

头插法直接改变头结点,应该直接对原头结点操作

—— 2、尾插法

void insertEnd(struct link** head, int data)
{
	struct link* node = newNode(data);
	struct link* xhead = *head;  // 替换操作对象,不影响到头结点

	if (xhead == NULL) *head = node;  // 头结点为空,直接替换成新节点
	else
	{
		while (xhead->next != NULL) xhead = xhead->next;  // 遍历到尾结点
		xhead->next = node;
	}
}

—— 3、随机插法 (自动升序)

void insertSort(struct link** head, int data)
{
	struct link* node = newNode(data);  // 新建一个结点
	struct link* xhead = *head;  // 替换操作对象,不影响到头结点
	struct link* before = NULL;  // 定义前一个结点,用于中间插入

	if (xhead == NULL) *head = node;  // 头结点为空,直接替换成新节点
	else
	{
		while (xhead != NULL && data > xhead->data)  // 从头遍历,寻找到比插入结点数据大的结点
		{
			before = xhead;
			xhead = xhead->next;
		}

		if (before == NULL)  // 如果前结点为空,则说明该数据比第一个数据还小,需要进行头插法
		{
			node->next = *head;
			*head = node;
		}
		else  // 否则进行中间插法(即使是尾部插入也是行得通的~)
		{
			node->next = xhead;
			before->next = node;
		}
	}
}

—— 4、下标插法 (指定下标插入)

void insertIndex(struct link** head, int data, int index)
{
	struct link* node = newNode(data);  // 新建一个结点
	struct link* xhead = *head, *temp;  // 替换操作对象,不影响到头结点, 中间变量

	if (xhead == NULL) *head = node;  // 头结点为空,直接替换成新节点
	else
	{
		for (int i = 0; i < index - 1; i++)  // 遍历到下标结点的头一个( 注意 0 和 1 都会直接跳过)
		{
			if (xhead->next == NULL) break;
			xhead = xhead->next;
		}

		if (index == 0)  // 0 表示从头部插入,应更换头结点
		{
			node->next = *head;
			*head = node;
		}
		else
		{
			node->next = xhead->next;
			xhead->next = node;
		}
		
	}
}

注意点:

  • 插入结点时新建的结点 必须通过 malloc 开辟空间 ,不能直接使用局部变量,因为当该函数结束时局部变量就没了,结点将添加失败
  • 尾插法 / 随机插法 添加节点时要注意 原头结点的位置 ,如果直接遍历头结点的话会导致添加完毕后头结点指到最后面去了,应该将它还原到最前面。
  • 这里使用的是 临时操作指针 方法,不会影响到原头结点

—② 删除结点

// 删除结点
void deleteNode(struct link** head, int data)
{
	struct link* del = *head, * before = NULL;

	while (del != NULL)
	{
		if (del->data == data)
		{
			if (before == NULL) *head = (*head)->next;
			else
			{
				before->next = del->next;
				before = del;
			}
			
			// 这里的 break 直接影响到是删除全部的 data 结点还是只删第一个
			// break 去掉将是删除全部 data结点
			break;  
		}
		else before = del;

		del = del->next;
	}
}

要删除全部 data 结点的话则将 break 去掉,加上 break 表示删除第一个 data 结点


◉ 数学算法

—① 判断素数

// 判断素数,是则返回1,不是则返回2
int isPrime(int num)
{
	if (num <= 1) return 0;
	for (int i = 2; i <= sqrt(num); i++) if (num % i == 0) return 0;
	return 1;
}

—② 两数交换(三种方法)

—— 1、中间量法

void exchange1(int *num1, int *num2)
{
	int temp;
	temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
注意不能写成:
temp = num1;
num1 = num2;
num2 = temp;
这样就又变为了值传递,只改变了局部指针变量的值

—— 2、加减乘除法

// 加减法
void exchange2(int* num1, int* num2)
{
	*num1 = *num1 + *num2;
	*num2 = *num1 - *num2;
	*num1 = *num1 - *num2;
}

// 乘除法
void exchange3(int* num1, int* num2)
{
	*num1 = *num1 * *num2;
	*num2 = *num1 / *num2;
	*num1 = *num1 / *num2;
}

这两种方法的本质差不多所以归为一种
都是先将两个数合并为一个数,然后再分别拆分达到交换的效果

—— 3、异或法

void exchange4(int* num1, int* num2)
{
	*num1 = *num1 ^ *num2;
	*num2 = *num1 ^ *num2;
	*num1 = *num1 ^ *num2;
}

—② 最大公约数

—③ 最小公倍数

—④ 其他进制转十进制

—⑤ 十进制转其他进制

◉ 其他算法

—① 统计单词数


未完待续(寒冰小澈)

本文链接http://www.dzjqx.cn/news/show-617318.html