编程杂谈

说明常应用于附近的人、两地距离计算、朋友圈定位…中文文档:http://redis.cn/commands/geoadd.html将有效的地理空间位置(经度,纬度,名称)添加到指定的Key中,这些Key会存到Hset(有序集合)中。有效的经度从-180度到180度。有效的纬度从-85.05112878度到85.05112878度。该类型的底层实现是Hset(有序聚合),所以也能使用有序集合的命令操作常用六大命令地理位置的坐标可以在网络上下载完整的信息进行添加geoaddkeylongitudelatitudemember[longitudelatitudemember...]127.0.0.1:6379>geoaddchina:city104.06573530.659462chengdu(integer)1127.0.0.1:6379>geoaddchina:city116.40528539.904989beijing114.08594722.547shenzhen(integer)2获取地理位置的坐标geoposkeymember[member]127.0.0.1:6379>geoposchina:citybeijing1)1)"116.40528291463851929"2)"39.9049884229125027"127.0.0.1:6379>geoposchina:citybeijingshenzhen1)1)"116.40528291463851929"2)"39.9049884229125027"2)1)"114.08594459295272827"2)"22.54699993773966327"获取两地距离keymember1member2[unit][unit]:m(米)、km(千米)、mi(英里)、ft(尺)127.0.0.1:6379>geodistchina:citybeijingshenzhenkm"1943.0240"获取附近的位置集合需要给==经纬度==通过半径来返回位置集合georadiuskeylongitudelatituderaidusm|km|ft|mi[withcoord][withdist][withhash][COUNTcount][asc|desc][storekey][storedistkey]下列可选参数是在返回结果上嵌套一层显示[withcoord]:返回结果显示位置经纬度[withdist]:返回结果显示距离[COUNTcount]:指定返回结果的数量[withhash]:返回结果哈希[asc|desc]:根据中心,由近到远|由远到近返回结果127.0.0.1:6379>georadiuschina:city110301000km1)"chengdu"2)"shenzhen"127.0.0.1:6379>georadiuschina:city110301000kmwithcoordwithdistwithhashasccount21)1)"chengdu"2)"574.3396"3)(integer)40261377941277544)1)"104.06573742628097534"2)"30.65946118872339099"2)1)"shenzhen"2)"923.4929"3)(integer)40464337336821184)1)"114.08594459295272827"2)"22.54699993773966327"获取附近的位置集合需要给==位置==通过半径来返回位置集合georadiusbymemberkeymemberraidusm|km|ft|mi[withcoord][withdist][withhash][COUNTcount][asc|desc][storekey][storedistkey]下列可选参数是在返回结果上嵌套一层显示[withcoord]:返回结果显示位置经纬度[withdist]:返回结果显示距离[COUNTcount]:指定返回结果的数量[withhash]:返回结果哈希[asc|desc]:根据中心,由近到远|由远到近返回结果127.0.0.1:6379>georadiusbymemberchina:citybeijing2000km1)"chengdu"2)"shenzhen"3)"beijing"127.0.0.1:6379>georadiusbymemberchina:citybeijing2000kmwithcoordwithdistwithhashasccount21)1)"beijing"2)"0.0000"3)(integer)40698853706710104)1)"116.40528291463851929"2)"39.9049884229125027"2)1)"chengdu"2)"1517.9907"3)(integer)40261377941277544)1)"104.06573742628097534"2)"30.65946118872339099"获取位置HASH将二维经纬度信息,转换成一维字符串,返回的11位哈希值字符串越相似,说明距离越近geohashkeymember[member]127.0.0.1:6379>GEOHASHchina:citybeijingchengdushenzhen1)"wx4g0b7xrt0"2)"wm6n2j6k730"3)"ws10k0dcg10"

编程杂谈

