先锋商泰一面

先锋商泰一面"/>

先锋商泰一面

1、什么是面向对象的编程思想(oop)？
面向对象就是用计算机模拟现实中实体及其关系
首先从字面意思来看，对象是人们要进行研究的事物，它不仅能表示具体的事物，还能表示抽象的规则、计划或事件
把具有相同或相似性质的对象进行抽象化就是类。因此，对象的抽象是类，类的具体化就是对象，也可以说类的实例是对象。
说白了就是就是用计算机模拟现实中实体机其关系
下面这个博客讲解的很清楚：

2、栈和队列
栈：先进后出的数据结构，操作受限，只能在一端进行插入删除操作，有一个指针指向栈顶。
STL中的stack(底层是deque)中的方法接口有：
top、pop 、push、empty、size

队列：先进先出的数据结构，操作受限，只能在尾端进行插入，头部进行进行删除，有两个指针，一个指向对头，一个指向队尾
STL中的deque中的方法接口有：
front、back、push、pop、size、empty

3、树的深度优先搜索和广度优先搜索

深度优先搜索：沿着树的深度遍历树的节点，尽可能深的搜索树的分支
深度优先搜索(先序遍历)：ABDECFG
利用栈后进先出的特点，将右子树压入栈中，在压入左子数，这样出栈就先出左子树

void DepthFirstSearch(BitNode* root)
{stack<BitNode*> nodestack;nodestack.push(root);while(!nodestack.empty()){BitNode * node = nodestack.top();cout<<node->data<<' ';nodestack.pop();if(node->left){nodestack.push(node->left);}if(node->right){nodestack.push(node->right);}}
}

广度优先搜索：从根节点沿着树的宽度搜索遍历，按照树的层次来遍历一棵树
广度优先搜索(中序遍历)：ABCDEFG
利用队列先进先出的特性， 来实现遍历

void BreadthFirstSearch(BitNode* root)
{queue<BitNode*> nodequeue;nodequeue.push(root);while(!nodequeue.empty()){BitNode * node = nodestack.front();cout<<node->data<<' ';nodequeue.pop();if(node->left){nodequeue.push(node->left);}if(node->right){nodequeue.push(node->right);}}
}

3、快速排序
思想：挖坑填数+分治法
(1)、挖坑填数：从数组中选取一个基准，用l和h分别标记数组的头和尾，h从后往前跑，找到比基准小的数字，填入基准被挖走的坑中，l从头往后跑，找到比基准大的数字，填入刚刚h的位置
一直重复这个操作，知道l和h相遇，相遇的位置就是基准该放的位置，此刻，基准左边的值都比基准小，基准右边的值都比基准大。
(2)、分治法
只要数据量大于2，就一直重复上面的操作
对之前基准所到位置的左边和右边分别重复（1）的操作。

#include<iostream>
using namespace std;static int Datum(int *arr,int low,int high)//一趟划分过程,返回基准下标
{int index;int tmp = arr[low];if(arr == NULL && low>high){return -1;}while(low<high){while((low<high)&& arr[high]>=tmp) --high;if(low == high) break;else{arr[low] = arr[high];}while((low<high)&& arr[low]<=tmp) --low;if(low == high) break;else{arr[high] = arr[low];}arr[low] = tmp;index = low;}return index;
}//时间递归深度 O(logn)  //空间 O(logn)
static void Quick(int *arr,int low,int high)
{int index = Datum(arr,low,high);if(low+1<index){Datum(arr,low,index-1);}if(index<high-1){Datum(arr,index+1,high);}
}void Q_sort(int *arr,int n)
{Quick(arr,0,n-1);//递归调用时，接口和实际调用有差距，重新实现一个子函数
}