数据结构实验八

发布于 2024-11-29  270 次阅读

8-1

#include <iostream>
using namespace std;

#define MAXSIZE 20		//¼Ç¼×î´ó¸öÊý
typedef struct{
	int r[MAXSIZE+1];		 //data[0]¿ÉÏÐÖûò×÷¼àÊÓÉÚ
	int length;				//˳Ðò±í³¤¶È
}SqList; 

//´´½¨Ë³Ðò±í
void CreateSqList(SqList &L, int n){
	int i;
	L.length = n;
	for(i=1; i<=L.length; i++){
		cin>>L.r[i];
	}
}

//Êä³ö˳Ðò±í
void PrintSqList(SqList &L){
	int i;
	for(i=1; i<=L.length; i++)
		cout<<L.r[i]<<endl;
}

//Ö±½Ó²åÈëÅÅÐò,Acc=1±íʾÉýÐò,Acc=-1±íʾ½µÐò
void InsertSort(SqList &L,int Acc){
	//--------²¹³ä´úÂë--Start------
	int i, j;
	for (i = 2; i <= L.length; i ++) {
		L.r[0] = L.r[i];
		j = i - 1;
		while (j > 0 && (Acc == 1 && L.r[j] > L.r[j + 1]) || (Acc == -1 && L.r[j] < L.r[j + 1])) {
			L.r[j + 1] = L.r[j];
			j --;
		}
		L.r[++ j] = L.r[0];
	}
	//--------²¹³ä´úÂë--End------	
}

//ÕÛ°ë²åÈëÅÅÐò
void BInsertSort(SqList &L){
	//--------²¹³ä´úÂë--Start------
	int i, j, low, high, mid;
	for (i = 2; i <= L.length; i ++) {
		low = 1;
		high = i - 1;
		L.r[0] = L.r[i];
		while (low < high) {
			mid = (low + high) / 2;
			if (L.r[0] < L.r[mid]) {
				high = mid - 1;
			}
			else if (L.r[mid] < L.r[0]) {
				low = mid + 1;
			}
			else {
				break;
			}
		}
	}
	for (j = i - 1; j > high; j --) {
		L.r[j + 1] = L.r[j];
	}
	L.r[high + 1] = L.r[0];
	//--------²¹³ä´úÂë--End------
}
//Ö÷º¯Êý
int main(){
	int n,Acc;
	SqList List,TempList;
	int select;

	while(cin>>select){
		if(select==0)
			return 0;
		else if(select==1){
			cin>>n;
			CreateSqList(List, n);
		}
		if(select==2){
			TempList=List;
			cin>>Acc;
			InsertSort(TempList,Acc);
			PrintSqList(TempList);
		}
		else if(select==3){
			TempList=List;
			BInsertSort(TempList);
			PrintSqList(TempList);
		}
	}
	return 0;
}

8-2

#include <iostream>
using namespace std;

#define MAXSIZE 20			//¼Ç¼×î´ó¸öÊý
//ѧÉú½á¹¹Ìå
typedef struct{
	char name[10];
	int age;
	int no;
}Student;
typedef struct{
	Student r[MAXSIZE+1]; //data[0]¿ÉÏÐÖûò×÷¼àÊÓÉÚ
	int length;					     //˳Ðò±í³¤¶È
}SqList; 

//´´½¨Ë³Ðò±í
void CreateSqList(SqList &L, int n){
	int i;
	L.length = n;
	for(i=1; i<=L.length; i++){
		cin>>L.r[i].no>>L.r[i].age>>L.r[i].name;
	}
}

//Êä³ö˳Ðò±í
void PrintSqList(SqList &L){
	int i;
	for(i=1; i<=L.length; i++)
		cout<<L.r[i].no<<" "<<L.r[i].age<<" "<<L.r[i].name<<endl;
}

