왕도 2019 데이터 구조 제2 장 선형 표 종합 응용 문제 노트

4546 단어 데이터 구조
#include
using namespace std;
#define MAXSIZE 50
typedef int ElemType;
typedef struct {

	ElemType data[MAXSIZE];
	int length;

}SqList;

//1、               (    )              ,              ,                  
bool Del_Min(SqList &L, ElemType &value) {
	//     L         ,        value    
	//      ,  true,  ,  false;
	if (L.length == 0) {
		return false;//  ,      
	}
	value = L.data[0];
	int pos = 0;
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] < value) {
			value = L.data[i];
			pos = i;
		}
	}
	L.data[pos] = L.data[L.length - 1];
	L.length--;
	return true;

}

//2、         ,           ,           O(1)
void Reverse(SqList &L) {
	ElemType temp;
	for (int i = 0; i < L.length / 2; i++) {
		temp = L.data[i];
		L.data[i] = L.data[L.length - 1 - i];
		L.data[L.length - 1 - i] = temp;
	}

}

//3、   n    L,          O(n)、      O(1)   ,             x     
void delete_(SqList &L, ElemType x) {
	int k = 0;
	for (int i = 0; i < L.length; i++) {//    x      ,           
		if (L.data[i] != x) {
			L.data[k] = L.data[i];
			k++;
		}
	}
	L.length = k;
}
//4、               s t  (  s= t || 0 == L.length) {
		return false;
	}
	int l, r, length;
	for (l = 0; s > L.data[l]; l++);//l         s    ,       , l       
	for (r = L.length - 1; t < L.data[r]; r--);//r         t    ,          r+1      
	length = r - l + 1;//l   r    r-l+1   
	for (int k = r + 1; k < L.length; k++) {
		L.data[l++] = L.data[k];
	}
	L.length -= length;//                 
	return true;
}
//5、             s t  (  s t  s= t || 0 == L.length) {
		return false;
	}
	int i, k = 0;
	//    :      L, k       s t        ,         ,  i    s t     k   ,    k++
	//    s t                 
	for (i = 0; i < L.length; i++) {
		if (L.data[i] >= s && L.data[i] <= t) {
			k++;
		}
		else {
			L.data[i - k] = L.data[i];
		}
	}
	L.length = k;
	return true;
}

//6、                  ,             
void delete_6(SqList &L) {
	int k = 0;
	for (int i = 1; i < L.length; i++) {
		if (L.data[i] == L.data[i - 1]) {
			k++;
			continue;
		}
		L.data[i - k] = L.data[i];
	}
	L.length -= k;
}

//7、                   ,             (    )
bool Ques7(SqList sqList1, SqList sqList2, SqList &newSqList) {
	//                                     
	if (size(newSqList.data) < sqList1.length + sqList2.length) { //                      size()             
		return false;
	}
	int i = 0, j = 0, k = 0;
	while (i < sqList1.length && j < sqList2.length) {
		if (sqList1.data[i] <= sqList2.data[j]) {
			newSqList.data[k++] = sqList1.data[i++];
		}
		else {
			newSqList.data[k++] = sqList2.data[j++];
		}
	}
	while (i < sqList1.length) {
		newSqList.data[k++] = sqList1.data[i++];
	}
	while (j < sqList1.length) {
		newSqList.data[k++] = sqList2.data[j++];
	}
	newSqList.length = k + 1;
	return true;

}

//8、       A[m+n]           (a1,a2,....,am) (b1,b2,...,bn)。       ,               
void Que8(ElemType A[], int m, int n) {
	//  :          ,         
	ElemType temp;
	int i = 0;
	for (i = 0; i < m / 2; i++) {//      
		temp = A[i];
		A[i] = A[m - 1 - i];
		A[m - 1 - i] = temp;
	}
	for (i = 0; i < (n - m) / 2; i++) {//      
		temp = A[i+m];
		A[i+m] = A[n-i-1];
		A[n - i-1] = temp;
	}

	for (i = 0; i < n / 2; i++) {//    
		temp = A[i];
		A[i] = A[n - 1 - i];
		A[n - 1 - i] = temp;
	}

}

int main() {
	/*SqList sqList;
	for (int i = 0; i < 20; i++) {
		sqList.data[i] = i/2;
	}
	sqList.length = 20;
	for (int i = 0; i < sqList.length; i++) {
		cout << sqList.data[i] << " ";
	}
	cout << endl;
	cout << sizeof(sqList.data) << endl;
	cout << sizeof(sqList.data[0]) << endl;
	cout << size(sqList.data)<< endl;
	cout << endl << "len" << sqList.length << endl;
	delete_6(sqList);
	for (int i = 0; i < sqList.length; i++) {
		cout << sqList.data[i] << " ";
	}
	cout << endl << "len" << sqList.length << endl;
	system("pause");
*/
	ElemType a[10];
	for (int i = 0; i < 10; i++) {
		a[i] = rand() % 99;
		cout << a[i] << " ";
	}
	cout << endl;
	Que8(a, 4, 10);
	for (int i = 0; i < 10; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

좋은 웹페이지 즐겨찾기