田宇轩编程的地方

这里用来安放一些有关编程的事

最新文章

算法导论的编程实现
为了学习算法，我们对《算法导论(第三版)》中算法和数据结构进行了多种语言的编程实现。最开始感觉这本书很厚，有一些数学基础不好的同学在接触到里面复杂的数学证明之后直接就弃坑了。不过…查看全文
兔兔
2 months ago
20 赞5 条评论
我可能是做了假炉石
最近学了一下libSVM的基础用法，嗯，很基础的那种，原理什么的数学不太好真心不能手写一个啊，然后加上一个垃圾估值网络，我就可以开心的复（山）刻（寨）自己喜欢的游戏—…查看全文
兔兔
5 months ago
173 赞29 条评论
A*算法可视化
经常有人说，数据结构和算法抽象难以理解，尤其是一些涉及多种复杂结构的算法，初学者很难在脑内脑补算法的执行方式。因此我做了一款算法可视化应用。这样就可以直观地看电…查看全文
兔兔
8 months ago
237 赞9 条评论
C++定级赛 1：基本类型与变量
C++定级赛 1：基本类型与变量考试时间：120分钟。一、单向选择题（每题2分,共21题，共42分）1. 以下4个IO对象中，哪个IO对象的读（写）不经过缓冲，直接和标准输入（输出…查看全文
兔兔
9 months ago
26 赞21 条评论
C++Primer第5版学习笔记（六）
第六章的重难点内容第六章是和函数有关的知识，函数就是命名了的代码块，可以处理不同的情况，本章内容包括： 1.函数的概念基础，包括函数的定义声明以及函数如…查看全文
兔兔
9 months ago
5 赞1 条评论
C++Primer第5版学习笔记（四、五）
第四、五章的重难点内容因为第五章的内容比较少，因此和第四章的笔记内容合并。第四章是和表达式有关的知识，表达式是C++的基础设施，本章由三部分组成： …查看全文
兔兔
9 months ago
8 赞0 条评论
C++Primer第5版学习笔记（三）
第三章的重难点内容第三章字符串、向量和数组这篇笔记记录了我在学习C++常用基本语法的学习过程，基本只记录一些重难点，对概念的描述不是一开始就详尽和准确…查看全文
兔兔
9 months ago
6 赞1 条评论
A*寻路算法的探寻与改良（三）
A*寻路算法的探寻与改良（三）by:田宇轩第三分：这部分内容基于树、查找算法等对A*算法的执行效率进行了改良，想了解细化后的A*…查看全文
兔兔
10 months ago
11 赞0 条评论
A*寻路算法的探寻与改良（二）
A*寻路算法的探寻与改良（二）by:田宇轩第二部分：这部分内容主要是使用C语言编程实现A*，想了解A*算法的优化内容…查看全文
兔兔
10 months ago
8 赞2 条评论
A*寻路算法的探寻与改良（一）
A*寻路算法的探寻与改良（一）第一部分：这里我们主要探讨A*算法的基本概念和原理，对A*算法有一定了解的朋友们可以跳过并阅读稍后更新的其他部分1.1 前言这篇文章…查看全文
兔兔
10 months ago
74 赞12 条评论
C++Primer第5版学习笔记（一、二）
C++Primer第5版学习笔记（一、二）第一、二章的重难点内容这个笔记本主要记录了我在学习C++Primer（第5版，中文版）的过程中遇到的重难点及其分析。因为第一…查看全文
兔兔
a year ago
4 赞0 条评论
田宇轩编程的地方
开通专栏后，以后我的文章都迁移到这里啦。接下来的时间，这里将会展示一些有趣又实用的小东西的快捷开发流程。虽然我才疏学浅、哗众取宠，但是还是希望这次…查看全文
兔兔
a year ago
3 赞2 条评论

