Posts Tagged ‘C’
winux项目[1]是我五年前参加学校科技创新申请的项目,用时一年实现了PE Loader以及kernel32.dll里面3个Win32 API的移植工作,后来因为项目结题加上要忙其他事情就把后续开发工作搁置了。最近整理以前的代码的时候发现关于这个项目除了结题时提交的一篇水paper之外再没写过任何技术资料,所以趁着相关知识还没全忘赶紧写篇手记留作纪念。
该问题来自于《Cracking the Coding Interview 5th edition》练习题9.6。原题描述如下:“Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.”
该问题是典型的递归问题,有点类似于全排列算法,不同之处在于这里含有重复元素,而且需要验证左右的括号是否正确匹配。我在这里给出的代码和书上给的第二种解法原理基本相同,不过我觉得我的代码更简洁和易懂一点,所以发出来以备有需要的人参考。
该问题来自于《Cracking the Coding Interview 5th edition》练习题2.7。原题描述如下:“Implement a function to check if a linked list is a palindrome.”我感觉原书给的答案中的递归方法太鬼畜了,没怎么看懂,于是就实现了自己的一个版本。
基本思想就是首先递归到链表尾,然后使用两个指针(一个从链表头向后移动,一个从链表尾向前移动)进行数据比较,并随着弹栈的过程各自移动到下个节点。当两个指针相遇或是错开一格的时候就不用再移动了,直接一溜返回true就行了。我的实现方式中使用了两个指针参数,其中一个还是Node**,好像看起来更鬼畜了……
问题来源于wwwyhx同学在一亩三分地论坛编程技术版上提供的一道Microsoft面试题,大意是如何仅使用一个栈来实现队列的数据结构,满足FIFO特性。在网上类似的问题一般是用两个栈来实现,当然就很简单了。那么如果要求只用一个栈来实现该怎么做呢?
昨晚整理资料,翻出一个自己一年前写的txt,估计是当时自己闲得蛋疼的时候研究的玩意,只记录了实验数据和结论。实验就懒得重现了,只把结果在这记一下吧,供参考。
1、返回类型为结构体
结论:
1、调用函数前,先给返回的结构体预留空间,并把首地址压栈;
2、函数内部利用压栈的首地址设置返回的结构体信息;
3、函数返回值(eax)为压栈的首地址;
4、调用者把返回值(eax)指向的空间存放的结构体拷贝到栈上层的一段空间中;//第一次copy
5、调用者利用栈上层的这段空间存放的结构体信息给变量赋值。//第二次copy
2、形参类型为结构体
结论:
结构体为参数时,仿照压栈的方式,在栈上拉出结构体大小的空间并填充,作为函数参数(相当于将结构体压栈)。