数据结构考试题目 数据结构 面试题 4

数据结构 面试题 4  

判断链表是否存在环型链表问题 判断一个链表是否存在环 例如下面这个链表就存在一个环 例如 N >N >N >N >N >N 就是一个有环的链表 环的开始结点是N 这里有一个比较简单的解法 设置两个指针p p 每次循环p 向前走一步 p 向前走两步 直到p 碰到NULL指针或者两个指针相等结束循环 如果两个指针相等则说明存在环 struct link { int data; link* next; };

bool IsLoop(link* head) { link* p =head *p = head; if (head ==NULL || head >next ==NULL) { return false; } do{ p = p >next; p = p >next >next; } while(p &# ;&# ; p >next &# ;&# ; p !=p ); if(p == p ) return true; else return false; }

链表反转的问题 单向链表的反转是一个经常被问到的一个面试题 也是一个非常基础的问题 例如 一个链表是这样的 > > > > 通过反转后成为 > > > > 最容易想到的方法遍历一遍链表 利用一个辅助指针 存储遍历过程中当前指针指向的下一个元素 然后将当前节点元素的指针反转后 利用已经存储的指针往后面继续遍历 源代码如下 struct linka { int data; linka* next; };

void reverse(linka*&# ; head) { if(head ==NULL) return; linka*pre *cur *ne; pre=head; cur=head >next; while(cur) { ne = cur >next; cur >next = pre; pre = cur; cur = ne; } head >next = NULL; head = pre; } 还有一种利用递归的方法 这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点 源代码如下 不过这个方法有一个缺点 就是在反转后的最后一个结点会形成一个环 所以必须将函数的返回的节点的next域置为NULL 因为要改变head指针 所以我用了引用 算法的源代码如下 linka* reverse(linka* p linka*&# ; head) { if(p == NULL || p >next == NULL) { head=p; return p; } else { linka* tmp = reverse(p >next head); tmp >next = p; return p; } }

判断两个数组中是否存在相同的数字的问题 给定两个排好序的数组 怎样高效得判断这两个数组中存在相同的数字？ 这个问题首先想到的是一个O(nlogn)的算法 就是任意挑选一个数组 遍历这个数组的所有元素 遍历过程中 在另一个数组中对第一个数组中的每个元素进行binary search 用C++实现代码如下 bool findmon(int a[] int size int b[] int size ) { int i; for(i= ;i ;i++) { int start= end=size mid; while(start<=end) { mid=(start+end)/ ; if(a[i]==b[mid]) return true; else if (a[i] end=mid ; else start=mid+ ; } } return false; } 后来发现有一个 O(n)算法 因为两个数组都是排好序的 所以只要一次遍历就行了 首先设两个下标 分别初始化为两个数组的起始地址 依次向前推进 推进的规则是比较两个数组中的数字 小的那个数组的下标向前推进一步 直到任何一个数组的下标到达数组末尾时 如果这时还没碰到相同的数字 说明数组中没有相同的数字 bool findmon (int a[] int size int b[] int size ) { int i= j= ; while(i &# ;&# ; j ) { if(a[i]==b[j]) return true; if(a[i]>b[j]) j++; if(a[i] i++; } return false; }

最大子序列问题 给定一整数序列A A An （可能有负数） 求A ~An的一个子序列Ai~Aj 使得Ai到Aj的和最大 例如 整数序列 的最大子序列的和为 对于这个问题 最简单也是最容易想到的那就是穷举所有子序列的方法 利用三重循环 依次求出所有子序列的和然后取最大的那个 当然算法复杂度会达到O(n^ ) 显然这种方法不是最优的 下面给出一个算法复杂度为O(n)的线性算法实现 算法的来源于Programming Pearls一书 在给出线性算法之前 先来看一个对穷举算法进行优化的算法 它的算法复杂度为O(n^ ) 其实这个算法只是对对穷举算法稍微做了一些修改 其实子序列的和我们并不需要每次都重新计算一遍 假设Sum(i j)是A[i] A[j]的和 那么Sum(i j+ ) = Sum(i j) + A[j+ ] 利用这一个递推 我们就可以得到下面这个算法 int max_sub(int a[] int size) { int i j v max=a[ ]; for(i= ;i { v= ; for(j=i;j { v=v+a[j];//Sum(i j+ ) = Sum(i j) + A[j+ ] if(v>max) max=v; } } return max; } 那怎样才能达到线性复杂度呢？这里运用动态规划的思想 先看一下源代码实现 int max_sub (int a[] int size) { int i max= temp_sum= ; for(i= ;i { temp_sum+=a[i]; if(temp_sum>max) max=temp_sum; else if(temp_sum< ) temp_sum= ; } return max; }

按单词反转字符串的问题 并不是简单的字符串反转 而是按给定字符串里的单词将字符串倒转过来 就是说字符串里面的单词还是保持原来的顺序 这里的每个单词用空格分开 例如 Here is 经过反转后变为 is Here 如果只是简单的将所有字符串翻转的话 可以遍历字符串 将第一个字符和最后一个交换 第二个和倒数第二个交换 依次循环 其实按照单词反转的话可以在第一遍遍历的基础上 再遍历一遍字符串 对每一个单词再反转一次 这样每个单词又恢复了原来的顺序 char* reverse_word(const char* str) { int len = strlen(str); char* restr = new char[len+ ]; strcpy(restr str); int i j; for(i= j=len ;i j ) { char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; } int k= ; while(k { i=j=k; while(restr[j]!= &# ;&# ; restr[j]!= ) j++; k=j+ ; j ; for(;i j ) { char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; } } return restr; } 如果考虑空间和时间的优化的话 当然可以将上面代码里两个字符串交换部分改为异或实现 例如将 char temp=restr[i]; restr[i]=restr[j]; restr[j]=temp; 改为 restr[i]^=restr[j]; restr[j]^=restr[i]; restr[i]^=restr[j]; ;i++;i++

删除数组中重复的数字问题 一个动态长度可变的数字序列 以数字 为结束标志 要求将重复的数字用一个数字代替 例如 将数组 转变成 问题比较简单 要注意的是这个数组是动态的 所以避免麻烦我还是用了STL的vector #include #include using namespace std; //remove the duplicated numbers in an intger array the array was end with ; //e g &# ;> void static remove_duplicated(int a[] vector &# ; _st) { _st push_back(a[ ]); for(int i= ;_st[_st size() ]!= ;i++) { if(a[i ]!=a[i]) _st push_back(a[i]); } } 当然如果可以改变原来的数组的话 可以不用STL 仅需要指针操作就可以了 下面这个程序将修改原来数组的内容 void static remove_duplicated (int a[]) { if(a[ ]== || a==NULL) return; int insert= current= ; while(a[current]!= ) { if(a[current]!=a[current ]) { a[insert]=a[current]; insert++; current++; } else current++; } a[insert]= ; }