1.链表逆置
void reverse()
{
Node* scan=head->next;
head->next=nullptr;
while(scan)
{
Node* n=scan->next;
scan->next=head->next;
head->next=scan;
scan=n;
}
}
2.链表排序
void SelectSort()
{
for(int i=0;i<length;i++)
{
Node *scan=head->next;
Node *beformaxnode=head;
for(int j=0;j<i;j++)
{
beformaxnode=beformaxnode->next;
scan=scan->next;
}
Node *maxnode=scan;
while(scan->next!=nullptr)
{
// cout<<"item:"<<scan->item<<endl;
if(scan->next->item > maxnode->item)
{
beformaxnode=scan;
maxnode=scan->next;
}
scan=scan->next;
}
beformaxnode->next=maxnode->next;
maxnode->next=head->next;
head->next=maxnode;
}
}
3.二叉树层次遍历分层
进行一个简短的说明，显然，每一层的访问都是在上一层结束之后才会开始。那么如果我们在每一层访问之前，统计一下当前队列的节点数，就是每一层的数量。
void LevelOrderTraverse()
{
if(root==nullptr) return;
queue<Node *> nl;
nl.push(root);
while(!nl.empty())
{
int size=nl.size();
for(int i=0;i<size;i++)//是为了分层
{
Node *n=nl.front();
nl.pop();
cout<<n->val<<' ';
if(n->left) nl.push(n->left);
if(n->right) nl.push(n->right);
}
cout<<endl;
}
cout<<endl;
}
4.判断是否完全二叉树
bool IsCompleted()
{
Node *scan;
queue<Node *> q;
bool n1=false;
q.push(root);
while(!q.empty())
{
scan=q.front();
q.pop();
if(scan->left==nullptr&&scan->right==nullptr)
{
n1=true;//出现叶结点就不能再出现只有左儿子的情况了
}
else if(!scan->left&&scan->right)
{
return false;
}
else if(scan->left&&!scan->right)
{
if(n1)
return false;
else{
n1=true;
q.push(scan->left);
}
}
else//有两个儿子
{
if(n1)
{
return false;
}
q.push(scan->left);
q.push(scan->right);
}
}
return true;
}
5.霍夫曼编码
核心函数是建立和编码
struct Node{
int weight;
int parent;
int lchild;
int rchild;
Node():weight(0),parent(0),lchild(0),rchild(0){};
Node(int x):weight(x),parent(0),lchild(0),rchild(0){};
};
class Haffmantree
{
public:
Haffmantree(){};
void inputData(int num)
{
n=num;
ans=new Node[2*n];
int x;
for(int i=1;i<n+1;i++)
{
cin>>x;
ans[i].weight=x;
}
ans[0].weight=0xfffffff;
}
void select2min(int pos,int&s1,int&s2)
{
s1=0;
s2=0;
for(int i=1;i<pos;i++)
{
if(ans[i].parent!=0)
{
continue;
}
if(ans[i].weight<ans[s1].weight)
{
s2=s1;
s1=i;
}
if(ans[i].weight>ans[s1].weight&&ans[i].weight<ans[s2].weight)
{
s2=i;
}
}
}
void Create()
{
int s1,s2;
for(int i=n+1;i<2*n;i++)
{
select2min(i,s1,s2);//从前i个选
ans[i].weight=ans[s1].weight+ans[s2].weight;
ans[i].lchild=s1;
ans[i].rchild=s2;
ans[s1].parent=i;
ans[s2].parent=i;
}
}
void OutPut()
{
for(int i=1;i<2*n;i++)
{
cout<<ans[i].weight<<" "<<ans[i].parent<<" "<<ans[i].lchild<<" "<<ans[i].rchild<<endl;
}
}
int GetWpl()
{
return ans[2*n-1].weight;
}
void encode()
{
bool a[2*n-1];
int length=0;
encodeHelp(2*n-1,a,length);//从最后一个开始
}
void encodeHelp(int n,bool *a,int length)//去编码第n号
{
if(ans[n].lchild==0&&ans[n].rchild==0)
{
cout<<ans[n].weight<<"编码是：";
for(int i=0;i<length;i++)
{
cout<<a[i];
}
cout<<endl;
return;
}
if (ans[n].lchild != 0)
{
a[length] = 0;
encodeHelp(ans[n].lchild, a, length + 1);
}
if (ans[n].rchild != 0)
{
a[length] = 1;
encodeHelp(ans[n].rchild, a, length + 1);
}
}
~Haffmantree()
{
delete[] ans;
}
private:
int n;
Node *ans;
};
6.快速排序
书上快排写得不便于背诵，给一个好背一点的。
void quickSort(vector<int> &a,int left,int right)
{
if(left>right) return;
int pivot = a[left];
int i=left,j=right;
for(;;)
{
while(a[i]<pivot) i++;
while(a[j]>=pivot) j--;
if(i<j) std::swap(a[i],a[j]);
else break;
}
a[i]=pivot;
quickSort(a,left,i-1);
quickSort(a,i+1,right);
}
void quickSort(vector<int> &a)
{
quickSort(a,0,a.size()-1);
}
7.堆排序
//约定len为不可访问的第一个下标
void HeapModify(vector<int> &a,int i,int len)
{
int p=i;
int son = p*2+1;
int tmp = a[i];
while(son<len)
{
if(son+1<len&&a[son]<a[son+1])
son++;
if(a[son]<tmp)
{
break;
}
else{
a[p]=a[son];
p=son;
son=p*2+1;
}
}
a[p]=tmp;
}
void HeapSort(vector<int> &a)
{
for(int i = (a.size())/2;i>=0;i--)
{
HeapModify(a,i,a.size());
}
for(int i=a.size()-1;i>=0;i--)
{
swap(a[0],a[i]);
HeapModify(a,0,i);
}
}