實(shí)驗(yàn)五排序鄰接表矩陣

實(shí)驗(yàn)五排序鄰接表矩陣第一頁(yè)，共二十二頁(yè)，編輯于2023年，星期二希爾排序dataList.hMain.cpp第二頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classtype>voidShellsort(DataList<type>&List)intgap=List.CurrentSize/2;while(gap){Shellnsert(List,gap);gap=gap==2?1:(int)(gap/2);開(kāi)始gap=List.CurrentSize/2Shellnsert(List,gap)Gap!=0Gap=1Gap=2結(jié)束Gap=gap/2NYYN這里也可以沒(méi)有這個(gè)判斷語(yǔ)句一次排序的過(guò)程第三頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classtype>voidShellnsert(DataList<type>&List,constintgap)for(inti=gap;i<List.CurrentSize;i++){Element<type>temp=List.Vector[i];intj=i;while(j>=gap&&temp.Getkey()<List.Vector[j-gap].Getkey()){List.Vector[j]=List.Vector[j-gap];j-=gap;}List.Vector[j]=temp;從第gap處開(kāi)始比較，用后面的與前面的比較開(kāi)始i=gapi++i<List.CurrentSizetemp=List.Vector[i]intj=ij>=gap&&temp.Getkey()<List.Vector[j-gap].Getkey()List.Vector[j]=List.Vector[j-gap]j-=gapList.Vector[j]=temp結(jié)束YN第四頁(yè)，共二十二頁(yè)，編輯于2023年，星期二程序運(yùn)行結(jié)果：第五頁(yè)，共二十二頁(yè)，編輯于2023年，星期二圖的鄰接表深度優(yōu)先遍歷GraphB.hMain.cppGraphBDef.h第六頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classNametype,classDisttype>Graph<Nametype,Disttype>::Graph(intsz=DifaultSize):NumVertices(0),MaxNumVertices(sz),NumEdges(0)intn,e,k,j;Nametypename,tail,head;Disttypeweight;NodeTable=newVertex<Nametype,Disttype>[MaxNumVertices];cout<<"Pleaseinputthenumberofthevertices:";cin>>n;NumVertices=n;cout<<"PleaseinputthenamesoftheVertexonebyone:";for(inti=0;i<n;i++){cin>>name;InsertVertex(name);}cout<<"pleaseinputthenumberoftheedges:";cin>>e;cout<<"pleaseinputtheirtail,headweightonebyone:\n";for(i=0;i<e;i++){cin>>tail>>head>>weight;k=GetVertexPos(tail);j=GetVertexPos(head);cout<<"\nNext\n";InsertEdge(k,j,weight);}開(kāi)始NodeTable=newVertex<Nametype,Disttype>[MaxNumVerticesINPUTNumVerticesINPUTnamesoftheverticesINPUTNumEdgesINPUTdataoftheEdges結(jié)束第七頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classNametype,classDisttype>voidGraph<Nametype,Disttype>::DFS()int*visited=newint[NumVertices];for(inti=0;i<NumVertices;i++)visited[i]=0;DFS(0,visited);delete[]visited;開(kāi)始*visited=newint[NumVertices];i=0i++i<NumVerticesvisited[i]=0DFS(0,visited)delete[]visitedYN結(jié)束初始化visit數(shù)組利用遞歸過(guò)程來(lái)深度優(yōu)先遍歷圖結(jié)束visit的作用域釋放空間第八頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classNametype,classDisttype>voidGraph<Nametype,Disttype>::DFS(intv,intvisited[])cout<<GetValue(v)<<'';visited[v]=1;intw=GetFirstNeighbor(v);while(w!=-1){if(!visited[w])DFS(w,visited);w=GetNextNeighbor(v,w);}開(kāi)始OUTPUTvaluevisited[v]=1w=GetFirstNeighbor(v)w!=-1!visited[w]DFS(w,visited)w=GetNextNeighbor(v,w)結(jié)束YNNY查找下一個(gè)鄰接頂點(diǎn)遞歸查找下一個(gè)返回后進(jìn)入另一支第九頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classNametype,classDisttype>voidGraph<Nametype,Disttype>::InsertVertex(constNametype&vertex)inti=0;for(;i<MaxNumVertices&&NodeTable[i].data!=Nametype(-1);i++);if(i==MaxNumVertices){cout<<"Outofmemory!";return;}elseNodeTable[i].data=vertex;開(kāi)始；i++i<MaxNumVertices&&NodeTable[i].data!=Nametype(-1)i==MaxNumVerticesOUTPUTERRORNodeTable[i].data=vertex結(jié)束YNYNNodeTable[i].data是nametype類型的，所以-1也要現(xiàn)實(shí)轉(zhuǎn)換為nametype類型第十頁(yè)，共二十二頁(yè)，編輯于2023年，星期二程序運(yùn)行結(jié)果：第十一頁(yè)，共二十二頁(yè)，編輯于2023年，星期二圖的鄰接矩陣的深度優(yōu)先遍歷Graph.hMain.cppGraphDef.hOrderList.hOrderListDef.h第十二頁(yè)，共二十二頁(yè)，編輯于2023年，星期二template<classNametype,classDisttype>Graph<Nametype,Disttype>::Graph(intsz)MaxNumVertices=sz;MaxNumEdges=sz*(sz-1)/2;Edge=newDisttype[sz*sz];VerticesList=newOrderList<Nametype>(sz);for(inti=0;i<sz*sz;i++)Edge[i]=0;CurrentEdges=0;VerticesList->currentSize=sz;開(kāi)始MaxNumVertices=szMaxNumEdges=sz*(sz-1)/2Edge=newDisttype[sz*sz]VerticesList=newOrderList<Nametype>(sz);i=0i++i<sz*szEdge[i]=0CurrentEdges=0VerticesList->currentSize=sz結(jié)束YNEdge與VerticesList都為指針類型的用一維數(shù)組表示二維數(shù)組第十三頁(yè)，共二十二頁(yè)，編輯于2023年，星期二voidInsertEdge(intv1,intv2,Disttypeweight)if(v1>=0&&v1<MaxNumVertices&&v2>=0&&v2<MaxNumVertices)Edge[v1*MaxNumVertices+v2]=weight;elsecout<<"Error!\n";開(kāi)始v1>=0&&v1<MaxNumVertices&&v2>=0&&v2<MaxNumVerticesEdge[v1*MaxNumVertices+v2]=weightOUTPUTERROR結(jié)束YN用一維數(shù)組表示二維數(shù)組下表間的轉(zhuǎn)換關(guān)系第十四頁(yè)，共二十二頁(yè)，編輯于2023年，星期二程序運(yùn)行結(jié)果：第十五頁(yè)，共二十二頁(yè)，編輯于2023年，星期二國(guó)名排序Sort.hMain.cpp第十六頁(yè)，共二十二頁(yè)，編輯于2023年，星期二voidRadixSort(staticlinklist&list,intd,intradix)int*rear=newint[radix];int*front=newint[radix];for(inti=0;i<list.CurrentSize-1;i++)list.Vector[i].link=i+1;list.Vector[list.CurrentSize-1].link=0;intcurrent=0;for(i=d-1;i>=0;i--){for(intj=0;j<radix;j++) front[j]=225;開(kāi)始*rear=newint[radix]*front=newint[radix]i=0i++i<list.CurrentSize-1list.Vector[i].link=i+1list.Vector[list.CurrentSize-1].link=0current=0i=d-1i--i>=0j=0j++j<radixfront[j]=225結(jié)束abYNYNNY最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，形成循環(huán)因?yàn)閒ront[j]=0要用來(lái)表示最后字符為空的國(guó)名表，所以初始化front[j]為一個(gè)用不到的值第十七頁(yè)，共二十二頁(yè)，編輯于2023年，星期二voidRadixSort(staticlinklist&list,intd,intradix)for(intx=0;x<list.CurrentSize;x++){if(list.Vector[current].key[i]=='0'){if(front[0]==225)front[0]=current;elselist.Vector[rear[0]].link=current;rear[0]=current;current=list.Vector[current].link;}else{intk=list.Vector[current].key[i]-96;if(front[k]==225) front[k]=current;elselist.Vector[rear[k]].link=current;rear[k]=current;current=list.Vector[current].link;}}j=0;while(front[j]==225)j++;cbx=0x++x<list.CurrentSizelist.Vector[current].key[i]=='0'front[0]==225front[0]=currentlist.Vector[rear[0]].link=currentrear[0]=currentcurrent=list.Vector[current].linkk=list.Vector[current].key[i]-96front[k]==225front[k]=currentlist.Vector[rear[k]].link=currentrear[k]=currentj=0front[j]==225j++YNNYYNNY該位上沒(méi)有字符，此是對(duì)于每個(gè)單詞后面的個(gè)別字符，這樣的單詞放到front[0]里字符a存儲(chǔ)表示為97，此表示該位上字符為a的單詞存儲(chǔ)在front[1]里第十八頁(yè)，共二十二頁(yè)，編輯于2023年，星期二list.head=current=front[j];intlast=rear[j];for(intk=j+1;k<radix;k++)if(front[k]!=225){list.Vector[last].link=front[k];last=rear[k];}list.Vector[last].link=current;}voidRadixSort(staticlinklist&list,intd,intradix)calist.head=current=front[j]last=rear[j]

k=j+1k++k<radixlist.Vector[last].link=front[k]last=rear[k]list.Vector[last].link=currentYNfront[k]!=225YN判