//°´ÕÕѧºÅÆðÅÝÅÅÐò£¬Acc=1±íʾÉýÐò,Acc=-1±íʾ½µÐò
void BubbleSort(SqList &L, int Acc){
	//--------²¹³ä´úÂë--Start------
	int i, j, len;
	Student tmp;
	len = L.length;
	for (i = 1; i < len; i ++) {
		for (j = 1; j <= len - i; j ++) {
			if ((Acc == 1 && L.r[j].no > L.r[j + 1].no) || (Acc == -1 && L.r[j].no < L.r[j + 1].no))
			 {
				tmp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = tmp;
			}
		}
	}
	//--------²¹³ä´úÂë--End------
}

//=============°´ÕÕѧºÅ¿ìËÙÅÅÐòstart=============
//Ò»ÌË¿ìËÙÅÅÐò¹ý³Ì,Acc=1±íʾÉýÐò,Acc=-1±íʾ½µÐò
int Partition(SqList &L, int low, int high, int Acc){
	//--------²¹³ä´úÂë--Start------
	Student pivotloc, tmp;
	pivotloc = L.r[low];
	while (low < high) {
		while (low < high && (Acc == 1 && L.r[high].no >= pivotloc.no) || (Acc == -1 && L.r[high].no <= pivotloc.no)) {
			high --;
		}
		L.r[low] = L.r[high];
		while (low < high && (Acc == 1 && L.r[low].no < pivotloc.no) || (Acc == -1 && L.r[low].no > pivotloc.no)) {
			low ++;
		}
		L.r[high] = L.r[low];
	}	
	L.r[low] = pivotloc;
	return low;
	//--------²¹³ä´úÂë--End------
} 
void QSort(SqList &L, int low, int high, int Acc) {
	int pivotloc;
	if(low<high){							//µ±L.r[low..high]Ϊ¿Õ»òÖ»ÓÐÒ»¸ö¼Ç¼ʱÎÞÐèÅÅÐò	
		pivotloc=Partition(L, low, high, Acc);	//¶Ô L.r[low..high]] ½øÐÐÒ»´Î»®·Ö,²¢·µ»ØÊàÖáλÖÃ
		QSort(L, low, pivotloc-1, Acc);		//µÝ¹é´¦Àí×óÇø¼ä
		QSort(L, pivotloc+1, high, Acc);		//µÝ¹é´¦ÀíÓÒÇø¼ä
	}
}
void QuickSort(SqList &L,int Acc){
	QSort(L, 1, L.length, Acc);
}
//=============°´ÕÕѧºÅ¿ìËÙÅÅÐòend=============

//Ö÷º¯Êý
int main(){
	int n,Acc,SortType;
	SqList List,TempList;
	int select;

	while(cin>>select){
		if(select==0)
			return 0;
		else if(select==1){
			cin>>n;
			CreateSqList(List, n);
		}		
		if(select==4){
			TempList=List;
			cin>>Acc;
			BubbleSort(TempList,Acc);
			PrintSqList(TempList);
		}
		if(select==5){
			TempList=List;
			cin>>Acc;
			QuickSort(TempList,Acc);
			PrintSqList(TempList);
		}
	}
	return 0;
}

8-3

#include <iostream>
using namespace std;

#define MAXSIZE 20			//¼Ç¼×î´ó¸öÊý
//ѧÉú½á¹¹Ìå
typedef struct{
	char name[10];
	int age;
	int no;
}Student;
typedef struct{
	Student r[MAXSIZE+1];//data[0]¿ÉÏÐÖûò×÷¼àÊÓÉÚ
	int length;				//˳Ðò±í³¤¶È
}SqList; 

//´´½¨Ë³Ðò±í
void CreateSqList(SqList &L, int n){
	int i;
	L.length = n;
	for(i=1; i<=L.length; i++){
		cin>>L.r[i].no>>L.r[i].age>>L.r[i].name;
	}
}

//Êä³ö˳Ðò±í
void PrintSqList(SqList &L){
	int i;
	for(i=1; i<=L.length; i++)
		cout<<L.r[i].no<<" "<<L.r[i].age<<" "<<L.r[i].name<<endl;
}

