实验五排序、邻接表、矩阵.ppt

1、试验五演示文稿,希尔排序,templatevoid Shellsort(DataList while(gap) Shellnsert(List,gap); gap=gap=2?1:(int)(gap/2);,这里也可以没有这个判断语句,一次排序的过程,templatevoid Shellnsert(DataList i temp=List.Vectori; int j=i; while( j=gap,从第gap处开始比较，用后面的与前面的比较,程序运行结果：,图的邻接表深度优先遍历,template Graph:Graph(int sz=DifaultSize):NumVertices(0),

2、MaxNumVertices(sz),NumEdges(0),int n,e,k,j; Nametype name,tail,head; Disttype weight; NodeTable= new VertexMaxNumVertices; coutn; NumVertices=n; coutname;InsertVertex(name); coute; couttailheadweight; k=GetVertexPos(tail); j=GetVertexPos(head); coutnNextn; InsertEdge(k,j,weight);,templatevoid Graph:

3、DFS(),int *visited=new intNumVertices; for(int i=0;iNumVertices;i+) visitedi=0; DFS(0,visited); deletevisited;,初始化visit数组,利用递归过程来深度优先遍历图,结束visit的作用域 释放空间,templatevoid Graph:DFS(int v,int visited),coutGetValue(v) ; visitedv=1; int w=GetFirstNeighbor(v); while(w!=-1) if(!visitedw) DFS(w,visited); w=Ge

4、tNextNeighbor(v,w);,查找下一个邻接顶点,递归查找下一个,返回后进入另一支,templatevoid Graph:InsertVertex(const Nametype for(;iMaxNumVertices,NodeTablei.data是nametype类型的，所以-1也要现实转换为nametype类型,程序运行结果：,图的邻接矩阵的深度优先遍历,template Graph:Graph(int sz),MaxNumVertices=sz; MaxNumEdges=sz*(sz-1)/2; Edge=new Disttypesz*sz; VerticesList=new

5、 OrderList(sz); for(int i=0;icurrentSize=sz;,Edge与VerticesList都为指针类型的,用一维数组表示二维数组,void InsertEdge(int v1,int v2,Disttype weight),if(v1=0,用一维数组表示二维数组下表间的转换关系,程序运行结果：,国名排序,void RadixSort(staticlinklist int *front=new intradix; for(int i=0;i=0;i-) for(int j=0;jradix;j+) frontj=225;,最后一个节点指向第一个节点，形成循环,因

6、为frontj=0要用来表示最后字符为空的国名表，所以初始化frontj为一个用不到的值,void RadixSort(staticlinklist xlist.CurrentSize;x+) if(list.Vectorcurrent.keyi=0) if(front0=225)front0=current; else list.Vectorrear0.link=current; rear0=current; current=list.Vectorcurrent.link; else int k=list.Vectorcurrent.keyi-96; if(frontk=225)frontk

7、=current; else list.Vectorreark.link=current; reark=current; current=list.Vectorcurrent.link; j=0; while(frontj=225) j+;,该位上没有字符，此是对于每个单词后面的个别字符，这样的单词放到front0里,字符a存储表示为97，此表示该位上字符为a的单词存储在front1里,list.head=current=frontj; int last=rearj; for(int k=j+1;kradix;k+) if(frontk!=225) list.Vectorlast.link=frontk; last=reark; list.Vectorlast.link=current;,void RadixSort(staticlinklist for(int e=0;Vectorhead.keye!=0;e+) coutVectorhead.keye; coutendl; for(int i=0;iCurrentSize-1;i+) for(e=0;Vecto