数据结构之栈、队列、字符串——软件测试工程师面试秘籍
时间: 2021-11-19 13:55 作者: G. li 点击次数:
考点：
·栈、队列的概念及特点
·函数如何压栈
·字符串复制、反转等操作
1．栈
栈又称后进先出（Last In First Out，LIFO）线性表。限制在栈的一端进行插入或者删除的操作，每次出栈的元素都是栈顶的元素，即最后入栈的元素，如图2.5所示。
按照存储方式，栈分为顺序栈和链式栈。顺序栈一般由一维数组和栈顶变量组成。链式栈不会出现栈溢出的情况。
函数通过栈来辅助完成调用过程。例如，Z()函数调用A()函数时，首先，将传给A的参数压栈，将现在这条指令（A(…)）的下一条指令的地址压入栈中，以便A()函数执行完后返回Z()函数中继续执行。然后，进入A()函数的内存空间，调用PUSH EBP，即将Z()函数的EPB的内容（地址0x000F）压入栈中。接着，调用MOV EBP ESP，让EBP有一个新的栈顶。最后，将A()函数的局部变量压入栈中，开始执行A()函数的代码。这时，栈和EBP的情况如图2.6所示。
图2.5 栈
图2.6 栈和EBP的情况
函数参数入栈时，按照从右到左的顺序，并要注意高地址和低地址。入栈时以机器字长为单位且所有参数按字对齐。
2．队列
队列又称先进先出（First In First Out，FIFO）线性表，它的所有插入操作（又称入队）在队列的一端，而删除操作（又称出队）在队列的另一端，如图2.7所示。
图2.7 队列
队列同样也有顺序队列和链式队列，需要两个变量或指针来指示队头和队尾。在顺序队列中，由于队列的队头和队尾位置是时刻变化的，因此可能会到达队头了，而队尾空出来很多新的空闲区域。而循环队列利用假溢出解决了该问题。到达队头之后，重新回到队尾，当队头指针连接到队尾指针时，视为满队。
循环队列次数=(队尾-队头+数组长度)mod(数组长度)
3．字符串
试题1．不调用库函数实现字符串复制函数strCpy()。
分析：函数声明为strCpy (char * src , const char * des)，其中有如下几点需要注意。
（1）src长度为0。
（2）src和des地址相同（src==des）。
答案：代码如下。
char *strcpy(char *strDest,const char *strSrc)
{
if(strDest==NULL||strSrc==NULL)
return NULL
if(strDest==strSrc)
return strDest
char*tempptr
=
strDest
while((*strDest++=*strSrc++)!
=
”∕0”
)
retum tempptr
}
int strlen(const char*str)
{
assert(strt!=NULL);//断言字符串地址非0
int len;
while((*str++)!=” ”)
{ len++; }
return len;
}
试题2．编写函数实现整数与字符串之间的相互转化。
分析：整数转化成字符串，可以采用加0、然后逆序的方法，整数加0后会隐性转化为字符串；字符串转化成整数，可以采用减0、然后乘以10累加的方法，字符串减0后会隐性转化为整数。
试题3．不调用库函数实现字符串反转。
答案：代码如下。
package com.others;
publicclassrevertStr {
publicstaticvoid main(String[] args) {
System.out.println(inverse("liuling"));
}
publicstatic String inverse(String str){
char[] chars=str.toCharArray(); //得到字符数组
for (int i=0;i<chars.length/2;i++) {
char temp=chars[i];
chars[i]=chars[chars.length-i-1];
chars[chars.length-i-1]=temp;
}
return String.copyValueOf(chars);
}
}