由于找工作要恶补数据结构的基础，为了手撕代码方便，写了很多代码并测试。都是些找工作常考的，现在贴上来，不定期更新部分代码。
- 含有链表反转，排序算法，查找算法和二叉树的遍历算法。
- 都是常考的手撕代码，建议找工作的童鞋使劲背。
- 里面每一段代码都是经过调试的。
- IDE建议使用CLion，个人感觉比较好用，没有VS那么大，不想破解就下社区版，配置教程可以参考我另一篇文章Window10极简CLion配置教程。
链表反转
1. 结点定义
struct node{
int node_data;
struct node* next;
node(int x) : node_data(x){}
};
2. 递归版
node* In_reverseList(node* head){
if(head!=NULL && head->next != NULL){
// l是新链表头
node* l = In_reverseList(head->next);
head->next->next = head;
head->next=NULL;
return l;
} else
return head;
}
3. 非递归版
node* reverseList(node* head){
if (head != NULL && head->next != NULL){
node* p = head;
node *q, *newNode=NULL;
while (p!=NULL) {
q = p->next;
p->next=newNode;
newNode=p;
p=q;
}
return newNode;
}
}
排序算法
1.冒泡排序法
// 冒泡排序
vector<int> bubblesort(vector<int> u_in)
{
vector<int> unii = u_in;
for (int i = 0; i < unii.size(); i++)
{
int tmp = 0;
for (int j = i + 1; j < unii.size(); j++)
{
if (unii[i] > unii[j])
{
tmp = unii[i];
unii[i] = unii[j];
unii[j] = tmp;
}
}
}
return unii;
}
2.选择排序法
// 选择排序法
void selectsort(int *a, int n) {
int min;
for (int i = 0; i < n; i++) {
min = i;
for (int j = i + 1; j < n; j++) {
if (a[min] > a[j]) {
min = j;
}
}
if (min != i) {
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
3.快速排序法
// 快排，数组版
void quicksort(int *a, int left, int right)
{
if (left >= right) return;
int i = left;
int j = right;
int based = a[left];
while (i < j) {
while (i < j && a[j] >= based) j--;
if (i < j) {
a[i] = a[j];
i++;
}
while (i < j && a[i] < based) i++;
if (i < j) {
a[j] = a[i];
j--;
}
if (i >= j) break;
}
a[i] = based;
quicksort(a, left, j - 1);
quicksort(a, j + 1, right);
}
4.归并排序法
// 归并排序单元使用
void mergearr(int* a, int begin, int mid, int end, int *temp){
int i=begin, j=mid+1;
int m = mid, n = end;
int k = 0;
while (i <= m && j<= n){
if (a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while (i<=m)
temp[k++]=a[i++];
while (j<=n)
temp[k++]=a[j++];
for (i=0;i<k;i++){
a[begin+i]=temp[i];
}
}
// 归并排序算子
void _merge_sort(int* a, int begin, int end, int *temp){
if(begin<end) {
int mid = (begin + end) / 2;
_merge_sort(a, begin, mid, temp);
_merge_sort(a, mid + 1, end, temp);
mergearr(a, begin, mid, end,temp);
}
}
// 归并排序
int* MergeSort(int *a, int len){
int *temp = new int[len];
_merge_sort(a,0,len-1,temp);
return temp;
}
查找算法
1.二分查找（递归版）
// 二分查找
int getkey (int* a, int key, int low, int high)
{
int mid = (low+high)/2;
if (low>high) return -1;
if (a[mid]==key) return mid;
else if (a[mid]<key)
return getkey(a,key,mid+1,high);
else
return getkey(a,key,low,mid-1);
}
int main(){
int a[8]={5,10,29,37,39,56,65,88};
int key = 88;
cout<<getkey(a,key,0,8);
return 0;
}
二叉树遍历（非递归版）
由于递归版过于简单，一般来说面试是不会考的，所以只放非递归版。
- 节点定义
// 二叉树节点
struct binode{
int val;
binode* left;
binode* right;
explicit binode(int v){
val=v;
left=nullptr;
right=nullptr;
}
binode(int v, binode* l, binode* r){
val=v;
left=l;
right=r;
}
void setlrnode( binode* l, binode* r){
left=l;
right=r;
}
void setlnode( binode* l){
left=l;
}
void setrnode( binode* r){
right=r;
}
};
1.先序遍历
// 先序遍历
void preorder(binode* root){
if (root==nullptr) return;
binode *p=root;
stack<binode*> s;
while (p!=nullptr || !s.empty()){
while (p!= nullptr){
cout<<p->val;
s.push(p);
p=p->left;
}
if (!s.empty()){
p=s.top();
s.pop();
p=p->right;
}
}
}
2.中序遍历
中序遍历就是先序遍历的cout放到if里面。
// 中序遍历
void midorder(binode* root){
if (root==nullptr) return;
binode *p=root;
stack<binode*> s;
while (p!=nullptr || !s.empty()){
while (p!= nullptr){
s.push(p);
p=p->left;
}
if (!s.empty()){
p=s.top();
cout<<p->val;
s.pop();
p=p->right;
}
}
}
3.后序遍历
后续遍历很容易出问题，之前的写的会内存泄露，现在修改了。
// 后序遍历
void postorder(binode* root){
if (root==nullptr) return;
binode *p=root;
stack<binode*> s;
stack<binode*> t;
while (p!=nullptr || !s.empty()){
while (p!= nullptr){
s.push(p);
t.push(p);
p=p->right;
}
if (!s.empty()){
p=s.top();
s.pop();
p=p->left;
}
}
while (!t.empty()) {
p=t.top();
t.pop();
cout<<p->val;
}
}
4.层序遍历
层序遍历即广度优先搜索，按照每一层的节点从左到右输出，代码非常简单，用于计算二叉树的高度（面试题，今天小米面试被问了，没想起来）。
// 二叉树层序遍历
void layerorder(binode* root){
if(root== nullptr)
return;
binode* p;
queue<binode*> q;
q.push(root);
while (!q.empty()){
p = q.front();
q.pop();
cout<<p->val;
if(p->left!= nullptr){
q.push(p->left);
}
if(p->right!= nullptr){
q.push(p->right);
}
}
}
5.测试用例
// 二叉树测试
int main()
{
/* 假设有二叉树
1
| \
2 3
| \
4 5
| \
6 7
*/
binode* root = new binode(1);
// 构造二叉树，这样写是为了MD可以正常显示
binode nd1(2);
binode nd2(3);
binode nd3(4);
binode nd4(5);
binode nd5(6);
binode nd6(7);
root->setlrnode(&nd1,&nd2);
nd1.setlrnode(&nd3,&nd4);
nd3.setlrnode(&nd5,&nd6);
// 遍历
preorder(root);
cout<<endl;
midorder(root);
cout<<endl;
postorder(root);
cout<<endl;
layerorder(root);
return 0;
}
测试结果如下：
测试结果图
不定期继续更新ing~
网友评论