---------------------------------------------------
1. 链表和数组的区别在哪里？
数组静态分配内存，链表动态分配内存；
数组在内存中连续存放，链表不连续；
数组可以用下标定位，时间复杂度 O(1)，链表定位元素时间复杂度 O(n)；
数组删除或插入元素时间复杂度 O(n)，链表时间复杂度 O(1)；
---------------------------------------------
2. 编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
可用排序方法 (考虑单向链表)：归并，插入、冒泡、选择。
(考虑双向链表)：归并、快排，插入、冒泡、选择。
优先考虑归并，时间复杂度低，实现简单。
也可以先建立一个数组，把链表里的指针都放进去，然后排序，最后重建链表。
-------------------------------------------------
3. 编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
可用排序方法：基数 (O(n)，对元素有限制)，归并、快排、堆 (O(nlogn)，插入、冒泡、选择(O(n^2))。
如果不考虑实际应用需要，优先考虑归并，时间复杂度低，实现简单。
实际应用中，需要根据实际情况选择：若数据元素个数有限，考虑基数；若数据随机，考虑快排，因为随机情况下快排平均复杂度低；若数据接近有序，考虑归并。
------------------------------------------------
4. 请编写能直接实现 strstr 函数功能的代码。
/* 实现一。 */
char * strstr(const char * content, const char * pattern)
{
const char * p_content;
const char * p_pattern;
if (NULL == content || NULL == pattern)
{
return NULL;
}
p_content = content;
p_pattern = pattern;
while (*p_content && *p_pattern)
{
if (*p_content == *p_pattern)
{
++p_content;
++p_pattern;
}
else
{
p_content = p_content - (p_pattern - pattern) + 1;
p_pattern = pattern;
}
}
if (0 == *p_pattern)
{
return p_content - (p_pattern - pattern);
}
else
{
return 0;
}
}
/* 实现二 (KMP)。 */
#include <stdlib.h>
char * strstr(const char * content, const char * pattern)
{
int i;
int j;
int len;
int * next;
if (NULL == content || NULL == pattern)
{
return NULL;
}
len = 0;
while (pattern[len])
{
++len;
}
next = (int *)malloc(len * sizeof(int));
next[0] = -1;
i = 0;
j = -1;
while (pattern[i])
{
if (-1 == j || pattern[i] == pattern[j])
{
++i;
++j;
if (pattern[i] == pattern[j])
{
next[i] = next[j];
}
else
{
next[i] = j;
}
}
else
{
j = next[j];
}
}
i = 0;
j = 0;
while (content[i] && pattern[j])
{
if (content[i] == pattern[j])
{
++i;
++j;
}
else
{
j = next[j];
if (-1 == j)
{
++i;
++j;
}
}
}
free(next);
if (pattern[j])
{
return NULL;
}
else
{
return &content[i - j];
}
}
------------------------------------------------
5. 编写反转字符串的程序，要求优化速度、优化空间。
#include <string.h>
void reverse_string(char * str)
{
int head;
int tail;
if (NULL == str)
{
return;
}
head = 0;
tail = strlen(str) - 1;
while (head < tail)
{
char tmp;
tmp = str[head];
str[head] = str[tail];
str[tail] = tmp;
++head;
--tail;
}
}
------------------------------------------------
6. 在链表里如何发现循环链接？
#include <stddef.h>
struct listtype
{
int data;
struct listtype * next;
};
typedef struct listtype * list;
/* Check that whether there is loop in the singly linked list sll or not. */
int find_circle(list sll)
{
list fast = sll;
list slow = sll;
if (NULL == fast)
{
return -1;
}
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
return 1;
}
}
return 0;
}
参考：
http://ostermiller.org/find_loop_singly_linked_list.html
---------------------------------------------------
7. 给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
---------------------------------------------------
8. 写一个函数，检查字符是否是整数，如果是，返回其整数值。 (或者：怎样只用 4 行代码编写出一个从字符串到长整形的函数？)
#include <ctype.h>
long strtol(const char * str)
{
int sign = 1;
long value;
if ('+' == *str)
{
++str;
}
else if ('-' == *str)
{
sign = -1;
++str;
}
value = 0;
while (*str)
{
if (!isdigit(*str))
{
return -1;
}
else
{
value = value * 10 + *str - '0';
}
++str;
}
return value * sign;
}
--------------------------------------------
9. 给出一个函数来输出一个字符串的所有排列。
#include <stdio.h>
void permutation(char * p_str, char * p_begin)
{
if(!p_str || !p_begin)
{
return;
}
/*
* If p_begin points to the end of string,
* this round of permutation is finished,
* print the permuted string.
*/
if('\0' == *p_begin)
{
printf("%s\n", p_str);
}
/* Otherwise, permute string. */
else
{
char * p_ch;
for(p_ch = p_begin; *p_ch != '\0'; ++p_ch)
{
char temp;
/* Swap p_ch and p_begin. */
temp = *p_ch;
*p_ch = *p_begin;
*p_begin = temp;
permutation(p_str, p_begin + 1);
/* Restore p_ch and p_begin. */
temp = *p_ch;
*p_ch = *p_begin;
*p_begin = temp;
}
}
}
int main(int argc, char * argv[])
{
if (argc > 1)
{
permutation(argv[1], argv[1]);
}
return 0;
}
参考：http://zhedahht.blog.163.com/blog/static/254111742007499363479/
-------------------------------------------
10. 请编写实现 malloc 内存分配函数功能一样的代码。
---------------------------------------------
11. 给出一个函数来复制两个字符串 A 和 B。字符串 A 的后几个字节和字符串 B 的前几个字节重叠。
-------------------------------------------------
12. 怎样编写一个程序，把一个有序整数数组放到二叉树中？
------------------------------------------------
13. 怎样从顶部开始逐层打印二叉树结点数据？请编程实现。
-------------------------------------------------
14. 转置单向链表 (也就是反序，注意链表的边界条件并考虑空链表)。
#include <stddef.h>
struct listtype
{
int data;
struct listtype * next;
};
typedef struct listtype * list;
/* Reverse the singly linked list *psll. */
void reverse_singly_linked_list(list * psll)
{
list h = NULL;
list p = *psll;
if (!psll || !*psll)
{
return;
}
while (p)
{
list tmp = p;
p = p->next;
tmp->next = h;
h = tmp;
}
*psll = h;
}
-------------------------------------------------
15. 将以空格为分隔符分隔的字符串逆序打印，但单词不逆序。例如“Hello world Welcome to China”的打印结果为“China to Welcome world Hello”。
#include <stdio.h>
#include <string.h>
/* Print string str partially, from start to end-1. */
void print_word(const char * str, int start, int end)
{
int i;
for (i = start; i < end; ++i)
{
printf("%c", str[i]);
}
}
/* Reversely print string str. */
void reversely_print_string(const char * str)
{
int len, i, end;
len = strlen(str);
end = len;
for (i = len - 1; i >= 0; --i)
{
if (' ' == str[i])
{
/* Print the word after this space. */
print_word(str, i + 1, end);
/* Print the space. */
printf("%c", str[i]);
/* Set the right boundary of the previous word. */
end = i;
}
}
/* Print the first word. */
print_word(str, 0, end);
}
int main(int argc, char * argv[])
{
if (argc > 1)
{
reversely_print_string(argv[1]);
}
printf("\n");
return 0;
}
------------------------------------------------------
16. 有 N 个数，这个 N 很大， 如有 100000 个，从这 N 个数中找出最大的 M 个数 (M << N)，它的复杂度大概为多少？
法壹：
采用堆排序的方法。
1) 先建大顶堆，时间 O(N)，然后 M 次取堆顶元素并维护堆，时间为 O(MlogN)。因此总的时间复杂度为 O(N + MlogN)。如果 M 为常数，则总的时间复杂度为 O(N)。
2) 如果 N 很大，不能一次载入内存。则我们可以先读入 M 个数，然后在这 M 个数基础上建小顶堆，时间 O(M)。然后对剩下的 N-M 个数，每读一个，将其与堆顶元素比较：若小等，读下一个；若大，则将其替换堆顶元素，然后维护一次堆，时间为 O(logM)。因此，最坏情况下时间复杂度为 O(M + N-M + (N-M)logM) = O(N + (N-M)logM)。若 M 为常数，则总的时间复杂度也为 O(N)。
比较 1 和 2：因为 M << N，因此 1 要快于 2。
法贰：
采用快速排序的方法。不断的划分后半部分 (比某个数大的部分)，直到这个部分的数量小等于 M。如果后面部分已不足 M 个元素，则在前一部分找不够的个数以补足 M 个。如此循环直到找到 M 个。
也可以在后面部分个数小到一定程度时，比如小于 10M，进行插入排序，找最大的 M 个。
这个方法的时间复杂度不理想，最坏情况下会是 O(N^2)。
法叁：
1) 从 N 个数中取出 M 个，以插入排序法,按照从小到大的顺序放入数组 arr。
2) 从剩余的 N-M 个数中，依次取出每一个数和 arr[0] 比较，如大于 arr[0], 则删除 arr[0], 采用插入排序将此数插入到数组。
复杂度分析：步骤 1 花费时间 O(M^2)；步骤 2 代价分为两部分：和 arr[0] 比较以及插入到数组 arr。对于前者，最好情况，最坏情况总是一样的，计作 O(N-M). 对于后者，虽然每次插入的代价不是固定的，但和 N 无关，平均和最快情况都是 O(M^2)，故这部分时间复杂度是 O((N-M)M^2)。总的复杂度是 O((N-M)M^2)。
参考：
1) http://blog.csdn.net/patriotlml/archive/2006/09/09/1199793.aspx
2) http://topic.csdn.net/t/20061031/14/5122253.html
3) http://topic.csdn.net/t/20051004/13/4307089.html
-----------------------------------------------------
|
| Windows Mobile | J2ME | 下载中心 | 游戏策划 | 招聘与求职 | 购书指南 | 视频教程
