分类： Algorithm

算法效率的度量

我们已经接触了很多对于数组排序的算法，比如冒泡排序、选择排序、快速排序、插入排序、希尔排序、归并排序等，算法这么多，我们到底该在实际运用中选择哪一个呢？这就涉及到了取舍的问题，当然我们取舍的重点是算法的运行效率。那算法的运行效率到底如何评价呢？有的人说，你写一个测试程序运行一下（事后统计法），看看具体使用了多少时间不就知道了吗？当然这是一种办法，但是它还有很多的缺陷，下面我们就详细介绍一下算法统计的两种方法，一种称为“事后统计法”，另外一种称为“事前分析估算”。

数组归并排序

（声明：文章全部图片均来自 传智播客 教师课件）归并排序是一种空间换时间的做法，排序的速度当然会提高很多，归并排序中会产生一个临时数组，这个临时数组用来把不断拆分到最后的有序数据进行合并，最后再把合并后的数据重新赋值给原数组，这样就实现了排序。主要分为以下三个步骤：

数组插入排序

插入排序是一个相对复杂一点的排序算法，但是效率要比我们以前接触过的排序算法快一些，他的思想是将数组分为两组数据（第一次分的时候就是数组第一个元素为一组，后面的所有元素为一组），然后从后面一组数据中抽取第一个元素与前面一组数据依次做对比，按需求将大的或者小的值插入到前面的一组数据中，最终后面一组数据全部插入完毕后，前面一组数据就是有序状态了。

STL stack 实现后缀表达式运算

以前我们使用自己封装的栈模型探讨并实现了后缀表达式的运算，“计算机是如何基于后缀表达式计算的”，在 C++ 的 STL 中，也有一个栈模型 stack，并且使用了模版类，这样可以让我们更方便的操作数据了，下面的代码就是使用 STL 的 stack 模型实现的后缀表达式运算，我们只是把自己实现的栈模型函数替换成了 STL 的函数而已。

栈应用代码检测就近匹配

你在使用编辑器写代码的时候是否思考过这个问题：如果少写了一个大括号或中括号，编辑器就会提示错误，这种做法是怎么做到的呢？

其实这个检测就可以通过栈模型来实现，括号的数量总是匹配出现的，并且都是与最近的一个匹配。我们可以编写代码来实现这个检测的功能。具体实现思路如下：

从第一个字符开始扫描, 当遇见普通字符时忽略，
当遇见左符号时压入栈中
当遇见右符号时从栈中弹出栈顶符号，并进行匹配.
匹配成功：继续读入下一个字符
匹配失败：立即停止，并报错
结束.
------成功: 所有字符扫描完毕，且栈为空
------失败：匹配失败或所有字符扫描完毕但栈非空

【实现代码】

以下代码需要用到栈模型链式存储的 LinkStack.h 和 LinkStack.c 头文件：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"

/***************** 算法思路 *****************
从第一个字符开始扫描, 当遇见普通字符时忽略，
当遇见左符号时压入栈中
当遇见右符号时从栈中弹出栈顶符号，并进行匹配.
匹配成功：继续读入下一个字符
匹配失败：立即停止，并报错
结束.
------成功: 所有字符扫描完毕，且栈为空
------失败：匹配失败或所有字符扫描完毕但栈非空*/

int match(char left, char right)
{
	int ret = 0;
	switch (left)
	{
	case '<':	//左尖括号
		ret = (right == '>');
		break;
	case '(':	//左小括号
		ret = (right == ')');
		break;
	case '[':	//左中括号
		ret = (right == ']');
		break;
	case '{':	//左大括号
		ret = (right == '}');
		break;
	case '\'':	//左单引号
		ret = (right == '\'');
		break;
	case '\"':	//左双引号
		ret = (right == '\"');
		break;
	default:
		ret = 0;
		break;
	}

	//匹配成功返回1,不成功返回0
	return ret;
}

int isRight(char right)
{
	int ret = 0;
	switch (right)
	{
	case '>':	//右尖括号
	case ')':	//右小括号
	case ']':	//右中括号
	case '}':	//右大括号
	case '\'':	//右单引号
	case '\"':	//右双引号
		ret = 1;	//是需要检测的符号返回1
		break;
	default:
		ret = 0;	//不是需要检测的符号返回0
		break;
	}
	return ret;
}

int isLeft(char left)
{
	int ret = 0;
	switch (left)
	{
	case '<':	//左尖括号
	case '(':	//左小括号
	case '[':	//左中括号
	case '{':	//左大括号
	case '\'':	//左单引号
	case '\"':	//左双引号
		ret = 1;	//是需要检测的符号返回1
		break;
	default:
		ret = 0;	//不是需要检测的符号返回0
		break;
	}
	return ret;
}

int read(const char* code)
{
	int i = 0;
	LinkStack* stack = LinkStack_Create();

	while (code[i])
	{
		// 判断是否是左符号
		if (isLeft(code[i]))
		{
			// 是的话就压如栈中
			printf("push = %c\n", code[i]);
			LinkStack_Push(stack, (void*)&code[i]);
			//continue;
		}

		// 判断是否是右符号
		if (isRight(code[i]))
		{
			// 如果是则取出栈顶的符号与这个右符号对比
			char left = *(char*)LinkStack_Top(stack);
			if (match(left, code[i]))
			{
				// 匹配成功，从栈中弹出匹配过的左符号
				printf("pop  = %c\n", code[i]);
				LinkStack_Pop(stack);
			}
			else
			{
				// 匹配失败直接报错并终止循环
				printf("数据异常，匹配失败！ left = %c, right = %c\n", left, code[i]);
				break;
			}
		}
		i++;
	}

	// 最后判断栈中是否还有数据，如果还有证明缺少右符号
	if (!LinkStack_Size(stack))
	{
		printf("匹配成功！\n");
	}
	else
	{
		char ch = *(char*)LinkStack_Top(stack);
		printf("缺少匹配 %c\n", ch);
	}
	// 销毁
	LinkStack_Destroy(stack);
	return 0;
}



int main(int argc, char* argv[])
{
	const char* code = "#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0;}";
	read(code);

	return 0;
}

 

© 2023 - All rights reserved
Go to top