信息安全法律基础的老师留了一个问题，和朋友石头剪刀布输了，所以是我来回答这个问题。那么

人生的价值是什么？

以前也想过这个问题，但更多是讲给别人听的，告诉他们要积极要向上。但是很少认真的考虑这个问题，拿出一个让我自己的满意的答案。寻寻觅觅，想了一段时间，感觉大概有能拿出来说一说的想法了吧。所以记录在这里：

一串数字，它可以是你的手机密码，可以是你暗恋的女生的生日，可以是路口第一辆车的车牌号，也可以是仅仅只是一串数字。不同的场景，不同的人看到它都会有着各种各样的理解与认识。我想这串数字本没有意义，它的“价值”是被人为的赋予的。就像是棋盒里的黑白棋子，它本来并不包含什么信息，但是当它落在棋盘中的瞬间，却被赋予各种各样的信息与“价值”；亦或是程序中的二进制，对于人类而言，杂乱无章毫无意义，但是在机器的眼中却是他们工作的金科玉律。

我想，人也大概如此。人生，剥离与外界的关系，无非是几句话加上几个动作，从本质来看也是这么一串”数字”。它的本身并没有什么意义，但是将它与外界联系起来，人生就有了无穷的意义。所以我认为，人生的价值更多是被”人”赋予的，你的行为和话语，会产生各种各样的影响，对不同的人产生不同的价值。可能一次无意间的囧事，陌生的人会嘲笑你，熟悉你的人会安慰你，爱你的人会包容你。这是因为大家对你的认识与理解不同，你的囧事本质上是一堆信息，但是被赋予的“价值”不同。想到这里，也许会觉得很恐怖吧，自己的价值依附于他人的评价。当然不！你还有自己，你也是“人”，你也可以为自己的行为赋予各种各样的意义。我想这就是这个问题的关键，价值是被人赋予的，这其中既有别人，也有自己，人生不仅被他人定义，也由自己决定。

外界的声音总是嘈杂的，就算是圣人也有人批判。所以人生的价值应从自己出发，《孟子》中有这么一句话“穷则独善其身，达则兼济天下”，我觉得人生的价值就是这样，从自己开始，由己及外，去探索自己的价值。首先是要对自己好一点，满足自我的价值。然后再去实现对于他人的价值，而不是好高骛远的，渴望所有人的认可。英国伦敦有一座教堂，旁边的碑石有这么一句话：

“当我年轻的时候，我梦想改变这个世界；

当我成熟以后，我发现我不能改变这个世界，我将目光缩短一点，打算只改变我的国家；

当我进入暮年以后，我发现我不仅不能改变我的国家，我的最后愿望仅仅是改变一下我的家庭，但是这也是不可能的

我现在躺在床上，行将就木之时，我突然意识到：

如果一开始我仅仅去改变自己，然后可能会改变我的家庭；

然后在家人的支持和帮助下，我可能会为国家做一点事；

然后，谁知道呢？我甚至可以改变这个世界”

正如《礼记》中“修身，齐家，治国，平天下”的抱负，我们追求的人生价值大抵也该如此吧。

但是我真正想说的并不是这些，让一个十八岁的大学生去大谈人生价值就像是问四五岁的小朋友为什么想当科学家一样，没有什么参考价值。未来我还会经历各种各样的事情，而现在的我，知道的太多，经历的却太少。人生的价值？我也不太清楚。如果你问我人生的价值是什么，人生的意义是什么？我现在更想打会儿游戏，听听歌，和喜欢的女生聊聊天，吃点想吃的东西，学点想学的技术。

这是第二遍学KMP算法，第一遍学习的过程中，对他的原理理解的是云里雾里。现在回过头来，深度学习一下KMP算法

首先我们要清楚什么是KMP算法？

KMP

KMP算法的优点相较于暴力匹配算法(BF)更有效率。这是因为KMP算法会利用每次匹配得到的已有的信息，来进行回溯。从而开始一次新的匹配。而暴力算法由于重复的匹配，其复杂度为 O(m*n)；KMP算法的主串指针始终向前，所以复杂度为 O(m+n)

next数组

我看很多教程一开始都是先讲KMP算法的实现，只是提了一嘴next数组的大致内容，我觉得挺难懂的。所以这里先从next数组开始讲起：

要讲next数组，我们首先要从字符串的最大公共前后缀讲起，下面的图片很好的体现了这个概念。每次增大子串的长度，然后求得其对应的最大公共前后缀长度。

在求的子串的最大公共前后缀组后，我们便可以着手开始建立我们的next数组。

（1）首先我们需要明确next数组在这里的作用是什么？

当模式串的某个字符与主串的某个字符失配时，我们需要根据失配的位置 j,还有我们的 next数组，来确定下一次模式串开始匹配的位置。下一步用 next[j]处的字符继续与主串 i处的字符进行匹配。相当于将模式串向右移动了 j-next[j]的长度

（2）接下来的难点在于如何构建next数组

首先我们让 next[0] = -1作为一个标记，且我们容易得到 next[1] = 0，那么在此基础之上，我们需要结合现有的信息来递推下一个 next[j+1]的值。现在问题转换成了，如何利用已有信息，求下一个 next[j+1]的值？

对此我们需要分成两种情况进行判断：

• 当p_k = p_j时，next[j+1] = next[j] + 1 = k+1,代表该字符前有最大长度为k+1的最大公共前后缀

• 当p_k != p_j时，我们就需要寻找更短的最大公共前后缀，此时关键来了，怎么找寻更短的最大公共前缀？

​ 因为 P_k!=P_j，所以我们需要再次尝试 P_next[k]和 P_j的比较，如此一直递归下去。直到得到 P_next[next[...]]和 P_j相 等，从而令 next[j+1] = next[index[P_next[…]]] + 1 = k+1；或者始终不能成功配对，则令 next[j+1] = 0

现在我们可以写出next数组的递推算法：

1
2
3
4
5
6
7
8
9
10
11
12