说明中文文档:http://redis.cn/documentation.htmlString文档:http://redis.cn/commands.html#stringList文档:http://redis.cn/commands.html#listSet文档:http://redis.cn/commands.html#setHash文档:http://redis.cn/commands.html#hashHset文档:http://redis.cn/commands.html#sorted_setKey实际使用中,建议key使用:(冒号)分割不同层次127.0.0.1:6379>setuser:2:nameAoaOK127.0.0.1:6379>setuser:1:nameBobOKString类型最简单Redis类型##设置K-V#################################################setkv[nx|xx][过期时间/秒]127.0.0.1:6379>setkvnx#Key不存在设置(分布式锁用到)OK127.0.0.1:6379>setkvnx(nil)127.0.0.1:6379>setkkvxx#Key存在设置(nil)##V自增|减#################################################原子性几个客户端同时操作会增加|减少127.0.0.1:6379>setk10OK127.0.0.1:6379>incrk#key自增1(integer)11127.0.0.1:6379>incrbyk10#key增加10(integer)21127.0.0.1:6379>decrk#key自减1(integer)20127.0.0.1:6379>decrbyk5#key减少5(integer)15##批量set|get#################################################原子操作一起成功|一起失败127.0.0.1:6379>msetk1v1k2v2k3v3OK127.0.0.1:6379>mgetk1k2k31)"v1"2)"v2"3)"v3"##修改|检查|删除################################################127.0.0.1:6379>setkvv#再次设置为修改OK127.0.0.1:6379>existsk#检查是否存在(integer)1127.0.0.1:6379>delk#删除并返回(integer)1127.0.0.1:6379>existsk(integer)0##获取指定长度#################################################getrange键起始位置长度127.0.0.1:6379>setkabcdeOK127.0.0.1:6379>getrangek12#getrange"bc"127.0.0.1:6379>getrangek0-1"abcde"##设置指定'位置'的值#################################################setrange键位置值127.0.0.1:6379>setkabcdeOK127.0.0.1:6379>setrangek1mm#setrange(integer)5127.0.0.1:6379>getk"ammde"List列表list列表常用于队列和栈的操作。【消息队列】实际上是一个链表如果key不存在,就创建新的链表如果key存在,就添加值移除了所有值,也就不存在了两边插入或者改动值,效率最高高!对中间元素进行操作,效率就相对于低一些##添加值(头部)#################################################lpush键值(一个值或者多个值)127.0.0.1:6379>lpushkv1(integer)1127.0.0.1:6379>lpushkv2(integer)2127.0.0.1:6379>lpushkv3(integer)3127.0.0.1:6379>LPUSHkv4v5(integer)5127.0.0.1:6379>##添加值(尾部)#################################################rpush键值(一个值或者多个值)127.0.0.1:6379>rpushkv6(integer)6##查看值(批量)#################################################lrange键startend127.0.0.1:6379>lrangek0-11)"v5"2)"v4"3)"v3"4)"v2"5)"v1"6)"v6"127.0.0.1:6379>lrangek011)"v5"2)"v4"##查看值(单个索引)#################################################lindex键索引127.0.0.1:6379>lindexk1"v4"##删除值(头部)#################################################lpop键[timeout]删除值并返回127.0.0.1:6379>lpopk"v5"##删除值(尾部)#################################################rpop键[timeout]删除值并返回127.0.0.1:6379>rpopk"v6"##获取长度################################################127.0.0.1:6379>llenk(integer)4##移除指定值#################################################lrem键数量值(移除多个数量时,是移除相同值)127.0.0.1:6379>lremk1v1(integer)1##修剪#################################################ltrim键01(修剪后,原来数据列表数据被改变)127.0.0.1:6379>ltrimk01OK(integer)1##修改值(替换值)#################################################指定下标,替换值127.0.0.1:6379>lrangek0-11)"v4"2)"v3"127.0.0.1:6379>lsetk3v2#修改值(error)ERRindexoutofrange#超出索引127.0.0.1:6379>lsetk1v2#修改值OK127.0.0.1:6379>lrangek0-11)"v4"2)"v2"##插入值#################################################linsert键before|after值插入值(某个值之前|之后添加)127.0.0.1:6379>linsertkbeforev2v3(integer)3127.0.0.1:6379>lrangek0-11)"v4"2)"v3"3)"v2"127.0.0.1:6379>linsertkafterv2v5(integer)4127.0.0.1:6379>lrangek0-11)"v4"2)"v3"3)"v2"4)"v5"127.0.0.1:6379>Set集合Set里面的值,是无序不重复的##添加值################################################127.0.0.1:6379>saddkv1(integer)1127.0.0.1:6379>saddkv2(integer)1##查看所有值################################################127.0.0.1:6379>smembersk1)"v2"2)"v1"##值是否存在################################################127.0.0.1:6379>sismemberkv5(integer)0127.0.0.1:6379>sismemberkv2(integer)1##获取Set集合元素个数################################################127.0.0.1:6379>scardk(integer)2##移除元素################################################127.0.0.1:6379>sremkv2(integer)1127.0.0.1:6379>smembersk1)"v1"##获取值(随机)#################################################srandmemberk[count]Set无序不重复,所以是随机获取127.0.0.1:6379>srandmemberk"v4"127.0.0.1:6379>SRANDMEMBERk"v3"127.0.0.1:6379>SRANDMEMBERk"v3"##删除值(随机)#################################################spopk[count]127.0.0.1:6379>spopk"v4"##移动值#################################################SMOVE源集合目标集合值(移动Set1元素到Set2)127.0.0.1:6379>SMOVEkk1v1(integer)1使用技巧交集,并集,差集127.0.0.1:6379>sdiffk1k2#差集1)"v1"127.0.0.1:6379>127.0.0.1:6379>sinterk1k2#交集(emptylistorset)127.0.0.1:6379>sunionk1k2#并集1)"v1"Hash哈希存储形式(Key-Map集合)Hash更适用于经常变更的数据,尤其用户数据之类的.Hash适用于对象的存储(用户、姓名、性别)String更适用于字符的存储##单个设置值################################################127.0.0.1:6379>hsetkhash1value1(integer)1##批量设置值################################################127.0.0.1:6379>HMSETkhash1value1hash2value2OK##查看所有Hash################################################127.0.0.1:6379>hgetallk1)"hash1"2)"value1"3)"hash2"4)"value2"##删除单个|多个Hash#################################################hdel键Map键(可以多个)127.0.0.1:6379>hdelkhash1(integer)1##Hash字段数量################################################127.0.0.1:6379>hlenk(integer)1##某个Hash是否存在#################################################127.0.0.1:6379>hexistskhash1(integer)0#不存在127.0.0.1:6379>hexistskhash2(integer)1#存在127.0.0.1:6379>##获取Hash所有key&value#################################################127.0.0.1:6379>hkeysk1)"hash2"127.0.0.1:6379>hvalsk1)"value2"127.0.0.1:6379>##Hash自增|自减################################################127.0.0.1:6379>hsetkhash1(integer)1127.0.0.1:6379>hincrbykhash1#增加(integer)2127.0.0.1:6379>hincrbykhash-1#减少(integer)1Zset有序集合在Set基础上,增加一个顺序段##添加值#################################################zadd键score值127.0.0.1:6379>zaddk1value1(integer)1127.0.0.1:6379>zaddk2value23value3(integer)2127.0.0.1:6379>##排序################################################127.0.0.1:6379>zaddk55value244value311value1(integer)3127.0.0.1:6379>zrevrangek0-1#大~小1)"value2"2)"value3"3)"value1"127.0.0.1:6379>zrangek0-1#小~大1)"value1"2)"value3"3)"value2"127.0.0.1:6379>##通过score段排序#################################################zrangebyscore键小值大值[withscores](小~大排序)127.0.0.1:6379>zaddk55value244value311value1(integer)3127.0.0.1:6379>zrangebyscorek-inf+inf#无穷小无穷大1)"value1"2)"value3"3)"value2"127.0.0.1:6379>ZRANGEBYSCOREk-inf+infwithscores1)"value1"2)"11"3)"value3"4)"44"5)"value2"6)"55"127.0.0.1:6379>##移除元素#################################################zremkmember[可以多个]通过member段移除127.0.0.1:6379>zremkvalue1(integer)1127.0.0.1:6379>zrangek0-11)"value3"2)"value2"##获取元素个数################################################127.0.0.1:6379>zcardk(integer)2##元素区间统计#################################################zcountkminmax127.0.0.1:6379>zcountk4466(integer)2使用技巧带权重元素的使用:1重要消息,2普通消息成绩表、工资表排行榜的实现