//°´ÕÕѧºÅ¼òµ¥Ñ¡ÔñÅÅÐò,Acc=1±íʾÉýÐò,Acc=-1±íʾ½µÐò
void SelectSort(SqList &L,int Acc){
	//--------²¹³ä´úÂë--Start------
	int i, j, len, ch;
	Student tmp;
	len = L.length;
	for (i = 1; i < len; i ++) {
		ch = i;
		for (j = i + 1; j <= len; j ++) {
			if ((Acc == 1 && L.r[j].no < L.r[ch].no) || (Acc == -1 && L.r[ch].no < L.r[j].no)) {
				ch = j;
			}
		}
		if (ch != i) {
			tmp = L.r[i];
			L.r[i] = L.r[ch];
			L.r[ch] = tmp;
		}
	}
	//--------²¹³ä´úÂë--End------
} 

//Ö÷º¯Êý
int main(){
	int n,Acc;
	SqList List,TempList;
	int select;

	while(cin>>select){
		if(select==0)
			return 0;
		else if(select==1){
			cin>>n;
			CreateSqList(List, n);
		}
		if(select==6){
			cin>>Acc;
			TempList=List;
			SelectSort(TempList,Acc);
			PrintSqList(TempList);
		}
	}
	return 0;
}

8-4

#include <iostream>
using namespace std;

#define MAXSIZE 20			//¼Ç¼×î´ó¸öÊý
//ѧÉú½á¹¹Ìå
typedef struct{
	char name[10];
	int age;
	int no;
}Student;
typedef struct{
	Student r[MAXSIZE+1];//r[0]¿ÉÏÐÖûò×÷¼àÊÓÉÚ
	int length;					    //˳Ðò±í³¤¶È
}SqList; 

//´´½¨Ë³Ðò±í
void CreateSqList(SqList &L, int n){
	int i;
	L.length = n;
	for(i=1; i<=L.length; i++){
		cin>>L.r[i].no>>L.r[i].age>>L.r[i].name;
	}
}

//Êä³ö˳Ðò±í
void PrintSqList(SqList &L){
	int i;
	for(i=1; i<=L.length; i++)
		cout<<L.r[i].no<<" "<<L.r[i].age<<" "<<L.r[i].name<<endl;
}

//=============°´ÕÕѧºÅ¹é²¢ÅÅÐòstart=============
//¹é²¢ÅÅÐò(½«ÓÐÐòµÄS[i..m]ºÍS[m+1..n]ºÏ²¢ÎªÓÐÐòµÄT[i..n])
void Merge(Student S[], Student T[], int i, int m, int n){
	//--------²¹³ä´úÂë--Start------
	int p, q, k;
	p = i;
	q = m + 1;
	k = i;
	while (p <= m && q <= n) {
		if (S[p].no <= S[q].no) {
			T[k ++] = S[p ++];
		}
		else {
			T[k ++] = S[q ++];
		}
	}
	while (p <= m) {
		T[k ++] = S[p ++];
	}
	while (q <= n) {
		T[k ++] = S[q ++];
	}
	//--------²¹³ä´úÂë--End------
}
//½«S[s..t]¹é²¢ÅÅÐòΪT[s..t]
void MSort(Student S[], Student T1[], int s, int t){
	int mid;	
	if(s==t)
		T1[s]=S[s];
	else{
		Student T2[MAXSIZE]; 
		mid=(s+t)/2;					//½«S[s..t]ƽ·ÖΪS[s..m]ºÍS[m+1..t]
		MSort(S, T2, s, mid);
		MSort(S, T2, mid+1, t);
		Merge(T2, T1, s, mid, t);
	} 
}
void MergeSort(SqList &L){
	MSort(L.r, L.r, 1, L.length);
}
//=============°´ÕÕѧºÅ¹é²¢ÅÅÐòend=============
//Ö÷º¯Êý
int main(){
	int n;
	SqList List,TempList;
	int select;

	while(cin>>select){
		if(select==0)
			return 0;
		else if(select==1){
			cin>>n;
			CreateSqList(List, n);
		}		
		if(select==7){
			TempList=List;
			MergeSort(TempList);
			PrintSqList(TempList);
		}
	}
	return 0;
}