webdancer's Blog
拓扑排序2
前一篇，学习了根据DFS，来进行拓扑排序的方法；今天看一下，按照贪婪算法来进行拓扑排序。主要的思想：找没有入度的顶点，放到队列里面；然后，逐渐从队列里删除顶点，加入一个数组，如果产生了新的没有入度的顶点，也加入队列，重复直到队列为空。
#include<stdio.h>
#include<stdlib.h>
#include"graph.c"
#include"queue.c"
#define MAX 100
int indeg[MAX];
int vl[MAX];
int *q;
void topolsort(Graph g){
int i,nv;
nv=g->nv;
for(i=0;i<nv;i++){
struct node * vnode;
vnode=g->adj[i];
while(vnode){
int u;
u=vnode->v;
indeg[u]++;
vnode=vnode->next;
}
}
q=initq(nv);
for(i=0;i<nv;i++)
if(indeg[i]==0)
add(q,i);
int iv;
iv=0;
while(!isempty()){
int u;
u=delete(q);
vl[iv++]=u;
struct node * unode;
unode=g->adj[u];
while(unode){
int v;
v=unode->v;
if(!(--indeg[v]))
add(q,v);
unode=unode->next;
}
}
}
int main(){
Graph g;
int n=6;
g=init(n);
edge e[8];
e[0].u=0;e[0].v=2;
e[1].u=0;e[1].v=3;
e[2].u=1;e[2].v=3;
e[3].u=1;e[3].v=4;
e[4].u=2;e[4].v=3;
e[5].u=2;e[5].v=5;
e[6].u=3;e[6].v=5;
e[7].u=4;e[6].v=5;
int i;
for(i=0;i<g->ne;i++)
insert(g,e[i]);
topolsort(g);
for(i=0;i<g->nv;i++)
printf("%d ",vl[i]);
printf("\n");
return 0;
}
时间复杂度分析：有向图的表示采用了邻接链表，所以时间复杂度为：Θ(V+E)。
拓扑排序
对一个DAG进行拓扑排序，结果为一个所有顶点构成的线性序列。序列满足：
对于<u,v>∈E(G),在序列中U出现在V的前面。
在算法导论中，给出的算法是：对DAG进行DFS遍历，计算每个顶点结束的时间，然后每完成一个顶点，将其加入到链表的头部。结果就是链表中的序列。
因此，对前面的DFS实现，稍加修改就可以了。此外，注意需要对原来的无向图实现修改。
代码：
#include<stdio.h>
#include"search.c"
extern int f[MAXV];
int * vq;
void reverse(int * a,int n){
int i,j;
for(i=1,j=n-1;i<j;i++,j--){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
void dfsv1(Graph g,int u){
color[u]=GRAY;
time++;
d[u]=time;
struct node * vnode;
vnode=g->adj[u];
while(vnode){
int vv;
vv=vnode->v;
if(color[vv]==WHITE){
p[vv]=u;
dfsv1(g,vv);
}
vnode=vnode->next;
}
color[u]=BLACK;
time++;
f[u]=time;
add(vq,u);
//printf("%d ",u);
}
void topolsort(Graph g){
int i,v;
v=g->nv;
for(i=0;i<v;i++){
color[i]=WHITE;
p[i]=-1;
}
vq=initq(NUM);
time=0;
for(i=0;i<v;i++)
if(color[i]==WHITE){
dfsv1(g,i);
}
reverse(vq,v+1);
}
int main(){
Graph g;
int n=5;
g=init(n);
edge e[7];
e[0].u=0;e[0].v=1;
e[1].u=0;e[1].v=3;
e[2].u=1;e[2].v=2;
e[3].u=1;e[3].v=3;
e[4].u=1;e[4].v=4;
e[5].u=4;e[5].v=2;
e[6].u=3;e[6].v=4;
int i;
for(i=0;i<7;i++)
insert(g,e[i]);
topolsort(g);
for(i=1;i<=g->nv;i++)
printf("%d ",vq[i]);
printf("\n");
return 0;
}
找出数组中重复次数最多的元素并打印
题目：找
这道题其实在做汇编实验时，已经做过了。但是当时的思路还是太简单，现在又想了一下，可以先排序，然后遍历。这样如果采用快排，时间复杂度应为：O(nlogn+n)。代码:
总结：1.排序的应用，排序可以用来对相同的元素分类，使他们相邻，从而解决问题。
2.语言问题：在代码中注释掉的：//printf("%d\n",(sizeof a )/(sizeof a[0])); Error。没有注意到：在函数中，a是个指针，而不是数组，分了错误，所以：在32位的机器上：(sizeof a )/(sizeof a[0])=1。
#include<stdio.h>
#include<stdlib.h>
int int_compare(const void * x1,const void * x2){
int * a=(int *)x1;
int * b=(int *)x2;
return (*a-*b);
}
void findremax(int a[],int n,int *m,int *c){
int index,count,maxc,i;
index=0;
count=1;
maxc=count;
//printf("%d\n",(sizeof a )/(sizeof a[0])); Error
for(i=1;i<n;i++){
if(a[i]==a[i-1])
count++;
else{
if(count>maxc){
maxc=count;
index=i-1;
}
count=1;
}
}
if(count>maxc){
maxc=count;
index=i-1;
}
*m=index;
*c=maxc;
}
int main(){
int maxindex,c;
int a[]={1,1,2,2,3,3,3,3,4,5,6,7,7,7,7,7,7};
int n=(sizeof a)/(sizeof a[0]);
maxindex=0;
c=0;
qsort(a,n,sizeof(a[0]),int_compare);
findremax(a,n,&maxindex,&c);
printf("%d appears %d times.\n",a[maxindex],c);
return 0;
}
shell排序算法
shell排序算法是一种插入排序算法，直接的插入算法很简单，shell算法不同于直接插入的插入时小步挪动，而做长距离的跳动。它由Donald Shell于1959年提出。
shell算法也叫作“减少增量的排序算法”，每一遍通过增量h,使得那些相距h的记录排序。增量的序列不是固定的，确定最好的增量序列需要大量的数学知识。
shell算法：
<1>确定增量序列S[ t]。
<2>对给出的记录，按照增量序列S，进行t遍排序。
<3>对每遍进行直接插入。
/*为了编程方便，增量序列采用：
[n/2,n/4,......,1].实际的增量序列很是有趣。
*/
void shsort(int a[],int n){
int i,j;
for(i=n/2;i>=1;i/=2){
for(j=i;j<n;j++){
int k;
for(k=j-i;k>=0&&a[k]>a[k+i];k-=i){
int t=a[k];
a[k]=a[k+i];
a[k+i]=t;
}
}
}
}
我觉得还是挺有趣的，注意算法在利用直接插入时的方法，后面的元素不断的插入。