编程杂谈

介绍Redis是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。官网:https://redis.io/中文官网:http://www.redis.cn/安装Windows安装Redis不推荐在Windows上使用,但可用以学习msi是安装程序,为了方便Linux上手下载压缩包下载地址:https://github.com/tporadowski/redis/releases解压点击redis-server.exe启动服务器点击redis-cli.exe启动客户端Linux安装==待补==性能测试快速测试直接点击redis-benchmark.exe带参测试redis-benchmark.exe-n10000-c50-q相关参数WindowsRidis可视化国内下载地址:https://gitee.com/qishibo/AnotherRedisDesktopManager/releases官方中文地址:https://github.com/qishibo/AnotherRedisDesktopManager/blob/master/README.zh-CN.md小知识Redis小知识&问题【遇到补】默认端口6379默认没有密码,密码在配置文件requirepass[密码]设置,需要重启生效默认有16个数据(0~15)基础命令命令官网:http://www.redis.cn/commands.html127.0.0.1:6379>ping#测试连通性PONG127.0.0.1:6379>SELECT2#切换数据库OK127.0.0.1:6379[2]>setnameI#设置K-VOK127.0.0.1:6379[2]>getna#K获取V(nil)127.0.0.1:6379[2]>getname"I"127.0.0.1:6379[2]>keys*#获取所有K1)"name"127.0.0.1:6379[2]>dbsize#当前数据库大小(integer)1127.0.0.1:6379[2]>flushdb#清空当前数据库OK127.0.0.1:6379[2]>dbsize(integer)0127.0.0.1:6379[2]>flushall#清空所有数据库OK127.0.0.1:6379>setnamennnOK127.0.0.1:6379>EXISTSname#检查K存在(integer)1127.0.0.1:6379>EXISTSna(integer)0127.0.0.1:6379>EXPIREname5#设置K-V过期时间(秒)(integer)1127.0.0.1:6379>ttlname#查看剩余过期时间(integer)-2#不存在(过期自动删除)127.0.0.1:6379>setnamennnOK127.0.0.1:6379>movename5#移动K-V到5号数据库(integer)1127.0.0.1:6379>setnamennnOK127.0.0.1:6379>typename#检查类型string

