一、数据结构部分
1、数组和链表的区别
C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。
从逻辑结构来看:数组必须事先定义固定的长度(元素个数)，不能适应数据动态的增减的情况，即数组的大小一旦定义就不能改变。当数据增加时，可能超出原来定义的元素个数，当数据减少时，造成内存浪费；链表动态的进行存储分配，可以适应数据动态的增减的情况，且可以方便的插入、删除数据项(数组中插入、删除数据项时，需要移动其他数据项)。 从内存存储来看：(静态)数组从栈中分配空间(用new创建的堆中)，对于程序员快速，但是自由度小，链表从堆中分配空间，自由度大但是申请管理比较麻烦。
从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问，链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效率比数组要低。
2、链表的一些操作：
链表的反转：参考博客链表的逆序
链表存在环路的判断：参考博客判断链表是否有环及两链表是否相交
有序链表:保持数据有序的链表叫做有序链表。
定义一个有序链表(Java实现)：
class Link{
public long dData;
public Link next;
public Link(long ){
dData = dd;
}
}
class SortedList{
private Link first;
public SortedList(){
first = null;
}
//插入一个元素
public void insert(long key){
Link newLink = new Link(key);
Link previous = null;
Link current = first;
while(current != null && key > current.dData){
previous = current;
current = current.next;
}
if(previous == null){
first = newLink;
}else{
previous.next = newLink;
}
newLink.next = current;
}
}
有序链表的效率：在有序链表插入和删除某一项最多需要O(N)次比较，(平均N/2)，因为必须沿着链表上一步一步才能找到正确的位置。然而，可以在O(1)的时间内找到或者删除最小值，因为它总是在表头。如果一个应用频繁的存取最小项，且不需要快速的插入，那么有序链表是一个有效的方案选择。例如：优先级队列可以用有序链表来实现。
表插入排序：有序链表可以用于一种高效的排序机制，假设一个无序数组，如果从这个数组中取出数据，然后一个一个地插入有序链表，他们自动的按顺序排列，把他们从有序表中删除，重新放入数组，那么数组就会排好序了。
双向链表相关操作:
双向链表既提供了向前遍历，也允许向后遍历。每个链节点有两个指向其他节点的引用，第一个像普通链表一样指向下一个链接点，第二个指向前一个链接点。数据结构如下：
class Link{
public long dData;
public Link next;
public Link previous;
...
}
循环链表相关操作：当循环链表的基本操作，双向循环链表的操作
3、队列(特殊的如优先队列参考博客http://blog.csdn.net/zhang20072844/article/details/10286997)，栈的应用。
4、二叉树的基本操作
二叉树的三种遍历方式(前序、中序、后序)及递归和非递归实现，三种方式的主要应用(如后缀表达式)。相关操作的时间复杂度。
先序遍历的递归算法：
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){
if(T){
if(Visit(T->data)){
if(PreOrderTraverse(T->lchild, Visit)){
if(PreOrderTraverse(T->rchild, Visit)){
return OK;
}
}
}
return ERROR;
}else return OK;
}
根据递归算法执行过程中的递归工作栈的状态变化状况可以写出相应的非递归算法。
Status InOrderTravers(BiTree T, Status(*visit)(TElemType e)){
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
InitStack(S);
Push(S, T);//根指针进栈
while(!StackEmpty(S)){
while(GetTop(S,p) && p)
Push(S,p->lchild);//向左走到尽头
Pop(S,p);//空指针出栈
if(!StackEmpty(S)){
Pop(S,p);
if(!Visit(p->data))
return error;
Push(S,p->rchid);
}
}
}
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){
//采用链表结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树T的非递归算法，对每个元素调用函数Visit
InitStack(S); p=T;
while(p || !StackEmpty){
if(p){
Push(S,p);
p = p->lchild;//根指针进栈，遍历左子树
}else{
Pop(S, p);
if(!Visit(p->data)) return ERROR;
p = p->rchild;
}
}
return OK;
}
5、字符串相关
(1)字符串逆序
普通逆序：
char[] chars = new char[a.length()];
for(int i=chars.length-1,j=0;i>=0;i--,j++){
chars[j] = a.toCharArray()[i];
}
System.out.println(String.valueOf(chars));
原地逆序：不允许额外分配空间，思想是将字符串两边的字符逐个交换。
public String reverse(String s){
//普通逆序
/* char[] chars = new char[s.length()];
for(int i=chars.length-1,j=0;i>=0;i--,j++){
chars[j] = s.toCharArray()[i];
}*/
//原地逆序
char[] chars = s.toCharArray();
for(int i=0,j=chars.length-1;i<=j;i++,j--){
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}
return String.valueOf(chars);
}
不允许临时变量的原地逆序。上面的原地逆序虽然没有额外的分配空间，但还是使用了临时变量，严格的说也算是额外空间吧，如果再严格一点，连临时变量 也不允许的话，主要有下面两种方法：一是异或操作，因为异或操作可以交换两个变量而无需借助第三个变量，二是使用字符串的结束符'\0'所在的位置作为交换空间，这样有个局限，就是只适合以'\0'结尾的字符串，对于不支持这种字符串格式的语言就不能使用了。 //判断是否是一个中文汉字
public static boolean isChineseChar(char c) throws UnsupportedEncodingException{
return String.valueOf(c).getBytes("GBK").length>1;
}
//截取字符串
public static String cutString(String orignal, int count) throws UnsupportedEncodingException{
if(orignal != null && !"".equals(orignal)){
orignal = new String(orignal.getBytes(), "GBK");
if(count > 0 && count < orignal.getBytes("GBK").length){
StringBuffer buffer = new StringBuffer();
char c;
for(int i=0;i<count;i++){
c = orignal.charAt(i);
buffer.append(c);
if(isChineseChar(c)){
--count;
}
}
return buffer.toString();
}
}
return orignal;
}
(3)字符串匹配算法二、算法部分
1、排序算法
排序算法是最基本的，最常用的算法，也是笔试面试中最常被考察到的算法。最基本的冒泡排序，选择排序，插入排序要很快的用代码实现，这些主要考察你的实际编码能力。堆排序，归并排序，快排序，这些算法需要熟悉主要的思想和需要注意细节的地方，需要熟悉常用排序算法的时间和空间复杂度。
各种排序算法的使用范围总结：
(1)当数据规模较小的时候，可以使用简单的排序算法如直接插入排序或直接选择排序。
(2)当文件的初态已经基本有序时，可以使用插入排序或冒泡排序。
(3)当数据规模较大时，应用速度快的排序算法。可以考虑快速排序。当记录随机分布的时候，快排的平均时间最短，但可能出现最坏的情况，这时候的时间复杂度是O(n^2)，且递归深度为n，所需的栈空间为O(n)。
(4)堆排序不会出现快排那样的最坏情况，且堆排序所需的辅助空间比快排要少。但这两种算法都不是稳定的，若要求排序时稳定，可以考虑用归并排序。
(5)归并排序可以用于内排序，也可以用于外排序。在外排序时，通常采用多路归并，并且通过解决长顺串的合并，产生长的初始串，提高主机与外设并行能力等措施，以减少访问外存次数，提高外排序的效率。
常见排序算法java实现：
插入排序：
public class InsertSort {
public static void main(String[] args){
int[] a = {0,2,1,5,4,3};
inserSort(a);
for(int i=1;i<a.length;i++){
System.out.println(a[i]);
}
}
public static void inserSort(int[] l){
int j=0;
for(int i=2;i<l.length;++i){
if(l[i] < l[i-1]){
l[0] = l[i];
l[i] = l[i-1];
for(j=i-2;l[0] < l[j];--j){
l[j+1] = l[j];
}
l[j+1] = l[0];
}
}
}
}
快速排序
public class Qsort {
public static void main(String[] args){
int[] a = {3,2,5,4,1};
qSort(a, 0, a.length-1);
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
public static void qSort(int[] a, int low, int high){
if(low < high){
int p = partion(a, low, high);
qSort(a, low, p-1);
qSort(a, p+1, high);
}
}
public static int partion(int[] a, int low, int high){
int p = a[low];
while(low < high){
while(low<high && a[high] > p) --high;
a[low] = a[high];
while(low<high && a[low] < p) ++low;
a[high] = a[low];
}
a[low] = p;
return low;
}
}
选择排序
public class SelectSort {
public static void main(String[] args){
int[] a = {3,2,5,4,1};
selectSort(a);
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
public static void selectSort(int[] a){
for(int i=0;i<a.length;i++){
int j = selectMinKey(a, i);
if(i != j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
public static int selectMinKey(int[] a, int i){
int min = Integer.MAX_VALUE,index=0;
for(int j=i;j<a.length;j++){
if(a[j] < min){
min = a[j];
index = j;
}
}
return index;
}
}
归并排序：
public class MergeSort {
public void mergeSort(int[] s){
msort(s, s, 1, s.length);
}
public void msort(int[] sr, int[] tr, int s, int t){
if(s == t) tr[s] = sr[s];
else{
int m = s+t/2;
int[] tr2 = null;
msort(sr, tr2, s, m);
msort(sr, tr2, m+1, t);
merge(sr, tr2, s, m, t);
}
}
public void merge(int[] sr, int[] tr, int i, int m, int n){
int j = 0,k=0;
for(j=m+1, k=i;i<m&&j<n;k++){
if(sr[i] < sr[k]) tr[k] = sr[i++];
else tr[k] = sr[j++];
}
if(i <= m){
for(int temp1=i;temp1<=m;temp1++){
tr[i] = sr[m];
}
}
if(j<=n){
}
for(int temp2=j;temp2<=n;temp2++){
tr[j] = sr[j];
}
}
}
2、查找算法
能够熟练写出或者是上机编码出二分查找的程序
int Search_bin(SSTable ST, KeyType key){
//在有序表ST中这般查找其关键字等于key的数据元素，
//则函数值为该元素在表中的位置，否则为0
low = 1; high=ST.length;
while(low < high){
mid = (low+hign)/2;
if(EQ(key, ST.elem[mid].key)) return mid;
else if(LT(key, ST.elem[mid].key)) high = mid-1;
else low = mid + 1;
}
return 0;
}
3、hash算法
4、一些算法设计思想
相关推荐
此外，面试时，数据结构和算法也是考察程序员能力的重要标准，许多知名科技公司都以算法题来评估应聘者的编程和逻辑思维能力。 总之，“现代计算机常用数据结构和算法”是一门深入探讨编程基础的教程，通过学习，你...
8. **常用算法**：除了上述数据结构，面试还会涉及排序、查找、图论、动态规划、贪心算法等经典算法。例如，快速排序、归并排序、二分查找、KMP字符串匹配、最小生成树（Prim或Kruskal）、最短路径（Dijkstra或...
在准备面试，特别是针对微软这样的顶级科技公司的面试时，数据结构和算法是不可或缺的重要部分。这份资源"面试前必备（微软数据结构+算法）"包含了针对这类面试的100道题目，旨在帮助求职者全面了解和掌握相关知识。...
在编程领域，尤其是在Java开发中，理解和掌握常用的数据结构与算法是至关重要的。这些基础知识能够帮助我们编写出更高效、可维护的代码。本资源"JAVA常用数据结构和算法"聚焦于这一核心主题，旨在深化对Java中数据...
在IT领域，尤其是在Java编程中，数据结构和算法是核心基础，它们对于开发高效、优化的软件至关重要。本文将深入探讨这些主题，并结合面试题，帮助你提升技能和准备面试。 首先，我们要理解数据结构。数据结构是组织...
在面试中，数据结构和算法的掌握程度往往被用来评估候选人的逻辑思维能力和问题解决能力。以下是对这些关键概念的详细阐述： 一、数据结构 1. 数组：最基础的数据结构，它是一系列相同类型元素的集合，通过下标...
在名企面试中，面试官通常会通过考察应聘者的数据结构和算法能力来评估其编程技能和问题解决能力。这里我们将深入探讨这两个主题，并结合提供的文件内容，给出一些可能的面试题目和解答思路。 首先，数据结构是存储...
数据结构与算法是计算机科学的基础，对于...以上知识点是数据结构与算法面试题中常见的部分，每个主题下都可能有深入的理论讲解和实践题目，对于准备面试的开发者来说，全面掌握这些内容将大大提升在面试中的竞争力。
在面试中，数据结构和算法的考察占据着重要地位，因为它们是软件开发和计算机科学中不可或缺的基础。 单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在面试中...
本书关注算法面试的实用性，特别强调了解题思路和常用代码模板。如遇到二叉树问题，可以尝试使用广度优先搜索来解决。同时，书中的“解题小经验”部分提供了许多实用的解题策略。通过学习并理解这些模板，读者可以更...
尽管很多人可能会有这样的误解，认为数据结构和算法是高深且脱离实际工作的理论知识，只在面试或者特定情况下才会用到。但事实上，这门学科与我们的工作息息相关，无论是在业务开发还是基础架构研发方面，数据结构与...
文件描述了一个名为July的人在csdn论坛上分享微软等公司的数据结构与算法面试题集，并与网友共同讨论解答，最终形成了名为“结构之法算法之道”的博客。这说明面试题库对于程序员的准备和提高具有极大的帮助，而且在...
数据结构与算法分析是计算机科学中的核心领域，对于任何想要深入理解编程和软件开发的人员来说，这都是不可或缺的知识。这个电子书合集包含了23本相关书籍，其中包括经典著作如《算法导论》、《编程之美》以及《设计...
这份“常见数据结构与算法笔试面试题大集合”涵盖了这一领域的核心概念，旨在帮助求职者更好地准备相关考试和面试。 1. **数组**：数组是最基础的数据结构，它提供了一种在内存中存储和访问固定数量元素的方式。...
总的来说，"数据结构与算法面试宝典"应该包含了大量的实践题目、解析和技巧，帮助面试者巩固基础，提升逻辑思维能力，并在面试中脱颖而出。通过系统学习和大量练习，不仅可以应对面试，还能为实际工作中的问题解决...
网上搜集的一个c++数据结构与算法的文档，包含各类数据结构、算法、大量数据处理等方法，然后我还增加了那些是笔试面试中重点需要看的。希望能帮助到找工作的同学。另外可以从我的资源中下载c++基础知识的文档。
在面试中，面试官可能会考察你在实际场景中如何应用这些数据结构和算法。例如，询问你如何设计一个高效的缓存系统，这就涉及到哈希表和LRU（最近最少使用）策略；或者让你分析一个递归算法的时间复杂度，这需要理解...
总之，“数据结构和常用算法大全”这个资源包提供了全面的学习材料，涵盖了从基础到高级的各种数据结构和算法。通过深入学习和实践，不仅可以增强编程技能，还能为解决实际问题提供有力的工具。