由于找工作要惡補(bǔ)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)褪子，為了手撕代碼方便量淌，寫了很多代碼并測(cè)試。都是些找工作诚油剩考的呀枢，現(xiàn)在貼上來(lái)，不定期更新部分代碼笼痛。
- 含有鏈表反轉(zhuǎn)裙秋，排序算法，查找算法和二叉樹的遍歷算法。
- 都是巢蟹裕考的手撕代碼财忽，建議找工作的童鞋使勁背。
- 里面每一段代碼都是經(jīng)過(guò)調(diào)試的泣侮。
- IDE建議使用CLion即彪，個(gè)人感覺(jué)比較好用，沒(méi)有VS那么大活尊，不想破解就下社區(qū)版隶校，配置教程可以參考我另一篇文章Window10極簡(jiǎn)CLion配置教程。
鏈表反轉(zhuǎn)
1. 結(jié)點(diǎn)定義
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.快速排序法
// 快排蛹锰，數(shù)組版
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;
}
二叉樹遍歷（非遞歸版）
由于遞歸版過(guò)于簡(jiǎn)單深胳，一般來(lái)說(shuō)面試是不會(huì)考的，所以只放非遞歸版铜犬。
- 節(jié)點(diǎn)定義
// 二叉樹節(jié)點(diǎn)
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.后序遍歷
后續(xù)遍歷很容易出問(wèn)題，之前的寫的會(huì)內(nèi)存泄露癣猾，現(xiàn)在修改了敛劝。
// 后序遍歷
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.層序遍歷
層序遍歷即廣度優(yōu)先搜索，按照每一層的節(jié)點(diǎn)從左到右輸出纷宇，代碼非常簡(jiǎn)單夸盟，用于計(jì)算二叉樹的高度（面試題，今天小米面試被問(wèn)了像捶，沒(méi)想起來(lái)）上陕。
// 二叉樹層序遍歷
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.測(cè)試用例
// 二叉樹測(cè)試
int main()
{
/* 假設(shè)有二叉樹
1
| \
2 3
| \
4 5
| \
6 7
*/
binode* root = new binode(1);
// 構(gòu)造二叉樹，這樣寫是為了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;
}
測(cè)試結(jié)果如下：
測(cè)試結(jié)果圖
不定期繼續(xù)更新ing~