2022-1-19 69 0
编程杂谈

注:有好久没更新了,也不是说没有学习,主要Js逆向,不适合发在网站上本文借鉴自:https://juejin.cn/post/6844903811601924103在此篇文章上进行了一点优化:处理标签多个属性值,增加属性值的兼容性说明JsinnerHTML方法是把文本型的HTML标签转换成DOM树,实现过程与解释器差不多,也算了解一下解释器解释器步骤词法分析->语法分析->解释执行词法分析词法分析的具体任务就是:把字符流变成token流。词法分析通常有两种方案:一种是状态机,一种是正则表达式。我们这里选择状态机。状态机的原理将整个HTML字符串进行遍历,每次读取一个字符,进行一次决策(决定出下一个字符处于哪个状态),当一个状态决策完成的token就会被存入到tokens里。<pclass="yy"id="xx">测试元素</p>对于上述节点信息,我们可以拆分出如下token开始标签:<p属性标签:class="yy"属性标签:id="xx"文本节点:测试元素结束标签:</p>词法分析函数说明封装开头函数functionHTMLLexicalParser(htmlString,tokenHandler){this.token=[];//存储已经分析完成的一个个tokenthis.tokens=[];//标签属性词法分析结束标志为处理标签多个属性添加this.attrFlag=0;//待处理的字符串this.htmlString=htmlString//处理函数tokens转换成树结构函数this.tokenHandler=tokenHandler}start函数start处理的比较简单,如果是<字符,表示开始标签或结束标签,因此我们需要下一个字符信息才能确定到底是哪一类token,所以返回tagState函数去进行再判断,否则认为是文本节点,返回文本状态函数HTMLLexicalParser.prototype.start=function(c){if(c==='<'){//表示开始标签或结束标签,所以需要进一步确认this.token.push(c)//记录tokenreturnthis.tagState}else{returnthis.textState(c)}}tagState、textState函数tagState根据下一个字符,判断进入开始标签状态还是结束标签状态,如果是/表示是结束标签,否则是开始标签textState用来处理每一个文本节点字符,遇到<表示得到一个完整的文本节点token。HTMLLexicalParser.prototype.tagState=function(c){this.token.push(c)if(c==='/'){//表示结束状态,返回结束处理函数returnthis.endTagState}else{//表示开始处理标签状态,接下来会有字母(开始)、空格(属性)、>(标签结束)returnthis.startTagState}}HTMLLexicalParser.prototype.textState=function(c){if(c==='<'){//表示文本状态处理完成,把此窗台存入tokens中this.emitToken('text',this.token.join(''));this.token=[]//置空token准备处理下一状态returnthis.start(c)}else{//还处理文本状态this.token.push(c)returnthis.textState}}emitToken、startTagState、endTagState函数emitToken用来将产生的完整token存储在tokens中,参数是token类型和值。startTagState用来处理开始标签,这里有三种情况:接下来的字符是字母,则认定依旧处于开始标签状态遇到空格,则认定开始标签态结束,接下来是处理属性遇到>同样认定为开始标签态结束,但接下来是处理新的节点信息endTagState用来处理结束标签,结束标签没有属性,因此只有两种情况:如果接下来的字符是字母,则认定依旧处于结束标签态遇到>同样认定为结束标签态结束,但接下来是处理新的节点信息HTMLLexicalParser.prototype.emitToken=function(type,value){varres={type,value}this.tokens.push(res)//流式处理this.tokenHandler&&this.tokenHandler(res)//存在则执行该函数}HTMLLexicalParser.prototype.startTagState=function(c){if(c.match(/[a-zA-Z]/)){//处理标签名状态this.token.push(c.toLowerCase())returnthis.startTagState}if(c===''){//标签名状态结束进入标签属性状态this.emitToken('startTag',this.token.join(''))this.token=[]returnthis.attrState}if(c==='>'){//标签结束状态进入开始分析状态this.emitToken('startTag',this.token.join(''))this.token=[]returnthis.start}}HTMLLexicalParser.prototype.endTagState=function(c){if(c.match(/[a-zA-Z]/)){//双标签结束时状态this.token.push(c.toLowerCase())returnthis.endTagState}if(c==='>'){//双标签结束时状态进入开始分析状态this.token.push(c)this.emitToken('endTag',this.token.join(''))this.token=[]returnthis.start}}attrStateattrState处理属性标签,也处理三种情形如果是字母、数字、等号、下划线、空格、中划线、冒号、分号,则认定为依旧处于属性标签态如果遇到引号,则表示遇到标签属性值,第二次遇到才表示一个标签属性结束(不代表标签状态结束),继续处理标签状态如果遇到>则认定为属性标签状态结束,接下来开始新的节点信息HTMLLexicalParser.prototype.attrState=function(c){if(c.match(/[a-zA-Z0-9=_\-\:;]/)){this.token.push(c)returnthis.attrState}if(c.match(/['"]/)){this.attrFlag=this.attrFlag+1;if(this.attrFlag==2){this.token.push(c)this.emitToken('attr',this.token.join(''))this.token=[]this.attrFlag=0;returnthis.attrState}this.token.push(c)returnthis.attrState}if(c==='>'){returnthis.start}}parse、getOutPutparse解析函数HTMLLexicalParser.prototype.parse=function(){varstate=this.start;for(varcofthis.htmlString.split('')){state=state.bind(this)(c)}}HTMLLexicalParser.prototype.getOutPut=function(){returnthis.tokens}测试词法分析varp=newHTMLLexicalParser('<divclass="xxyy"data="hh">测试并列元素的</div><pclass="pp"data="kk"style="display:none;">测试并列元素的</p>')p.parse()p.getOutPut()语法分析语法分析:就是把上一步分析的结果,处理成有层次的树结构定义树结构//语法分析functionElement(tagName){this.tagName=tagNamethis.attr={}this.childNodes=[]}functionText(value){this.value=value||''}处理词法分析结果思路通过上图分析结果很容易看出层次结构startTagtoken,push一个新节点elementendTagtoken,则表示当前节点处理完成,此时出栈一个节点,同时将该节点归入栈顶元素节点的childNodes属性,这里需要做个判断,如果出栈之后栈空了,表示整个节点处理完成,考虑到可能有平行元素,将元素push到stacks。attrtoken,直接写入栈顶元素的attr属性texttoken,由于文本节点的特殊性,不存在有子节点、属性等,就认定为处理完成。这里需要做个判断,因为文本节点可能是根级别的,判断是否存在栈顶元素,如果存在直接压入栈顶元素的childNodes属性,不存在push到stacks。functionHTMLSyntacticalParser(){this.stack=[]this.stacks=[]}HTMLSyntacticalParser.prototype.getOutPut=function(){returnthis.stacks}//一开始搞复杂了,合理利用基本数据结构真是一件很酷炫的事HTMLSyntacticalParser.prototype.receiveInput=function(token){varstack=this.stackconsole.log('token',token)if(token.type==='startTag'){stack.push(newElement(token.value.substring(1)))}elseif(token.type==='attr'){vart=token.value.split('=');//console.log('t',t);varkey=t[0].replace(/^\s*|\s*$/g,""),value=t[1].replace(/'|"/g,'')stack[stack.length-1].attr[key]=value}elseif(token.type==='text'){if(stack.length){stack[stack.length-1].childNodes.push(newText(token.value))}else{this.stacks.push(newText(token.value))}}elseif(token.type==='endTag'){varparsedTag=stack.pop()if(stack.length){stack[stack.length-1].childNodes.push(parsedTag)}else{this.stacks.push(parsedTag)}}console.log(stack);}测试语法分析结果varhtml='<divclass="xxyy"data="hh"><pclass="ss"data="ff"style="display:none;">嵌套</p></div><pclass="pp"data="kk"style="display:none;">并列</p>'varsyntacticalParser=newHTMLSyntacticalParser()varlexicalParser=newHTMLLexicalParser(html,syntacticalParser.receiveInput.bind(syntacticalParser))lexicalParser.parse()syntacticalParser.getOutPut()解释执行就是把上面的树结构,使用递归映射成真实的dom结构functionvdomToDom(array){varres=[]for(letitemofarray){res.push(handleDom(item))}returnres}functionhandleDom(item){if(iteminstanceofElement){varelement=document.createElement(item.tagName)for(letkeyinitem.attr){element.setAttribute(key,item.attr[key])}if(item.childNodes.length){for(leti=0;i<item.childNodes.length;i++){element.appendChild(handleDom(item.childNodes[i]))}}returnelement}elseif(iteminstanceofText){returndocument.createTextNode(item.value)}}封装函数functionhtml(element,htmlString){varsyntacticalParser=newHTMLSyntacticalParser()varlexicalParser=newHTMLLexicalParser(htmlString,syntacticalParser.receiveInput.bind(syntacticalParser))lexicalParser.parse()vardom=vdomToDom(syntacticalParser.getOutPut())varfragment=document.createDocumentFragment()dom.forEach(item=>{fragment.appendChild(item)})element.appendChild(fragment)}我修改过的代码地址:https://pan.bigdataboy.cn/s/Xaato