void GetNext(char T[]){
    int j=0,k=-1;
    next[j] = k;
    while (T[j]!='\0'){
        if(k==-1||T[j]==T[k]){
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

这个程序还有一个递归版本：

1
2
3
4
5
6
7
8
9
10
11
12

int GetNext(int j,char T[]){
    if(j==0)return -1;
    if(j>0){
        int k = GetNext(j-1,T);
        while(k>=0){
            if(T[j-1]==T[k])return k+1;
            else k=GetNext(k,T);
        }
        return 0;
    }
    return 0;
}

KMP算法

我们在得到next数组之后，便可以根据next数组的特性和简单的判断，来实现我们的KMP算法，以下是我们的算法流程：

• 如果j = -1，则i++，j++，继续匹配下一个字符
• 如果S[i] = T[j]，则i++，j++，继续匹配下一个字符
• 如果j != -1，且S[i] != P[j]，则i不变，j = next[j]。这意味着失配，接下来模式串需要对主串相对右移j-next[j]的距离

现在我们可以写出完整的KMP算法：

1
2
3
4
5
6
7
8
9
10
11
12

int KMP(int start,char S[],char T[]){
    int i = start,j = 0;
    while(S[i]!='\0'&&T[j]!='\0'){
        if(j==-1||S[i]==T[j]){
            i++;		//下一个字符的比较
            j++;		//模式串右移
        }
        else j = next[j];
    }
    if(T[j]=='\0') return(i-j);		//匹配成功则返回下标（当前比较位-比较长度 = 起始下标）
    else return -1;
}

当然，在KMP的基础之上，还有很多优化之后的算法，在此就不过多赘述

Python版本

这个是python版本的KMP算法，基本上一样，只不过边界条件的判断改为使用长度判断。

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

class Solution(object):
    def strStr(self, haystack:str, needle:str)->int:
        next = self.getnext(needle)
        h,n = 0,0
        while h<len(haystack) and n<len(needle):
            if n==-1 or haystack[h] == needle[n]:
                h += 1
                n += 1
            else:
                n = next[n]
        if n == len(needle):
            return h-n
        else:
            return -1

    def getnext(self,T:str)->List[int]:
        j=0
        k=-1
        next = [0 for i in range(len(T))]
        next[j]=k
        while j <len(T)-1:
            if k==-1 or T[j]==T[k]:
                j+=1
                k+=1
                next[j] = k
            else:
                k = next[k]
        return next

继续算法的日常练习

字符串

最大公共前缀

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个函数来查找字符串数组的最大公共前缀；如果不存在，则返回 ""

1
2
3
4
5
6
7
8
9
10
11
12

def longestCommonPrefix(self, strs:List(str))->str:
        min_str = min(strs, key=len)
        result = ""
        p = 0
        while p < len(min_str):
            char = strs[0][p]
            for s in strs:
                if s[p] != char:
                    return result
            result += char
            p += 1
        return result

先纵向比对第一个字符，如果均为相同，则加入返回值中；若不正确，则直接返回

最长回文子串

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个字串s找到s中最长的子串,并返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def longestPalindrome(self, s:str)->str:
        ans = ""
        for i in range(len(s)):
            temp = self.search(s,i,i)
            if len(temp) > len(ans):
                ans = temp
            temp = self.search(s,i,i+1)
            if len(temp) > len(ans):
                ans = temp
        return ans

    def search(self,s,first,end):
        while first>=0 and end<len(s) and s[first] == s[end]:
            first -= 1
            end += 1
        return s[first+1:end]

首先构造一个中心回文的函数 search,先为两边设置边界条件，然后当中心索引两边的值相等时，则向外拓展。我们构造这个辅助函数之后，在主函数中调用。（需要考虑奇偶回文的情况）

翻转字符串里的单词

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个字符串s，反转字符串中单词的顺序

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

1
2

def reverseWords(self, s:str)->str:
    return (" ").join(s.split()[::-1])

啊，因为python丰富的内置函数，直接做完了。可以稍微讲下这几个函数的用法：

• ("拼接符号").join(待拼接数组)
• (待分隔数组).split(分隔符号)

双指针

指针常用的两种用法：

• 首尾指针
• 快慢指针

反转字符串

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题

1
2
3
4
5
6
7

def reverseString(self, s):
    i,j = 0,len(s)-1
    while i<j:
        s[i],s[j] = s[j],s[i]
        i += 1
        j -= 1
    return s

这里实际上是用了双指针的思想，相对移动然后互换位置。python中虽然没有指针，但是我们仍然可以通过数组去模拟这个过程，不过设置边界条件时一定要注意

数组拆分

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该 最大总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def arrayPairSum(self, nums:List[int])->int:
        ans = 0
        nums = self.quick_sort(nums)
        print(nums)
        for i in range(len(nums)//2):
            ans += nums[i*2]
        return ans

    def quick_sort(self,array):
        if len(array) <= 1:
            return array
        else:
            reference = array[0]
            small = [s for s in array[1:] if s < reference]
            equal = [e for e in array if e == reference]
            large = [l for l in array[1:] if l > reference]
        return self.quick_sort(small) + equal + self.quick_sort(large)

这道题主要在于分析怎么得到最大总和，观察可以发现先对数组进行排序，再将已排序数组的偶数位累加即可。排序的话要尽量使用，较快的排序，不然会超时（冒泡就超了），所以这里使用快速排序

两数之和

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

1
2
3
4
5
6
7
8
9
10

def twoSum(self, numbers:List[int], target:int)->List[int]:
	i,j = 0,len(numbers)-1
	while True:
		a = numbers[i]+numbers[j]
		if a>target:
			j -= 1
		elif a<target:
			i += 1
		else:
			return [i+1,j+1]

对于这类题可以用一种匹配方式，有效的减少重复的索引：

• 双指针指向首尾，求和与target进行比较
• 当值较小时，我们将首指针前移
• 当值较大时，我们将尾指针后移

移除元素

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
• nums 的其余元素和 nums 的大小并不重要。
• 返回 k

1
2
3
4
5
6
7

def removeElement(self, nums:List[int], val:int)->int:
       slow = 0
       for fast in range(len(nums)):
           if nums[fast] != val:
               nums[slow] = nums[fast]
               slow += 1
       return slow

快慢指针，一个负责定位，一个负责向前索引匹配。这个思想十分常见

最大连续的1的个数

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数

1
2
3
4
5
6
7
8
9
10

def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
    a,b = 0,0  # 分别存储当前最大连续数与历史最大连续数
    for i in range(len(nums)):
        if nums[i] == 0:
            if a > b:
                b = a
            a = 0
        else:
            a += 1
    return max(a,b)

这里，我用了一个比较清晰的答案，同时这里也体现了快慢指针的思想，很优雅

长度最小的子数组

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12

def minSubArrayLen(self, target:int, nums:List[int])->int:
    left,right = 0,0
    count = len(nums)+1
    sum = 0
    while right < len(nums):
        sum += nums[right]
        while sum >= target:
            count = min(count,right-left+1)
            sum -= nums[left]
            left += 1
        right += 1
    return 0 if count==len(nums)+1 else count

这里使用了尺缩法，其大致流程如下：

• 右边界右移，直到和大于target，令左边界右移
• 若和仍然大于target，左边界继续右移
• 若和小于target，右边界右移

这种和上面的相对收缩有着异曲同工之妙，但是这里是追及收缩，要注意边界条件

互联今日

我本来有好多好多话想说啊

写着写着什么也写不下去了

很怀念以前在网上认识的朋友们

再看看如今的网络环境 唏嘘不已

用Python感受十大排序算法，首先我们对这十个排序进行分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

十大排序算法：
	非线性时间比较类：
		交换类：
			冒泡排序
			快速排序
		插入类：
			直接插入排序
			希尔排序
		选择类：
			简单选择排序
			堆排序
		归并类#：
			归并排序
	线性时间排序：
		计数排序
		桶排序
		基数排序

非线性排序

冒泡排序

最经典的排序算法

算法思想

将数据中的每个数与相邻的数进行比较并交换，大数往上冒，小数向下沉。将每个数遍历排序一遍

算法步骤

• 取第一个数，依次与下一个数进行排序，然后与小于(或大于)自己的数交换位置直到最后一个数
• 如果未发生位置交换，说明数据有序，排序结束。如果发生了位置交换重复上一步

算法分析

时间复杂度：

• 当排序为正序时，只需要排序一次，比较n-1次，时间复杂度为O(n),这是最优情况
• 当排序为逆序时，需要进行n-1次遍历，每次比较n-i次，时间复杂度为O(n^2)，这是最差情况

算法代码

1
2
3
4
5
6
7
8
9
10
11

# 冒泡排序
def bubble_sort(nums):
    # 冒泡排序进行的次数n-1,每次遍历确定一个最大值
    for i in range(len(nums)-1):
        # j为进行比较的数据下标
        for j in range(len(nums)-1-i):
            # 若下标为j的数据大于其右相邻数据
            if nums[j] > nums[j+1]:
                # 二者交换数据
                nums[j],nums[j+1] = nums[j+1],nums[j]
    return nums

快速排序

也称为分区交换排序，它采用了分治思想，是冒泡排序的改良版。冒泡排序只能比较和交换两个数据，但是快速排序可以交换和比较两个分区，其效率更高

算法思想

选取一个基准值，将待排序数据分为左（小于基准值）和右（大于基准值）两个区间，然后对两个分区的数据进行相同的操作，最终得到一组有序数据

算法步骤

• 选取待排序数据的第一个数值作为分区标准
• 遍历数组，将小于标准的放在左边，大于标准的放在右边，则中间为标准数
• 对标准数左右两个子序列分别进行（1）和（2）的操作
• 当左右序列的长度均小于等于1时，排序完成

算法分析

时间复杂度

• 如果选取的标准数位待排序数组的中位数，即每次划分后的左右子序列长度基本一致，时间复杂度为 O(n*log_2(n)),为最好情况
• 如果待排序数组是逆序，且第一趟选取的标准数位待排序数组的最大值，经过n-1次比较后，得到一个n-1个元素的左子序列；然后第二趟选取的标准数仍然是最大值,…依次类推，最终的时间复杂度为 O(n^2)，这是最坏的情况

算法代码

学习版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 快速排序
def quick_sort(array):
    if len(array)<=1:			# 当子序列长度<=1
        return array			# 排序完成,停止递归
    else:
        small = []				# 由所有小于基准值的元素组成的子数组
        equal = []				# 包括基准值在内并且和基准相等的元素
        large = []				# 由所有大于基准值的元素组成的子数组
        reference = array[0]	 # 选择第一个数作为基准值
        # 遍历array中的每一个元素
        for s in array:
            # 当前元素小于基准值时
            if s < reference:
                # 当前元素插入small
                small.append(s)
            # 当前元素等于基准值
            elif s == reference:
                equal.append(s)
            # 当前元素大于基准值
        	else:
                large.append(s)
            print(small,equal,large)
    # 调用自身，即为递归
    return quick_sort(small) + equal + quick_sort(large)

实用版：

1
2
3
4
5
6
7
8
9

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        reference = array[0]
        small = [s for s in array[1:] if s < reference]
        equal = [e for e in array if e == reference]
        large = [l for l in array[1:] if l > reference]
    return quick_sort(small) + equal + quick_sort(large)

直接插入排序

直接插入法是直接排序的典型方法，毫无技术可言

算法思想

将排序数组中的数据逐一插入已排序的子序列中，从而得到一个完整的有序数组

算法步骤

• 将数组的第一个数据看成一个有序的的子序列
• 从第二个数据开始，依次与前面的有序子序列进行比较，若待插入数据array[i]大于或等于array[i-1]，则原位插入；若待插入数据array[i]小于数据array[i-1]，则将array[i]临时存在临时变量temp中，将有序序列中大于temp的所有数据都后移一位，然后将temp插入对应的位置
• 重复步骤(2)

算法分析

时间复杂度：

• 当数组为正序排列时，比较次数为n-1，移位次数为0，均为最小值，因此时间复杂度为 O(n)
• 当数组为逆序排列时，每次比较都需要做一次位移，此时时间复杂度为 O(n^2)，是最差情况

空间复杂度：

​ O(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

# 直接插入排序
def inset_sort(array):
    n = len(array)
    # 切记是从1到n-1，前闭后开
    for i in range(1,n):
    	# 如果待插入数据小于前一个数据
        if array[i] < array[i-1]:
            # index为待插入的下标
            index = i
            # 将待插入的数据放在temp中
            temp = array[i]
            # 从i-1循环到0,反向取值，间距为1
            # 前两个参数为区间范围，第三个参数为取值方向和大小
            for j in range(i-1,-1,-1):
                # 如果array[j]大于temp
                if array[j] > temp:
                    # 将array[j]后移一位
                    array[j+1] = array[j]
                    # 更新待插入的下标
                    index = j
                # 如果array[j]小于或等于temp
            	else:
                    # 跳出并结束
                    break
            # 将temp插入有序子数列
            array[index] = temp
       # 如果待插入数据大于前一个数据，则不需要移动
    return array

希尔排序

即shell排序，也叫缩小增量排序，通过将原始列表分解为多个子列表来改进插入排序

算法排序

shell排序摒弃了直接插入排序逐一比较的区别，而是对指定距离(增量d)的元素进行比较，并不断把增量减小到1,直到排序完成

算法步骤

• 选取增量d = n/2
• 将排序数组分成d个子序列，然后分别进行直接插入排序
• 将增量取半，即 d = d/2 = n/2/2
• 重复步骤(2)和(3)
• 对整个待排序数组进行直接插入排序

算法分析

似乎希尔排序并不比直接插入排序快多少，但是我们可以注意到它的特点：

• 当d较大时，分组多，每组记录少，因此直接插入排序快
• 当d教小时，分组少，每组记录多，但是此时各组记录已经为正序，因此排序比正常的直接插入要快

实际上希尔排序相较于直接排序，主要是优化了待排序数组的初始顺序，使其达到或接近于直接插入排序的最优情况

时间复杂度：

• 最好的情况下为O(n^1.3)
• 最差的情况仍然为O(n^2)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 希尔排序
def shell_sort(array):
    # 设定初始增量d=n/2
    d = len(array)//2
    # 当增量大于0时执行,如果小于0,则退出循环
    while d>0:
        # i 的取值范围为d到n
        for i in range(d,len(array)):
            # 类似直接插入排序，比较当前值与指定增量的值
            while i>=d and array[i-d]>array[i]:
                # 符号条件则交换
                array[i],array[i-d] = array[i-d],array[i]
                # 取前一个指定增量的值，继续下一个判断
                i -= d
        # 将增量取半,回到while循环
        d = d//2
    return array

简单选择排序

选择排序的思想和简单，每次从待排序数据中选择最小的一个放在最前面，直到将所有数据都遍历完

算法思想

遍历待排序数组并选出其中的最小数据元素，并于第一个元素交换位置，第二小的元素和第二个元素交换位置，直到剩下最后一个数据为最大数据，排序结束

算法步骤

• 将第一个位置上的元素依次与后面的元素进行比较，若前者大，则交换二者位置
• 重复步骤（1），比较第二个位置上的元素，然后比较第三个位置上的元素…直到比到倒数第二个元素

算法分析

这个算法被视作在排序算法中最差劲的算法

时间复杂度：

无论时最好的情况还是最差的情况，都需要与所有数据进行遍历，因此时间复杂度始终为 O(n^2)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13

# 简单选择排序
def select_sort(array):
    # 从0遍历到待排序数组的长度len(array)-1
    for i in range(len(array)-1):
        # smallest为最小值的index，初始默认为当前的i
        smallest = i
        # j为比较index,从当前的index的下一位到数组结束
        for j in range(i+1,len(array)):
            # 如果当前最小值大于当前值
            if array[smallest]>array[j]:
                # 则二者交换位置
                array[smallest],array[j] = array[j],array[smallest]
    return array

堆排序（这个和数据结构相关，我不是太理解）

简单排序只顾着，一次又一次的重新比对，却不对每一次的比较结果进行分析保存，所以导致效率低下，而堆排序加以改进

算法思想

首先需要直到什么是堆，堆是用数组实现的已标号的完全二叉树。接着需要引入小顶堆和大顶堆的思想：

• 如果父节点的键值均不小于子节点，则为大顶堆：arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]
• 如果父节点的键值均不大于子节点，则为小顶堆：arr[i]<=arr[2*i+1] && arr[i]<=arr[2*i+2]

也就是说，堆排序实际上就是一次又一次的将待排序数组构造成一个大顶堆，又一次次的将大顶堆的根节点(最大值)和最末尾的元素互换位置，并末尾的元素隔离，直到整个序列变得有序

算法步骤

• 将待排序数组构建成一个大顶堆（如果降序排列，则使用小顶堆）。为了构建大顶堆，我们需要从从最后一个非叶子节点开始先从上到下，再从左往右进行调整。最后一个非叶子节点的计算公式为 arr.length//2-1
• 将堆顶元素与末尾元素交换，使最大元素沉至数组末尾
• 重复步骤（1）和（2），直到整个序列都变得很有序。重新调整数组结构，使其满足大顶堆的结构

算法分析

时间复杂度：

• 最好的情况是正序，只需要进行 O(n*log_2(n)复杂度的比较操作，而不需要移动
• 最坏的情况时间复杂度还是O(n*log_2(n)
• 从上面可以看出待排序数据的原始分布情况堆堆排序的效率影响较少

算法代码

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

# 堆排序
def heap_sort(array):
    """
    需要注意两点：
    （1）递归思想
    （2）切片思想
    """
    length = len(array)
    # 当数组array的长度为1时，说明只有一个元素
    if length <= 1:
        return array
    # 若存在两个及以上的节点
	else:
        # 调整为大顶堆，按照从下往上从左往右的顺序进行调整
        # 从最后一个非叶子节点开始想前遍历，直到根节点
        for i in range(len(array)//2-1,-1,-1):
            # 当左孩子大于父节点
            if array[2*i+1]>array[i]:
                # 交换位置
                array[2*i+1],array[i] = array[i],array[2*i+1]
            # 如果右孩子存在且大于父节点
            if 2*i+2 <= length-1:
                if array[2*i+2]>array[i]:
                    # 交换位置
                    array[2*i+2],array[i] = array[i],array[2*i+2]
        '''此处省略剩余数组重构过程,对结果无影响'''
        # 将堆顶元素与末尾元素进行交换
        array[0],array[length-1] = array[length-1],array[0]
        # 递归调用heap_sort函数堆前n-1个元素进行堆排序并返回堆排序后的结果
        return heap_sort(array[0:length-1]) + array[length-1:]

归并排序

归并排序是包含归并思想的排序方法，它是分治法的一个应用。分治法即“分而治之”

算法思想

先将原数组分为子序列，一生二，二生四，四生无穷，然后使每个子序列有序，再将两个有序子序列合并为一个有序序列，最终合一

算法步骤

• 将排序数组一分为二，再将两个子序列一分为二，生成两个新的待排序数组
• 重复步骤（1），直到待排序数组的长度为1
• 按原路径将长度为1的两个数合并为一个有序序列，然后一直向前合并，最终得到一个完整的有序序列

算法分析

归并排序十分高效，它的分与合的结构都是完成二叉树，而分和合的二叉树深度均为log_2(n)，而每次分合的时间复杂度为 O(n)，故

时间复杂度：

始终为 O(n*log_2(n))，不论情况好坏

算法代码

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

# 归并排序
def merge(left,right):
    """
    两个有序子序列的有序合并：
    依次对两个有序列表的最小数进行比较，较小的放入result中
    :param left: 左子序列
    :param right: 右子序列
    :return: 左右子序列所合成的有序序列
    """
    # result: 存好已经排序的数组
    result = []
    # 如果不符合左右子序列长度均大于0,则说明至少其中的一个数组已经无数据了
    while len(left)>0 and len(right)>0:
        # 相等的时候优先把左侧的数放进结果列表，以保证其稳定性
        if left[0] <= right[0]:
            # list.pop(0)为移除并返回数组的第一个值
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 跳出while循环后,我们便可以把另一个数组尽数加入result后面
    result += left
    result += right
    return result

def merge_sort(array):
	"""
	无序序列的不断拆分
	每次均由中间位置进行拆分,不断自我递归调用，直到子序列长度为1
	"""
    # 如果拆分后仅有单个元素，则返回该元素而不拆分
    if len(array) == 1:
        return array
    # 如果有两个以上元素，则从中间位置开始拆分
    middle = len(array)//2
    # 拆分后的左侧子串
    array_left = array[:middle]
    # 拆分后的右侧子串
    array_right = array[middle:]
    # 对拆分后的左右子串序列再进行拆分，直到len(arr)=1
    left = merge_sort(array_left)
    right = merge_soort(array_right)
    # 合并已拆分的左右子序列的同时进行排列并返回排列后的结果
    return merge(left,right)

线性时间非比较类排序

计数排序

一种非基于比较的排序算法，通过辅助数组来确定各元素的为最终位置。因为在排序过程中不存在元素之间的比较和交换操作，当待排序数组为整数且数组内数据范围较小时，其优势十分明显

算法思想

对待排序数组中的每一个元素分别进行计数，确定整个数组中小于当前元素的个数，计数完成后便可以按照各计数值将各元素直接存放在已排序的数组中

算法步骤

• 根据待排序序列中的最大元素和最小元素确定计数数组c的空间大小
• 统计待排序序列中的每个元素i出现的次数并存入c[i-1]
• 对c中的所有值进行累加，后者为其前面所有的值的总和
• 将每个元素放入已排序序列的第c[i]项，每放入一个元素，c[i]便减1
• 所有的元素都放入或者c[i]均为0之后,排序结束

算法分析

我们可以观察到计数排序的弊端,当最大值与最小值间的差值过大,会使开销增大,性能变差.其次当出现浮点数或其他形式时,也会有问题

时间复杂度:

第一个循环用于记录每个元素出现的次数,复杂度为 O(n)第二个循环用于对计数数组进行累加,复杂度为 O(k),k为申请空间的大小(即差值范围),第三个循环用于反向填充已排序的数列,复杂度为O(n).总结可得,时间复杂度为 O(n+k)

空间复杂度:

由于我们额外申请了一个大小为k的计数数组和一个与待排序数组同样大小的排序空间,所以空间复杂度为 O(n+k)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 计数排序
def count_sort(arr):
    # 计算序列的最大值和最小值
    maximum,minimum = max(arr),min(arr)
    # 申请额外的空间作为计数数组,大小为最大值减最小值+1
    countArr = [0 for i in range(maximum-minimum+1)]
    # 申请一个存放已排序序列的等长空间
    finalArr = [0 for i in range(len(arr))]
    # 统计各元素出现的次数,并将统计结果存入计数数组
    for i in arr:
        # 出现一次就加1
        countArr[i-minimum] += 1 	# 注意下标index = data - min
    # 对计数数组进行累加
    for i in range(1,len(countArr)):
        # 从第二个位置开始,每个每个位置的值等于其本身加上前者
        countArr[i] += countArr[i-1]
    # 开始将元素反向填充到最终的数组中
    for i in arr:
        finalArr[countArr[i-minimum]-1] = i
        # 填充了一个就减一
        countArr[i-minimum] -= 1
    return finalArr

桶排序

这是计数排序的改进版本

算法思想

根据元素的特性将集合拆分成为多个值域,我们称之为桶,将同一值域的元素存放在同一个桶内排序使其处于有序状态.如果每个桶是有序的,则由这些桶按顺序构成的集合也必定是有序的

算法步骤

• 根据待排序序列中元素的分布特征和差值范围，确定映射函数与申请桶的个数
• 遍历序列，将每个记录放到对应的桶中
• 选取排序算法，对不为空的桶内部进行排序
• 把已排序的桶中的元素放回已经清空的原序列中

算法分析

我们可以注意到，桶排序和快速排序与计数排序的相似性。为了加深理解，我们在此进行区分：

• 快速排序是对两个分区的排序，而桶排序是多个分区
• 快速排序是原地排序方式，即在数组本身内进行排序，而桶排序则是在申请的额外操作空间进行排序
• 快速排序中的每个区间仍然是快速排序，而桶排序可以自主选择桶内的排序方式
• 计数排序的申请空间的跨度是从最小元素到最大元素，受待排序序列的范围的影响很大，而桶排序弱化了这种影响，减少了元素大小不连续时计数排序所存在的空间浪费

这里对于桶排序要抓住两个关键点：元素值域的划分和排序算法的选择

时间复杂度：

映射过程的排序复杂度为 O(n)桶内排序算法的时间复杂度则和选择的排序复杂度相关

空间复杂度：

由于桶排序需要申请额外的空间进行分桶操作，所以空间复杂度为 O(m+n)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 桶排序
def bucket_sort(arr):
    maximum,minimum = max(arr),min(arr)
    # 确定桶的个数
    buckets = [[] for i in range(maximum-minimum)//10+1]
    for i in arr:
        # 计算各元素的所属的桶位
        index = (i - minimum)//10
        # list.append()---添加元素
        buckets[index].append(i)
    # 将原数组清空
    arr.clear()
    for i in buckets:
        # 桶内排序---堆排序(可以用别的替代)
        i = heap_sort(i)
        # 将已排序的桶重新放回已经清空的原数组中
        arr.extend(i)
    return arr

基数排序

基数排序是桶排序的扩展，因此又称之为”桶子法”,它是通过键值的部分信息，将要排序的元素分配至”桶”中,以达到排序作用

算法思想

将各元素按位数切割成不同的数字，然后分别根据每个位数的比较结果进行排序

算法步骤

• 确定待排序序列的最大位数
• 将所有待排序元素统一为最大数位长度(左补0)
• 从最低位到最高位分别进行排序
• 当最高位排序完成后，原数组变成有序数列

算法分析

时间复杂度：

每一轮排序的时间复杂度为 O(n)，而轮数由最大值的位数d决定，因此时间复杂度为 O(d*n)

空间复杂度：

需要额外申请空间k，因此空间复杂度为 O(n+k)

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 基数排序
def radix_sort(arr):
    maximum = max(arr)	 # 确定待排序数组中的最大位数
    d = 0				# 用d记录最大位数 
    while maximum!=0:
        maximum = maximum//10
        d += 1
    # d轮排序
    for i in range(d):					
        # 因为每一位数字都是0~9，所以建十个桶
        s = [[] for k in range(10)]		 
        for j in arr:
            # 从个位数开始注意进行分桶操作
            s[int(j/(10**i))%10].append(j)
        # 用10个桶回填原数组
        arr = [a for b in s for a in b]
    return arr

四月份还是三月份有蓝桥杯的算法比赛，加上一直对算法感兴趣。所以从现在开始稍微学一下。

每天会坚持做几题吧，因为不知道哪些比较重要，我就主要记一些我认为重要的内容和算法

数组

数组中心索引

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

当数组中一个索引右边的和等于左边和时，称这个索引为数组的中心索引

1
2
3
4
5
6
7
8
9

def midIndex(nums:List[int])->int:
    all = sum(nums)
    left = 0
    for i in range(len(nums)):
        if left*2+nums[i]==all:
            return i
        else:
            left += nums[i]
    return -1

大概的思路就是根据它的数值对称的思路来实现中心索引的寻找

二分法查找

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

这是一个经典的查找算法，相较于线性查找，它的时间复杂度更简单O(log_n)

1
2
3
4
5
6
7
8
9
10
11

def binary_search(nums:List[int],target:int)->int:
    left,right = 0,len(nums)-1
    while left<=right:
        mid = left + (right-left)//2	# 避免整数溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return -1

首先设置左右边界，然后判断目标在左区间还是右区间。如果在左区间，则更改右边界条件；在右区间，则更改左边界条件。直到找到目标数值，返回索引

区间合并

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给一个若干区间组成的数组，其区间含义为[start,end]，我们将其进行合并

1
2
3
4
5
6
7
8
9

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key= lambda x:x[0])
        rList = list()
        for interval in intervals:
            if not rList or rList[-1][-1]<interval[0]:
                rList.append(interval)
            else:
                rList[-1][-1] = max(rList[-1][-1],interval[1])
        return rList

首先根据区间的起始位置进行排序，然后创建一个新的列表，设置以下规则：

• 当列表为空时，加入数组
• 当列表中数组的最后一位小于当前数组的第一位，说明不重叠，加入数组
• 当发生重叠时，比较两数组的最后一位，保留大的数字

二维数组

旋转矩阵

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个NXN矩阵表示的图像，其中每个像素大小为4字节，设计一种算法，将图像顺时针旋转90°

方法一：

使用一个额外的数组来辅助完成

1
2
3
4
5
6
7
8

def rotate(self,matrix: List[List[int]])->List[List[int]]:
    rlists = list()
    for j in range(len(matrix[0])):
        rlist = list()
        for i in range(len(matrix)-1,-1,-1):
            rlist.append(matrix[i][j])
            rlists.append(rlist)
    return rlists

这个实际上是通过更改读取顺序的方式，重新创建一个矩阵，但是不符合题目不额外使用空间的思想

方法二：

通过矩阵的几何特性来实现

1
2
3
4
5
6
7
8
9

def rotate(self,matrix: List[List[int]]):
    N = len(matrix)
    # 对角线互换
    for i in range(N):
        for j in range(i):	# 这里要仔细理解，因为接下来要进行互换，所以j要随i增大
            matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
    # 水平互换
    for i in range(N):
        matrix[i][:] = matrix[i][::-1]

这里我们可以总结：

• 顺时针旋转90°，先对角翻转，再水平翻转
• 逆时针旋转90°，先水平翻转，再对角线翻转

零矩阵

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

数字0所在的行与列，在矩阵中全部置0

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def setZeroes(self, matrix:List[List[int]]):
    M=len(matrix)
    N=len(matrix[0])
    line=[0]*M
    row=[0]*N
    for i in range(M):
        for j in range(N):
            if matrix[i][j]==0:
                line[i] = 1
                row[j] = 1
    for i in range(M):
        for j in range(N):
            if line[i]==1 or row[j]==1:
                matrix[i][j]=0

这个方法很直观，分别创建行和列的索引，并进行标记，当匹配到标记时，将数据置0

对角线遍历

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个大小mxn的矩阵mat，以对角线遍历的顺序，用一个数组返回

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

class Solution(object):
    def findDiagonalOrder(self, mat:List[List[int]])->List[int]:
        ans = []
        Xsize = len(mat)
        Ysize = len(mat[0])
        tot = Xsize + Ysize - 1
        x,y = 0,0
        for i in range(tot):
            if i%2==1:
                while y>=0 and x<Xsize:
                    ans.append (mat[x][y])
                    x += 1
                    y -= 1
                if x<Xsize:
                    y += 1
                else:
                    y += 2
                    x -= 1
            else:
                while x>=0 and y<Ysize:
                    ans.append (mat[x][y])
                    x -= 1
                    y += 1
                if y<Ysize:
                    x += 1
                else:
                    x += 2
                    y -= 1
        return ans

这道题目难在边界条件的处理，需要仔细分析（分类讨论）

注意：在观察二维数组时，一定要把索引与行列之间的关系理清除

这里附上一个很好的解答498. 对角线遍历 - 力扣（LeetCode）

久仰CE修改器大名，今天来学习一下CE的基础使用（官方教程）

我看网上有很多图文教程，在此就尽量不配图。主要记录学习过程中的感受心得为主

1. 打开进程

​ 这一步没啥难度，不做说明

2. 已知数值查找

​ 先在此附上官方说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

步骤 2: 精确值扫描 (密码=090453)

现在你已经在 Cheat Engine 中打开了训练程序，为我们下一步的练习做好了准备。
本窗口的左下方显示的"健康:XXX"，
在你每次点击"打我"按钮时，它的值便会减少。
要进入下一关，你必须找到这个数值并把它改成 1000 。
很多方法都可以找到这个数值的位置，但我将告诉你一个最简单的方法，"精确数值"扫描：
首先确认数值类型设置为2字节或4字节，设置成1字节也可以的，不过最终修改数据的时候便会有点麻烦了（虽然说这是很容易解决的问题）。假如该地址后边的字节数值都为 0 ，
那么你设置成 8 字节也未尝不可，
在这我们就不必尝试了。单浮点数，双浮点数，以及其他的扫描方法在这里行不通的，因为它们储存数值的方式不同。
当数值类型设置正确后，确认扫描类型设置了"精确数值"，把健康值填写在数值的输入框，并点击"首次扫描"，稍等一会儿（假设你的电脑非常的慢），扫描完毕，扫描的结果将会显示在主界面的左侧。
如果检索结果多于一个，你无法确定哪一个是正确的地址，那么继续点击"打我"，并将变更后的"健康值"填写在数值输入框中，点击"再次扫描"，重复这些步骤，直到你能确认已经找到了地址（在地址列表中只有一个地址）。
好，双击左侧列表中的地址，该地址便会移动到下方的地址列表中并显示它的当前数值。r
双击下方地址列表中的数值（或者选择它，按下回车），填写你要修改的数值：1000 。
如果操作正确，"下一步"按钮将变成可点击状态，本关就完成了。

提示：
如果你在扫描过程中出现了错误，可以点击"新的扫描"重新再来。当然，你也可以点击"打我"去查找一些更有价值的线索。

• 扫描类型设置为“精确数值”，并设置初始数值为100，使用首次扫描
• “打我”之后血量减少，再次扫描新的数值，找到设置血量的指针
• 双击装载下来后，更改其数值为1000

总结：有时候会遇到无法直接检索到地址的情况（有多个地址），此时反复几次即可，如果始终没有成功检索到，思考一下扫描的数值类型是否正确。或者多尝试几次？

3. 未知数值查找

​ 先附上官方说明

1
2
3
4
5
6
7
8
9
10
11
12

步骤 3: 未知的初始值 (密码=419482)

OK, 看来你已经理解了如何利用"精确数值"扫描查找数值了，让我们进行下一步。
在上一关中我们知道初始数值的大小，所以我们可以利用"精确数值"扫描，但本关中仅有一个状态栏，我们并不知道它的初始数值。
我们只知道这个数值在0到500之间，并且每次点击"打我"之后便会减些健康值，每次减少的健康值会显示在进度条的上方。
同样有好几种方法可以找这个数值，（例如使用"数值减少了..."扫描方式），但我只教你最简单的方法，"未知的初始值"和"减少的数值"。 
由于不知道当前数值的大小，"精确数值"扫描便派不上了用场，所以选择扫描方式"未知初始数值"。数值类型仍然选择 4 字节（这是因为大多数WINDOWS应用程序都使用 4 字节存放数据）。点击"首次扫描"并等待扫描结束。
扫描完成后，点击"打我"，你会减少一些健康值。（减少的健康值显示几秒便会消失，你并不需要刻意记下它）。
回到 Cheat Engine，在扫描类型中选择"减少的数值"，然后点击"再次扫描"。
扫描完毕后，再次点击"打我"，并重复上述步骤，直到检索出很少的几个地址。 
我们已经知道这个数值在0到500之间，所以挑出那个最为相似的地址，并将它加到下方的地址列表。
现在，更改健康值为 5000，以便我们进入到下一关。

由于是未知的初始值，我们无法像常规的做法一样。所以搜索的步骤如下：

• 扫描类型设置为”未知的初始值”，然后进行首次扫描，这个时候是检索不到内容的
• 此时选择”减少的数值”，然后再次扫描，此时会出现很多未知的地址，多重复几次，可以看到几个有可能的数值
• 我们将其选中并修改参数为5000即可’

总结：知道变化值的使用”减少了…“或者”增加了…“，不知道变化值的使用”减少的数值”或者”增加的数值”

4. 浮点数

​ 先附上官方说明

1
2
3
4
5
6
7
8
9
10
11

步骤 4: 浮点数 (密码=890124)

在前面的教程中我们使用字节的方式进行扫描，但有些游戏使用了"浮点数"来存储数值（这么做是为了给菜鸟制造一些麻烦，让他们没那么容易修改游戏）。
浮点数是带有小数点的数值（如 5.12 或 11321.1）。
正如本关中的健康和弹药，两者都以浮点方法储存数据，不同的是，健康值为单精度浮点数，而弹药值为双精度浮点数。
点击"打我"将减少一些健康值，而点击"开火"则消耗掉 0.5 的弹药。
你得把这两项都修改到 5000 或者更多才能过关。
"精确数值"扫描的方式虽然也可以完成本关的工作，但你应该试试其它更简练的扫描方式。


提示: 扫描双浮点数类型建议禁用 "快速扫描" 

首先要确定一个数据是单精度浮点数还是双精度浮点数，不过这里给了数据所以正常搜索即可

总结：没什么好总结的哦

5. 代码查找

·先附上官方说明

1
2
3
4
5
6
7
8
9
10
11
12
13

步骤 5: 代码查找 (密码=888899)

某些游戏重新开始时，数据会存储在与上次不同的地方, 甚至游戏的过程中数据的存储位置也会变动。在这种情况下，你还是可以简单几步搞定它。
这次我将尽量阐述如何运用"代码查找"功能。
下方的数值每次启动教程的时候都会存放在内存不同的位置，所以地址列表中的固定地址是不起作用的。
我们要先找到这个数值当前的存储地址（要如何去做，相信不用我再啰嗦了）。
当你找到了地址就添加在下方的地址列表中，然后右健单击该地址，在弹出的菜单中选择"找出是什么改写了这个地址"，将弹出一个空白的窗口。
接着点击本教程窗体上的"改变数值"按钮，并返回 Cheat Engine 。如果操作没问题 在刚才弹出的空白窗口中会出现一些汇编代码。
选中代码并点击"替换"按钮，将它替换成什么也不做的代码（空指令），同时，修改后的代码也将放置在"高级选项"的代码列表中去（保存地址列表时会同时保存）。
点击"停止"，游戏会以正常的方式继续运行下去，点击"关闭"按钮，关掉窗口。
现在，再次点击教程窗口上的"改变数值"，没问题的话，"下一步"将变为可点击的状态。

提示：如果你以足够快的速度锁定住该地址，"下一步"按钮也会变为可点击的。

这里改变数值实际上是通过汇编指令来实现对内存地址存储的修改：

实际上我们的代码查找步骤可以分解成以下几个动作：

• 找到存储此数值的当前地址
• 但我们使用“找出什么改写了这个地址”时，启动一个监视器，记录修改了该地址的汇编指令
• 将修改数值的汇编捕获后修改为 nop从而实现锁定数值的效果

总结：在游戏中许多数据的存储地址并不是固定的，而是通过动态分配实现的，也就是说传统的”固定地址”修改方法时不起作用的。这个时候衍生一个新的思路，我们不对数据进行修改，而是对改变数据的程序进行修改，这也是一种曲线救国的思路。

6. 指针

​ 先附上官方说明文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

步骤 6: 指针: (密码=098712)

上一步阐述了如何使用"代码查找"功能对付变化位置的数据地址，但这种方法往往不能达到预期的效果，
所以我们需要学习如何利用指针。
在本关的 Tutorial.exe 窗口下面有两个按钮，一个会改变数值，另一个不但能改变数值而且还会改变数值在内存中存储的位置。
这一步，你不需要懂得汇编，但如果懂的话会很有帮助。
首先找到数值的地址，然后再查找是什么改写了这个地址。
再次改变数值，CE 便可以列出找到的汇编代码。 双击一行汇编代码（或选择它并点击"详细信息"）并打开"详细信息"窗口以显示详细的信息，用来告诉你当这个指令运行时发生了什么事情。
如果在这条汇编指令中没看到方括号（[]）的存在，我们就应该查看下一条汇编代码的详细信息，
如果看到了方括号，那很可能表示我们已经找到了需要的指针。
返回到主 cheat engine 窗口 （只要你愿意，你可以保持这个额外的信息窗口为打开状态。如果你要关掉它，那么要记好方栝号中间的代码）并做一次 4 字节的扫描，扫描"详细信息"窗口中告诉你的一串十六进制数值。
扫描完成时它可能返回一个或几百个地址。大多数时候你需要的地址将是最少的一个。现在点击"手工添加地址"按钮，并勾选"指针"选项。
"添加地址"窗口将发生变化，多出了"Address of Pointer（指针地址）"和"Offset (Hex)（偏移量(16进制)）"的文本框，以便您键入一个指针的地址和偏移量。
请尽量填入刚才扫描到的地址。
如果汇编指令中的方栝号里存在计算（例如：[esi+12]）则把数值部分填在"Offset (Hex)"的文本框中，如果不存在，则让它保持为 0 。
如果看上去是更复杂的计算指令的话（举例说明一下）：
[EAX*2+EDX+00000310] eax=4C 并且 edx=00801234.
这种情况下 EDX 便是数值的指针，而 EAX*2+00000310 则是它的偏移量, 所以你要填在"Offset (Hex)"的将是 2*4C+00000310=3A8。（这些都是在十六进制下计算的，你可以使用WINDOWS的计算器，在科学方式下用十六进制计算）。
回到教程，点击"确定"这个地址便会加到 CE 主窗口下方的地址列表中，如果没做错，在地址栏将显示 P->xxxxxxxx，而 xxxxxxxx 和你扫描到的地址数值是一致的，如果不一致，那么可能是哪里出错了。
现在, 改变那条指针地址的数值为 5000 并锁定它，然后点击 Tutorial.exe 窗口上的"改变指针"按钮，如果一切正确，"下一步"按钮将变为可点击状态。

备注:
你也可以使用"指针扫描"的方式来查找这个指针地址。

一开始对着教程做，怎么也理解不了这个过程，以及为什么要这样子做。这里我们结合C语言来加以理解：

1
2
3
4
5
6
7
8
9

int ** pp;
int *p;
int q;
// 数据一般情况下被动态分配
//此时假设p为数据存储的位置，也是p的数据被动态分配，导致数据的位置不确定
p = &q; 
//但是我们能找到一个二级指针来指向p的位置，pp自身的位置是硬编码，并不会改变
pp = &p;
//也就是说只要我们能找到二级指针，就能根据指向，取到q中的数据

在这里，我们将二级指针的地址称之为数据的基址，我们可以通过设置基址和偏移量来实现一个指向数据的指针。

在这一关中，我们需要进行以下操作：

• 确定数据当前的地址
• 记录修改了此地址的汇编指令，并定位一级指针的基址
• 设置指针指向当前的数据，手动添加地址

思考：在我们手动设置地址时，添加偏移地址有什么用？

指针存储的是另一个变量的内存地址。通过指针和偏移地址，可以间接访问目标变量。偏移量用于从指针指向的基地址出发，找到目标变量的具体位置。同时这样也可以增强代码的可移植性，因为绝对地址在内存分布中可能会发生改变，但是相对地址是不变的。使用偏移地址，是内存管理的一种智慧

7. 代码注入

​ 附上官方说明文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

步骤 7: 代码注入: (密码=013370)

代码注入是将一小段你写出的代码注入到目标进程中并执行它的技巧。
在这一步教程中，你将有一个健康值和一个每按一次将减少 1 点健康值的按钮，
你的任务是利用"代码注入"，使每按一次按钮增加2点的健康值。
查找这个地址，然后看看是什么在改写它（"找出是什么改写了这个地址"）。
当你看到那条减少数值的汇编代码后，选择"显示反汇编程序"，然后打开"自动汇编窗口"（菜单-工具->自动汇编 或 按下快捷键 Ctrl+a )，选择"模板"中的"代码注入"。CE 将自动生成一部分汇编代码并为你输入指令做好准备（如果 CE 没有给出正确的地址，你也可以手工输入它）。
注意 alloc 这部分代码，它会为你的代码分配出一小块空白的内存，过去，在 Win2000 之前的系统，这种行为存在安全隐患，很可能导致系统崩溃，幸运的是，这种情况在 win2000 以后的操作系统得到改善。
也要注意line newmem: 、originalcode: 以及用文本"此处放置你的代码"标示出的空白部分
正如你猜测的， 在这儿可以写下每次增加2点健康值的代码。
在这种情况下推荐你使用 "ADD" 汇编指令，
下面是一些示例：
"ADD [00901234],9" 使 [00901234] 地址的值增加9
"ADD [ESP+4],9" 使地址指针 [ESP+4] 的值增加9
在本关的情况下，你可以使用相同的手法处理减少健康值的那条原代码方括号之间的部分。

提示 1：
推荐你从原代码中删除减少健康值的那行代码，否则你得加 3 点健康值（你增加了3点，原代码减去1点，最终结果才会增加2点），这样看上去很容易让人迷惑，但最终方案还是由你来决定好了。
提示 2:
某些游戏中，原代码可能在多条指令之外，有时候（并非一向如此），它可能由不同的地方跳转至你的指令中并结束运行，其结果可能引起未知的错误；如果出现了这种情况，通常应当查看附近的那些跳转指令，进行修改，或者尝试使用不同地址进行代码注入，确认无误后便可以将你修改的代码注入到原代码中了。

这个原理很简单：

• 显示监视到修改数据的汇编程序，然后通过反汇编程序找到修改数据的程序
• 通过 菜单-工具->自动汇编->代码注入的方式来对源程序进行修改

思考：代码注入在汇编层面是怎么实现的？

我一开始以为代码注入，是对源程序进行覆盖，但是这样是不安全的行为。仔细观察后发现，在注入代码后，原来的地址被替换为了一个跳转指令。然后在未使用的空间注入我们修改的代码，然后在使用后跳转回来，也就是说，本质上这是一个子程序调用的过程。那么如果我们只需要修改一行命令或者将其nop掉，我们只需要使用 替换即可，对于多行注入才使用 代码注入

8. 多级指针

​ 附上官方说明文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14

步骤 8: 多级指针: (密码=525927)

在这一步将解释如何使用多级指针。
在第 6 步，你已经清楚 1 级指针的概念和用途，并可以利用数值的首个地址找到存放数据真正的基址。
在本关中，你将看到 4 级指针，它由第一个指针指向第二个指针，再由第二个指针指向第三个指针，由第三个指针指向第四个指针，最终指向健康值的真正地址。
开始的几步与在第 6 步中的操作基本相同。找出是什么访问了这个地址，然后分析汇编指令，查找指针地址中的数值，以及它的偏移量，将它们记下来。但这次你按数值找出的仍然是一个指针，你得依据这些数值，使用同样的操作方法找出指向这个指针的指针。看看是什么访问了你发现的那个指针地址，分析汇编指令，留意可能的代码和偏移量，并加以利用。
持续这种过程，直到不能更进一步查找为止（通常基址为静态时，地址将以绿色标示）。
点击"改变数值"改变健康值，
如果你发现列表中那些指针地址所指向的值发生同样的变化时，那表示你可以试着将基址中的值更改为 5000，并锁定它，以便完成本关的任务了。

备注1: 本步骤也可以使用自动汇编程序脚本或者使用指针扫描器加以解决。
备注2: 在某些情况下，可以改变 CE 软件"代码查找"的相关设置。
当你遇到类似于 mov eax,[eax] 的指令时，调试程序将显示改变之后的寄存器中的值，也许利用它更容易找出指针的位置。
备注3: 你还在读？！当你查看汇编指令时你可能已经注意到，这些指针是在相同的代码块（相同的程序，如果你懂汇编，可以查看程序的起始代码）位置被读写。这种情况并不总会发生，但是当你在查找某个指针遇到问题的时候，没准能起到很大的用处。

本来想试试指针扫描器的，但感觉有点复杂，所以用第六关一样的方法向上搜索这不过这一次的复杂一点，其步骤如下：

• 首先定位数据，然后查找指向这个数据的指针
• 在详细信息中，我们可以看到一级指针的地址和偏移地址，然后我们创建一个一级指针
• 然后我们在查找执行一级指针地址的指针…
• 如此往复，直到找到数据的基址

总结：一个数据可能由多级指针定位，我们可以任然可以通过寻找基址的方法定位这个指针链。这个需要耐心，而且操作的过程需要清楚自己在做什么（从1号柜子拿到2号柜子的钥匙，打开2号柜子拿到3号柜子的钥匙…）

9. 注入 ++

​ 附上官方文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

步骤 9: 注入++: (密码=31337157)

这一步将会解释如何处理游戏中的共用代码, 这种代码是通用在除了自己以外的其他同类型对像上

常常你在修改游戏的时候, 你找到了一个单位的健康, 或是你自己角色的健康, 你会发现一种情况: 如果你把健康相关代码移除的话，其结果是你的角色无敌, 但你的敌人也无敌了。
在这种情况下, 你必须想办法区分自己与敌人。
有时候很简单, 你只要检查最前面的4个字节(函数指针表), 它通常指向一个独一无二的地址, 代表着游戏玩家角色，而有的时候它是一个团体号码, 或者也可能是一个指针, 它指向另一个指针, 该址针又指向下一个指针,搞不好还指向下下一个指针, 最后指向一个玩家名字。总之完全取决于游戏的复杂度, 以及你的运气

最简单的方法是以"找出是什么改写了这个地址"去找出游戏代码，然后使用"分析(新/旧)数据/结构"的功能去比较两种结构。(你的单位和敌人的单位)然后看看是不是可以找到一个区分两者的方法。
当你找到如何区分你和电脑单位的方法后，你可以注入一段自动汇编脚本来检查状态，然后看是要运行游戏的代码还是要做其他的修改。(例如一击必杀)
另外, 你还可以用这个方法去创建一般所说的"字节数组"的字串, 它可以用来搜寻并产生一份所有你的单位或是敌人单位的列表
在这个教程中, 我已经实现了你将会玩到的最惊人的游戏.
这个游戏有4个玩家。2个属于你的阵容, 另外两个属于电脑方。
你的任务是找到改写健康的代码, 并且修改以至于你可以获得胜利，但"绝不能"使用锁定HP的方法.
完成修改以后, 请按 "重新启动游戏并自动执行" 来测试你的修改是否正确

提示1: 健康是一个单浮点数
提示2: 解法不只一种

这个是一个应用题，所以就详细讲讲过程

• 首先定位 四个人物血量的存储地址
• 然后追踪发现这四个任务的血量修改的程序都是同一个（无差别），可是我们希望能攻击敌人却不攻击自己，所以我们需要找到同伴与敌人的特征码
• 接下来 找出指令访问的地址 然后 打开选中地址分析数据，我们可以比较这四个数据的不同点，观察发现在偏移地址位+10的地方有着识别码，而在+04的偏移地址存放着血量
• 接下来我们需要代码注入，当识别为同伴时恢复至满血，当识别为敌人时直接杀死
• 然后重启程序并执行即可

书接上回 这一篇主要讲一下，当一个C语言函数在执行时，操作系统是如何调度内存将数据存放并完成相关函数操作的

C语言内存分布

当一个C语言程序被编译成可执行文件执行时，它在内存中的存储如右图所示。这是一个内存空间，地址由底部逐渐升高：

• 其中顶层的Kernel是操作代码的核心源码，它是操作系统完成功能的关键
• 栈用于静态分配中的存放局部变量，例如程序中的局部变量t和ptr都被存储在栈中
• BSS存储未初始化的全局变量和静态变量
• Heap(堆)用于负责存储动态分配的内存空间比如malloc和free操作的内存空间
• data用于存储已经进行了初始化的全局变量
• 在heap和stack中间的内存空间，是一片共享的内存空间,heao从低地址向高地址分配空间，stack从高地址向低地址分配

栈中的内存分配与工作原理

现在分析一下函数调用时，栈的内存空间中是如何分配的

要了解栈，首先需要理解栈中常用的几个寄存器：

• 在32位中，我们用esp,ebp,eip三个寄存器
• 在64位中，我们用rsp,rbp,rip三个寄存器

接着我们需要了解一下栈帧的概念，一个栈帧就是保存一个函数的状态，简单地说，就是一个函数所需要的栈空间。 sp永远指向栈帧的栈顶， bp永远指向栈帧的栈底， ip则指向当前栈栈帧执行的命令。

我们现在可以分析一下函数调用的过程，栈底的第一个栈帧存储着我们的主函数的父函数，所以说main实际上并不是第一个栈帧，在main之前还有一些编译过程中产生的库文件，只不过不产生栈帧。

当我们在main中调用其他函数时，我们便在栈中开辟一块新的栈帧，并在其中存储上一个栈的栈底，当函数调用结束时，我们就将现在的栈帧弹出，恢复到原来的main函数继续执行完main函数。

那么，至此我们需要进一步的对栈帧的具体结构进行讲解。首先是栈帧的创建：

以上是一个栈帧建立的过程，我们注意到新栈帧底部的返回地址。这是栈溢出使用的关键，这个返回地址的实际作用是在当前栈帧结束后，弹出至ip，实现函数返回。而在栈溢出的攻击中，我们可以通过覆盖/修改返回地址的内容，使其指向我们想要的后门函数。这就是栈溢出攻击的原理

我们接下来进一步看看栈帧的返回过程：

这里我们需要注意返回地址实际上是调用函数指令的下一条，并不是我们理解的返回函数入口。

在这些PPT中我们可以感受到一个函数返回的过程：

• 首先是撤销我们的栈帧中的局部变量，我们直接弹出即可
• 然后我们将原函数的栈底弹出，恢复原来栈底
• 再将返回地址弹出，让函数继续执行

这样的一个过程便是函数调用与返回，通过图片的形式展现出来。

栈溢出攻击

在学习了函数返回的原理之后，我们明确，只要想办法修改返回地址即可实现攻击

那么我们在哪一步中有机会实现这个操作呢？

我们可以通过将局部变量溢出来实现攻击，但是并非所有的情况下都能实现攻击。不过当程序中使用了 gets的有安全隐患的函数时，因其并没有设置边界，理论上是可以栈溢出至返回地址，并将其覆盖的。

我们可以写出常见的攻击脚本：

1
2
3
4
5
6

from pwn import *
p = remote("xxxx",端口)
payload="a"*(局部变量的长度)+"a"*(栈底的长度)+p64(你想要的返回地址)
# 注意 这里的长度随机器变化，32位与64位不同
p.sendline(payload)
p.interactive()

这里我们接下来使用TurboC2来尝试编写可执行程序，它是一个可以在DOS十六位上运行的C语言编辑器，我们使用C语言来进一步的对8086进行学习

有关Turbo2C的安装到网上找教程即可

使用寄存器

在汇编中使用寄存器，需要指定寄存器名，在C语言中也是如此

我们可以tc2.0支持以下寄存器名

根据寄存器名称可以理解对应的寄存器关系

我们进行以下思考

1. 用TurboC编译出来的可执行程序和用masm编译出来的程序有什么区别？

首先我们用turboC写出以下程序然后进行编译

我们注意到当我们查看debug时看到的汇编代码和我们写的C语言程序并不一样

此时我们思考下一个问题：

2. main函数的代码在什么段中，我们怎么找到它？

在这里我将答案写在了我的源程序中，我们可以看到 printf("%x",main)

这一条指令的作用是答应出main函数在代码段中的偏移地址: 0x01FA

这里还需要注意，为什么可以用main来找到其在代码段中的偏移地址。这是因为在这里，main是一个标号，并不是一个变量。我们可以通过printf("%x",&main)来验证，如果main是变量，那么此时打印出来的是main变量的存储地址，然而实际上main是一个直接指向代码段地址的标号

所以我们可以定位到我们的程序，并看到我们写的程序逻辑：

3. 那么程序DEBUG时我们，一开时看到的内容是什么？

我们可以判断添加这一部分内容的肯定时编译连接程序，所以其作用，可能与程序执行前后的饿现场保护，系统调度有关系。那么，这多出来的部分应该是固定的，与我们编写的程序无关。所以在 上面拿到的偏移地址，对于所有的程序都是一样的。

4. 我们在程序中看到main函数后有ret指令，因此我们可以设想：C语言将函数实现为汇编中的子程序。但是如何验证？

我们编写一个有函数调用过程的C程序即可

我们通过调试打开可以看到

在这里看可以看到函数的调用过程，实际上就是子程序的调用

使用内存空间

首先要明确内存空间的使用，对于寄存器而言，我们需要给出寄存器的名称，寄存器的名称中也包含了他们的类型信息。而对于内存空间我们同样也需要给出内存地址（准确的说是内存空间首地址）和空间存储数据的类型。

现在我们对一些C语言的指令进行分析：

1

*(char *)0x2000 = 'a';

这里我们的第一个*是访问内存空间地址的意思，而(char *)则是指明这是一个存储char型数据的内存空间地址

当然我们也可以直接使用给出段地址和偏移地址，比如我们要向一个地址为 2000：0存储一个字节的内存空间写入字符a

1

*(char far *)0x20000000='a';

“far”指明内存空间的地址是段地址和偏移地址，而0x20000000中的0x2000给出了段地址，0000给出了偏移地址

当然这种对内存空间进行直接访问的方式是不安全的，我们可能无意间修改了别的程序的代码或者数据，从而引起错误

（1）首先编写一个程序，看看C语言的内存空间使用，在汇编中是以什么形式呈现？

我们可以看到汇编中的完成方式（由此可以感受到汇编与C的相似性）

（2）现在我们尝试在C语言中写一个程序来实现打印字符”Hello”

简单粗暴的方法

（3）那么我们现在进一步的思考，C语言将全局的变量存放在哪里？将局部变量又存放在哪里？每个函数开头的push bp mov bp sp又有什么意义？分析以下代码思考一下

1
2
3
4
5
6
7
8
9
10
11
12

int a1,a2,a3;
void f(void);
main(){
    int b1,b2,b3;
    a1=0xa1;a2=0xa2;a3=0xa3;
    b1=0xb1;b2=0xb2;b3=0xb3;
}
void f(void){
    int c1,c2,c3;
    a1=0x0fa1;a2=0x0fa2;a3=0x0fa3;
    c1=0xc1;c2=0xc2;c3=0xc3;
}

我们看到 SUB SP,+06将栈顶下移了6个字节用来存放局部变量，为什么是存放局部变量而不是全局变量呢，在存储的过程中，我们可以看到对于全局变量，是使用直接定址的方法进行存储在程序的数据段中，而对于局部变量则是以栈底的相对位置进行访问。由此可以看出，局部变量以栈的形式存储在函数的同一个栈中。

在这里我们便可以理解push bp mov bp sp的意义，通俗来讲。这是因为全局变量被存储于数据段中，而局部变量被存储于栈段中，和函数功能存放在一起，而这段指令则是用于创建一个新的函数栈帧。

我在下一篇博客中会详细讲解这个过程。

（4）此时我们进一步思考，函数的返回值被存放在哪里？分析下面的程序

1
2
3
4
5
6
7
8
9
10

int f(void);
int a,b,ab;
main(){
    int c;
    c=f();
}
int f(void){
    ab = a+b;
    return ab;
}

我们很容易理解前面的逻辑，其中 [01A6],[01A8],[01AA]都是全局变量的位置，但是此时我们注意到 MOV AX,[01AA]观察可以得到，在这里函数的返回值通过寄存器的方式返回。

（5）理解内存的创建与释放？分析以下函数

1
2
3
4
5
6
7
8
9

#define Buffer ((char *)*(int far *)0x2000000)
main(){
    Buffer = (char *)malloc(20);
    Buffer[10]=0;
    while(Buffer[10]!=8){
        Buffer[Buffer[10]]='a'+Buffer[10];
        Buffer[10]++;
    }
}

气死了，这个实验不知道为什么做的很不成功，先是没办法正常分配内存，然后再是拿不到正常的返回值，算了算了

不用main函数编程

现在我们讨论一个问题，如果一个C程序中它没有使用main函数编程，那它是否能被编译并正常运行呢？

现在我们准备两个程序

1
2
3
4

f(){
    *(char far *)(0xb8000000+160*10+80)='a';
    *(char far *)(0xb8000000+160*10+81)=2;
}

1
2
3
4

main(){
    *(char far *)(0xb8000000+160*10+80)='a';
    *(char far *)(0xb8000000+160*10+81)=2;
}

我们在对F.exe进行编译后出现了如下报错，且编译失败，故我们用link对F.obj进行编译

接下来我们分别运行M.exe和F.exe，运行结果如下：

M运行后正常显示并正常返回，但是F出现了一些情况。虽然a的显示是正常的，但是F运行之后，程序卡死，无法返回正常的操作

这是为什么呢，我们观察两个程序的大小

发现M程序的大小远大于F程序，说明M程序中包含了跟多的指令和信息，我们对其分别进行反汇编，发现相较于M程序，F程序只是一个孤零零的子程序只有入口却没有返回。而M程序则是一个完整的程序，且在01FA之前，有着完整的程序

而且相较于F程序，M程序的子程序结尾多了 RET PUSH BP MOV BP,SP这一部分的作用是用于函数返回，恢复原栈帧用的

现在我们可以好好分析一下二者的区别：

• 首先main函数被作为了一个子程序，且在编译时被添加了很多代码
• f函数则是作为一个子程序被直接调用却没有返回

因此，问题出在main函数被编译连接的过程中，我们回想f函数编译失败的报错 Linker Error:Undefined symbol _main in module C0S我们可以猜测，在连接的过程中，连接器把main.obj与C0S.obj连接在了一起，得到我们的main.exe函数。此时我们可以进一步的推断，01FA地址以前的程序都是来自COS.obj中。接下来我们对此进行验证：

我们在lib文件夹下面找到C0S.obj文件并将其编译，然后对执行程序进行反编译

​

我们发现这部分代码和01FA以前的代码很像啊，几乎一样，所以我们可以认定main函数以前的代码都与C0S是有关系的

从上面我们可以看出，tc.exe把c0s.obj和用户.obj文件一同进行连接，生成.exe文件。按照这个方法生成.exe文件中的程序的运行过程如下：

• c0s.obj中的程序先运行，进行相关的初始化，比如，申请资源，设置DS,SS等寄存器
• c0s.obj中的程序调用main函数，从此用户程序开始运作
• 用户程序从main函数中返回到c0s.obj的程序中
• c0s.obj程序接着运行，进行相关资源的释放,环境恢复等问题;
• c0s.obj的程序调用DOS的int 21h例程的4ch号功能，程序返回

所以看来C语言程序必须从main函数开始，是C语言的规定，这个规定不是在编译时保证的，也不是连接的时候保证的，而是用下面的机制保证的：

• 首先，C开发系统提供了用户写的应用程序正确运行所必须的初始化和程序返回等相关程序，这些程序被存放在相关的.obj程序中
• 其次，需要将这些文件和用户.obj文件一起连接，才能生成可正确运行的.exe文件
• 基于这个机制，我们只需要改写c0s.obj，让它调用其他函数，编程时就可以不写main函数了

现在我们自己写一个简单的c0s.obj程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

assume cs:code
data segment
	db 128 dup(0)
data ends
code segment
start:
	mov ax,data
	mov ds,ax
	mov ss,ax
	mov sp,128
	
	call s

	mov ax,4c00h
	int 21h
s:

code ends
end start

我们尝试将它和f.obj连接在一起看看能不能生成可正确执行的可执行程序

OK ,经过不懈的努力我们也是成功连接出了一个可正确执行的可执行程序。

这里需要补充一下连接多个目标文件的用法 link file1.obj file2.obj...;

函数如何接受不定数量的参数

给定参数的函数参数传递

我们通过一个简单的程序来研究两个问题，main函数时如何给showchar传递参数的？showchar是如何接受参数的？

1
2
3
4
5
6
7
8

void showchar(char a,int b);
main(){
    showchar('a',2);
}
void showchar(char a,int b){
    *(char far *)(0xb800+160*10+80) = a;
    *(char far *)(0xb800+160*10+81) = b; 
}

我们先编译成可执行程序后，反汇编其代码：

我们可以看到一个下面这样的栈结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

内存地址 (低地址)
+-----------------+
|      		      |  <- SP 指向这里 (0000)
+-----------------+
|                 |  <- 0001
+-----------------+
|      BP (低位)  |  <- 0002
+-----------------+
|      BP (高位)  |  <- 0003 (PUSH BP)
+-----------------+
|      AX (AL)    |  <- 0004
+-----------------+
|      AX (AH)    |  <- 0005 (PUSH AX)
+-----------------+
|      AX (AL)    |  <- 0006
+-----------------+
|      AX (AH)    |  <- 0007 (栈底)(PUSH AX)
+-----------------+
内存地址 (高地址)

我们可以看到在函数调用传入参数时，是以栈底为基础相对位移对传入的参数进行访问。也就是说，依次向AL中传入的数值便是我们的参数。

总结得到C语言中参数的传递是通过栈来实现的。在函数调用前，将参数放入AX中，进入调用函数后，先把参数中的值出栈到AX中。这样就完成了函数间参数值的传递工作。其次我们还需要注意：在参数入栈中首先入栈的是后面的参数，即入栈时为倒序入栈，这是因为栈先进后出的特性

不定参数个数的函数传参

我们编写一个不定参数个数的函数后进行分析

1
2
3
4
5
6
7
8
9
10
11

void showchar(int,int,...);
main(){
	showchar(8,2,'a','b','c','d','e','f','g','h')
}
void showchar(int n,int color,...){
	int a;
	for(a=0;a!=n;a++){
		*(char far *)(0xb8000000+160*10+80+a+a)=*(int *)(_BP+8+a+a),
		*(char far *)(0xb8000000+160*10+81+a+a)=color;
	}
}

这里我用AI画了一个栈段图，可以更形象的理解这个调用的过程

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

+-------------------+
|   返回地址        | <- _BP + 0
+-------------------+
|   旧的 _BP 值     | <- _BP + 2
+-------------------+
|   第一个参数 n    | <- _BP + 4
+-------------------+
|   第二个参数 color| <- _BP + 6
+-------------------+
|   第三个参数 'a'  | <- _BP + 8
+-------------------+
|   第四个参数 'b'  | <- _BP + 10
+-------------------+
|   第五个参数 'c'  | <- _BP + 12
+-------------------+
|   第六个参数 'd'  | <- _BP + 14
+-------------------+
|   第七个参数 'e'  | <- _BP + 16
+-------------------+
|   第八个参数 'f'  | <- _BP + 18
+-------------------+
|   第九个参数 'g'  | <- _BP + 20
+-------------------+
|   第十个参数 'h'  | <- _BP + 22
+-------------------+

因此就不过多赘述了，这便是函数传递参数的原理

写一个printf函数

知道了传递参数的原理，我们写一个简单的print函数来结束对于TurboC 的简单学习

功能：实现一个支持%c,%d的printf函数

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

void print(char *str,...);

main(){
	print("%c %c %c %c",'a','b','c','d');
}

void print(char *str,...){
	int color = 2;
	int x = 2;
	int i = 0;
	int j = 0;
	int data = 0;
	int buffer[100];
	int bit = 0;
	char ch = str[i++];

	while(ch){
		if(ch == '%'){
			ch = str[i++];
			if(ch == 'c'){
				*(char far *)(0xb8000000+160*10+80+x) = *(int *)(_BP+6+j);
				*(char far *)(0xb8000001+160*10+80+x) = color;
				x = x+2;
				j++;
			}
			if(ch == 'd'){
				bit = 0;
				data = *(int *)(_BP+6+j);
				j++;
				if(data == 0){
					*(char far *)(0xb8000000+160*10+80+x)='0';
					*(char far *)(0xb8000001+160*10+80+x)=color;
					x = x+2;
				}else{
					while(data !=0){
						buffer[bit] = data%10;
						data = data / 10;
						bit++;
					}
					bit--;
					for(;bit>=0;bit--){
						*(char far *)(0xb8000000+160*10+80 + x) = buffer[bit]+'0';
						*(char far *)(0xb8000001+160*10+80 + x) = color;
						x = x+2;
					}
				}
			}
		}else{
			*(char far *)(0xb8000000+160*10+80+x)=ch;
			*(char far *)(0xb8000001+160*10+80+x)=color;
			x = x+2;
		}
		ch = str[i++];
	}
}

至此对于8086的简单学习到这里结束了

这几天一直在玩，要抓紧学完，去学别的东西哦

直接定址表

学习如何有效的组织数据，以及相关的编程技术

描述了单元长度的标号

我们先以一个程序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

assume cs:code 
code segment
    a: db 1,2,3,4,5,6,7,8
    b: dw 0
start:
    mov si,offset a
    mov bx,offset b
s:
    mov al,cs:[si]
    mov ah,0
    add cs:[bx],ax
    inc si
    loop s
    mov ax,4c00H
    int 21h
code ends
end start  

这里的 a b start s code都是标号。这些标号仅仅表示了内存单元的地址

但是我们还有一种标号，这种标号不仅表示内存单元的地址，同时还表示了内存单元的长度

上面的程序可以写成下面的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

assume cs:code 
code segment
    a db 1,2,3,4,5,6,7,8
    b dw 0
start:
    mov si,offset a
    mov bx,offset b
s:
    mov al,cs:[si]
    mov ah,0
    add cs:[bx],ax
    inc si
    loop s
    mov ax,4c00H
    int 21h
code ends
end start  

在code段中使用的标号a，b后面没有 :，他们是同时描述内存地址和长度的标号，例如：

• 标号a，描述了地址code:0，和从这个地址开始，以后的内存单元都是字节单元
• 标号b，描述了地址code:8，和从这个地址开始，以后的内存单元都是字单元

可见，使用这种包含单元长度的标号，可以使我们以简洁的形式访问内存中的数据。我们将这种标号称为 数据标号

在其他段中使用数据标号

指定段寄存器

在其他段中，也可以使用数据标号来描述存储数据的单元的地址和长度

不过要注意，在后面加有”:“的地址标号，只能在代码段中使用，不能在其他段中使用

比如我们以一个累加程序为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

assume cs:code,ds:data
data segment
    a db 1,2,3,4,5,6,7,8
    b dw 0
data ends
code segment
start:
    mov ax,data
    mov ds,ax
    mov si,0
    mov bx,8
s:
    mov al,a[si]
    mov ah,0
    add b,ax
    inc si
    loop s
    mov ax,4c00H
    int 21h
code ends
end start  

注意，如果想在代码段中直接用数据标号访问数据，需要用都安寄存器和标号所在的段进行关联，否则编译器无法却确定标号的段地址在哪一个寄存器里。

这里并不是说，如果用assume指令将段寄存器和某个段相联系，段寄存器中就真的回存放该段的地址。我们在程序中，仍然需要指令对段寄存器进行设置

将标号当作数据定义

可以将标号当作数据来定义，此时，编译器将标号所表示的地址当作数据的值。比如：

1
2
3
4
5

data segment
	a db 1,2,3,4,5,6,7,8
	b dw 0
	c dw a,b
data ends

数据标号c存储的两个字型数据为标号a,b的偏移地址。相当于：

c dw offset a, offset b

再比如：

1
2
3
4
5

data segment
	a db 1,2,3,4,5,6,7,8
	b dw 0
	c dd a,b
data ends

数据标号c处存储的两个双字型为标号a的偏移地址和段地址，标号b的偏移地址和段地址。相当于：

c dw offset a,seg a,offset b,seg b

这里的seg操作符,功能为取得某一标号的段地址

直接定址表

我们注意到数值0_{15和字符”0”}“F”之间并没有直接的映射关系，所以我们需要再他们之间建立新的映射关系

数值0_{9和字符”0”}“9”之间的映射关系最明显，有 数值 + 30H = 对应字符的ASCII值

数值10_{15和字符”A”}“F”之间的映射关系则是，数值 + 37H = 对应字符的ASCII值

具体的做法是，建立一张表，表中依次存储字符”0”_{“F”，我们可以通过数值0}15直接查找到对应的字符

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

assume cs:code
stack segment
    dw 16 dup(0)
stack ends
code segment
start:
    mov ax,stack
    mov ss,ax
    mov sp,16
    mov ax,3AH
    call show

    mov ax,4c00H
    int 21h

showbyte:
    jmp short show
    table db '0123456789ABCDEF' ;字符表

show:
    push bx
    push es

    mov ah,al
    shr ah,1
    shr ah,1
    shr ah,1
    shr ah,1            ;取高四位
    and al,00001111b    ;取低四位

    mov bl,ah
    mov bh,0
    mov ah,table[bx]

    mov bx,0b800H
    mov es,bx
    mov es:[160*12+40*2],ah

    mov bl,al
    mov bh,0
    mov al,table[bx]

    mov es:[160*12+40*2+2],al

    pop es
    pop bx

    ret

code ends
end start  

这张表定义后可以实现映射操作，当我们向ax中传输一个数值时，它会返回这个数值到显示器上

这种映射关系一般用作以下几种用途：

• 为了算法的清晰和简洁
• 为了加快运算速度
• 为了使程序易于填充

接下来编写一个子程序sin (x),  x ∈ {0^∘, 30^∘, 60^∘, 90^∘, 120^∘, 150^∘, 180^∘}并在屏幕中央显示结果，我们可以用麦克劳林公式进行计算sin(x)，不过为了加快运算速度，在这里我们使用映射来加快这个过程。我们可以写出以下程序：

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

assume cs:code
stack segment
    dw 16 dup(0)
stack ends
code segment
start:
    mov ax,stack
    mov ss,ax
    mov sp,16
    mov ax,120
    call show

    mov ax,4c00H
    int 21h

showsin:
    jmp short show
    table dw ag0,ag30,ag60,ag90,ag120,ag150,ag180   ;字符串偏移地址
    ag0 db '0',0
    ag30 db '0.5',0
    ag60 db '0.866',0
    ag90 db '1',0
    ag120 db '0.866',0
    ag150 db '0.5',0
    ag180 db '0',0
show:
    push bx
    push es
    push si
    mov bx,0b800H
    mov es,bx
    ;用角度/30作为相对于table的偏移值，取得对应的字符串的偏移地址，放在bx中
    mov ah,0
    mov bl,30
    div bl
    mov bl,al
    mov bh,0
    add bx,bx       ;注意每个标号实际上使双字节的
    mov bx,table[bx]
    ;显示
    mov si,160*12+40*2
shows:
    mov ah,cs:[bx]  ;此时bx存储了表中的偏移地址
    cmp ah,0
    je showret
    mov es:[si],ah
    inc bx
    add si,2
    jmp short shows
showret:
    pop si
    pop es
    pop bx
    ret


code ends
end start  

上面这种可以通过依据数据，直接计算出所要找的元素的位置的表，我们称之为直接定址表

程序入口的直接定址表

我们可以在直接定址表中存储子程序的地址，从而方便的实现不同子程序的调用。

我们编写以下程序

得知需求之后，分析一下功能的实现：

1. 清屏：讲显存中当前屏幕中的字符设置为空格符
2. 设置前景色：设置显存中当前屏幕中处于奇地址的属性字节的第0，1，2位
3. 设置背景色：设置显存中当前屏幕中处于奇地址的属性字节的第4，5，6位
4. 向上滚动一行：依次将第n+1行的内容复制到第n行；最后一行为空

我们可以写出以下程序：

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

assume cs:code
stack segment
    dw 32 dup(0)
stack ends
code segment
start:
    mov ax,stack
    mov ss,ax
    mov sp,32

    mov ah,3
    mov al,1
    call setscreen

    mov ax,4c00h
    int 21h
setscreen:
    jmp short set
table  dw sub1,sub2,sub3,sub4
set:
    push bx
    cmp ah,3
    ja sret
    mov bl,ah
    mov bh,0
    add bx,bx

    call word ptr table[bx]

sret:
    pop bx
    ret

;清屏
sub1:
    push bx
    push cx
    push es
    mov bx,0b800h
    mov es,bx
    mov bx,0
    mov cx,2000
sub1s:
    mov byte ptr es:[bx],' '
    add bx,2
    loop sub1s
    pop es
    pop cx
    pop bx
    ret
;设置前景色
sub2:
    push bx
    push cx
    push es
    mov bx,0b800h
    mov es,bx
    mov bx,1
    mov cx,2000
sub2s:
    and byte ptr es:[bx],11111000b
    or es:[bx],al
    add bx,2
    loop sub2s
    pop es
    pop cx
    pop bx
    ret
;设置背景色
sub3:
    push bx
    push cx
    push es
    mov cl,4
    shl al,cl
    mov bx,0b800h
    mov es,bx
    mov bx,1
    mov cx,2000
sub3s:
    and byte ptr es:[bx],10001111b
    or es:[bx],al
    add bx,2
    loop sub3s
    pop es
    pop cx
    pop bx
    ret
;上移一行
sub4:
    push cx
    push si
    push di
    push es
    push ds
    mov si,0b800h
    mov es,si
    mov ds,si
    mov si,160  ;ds:si指向第n+1行
    mov di,0    ;es:di指向第n行
    cld
    mov cx,24
sub4s:
    push cx
    mov cx,160
    rep movsb
    pop cx
    loop sub4s
    mov cx,80
    mov si,0
sub4s1:
    mov byte ptr [160*24+si],' '
    add si,2
    loop sub4s1
    pop ds
    pop es
    pop di 
    pop si 
    pop cx
    ret
code ends
end start

根据上面的程序需求即可修改对应的参数

最后的挑战

字符串打印

程序如下，利用栈和int 16h模拟了键盘的输入和撤回：

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

assume cs:code
stack segment
    dw 128 dup(0)
stack ends
code segment
start:
    mov ax,stack
    mov ss,ax
    mov sp,256
    call clean
    mov dh,12
    mov dl,25
    call getstr

    mov ax,4c00h
    int 21h

charstack:
    jmp short charstart
table dw charpush,charpop,charshow
top dw 0            ;栈顶
charstart:
    push bx
    push dx
    push di
    push es

    cmp ah,2
    ja sret
    mov bl,ah
    mov bh,0
    add bx,bx       ;表项是二字节的，所以偏移位置要左移一位
    jmp word ptr table[bx]
charpush:
    mov bx,top
    mov [si][bx],al
    inc top
    jmp sret
charpop:
    cmp top,0
    je sret
    dec top
    mov bx,top
    mov al,[si][bx]
    jmp sret
charshow:
    mov bx,0b800h
    mov es,bx
    mov al,160
    mov ah,0
    mul dh          ;行号
    mov di,ax
    add dl,dl
    mov dh,0        ;列号
    add di,dx
    mov bx,0
charshows:
    cmp bx,top
    jne noempty
    mov byte ptr es:[di],' '
    jmp sret
noempty:
    mov al,[si][bx]
    mov es:[di],al
    mov byte ptr es:[di+2],' '
    inc bx
    add di,2
    jmp charshows
sret:
    pop es
    pop di
    pop dx
    pop bx
    ret
; bye:
;     mov ax,4c00h
;     int 21h
getstr:
    push ax
getstrs:
    mov ah,0
    int 16h
    ; cmp al,1
    ; je bye
    cmp al,20h  
    jb nochar   ;字符码小于20h,说明不是字符
    mov ah,0
    call charstack ;字符入栈
    mov ah,2
    call charstack ;显示字符
    jmp getstrs
nochar:
    cmp ah,0eh     ;BS的扫描码
    je backspace 
    cmp ah,1ch      ;Enter的扫描码
    je enter
    jmp getstrs
backspace:
    mov ah,1
    call charstack  ;字符出栈
    mov ah,2
    call charstack  ;显示字符
    jmp getstrs
enter:
    mov al,0
    mov ah,0
    call charstack  ;0入栈
    mov ah,2
    call charstack  ;显示字符
    pop ax
    ret
;清屏
clean:
    push bx
    push cx
    push es
    mov bx,0b800h
    mov es,bx
    mov bx,0
    mov cx,2000
cleans:
    mov byte ptr es:[bx],' '
    add bx,2
    loop cleans
    pop es
    pop cx
    pop bx
    ret
code ends
end start