2021データ構造大学院受験指導

与えられたツリーがツリーソートツリーであるか否かを判断するアルゴリズムを作成してみる.

KeyType predt=-32767;
int JudgeBST(BiTree bt){
     
    int b1,b2;
    if(bt==NULL)
        return 1;
    else{
     
        b1=JudgeBST(bt->lchild);
        if(b1=0||predt>bt->data)
            return 0;
        predt=bt->data;
        b2=JudgeBST(bt->rchild);
        return b2;
    }
}

は、図の隣接テーブル表現から隣接マトリクス表現に変換するアルゴリズムを記述する.

void Convert(ALGraph &G,int arcs[M][N]{
     
    //             G       ares
    for(i=0;i<n;i++){
                 //                
        p=(G->v[i].firstarc;     //    i     
        while(p!=NULL){
     。        //     
            arcs[i][p->data]=1;
            p=p->nextarc;        //       
        }
    }
}

広さ優先探索遍歴アルゴリズム

bool visited[MAX_VERTEX_NUM];		//      
void BFSTraverse(graph G){
     			//  G        
	for(i=0;i<G.vexnum;i++)			
		visited[i]=FALSE;			//         
	InitQueue(Q);					//       Q
	for(i=0;i<G.vexnum;i++)			// 0       
		if(!visited[i])				//           BFS
			BFS(G,i);				//Vi    ， Vi  BFS
}
void BFS(Graph G,int v){
     			//   v  ，       G
	visit(v);						//      v
	visited[v]=TRUE;				// v      
	Enqueue(Q,v);					//  v   Q
	while(!isEmpty(Q)){
     
		Dequeue(Q,v);				//  v   
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v.w))	//  v      
			if(!visited[w]){
     		//w v          
				visit(w);			//    w
				visited[w]=TRUE;	// w       
				EnQueue(Q,w);		//  w   
			}
	}
}

深さ優先ループアルゴリズム(再帰形式)

bool visited[MAX_VERTEX_NUM];		//      
void DFSTraverse(Graph G){
     			//  G        
	for(v=0;v<G.vexnum;++v)
		visited[v]=FALSE;			//          
	for(v=0;v<G.vexnum;++v)			//      v=0    
		if(!visited[v])
			DFS(G,v);
}
void DFS(Graph G,int v){
     			//   v  ，       G
	visit(v);						//    v
	visited[v]=TURE;				//      
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w]){
     			//w u          
			DFS(G,w);
		}
}

直接挿入ソート

このアルゴリズムは理解の面で哨兵付きアルゴリズムより優れている.

void InsertSort(ElemType A[],int n){
     
	int i,j,temp;
	for(i=1;i<n;i++)							//               
		if(A[i]<A[i-1]){
     						// A[i]       
			temp=A[i];							// temp  A[i]
			for(j=i-1;j>=0 && A[j]>temp;--j)	//             
				A[j+1]=A[j];					//    temp        
			A[j+1]=temp;						//       
		}
}

並べ替えられた「哨兵」付きの実現方法を直接挿入する

void InsertSort(ElemType A[],int n){
     
	int i,j;
	for(i=2;i<=n;i++)					//   A[2]~A[n]           
		if(A[i]<A[i-1]){
     				// A[i]        ， A[i]     
			A[0]=A[i];					//     ，A[0]     
			for(j=i-1;A[0]<A[j];--j)	//           
				A[j+1]=A[j];			//    
			A[j+1]=A[0];				//       
		}
}

折半挿入並べ替えアルゴリズム

void InsertSort(ElemType A[],int n){
     
	int i,j,low,high,mid;
	for(i=2;i<=n;i++){
     			//   A[2]~A[n]           
		A[0]=A[i];				// A[i]   A[0]
		low=1;
		high=i-1;			//         
		while(low<=high){
     		//    （      ）
			mid=(low+high)/2;	//    
			if(A[mid]>A[0])
				high=mid-1;		//      
			else
				low=mid+1;		//      
		}
		for(j=i-1;j>=high+1;--j)
			A[j+1]=A[j];		//      ，      
		A[high+1]=A[0];			//    
	}	
}

ヒルソート

void ShellSort(ElemType A[],int n){
     
	int d,i,j;									//A[0]      ，    ， j<=0 ，      
	for(d=n/2; d>=1; d=d/2)						//    
		for(i=d+1; i<=n; ++i)
			if(A[i]<=A[i-d])					//  A[i]        
				A[0]=A[i];						//   A[0]
				for(j=i-d;j>0&&A[0]<A[j];j-=d)
					A[j+d]=A[j];				//    ，       
				A[j+d]=A[0];					//  
}

バブルソートアルゴリズム

void swap(int &a,int &b){
     
	int temp = a;
	a = b;
	b = temp;
}

void BubbleSort(ElemType A[],int n){
     
	for(i=0;i<n-1;i++){
     
		bool flag=false;			//               
		for(int j=n-1;j>i;j--)		//      
			if(A[]j-1]>A[j]){
     		//    
				swap(A[j-1],A[j]);	//  
				flag=ture;
			}
		if(flag==falsh)
			return;					//           ，       
	}
}

クイックソート

試験のポイント、しっかり覚えてください!!!

void QuickSort(ElemType A[],int low,int high){
     
	if(low<hjgh){
     		//       
						//Partition()      ，  A[low···hjgh]              
		int pivotpos=Partition(A,low,high);		//  
		QuickSort(A,low,pivotpos-1);			//             
		QuickSort(A,pivotpos+1,high);
	}
}

int Partition(ElemType A[],int low,int high){
     		//    
	ElemType pivot=A[low];			//              ，      
	while(low<high){
     		//      
		while(low<high&&A[high]>=pivot)
			--high;
		A[low]=A[high];		//             
		while(low<high&&A[low]<=pivot)
			++low;
		A[high]=A[low];		//             
	}
	A[low]=pivot;			//           
	return low;				//           
}

単純選択ソート

//  
void swap(int &a,int &b){
     
	int temp = a;
	a = b;
	b = temp;
}

//      
void SelectSort(ElemType A[],int n){
     
	for(int i=0;i<n-1;i++){
     			//    n-1 
		int min=1;					//        
		for(int j=i+1;j<n;j++)		// A[i···n-1]        
			if(A[j]<A[min])
				min=j;				//        
		if(min!=i)
			swap(A[i],A[min]);
	}
}

スタックソート

「大根ヒープ」に基づくヒープのソート.すなわち,ルートノードの値は左右のサブツリーのいずれかのノードの値よりも大きく,ルートノードの値が最大である.

//     
void BuildMaxHeap(ElemType A[],int len){
     
	for(int i=len/2;i>0;i--)			//             
		HeadAdjust(A,i,len);
}

//  k           
void HeadAdjust(ElemType A[],int k,int len){
     
	A[0]=A[k];							//A[0]        
	for(int i=2*k;i<=len;i*=2){
     			// key          
		if(i<len&&A[i]<A[i+1])			//"i
			i++;						// key         
		if(A[0]>=A[i])
			break;						//    
		else{
     
			A[k]=A[i];					// A[i]        
			k=i;						//  k ，        
		}
	}
	A[k]=A[0];							//             
}

//        
void HeapSort(ElemType A[],int len){
     
	BuildMaxHeap(A,len);				//    
	for(int i=len;i>1;i--){
     				//n-1         
		swap(A[i],A[1]);				//           
		HeadAdjust(A,1,i-1);			//             
	}
}

//swap    
void swap(int &a,int &b){
     
 int temp = a;
 a = b;
 b = temp;
}