编程杂谈

二叉树的遍历因为使用二叉树最多是链式存储结构,所遍历的方式也是按照链式结构来的。遍历的宗旨在遍历是按照某种次序依次访问二叉树的所有节点,并且每个节点仅仅被访问一次。前序遍历(根左右)遍历顺序ABDHIEJCFKG中序遍历(左根右)遍历顺序HDIBEJAFKCG后序遍历(左右根)遍历顺序HIDJEBKFGC层序遍历遍历顺序ABCDEFGHIJK二叉树代码实现前序遍历(根左右)二叉树的遍历方式,在创建二叉树时就确定好了#include<stdio.h>#include<stdlib.h>typedefcharElemType;//二叉树结构typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//创建二叉树按照用户遵循的前序遍历的(根左右)方式输入数据voidcreateBiTree(BiTree*T){charc;printf("输入元素:");scanf("%c",&c);getchar();if(c=='#'){*T=NULL;}else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=c;createBiTree(&(*T)->lchild);//先创建左子节点createBiTree(&(*T)->rchild);//再创建右子节点}}//遍历二叉树voidpreOrderTraverse(BiTreeT,intlevel){if(T!=NULL){printf("数据%c在第%d层\n",T->data,level);preOrderTraverse(T->lchild,level+1);preOrderTraverse(T->rchild,level+1);}}intmain(){intlevel=1;BiTNode*T;createBiTree(&T);preOrderTraverse(T,level);return0;}输入顺序中序遍历(左根右)输入方式还是前序的输入方式,只是遍历的打印位置修改了一下//中序遍历二叉树voidpreOrderTraverse(BiTreeT,intlevel){if(T!=NULL){preOrderTraverse(T->lchild,level+1);printf("数据%c在第%d层\n",T->data,level);preOrderTraverse(T->rchild,level+1);}}后序遍历(左右后)输入方式还是前序的输入方式,只是遍历的打印位置修改了一下//后序遍历二叉树voidpreOrderTraverse(BiTreeT,intlevel){if(T!=NULL){preOrderTraverse(T->lchild,level+1);preOrderTraverse(T->rchild,level+1);printf("数据%c在第%d层\n",T->data,level);}}