{"database":{"Post":{"21308771":{"title":"田宇轩编程的地方","author":"t.t.","content":"<p>       开通专栏后，以后我的文章都迁移到这里啦。</p><p>       接下来的时间，这里将会展示一些有趣又实用的小东西的快捷开发流程。虽然我才疏学浅、哗众取宠，但是还是希望这次能做出来大家都能用的好玩的东西，然后发在github（</p><p><a href=\"https://github.com/TiriSane\" class=\"\" data-title=\"https://github.com/TiriSane\" data-editable=\"true\">https://github.com/TiriSane</a></p><p>       Fight!!!!!</p>","updated":"2016-06-06T05:12:53.000Z","canComment":false,"commentPermission":"anyone","commentCount":2,"likeCount":3,"state":"published","isLiked":false,"slug":"21308771","isTitleImageFullScreen":true,"rating":"none","sourceUrl":"","publishedTime":"2016-06-06T13:12:53+08:00","links":{"comments":"/api/posts/21308771/comments"},"url":"/p/21308771","titleImage":"https://pic1.zhimg.com/6f5fdbfa9d5b3b571a4922077000b914_r.jpg","summary":"","href":"/api/posts/21308771","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":2,"likesCount":3},"21820756":{"title":"C++Primer第5版学习笔记（一、二）","author":"t.t.","content":"<strong>      C++Primer第5版学习笔记（一、二）</strong><br><strong>      第一、二章的重难点内容</strong><br><br><br><b> 这个笔记本主要记录了我在学习C++Primer（第5版，中文版）的过程中遇到的重难点及其分析。因为第一、二章都比较简单，因此这里合并这两章中我遇到的问题。</b><br><br><br><strong>       第一章 开始</strong><br><b> 这一章在第一部分之前，是一个helloworld式的章节，包含基本的函数，io流以及类的介绍。依靠这一章的内容可以创建第一个完整可被编译的cpp文件。</b><br><br><br><strong>      知识点1：P6，1.2，include指令（英文版7页）</strong><br>       通常情况下#include指令必须在所有函数之外。include和它想包含的头文件名字必须在同一行里，不然会报错。一般情况下我们把include指令放在源文件代码内容的最前面，这是因为inlcude起到声明的作用，我们想使用一个在头文件中声明的变量/函数/类等C++标准设施时，必须先包含头文件来对要使用的东西进行声明，之后才能够使用。当你在源文件中使用#include声明了一个头文件，效果相当于你把整个头文件黏贴到对应的那一行上。<p><br><br><strong>      知识点2：P19，1.5，文件重定向（英文版22页）</strong><br>      可以在windows下的cmd中或者mac，linux系统的终端窗口中用输入命令的形式执行程序并使它从一个文件中读入数据，再把标准输出改为输出到另一个文件里。<br>       如果我们编译好的程序为a.exe，程序需要输入两个整数，整数之间用逗号间隔，然后需要检测到EOF(End_Of_File,文件结束符)程序才会停止。这时为了文件重定向，我们可以新建一个文本文档（b.txt），接着我们在文档里记录”1,2“然后保存起来，保存后系统会在这个文件的末尾自动添加文件结束符。然后再新建一个空白文本文档（c.txt），使a.exe,b.txt,c.txt在同一个目录下。这时打开终端，转到这个目录，输入a &lt;b.txt&gt;c.txt回车确认。之后我们就实现了文件重定向了。<br>      但是cerr流的数据是不被缓冲的，因此没法把它们重定向到指定文件里。<br>       文件重定向主要依靠的是终端的命令提示符的行为，并不是C++语法中的一部分。<br>      （交叉引用：P23,第一章小结）cout和clog的内容都会先被存储到缓存区里面再被输出，因此你可以在缓存区被刷新之前，指定（重定向）它们输出的位置。而cerr是直接输出的，因此只能做标准输出，不能重定向。读cin，程序意外终止或者使用endl都会刷新缓存区。<br><br><strong>       第一章补充说明的内容：</strong>根据C++Primer这本书的设定，有一些书上的内容并非C++语法，但是在书中起到了辅助我们编程和理解概念的作用，这部分的内容在笔记里将成为补充的部分被记录下来。<br><strong> 1.关于练习的情景 假设</strong><strong>：</strong><br>       为了练习编写程序，C++primer这本书很多地方都用到了假定我们要编程处理一个书店的问题。并在此问题上慢慢扩展，最后实现这个书店的问题的编程。这个问题的假定是这样的：首先，书店程序将记录所有的交易记录。每条销售记录都会包含一下内容：ISBN号，用来记录本次交易的书的isbn号，isbn是书的唯一标识。之后，每条交易记录还含有本次交易的书的单价和销售本数。书店销售记录支持的操作包括查看书的销量，平均价格，计算每本书的销售额度，录入和读取每本销售记录等等。<br>        另外，我们能够对销售记录结构体进行的操作包括：读取书目的isbn号，把两个销售记录累加起来。输入输出一组交易记录。<br><strong>2.关于一些经常出现的词汇</strong><strong>：</strong><br>  当我们说类型的时候，其实是在说一个对象的属性，或者多个对象的共同属性。当我们在说对象的时候，往往是说按照类型分类存在的变量实体。比如a是b类型的对象。b是a的类型。这种说法会在学习C++的过程中被多次提到。C++默认的类型加上我们自己定义的类型有很多，我们可以把任何概念使用这门语言的类型等设施抽象到代码中。所以一切都是对象这种说法就指的是这种通过语言提炼事物的基本信息，并把这种可以量化的信息记录保存和抽象的特征。<br><strong>3</strong><strong>.IDE</strong><strong>：</strong><br>       IDE是指集成开发环境。如何使用代码生成可执行程序，如何在各个系统和各个系统的各种版本支持C++，怎样提供调试功能，这些点就是IDE解决的问题。基本上这部分的知识和C++语法没有关系，反过来，对C++和一些计算机知识了解的越多，就越能够理解IDE的各种功能和作用。因此，书中只是简单地提到了IDE的概念，关于如果下载，安装IDE，配置IDE或者使用IDE的特性不在此书的知识体系范围之内，应该另行学习使用IDE。因此书上只建议IDE应该选择起码支持C++11的版本。<br><strong>4</strong><strong>.回车键</strong><strong>：</strong><br> 不同的编程环境对按下回车键这个动作的处理是不一样的。通常我们只是想在控制台里敲入回车键来确认我们的输入，但是有的系统里也同时提供了一个回车键作为字符（换行符）输入。遇到一些复杂的情况回车键的使用可能导致未定义的行为。在第三章我们将看到，可以使用getline从输入流中读取换行符（回车）并抛弃它。因此，谨慎的使用回车键是很重要的。<br><strong>5</strong><strong>.进制转换和原反补码的概念</strong><strong>：</strong><br>      不同进制的手动转换和原码反码补码这些概念都是一般高校C++课程中的考察范围内概念，不过C++Primer这本书没有对此特殊说明，因此在这里特别地补充这些概念。<br><b>  5-1.</b>十进制整数转换为R进制整数。<br>       这里介绍<b>除R取余法</b>，要把数转换成哪个进制的数，R就是多少。这个方法把要转换为R进制的十进制整数不断除R，直到商为0为止，先计算出的余数就是被转化进制数的低位，后计算出的余数就是被转化进制数的高位。例如把10进制68转为二进制数，先68/2，得34，余0。因此对应的二进制数倒数第一位是一个0；34/2=17.......0，因此二进制数的倒数第二位也是0，17/2=8....1，倒数第三位是1；8/2=4.......0，倒数第四位是0；4/2=2.......0，因此倒数第五位是0；2/2=1......0，因此倒数第六位是0；1/2=0........1;商为0，停止这个过程，最高位为1.因此，对应的二进制数为1000100。完成进制转换。<br><b>5-2.</b>十进制纯小数转换为R进制纯小数。<br>       纯小数就是整数部分为0的小数。十进制纯小数可以不断乘R直到小数部分为0或者小数位数到达要求的精度对应的小数位数，这个方法也被叫做<b>乘R取整法</b>。比如把0.2135转化成对应的二进制数。首先0.3125*2=0.625。取整数部分0，这个0就是最高位。然后0.625*2=1.25。取整数部分1。剩下的部分是0.25，0.25*2=0.5，取整数部分0。0.5*2=1.0，取整数部分1。结果就是0.0101。<br>      综上所述，把一个整数部分不为0，小数部分也不为0的十进制数转化为R进制数只需要把这个数拆成整数部分为0的纯小数和小数部分为0的整数，分为转换并加在一起就行了。<br><b>5-3.</b>R进制数转化为10进制数。<br>       R进制数每一位乘R的数的权值次幂，得到的结果就是对应的十进制数，比如二进制数1101.11转换为10进制等于1*2^3+1*2^2+0*2^1+1*2^0+1*2^-1+1*2^-2。这个数就是十进制的13.75。<br><b>5-4.</b>二，八，十六进制的互相转换<br>       因为二、八、十六进制之间有内在联系，因此可以很方便的互相转换。每位八进制数相当于三位二进制数；每位十六进制数相当于四位二进制数字。因此，遇到一个二进制数转化为八/十六进制数，我们可以把这个二进制数划为3/4个数字一组的方式转换为对应的八/十六进制数字。比如有二进制数字1000100，把这个二进制数转化为八进制数。首先分组，3位数字一组。这个数就变成了001  000   100，每三个二进制数转为一个八进制数，100转为八进制是4，000转为八进制是0，001转为八进制数是1，因此这个数就相当于八进制的104。<br>       类似地，反过来每一个八/十六进制都是3/4个二进制数。比如十六进制的F7。首先7转为十进制是7，F转为十进制是15 。然后7转为四位2进制就是0111，15转为四位二进制数就是1111。合起来就是11110111。<br>      另外，数值在机器中的表示也是非常重要的，下面是有关概念的介绍：<br><strong>原码：</strong>把符号位化为0或者1，之后把符号位和数值的绝对值在一起编码，之后得到的编码就是原码。一般把正数的符号位设为0，负数的符号位设为1。对于一个纯小数，整数位为符号位。<br><strong>反码：</strong>正数的反码是它本身，负数的反码是它去掉符号位之后按位取反。<br><strong>补码：</strong>正数的补码是它本身，负数的补码是负数的反码加一。符号位参与运算。<br><br><b> 本章英语重点专业词汇：</b><br><br><br><b>    1.花括号                   curly brace</b><br><b>    2.内置类型                built-in type</b><br><b>    3.形参列表                parameter list</b><br><b>    4.字符串字面值常量   string literal</b><br><b>    5.操作符                   manipulator</b><br><b>    6.变量                      variable</b><br><b>    7.初始化                   initia</b><b>lize</b><br><b>    8.注释                      comments</b><br><b>    9.集成开发环境         Integrated Developed Environment,IDE</b><br><b>    10.条件                    condition</b><br><b>    11.赋值                    assignment</b><br><b>    12.表达式                 expression</b><br><b>    13.语法错误              syntax error</b><br><b>    14.方法（类方法）    method</b><br><br><br><br><strong>     第I部分：C++基础</strong><br><strong>      C++Primer的结构由</strong><strong>一个入门的开始章节和</strong><strong>四大部分组成，入门的开始章节上面</strong><strong>已经介绍完了，</strong><strong>这里介绍的是比较基础的第一部分，这部分共有六章。</strong><br><br><br><br><strong>       第二章  变量和基本类型</strong><br></p><p><strong>       第二章主要讲变量，变量类型，定义变量的各种情况和规则以及变量之间互相转换的规则。</strong></p><br><strong>       知识点2：P30，2.1.1，C++语言关于类型的规定（英文版32页）</strong><br>C++语言的基本类型的设定与硬件紧密相关，因此很多类型的内存尺寸也都只是给了一个范围，其实各家IDE（LLVM，GCC，Visaul C++）的实现都是在范围内，具体的实现细节都是不确定的。<br>       其中bool最小尺寸未定义，char最小尺寸是8位，wchar_t和char16_t的最小尺寸都是16位，char32_t的最小尺寸是32位，int的最小尺寸是16位，long和long long的最小尺寸分别是32位和64位，对于浮点型数据的表现尺寸是按照精度计算的，其中float的最小尺寸精度是小数点后6位(通常占内存32bytes)，double（通常占内存 64bytes）和long double(通常占内存 96~128bytes)的最小尺寸精度则是小数点后10位(实际可能比这个精度要大一些，比如float小数点后有效位为7，double为16)。int不得小于short,long不得小于int,long long不得小于long。float,double,long double也应该是精度递增（或者相同）的关系。要特别注意的是，扩展的字符类型(char16_t，char32_t，wchar_t)和布尔类型都没有带符号和无符号之分（尽管它们也确实属于算数类型）。<p><br><br><strong>知识点3：P32，2.1.2，类型转换</strong><strong>（英文版35页）</strong><br>       程序自动执行的类型转换操作发生在程序里IDE预期我们使用A类型但是实际上我们使用B类型的时候，B类型的对象会自动转换为A类型的，如果没法转换，程序就会报错。赋值操作中就可能发生这样的情况。<br>       我们先看赋值操作里表达式里面发生的自动转换，赋值操作A=B中，等号左边的A被叫做左值，B被叫做右值，程序期待事情是你给定的右值和左值类型完全相同。如果不相同，这里就会发生强制的类型转换，即把B的类型转化为A的类型。如果把一个超出左值类型表达范围的数赋值给左值，左值又是一个无符号类型，比如unsigned char c=-1;这时-1（整型，负的），右值会转化为无符号字符型，初始值对无符号类型表示数值总数取模，然后求余数，这个余数就是转化后的数。<br>       因为C++没有明确规定有符号类型的数应该如何表示，因此如果把一个超出左值类型表达范围的数赋值给左值，左值又是一个有符号类型，这种行为的结果是不一定的，因为C++标准委员会没有规定这样做之后到底会发生什么，因此各个IDE可能会有不同的实现。我们把这种不确定造成结果的行为叫做未定义行为。<br>       更详细的内容见第四章知识点9。<br><br><br><strong>知识点4：P36，2.1.3，转义序列</strong><strong>（英文版39页）</strong><br>       字符的转义序列可以为\\后面加上最多3个8进制数字（如果多于3个不会引发报错，多出的部分会被当成字符），或者\\x后面加上最多两个16进制数字（多出会报错）。数字转换成10进制后的大小不得超过字符集的限定范围。一般的字面值转义无此限制，不过，一般的字面值的类型是不确定的。10进制数字类型字面值会被转换为能够容纳这个数的带符号整数类型，其他进制中它们则会被转换为能容纳它们的占内存最小的类型的值。<br>      在最新的C++14标准中，数字字面值里还允许以0b或者0B开头，后面加上二进制数成为二进制字面值。如0B101，代表数字5；0b11，代表数字3。<br><br><br><strong> 知识点5：P55，2.4.1，const的引用和指针</strong><strong>（英文版62页）</strong><br>const是用来声明常量的标识符，<strong>代表我们不能够使用const后声明的变量名更改变量的值</strong>。如有前提const int i=32;，则之后给i赋值的语句就都是错误的。但是在int a=0;const int &amp;p=a;的前提下，给a赋值的语句却是正确的，因为a不被const修饰而声明，这仅仅意味着，我们不能够通过p这个名称更改p的实体——a的值。由此可见，我们允许把引用绑定到const对象上，但是必须用const int &amp;i=ci;这种形式，其中ci可以是也可以不是一个const对象，但是这个绑定操作之后i的值是不可更改的。<br></p><p>         对一个常量的访问也可以用指向常量的引用或者指向常量的指针实现，不同的是，指向常量的引用是常量的一个别名，不能够被赋值，不过指向常量的指针本身是一个对象，它的本身值可以更改，不过指向的对象的值不能够被更改。</p><br>        如果不想让指针指向的对象被更改，可以用const指针，int a=1;int *const p=a;这样指针本身的值不可以被改变但是它指向的对象的值是可以被改变的。如const int *const p=a;这种语句使指针本身和它指向的对象值都不会被改变。<br><br><br><strong>知识点6：P57，2.4.3，顶层const</strong><strong>（英文版64页）</strong><br>      顶层const是对const而言的，“顶层”可以用来修饰const状态的形容词。一个const使对象本身的值固定，这个const就被称为顶层const，一个const是对象指向或引用的对象成为固定值，这个const就被称为底层const。顶层和底层const对拷贝来说密切相关，有相同底层const资格的两个对象才能够互相拷贝，而且顶层const声明变量之后不允许再次改变const的值。int p,const int *a＝&amp;p;这种语句中的const就是底层const。<br><p>      像int v1=9;const int *p=&amp;v1;int *p2=p;这种语句如果能够通过编译，那么我们就可以使用p2的性质改变p1指向的常量的值，但是常量的值是不能够被改变的，因此这种变相改变常量的值的表达式都是错误的。可以通过分析const级别得到表达式中常量是否被更改，从而判断语句的正确性。</p><br>      说到底，顶层底层说的是对拷贝控制的约束。总的规则就是“不能改变常量的值”。因此“拷入和拷出的对象都要有相同的底层const资格，或者两个对象数据类型必须能转换”，例如，有int *p1,const int *p2;。p1没有底层const,p2有底层const。p1=p2;这时const int*不能转换成int *(如果转换，就违反了“不能改变常量的值这一约束条件”)，因此p1=p2;不合法。p2=p1;int * 能够转换成const int *,因此p2=p1合法。<br><br><br><strong>知识点7：P58，2.4.4，constexpr</strong><strong>（英文版65页）</strong><br><p>      我们在了解constexpr之前，应该先了解常量表达式。所谓常量就是固定的量，那么常量表达式就是值固定不变的表达式，这里“值固定不变”，指的是程序编译阶段，常量表达式的值就能被确定下来之后也不能对其进行任何种方式的修改。因此这个固定，是编译之后固定的。像cout&lt;&lt;1234&lt;&lt;endl;中的1234，就是常量表达式，显然，字面值是常量表达式。</p><br>       constexpr的作用之一就是帮助程序员在IDE的提示下查看一个赋值语句是不是常量表达式。使用的方式包含在声明语句里面，形如constexpr 变量类型 变量名=右值;如果右值是一个常量，这条语句就是正确的。在所有函数体外声明的全局变量的地址就符合“在编译期间能确定，编译后值不被改变”这两个条件，因此也属于常量。<br>    另外，用constexpr声明的指针(比如，constexpr int *p=&amp;v1;中的*p，相当于int *const p=&amp;v1;   )都是顶层const，即指针本身值固定。但是指针指向的内容是可以变的。引用也一样。<br> 当你使用constexpr定义引用变量的时候，这个变量引用的对象只能是全局基本数据类型（引用类型除外的）变量（因为要求的内存地址必须是固定不变的）。constexpr引用的结果和正常的引用的结果是一致的，因为引用本身就是固定不变的，因此相当于顶层const修饰的constexpr对引用类型类说没有特殊的意义。  <br><br><strong>知识点8：P61，2.4.4，类型别名</strong><strong>（英文版68页）</strong><br>使用typedef int zhengxing;这种对简单的类型名进行替换的方式无疑是非常直观并且好理解的，但是在涉及到复杂的类型名的时候往往会出现各种各样的问题。比如typedef char *Pstring;这条语句是不是就意味着我们看到Pstring就可以用char *替换呢。其实并不是，实际上类型别名不只是替换的规则，而是要复杂很多。比如我们遇到const Pstring a;的时候，按照替换的规则，这条语句就相当于const char * a;这里的const这种情况下是底层const，但是结果并不是这样的，这条语句正确的等同语句应该是char *const a;是一个顶层const，即指针本身是一个常量。让我们来分析一下为什么是这个样子，而不是简单的替换就行了。typedef char *Pstring；这条语句就是说Pstring是一个类型别名，它是什么类型的类型别名呢？Pstring是 <strong>指向char的指针的类型别名</strong> ，也就是说，这个类型修饰的对象必须是一个指针，<strong>这个指针也必须指向char而不能指向别的什么东西，比如，不能指向const char</strong>。我们再看看const Pstring a;这个语句，首先a一定是指向char的指针。所以这个前面的const应该是用来修饰这个指针本身。也就是说，这个指针是常量指针而非指向常量的指针。这一点非常重要。const char * a这个语句里面，实际上类型是const char，*是声明符的一部分。我们说过，定义一个变量由两部分组成，类型名和声明符，声明符可以是*或者&amp;加上变量名的形式。而类型别名只是给类型一个别名，至于声明符是怎样的，不在它修饰的范围内。因此在有const的情况下，就可以看出来这两者之间的区别还是很明显的。<br><br><br><strong>知识点9：P61，2.5.2，auto和decltype类型声明/指示符</strong><strong>（英文版69页）</strong><br>      auto变量通过初始化语句，计算出右值的类型，并推导出左值的类型。这个过程中auto将会忽视顶层const和引用类型，可用const auto &amp;a=i;这种方式显式地指出了：指出要推导的结果是带顶层指针属性的或者是引用属性的。auto推导多个值时，这些值的类型必须是一样的。因为auto是利用初始化赋值，因为此它的行为基本上也和初始化有关。<br>       decltype不通过计算，只通过推算出变量应有的值，表达式本身应有的值和函数的返回值来推导类型。对于变量类型，decltype保留顶层const和引用的属性。对于表达式，解引用表达式(如:int i=1;   int *p=&amp;i;    decltype (*p) a=i;中的*p,对p解引用是int &amp;类型的)和带括号的表达式，（如：decltype ((a+1)) c=i;）的结果都将是引用类型。因为decltype通过处理表达式得到结果，因此更详细的内容在第四章将会被提到。有的表达式返回左值，有的表达式返回右值，返回左值的表达式在decltype类型推导下得到的将是引用的结果。<br><br><br><strong>     知识点10：P65，2.6.1，用关键字struct自定义数据结构</strong><strong>（英文版73页）</strong><br>      使用struct关键字定义类的形式如struct 类名｛数据成员类型1  数据成员名1；数据成员类型2  数据成员名2；｝；C++11规定可以给类内成员提供类内初始值用于初始化用我们自定义类创建的对象实例中的成员的值。形式如下：<br>struct MyClass<br>{<br>     int student=0;<br>     float numbers=1;<br>};<br><br><br><strong>       第二章补充说明的内容：</strong><br><strong>       1.对于已知的类型范围的编程假定：</strong><br>       为了很多情况下我们都会默认我们开发机的一些环境就是客户机的使用环境。因为类型本身是依赖于机器的，因此这里也应该使用固定的类型值比如int32_t类型。另外，使用防越界溢出的良好编程风格也对程序有很大帮助。使用C++语言编程时，可以执行仍然是我们需要时刻考虑的问题。<br><strong>       2.不同语境下对象这个词的不同含义：</strong><br>      通常情况下对象指一块能存储数据的内存空间，但是当我们想区分命名的对象和未命名的对象的时候，通常把命名了的对象叫做变量，相应地，这时并列提出的对象可能指的是普通的内存区间；当我们区分对象和值的时候，又衍生出来了左值和右值的概念（第4章），这时会把对象所具有的属性作为对象，对象本身的内容作为值的说法被表述。因为一切都可以叫做对象，所以这是一个意义广泛的概念。通常交流中我们想表达具体的概念的时候也会使用对象这个词汇来表达我们的想法。但这时候要联系上下文和语境来猜测这个表达出来“对象”究竟指的是什么。<br><strong>       3.关于extern：</strong><br>       extern外部变量声明其实是在IDE进行编译的时候告诉IDE，这有一个外部变量你要去别的地方找。因此我们应该掌握编译链接这套流程才能够更加方便的会用extern。假设有一个头文件a.h，这个头文件里面定义了int aaa=0;还有一个源文件b.cpp。这个b.cpp里面使用了extern int aaa;这样的语句，那么这个b.cpp是编译不了的。因为头文件如果不被别的源文件引用，是不参与被编译为obj的过程的，一旦它不参与这个过程，它里面声明的aaa这个全局变量其实就不存在，因此在b.cpp里面外部生命一个不存在的变量自然就是非法的。另外，使用extern也要和static做区分并考量它在别的文件中会不会造成内存污染等问题。这里应该掌握分离式编译的编译和链接特性再使用extern比较好。<br><br><b> 本章英语重点专业词汇：</b><br><br><br><b>  1.算数类型                  arithmetic type</b><br><b>  2.整型                        integarl type</b><br><b>  3.转换                        convert</b><br><b>  4.不可打印                  nonprintable</b><br><b>  5.转义序列                  escape sequence</b><br><b>  6.类型说明符               type specifier</b><br><b>  7.分离式编译               separate compilation</b><br><b>  8.声明                        declaration</b><br><b>  9.声明符                     declarator</b><br><b>  10.静态类型                statically typed</b><br><b>  11.类型检查                type checking</b><br><b>  12.标识符                    identifier</b><br><b>  13.内层作用域             inner scope</b><br><b>  14.复合类型                compound type</b><br><b>  15.左值引用                lvalue reference</b><br><b>  16.预处理                   preprocessor</b><br><b>  17.临时量                   temporary</b><br><b>  18.指向常量的指针      pointer to const</b><br><b>  19.常量指针                const pointer</b><br><b>  20.字面值类型             literal type</b><br><b>  21.类型别名                type alias</b><br><b>  22.类内初始值             in-class initializer</b><br><b>  23.预处理器                preprocessor</b><br><b>  24.头文件保护符          header guard</b>","updated":"2016-08-01T10:28:48.000Z","canComment":false,"commentPermission":"anyone","commentCount":0,"likeCount":4,"state":"published","isLiked":false,"slug":"21820756","isTitleImageFullScreen":false,"rating":"none","sourceUrl":"","publishedTime":"2016-08-01T18:28:48+08:00","links":{"comments":"/api/posts/21820756/comments"},"url":"/p/21820756","titleImage":"https://pic4.zhimg.com/0dfde4b61345066149e2c42d02bb7893_r.png","summary":"","href":"/api/posts/21820756","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":0,"likesCount":4},"23199073":{"title":"A*寻路算法的探寻与改良（一）","author":"t.t.","content":"<h1><strong>A*寻路算法的探寻与改良（一）</strong></h1><br><br><h3><strong>第一部分：这里我们主要探讨A*算法的基本概念和原理，对A*算法有一定了解的朋友们可以跳过并阅读稍后更新的其他部分</strong></h3><br><strong>1.1 前言</strong><br>       这篇文章原来属于我的数据结构课设内容。<br><p><strong>1.2 A*算法要解决的问题</strong></p><p>      我们可以通过先了解A*算法解决的问题来了解A*算法的概念。A*是一种用于寻路的算法，现在我们给计算机一张地图，标记了哪些地方能走，哪些地方不能走，然后告诉计算机起点A和终点B，计算机自动计算出一条从A点到B点的最短路径，我们的问题就解决了。A*算法就是用于快速解决这类问题的方法。</p><p>      让我们先用抽象的方法看这个问题，首先，解决这类问题的前提条件有以下两个：</p><p>      第一个条件是，<strong>地图必须是事先设计好的</strong>（这里重点内容会用黑体mark一下，后同）。也就是说地形、各点的位置等地图的属性是固定不变的，这种地图不能前一秒里面还有一条河，后一秒同样位置就没有这条河了。本着抽象的原则，我们把这种有固定属性的地图叫做<strong>静态路网</strong>。因此，A*是一种基于静态路网的寻径算法。</p><br><br>      使用A*的第二个条件是，<strong>已知起点和终点。</strong>在一些RPG游戏中，经常会有游戏迷宫这种设定，在游戏迷宫中，玩家只能确定自己的位置（仙剑3的一些迷宫里，因为有传送的概念，玩家甚至不能确定自己的位置），但是玩家并不知道迷宫的终点在哪里，这种情况下用A*算法是不合适的。因此，A*算法需要知道起点和终点才能求出最优路径。<br><br>      符合这两个条件的问题，就是我们可以尝试用A*算法解决的问题。和你预料的一样，A*算法被广泛应用在游戏编程之中。<br><p><strong>1.3 A*算法的寻路思路</strong></p><p><strong>1.3.1 设定和定义地图、地貌、起点和终点</strong></p><p>      了解了A*算法的概念之后，我们来看看A*算法是怎么解决寻路这个问题的。</p><p>      首先，我们给计算机一张地图的同时，我们也要给计算机一个处理地图的方式。在A*中，处理地图的思想就是让计算机把一张大地图看成是由大小相等的格子拼出来的结构，这些格子都不可再分割成更小的格子，它们是地图上的最小完整单位。我们事先把每个格子的状态在电脑中标记起来，比如这个格子的地形不可通过，我们就打上一种标签；如果这个格子能通过，但是由于现实地形的原因（比如，这条路比较坎坷），这个格子就被打上另一种标签（比如：”难以通过的格子”）；如果这个格子对应的地形一马平川，这个格子的标签可以换成\"可以通过的格子\"。</p><p>      好的，读到这里，我们大概能知道地图是怎么在A*算法中被处理的了，还是基于抽象的思想，我们可以得出重要的两种结构：</p><p><strong>1.地图</strong></p><p>      地图由有各种属性的格子组成。</p><p><strong>2.格子</strong></p><p>格子的基本属性包括以下两点：</p><p>     （1）.格子在地图中的位置，即<strong>坐标</strong>。要保证现有的格子足以描述一片完整的区域，因此这个坐标应该是连续的而非离散的。</p><p>     （2）.格子的“路况”，就是上面我们说的那些标签，不同的标签代表不同的格子内路况，每次寻路如果格子内相对路况更差，我们就会尽量绕开它，其实路况有很多种，这么多种类用标签分类，其实是不太靠谱的，这里我们直接<strong>量化这些不同的格子内路况，</strong>比如地形越难通过，相应地就设定一个更大的值（比如，999），地形越容易通过，就设一个更小的值。在A*算法里，我们把这种值叫做<strong>“权”</strong>，或者权值，它量化地直观体现了每个格子的路况。</p><p>      在设定好地图组成的基础上，只要再设定好哪个格子是起点，哪个格子是终点，我们就可以考虑怎么找一条<strong>最优路径</strong>了。</p><p><strong>1.3.2 BFS（Breadth First Search，广度优先搜索）和DFS（Depth-First-Search，<strong>深度优先搜索算法</strong>）</strong></p><p>      在思考怎么寻找最优路径之前，应该先定义什么叫做最优路径，最优路径不只是A与B的距离最短，还要求我们权衡经过的路径权值尽量的低，权值越低的路径就意味着越适合的路线。这里，我们把起点到终点经过格子用的长度和一路格子的权值之和一起考虑，我们设这种衡量路线是否最优的标准叫<strong>“代价”</strong>，计算最优路径，其实就是计算代价最小的路径。因此，A*算法的重点就是如何<strong>评估代价。</strong></p><p>      对于从A点到B点的寻路方法，可能最容易被想出来的就是，列举出所有从A到B的路径，并逐个计算每个路径需要的代价，量化代价值，挨个比较，这样就很容易看哪个路径最短了，其实这是种“笨方法”，因为可能地图比较大，格子比较多，起点A到终点B距离很远，所以逐一列举出来A到B的路线，逐一计算显然需要很高的时间/空间复杂度（对于数据结构中的一些百度一下就能理解的基础概念，这里用深绿色标明，本文不加解释，下同）,不是好的算法。这有点像网络安全中的暴力破解，一个密码锁有三位数，000~999，挨个数尝试解锁最多用999次不断尝试，就能知道正确密码，但这种方法显然不如社工密码锁主人或者用生日什么的做线索数字去试高效。</p><p>      虽然这种逐步寻径的方法并不高效，但是A*算法的思路融合了这两种方法，因此，在学习A*之前掌握BFS和DFS还是很重要的。BFS以起点A为圆心，先搜索A周围的所有点，形成一个类似圆的搜索区域，再扩大搜索半径，进一步搜索其它没搜索到的区域，直到终点B进入搜索区域内被找到。整个搜索过程就像下面的图1.3.2.1一样。</p><img src=\"v2-8f8577e2c31c1b7fab08a5f5e7eaa5e8.png\" data-rawwidth=\"526\" data-rawheight=\"376\"><p>图1.3.2.1—BFS搜索终点</p><p>    图中，粉色的点是起点A，紫色的点是终点B，颜色为灰色的色块代表未检索区域，蓝色/蓝黑色的色块代表已经检索了的区域，颜色越黑的色块代表地图上越先被BFS搜索的格子。从图中我们可以看出，BFS尽可能把更多的格子纳入搜索区域，并总是能找到A与B之间的最佳路径（如果存在这么一条路径的话）。但是DFS寻找终点的思路就和BFS不同，BFS尽量遍历A周围的区域，DFS则是让搜索的区域离A尽量远，离B尽量近，比如现在你在一个陌生的大学校园里，你知道校门口在你的北方，虽然你不知道你和校门口之间的路况如何，地形如何，但是你会尽可能的往北方走，总能找到校门口。DFS的搜索过程就像下图1.3.2.2这样：<br></p><img src=\"v2-f74e6b11c6b580837d99f59e979cd961.png\" data-rawwidth=\"526\" data-rawheight=\"376\"><p>图1.3.2.2—DFS搜索过程</p><p>    可以清楚地对比出来，比起BFS，DFS因为尽量靠近终点的原则，其实是用终点相对与当前点的方向为导向，所以有一个大致的方向，就不用盲目地去找了，这样，就能比BFS能快地找出来最短路径，但是这种快速寻找默认起点A终点B之间没有任何障碍物，地形的权值也都差不多。如果起点终点之间有障碍物，那么DFS就会出现绕弯的情况。见图1.3.2.4：</p><p><img src=\"v2-faa7aea09449a87eba4f5a5fe91b7797.png\" data-rawwidth=\"526\" data-rawheight=\"376\">图1.3.2.4—DFS一直向右下角搜索，但由于被挡住去路，因只能绕了一个大圈</p><p>     图中DFS算法使电脑一路往更右下方的区域探索，可以看出，在DFS遇到障碍物时，其实没有办法找到一条最优的路径，只能保证DFS会提供其中的一条路径（）如果有的话。</p><p>     大概了解了BFS和DFS，对比这两者可以看出来，BFS保证的是<strong>从起点到达路线上的任意点花费的代价最小</strong>（但是不考虑这个过程是否要搜索很多格子）<strong>；</strong>DFS保证的是<strong>通过不断矫正行走方向和终点的方向的关系，使发现终点要搜索的格子更少</strong>（但是不考虑这个过程是否绕远）。</p><p>A*算法的设计同时融合了BFS和DFS的优势，既考虑到了从起点通过当前路线的代价（保证了不会绕路），又不断的计算当前路线方向是否更趋近终点的方向（保证了不会搜索很多图块），是一种静态路网中最有效的<strong>直接搜索算法</strong>（会在稍后的文章中提到不直接搜索地图的寻路方式）。</p><br><p><strong>1.3.3 A*算法的估价思想</strong></p><p>计算机上的事物，一定是先要量化，然后再计算的，这是一种抽象的过程。在BFS中，越接近起点的格子的代价越低，越远离起点的格子的代价越高。每次搜索，都是在尚未搜索的范围中寻找他们之间更接近起点的格子来进行搜索；在DFS中，越接近终点的格子代价越低，离终点越远的格子的代价越高。如果要融合这两种方法，我们应该怎么对每个格子估值呢？</p><p>     在A*中，每个格子的估值（估值了这个格子代价）是由两部分组成的，一部分是这个格子距离起点的距离，我们记作<strong>G</strong>，另一部分是这个格子距离终点的距离，这种距离，我们记作<strong>H</strong>。注意，<strong>这里的距离不是指直线距离</strong>，G指的是从这个格子的起点到达这个格子一共花费的距离，H指的是估算一下从这个格子到终点将会用多少距离，我们可以看出来，我们事先并不知道这个格子到终点的花费，因此，我们必须找一种方法估算当前点与终点的距离，这种估算的方法，我们称为<strong>启发式算法</strong>，A*的估价思想就是用量化G值和F值（其实就是求出每个要搜索格子的这两个值），然后加在一起，它们的和就是这个格子的估值（或者叫做代价），这里我们把他们的和记作<strong>F</strong>。很好，我们现在就可以得出A*算法中计算格子代价的公式：<strong>F=G+H.</strong>F，G，H也都是格子的属性，让我们把这三个参数添加到格子的性质中去。</p><p>通过这个公式，求出搜索的每个格子的权值，然后每次都选择代价更小的格子，这样，我们就能得出一条最佳路径。这就是A*算法的估价思想。</p><p><strong>1.4 A*算法的描述</strong></p><p>     以下是对A*算法的完整概括：</p><p>     1，找到起点对应的格子，并把起始格添加到开启列表里。开启列表是一个用于记载我们待处理格子的列表。（蓝色用于写注释，下同）</p><p>     2，重复如下的工作：</p><p>      a) 寻找开启列表中F值最低的格子。我们称它为<strong>当前格</strong>。</p><p>      b) 把当前格从开启列表中删除，放到关闭列表里面。关闭列表是一个用于记载我们已经处理过的处理格子的列表。</p><p>      c) 对当前格的每一个相邻格子，分三种情况进行操作：</p><p>          * 如果它不可通过或者已经在关闭列表中，略过它。反之如下。</p><p>          * 如果它不在开启列表中，把它添加进去。把当前格作为它的父节点。记录这一格的F,G,和H值。父节点用于记载当前格子是哪个格子的相邻格。</p><p>          * 如果它已经在开启列表中，就说明我们之前已经访问过了这个格子，现在我们又遇到了它，说明可以通过这个格子的父节点直接到达当前格，这种情况下进一步说明至少有两种方式到达这个格子，因此我们必须知道哪种方式到达这一格更好，才能进行下一步操作。</p><br><br>          为了知道哪种方式更好，我们假设当前点是这个格子的父节点，然后计算这个节点的G值，然后比较我们刚计算出来的G值是否比原来的G值（因为这个格子如果在开启列表，就说明已经有了父节点和求好的G值），更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。<br><br>      d) 停止，当你<br>          * 把目标格添加进了关闭列表，这时候路径被找到，或<br>          * 没有找到目标格，开启列表已经空了。这时候，路径不存在。<br><br>      这就是今天归纳出的A*算法的寻路过程，在下一篇文https://zhuanlan.zhihu.com/p/23199758中，我将用C语言实现它，并进一步阐释A*算法的执行逻辑。","updated":"2016-10-25T09:40:15.000Z","canComment":false,"commentPermission":"anyone","commentCount":12,"likeCount":74,"state":"published","isLiked":false,"slug":"23199073","isTitleImageFullScreen":false,"rating":"none","sourceUrl":"","publishedTime":"2016-10-25T17:40:15+08:00","links":{"comments":"/api/posts/23199073/comments"},"url":"/p/23199073","titleImage":"https://pic1.zhimg.com/v2-8f8577e2c31c1b7fab08a5f5e7eaa5e8_r.png","summary":"","href":"/api/posts/23199073","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":12,"likesCount":74},"23199758":{"title":"A*寻路算法的探寻与改良（二）","author":"t.t.","content":"<h1><strong>A*寻路算法的探寻与改良（二）</strong></h1><p><strong>by:田宇轩                                                     </strong></p><br><br><strong>第二部分：这部分内容主要是使用C语言编程实现A*，想了解A*算法的优化内容的朋友们可以跳过这部分并阅读稍后更新的其他内容</strong><br><strong>2.1 回顾</strong><br><p>       在我的上一篇文章中，我们通过抽象的思维方式得出了A*算法的概念和原理，这一章内容中主要探讨如何用编程实现A*算法。</p><p>       在数据结构与算法的学习中，每个算法都应该结合一定的数据结构在计算机中存储，然后用对应的函数操控这些数据结构，A*算法也不例外，从上一篇文章中，我们知道，A*算法需要：</p><p>（1）<strong>地图</strong>，这是一个存储静态路网的结构，由格子组成</p><p>（2）<strong>格子</strong>，格子是组成地图的基本单位，每个格子都有<strong>坐标，F，G，H，父节点</strong>这五种属性；</p><p>（3）<strong>开启列表</strong>，用于记录等待处理的格子；</p><p>（4）<strong>关闭列表</strong>，用于记录已经处理的格子；</p><p>（5）<strong>起点和终点</strong>，用于接受用户输入指定哪个点为起点，哪个点为终点；</p><br>       这些存储结构都是A*算法需要的，其实为了实现A*算法，我们还需要更多的存储结构，这些结构我们将会在用到的时候抽象出来的。弄清思路之后，我们先用C语言定义一下这些结构，如果您是其他语言的使用者，也可以按照这些结构的描述用其他语言的定义和实现。下面就是C语言对A*所需结构的实现，下面这段代码可以单独定义在一个头文件中，拥有全局作用域，其实让这些代码拥有全局作用域的方式我们并不提倡，这里只是方便教学和理解用。<br> 1 #define MAX_number 5   //这是地图的最大值，可以自己修改以符合实际需求<br> 2 <br> 3 //一个比较基础的结构体，用于和地图联动<br> 4 struct baseNode<br> 5 {<br> 6     int i;<br> 7     int j;<br> 8     int weigt;<br> 9 <br>10     int f;<br>11     int g;<br>12     int h;<br>13 <br>14     struct baseNode *father;<br>15 };<br>16 <br>17 //定义了一个全局变量用来存储二维矩阵地图<br>18 struct baseNode map[MAX_number][MAX_number];<br>19 <br>20 //记录起点和终点的数组，起点为Ascenery[0],终点为Ascenery[1]<br>21 struct baseNode AsceneryList[2];<br>22 <br>23 //开启列表，用于A*算法<br>24 struct baseNode OpenList[MAX_number*MAX_number];<br>25 <br>26 //关闭列表，用于A*算法<br>27 struct baseNode CloseList[MAX_number*MAX_number];<br>28 <br>29 //用于记录开启列表中元素的个数<br>30 int openListCount = 0;<br>31 <br>32 //用于记录关闭列表中元素的个数<br>33 int closeListCount = 0;<br><p>代码2.1.1—A*的基本存储结构</p><p><strong>2.2 A*算法的流程</strong></p><p><strong><strong>2.2.1 设计代码体系结构</strong></strong></p><br>      为了方便用户输入和输出，也方便我们直观地看到A*的结果，在代码结构上，我们准备设计三个头文件：<strong>data.h</strong>，用于存储A*依赖的结构，<strong>func.h</strong>，用于写一些功能，<strong>process_control.h</strong>，用于显示一个简单的用户界面，控制用户流程，识别用户的输入是否在合法范围内，最后，我们用<strong>main.c</strong>调用所有这些内容。主函数很简单，这里先写出来：<br>1 #include \"process_control.h\"<br>2 <br>3 int main()<br>4 {<br>5     testStart();<br>6 <br>7     return 0;<br>8 }<br><p>代码2.2.1.1—主函数</p><p><strong>2.2.2 流程控制函数</strong></p><br>      我们把前面定义的存储结构写在了data.h里面。然后我们稍微设计一下控制流程的process.h。这是main.c唯一引用的头文件，里面包含一个testStart函数。<br> 1 #pragma once<br> 2 <br> 3 #include \"funcs.h\"<br> 4 <br> 5 //用于控制整个校园导航系统流程<br> 6 void testStart()<br> 7 {<br> 8         //flag用于辅助程序判断有没有足够条件执行各功能<br> 9     int flag1 = 0, flag2 = 0;<br>10 <br>11         //不断的让用户选择菜单<br>12     for (;;)<br>13     {<br>14         printf(\"基于A*算法的校园导航系统程序\\n\\n\");<br>15 <br>16         printf(\"你可以进行以下操作：\\n\");<br>17         printf(\"1.设定校园地图地形\\n\");<br>18         printf(\"2.设定寻径的起点和终点\\n\");<br>19         printf(\"3.找出最佳路径\\n\");<br>20         printf(\"0.退出系统\\n\\n\");<br>21 <br>22                 //让用户输入自己的选择<br>23         int userInput = 0;<br>24         scanf(\"%d\", &amp;userInput);<br>25 <br>26                //根据自己的选择分别执行inputmap,setroad,Astar三个函数<br>27         switch (userInput)<br>28         {<br>29         case 1:<br>30             inputmap(); <br>31             flag1 = 1;<br>32             printf(\"设定校园地图地形成功\\n\\n\");<br>33             break;<br>34 <br>35         case 2:<br>36             if (flag1 == 1)<br>37             {<br>38                 setRoad();<br>39                 flag2 = 1;<br>40                 printf(\"起点终点设定完毕\\n\\n\");<br>41             }<br>42             else<br>43             {<br>44                 printf(\"请先完成地图设定\\n\");<br>45             }<br>46             break;<br>47 <br>48         case 3:<br>49             if (flag1 == 1&amp;&amp;flag2==1)<br>50             {<br>51                 Astar();<br>52                 printf(\"寻径完毕\\n\\n\");<br>53             }<br>54             else<br>55             {<br>56                 printf(\"请先完成地图、起点终点设定\\n\");<br>57             }<br>58             break;<br>59 <br>60         case 0:<br>61             exit(0);<br>62             break;<br>63 <br>64         default:<br>65             printf(\"输入不在指定范围内，请重新输入\\n\\n\");<br>66             break;<br>67         }<br>68     }<br>69 }<br><p>代码2.2.2.1—流程控制函数</p><p><strong>2.2.3 设定地图样式的函数inputmap和设定起点终点的函数setroad</strong></p><br><br>让我们先设定好地图再进行A*算法本体的编写，这部分没有什么难度，因此也不先写伪代码和分析逻辑了，对此不感兴趣的朋友可以直接往后看Astar函数的实现。<br> 1 #pragma once<br> 2 <br> 3 #include &lt;stdio.h&gt;<br> 4 #include &lt;stdlib.h&gt;<br> 5 #include &lt;string.h&gt;<br> 6 #include &lt;math.h&gt;<br> 7 #include \"data_define.h\"<br> 8 <br> 9 //设定地图的函数<br>10 void inputmap()<br>11 {<br>12     printf(\"目前地图大小为%d * %d。\\n\",MAX_number,MAX_number);<br>13     printf(\"请通过输入整数的形式填充地图，0代表地形不可通过，\\n其他正整数代表权值，权值越大，地形越不方便通过\\n\\n\");<br>14 <br>15     for (int i = 0; i &lt;MAX_number; ++i)<br>16     {<br>17         for (int j = 0; j &lt; MAX_number; ++j)<br>18         {<br>19             scanf(\"%d\", &amp;map[i][j].weigt);<br>20 <br>21             map[i][j].i = i;<br>22             map[i][j].j = j;<br>23         }<br>24         printf(\"第%d行输入完毕,共%d行\\n\\n\",i+1,MAX_number);<br>25     }<br>26 }<br>27 <br>28 //设定起点和终点的函数<br>29 void setRoad()<br>30 {<br>31     int i = 0, j = 0, p = 0, q = 0;<br>32 <br>33         printf(\"地图坐标从【1，1】开始\\n\");<br>34         printf(\"请输入起点的横坐标:\\n\");<br>35         scanf(\"%d\", &amp;i);<br>36         printf(\"请输入起点的纵坐标:\\n\");<br>37         scanf(\"%d\", &amp;j);<br>38 <br>39         AsceneryList[0].i = i - 1;<br>40         AsceneryList[0].j = j - 1;<br>41 <br>42         printf(\"请输入终点的横坐标:\\n\");<br>43         scanf(\"%d\", &amp;p);<br>44         printf(\"请输入终点的纵坐标:\\n\");<br>45         scanf(\"%d\", &amp;q);<br>46 <br>47         AsceneryList[1].i = p - 1;<br>48         AsceneryList[1].j = q - 1;<br>49 <br>50 }<br><p>代码2.2.3.1—设定地图样式和起点终点的函数</p><p><strong>2.2.4 Astar函数的设计</strong></p><p> 由于Astar算法需要对每个点的邻居都分析其F值，而且这里我们用二维矩阵来设定地图，因此一个格子最多有8个邻居格子，为了一一处理这些邻居格子，我们设计一种大小为8的邻居数组，用循环从邻居数组的第一个元素处理到邻居数组的最大第八个元素。邻居数组定义如下：</p><br><code lang=\"text\">1 //邻居列表，用于记录每个当前点的所有邻居2 struct baseNode Neibo[8];\n3 \n4 //用于记录邻居的个数5 int neibNum = 0;\n</code><p>代码2.2.4.1—邻居列表的定义</p><p>     接下来我们按照上前文章总结的流程编写一个代码框架，先不实现各个函数的具体功能。先回顾一下上一篇文章的A*寻路流程：</p><p>2.2.4.1—A*寻路流程</p><br><br>       复习了流程之后，我们就可以按照流程上面的大致打一个框架：<br> 1 //假设我们预先把起点放入迭代器iter，终点设为ender<br> 2 //把起点放入开启列表<br> 3     putInOpenList(iter);<br> 4 <br> 5     //当开启列表为空或者终点在关闭列表中，结束寻径<br> 6     for (;  openListCount != 0 &amp;&amp; isInCloseList(ender)==0;)<br> 7     {<br> 8         //取出开启列表中f值最小的节点（之一），并设为iter（当前点）<br> 9         iter = readTopOpenList();<br>10 <br>11         //把当前点从开启列表中删除<br>12         outOpenList(iter);<br>13 <br>14         //把当前点记录在关闭列表中<br>15         putInCloseList(iter);<br>16 <br>17         //把当前点的邻居加入邻居列表<br>18         addNeibo(iter);<br>19 <br>20         //对于每个邻居，分三种情况进行操作<br>21         for (int i = 0; i &lt; neibNum; ++i)<br>22         {<br>23             //如果这个邻居节点不可通过，或者这个邻居节点在关闭列表中，略过它<br>24             if (Neibo[i].weigt==0 || isInCloseList(Neibo[i]))<br>25             {<br>26             }<br>27             //如果这个邻居节点已经在开启列表中<br>28             else if(isInOpenList(Neibo[i]))<br>29             {   //看看以当前格子为父节点，算出来的新G值是不是比原来的G值小，如果更小，就改变这一格的父节点，G值，重新计算F值<br>30                 if (NewG(Neibo[i],iter)&lt;Neibo[i].g)<br>31                 {<br>32                     map[Neibo[i].i][Neibo[i].j].father = &amp;map[iter.i][iter.j];<br>33                     map[Neibo[i].i][Neibo[i].j].g = map[iter.i][iter.j].g + increment(Neibo[i]);<br>34                     map[Neibo[i].i][Neibo[i].j].f = map[Neibo[i].i][Neibo[i].j].g + map[Neibo[i].i][Neibo[i].j].h;<br>35                     //把这一格的旧记录从开启列表删除，把更新后的这一格的值加入开启列表等待处理<br>36                     outOpenList(Neibo[i]);<br>37                     putInOpenList(Neibo[i]);<br>38                 }<br>39             }<br>40             //如果这个邻居节点不在开启列表中<br>41             else<br>42             {<br>43                 map[Neibo[i].i][Neibo[i].j].father= Neibo[i].father = &amp;map[iter.i][iter.j];<br>44                 map[Neibo[i].i][Neibo[i].j].g = map[iter.i][iter.j].g + increment(Neibo[i]);<br>45                 map[Neibo[i].i][Neibo[i].j].f = map[Neibo[i].i][Neibo[i].j].g + map[Neibo[i].i][Neibo[i].j].h;<br>46 <br>47                 Neibo[i] = map[Neibo[i].i][Neibo[i].j];<br>48                 putInOpenList(Neibo[i]);<br>49             }<br>50         }<br>51     }<br><p>代码2.2.4.2—A*寻路流程的代码</p><br><br>     然后，只要分别实现上面代码逻辑中的函数就好了：<br>  1 //以下函数都是A*算法的一部分///////////////////////////<br>  2 <br>  3 //把一个元素插入开启列表中/////////<br>  4 void putInOpenList(struct baseNode inList)<br>  5 {<br>  6     OpenList[openListCount] = inList;<br>  7     ++openListCount;<br>  8 }<br>  9 <br> 10 //取出开启列表中最小的数<br> 11 struct baseNode readTopOpenList()<br> 12 {<br> 13     struct baseNode temp;<br> 14     <br> 15     for (int i = 0; i &lt; openListCount-1; ++i)<br> 16     {<br> 17         if (OpenList[i].f&lt;OpenList[i+1].f)<br> 18         {<br> 19             temp=OpenList[i];<br> 20             OpenList[i]=OpenList[i + 1];<br> 21             OpenList[i + 1] = temp;<br> 22         }<br> 23     }<br> 24 <br> 25     return OpenList[openListCount-1];<br> 26 }<br> 27 <br> 28 //把一个元素加入关闭列表中<br> 29 void putInCloseList(struct baseNode temp)<br> 30 {<br> 31     CloseList[closeListCount] = temp;<br> 32 <br> 33     ++closeListCount;<br> 34 }<br> 35 <br> 36 //把开启列表中的当前节点删除<br> 37 void outOpenList(struct baseNode iter)<br> 38 {<br> 39     int i = openListCount - 1;<br> 40     for (; i &gt;= 0;--i)<br> 41     {<br> 42         if (OpenList[i].i==iter.i&amp;&amp;OpenList[i].j==iter.j)<br> 43         {<br> 44             break;<br> 45         }<br> 46     }<br> 47 <br> 48     for (int j = i; j &lt; openListCount-1; ++j)<br> 49     {<br> 50         OpenList[j] = OpenList[j+1];<br> 51     }<br> 52     --openListCount;<br> 53 }<br> 54 <br> 55 //对于一路上的每个点，分析它的最多八个邻居，并加入邻居列表<br> 56 void addNeibo(struct baseNode iter)<br> 57 {<br> 58     neibNum = 0;<br> 59 <br> 60     for (int i = iter.i - 1; i &lt;= iter.i + 1; ++i)<br> 61     {<br> 62         for (int j = iter.j - 1; j &lt;= iter.j + 1; ++j)<br> 63         {<br> 64             if (i &gt;= 0 &amp;&amp; i &lt;= MAX_number - 1 &amp;&amp; j &gt;= 0 &amp;&amp; j &lt;= MAX_number - 1)<br> 65             {<br> 66                 if (i == iter.i&amp;&amp;j == iter.j)<br> 67                 {<br> 68                 }<br> 69                 else<br> 70                 {<br> 71                     map[i][j].h = manhatten(i, j);<br> 72 <br> 73                     Neibo[neibNum] = map[i][j];<br> 74                     ++neibNum;<br> 75                 }<br> 76             }<br> 77         }<br> 78     }<br> 79 }<br> 80 <br> 81 //查看临近格在不在开启列表中的函数<br> 82 int isInOpenList(struct baseNode neibo)<br> 83 {<br> 84     for (int i = 0; i &lt; openListCount - 1; ++i)<br> 85     {<br> 86         if (OpenList[i].i == neibo.i&amp;&amp;OpenList[i].j == neibo.j)<br> 87         {<br> 88             return 1;<br> 89         }<br> 90     }<br> 91     return 0;<br> 92 }<br> 93 <br> 94 //查看指定的temp在不在关闭列表中的函数<br> 95 int isInCloseList(struct baseNode temp)<br> 96 {<br> 97     for (int i = 0; i &lt; closeListCount-1; ++i)<br> 98     {<br> 99         if (CloseList[i].i == temp.i&amp;&amp;CloseList[i].j == temp.j)<br>100         {<br>101             return 1;<br>102         }<br>103     }<br>104     return 0;<br>105 }<br>106 <br>107 //A*中的启发式函数，用于求指定位置和终点之间的曼哈顿距离<br>108 int manhatten(int i, int j)<br>109 {<br>110     return (abs(AsceneryList[1].node.i - i) + abs(AsceneryList[1].node.j - j))*10;<br>111 }<br>112 <br>113 //求当前点与父亲节点的距离<br>114 int increment(struct baseNode this)<br>115 {<br>116     if ((abs(this.father-&gt;i-this.i)==1) &amp;&amp; (abs(this.father-&gt;j - this.j) == 1))<br>117     {<br>118         return 14*this.weigt;<br>119     }<br>120     else if ((this.father-&gt;i - this.i) == 0 &amp;&amp; (this.father-&gt;j - this.j) == 0)<br>121     {<br>122         return 0;<br>123     }<br>124     else<br>125     {<br>126         return 10*this.weigt;<br>127     }<br>128 }<br>129 <br>130 //求出用当前点作为父节点时这个点的G值<br>131 int NewG(struct baseNode this,struct baseNode father)<br>132 {<br>133     if (abs(father.i - this.i) == 1 &amp;&amp; abs(father.j - this.j) == 1)<br>134     {<br>135         return father.g+14;<br>136     }<br>137     else if (abs(father.i - this.i) == 0 &amp;&amp; abs(father.j - this.j) == 0)<br>138     {<br>139         return father.g;<br>140     }<br>141     else<br>142     {<br>143         return father.g+10;<br>144     }<br>145 }<br><p>代码2.2.4.3—刚才代码中具体函数的分别实现</p><p>    经过函数实现之后，我们就得出来了一条最短的从起点A到终点B的路径，这条路径上（包含A和B），每一个格子都指向它的父节点，因此我们可以从终点开始，一直遍历父节点，并设置一个迭代器，把每个格子的父节点赋值给迭代器，再储存入一个存储路径的数组里，我们就得到了这条路径：</p><br><code lang=\"text\">1 //用来记录路径经过的点的个数2 int AstackCount = 0;\n3 \n4 //用来储存整理后的路径5 struct baseNode Astack[MAX_number*MAX_number];\n</code><br>代码2.2.4.4—存储最佳路线的数组<br> 1 //把A*算法的节点按倒序整理到Astack里面<br> 2 void arrange(struct baseNode iter)<br> 3 {<br> 4     AstackCount = 0;<br> 5     for (; ; iter=map[iter.father-&gt;i][iter.father-&gt;j])<br> 6     {<br> 7         Astack[AstackCount] = iter;<br> 8         ++AstackCount;<br> 9         if (iter.i == AsceneryList[0].node.i&amp;&amp;iter.j == AsceneryList[0].node.j)<br>10         {<br>11             break;<br>12         }<br>13     }<br>14 }<br>15 <br>16 //打印出A*算法的路径矩阵<br>17 printAstar()<br>18 {<br>19     printf(\"A为最佳路径，Q为不经过区域\\n\\n\");<br>20     int boole = 0;<br>21 <br>22     for (int i = 0; i &lt; MAX_number; ++i)<br>23     {<br>24         for (int j = 0; j &lt; MAX_number; ++j)<br>25         {<br>26             for (int w=0; w&lt;AstackCount; ++w)<br>27             {<br>28                 if (Astack[w].i==i&amp;&amp;Astack[w].j==j)<br>29                 {<br>30                     boole = 1;<br>31                     break;<br>32                 }<br>33             }<br>34 <br>35             if (boole==1)<br>36             {<br>37                 printf(\"A \");<br>38                 boole = 0;<br>39             }<br>40             else<br>41             {<br>42                 printf(\"Q \");<br>43             }<br>44         }<br>45         printf(\"\\n\");<br>46     }<br>47 }<br><p>代码2.2.4.5—迭代整理和输出</p><br><br>大功告成......等等，还差一步，我们在做A*操作时曾经假设iter初始化为起点，ender为终点，记得吗？因此，我们在做A*算法之前还要做这种类似初始化的操作：<br>//每次执行A*算法，都初始化开启/关闭列表<br>    openListCount = 0;<br>    closeListCount = 0;<br><br>    //创建一个迭代器,每次都等于f值最小的节点<br>    struct baseNode iter;<br><br>    //让这个迭代器的初值为起点<br>    iter.i = AsceneryList[0].i;<br>    iter.j = AsceneryList[0].j;<br>    iter.weigt = map[AsceneryList[0].i][AsceneryList[0].j].weigt;<br><br>    //起点的没有父节点，且为唯一G值为0的点<br>    iter.g = 0;<br>    iter.h = manhatten(iter.i,iter.j);<br>    iter.f = iter.g + iter.h;<br><br>    //创建终点<br>    struct baseNode ender;<br><br>    ender.i = AsceneryList[1].i;<br>    ender.j = AsceneryList[1].j;<br><br>    //把起点放入开启列表<br>    putInOpenList(iter);<br><p>代码2.2.4.6—初始化A*</p><br><br><strong>2.3 A*算法总结</strong><br><br><br>       其实，了解数据结构的人会看出来，A*里的开启列表每次都要找出里面的最小值，本文中逐个搜索取最小值的方法并不是最好的方法，这涉及到查找，二叉排序树等等知识，在下一篇文章中，我们开始正式分析如何优化这个算法。<br><p>     作为参考，这篇文章里的程序在VS2015中运行的结果差不多是这样的：</p><br><img src=\"v2-a89ddeda7950e9c5b5cfeda553d1b657.png\" data-rawwidth=\"799\" data-rawheight=\"519\"><br><img src=\"v2-325a2299ab80a7312541e167ebebc600.png\" data-rawwidth=\"360\" data-rawheight=\"619\"><img src=\"v2-9f80353dcffb7ee76f3feaacc2041993.png\" data-rawwidth=\"377\" data-rawheight=\"583\"><img src=\"v2-8f017f3d7123a57176a793e33e2da8fe.png\" data-rawwidth=\"444\" data-rawheight=\"349\"><br>       下一篇文章<a href=\"https://zhuanlan.zhihu.com/p/23199897\">https://zhuanlan.zhihu.com/p/23199897</a>里我们将介绍A＊算法的改良。","updated":"2016-10-25T09:51:23.000Z","canComment":false,"commentPermission":"anyone","commentCount":2,"likeCount":8,"state":"published","isLiked":false,"slug":"23199758","isTitleImageFullScreen":false,"rating":"none","sourceUrl":"","publishedTime":"2016-10-25T17:51:23+08:00","links":{"comments":"/api/posts/23199758/comments"},"url":"/p/23199758","titleImage":"https://pic3.zhimg.com/v2-8f017f3d7123a57176a793e33e2da8fe_r.png","summary":"","href":"/api/posts/23199758","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":2,"likesCount":8},"23199897":{"title":"A*寻路算法的探寻与改良（三）","author":"t.t.","content":"<h1><strong>A*寻路算法的探寻与改良（三）</strong></h1><p><strong>by:田宇轩                                        </strong></p><h3><strong>第三分：这部分内容基于树、查找算法等对A*算法的执行效率进行了改良，想了解细化后的A*算法和变种A*算法内容的朋友们可以跳过这部分并阅读稍后更新的其他内容</strong></h3><br><strong>3.1 回顾</strong><br><p>       在我的上一篇文章中，我们探讨了如何用编程实现A*算法，并给出了C语言的算法实现，这一章内容中我们主要研究如何提高A*算法的执行效率。抛开时间复杂度的复杂计算，我们大概可以知道，函数对数据的操作次数越少，达成目的越快，算法的效率也就越高。沿着这个思路，我们可以先从研究函数对存储结构做的操作频率和具体内容改造它们，使A*更高效。如果前两部分只是初学者的新手教程，那么从本章开始，我们进入了更难的部分。</p><p><strong>3.2 分析A*函数的中代价高的操作</strong></p><p>      在A*中，我们把起点放入iter，然后就重复for循环，可见for循环中重复执行的函数对于A*算法性能的影响是非常重要的，我们就从这个Astar里的最外层for循环开始看，一个函数一个函数地分析出哪个部分可以如何提高A*算法的效率。</p><p><strong>（一）</strong>首先我们分析的就是这个for循环的循环条件，这个循环的条件在每一次循环发生的时候都会进行判定。最外层的for循环里，我们只判定这么两项内容：</p><p><strong>（1）开启列表是否为空</strong>。开启列表如果是空的，这就代表我们没有待处理的格子了，已经无路可走，因此开启列表一旦为空，A*算法也就不用执行了。但是看过上一篇文章的朋友应该记得，我们用一个有全局作用域的变量openListCount（引用代码内容用基佬紫色，下同）来记录开启列表里格子的个数，因此，这个判定就只是判定openListCount这个参数是否为0，这种判定很简单，因此<strong>不用优化</strong>。</p><p><strong>（2）终点是否在关闭列表中</strong>。一旦终点在关闭列表之中，就说明我们已经找到了最优路径，并且把路径的最有一个格子——终点也进行了父节点标记的操作，这一操作之后，A*也不必继续下去了。回顾上一篇文章，我们是在关闭列表中逐一匹配里面格子的坐标是否和终点坐标相等，这其实是很麻烦的方法。那么，怎么检测终点是否在关闭列表中呢，这里有一个更好的思路：我们都知道<strong>起点是唯一一个G值为0的格子</strong>（起点距离自己的距离为0），<strong>相应的，终点也是唯一一个H值为0的格子。</strong>在求曼哈顿距离时，如果发现一个格子的H值为0，那么毫无疑问，这个格子就是终点。我们可以用一个标记（类似process_control.h里面的参数flag一样）来使主循环停止而不用一一匹配新格子与关闭列表。</p><p><strong>（二）</strong>主循环分析完了，我们来看看迭代器进入循环体内部发生的事情。之后首先发生的事情，是一个查找操作，开启列表中F值最小的（之一）会被找出来并设为当前格。然后是一个把当前格放入关闭列表的操作。先分析这两步操作：</p><p><strong>（1）查找开启列表中的最小值</strong>。之前这一步操作中我们用的是冒泡排序的一层循环，把它们中最小的数（之一）沉到底，但是这种查找方法显然并不快，开启列表是在稍后的迭代操作中一步一步建立起来的，因此我们每次把东西加入开启列表可以按照最小二叉堆的添加操作做，这样数组的最后一个元素自然就是开启列表中最大的元素（之一）了。</p><p><strong>（2）往开启列表中插入新的元素</strong>。开启列表是最小二叉堆，因此插入元素要根据最小二叉堆的性质。</p><p><strong>    （3）删除开启列表中最小的元素</strong>。开启列表是最小二叉堆，因此删除元素要根据最小二叉堆的性质。</p><p><strong>    （4）删除开启列表中指定的元素</strong>。开启列表中元素的f值可能会随着重新计算NewG的值而改变，因此我们会先删除指定的元素。<strong>这个过程可以有很多种方式实现，这里，我的例子选择完全重新排序开启列表，其实不是很有效率。</strong></p><p><strong>（5）把当前元素加入关闭列表，</strong>用方便查找的方式构建关闭列表使其易于查找。</p><p><strong>（6）搜索关闭列表，</strong>配合关闭列表结构提高效率。</p><p>     因此，我们可以总结出<strong>7条可以优化的操作</strong>（函数）：</p><p>     （1）void putInOpenList(struct baseNode inList),把一个元素插入开启列表中。开启列表主要是插入删除，因此用最小二叉堆就好了，每次都出队列最小的数字，改进后要求格子按照最小二叉堆的性质进行插入操作。</p><p>     （2）struct baseNode readTopOpenList()，取出开启列表中最小的数字。改进后这个函数根据最小二叉堆的性质直接获取列表顶部格子即可。</p><p>     （3）void putInCloseList(struct baseNode temp)，当前点加入到关闭列表中。关闭列表只有插入和搜索操作，为了方便检索，可以按照二叉排序树、AVL树或者红黑树的性质做一个关闭列表的操作（然而我并不会红黑树，（逃（哔站粉用于标记吐槽和没什么卵用的内心独白，下同），等我学完红黑树就回来补完这个~QwQ），这里，为了简单（其实只是自己水平有限），做一个方便查找的普通排序列表配合折半查找好了。</p><p>     （4）void outOpenList(struct baseNode iter），把开启列表中的当前节点删除。既然开启列表是最小二叉堆，删除也要按照这个性质来。<br>\n     （5）void outopenlist2(struct baseNode iter), 重新排序最小二叉堆，并删除指定的点。</p><p>     （6）int isInCloseList(struct baseNode temp)，查看指定的temp在不在关闭列表中的函数，用折半查找提高效率就好了。</p><p>     （7）int manhatten(int i, int j)，求曼哈顿函数的值，当值为零，赶紧立一个flag，让主循环停止。</p><p>      OpenList和CloseList的存储结构也随着新设计的数据结构改变就好，明确了这些重点，剩下的活只要实现这些函数，然后把函数覆盖原来的函数（位于func.h中）就好。</p><p><strong>3.3 实现7条优化</strong></p><p>下面的内容就是这些函数的具体实现。</p><p><strong>3.3.1 优化终点在不在关闭列表的判定</strong></p><br><br>      首先，我们对比较简单的（7）int manhatten(int i, int j)，进行改造如下：<br> 1 //A*中的启发式函数，用于求指定位置和终点之间的曼哈顿距离<br> 2 int manhatten(int i, int j)<br> 3 {<br> 4     int a= (abs(AsceneryList[1].node.i - i) + abs(AsceneryList[1].node.j - j));<br> 5     if (a==0)<br> 6     {<br> 7         FLAG = 1;<br> 8     }<br> 9 <br>10     return a*10;<br>11 }<br><p>代码3.3.1.1——改造后的manhatten</p><p>    这里，我们在data.h里定义一个全局变量，int FLAG=0;,这个FLAG初值为0，每当Astar执行中发现某个格子曼哈顿距离为0,相应地，就把这个FLAG的值改为1，然后Astar内最外层for循环判定条件发现FLAG等于1，就意味着终点已经在关闭列表内，可以松口气了（以前是遍历关闭列表找终点在不在里面，这显然是一步优化）。但是相应地，改变Astar最外层for语句为for (;  openListCount != 0 &amp;&amp; FLAG==0;)。</p><p>    同时别忘了每次执行Astar前都重置FLAG值为1，只需在Astar函数内开始加上一句FLAG=0;。</p><p><strong>3.3.2 优化开启列表</strong></p><br><br>    函数（1）（2）（4）（5）都和开启列表有关，分别对应着开启列表的添加元素，最小值出队列，删除元素和搜索，我们这里再处理他们，改为下面这样的函数：<br> 1 //把一个元素插入开启列表中/////////<br> 2 void putInOpenList(struct baseNode inList)<br> 3 {<br> 4     ++openListCount;<br> 5 <br> 6     OpenList[openListCount - 1] = inList;<br> 7     for (int i = openListCount - 1; i &gt;0; i=(i-1)/2)<br> 8     {<br> 9         if (OpenList[i].f&lt;OpenList[(i-1)/2].f)<br>10         {<br>11             OpenList[i]=OpenList[(i - 1) / 2];<br>12             OpenList[(i - 1) / 2] = inList;<br>13         }<br>14         else<br>15         {<br>16             break;<br>17         }<br>18     }<br>19 }<br>20 <br>21 //取出开启列表中最小的数<br>22 struct baseNode readTopOpenList()<br>23 {<br>24     return OpenList[0];<br>25 }<br>26 <br>27 //把开启列表中的当前节点删除<br>28 void outOpenList()<br>29 {<br>30     --openListCount;<br>31 <br>32     OpenList[0]=OpenList[openListCount];<br>33     struct baseNode temp;<br>34 <br>35     for (int i = 0,p=0; 2*i+1&lt;openListCount;i=p)<br>36     {<br>37         if (2*i+2&gt;openListCount-1)<br>38         {<br>39             p = 2 * i + 1;<br>40         }<br>41         else<br>42         {<br>43             if (OpenList[2 * i + 1].f&lt;OpenList[2 * i + 2].f)<br>44             {<br>45                 p = 2 * i + 1;<br>46             }<br>47             else<br>48             {<br>49                 p = 2 * i + 2;<br>50             }<br>51         }<br>52 <br>53         if (OpenList[p].f&lt;OpenList[i].f)<br>54         {<br>55             temp=OpenList[p];<br>56             OpenList[p]=OpenList[i];<br>57             OpenList[i] = temp;<br>58         }<br>59         else<br>60         {<br>61             break;<br>62         }<br>63     }<br>64 }<br>65 <br>66 //删除开启列表中指定的元素，重构最小二叉堆<br>67 //<strong>（注：这个可以用很多方法实现，示例并非最优）</strong><br>68 void outOpenList2(struct baseNode iter)<br>69 {<br>70     int number=openListCount-1;<br>71     struct baseNode openlist2[MAX_number*MAX_number];<br>72     for (int i = 0; i &lt; openListCount; ++i)<br>73     {<br>74         if (OpenList[i].i==iter.i&amp;&amp;OpenList[i].j==iter.j)<br>75         {<br>76             continue;<br>77         }<br>78         openlist2[i]=OpenList[i];<br>79     }<br>80 <br>81     openListCount = 0;<br>82     for (int i = 0; i &lt; number; ++i)<br>83     {<br>84         putInOpenList(openlist2[i]);<br>85     }<br>86 }<br><p>代码3.2.2.1——优化开启列表</p><p><strong>3.3.3 优化关闭列表</strong></p><br><br>关闭列表中的元素是只进不出的，因此这里用简单的排序+折半查找优化效率，<strong>注意：对于关闭列表中的排序，应该用唯一值做key方便折半查找</strong>，这里，唯一key被设置成为格子的i坐标乘地图边的最大值加上格子的j坐标：<br> 1 //把一个元素加入关闭列表中<br> 2 void putInCloseList(struct baseNode temp)<br> 3 {<br> 4     CloseList[closeListCount] = temp;<br> 5 <br> 6     struct baseNode iter;<br> 7     for (int i = closeListCount; i&gt;0; --i)<br> 8     {<br> 9         if ((CloseList[i].i*MAX_number+CloseList[i].j+1)&lt;(CloseList[i-1].i*MAX_number + CloseList[i-1].j + 1))<br>10         {<br>11             iter = CloseList[i];<br>12             CloseList[i]=CloseList[i - 1];<br>13             CloseList[i - 1] = iter;<br>14         }<br>15         else<br>16         {<br>17             break;<br>18         }<br>19     }<br>20     ++closeListCount;<br>21 }<br>22 <br>23 //查看指定的temp在不在关闭列表中的函数<br>24 int isInCloseList(struct baseNode temp)<br>25 {<br>26     int low = 0, high = closeListCount - 1, mid = (low + high) / 2;<br>27 <br>28     for (; low&lt;=high; mid = (low + high) / 2)<br>29     {<br>30         if ((CloseList[mid].i*MAX_number + CloseList[mid].j + 1)==(temp.i*MAX_number + temp.j + 1))<br>31         {<br>32             return 1;<br>33         }<br>34         else if((CloseList[mid].i*MAX_number + CloseList[mid].j + 1) &gt; (temp.i*MAX_number + temp.j + 1))<br>35         {<br>36             high = mid - 1;<br>37         }<br>38         else<br>39         {<br>40             low = mid + 1;<br>41         }<br>42     }<br>43     return 0;<br>44 }<br><p>代码3.3.3.1——优化关闭列表</p><br>      这里要说明一下思路，我们为了使关闭列表方便查找，使用了插入新元素时排序关闭列表的方式，排序依赖的值应该类似主码，是格子唯一的标记，格子存储在二维数组中，唯一标记显然是格子的坐标，不过坐标是两个值，我们不想弄一个结构体储存格子的key，所以就采用哈希表的思路把格子的横纵坐标转换为一个唯一值，那就是一个格子在二维列表的次序（这个格子在二维列表中是第几个格子）。这样所有的函数就优化完了。<p><a href=\"https://github.com/TiriSane/Algorithm/tree/master/Astar\" class=\"\" data-editable=\"true\" data-title=\"Algorithm/Astar at master · TiriSane/Algorithm · GitHub\">Algorithm/Astar at master · TiriSane/Algorithm · GitHub</a></p>","updated":"2016-10-25T09:57:07.000Z","canComment":false,"commentPermission":"anyone","commentCount":0,"likeCount":11,"state":"published","isLiked":false,"slug":"23199897","isTitleImageFullScreen":true,"rating":"none","sourceUrl":"","publishedTime":"2016-10-25T17:57:07+08:00","links":{"comments":"/api/posts/23199897/comments"},"url":"/p/23199897","titleImage":"https://pic1.zhimg.com/v2-911dbe48548fc6a79896e15f9e386e0c_r.jpg","summary":"","href":"/api/posts/23199897","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":0,"likesCount":11},"23503699":{"title":"C++Primer第5版学习笔记（三）","author":"t.t.","content":"<strong>      第三章的重难点内容</strong><br><strong>第三章 字符串、向量和数组</strong><br>      这篇笔记记录了我在学习C++常用基本语法的学习过程，基本只记录一些重难点，对概念的描述不是一开始就详尽和准确的，而是层层深入的。第三章主要讲这么五个概念：<br><p><strong>      1.using声明</strong>，我知道挺多同学写代码练手都要在源文件前几句直接加using namespace std;然而using语句并不是什么情况都这么使用的，稍后我们将会看到详细的用法。</p><p><strong> 2.标准库类型string</strong>,和C味的字符数组有区别的string，到底是怎么个构造，这章将会讲述。</p><p><strong> 3.标准库类型vector</strong>，vector和数组区别很大，这里将会提到，并引入一个“容器”的重要概念。</p><p><strong>4.迭代器</strong>，迭代器用来代替下标这种传统方式访问容器或一些支持迭代器的类型。</p><br><strong>5.数组和多维数组</strong>，经典概念。<br><br><strong> 下面是这一章的知识点：</strong><br><strong> 知识点1：P75，3.1，头文件和using语句</strong><strong>（英文版84页）</strong><br>      尽管我们可以在各种文件里都使用using namespace std;或者using std::endl;这种语句，但是，在头文件包含命名空间可能产生各种意外。因此，头文件不应包含using声明。cocos2dx引擎3.2的版本就在头文件也使用了using namespace的语句，在现在3.10版本已经在头文件里用命名空间标识符来代替以前的做法。可见不在头文件中使用using语句是很标准的用法。（这里的using 语句指的只是使用命名空间作用域的using语句，不包括using SI＝int这种别名声明语句。）<br><br><strong>  知识点2：P76，3.2.1，定义和初始化string对象</strong><strong>（英文版85页）</strong><br><p>以下几种初始化语句被string支持：</p><p>      string s1;//创建了一个空的字符串，对象名为s1，类型为string类型。</p><p>      string s2(s1);//是s2的值与s1的值相等。</p><p>      string s2=s1;//同上一句，拷贝初始化。</p><p>      string s3(\"value\");//直接用字符串字面值初始化string类型的对象。</p><p>      string s3=\"value\";//字符串字面值转化为string类型变量并赋值给string。</p><p>      string s4(n,'c');//直接初始化string，操作后s4拥有10个字符，每个字符的值都是'c'。</p><p>      最后，其实string s5={\"value\"}和string s3=\"value\"一样，也是合法的。不过大括号初始化是严格检测匹配的，比如int a={3.5};就是错误的。</p><br><strong>      知识点3：P77，3.2.2，string支持的操作</strong><strong>（英文版86页）</strong><br>1.输入流中获取字符串首先要强调是cin&gt;&gt;string的操作，这种操作就是从输入流中读字符串，值得注意的是这个过程会忽略掉开头输入的各种空白（我们说空白时是在说  空格，换行符，制表符）,读取输入流直到遇到字符后的第一个空白为止，另一种getline（cin,string）;的操作则可以读一行，也就是读入输入流的数据（包括空格，制表符），直到遇到换行符为止，这里输入流中的换行符本身已经被读过了，但是字符串里不保存这个换行符。下次再从输入流里读什么数据至少也要从这个换行符后面对输入流进行操作了。<br>      2.string::type_size 为了更抽象，脱离机器特性，调用每个string对象的size成员函数，返回值都是一个string::type_size类型，这个类型拥有无符号整形数的一些性质。在string对下标的支持中，[ ]中的数字也会被转换为string::type_size类型。这里要强调的是string::type_size是一个无符号类型。使用这个类型和int型这种有符号的类型一起进行计算可能出现一些错误。<br><p>      3.string对象与字符串字面值相加  字符串字面值是字符数组类型，字符串字面值和string类型的对象在一起计算时会被自动转换为string类型。</p><p>      4.其他支持的操作：包括下标运算符[ ]、重载的+、==、！=、&lt;、&gt;、&lt;=、&gt;=。</p><br><strong>知识点4：P82，3.2.3，范围for（range for）语句</strong><strong>（英文版91页）</strong><br><p> 范围for语句用于遍历元素。形如：for(一个用于访问序列中基础元素的变量a : 被访问的序列对象b){statement..... blabla;}</p><p>      首次初始化，变量a的值会被初始化为对象b序列中的第一个元素，迭代之后每次访问下一个元素，直到序列被完全访问结束。</p><p>      可以使用auto &amp;a的方式声明变量a,使变量绑定到具体的序列元素上，从而进行更改。如在for(auto a : str){}中，每次把a初始化的行为实质上是使a获得str每个元素的副本（拷贝），而for(auto &amp;a ： str){}这样的语句则使a成为了str对应的每个元素的\"别名\",从而可以修改str。</p><br>      使用范围for循环遍历多维数组，为了不手动打类名，也为了防止外层数组的名被auto类型转化成指针，要在对外层数组的访问上都加上&amp;绑定。<br><br><strong> 知识点5：P82，3.2.3，处理每个字符的头文件cctype</strong><strong>（英文版91页）</strong><br><p> 我们可以通过引用头文件&lt;cctype&gt;的形式处理每一个字符。这个头文件包含很多方便处理字符的函数。列举如下：<br></p><p>      isalnum(c);    //当c是字母或者数字时为真      isalpha(c);     //当c是字母时为真 </p><p>      iscntrl(c);      //当c是控制字符时为真</p><p>      isdigit(c);      //当c是数字时为真                    isgraph(c);    //当c不是空格但是可打印时为真</p><p>      islower(c);    //当c是小写字母为真</p><p>      isprint(c);      //当c可打印时为真                    isupper(c);    //当c是大写字符时为真</p><p>      isxdigit(c);     //当c是16位数字时为真</p><p>      ispunct(c);    //当c是标点符号时为真（一个字符除了控制字符，字母，数字，可打印空白就是标点符号） </p><p>      isspace(c);    //当c是空白时为真（空白包括空格，横向/纵向制表符，回车符，换行符，进纸符）</p><p>      tolower(c);    //把大写字符转换为小写字符，本来就是小写字符的不变，返回转换后的字符</p><p>      toupper(c);   //把小写字符转换为大写字符，本来就是大写字符的不变，返回转换后的字符</p><br><strong>知识点6：P87，3.3，类模板、容器和实例化</strong><strong>（英文版97页）</strong><br><p>      当我们在C++里面谈论容器这个概念时，我们应该知道容器是用来存储和组织一类特定对象的集合。下面提到的标准库类型vector，就是一个容器。</p><p>      类模板一般用于按照模板规定好的规则生成不同的类。我们无需很麻烦的一个一个写类的定义，只需使用模板，给出指定的少量信息，类模板就会帮助我们自动生成一个我们可以直接使用的类。vector也是一个类模板。</p><p>      通过类模板创建类的过程，或者通过类型创建对象的过程，就叫做实例化。</p><br><strong>知识点7：P87，3.3.1，定义和初始化vector对象</strong><strong>（英文版97页）</strong><br><p> 与string的定义和初始化一样，我们也可以使用多种方式定义和初始化一个vector对象。</p><p>以下几种初始化语句被string支持：</p><p>      vector&lt;Type&gt; v1;//创建了一个空的vector容器，这个容器是Type类型对象的集合，这个集合名字叫做为v1，执行默认初始化。</p><p>      vector&lt;Type&gt; v2(v1);//创建了一个叫做v2的vector容器，这个容器的内容和v1相同。</p><p>      vector&lt;Type&gt; v2=v1;//同上一句，拷贝初始化。</p><p>      vector&lt;Type&gt; v3{a,b,c};//v3包含了初始值个数的元素。</p><p>      vector &lt;Type&gt; v4={a,b,c};//同上。</p><p>      vector &lt;Type&gt; v5(n,val);//直接初始化这个容器，操作后v5拥有n个元素，每个元素的值都是val。</p><p>      vector &lt;Type&gt; v5(n);//直接初始化这个容器，操作后v5拥有n个元素，每个元素的值都被默认初始化。</p><p>      当我们使用圆括号（）初始化对象时，IDE会认为我们在通过语句“构建”这个对象  ；当我们使用花括号{ }初始化对象时，IDE会认为我们在初始化对象。</p><p>当我们使用等号=初始化对象时，我们就执行了“拷贝初始化”；当我们不使用=初始化对象时，我们就执行了“直接初始化”。</p><p><strong>      但是当我们在花括号里面给一个不符合对象类型的值，IDE就会认为我们正在构建而非初始化对象，</strong>一个体现就是，vector&lt;string&gt; s1{10};  这个语句中，10不能转换为string，因此被系统理解为“这个string容器里有10个元素”。当然，像vector &lt;string&gt;s1={10};这样的语句是错误的，因为=就应该是拷贝初始化了，然而10并不能够被转化为string因此也无法赋值。</p><br><br><strong>      知识点8：P90，3.3.2，vector支持的操作</strong><strong>（英文版102页）</strong><br><p> 1.向容器的后面添加元素：已存在vector&lt;T&gt; v;，可以使用 v.push_back(vector&lt;T&gt; a)的方式在集合v的尾部添加元素。</p><p>      2.empty和size函数成员：已存在vector&lt;T&gt; v;，可以使用 v.empty()的方式判断v是否为空，可以使用v.size()的方式返回v的大小。</p><p>      3.重载的运算符：vector支持的运算符包括下标运算符[ ]、重载的+、==、！=、&lt;、&gt;、&lt;=、&gt;=。这一点和string类似。</p><br><strong> 知识点9：P95，3.4.1，迭代器</strong><strong>（英文版106页）</strong><br>为了访问容器的元素（有些容器可能不支持下标运算符），因此C++提供了迭代器这个概念来访问容器中的指定元素。<br>     支持迭代器的类都会提供名为begin和end的函数成员来供我们获取迭代器。如已定义vector&lt;int&gt; i1(10);这时使用auto ben=i1.begin();这个语句获取指向第一个字符的迭代器，使用auto end=i1.end();获取指向i1容器最后一个元素的下一个元素的迭代器，术语“尾后迭代器”。两个迭代器可以相减，但是两个迭代器相加后的行为是未定义的。<br><p>     当使用vector &lt;int&gt; 创建类时，这个类的命名空间就是vector &lt;int&gt;，命名空间中的迭代器类型写作vector&lt;int&gt;::iterator。因为这个叫做\"vector&lt;int&gt;::iterator\"的迭代器类型名太长了也不好记，这里我们使用auto推导这个类型。用成员函数cbegin和cend可以推导出底层const迭代器，就是这个迭代器对迭代器指向的内容只读不写。第6章会详细说明。</p><br>     迭代器 对 迭代器指向的容器内容    可以像    指针 对 指针指向的数组元素一样使用。<br>     虽然数组不是直接支持迭代器的类型，但是可以引入&lt;iterator&gt;头文件，使用begin(数组名)和end(数组名)的方式获得指向数组第一个元素和尾后第一个元素的指针。因为大多数容器不支持下标运算符，所以使用迭代器访问容器等结构中的元素是最好的方法。<br><br><strong>知识点10：P102，3.5.1，一维数组的定义和初始化</strong><strong>（英文版114页）</strong><br><p>      一维数组声明形式：类型名  数组名[一个常量]。比如int a[15];这里这个数组的名字是a，有15个元素，每个元素都是int型的。再比如int *a[15];这里a数组的15个元素都是int *型的，即指向int的指针，这样的指针有15个，构成了一个数组。虽然有指针数组，但是<b>不</b><strong>存在元素都是引用类型的数组</strong>。</p><p>      一维数组的初始化方式就是花括号初始化，形如int a[n]={1,2,3};大括号里面的内容就是初始化列表，n为数组大小，可以缺省，缺省时数组长度由初始化列表的元素个数决定。当初始化列表的值的个数比数组长度小，数组剩下的元素被初始化为默认的值，比如对于有10个元素的int型数组，如果只给出第一个元素的值，后几个元素将被初始化为0。</p><br>      当我们声明int a[]的时候代表通过数组名a访问这个数组。我们也可以定义指向数组的指针和指向数组的引用来间接访问这个数组。已有int arr[10];的情况下，int (*ptr) [10]=&amp;arr;这条语句可以使指针ptr指向arr这整个数组。int (&amp;ref)[10]=arr;则会使ref作为整个arr数组的引用。int *(&amp;ref)[10]=arr;这个语句则是说ref是arr的引用，这个被引用的数组的类型是指针数组。<br>      auto a=一个数组名，a的类型将会是这个指针，指针指向的类型就是数组元素的类型。用decltype(一个数组名) a;这样的形式，a将会是和数组名属性一致的数组。在大部分运算中，数组名都会被转化成相应的指针类型。如*(ai+4)中，数组名ai是指向整个数组首元素的指针，这个指针＋4就是向右侧移动4位，指针原来指向第一个元素，移动4位就指向了数组中的第五个元素。然后指向的值就是ai数组第五个元素的值，相当于ai[4]。<br><br><strong>   知识点11：P111，3.5.5，用数组初始化vector对象    和     用string对象赋值字符数组</strong><strong>（英文版124页）</strong><br>作为与旧代码的接口，C++提供了方便的把数组转化为vector对象的方法。在声明vector对象时，我们可以通过迭代器用一个数组初始化vector。在已经存在int oldarray[10];的情况下，声明的语句形如：vector&lt;int&gt; arr( begin(oldarray)  ,  end(oldarray)  );可以把arr初始化为oldarray。begin和end这两个函数在&lt;iterator&gt;头文件里，作用是返回数组的首元素/尾后指针。这种初始化接受两个参数：拷贝开始部分指针和结束部分的指针。我们也可以写形如int arr[10]={0};   vector &lt;int&gt; newarr( arr+1   ,  arr+6 );这种方式拷贝数组arr的第2~第5号元素，并用它们初始化newarr。<br>       类似地，我们可以通过string a(\"23333333\\n\");  const char *b=a.c_str();这样的语句使string型的a被赋值给字符数组指针b。返回结果是const是为了确保我们不会通过这个指针改动返回的字符数组的值。<br><br><br><b>     第三章补充说明的内容：</b><br><b>1.关于命名空间作用域</b><b>：</b><br>     书上的之后的代码都默认它们已经使用了正确的命名空间作用域。关于书中使用到的命名空间作用域，书后的附录A1部分有列表标注了这些书中用到的命名空间作用域。<br><b>     2：默认初始化、值初始化、拷贝初始化、直接初始化和列表初始化</b><b>：</b><br> 本章介绍了这几种初始化概念，这里主要分析它们的区别。默认初始化依赖于类的默认行为，函数外定义的类如果没有初始值，将被默认初始化为这个类“0”这个概念对应的值。函数内定义的未初始化的值执行默认初始化时有两种情况，当这个类是C++内置类的时候，比如说int,float，这个值不被初始化；当这个类是用户定义的或者是我们使用类模板定义的，将被构造函数初始化。其中如果这个类的对象被隐式初始化为这个类意义上的零，对应的这种初始化的行为就叫做值初始化。<br>     拷贝初始化和直接初始化的区别只在于初始化语句带()、{}还是由=构成。使用小括号或者大括号初始化对象的行为叫做直接初始化。使用=号初始化对象的行为叫做拷贝初始化，其中，使用{}初始化对象的行为叫做列表初始化。特点是列表初始化的列表内容必须要和初始化对象的类型严格匹配。<br><b> 本章英语重点专业词汇：</b><br><br><br><b>    1.拷贝初始化             copy initialization</b><br><b>    2.直接</b><b>初始化             direct initialization</b><br><b>    3.范围for                  range for</b><br><b>    4.容器                      container</b><br><b>    5.类模板                   class template</b><br><b>    6.实例化                   instantiation</b><br><b>    7.值初始化                value-initialized</b><br><b>    8.构造                      construct</b><br><b>    9.列表初始化            list initialize</b><br><b>    10.迭代器                iterator</b><br><b>    11.迭代器运算          iterator arithmetic</b><br><b>    12.C风格字符串        C-style character string</b><br><b>    13.空字符                 null terminated</b><br><b>    14.缓冲区溢出          buffer overflow</b><br><b>    15.编译器扩展          complier extension</b>","updated":"2016-11-08T02:53:51.000Z","canComment":false,"commentPermission":"anyone","commentCount":1,"likeCount":6,"state":"published","isLiked":false,"slug":"23503699","isTitleImageFullScreen":true,"rating":"none","sourceUrl":"","publishedTime":"2016-11-08T10:53:51+08:00","links":{"comments":"/api/posts/23503699/comments"},"url":"/p/23503699","titleImage":"https://pic1.zhimg.com/v2-96f53f6d90d8be2813c2d285090e110c_r.jpg","summary":"","href":"/api/posts/23503699","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":1,"likesCount":6},"23535827":{"title":"C++Primer第5版学习笔记（四、五）","author":"t.t.","content":"<strong>       第四、五章的重难点内容</strong><br><br>      因为第五章的内容比较少，因此和第四章的笔记内容合并。<br><strong>  第四章是和表达式有关的知识，表达式是C++的基础设施，本章由三部分组成：</strong><br><br><strong>      1.表达式概念基础</strong>，包括表达式的基本概念，左值和右值的概念，优先级结合律，求值顺序。<br><strong> 2.各种运算符</strong>,主要包括算数\\关系\\逻辑\\赋值\\递增递减\\成员访问\\条件\\位运算\\sizeof\\逗号运算符 这10种运算符。<br><strong> 3.类型转换</strong>，包括隐式和显式两种转换的规则。<br><br><strong> 下面是这一章的知识点：</strong><br><br><br><strong> 知识点1：P120，4.1.1，表达式的基本概念</strong><strong>（英文版134页）</strong><br>      表达式由一个或者多个运算对象组成，多个对象组成表达式时，对象之间用运算符连接形成复杂表达式。<br>      运算符中，需要两个对象和运算符连接形成表达式的这种运算符叫做二元（双目，二目）运算符。<br>       分析一个表达式，必须先了解运算对象的含义、运算符的优先级结合律和运算符的求值顺序。<br><strong>1.</strong>对于含有子表达式的复杂表达式，应该按照求值顺序，看看应该先求哪一个子表达式的值。<br><strong>     2.</strong>对于不那么复杂的子表达式，应该按照优先级，查看表达式中的每个操作数（对象）应该先跟那一个运算符在一起运算。<br><strong>     3.</strong>如果有优先级相同的运算符同时在同一个运算对象左右，应该按照结合律选定结合顺序是从右向左还是从左向右计算表达式的值。<br><br><strong>  知识点2：P121，4.1.1，左值和右值</strong><strong>（英文版136页）</strong><br><strong>起源：</strong>左值和右值原来是C语言中的概念，特指赋值运算符左右两段的表达式。C语言中，能放在赋值运算符左侧被赋值的对象就是左值，反过来在赋值运算符右侧的对象就是右值。C++中的这两个概念的词义发生了改变。<br><strong>概述：</strong>可以暂时概述一下C++中左值和右值的概念。从性质上来看，当一个对象做右值时，我们使用的是这个对象的内容；当一个对象做左值时，我们使用的是它在内存中的位置。<br>      应用：表达式中有的位置需要的是左值，有的位置需要的是右值。表达式的值本身也有左右的分别。<br>      赋值运算符中左侧操作数和表达式结果都是左值。<br>      取地址符的操作对象是左值，得到的是右值。<br>      解引用、下标运算符的求值结果是左值。<br>      decltype作用于表达式时，如果表达式的结果是一个左值，decltype会返回一个引用类型。<br><br><strong>      知识点3：P122，4.1.2，优先级和结合律</strong><strong>（英文版137页）</strong><br>1.优先级 复杂表达式中一个运算对象连接多个不同运算符时，哪个运算符优先级高，就先计算哪个运算符和对象作用后的值。<br>      2.结合律 复杂表达式中一个运算对象连接多个优先级相同的运算符时，根据这一优先级对应的结合律，按从右至左或者从左至右的顺序计算表达式的值。<br>     如3+2*4-7；这个表达式是一个复杂表达式，因为表达式里*号优先级比较高，所以先计算2*4，得到3+8-7；得到的新表达式更简洁了，只剩下+-两个符号，这两个符号优先级相同，因此查看这个优先级对应的结合律可知这一级别的符号满足左结合性。因此从左向右计算，得到11-7；进一步得到结果4。<br><br><strong>知识点4：P123，4.1.3，求值顺序</strong><strong>（英文版138页）</strong><br> 一个表达式里如果运算对象都是函数返回的，都需要计算求值才知道对象的状态，函数调用符号优先级右一致，中间隔着几个优先级低的其他符号连接操作对象，比如int a=f()+g();这时候是函数f()先被调用还是g()先被调用呢？答案是<strong>未定义</strong>。C++语法没有规定这种情况应该谁先谁后。就像下面的表达式++i+i++这个表达式中，优先级最高的表达式++i和i++中间隔着优先级低的运算符+，这是，关于++i先计算还是i++先计算，这是未定义的，而因为这个表达式先计算++i或先计算i++的结果不同，所以这条表达式是错误的。一个变量如果在同一个表达式里被多次改变，这个表达式的求值顺序又不一定，就会出现二义性。应该避免这样的写法。<br>       目前只有四种运算符明确规定了求值顺序。<br>       1.逻辑运算符&amp;&amp;和||：这两个运算符先计算左边操作数的值。<br>       2.条件运算符?: ：条件运算符先计算？前的表达式，并求值，之后对视情况对：左右侧的表达式求值。<br>        3.逗号运算符， ：这个运算符的求值顺序是从左至右。<br><br><strong> 知识点5：关于运算符，左值和右值的归纳</strong><strong>（英文版140页往后）</strong><br> 本章各种运算符形成的表达式所返回的值的属性和运算符需要的操作数的属性如下：<br>      算数/逻辑/位运算符：  操作对象和结果都是右值   <br>      赋值运算符：左侧的操作对象必须是可以修改的左值，右侧的操作对象是右值，返回一个左值。                                                                                                                                                  <br>      递增/递减运算符：  前置版本的++/--返回左值，后置版本的++/--返回右值。操作对象都必须是左值。<br>      箭头成员访问运算符： 作用于指针，表达式结果是一个左值。<br>      点成员访问运算符:  这个成员所属的对象是左值，结果就是左值；这个成员所属的对象是右值，结果就是右值。                                                                                                                                                                   <br>      条件运算符： 条件运算符的三个表达式都是左值或者都能转化成左值类型时，结果为左值；否则是右值。<br><br><strong>知识点6：P125，4.3，除法和取模的结果 </strong><strong>（英文版141页）</strong><br>      两个非浮点型变量/字面值相除，结果还是原来的类型，不会有原来操作数是整数，运算之后结果是小数的情况。<br>        C++11中， 对于除运算符，结果向零取整（直接切掉小数部分，得到的数就是结果）。对于取模运算符，结果的符号和被除数的符号一致。（之前的语法标准里除法的结果可以选择是否向零取整，求模（模就是余数）运算可选符号）<br><br><strong>知识点7：P136，4.8，位运算符</strong><strong>（英文版152页）</strong><br> 左移运算符移动二进制数后会在右侧插入零，右移运算符在处理有符号类型的操作数（尤其是带负号的）时具体行为由环境决定。<br><br><strong>      知识点8：P139，4.9，sizeof运算符</strong><strong>（英文版157页）</strong><br> sizeof运算符有两种用法，第一种是sizeof后面直接加一条表达式语句；第二种形如sizeof (类型名)；第二种形式后会得到该类对象所占空间的大小。第一种形式中，如果表达式是指针类型，sizeof运算符会返回指针本身的大小。当有一个类名叫data，类中有一个成员叫做student时，可以使用作用域标识符和sizeof联动，使用sizeof(data::student);就可以计算出student占字节数。<br><br><strong> 知识点9：P141，4.11，隐式类型转换</strong><strong>（英文版159页）</strong><br> 概述：在C++中，一些类型可以按照一定规则互相转换，很多时候语境中需要使用两个或多个相同的类型才能继续运算。因此这时一种类型的值会被自动转换成另一个类型的值。这个过程就是隐式转换，其中算术隐式转换较为常见。<br>      主要的隐式转换发生的情况：<br><strong>1、</strong>大多数表达式中，比int小的类型会被提升为int型。<br><strong>2、</strong>在条件中，非布尔值要转化成布尔值。<br><strong>3、</strong>在初始化和赋值语句中，赋值符号的右侧对象的类型转换成左侧对象的类型进行运算。<br><strong>4、</strong>算术/关系运算中对象有有多种类型的，转化成同一类型。<br><strong>5、</strong>形参转化为实参的类型（第六章）。<br><strong>6、</strong>数组名会被转换为指针。<br><strong>7、</strong>0，nullptr会转为任何类型的指针。任何类型的指针都可以转化为（const）void *类型。<br><br>        对第四条算数转换时发生隐式转换的补充：<br>       再算术运算符的作用下，不同的操作数要转换成同一个类型才能够进行计算。以i+a；这个表达式举例，了解算术转换的方式。<br><strong>1、</strong>首先，当i和a的类型占字节比int小，如char、short，把他们转换为int型。如果他们原来类型的最大值在当前系统里大于int型最大值，则转化成unsigned int型。<br><strong>2、</strong>之后，如果i和a的类型相同，结束算数隐式转换，若i和a的类型不同，把占字节少的类型的对象转成占字节多的类型的对象。<br><strong>3、</strong>如果占字节多的带符号类型的最大值小于占字节少的带转换对象的最大值，带符号类型将被转换为无符号类型。<br><br><strong>知识点10：P144，4.11.3，显式转换</strong><strong>（英文版163页）</strong><br>      一个命名的强制类型转换具有以下形式：cast-name&lt;要转换成的类型&gt; （被转换的值）；其中，cast-name是四种强制类型转换：static_cast、dynamic_cast、const_cast和reinterpret_cast之中的一种。<br><strong>static_cast</strong>用于常见的强制类型转换。只要两个类型有关联，比如浮点数类型和整数类型，整数类型和布尔值类型，布尔值类型和指针类型，就可以使用static_cast。只是不能转换常量const到变量。<br><strong>const_cast</strong>用于去掉（或者加上）对象的底层const，要转换的类型和转换的类型都必须是指针或者引用类型。常用于将在第六章介绍的函数重载。当然，这个重载只能针对指针或者引用类型。<br><strong>reinterpret_cast</strong>依赖机器，是强行改变一个类型到另外一个不相干的类型。<br><b>dynamic_cast</b>支持运行时类型识别，在19章将会提到。<br><br><b>     第四章补充说明的内容：</b><br><b>1.运算符优先级列表的规律</b><b>：</b><br>     优先级和结合性是第四章的重要内容，因此第四章之后给出了完整的优先级和结合性的参考表。这里是有一定的规律的。<br>   1. 首先优先级最高的运算符都有这样的属性：单独拿出这个运算符左面的操作数和右面的操作数都没有意义。即运算符本身是连接两个名字组合一个概念的连接器。比如优先级最高的运算符::（作用域运算符），优先级比较高的点运算符（成员选择）下标运算符[]。<br>   2.比连接不同名字形成概念的这种运算符稍微低一级别的就是计算对象本身的运算符，比如++，--，类型转换，位求反，逻辑非，解引用，取地址，求类型占的字节数这些运算符大多都是单目元素符，他们的运算目的一般是根据操作数本身的属性进行计算或者改变操作数本身。<br>  3.算术运算符。<br>  4.逻辑运算符。<br>  5.条件运算符。<br>  6.赋值运算符 。<br>  7.复合赋值，抛出异常，逗号运算符等。<br><br><b>   本章英语重点专业词汇：</b><br><br><br><b>  1.运算对象                  operand</b><br><b>  2.结果                        result</b><br><b>  3.一元运算符               unary operator</b><br><b>  4.二元运算符               binary operator</b><br><b>  5.优先级                     precedence</b><br><b>  6.结合律                     associativity</b><br><b>  7.求值顺序                  order of evaluation</b><br><b>  8.提升                        promoted</b><br><b>  9.重载运算符               overloaded operator</b><br><b>  10.右值                      rvalue</b><br><b>  11.左值                      lvalue</b><br><b>  12.复合表达式            compound expression</b><br><b>  13.短路求值               short-circuit evaluation</b><br><b>  14.高位                      high order position</b><br><b>  15.逗号运算符            comma operator</b><br><b>  16.相互转换               conversion</b><br><b>  17.隐式转换               implicit conversion</b><br><b>  18.算术转换               arithmetic conversion</b><br><b>  19.整型提升               intergral promotion</b><br><b>  20.运算对象               operand</b><br><br><strong>      第五章是和语句有关的知识，语句也是C++的重要组分，本章由三部分组成：</strong><br><br><br><strong>1.语句的概念</strong>，包括简单语句和语句作用域的概念。<br><strong> 2.条件/循环/跳转语句</strong>,条件语句主要包括if/else语句、switc语句和：？表达式条件语句；循环语句则是for语句和while语句；跳转语句包括continue、break和goto语句。<br><strong> 3.try/throw和异常处理</strong>，包括异常处理的使用方法。<br><br><strong> 下面是这一章的知识点：</strong><br><br><br><strong> 知识点1：P155，5.2，语句作用域</strong><strong>（英文版174页）</strong><br>      用花括号括起来的块就是作用域的标志。在作用域中定义的对象只在作用域中起作用。块之外是没法访问和控制块内部的变量的。<br>      尤其是在switch语句中，switch的执行过程可能跨过一些标签，当标签里声明并定义了一个对象，这个对象的作用域就延伸到了所有case标签里，如果case 1定义了int a；switch执行了case2，这时这个我们不想执行的语句却产生了自己的作用域，这显然是不行的。因此可以在case标签后使用大括号形成块，这样就不会出现作用域的问题。<br>      goto也一样不能向前（代码的后几行）跳过对象的定义。不允许跨过变量的定义到达变量的作用域内。但是goto语句可以向后（代码的前几行）跳过定义。<br><br><strong>  知识点2：P172，5.6，try语句块和异常处理</strong><strong>（英文版194页）</strong><br> 可以用try\\throw和catch联动进行异常处理，形式如下：<br>      try<br>      {待检测块}    //待检测块里面包括throw语句来抛出异常<br>      catch (异常类型   异常对象的对象名)<br>      {异常处理语句 }<br>      catch （同上，可以写很多catch）<br>      {另一组异常处理语句}<br><br>      throw抛出异常和catch处理异常的头文件都在stdexcept里定义。抛出异常的语句形如：throw 异常类型（\"异常文本\"）；<br>      异常类型一般只支持赋值，初始化，调用成员函数.what之类的几种操作。<br><br><b> 本章英语重点专业词汇：</b><br><br><b>  1.控制流                  flow-of-control</b><br><b>  2.表达式语句            expression statement</b><br><b>  3.空语句                  null statement</b><br><b>  4.复合语句               compound statement</b><br><b>  5.悬垂else               dangling else</b><br><b>  6.case标签              case label</b><br><b>  7.引发（异常）        raise</b><br><b>  8.catch子句            catch clause</b><br><b>  9.异常处理代码        exception handler</b><br><b>  10.异常安全（这不是特别安全的意思，而是在异常情况下也能保证程序执行预期的正确行为）            exception safe</b>","updated":"2016-11-09T06:10:57.000Z","canComment":false,"commentPermission":"anyone","commentCount":0,"likeCount":8,"state":"published","isLiked":false,"slug":"23535827","isTitleImageFullScreen":true,"rating":"none","sourceUrl":"","publishedTime":"2016-11-09T14:10:57+08:00","links":{"comments":"/api/posts/23535827/comments"},"url":"/p/23535827","titleImage":"https://pic2.zhimg.com/v2-70c191f084755532a2a8366b7335e8e1_r.jpg","summary":"","href":"/api/posts/23535827","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":0,"likesCount":8},"23536587":{"title":"C++Primer第5版学习笔记（六）","author":"t.t.","content":"<strong>    第六章的重难点内容</strong><br><br><strong>  第六章是和函数有关的知识，函数就是命名了的代码块，可以处理不同的情况，本章内容包括：</strong><br><br><strong>      1.函数的概念基础</strong>，包括函数的定义声明以及函数如何生成值和返回结果。<br><strong> 2.函数重载</strong>,重载可以使函数接受不同种类或者数量不同的参数。<br><strong> 3.函数指针</strong>，指向函数的一类特殊指针。<br><br><strong> 下面是这一章的知识点：</strong><br><br><strong>      知识点1：P182，6.1，函数基础（英文版203页）</strong><br>      在调用函数时，第一步编译器会隐式的定义并初始化它的形参。比如一个函数void f(int a);形参int a会被用户传入的实参初始化，此时形参是实参的一个副本。当有多个形参时，形参对应的实参的求值顺序是不一定的。实参的类型必须和形参的类型一致或能转化为形参声明的类型。<br>     函数可以返回空值。返回函数指针和数组的特殊函数类型将在之后提到。<br><br><strong>      知识点2：P185，6.1.1，局部静态对象（英文版206页）</strong><br>      一个对象的名字有作用域，对象本身也有生命周期。名字的作用域是我们可以通过名字访问对象的的区间。相对的，生命周期是指对象的产生和销毁的过程。<br>      定义在所有函数外部的变量叫做全局变量，在整个程序的执行过程中一直存在。这种对象在程序启动时被创建，直到程序结束才会被销毁。<br>      定义在函数体内的对象或者函数的形参都是局部变量。当函数执行路径经过该对象的定义语句时才会自动开始创建该对象，在对应的块结束时，这个对象会被销毁。<br>      有时候我们有必要使局部变量的生命周期贯穿函数调用及之后的时间，所以我们可以将局部对象定义成static对象，定义语句形如static int a=1;这样我们就可以在程序的别的地方（只要是在这个static对象的作用域内访问它）操作这个局部静态对象。<br>      在一个程序中多次定义局部静态对象仍然是不被允许的。但是当一个函数里的对象被定义为局部静态对象，多次调用这个函数并不会重置这个局部静态对象的值。它自己会记得上一次被函数调用之后的值并继承这个值，不被第二次函数调用的变量定义初始化，这就是它<strong>静态</strong>的特性。<br><br><strong>     知识点3：P186，6.1.2，函数声明（英文版207页）</strong><br>     函数声明要在使用这个函数之前。规范的形式是通常放在头文件里。函数声明可以不写形参的名字，只写形参的类型。<br><br><strong>     知识点4：P189，6.2.2，传引用调用（英文版211页）</strong><br>     当函数的形参是一个引用类型的时候，在使用函数时，这个函数的引用形参就绑定在了传入的实参上，这种函数调用就叫做传引用调用。在函数涉及到一些比较大的类型对象作为参数的时候，通常地我们使用传引用调用，这样就可以避免实参初始化形参带来的拷贝。在C语言里经常传入指针避免拷贝，在C++里，一般使用引用。<br>     大多数情况下函数只能有一个返回值，因此在我们需要的时候，我们可以传一个引用的参数在函数里面。这样函数体内就可以改变引用的值进而改变函数外部被引用连接的对象的值，从而返回多个数值。<br><br><strong>     知识点5：P190，6.2.2，const形参和实参（英文版213页）</strong><br>     函数形参的类型也可以是带const的类型。当我们接受函数的参数是为了完成比较或者判断等操作，而不需要改变参数的值，我们应该使用带const的参数来确保参数不会被更改。另外，const类型的形参能比普通类型的形参接受更多种类的参数。比如void fn(const string&amp;);这个函数，字符串字面值是const char [ ]类型，因此fn这个函数接受字符串字面值。但是如果声明成了void fn(string&amp;);，那么这个函数就没有办法接受字符串字面值（类似：“string”这样的值就是字符串字面值）。另外，带const的形参也接受带底层const的对象。<br><br><strong>    知识点6：P193，6.2.4，想要传递数组作为参数（英文版215页）</strong><br>    又是我们想要向函数传递一个数组，但是数组是不可拷贝的，因此我们不能够通过值传递的方式传递一个数组到函数里，另外，如果数组的内容很大，传递数组的每个元素会带来不必要的拷贝。因此正确的做法有以下四种：<br><strong>0.</strong>以下的方法都基于或类似传递数组的指针。一维数组的指针指向数组的第一个元素。我们可以声明类似void pri(int*);void pri(int []);或者void pri(int [10]);的形式传递一个数组指针到函数。这三者是等价的。传递之后形参的类型都是int *类型。<br>      但是正因为数组的信息是以指针的形式传递给函数的，所以函数只得到一个地址，并不知道数组的大小，因此也就很容易访问到未定义的内存区域，因此在传递数组指针的基础上，我们可以通过手动标志数组大小等方法保证函数访问的内存是合法的不越界的。因此衍生出以下几种方法。<br><strong> 1.第一种方法：</strong>在数组的末尾加标记。<br>     这种方法类似于C风格字符串，末尾会自动加'\\0'来告诉大家这个字符串结束了。在数组末尾加特殊的标记来使数组不越界是简单易用的方法。<br><strong>2</strong><strong>.第二种方法：</strong>使用标准库规范中的begin和end函数。<br>     头文件iterator里有针对数组的begin和end函数，返回数组的首指针和尾后指针，指针指向数组元素的类型，这种方法也可以检测越界。<br><strong> 3</strong><strong>.第三种方法：</strong>传递一个表示数组大小的参数。<br>      这样构建函数时就知道数组有多大了。<br><strong>4</strong><strong>.第四种方法：</strong>传递数组的引用。<br>      除了使用指针，我们还可以使用引用来得到一个完整数组的引用（别名）。<br>      声明格式类似下面这种：void fx(int (&amp;arr)[10]);这里形参的名字是arr，arr前面的&amp;符号代表它是引用类型，引用了一个实参数组，这个数组必须只有10个元素（因为arr后面的[10]也是构成引用声明的必要部分。）<br><strong> 5.传递多维数组：</strong>有时我们也需要向一个函数传递多维数组。多维数组的实质是数组的数组，一维数组的名是指向数组元素的指针，二维数组是指向数组元素的指针的指针。因此想要一个函数传递多维数组的形参声明如下：void fx(int (*arr)[10]);这时arr指向有10个int型元素的数组。当我们把arr+1，它就又指向了新的10个元素，因此arr相当于二维数组的数组名（两者都是指向包含的一维数组首元素的指针）。<br>      也可以用int arr[][10]代替int (*arr)[10]，因为它们是等价的，都是二维数组名。用int arr[][10]这种方式定义形参时，要标出除了第一个维度以外的每个维度。（假设有一个数组int b[2][3]，就说明b有两列，每列3个元素，这里的2就是第一个维度。指向一维数组的指针不关心在这个维度上有几个元素，因此忽略）。<br><br><strong>    知识点7：P196，6.2.5，main函数的命令行选项</strong><strong>（英文版218页）</strong><br>    最开始我们使用UNIX或LINUX系统编程时经常使用没有图形界面的编译器来把写好的代码编译成obj文件，这时候我们使用命令行来编译一份源代码文件，我们需要在终端里输入类似“prog -d -o oflie data0”的命令行来进行命令行控制。<br>     现在我们看到的main函数一般都是int main()，括号里面什么也不写，我们也可以给main传递上述的那个命令行参数。形如：int main(int argc,char *argv[])  main可以什么参数也不接受，也可以接受一个int和一个指向字符串的指针这两个参数。main没有第三种形式了。<br>   int argc是表示后面的argv一共指向几个字符串用的。char *argv[] 里面的每一个字符串都顺序对应着命令行的参数。这些参数的字符串数组的第一个元素应该是可执行文件的名字或者空参数，最后一个字符串的值必须为0。有关命令行的更多选项和argv参数的具体用法，可以参照对应的编译器文档。<br><br><strong>   知识点7：P197，6.2.6，含有可变形参的函数</strong><strong>（英文版220页）</strong><br>   到现在我们定义的函数都是固定参数的，但是有时候我们无法预知向函数传递几个参数，又想使用一个函数接受这种变化，我们就可以使用C++指定的两种方法来定义含有可变形参的函数。<br>   第一种方法是当参数个数不一定，但是参数类型都相同时，我们可以传递一个initializer_list参数。这是标准库设施中的一部分。<br>   第二种方法在当我们想传递不确定个数的不同类型的实参时要使用的技术：可变参数模板。这个16章才介绍。<br>   其实还有一种方法使函数接受多种形参，不过这种方法多用于和C语言旧代码对接时使用。这个方法用省略符来传递可变数量的形参。<br><br><strong>     知识点8：P197，6.2.6，initializer_list</strong><strong>（英文版220页）</strong><br><strong>下面是关于定义可变形参函数的第一种方法——</strong><strong>initializer_list参数的介绍：</strong><br>     initializer_list类似vector，是一种容器，接纳一种同样类型的元素。initializer_list定义在&lt;initializer_list &gt;中，我们可以把任意数量，同样类型的参数传递给这个容器使函数能够处理多个元素。<br>     initializer_list支持的操作包括：<br>     initializer_list&lt;容器内元素的类型名&gt; 容器名   //默认初始化一个 initializer_list空容器<br>     initializer_list&lt;容器内元素的类型名&gt; 容器名{元素值1，元素值2，元素值2...}   //大括号初始化<br>     initializer_list 容器名1（已被定义的initializer_list 容器的容器名2 ）//使容器1的内容和容器二一致，两个容器共享容器二里面的元素。不会形成拷贝，（也可以用initializer_list 容器名1=initializer_list 容器名2）<br>     initializer_list 容器名.size()      //元素数量<br>     initializer_list 容器名.begin()   //指向首元素的迭代器<br>     initializer_list 容器名.end()      //尾后迭代器<br>     initializer_list里面元素的值永远是常量不能被更改，如果里面的元素是指针或饮用，这个元素的属性将被自动加上底层const。<br>    当我们声明一个接受 initializer_list类型的函数 void fa(initializer_list&lt;int&gt; list1);的时候，我们需要使用大括号来调用这个函数，形如fa({2,3,4});这样我们就向initializer_list传递了一个值的序列。<br>    我们也可以声明void fa(string b,initializer_list&lt;int&gt; list1);这种函数。<br><br><br><strong>     知识点9：P199，6.3，省略符形参</strong><strong>（英文版222页）</strong><br><strong>下面是关于定义可变形参函数的第二种方法——省略符形参的介绍</strong><br>     省略符形参有下列两种形式：<br>     void foo ( parm_list , ...); <br>     void foo ( ... );<br>     第一种形式为特定数目的形参提供了声明。在这种情况下，当函数被调用时，对于与显示声明的形参相对应的实参进行类型检查，而对于与省略符对应的实参则暂停类型检查。在第一种形式中，形参声明后面的逗号是可选的。如果没有逗号，相应地，就变成了第二种情况。<br>      你可以传递任意数量的参数给省略符形参。要注意省略号的优先级别最低，所以在函数解析时，只有当其它所有的函数都无法调用时，编译器才会考虑调用省略号函数的。 <br>      首先，如果要用省略符的方式处理不定参数的函数要包含头文件：#include &lt;stdarg.h&gt; （C语言中）或者#include &lt;cstdarg&gt;（C++中）。 然后利用va_list类型和va_start、va_arg、va_end 3个宏读取传递到函数中的参数值。用省略符处理不定参数的函数基于C语言的方法，在C++中不建议使用。（使用了C语言标准库功能varargs）。<br><br><strong>     知识点10：P202，6.3，返回值</strong><strong>（英文版226页）</strong><br>     在void返回值的语句最后会隐式地有return;语句，这时函数什么也不返回。函数可以返回一个引用作为左值。也可以返回一个花括号括起来的列表，来初始化vector等类型。main函数的return语句可以不写，编译器会带为隐式补充。<br><br><strong>     知识点11：P205，6.3.3，返回数组指针</strong><strong>（英文版229页）</strong><br>     虽然我们不能直接让函数返回一个数组，但是我们可以设定函数返回一个指针的类型。函数会返回数组的指针。返回数组指针的函数定义语句如下所示：数组元素类型 （*函数名 （参数列表））[ 数组大小 ]当然，返回一个临时量或者局部对象的引用/指针都是错误的行为，如果你在函数里普通地定义了一个数组，那么这个数组的生命周期在函数返回时就结束了，会被内存中释放，因此可能需要用static使这个数组静态。静态对象只是延长了对象的生命周期，但是无论如何在函数内部定义的对象在外部都无法访问，除非使用返回指针的方法。<br>     一条double (*func(int a))[10]这种语句来说明函数接受一个<strong>int a形参</strong>并且返回一个<strong>带有10个元素的double数组，</strong>这种语句在写法上比较乱，因此C++提供了尾置返回的方法让程序员不必要非要迁就编译器的理解能力，上一条语句等价于这样：auto func(int a)-&gt;double(*)[10]   我们使用-&gt;符号把返回值类型的描述放在了参数列表后面并和函数声明分离开让函数看起来不那么乱。<br>      我们也可以使用<strong>de</strong><strong>cltype</strong>语句返回数组指针。decltype后面的括号可以括起一个现有的数组推导数组类型。<br>我们再手动加*得到数组指针类型的返回值。在已有int  a[10];的情况下，我们可以使用decltype(a) *fn(int b)这种形式定义一个返回指向数组的指针的返回值类型。<br><br><strong>     知识点11：P207，6.4，函数重载</strong><strong>（英文版233页）</strong><br>     我们可以定义一组功能类似，函数名一致，但是接受的参数类型或数量不同的函数。定义多个这种函数就叫做函数重载。函数重载可以提供给我们用一个函数名处理多种参数形式的情况。<br>     定义重载函数要能重传入的参数里区别出实质不同的重载函数，如函数A的定义为int fa(const int a);和函数B int fa(int b);这两个函数函数名一样，形参类型不同，但仍然无法作为重载函数。因为我们传入一个int值时，fa不知道应该执行第一种还是第二种。所以只有参数顶层const属性不同的几个函数不是重载函数。<br>     当然，对于底层const，比如参数列表为<strong>const int *a</strong>的函数和参数列表为<strong>int a</strong>的函数能被看出不同，因为对于一个传入的const常量指针，这个实参只能初始化<strong>const int *a</strong>，不能被初始化<strong>int a</strong>。当同时有这两种形式的重载函数时，当传入一个非常量，IDE会优先选择为它匹配形参为int a版本的普通变量形参函数。<br><br><strong>     知识点12：P209，6.4，const_cast和函数</strong><strong>（英文版234页）</strong><br>     这里主要介绍const_cast类型强制转换是如何在函数中被使用的。在第四章第一次接触const_cast的时候我们提到过这个常被用于函数里。这里我们就看看怎么使用。<br>     之前说过，向函数传递参数时最好传递const型参数使其能够接受多种参数，这里我们可以在函数体内使用const再把参数变回普通的变量，这样就可以返回一个非const值了。<br><br><br><br><strong>      知识点13：P210，6.4，重载和作用域</strong><strong>（英文版234页）</strong><br>     声明变量时，变量的作用域就在块里，声明函数也一样，而且里层的作用域会隐藏外部的作用域。例子如下：<br>    {<br>        int a=0;    //这里是a的外层作用域<br>        {<br>              double a=1.2;   //外边已经有a了，这里又声明了一个a，因此这个a的作用域覆盖了前面的int a；<br>              cout&lt;&lt;a&lt;&lt;endl;      //输出的会是1.2<br>        }<br>     }<br>     函数声明也一样，<br>    {<br>        int fa(int b);    //这里是函数fa的外层作用域<br>        double fa(double b);    //重载了函数fa使它能够接受double<br>        {<br>              double fa(string &amp; c);  //外边已经有fa了，这里又声明了一个fa，因此这个fa的作用域覆盖了前面的;<br>              fa(2.3);    //错误，原型为double fa(double b)的函数声明作用域被double fa(string &amp; c);覆盖，匹配不到函数<br>        }<br>     }<br><br><strong>     知识点14：P211，6.5.1，默认实参</strong><strong>（英文版236页）</strong><br>     有时候一些函数我们每次调用它总会向它传递一些特殊的值。我们可以声明带有默认实参的函数。默认实参如果没有明确说明，默认实参会被自动当做函数的初始值传递进去。<br>     形如int fn(int a,int b=2,double c=3.3)这样定义函数头的方式就给了b和c默认的实参，注意，当一个形参被给了默认实参，它后面的所有参数都要有默认实参才行。<br>     当我们想使用默认实参的时候，只要调用函数的时候使用这种对应的实参就行了，默认实参会用来填补缺少的尾部实参，上面的定义的函数如果这么调用：fn(1,2);double c的值会被自动设为3.3。书写这种函数时要尽量保证要经常用到的默认实参放在参数列表的更后面一点，这样才合理。<br>     可以只在函数声明里标注默认实参不在函数定义里这样写，结果仍然将是正确的。void fn(int = 1, int = 2, int =3);这种函数声明语句省略了形参的名字，不过也是可以的。<br>     局部变量不能做默认实参，默认实参的定义在函数体之外。另外，默认实参是可以在名字的作用域内通过名字更改的。<br><br><strong> 知识点15：P213，6.5.2，内联函数（英文版238页）</strong><br> 有时我们要频繁调用一个优化规模小，流程直接，频繁被调用的函数，定义函数时我们可以在返回值类型前面加上关键字inline使它成为内联函数，减少运行时的开销。<br><br><strong>   知识点16：P214，6.5.2，constexpr函数（英文版239页）</strong><br> 这是一种能够被用在常量表达式的函数，但是函数的返回值类型和形参类型必须都是字面值。函数体中必须有且只有一条return语句，constexpr函数被隐式的指定为内连函数。const函数中也可以有类型别名，使用作用域声明等不执行操作的其他语句。这里没有赋值，没有构建对象。同时constexpr可以返回计算后的结果。如constexpr int fn(int a){return a+22;}，这条定义是正确的，前提是调用函数这个函数fn时，传入的实参是一个常量。比如fn(3);<br><br><strong>知识点17：P215，6.5.3,调试帮助（英文版240页）</strong><br>  程序员在写程序时可能涉及到一些调试中的代码，这些代码只在开发程序时使用，当即将发布程序的时候，要暂时屏蔽掉正在调试中的代码。C++提供了assert和NDEBUG两个预处理功能屏蔽测试代码。<br>    assert这个宏定义在cassert头文件中，assert使用一个表达式作为它的条件，形如assert(expr);首先对expr或者表达式求值，如果结果为真（非0），那么assert什么都不做。如果结果为假(表达式值为0)，那么assert输出信息并且终止程序的执行。<br>    assert经常用于处理不能发生的条件，如果你写了一段代码，代码没测试越界，你就可以用assert，当它越界了我们就结束程序的执行。<br>    NDEBUG宏定义可以影响assert的行为，这个默认是没被定义的。当我们宏定义了NDEBUG，就屏蔽掉了assert的功能。<br>    此外，IDE还提供了__FILE__(这里是两个英文下划线，这个存放文件名) 、__func__（这个存放所在的函数名)  、 __LINE__（这个存放所在的行数)  、__TIME__（这个存放调试的时间)  、 __DATE__（这个存放调试的日期)  这五种静态数组来提供错误信息。<br><br><strong>    知识点18：P217，6.6,函数匹配（英文版242页）</strong><br>  程序员定义重载函数之后就可以使用它们了，挑选到底使用哪个版本的函数是一个过程，这个过程叫做函数匹配。<br><strong>1、</strong>函数匹配的第一步是在调用时先找与与调用函数同名的函数名。且调用点在函数作用域内。这一步筛选出的函数叫做<strong>候选函数。</strong><br><strong>    2、</strong>函数匹配的第二步是从候选函数中选择出能够被本次函数调用的实参传入的函数，函数名一致的前提下还要求函数的形参个数和实参一致，实参能够转化成（或者就是）形参规定的类型。这一步筛选出的函数叫做<strong>可行函数。</strong><br><strong>  3、</strong>寻找<strong>最佳匹配</strong>。当有int fn(int a);和int fn(double a,double b=1.0)时，我们调用函数fn形如fn(3.4);显然这两种函数都是可行函数，这是我们再寻找最佳的匹配，因为fn(3.4);对应fn(double,double=1.0);的话无需转化，因此是最佳匹配。当有多个最佳匹配的时候函数将停止调用。<br><br>      为了划分最佳匹配的各种情况，编译器将实参类型到形参类型的转换划分为几个等级，具体排序如下所示：<br><strong>1.精确匹配：</strong><br>       精确匹配可以包含以下情况：数组名转化成数组指针的匹配，函数类型转换成函数指针的匹配，实参类型与形参类型相同。另外，像实参添加顶层const或者忽略实参赋值给形参的顶层const也属于精确匹配。<br><strong>2.通过指针的转换把</strong><strong>非常量指针转换成常量指针。</strong><br><strong>3.通过类型提升实现的匹配。</strong><br><strong>4.通过算数类型转换或指针转换实现的匹配</strong><br><strong>    5.通过类类型转换实现匹配（类类型转换还没有讲）</strong><br>      要注意小整数字面值会被自动转换成int，而带小数点的字面值会被默认转换成doube。<br><br><strong>    知识点19：P221，6.7，函数指针（英文版248页）</strong><br> 声明一条函数指针的语句如下: int (*PtrOfFunc)(参数列表)，其中PtrOfFunc就是指向函数的指针。我们可以把函数名赋值给定义的函数指针的名字。<br>    返回函数指针的形参定义为 double(*fn(int a)) (int d,char b);这里声明的函数是fn，函数的形参是int a，返回值是函数指针类型的，返回的函数指针对应的函数的返回类型是double，参数是int d,char b。<br>     和处理数组一样，我们也可以使用尾置返回来返回一个函数指针，尾置返回函数指针的声明是auto fn(int a)-&gt;double (*)(int d,char b);尾置返回适合用来返回复杂的类型比如数组，函数指针等等。<br>    遇到double(*fn(int a)) (int d,char b);这种复杂的表达式，应该以定义的变量名为中心，从里往外一层层往外扩展。这个函数的定义语句里面，fn就是其中的变量名，看它右侧，有（int a）,这（int a）是一个形参列表。因此得出结论fn的本质是一个函数，再看左侧，*代表这个函数返回一个指针，这个指针的类型在更外层（double (*) (int d,char b)）型。<br>    当然这种声明/定义容易让人心累，所以这种情况下使用auto fn(int a)-&gt;double (*)(int d,char b)是不错的选择。如果这样还是觉得太长了，可以使用typdef，USING等重命名语句加上decltype推导。比如tpyedef double func (int d,char b);这样的语句之后，func就是一个函数类型。<br>也可以使用tpyedef decltype(fn) func2;这条语句等价于上面的语句。对于using语句，using Func2 = double  (int d,char b);即可。可见typedef和using的替换原则是不同的，在涉及到复杂类型的时候，类似数组，函数指针，tpyedef的替换名要和被替换的类型一起被声明。<br><br><b>   本章英语重点专业词汇：</b><br><b>    1.函数                               function</b><br><b>   2.形参                               parameter</b><br><b>   3.调用运算符（一个动作）  call operator</b><br><b>   4.实参                               argument</b><br><b>   5.主调函数                        calling function</b><br><b>   6.被</b><b>调函数                        called function</b><br><b>   7.生命周期                        lifetime</b><br><b>   8.局部变量                        local variable</b><br><b>   9.自动对象                        automatic object</b><br><b>   10.局部静态对象               local static object</b><br><b>   11.函数原型                     function prototype</b><br><b>   12.分离式编译                  separate compilation</b><br><b>   13.可执行文件                  executable file</b><br><b>   14.引用传递                     passed by reference</b><br><b>   15.传引用调用                  called by reference</b><br><b>16.值传递                        passed by value</b><br><b>   17.传值调用                     called by value</b><br><b>   18.重载                           overloaded</b><br><b>   19.函数匹配                     function matching</b><br><b>   20.重载确定                     overloaded resolution</b><br><b>   21.最佳匹配                     best match</b><br><b>   22.二义性调用                  ambiguous call</b><br><b>   23.默认实参                     default argument</b><br><b>   24.预处理宏                     preprocessor marco</b><br><b>   25.候选函数                     candidate function</b><br><b>   26.可行函数                     viable function</b><br><b>   27.递归循环                     recursion loop</b><br><b>   28.递归函数                     recursive function</b><br><b>   29.尾置返回类型               trailing return type</b>","updated":"2016-11-09T06:32:06.000Z","canComment":false,"commentPermission":"anyone","commentCount":1,"likeCount":5,"state":"published","isLiked":false,"slug":"23536587","isTitleImageFullScreen":true,"rating":"none","sourceUrl":"","publishedTime":"2016-11-09T14:32:06+08:00","links":{"comments":"/api/posts/23536587/comments"},"url":"/p/23536587","titleImage":"https://pic3.zhimg.com/v2-ce469eb472d802e0c0e117e45e0da9ca_r.jpg","summary":"","href":"/api/posts/23536587","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":1,"likesCount":5},"23761747":{"title":"C++定级赛 1：基本类型与变量","author":"t.t.","content":"<h1>C++定级赛 1：基本类型与变量</h1><p><b>考试时间：120分钟。</b></p><h2>一、单向选择题（每题2分,共21题，共42分）</h2><p>1.  以下4个IO对象中，哪个IO对象的读（写）不经过缓冲，直接和标准输入（输出）设备做关联？                                         （ ）</p><p>A.  cin          B. cout          C. cerr           D.clog</p><p>2.  以下四个独立的输出语句中，哪个语句不会进行输出这个行为？     （ ）                          </p><p>A. \nstd::cout\n&lt;&lt; \"/*\";</p><p>B. \nstd::cout &lt;&lt;\n\"*/\";</p><p>C. \nstd::cout\n&lt;&lt; /* \"*/\" */;</p><p>D. \nstd::cout\n&lt;&lt; \"/*\"; std::cout &lt;&lt; \"*/\";</p><p>3.  以下语句中条件语句的条件在什么时候为假？                     （ ）</p><p>int test;if(std::cin\n&gt;&gt; test){};</p><p>A.  输入3.14</p><p>B.  输入0</p><p>C.  输入-1</p><p>D.  输入X</p><p>4.  C++11/14标准中，short，int，long，long long，bool，char的最小尺寸分别是多少位(byte(s))？                                      （ ）</p><p>A.  8,16,32,64,1,8</p><p>B.  8,16,32,64,未定义,8</p><p>C.  16,16,32,64,未定义,8</p><p>D.  16,16,32,64,1,8</p><p>5.  C++11/14标准中，float类型的精度至少能达到小数点后（\n）位，double/long double类型的精度至少能达到小数点后（ ）位。实际上大多数编译器支持的float类型的精度为精确到小数点后（ ）位，double类型的精度通常为精确到小数点后（\n）位。</p><p>A.  6，10，8，12</p><p>B.  6，10，7，16</p><p>C.  8，12，10，16</p><p>D.  8，12，13，24</p><p>6.  执行赋值语句 unsigned i = -1;之后，i的值为（ ）；假定在某个电脑上int类型能表示的最大值是<a href=\"tel:2147483647\">2147483647</a>，执行赋值语句int i= 2147483648;之后，i的值为（ ）。</p><p>A.  i能表达的最大值，未定义</p><p>B.  i能表达的最大值，-1</p><p>C.  未定义，未定义</p><p>D.  未定义，-1</p><p>7.  unsigned a = 0;int b = -1;表达式a+b的值的类型为（ ）。</p><p>A.  int</p><p>B.  unsigned</p><p>C.  如果当前环境下int类型所占位数大于unsigned，则用int，否则用unsigned</p><p>D.  如果当前环境下int类型所占位数大于等于unsigned，则用int，否则用unsigned</p><p>8.  字符字面值中\\后面最多可以加（\n）个数字，\\x后面最多可以加（ ）个数字。</p><p>A.  2个，无限多个（不过超出3位的数字会被当作字符）</p><p>B.  2个，3个</p><p>C.  由当前机器char型的大小决定，3个。</p><p>D.  由当前机器char型的大小决定，无限多个（不过超出3位的数字会被当作字符）</p><p>9.  int大小为32bytes时，数字字面值<a href=\"tel:2147483648\">2147483648</a>的类型为（ ），数字字面值0x80000000的类型为（\n）。</p><p>A.  long ,unsigned int</p><p>B.  unsigned int,long</p><p>C.  long,long</p><p>D.  unsigned int,unsigned int</p><p>10.以下四种初始化语句中，哪种策略是错误的？                     （ ）</p><p>A.  int a(0.5);</p><p>B.  int a{0.5};</p><p>C.  double a(1);</p><p>D.  double a{1};</p><p>11.以下四种情况下，没有发生初始化的情况是                       （ ）</p><p>A.  函数体内定义了string类型的变量，但是没有指定初始值。</p><p>B.  函数体内定义了int类型的变量，但是没有指定初始值。</p><p>C.  函数体外定义了string类型的变量，但是没有指定初始值。</p><p>D.  函数体外定义了int类型的变量，但是没有指定初始值。</p><p>12.下面程序中局部变量j的值是多少？</p><p>int i = 10;int j = 5;</p><p>int main()</p><p>{<br>\n    int i=50; int j=60;</p><p>   \ni+=::i;   j+=j;   j+=i; \n return 0;</p><p>}                                                          \n （ ）</p><p>A.  220</p><p>B.  30</p><p>C.  165</p><p>D.  180</p><p>13.下面几个相互独立的语句中语法正确的是？                       （ ）</p><p>A.  int &amp;ref;</p><p>B.  const int &amp;ref = 1024;</p><p>C.  int &amp;ref = 1024;</p><p>D.  const int a = 1024;int\n&amp;ref = a;</p><p>14.下面几个相互独立的语句中语法正确的是？                       （ ）</p><p>A.  char *e=\"1234\";</p><p>B.  const int a=13;int *b = &amp;a;</p><p>C.  int a = 123;double &amp;b = a;</p><p>D.  int a = 123;const double\n&amp;b = a;</p><p>15.以下代码运行后的输出应该是怎样的？                            （ ）</p><p>#include\n&lt;iostream&gt;</p><p>using namespace\nstd;</p><p>int main()</p><p>{</p><p>const char *p[2][3] = {\"Too\",\"Young\",\"Simple\",\"Sometimes\",\"Naive\",\"Excited\"};</p><p>cout &lt;&lt;\n(*(*(p+1))[2])&lt;&lt; \":\";</p><p>cout &lt;&lt; ((p[1][1])+2)&lt;&lt; \":\";</p><p>cout &lt;&lt; *(*(*(p + 1))+1);</p><p>return 0;</p><p>}</p><p>A.  E:i:o</p><p>B.  E:ive:o</p><p>C.  u:ung:S</p><p>D.  u:u:S</p><p>16.如何在cpp文件A中访问cpp文件B中定义的const变量？\n        （ ）</p><p>A.  定义变量时需要在定义前加关键字extern（文件A中）,使用变量时需要在声明前加关键字extern（文件B中）。</p><p>B.  定义变量时不用在定义前加关键字extern（文件A中）,使用变量时需要在声明前加关键字extern（文件B中）。</p><p>C.  定义变量时需要在定义前加关键字extern（文件A中）,使用变量时在不用声明前加关键字extern（文件B中）。</p><p>D.  定义变量时不用在定义前加关键字extern（文件A中）,使用变量时不用在声明前加关键字extern（文件B中）。</p><p>17.下面哪个定义语句是合法的？ \n                                （\n）</p><p>A.  int *p1,*const p2;</p><p>B.  const int i = -1, &amp;r =\n0;</p><p>C.  const int &amp;const c;</p><p>D.  const int ic, &amp;r = ic;</p><p>18.下面几个语句中语法正确的是？ \n                               （ ）</p><p>A.  constexpr int *q = nullptr;const\nint *p=q;</p><p>B.  const int a = -1;constexpr\nconst int *q=&amp;a;</p><p>C.  constexpr string a =\n\"1024\";</p><p>D.  constexpr int *p = &amp;a;p\n= &amp;b;//a.b为整形全局变量</p><p>19.下面几个语句中语法正确的是？ \n                               （\n）</p><p>A.  using CHARSTAR = char*;char\nc = 'a',d='b';</p><p>const CHARSTAR b\n= &amp;c;b = &amp;d;</p><p>B.  typedef char* CHARSTAR;char\nc = 'a',d='b';</p><p>const CHARSTAR b\n= &amp;c;b = &amp;d;</p><p>C.  typedef double a, *b;a i= 2; b j= &amp;i;</p><p>D.  typedef a double;</p><p>20.以下程序的输出会是哪种结果？ \n                               （\n）</p><p>#include &lt;iostream&gt;</p><p>using namespace std;</p><p>int func() { cout &lt;&lt;\n\"1\"; return 1; }</p><p>int main()</p><p>{auto a = func();decltype(func())\nb;return 0;}</p><p>A.  1</p><p>B.  11</p><p>C.  111</p><p>D.  10</p><p>21.以下四种描述哪个是正确的？                                   （ ）</p><p>A．const int i = 0;const int &amp;ri =\ni;auto a = ri;此时a的类型也为const int。</p><p>B．const int i = 0; auto e = &amp;i;此时e的类型为int *const。</p><p>C．int i = 0; const auto e = &amp;i;auto\nconst r = &amp;i;此时e和r的类型是相同的。</p><p>D．int i = 0; const int ci = i; auto\n&amp;n = i, *p2 = &amp;ci;语句中自动推导出的类型是const int。</p><h2>二、填空/简答题（每题4分,共7题，共28分）</h2><p>1. 当从键盘上向程序输入数据时，对于如何指出文件已经结束，不同的操作系统有不同的约定。在Windows系统中，输入文件结束符的方法是____________，然后按下回车键；在UNIX系统中，输入文件结束符的方法是____________，然后按下回车键。</p><p>2. 分别写出下列字面值的类型。</p><p>   3e1L         ___________</p><p>   3U           ___________</p><p>   U'3'         ___________</p><p>   \"1234\"       ___________</p><p>3. 下面是一些C++的标识符，在你认为正确的标识符后面打√，在你认为不正确的标识符后面打×。</p><p>   第一个标识符：_                                             （  ）</p><p>   第二个标识符：__                                            （  ）</p><p>   第三个标识符：Double                                        （  ）</p><p>   第四个标识符：decltype                                      （  ）</p><p>4.指针本身是一个对象，它也可以指向另外一个对象。因此，指针本身是不是一个常量以及指针所指的是不是一个常量就是两个相互独立的问题。用名词_____________表示指针本身是一个常量；用名词_____________表示指针所指的对象是一个常量。</p><p>5. const int i = 42;</p><p>auto j = i; const auto\n&amp;k = i; auto *p = &amp;i;</p><p>const auto j2 = i, &amp;k2 =\ni;</p><p>   其中，j的类型是__________。k的类型是___________。p的类型是___________。k2的类型是___________。</p><p>6.  const int ci = 0,&amp;cj =\nci,*p=&amp;ci;</p><p> decltype(ci) x = 0;</p><p> decltype((ci)) y = 0;</p><p> decltype(cj) z = x;</p><p> decltype(*p) o=ci;</p><p>   其中，x的类型是________。y的类型是_________。z的类型是__________。</p><p>   o的类型__________。</p><p>7.读程序，写输出结果。</p><p>   int a = 1,b = 4;</p><p>    decltype(a) c = a;</p><p>    decltype((b)) d = a;</p><p>    ++c; ++d;</p><p>    cout &lt;&lt; a &lt;&lt; b\n&lt;&lt; c &lt;&lt; d;</p><p>   __________________________</p><h2>三、编程题（每题10分,共3题，共30分）</h2><p>1.编写一个函数，函数原型为void func(int N);这个函数的功能为可以接受N个学生的学号和成绩的输入，输出高于平均成绩的学生的学号和成绩，其中学号和成绩均为整数，不允许使用数组/结构体数组/容器。</p><p>2.编写一个函数，函数原型为void func(int arr[],int n);arr为整型数组指针，n为数组元素个数。函数实现的功能就是\n用你能想到的时间复杂度最低的方法对这个数组进行从小到大排序并输出。</p><p>3. 编写一个程序，求方程ax^2+bx+c=0的根,a,b,c均为变量。 </p><br><p>答案（你们看不到我（逃）</p><p>一、选择题</p><p>1.C   2.C   3.D   4.C   5.B</p><p>6.A   7.C   8.D   9.A   10.B</p><p>11.B  12.D  13.B  14.D  15.B</p><p>16.A  17.B  18.A  19.C  20.A</p><p>21.C</p><p>二、填空/简答题</p><p>1.输入Ctrl+Z，输入Ctrl+D</p><p>2.long double,unsigned,char32_t,const char*</p><p>3.√√√×</p><p>4.顶层const，底层const</p><p>5.int,const int&amp;,const int*,const int&amp;</p><p>6.const int,const int&amp;,const int&amp;,const int&amp;</p><p>7.2422</p><br><p>三、编程题</p><p>1.</p><p>#include &lt;iostream&gt;</p><p>using namespace std;</p><br><p>void studentInfo(int N);</p><br><p>struct ListNode</p><p>{</p><p>\tint Data = 0;</p><p>\tListNode *next = nullptr;</p><p>};</p><br><p>ListNode *headNoOfStu = new ListNode;</p><p>ListNode *headGradeOfStu = new ListNode;</p><br><p>int main()</p><p>{</p><p>\tconst int N = 3;</p><p>\tstudentInfo(N);</p><br><p>\treturn 0;</p><p>}</p><br><p>void studentInfo(int N)</p><p>{</p><p>\tdouble SumOfGrade = 0.0,AVGGrade=0.0;</p><br><p>\tListNode *thisNo = headNoOfStu, *thisGrade = headGradeOfStu;</p><p>\tfor (int i=0;i&lt;N;++i)</p><p>\t{</p><p>\t\tint NoS = 0, GradeS = 0;</p><p>\t\tcout &lt;&lt; \"请输入学号：\" &lt;&lt; endl;</p><p>\t\tcin &gt;&gt; NoS;</p><p>\t\tcout &lt;&lt; \"请输入成绩：\" &lt;&lt; endl;</p><p>\t\tcin &gt;&gt; GradeS;</p><p>\t\tSumOfGrade += GradeS;</p><br><p>\t\tthisNo-&gt;Data = NoS;</p><p>\t\tthisGrade-&gt;Data = GradeS;</p><br><p>\t\tthisNo-&gt;next = new ListNode;</p><p>\t\tthisGrade-&gt;next = new ListNode;</p><br><p>\t\tthisNo = thisNo-&gt;next;</p><p>\t\tthisGrade = thisGrade-&gt;next;</p><p>\t}</p><br><p>\tAVGGrade = SumOfGrade / N;</p><br><p>\tthisNo = headNoOfStu; thisGrade = headGradeOfStu;</p><br><p>\tcout &lt;&lt; endl;</p><p>\tfor (int i=0;i&lt;N;++i)</p><p>\t{</p><p>\t\tif (thisGrade-&gt;Data&gt;AVGGrade)</p><p>\t\t{</p><p>\t\t\tcout &lt;&lt; \"学号：\" &lt;&lt; thisNo-&gt;Data &lt;&lt; \"成绩：\" &lt;&lt; thisGrade-&gt;Data &lt;&lt; endl;</p><p>\t\t}</p><br><p>\t\tthisNo = thisNo-&gt;next;</p><p>\t\tthisGrade = thisGrade-&gt;next;</p><p>\t}</p><br><p>\tthisNo = headNoOfStu; thisGrade = headGradeOfStu;</p><p>\tfor (int i=0;i&lt;N+1;++i)</p><p>\t{</p><p>\t\tListNode *No = thisNo-&gt;next;</p><p>\t\tListNode *Grade = thisGrade-&gt;next;</p><p>\t\tdelete thisNo;</p><p>\t\tdelete thisGrade;</p><br><p>\t\tthisNo = No; thisGrade = Grade;</p><p>\t}</p><p>}</p><p><img src=\"v2-1c0d0137136b83346b87cb0ba22badbf.jpg\" data-rawwidth=\"623\" data-rawheight=\"669\"><img src=\"v2-02d6701af175cacede710dfbe6cfad9c.jpg\" data-rawwidth=\"903\" data-rawheight=\"1217\">编程题的第一题中，我原来的解法是不太合适的，感谢<a href=\"https://www.zhihu.com/people/e35e111b7fd5e8b9c9f9304ab277e40c\" data-hash=\"e35e111b7fd5e8b9c9f9304ab277e40c\" class=\"member_mention\" data-hovercard=\"p$b$e35e111b7fd5e8b9c9f9304ab277e40c\">@孙明琦</a>的指导。现在已经在这里更新了一个基于链表的答案。这道题原来是一个考研的考试题来着。</p><br><br><p>（其他略）</p>","updated":"2016-11-18T04:13:24.000Z","canComment":false,"commentPermission":"anyone","commentCount":21,"likeCount":26,"state":"published","isLiked":false,"slug":"23761747","isTitleImageFullScreen":true,"rating":"none","sourceUrl":"","publishedTime":"2016-11-18T12:13:24+08:00","links":{"comments":"/api/posts/23761747/comments"},"url":"/p/23761747","titleImage":"https://pic2.zhimg.com/v2-b4a5db8b8a9af5eefa0859e6ccd013d1_r.jpg","summary":"","href":"/api/posts/23761747","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":21,"likesCount":26},"24392334":{"title":"A*算法可视化","author":"t.t.","content":"经常有人说，数据结构和算法抽象难以理解，尤其是一些涉及多种复杂结构的算法，初学者很难在脑内脑补算法的执行方式。因此我做了一款算法可视化应用。这样就可以直观地看电脑怎么寻径的了。有Win32和安卓两个版本。项目地址<a href=\"https://github.com/TiriSane/Visually-Algorithm\" class=\"\">https://github.com/TiriSane/Visually-Algorithm</a><br><br><p>只做了一点工作，感谢业界各位这么抬爱。虽然现在我遇到的唱衰C++技术栈的人多一点，但看得出来还是有很多人打心眼里喜欢这种比较直觉自然的语言。最近要考试了没什么时间，不过正好最近有一个很初级的架构方面这么个东西可以聊聊，可能近期还是会分享一些这方面的独特的项目经验给大家。再次感谢。</p><br><img src=\"v2-33029d6708ab9e6902607c9a9038f77f.jpg\" data-rawwidth=\"1284\" data-rawheight=\"770\"><img src=\"v2-469c7dcbc2bfd5ec40a72aea384ffecf.jpg\" data-rawwidth=\"1284\" data-rawheight=\"770\">","updated":"2016-12-15T12:31:01.000Z","canComment":false,"commentPermission":"anyone","commentCount":9,"likeCount":237,"state":"published","isLiked":false,"slug":"24392334","isTitleImageFullScreen":false,"rating":"none","sourceUrl":"","publishedTime":"2016-12-15T20:31:01+08:00","links":{"comments":"/api/posts/24392334/comments"},"url":"/p/24392334","titleImage":"https://pic4.zhimg.com/v2-1bd666ed4ba3f281532bd67146284aa3_r.jpg","summary":"","href":"/api/posts/24392334","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":9,"likesCount":237},"25821861":{"title":"我可能是做了假炉石","author":"t.t.","content":"最近学了一下libSVM的基础用法，嗯，很基础的那种，原理什么的数学不太好真心不能手写一个啊，然后加上一个垃圾估值网络，我就可以开心的复（山）刻（寨）自己喜欢的游戏——炉石传说了。<p>一共有两个模式，左边的是训练，右边的是使用你训练出的AI对战。是不是很简单（逃</p><p><img src=\"v2-d96c8906886ff705e1d08a41d2014c2f.png\" data-rawwidth=\"1284\" data-rawheight=\"770\">训练AI时，每次你的回合出牌之前，电脑都会问你你认为面对当前的局面，应该是选用站场策略还是解场策略，这样就可以简单地把问题划归为分类器问题啦！（然而还是存在很多问题，后面我们会提到。</p><p><img src=\"v2-109ef08cb1636770894ff467755baaf9.png\" data-rawwidth=\"1284\" data-rawheight=\"770\">这里先后手可能对游戏平衡性影响比较大，因为只搞了30张卡牌，所以先手优势可能比较明显。。。哭哭，下个版本重构这个项目（</p><p><img src=\"v2-fc3da59439f450a1e167540b928698f6.png\" data-rawwidth=\"1284\" data-rawheight=\"770\">AI的好处是算控场和斩杀还是很精准的，而且比人类快，不过策略啊，打combo啊，总归是逊色一点。另外随便写了个界面，操作手感也可能比较垃圾。比如选择手牌时点击右下角绿色确认键才能出牌。一次只能出一张牌，再想出牌还要点右下角手牌区域。比如使用随从时，按住左键，把这个随从拖拽到你的攻击目标上，才能完成攻击。当然也是因为代码写得太随性了（</p><p>不过这个思路我感觉还不错可以成为一些小白入门机器学习的练手项目（大神都知道，SVM并不太适合解决这种AI），毕竟入门就要从简单的出发，充分调动自己的兴趣，为了这个我可是把概率论线代复习了一遍什么的，也算是有进步。</p><p>好啦，多说无益，放码过来。代码在这里：<a href=\"https://github.com/TiriSane/CardLearning\" class=\"\" data-editable=\"true\" data-title=\"TiriSane/CardLearning\">TiriSane/CardLearning</a>。欢迎大家批评指教。</p>","updated":"2017-03-17T01:27:51.000Z","canComment":false,"commentPermission":"anyone","commentCount":29,"likeCount":173,"state":"published","isLiked":false,"slug":"25821861","isTitleImageFullScreen":false,"rating":"none","sourceUrl":"","publishedTime":"2017-03-17T09:27:51+08:00","links":{"comments":"/api/posts/25821861/comments"},"url":"/p/25821861","titleImage":"https://pic4.zhimg.com/v2-60927d2291744000f276cfda31667333_r.png","summary":"","href":"/api/posts/25821861","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":29,"likesCount":173},"27453583":{"title":"算法导论的编程实现","author":"t.t.","content":"<img src=\"v2-efb13209d7689daed2190a2b5f46eba8.jpg\" data-rawwidth=\"753\" data-rawheight=\"1085\"><br><p>为了学习算法，我们对《算法导论(第三版)》中算法和数据结构进行了多种语言的编程实现。</p><p>最开始感觉这本书很厚，有一些数学基础不好的同学在接触到里面复杂的数学证明之后直接就弃坑了。</p><p>不过这本书各个章节比较独立，既可以跳着看，也可以只看一个章节里自己关注的某些部分。</p><p>这里我们不关注算法设计、分析和数学证明。只是先来实现一遍书上总结好的算法和数据结构。这样尝试着之后我们发现，其实这本书里描述的已有的数据结构和算法不是看上去那么多，而且都是经典和正确的，可以每天零零碎碎的一小节一小节的掌握，日积月累，就对算法有的更深刻的认识。<br></p><p>当有足够集中的时间和数学素养之后，再集中看算法导论里的算法分析，设计和证明。</p><p>轻松看算法。每天都更新。</p><br>这个更新中的项目你可以在这里看到：<br><a href=\"https://github.com/TiriSane/CLRS_3rd_Edtion_in_Action\" data-editable=\"true\" data-title=\"TiriSane/CLRS_3rd_Edtion_in_Action\" class=\"\">TiriSane/CLRS_3rd_Edtion_in_Action</a>","updated":"2017-06-19T02:00:44.000Z","canComment":false,"commentPermission":"anyone","commentCount":5,"likeCount":20,"state":"published","isLiked":false,"slug":"27453583","isTitleImageFullScreen":false,"rating":"none","sourceUrl":"","publishedTime":"2017-06-19T10:00:44+08:00","links":{"comments":"/api/posts/27453583/comments"},"url":"/p/27453583","titleImage":"","summary":"","href":"/api/posts/27453583","meta":{"previous":null,"next":null},"snapshotUrl":"","commentsCount":5,"likesCount":20}},"User":{"t.t.":{"isFollowed":false,"name":"兔兔","headline":"才疏学浅，哗众取宠。东软NSS友情社员。岛娘的自动打牌器（","avatarUrl":"https://pic2.zhimg.com/3c69db683d8830ab3438204d2c9c2265_s.jpg","isFollowing":false,"type":"people","slug":"t.t.","bio":"github.com/TiriSane","hash":"1c638296d06b23d6d995545fdb835052","uid":76545464991744,"isOrg":false,"description":"才疏学浅，哗众取宠。东软NSS友情社员。岛娘的自动打牌器（","profileUrl":"https://www.zhihu.com/people/t.t.","avatar":{"id":"3c69db683d8830ab3438204d2c9c2265","template":"https://pic2.zhimg.com/{id}_{size}.jpg"},"isOrgWhiteList":false}},"Comment":{},"favlists":{}},"me":{},"global":{},"columns":{"next":{},"tutut":{"pins":[],"followersCount":338,"creator":{"bio":"github.com/TiriSane","isFollowing":false,"hash":"1c638296d06b23d6d995545fdb835052","uid":76545464991744,"isOrg":false,"slug":"t.t.","isFollowed":false,"description":"才疏学浅，哗众取宠。东软NSS友情社员。岛娘的自动打牌器（","name":"兔兔","profileUrl":"https://www.zhihu.com/people/t.t.","avatar":{"id":"3c69db683d8830ab3438204d2c9c2265","template":"https://pic2.zhimg.com/{id}_{size}.jpg"},"isOrgWhiteList":false},"topics":[{"url":"https://www.zhihu.com/topic/19584970","id":"19584970","name":"C++"},{"url":"https://www.zhihu.com/topic/19554298","id":"19554298","name":"编程"}],"activateState":"activated","href":"/api/columns/tutut","acceptSubmission":true,"firstTime":false,"postTopics":[{"postsCount":6,"id":11569,"name":"C++"},{"postsCount":5,"id":32038,"name":"C++ Primer"},{"postsCount":2,"id":1093,"name":"算法"},{"postsCount":2,"id":13849,"name":"数据结构"},{"postsCount":2,"id":25257,"name":"算法与数据结构"},{"postsCount":1,"id":17109,"name":"课程设计"},{"postsCount":1,"id":25295,"name":"Cocos2d-x"},{"postsCount":1,"id":93852,"name":"炉石传说（Hearthstone）"}],"pendingName":"","avatar":{"id":"09f567d363e2fb65f71d5d94b5f11b9a","template":"https://pic3.zhimg.com/{id}_{size}.jpeg"},"canManage":false,"description":"欢迎来到兔兔的小洞（就是专栏啦=w=","pendingTopics":[],"nameCanEditUntil":0,"reason":"","banUntil":0,"slug":"tutut","name":"田宇轩编程的地方","url":"/tutut","intro":"这里用来安放一些有关编程的事","topicsCanEditUntil":0,"activateAuthorRequested":"none","commentPermission":"anyone","following":false,"postsCount":12,"canPost":false,"FULLINFO":true}},"columnPosts":{"tutut":{"entity":["27453583","25821861","24392334","23761747","23536587","23535827","23503699","23199897","23199758","23199073","21820756","21308771"]}},"columnSettings":{"colomnAuthor":[],"uploadAvatarDetails":"","contributeRequests":[],"contributeRequestsTotalCount":0,"inviteAuthor":""},"postComments":{},"postReviewComments":{"comments":[],"newComments":[],"hasMore":true},"favlistsByUser":{},"favlistRelations":{},"promotions":{},"switches":{"couldAddVideo":false},"draft":{"titleImage":"","titleImageSize":{},"isTitleImageFullScreen":false,"canTitleImageFullScreen":false,"title":"","titleImageUploading":false,"error":"","content":"","draftLoading":false,"globalLoading":false,"pendingVideo":{"resource":null,"error":null}},"drafts":{"draftsList":[],"next":{}},"config":{"userNotBindPhoneTipString":{}},"recommendPosts":{"articleRecommendations":[],"columnRecommendations":[]},"env":{"isAppView":false,"appViewConfig":{"content_padding_top":128,"content_padding_bottom":56,"content_padding_left":16,"content_padding_right":16,"title_font_size":22,"body_font_size":16,"is_dark_theme":false,"can_auto_load_image":true,"app_info":"OS=iOS"},"isApp":false},"sys":{}}