部分IT公司算法笔试题面试题(四)

17、2005年11月15日华为软件研发笔试题。实现一单链表的逆转。
#include “stdafx.h”
typedef char eleType; // 定义链表中的数据类型
typedef struct listnode { // 定义单链表结构
eleType data;
struct listnode *next;
}node;

node *create(int n) { // 创建单链表，n为节点个数
node *p = (node *)malloc(sizeof(node));
node *head = p; head->data = ‘A’;
for(int i=’B'; i<’A'+n; i++) {
p = (p->next = (node *)malloc(sizeof(node)));
p->data = i;
p->next = NULL;
}
return head;
}

void print(node *head) { // 按链表顺序输出链表中元素
for(; head; head = head->next)
printf(“%c “, head->data);
printf(“\n”);
}

node *reverse(node *head, node *pre) { // 逆转单链表函数。这是笔试时需要写的最主要函数
node *p=head->next;
head->next = pre;
if(p) return reverse(p, head);
else return head;
}

int main(int argc, char* argv[]) {
node *head = create(6);
print(head);
head = reverse(head, NULL);
print(head);
}

18、编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符串 ”+123” 123, ”-0123” -123, “123CS45” 123, “123.45CS” 123, “CS123.45” 0
#include “stdafx.h”
int str2int(const char *str) { // 字符串转整型函数
int i=0, sign=1, value = 0;
if(str==NULL) return NULL; // 空串直接返回 NULL
if(str[0]==’-’ || str[0]==’+') { // 判断是否存在符号位
i = 1;
sign = (str[0]==’-’ -1 : 1);
}
for(; str[i]>=’0′ && str[i]<=’9′; i++) // 如果是数字，则继续转换
value = value * 10 + (str[i] – ’0′);
return sign * value;
}

int main(int argc, char *argv[]) {
char *str = “-123.45CS67″;
int val = str2int(str);
printf(“str=%s\tval=%d\n”, str, val);
}

19、歌德巴赫猜想。任何一个偶数都可以分解为两个素数之和。（其实这是个C二级考试的模拟试题）
#include “stdafx.h”
#include “math.h”
int main(int argc, char* argv[]) {
int Even=78, Prime1, Prime2, Tmp1, Tmp2;
for(Prime1=3; Prime1<=Even/2; Prime1+=2) {
for(Tmp1=2,Tmp2=sqrt(float(Prime1)); Tmp1<=Tmp2 && Prime1%Tmp1 != 0; Tmp1++);
if(Tmp1<=Tmp2) continue;
Prime2 = Even-Prime1;
for(Tmp1=2,Tmp2=sqrt(float(Prime2)); Tmp1<=Tmp2 && Prime2%Tmp1 != 0; Tmp1++);
if(Tmp1<=Tmp2) continue;
printf(“%d=%d+%d\n”, Even, Prime1, Prime2);
}
}

20、快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）
#include “stdafx.h”
#define N 10
int part(int list[], int low, int high) { // 一趟排序，返回分割点位置
int tmp = list[low];
while(low while(low=tmp) –high;
list[low] = list[high];
while(low list[high] = list[low];
}
list[low] = tmp;
return low;
}
void QSort(int list[], int low, int high) { // 应用递归进行快速排序
if(low int mid = part(list, low, high);
QSort(list, low, mid-1);
QSort(list, mid+1, high);
}
}
void show(int list[], int n) { // 输出列表中元素
for(int i=0; i printf(“%d “, list[i]);
printf(“\n”);
}
int main(int argc, char* argv[]) {
int list[N] = {23, 65, 26, 1, 6, 89, 3, 12, 33, 8};
show(list, N); // 输出排序前序列
QSort(list, 0, N-1); // 快速排序
show(list, N); // 输出排序后序列
}

21、2005年11月23日慧通笔试题：写一函数判断某个整数是否为回文数，如12321为回文数。可以用判断入栈和出栈是否相同来实现（略微复杂些），这里是将整数逆序后形成另一整数，判断两个整数是否相等来实现的。
#include “stdafx.h”
int IsEchoNum(int num) {
int tmp = 0;
for(int n = num; n; n/=10)
tmp = tmp *10 + n%10;
return tmp==num;
}

int main(int argc, char* argv[]) {
int num = 12321;
printf(“%d %d\n”, num, IsEchoNum(num));
}

22、删除字符串中的数字并压缩字符串（神州数码以前笔试题），如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）
#include “stdafx.h”
void delNum(char *str) {
int i, j=0;
// 找到串中第一个数字的位子
for(i=j=0; str[i] && (str[i]<’0′ || str[i]>’9′); j=++i);

// 从串中第一个数字的位置开始，逐个放入后面的非数字字符
for(; str[i]; i++)
if(str[i]<’0′ || str[i]>’9′)
str[j++] = str[i];
str[j] = ‘\0′;
}

int main(int argc, char* argv[]) {
char str[] = “abc123ef4g4h5″;
printf(“%s\n”, str);
delNum(str);
printf(“