编程杂谈

栈相关概念什么是栈是限定仅在表尾(栈顶)进行插入和删除操作的线性表栈又称为后进先出(LastInFirstOut)的线性表,简称LIFO结构栈顶(top)我们把允许插入和删除的一端称为栈顶栈底(bottom)另一端称为栈底空栈不含任何任何数据元素的栈称为==空栈==栈的操作入栈入栈又称压栈,就是向栈中放数据,每次放入一个top指针就+1出栈取出栈中数据的操作,每取出一个top指针就-1清空栈清空栈,是把top指针直接指向bottom指针,原本物理空间上数据还存在栈的实现创建队列结构体#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE20//栈大小#defineSTACK_INCREMENT10//申请空间大小typedefcharElemType;//定义栈typedefstruct{ElemType*base;//栈低ElemType*top;//栈顶intstackSize;//当前栈容纳的大小}sqStack;初始化队列//初始化栈voidinitStack(sqStack*s){s->base=(ElemType*)malloc(STACK_INCREMENT*sizeof(ElemType));if(s->base==NULL)exit(-1);//空间申请失败s->top=s->base;s->stackSize=STACK_INIT_SIZE;printf("s->top:%p\n",s->top);printf("s->base:%p\n",s->base);}入栈(压栈)//压栈voidpush(sqStack*s,ElemTypee){//判断是否满栈,满栈则扩容if(s->top-s->base>=s->stackSize){s->base=(ElemType*)realloc(s->base,(s->stackSize+STACK_INCREMENT)*sizeof(ElemType));if(!s->base)exit(-1);}*(s->top)=e;//栈顶的值赋值es->top++;//栈顶地址向前推进}出栈//出栈voidpop(sqStack*s,ElemType*e){//判断下溢出if(s->top==s->base){return;}*e=*--s->top;//减之后赋值,*为取值,不是指针}当前栈长度//当前栈长度intsqStackLen(sqStack*s){returns->top-s->base;}主函数使用用户输入值,进行压栈,#号结束,输出栈内数据intmain(){sqStacks;initStack(&s);//初始化栈ElemTypec;printf("输入栈:");while((c=getchar())!='#'){getchar();push(&s,c);//压栈}getchar();//把\n从缓冲区去掉ElemTypee;while(sqStackLen(&s)){pop(&s,&e);//出栈printf("%c",e);}return0;}扩展(栈链)就是把栈和单链表结合,如下图一样栈链内元素是指针相连,而栈是顺序的地址队列概念什么是队列队列(queue)是只允许在一端进行插入的操作,而在另一端进行删除操作的线性表。队列主要特征是先进先出(FirstInFirstOut)队列操作队列的结构体#include<stdio.h>#include<stdlib.h>#defineElemTypechar//队列元素结构体(链表)typedefstructQNode{ElemTypedata;//队列节点数据structQNode*next;//队列指针}QNode,*QueuePrt;//队列头尾typedefstruct{QueuePrtfront,rear;//队头指针,队尾指针}LinkQueue;创建队列/*创建结构体在内存中创建一个头结点,将队列的头尾指针指向头结点,此时队列为空*/voidinitQueue(LinkQueue*q){q->front=q->rear=(QueuePrt)malloc(sizeof(QNode));if(!q->front)exit(-1);q->front->next=NULL;}入队列//入队列(下面是在从尾部入)voidinertQueue(LinkQueue*q,ElemTypee){QueuePrtnode=(QueuePrt)malloc(sizeof(QNode));if(!node)exit(-1);node->data=e;node->next=q->rear->next;q->rear->next=node;q->rear=node;}出队操作(取出队列的数据)//出队操作(下面是从队列头部取值)voidgetQueue(LinkQueue*q,ElemType*e){if(q->front==q->rear)return;//队列为空QueuePrtnode=q->front->next;*e=node->data;q->front->next=node->next;//队列头部向移动一位if(q->rear==node)q->rear=q->front;//队列最后数据被取出是,初始化为空free(node);};销毁队列//销毁队列voiddeleteQueue(LinkQueue*q){while(q->front){q->rear=q->front->next;free(q->front);q->front=q->rear;}}主函数使用intmain(){LinkQueueq;initQueue(&q);ElemTypee=0;printf("输入队列数据:");scanf("%c",&e);while(e!='#'){inertQueue(&q,e);scanf("%c",&e);}printf("队列中的数据:\n");while(q.rear!=q.front){getQueue(&q,&e);printf("%c",e);}return0;}

