数据结构代码题--排序算法（快排），二叉树的基本知识，链表的基本操作引申

排序算法：

完成比完美更重要！

题目中常考的是平均时间复杂度：但是具体计算时，能用最坏就用最坏

插入：直接插，希尔

交换：冒泡，快排

选择：简单选择，堆排

归并，二路归并，基数

为了高分，一般选择希尔，堆排，快排，但是堆排的代码不好写，希尔的复杂度不好分析，一般代码提只考虑快排

什么时候用快排：
- 顺序表，数组
- 乱序数组，并且排序号有利于解决问题

//快速排序基本代码
int partition(int A[],int L,int R){int mid = A[L];while(L<R){while(A[R]>=mid) R--;//右指针从右往左移A[L] = A[R];//当<mid时，退出循环，和R交换位置while(A[L]<=mid) L++;A[R] = A[L];}A[L] = mid;return L;
}
void quick_sort(int A[],int L,int R)
{if(L >= R) return;int M = partition(A,L,R);quick_sort(A,L,M-1);quick_sort(A,M+1,R);
}

/*（1）折半查找（最优），顺序查找，归并排序，快速排序
本题采用快排：（1）两个数组合并成一个大数组
（2）对大数组进行排序（Qsort）
（3）找到中间元素
*/int partition(int A[],int L,int R){int pivot = A[L];while(L<R){while(A[R]>=mid) R--;A[L] = A[R];while(A[L]<=mid) L--;A[R] = A[L];}mid = A[L];		
}void Qsort_Judge(int A[],int L,int R){int M = partition(A,L,R);if(M==Qsort_Judge
}

（1），先将数组排序好
（2），找中间的元素，遍历数组，count中间元素的值
（3），如果count>2/nQsort(A,0,n-1);
int x = A[n/2];
for((int i = n/2-1,i>=0;i--){if(A[i] == x){count++;}}比较好的方法：投票算法：定义一个候选值candidata,一个count如果count == 0把第一个元素设置为candidat,遍历，如果下一个元素==candidate count++如果下一个元素 ！=candidate count--for (int num : nums) {if (count == 0) {candidate = num;count = 1;} else if (num == candidate) {count++;} else {count--;}}

往快排上面想一下：（1）乱序，所以先利用快排排序（2）遍历找到第一个大于0的数（3）如果那个数>=2,那么结果就是1（4）如果那个数=1.让它往后遍历，同时定义一个m++,直到两者不相等(4ii) 或者，遍历，比较差值插值>2,就返回k 为第一个大于0的数组位置for(int m = k+1;m<n;m++){if(A[m] - A[m-1] >1)return A[m}

划分函数的意义：

划分函数返回pivot在数组中的位置
利用划分函数可以找到数组中第k小或者第k大的元素（如果划分结果是k)
找到数组中更小的或者更大的k个元素（如果划分结果是k)
把数组用划分为左右两个部分
先利用一次划分返回值m
如果k<m,对(0,m-1)的元素再次划分

利用划分函数找到数组中第k小的元素
int func(int A[],int n,int k){while(1){int M = partition(A,L,R);if(M==k-1) break;else if(M>k-1) R = M-1;eles if(M<k-1) L = M+1;}
return A[k-1];
}

利用划分函数找到数组中第k小的元素
int func(int A[],int n,int k){while(1){int M = partition(A,L,R);if(M==k) break;else if(M>k) R = M-1;eles if(M<k) L = M+1;}
return A[k-1];
}

利用划分的思想，找到第n/2的位置

二路归并函数思想运用（空间复杂度（O(n))

什么时候用归并
- 合并数组(有序的）
- 合并好之后是有序的
归并函数基本功

int Merge(int A[],int N,int B[],int M,int C[]){while(i<M&&j<N){if(A[i]<B[j]{C[k++] = A[i++];}if(B[j]<A[i]{C[k++] = B[j++];}//复制操作while(i<M){C[k++] = A[i++];}while(j<N){C[k++] = B[j++];}return 1;
}

(1)归并排序(O(logn))
(2)找（N+M)/2

链表算法题:灵活度低，回归基础

//定义单链表结点
typedef struct LNode{int data;struct LNode *next;
} LNode,*LinkList;//求单链表的长度
int get_length(Linklist L){int length = 0;LNode * p = L->next;while(p!=NULL){length++;p = p->next;}cout<<"链表长度为"<<length<<endl;return length;
}//返回单链表的中间结点
LNode getMidNode(LinkList L){int length = 0;LNode * p = L->next;while(p!=NULL){length++;p = p->next;}int n = p/2;return getnNode(L,n);
}// 返回单链表第n个结点
LNode getnNode(LinkList L,int n){LNode *p = L->next;int count = 0;while(p!=NULL){count++;if(count==n)break;p = p->next;}return p;
}
// 倒数第k个结点：快慢指针，快指针先走k步，之后快指针和慢指针
再一起走//

1，分别计算str1,str2的长度m,n,以及他们的差值k
2，p指针从str1,开始向后走k步
3，q指针从str2开始，与p指针现在的位置共同走，边走边判断两者是
否相等LNode getLastSameLetter(LinkList L1,LinkList L2){int m = get_length(L1);int n = get_length(L2);int k = m-n;int count = 0;if(k>=0){LNode *p = getnNode(L1,k);q = L2;}else{LNode *q = getnNode(L2,k);q = L1->next;}while(p!=NULL&&q!=NULL){if(p = q)break;p = p->next;q = q->next;}return p;
}

按关键字条件查找删除（前后指针）

删除操作，用双指针，删除p

void deleteX(LinkList L,int x){LNode pre = L->next;LNode p = pre->next;while(p!=NULL){if(p->data == x){LNode *q = p;p = p->next;q ->next = p;free(q);}else{pre = p;p = p->next;}}
}

插入操作，用双指针，插入x

在关键字递增有序的单链表中插入新的关键字，确保插入后单链表
递增有序
void insert（LinkList L,int x){LNode pre = L->next;Lnode p = pre -> next;LNode temp = new LNode(x,NULL);temp ->data =  x;while(p!=NULL){if(p->data >x){pre->next = temp;temp ->next = p;}else{pre = pre->next;p = p ->next;}if(p == NULL){pre ->next = temp;}}
}

1,需要找到绝对值相等的结点
2，需要双指针进行删除
3，如果题目中说时间复杂度尽可能高的算法，那么可以考虑空间换时
间，也就是，用一个数组进行记录，出现了多少次void removeDuplicateNode(LinkList L,int a){int count[n+1];for(int i = 0;i<=n;i++){count[i] = 0;}LNode pre = L;LNode p = pre->next;while(p!=NULL){if(count[abs(p->data)]==0)count[abs(p->data)] = 1;else if(count[abs(p->data)]==1){LNode temp = p;p = p->next;pre->next = p;free(p);}pre = pre->next;p = pre->next;}
}

头插法：实现链表的原地逆置

尾插法：保持原顺序

尾插法

设置两个链表，与一个计数器

计数器为奇数采用尾插法进A

计数器为偶数采用头插法进B

设置两个链表头，与一个计数器

计数器<n/2的，把数据拆下来，采用尾插法进A

计数器>n/2的，把数据拆下来，采用头插法进B

在原始L，依次拆下来A,B，进入L

二叉树的算法题：

typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;	int treeHeight = 0;
int max(int a,int b){return ( a > b) ? a:b;
}//前序遍历
void PreOrder(BiTree root,int depth){//n是第几层if(root == NULL) return;visit(root);treeHeight = max(treeHeight,depth);PreOrder(root->lchild,depth+1);PrePrder(root->rchild,depth+1);
}//中序遍历
void InOrder(BiTree root){if(root == NULL) return;InOrder(root->lchild);visit(root);Inorder(root->rchild);
}//后序遍历
int  PostOrder(BiTree root){if(root == NULL) return;int l = PostOrder(root->lchild);int r = PostPrder(root->rchild);cout<<"该树的平衡因子为"<<l-r<<endl;visit(root);
}//层序遍历，由于要实现Q,大题代码一般不考，如果考了，直接用队列
void InitQueue(Queue &Q);
void EnQueue(Queue &Q,BiTNode *x);
void DeQueue(Queue &Q,BitNode *x);
bool IsEmpty(Queue &Q);
void levelOrder(BiTree T){Queue Q:InitQueue(Q);Bitree p;Enqueue(Q.T);while(!IsEmpty(Q)){Dequeue(Q,p);//让队头元素出列visit(p);//出队访问if(p->left !=NULL)EnQueue(Q,p->lchild);//if(p->right !=NULL)EnQueue(Q,p->right);}}
}//求树的高度1(通过参数传递向下传递）
int TreeHeight = 0;
PreOrder(BiTree root ,int height){if(root ==NULL) return;visit(root);if(height >TreeHeight)TreeHeight = height;PreOrder(root->left,height+1);PreOrder(root->right,height+1);
}
PreeOrder(root,1)//求树的高度2（通过返回值）
PostOrder(BiTree root){if(root ==NULL) return;int l = PostOrder(root->left,height+1);int r = PostOrder(root->right,height+1);TreeHeight = ( l > r ) ? l : r;visit(root);
}//求树的宽度：结点最多的那一层有多少结点
//最初想到的是层序，但是尽量用先中后
//利用先中后的参数或者返回值
//利用先序遍历作为代码的框架
int width[MAX];
void PreOrder(BiTree root,int level){//n是第几层if(root == NULL) return;width[level]++;PreOrder(root->lchild,depth+1);PrePrder(root->rchild,depth+1);
}
void treeWidth(BiTree T){for(int i = 0;i<MAX;i++)width[i] = 0;PreOrder(root,0);int maxWidth = 0;for(int i = 0;i<MAX;i++){if(width[i]>maxWidth)maxWidth = width[i];}cout<<"树的宽度是:"<<maxWidth;g
}//求WPL（带权路径长）
1，找到叶子结点，没有子节点
2，向下传参
int WPL;
void PreOrder（BiTree T,int n){if(T==NULL) return;if(T->left==NULL&&T->right==NULL){WPL+=T->weight*n}PreOrder(root->lchild,depth+1);PrePrder(root->rchild,depth+1);
}
PreOrder(root,0);//判断二叉排序树
中序遍历，判断递增
int temp = MIN_INT;//已经访问过的最大值
bool isBST = True;
void InOrder(BiTree root){if(root == NULL) return;InOrder(root->lchild);if(T->data >=temp) temp = T=>data;else isBST = False;Inorder(root->rchild);
}//二叉树是否平衡
后续遍历返回树高
bool isBalance = true;
int  PostOrder(BiTree root){if(root == NULL) return;int l = PostOrder(root->lchild);int r = PostPrder(root->rchild);if(left-right>1) isBalance = False;if(left->righ<-1) isBalance = False;if(left >right) return left+1;else return right+1;visit(root);
}
//完全二叉树  
第一个不满的孩子是否是：有右但没左孩子
使用层序遍历
void InitQueue(Queue &Q);
void EnQueue(Queue &Q,BiTNode *x);
void DeQueue(Queue &Q,BitNode *x);
bool IsEmpty(Queue &Q);
void levelOrder(BiTree T){Queue Q:InitQueue(Q);Bitree p;Enqueue(Q.T);while(!IsEmpty(Q)){Dequeue(Q,p);//让队头元素出列visit(p);//出队访问if(p->left !=NULL)EnQueue(Q,p->lchild);//if(p->right !=NULL)EnQueue(Q,p->right);}}
}
bool isComplete = true;//判断是否为完全二叉树
bool flag = false;//flag = true表示层序遍历时出现
//过叶子或者只有左孩子的分枝结点
void visit（BiTNode *p){if(p->lchild==NULL&&p->rchild==NULL) flag = true;
//第一次访问到孩子缺失的结点
//如果是无左有右，可以判断一定不完全，
//如果是有左无右，此时还没没有办法判断，因为后续可能出现有问题的
//如果是无左无右，此时也没有办法判断，因为后续可能出现有问题的
//因此做个标记，表明后面不可以出现这两种情况，如果出现，那就是错的if(p->lchild == NULL &&p->rchild!=NULL) isComplete = flase;if(p->lchild!=NULL &&p->right==NULL{if(flag) isComplete = false;flag = true;}//前一步是为了判断这个结点是不是第二次出现//flag = true是判断，这个结点，是不是第一次出现，如果是第一次出现，也即是flag是falsa，//那就应当当做第一次出现来判断if(p->lchild!=NULL &&p->right!=NULL{if(flag) isComplete = false;
}
}