基础编程面试——数据结构

1、将一个字符串倒序，如“abcd”倒序后变为“dcba”。

 1 /*字符串倒序*/
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 
 6 char *str_reverse(char *src)
 7 {
 8     char *dest = NULL;
 9 
10     int len = strlen(src);
11     dest = (char *)malloc(len+1);  //要为分配一个空间
12     char *d = dest;
13     char *s = &src[len-1];
14     while(len != 0)
15     {    
16         *d++ = *s--;
17         len--;
18     }
19     *d = '';   //此时d指向末元素,'0'或''
20     return dest;　//可以返回指向堆内存的指针，栈就不行
21 }
22 
23 int main(int argc, const char *argv[])
24 {
25     char *src  = "ABCDEF";
26     char *dest = str_reverse(src);
27     printf("%s
",dest);
28 
29     free(dest);  //释放堆内存，避免内存泄露
30 
31     return 0;
32 }

str_reverse.c

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 int main(int argc, const char *argv[])
 6 {
 7     char str[] = "ABCDEFG";
 8     int len = strlen(str);
 9 
10     char t;  //用于中间变量
11     int i;
12     for(i=0;i<=len/2;i++)
13     {
14         t = str[i];
15         str[i] = str[len-i-1];
16         str[len-i-1] = t;
17     }
18     printf("%s
",str);
19     return 0;
20 }

str_reverse.c

相关知识：字符串与字符数组

C 语言中并不存在字符串这个数据类型，而是使用字符数组来保存字符串

字符串指针变量本身是一个变量，用于存放字符串的首地址。字符串本身是存放在以该首地址为首的一块连续的内存空间中并以‘’作为串的结束。

字符指针可以整体赋值：

char *ps=”C Language”;可以写成char *ps;ps=”C Language”;

字符数组只能在声明并初始化时整体赋值：

数组方式char st[]={”C Language”};不能写成 char st[20]; St={”C Language”}; 在初始化之后，只能对字符数组的各元素逐个赋值。

2、用两个栈实现一个队列的功能

思路：

设2个栈为A,B, 一开始均为空.

入队:

将新元素push入栈A;

出队:

(1)判断栈B是否为空；

(2)如果不为空，则将栈B中最顶元素pop出；如果为空，则将A中所有元素POP出并PUSH到B中，这后POP出最顶元素，A则下移一单位。

3、使用宏实现swap

算术运算法

a=a+b;
b=a-b;
a=a-b;

#define swap1(x, y)  (y) = (x) + (y); (x) = (y) - (x); (y) = (y) - (x);

4、宏输入两个参数并返回较小的一个

#define MIN(x,y)  ((x)<(y)?(x):(y))

5、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；

6、给两个数组和他们的大小，还有一动态开辟的内存，求交集，把交集放到动态内存dongtai，并且返回交集个数

7、单连表的建立，把'a'-'z'26个字母插入到连表中，并且倒叙，还要打印！

8、请列举一个软件中时间换空间或者空间换时间的例子。

 1 --->时优
 2 void swap(int a,int b)
 3 {
 4     int c;
 5     c=a;
 6     a=b;
 7     b=c;
 8 }
 9 --->空优
10 void swap(int a,int b)
11 {
12     a=a+b;
13     b=a-b;
14     a=a-b;
15 }

swap

9、不用库函数,用C语言实现将一整型数字转化为字符串

10、求最小公共字符串

11、写一个函数比较两个字符串str1和str2的大小，若相等返回0，若str1大于str2返回1，若str1小于str2返回－1