编程杂谈

常规想法遍历一遍单链表,记录长度再一次遍历,输出中间元素这样的效率不是最优另一种方式(来源于网络)search的速度是mid的两倍,search走完恰好mid走一半voidprintInt(intList*head){intList*mid,*search;//search的速度是mid的两倍,search走完恰好mid走一半mid=search=head;//保证midsearch启点一样while(search->next!=NULL){search=search->next;//search取下一个if(search->next!=NULL){search=search->next;//search再去下一个mid=mid->next;//mid就取一次}else{mid=mid->next;//search取到头,mid再往下取一位}}printf("\n%d",mid->num);}完整代码随机生成任意长度单链表输出单链表值输出位于中间的值奇数个是最中间值,偶数个是中间两个的前一个#include<stdio.h>#include<stdlib.h>#include<time.h>typedefstructIntList{intnum;structintList*next;}intList;intList*applyList();//生成随机长度单链表voidprintList(intList*head);//查看单链表voidprintInt(intList*head);//输出单链表中间值intList*applyList(){srand((unsigned)time(NULL));intlen=rand()%10+10;//10到20的随机数intList*head=(intList*)malloc(sizeof(intList));if(head==NULL)exit(-1);//链表头部申请失败head->next=NULL;while(len){intList*node=(intList*)malloc(sizeof(intList));node->num=rand()%10+20;node->next=head->next;head->next=node;len--;}returnhead;}voidprintList(intList*head){intList*t=head->next;while(t){printf("%d",t->num);t=t->next;}};voidprintInt(intList*head){intList*mid,*search;//search的速度是mid的两倍,search走完恰好mid走一半mid=search=head;//保证midsearch启点一样while(search->next!=NULL){search=search->next;//search取下一个if(search->next!=NULL){search=search->next;//search再去下一个mid=mid->next;//mid就取一次}else{mid=mid->next;//search取到头,mid再往下取一位}}printf("\n%d",mid->num);}intmain(){intList*list=applyList();//随机生成单链表printList(list);//查看链表的值printInt(list);//输出中间值return0;}

编程杂谈

什么是数据结构简单点就是程序设计=数据结构+算法逻辑结构&物理结构传统上把数据结构分为逻辑结构&物理结构逻辑结构:是指数据对象中数据元素之间的相互关系,是需要着重关注和讨论的问题。四大逻辑结构:集合结构:数据元素之间相互没有关系。线性结构:数据元素之间是一对一的关系。树性结构:数据元素之间有一对多的层级关系。图形结构:数据元素是多对多的关系。物理结构:指数据的逻辑结构在计算机中的存储形式。根据物理结构的定义,我们实际上研究的就是如何把数据元素存储到计算器的存储器中。数据元素的存储形式有两种:顺序存储:把数据元素存放在地址连续的存储单元里,其数据之间的逻辑关系和物理关系是一致的。就如:一些编程语言的数组就是这样。链式存储:把数据元素存放在任意的存储单元里,这组储存单元可以是连续的,也可以是不连续。就如单链表,只要知道下一个数据元素指向的地址就行`。什么是算法引入计算1+2+3+4+…+99+100的值常规算法(使用循环一个一个加):inti,sum=0,n=100;for(i=1;i<100;i++){sum=sum+i;}printf("sum=%d",sum);使用高斯算法:inti,sum=0,n=100;sum=(1+n)*n/2;printf("sum=%d",sum);这样是不是效率高很多。算法的特征算法有五大特征解决问题并不只有一种算法输入算法具有零个或者多个输入。尽管大多数时候算法来说,输入参数是必要的,但是就像打印bigdataboy.cn,就不需要参数。voidprint(){printf("bigdataboy.cn");}输出:算法需要至少一个或者多个输出。有穷性是指在执行有限的步骤后,自动结束,并且每一步都是在可接受的时间范围内完成。确定性:算法的每一步都具有确定的含义,不会出现二义性。相同的输入只能有唯一的输出结果。可行性:算法的每一步都必须是可行的,就是说,每一步都能通过执行有限的次数完成。算法设计的要求正确性:是指算法至少应该具有输入、输出和加工处理无歧义,能得到正确的结果。大致分为以下四个层次算法程序没有语法错误算法程序对于合法的输入能得到满足要求的输出算法程序对于非法输入能产生相应的说明算法程序对于故意刁难的测试输入都有满足要求的输出结果可读性算法需要便于阅读、理解和交流,方便日后他人和自己的阅读和修改。健壮性当输入不合法时,算法也能做出相关的处理,而不是产生异常、崩溃或莫名其妙的结果时间效率高和存储量低在生活中大家都想找一个漂亮乖巧懂事,懂分寸的女朋友。好的算法就像好的女朋友,应该同时具备时间效率高和存储量低的特点,设计算法时,因尽量考虑这两方面的问题!!!