[왕도 데이터 구조 문제 풀이 기록] 2.2.3 순서 표 코드 부분 (업데이트 중)

앞 에 쓰기:
책 에 코드 문 제 를 쓸 수 없 기 때문에 블 로 그 를 열 어 코드 문 제 를 쓰 는 과정 을 기록 하 세 요.개정 부분 은 표기 할 것 이다.
그래서 이것 은 저 개인의 문제 기록 일 뿐 정 답 이 아 닙 니 다. 일 부 는 정 답 을 주 고 교 류 를 환영 합 니 다.
2.2.3 종합 응용 문제 p19
1. 순서 표 에서 최소 값 을 가 진 요 소 를 삭제 하고 함수 에서 삭 제 된 요소 의 값 을 되 돌려 줍 니 다.비어 있 는 위 치 는 마지막 요소 로 채 워 집 니 다. 순서 표 가 비어 있 으 면 오류 정 보 를 표시 하고 실행 을 종료 합 니 다.
알고리즘 사상: 찾기 + 교체

bool Del_min(SeqList &L, int &e)
{
	int t = 100000;
	int k = 0;
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] < t) {
			t = L.data[i];
			k = i + 1;
		}
	}
	if (k<1 || k>L.length)
		return false;
	e = L.data[k - 1];
        L.data[k - 1] = L.data[L.length - 1];
        L.length--;//      
	return true;
}

2. 효율 적 인 알고리즘 을 설계 하여 순서 표 L 의 모든 요 소 를 역 설정 하고 알고리즘 의 공간 복잡 도 를 O (1) 로 요구한다.
알고리즘 사상: 값 을 꺼 내 서 거꾸로 값 을 부여 합 니 다.

void SL_inverse(SeqList &L)
{
	int a[1000];
	int j = 0;
	for (int i = L.length - 1; i >= 0; i--)
	{
		a[j] = L.data[i];
		j++;
	}
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = a[j - 1];
		j--;
	}
}

참고 답안:

void Reverse(SqList &L)
{
    Elemtype temp;
    for(int i=0;i

3. 길이 가 n 인 순서 표 L 에 대해 시간 복잡 도가 O (n) 이 고 공간 복잡 도가 O (1) 인 알고리즘 을 작성 합 니 다. 이 알고리즘 은 선형 표 의 모든 값 이 x 인 데이터 요 소 를 삭제 합 니 다.
알고리즘 사상: 값 에 따라 찾기, 삭제

bool DeleteX(SeqList &L, Elemtype &x)
{
	int k[MaxSize];
	int j = 0;
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == x) {
			k[j] = i;
			j++;
		}
	}
	int g = j - 1;
	if (j==0)
		return false;
	for (j = 0; j < g; j++) {
		x = L.data[k[j]];
		for (int p = 0; p < L.length; p++)
		{
			L.data[p - 1] = L.data[p];
		}
		L.length--;
	}
	return true;
}

이 답안 은 너무 우수 하 다

void del_x(SeqList &L, Elemtype x) {
	int k = 0;
	for (int i = 0; i < L.length; i++)
		if (L.data[i] != x) {
			L.data[k] = L.data[i];
			k++;
		}
	L.length = k;
}

4. 질서 있 는 순서 표 에서 그 값 을 삭제 합 니 다. 주어진 값 s 와 t 사이 (요구 s)
알고리즘 사상: 삭제

bool del_s_t(SeqList &L, int s, int t, int &e)
{
	if (L.length<1 || s>t)return false;//    s>=t
	int k = 0;
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i]<=s) {
			L.data[k] = L.data[i];
			k++;
		}
		else if (L.data[i] >= t) {
			L.data[k] = L.data[i];
			k++;
		}
	}
	L.length = k;
	return true;
}

emmm 나 는 내 가 이 문제 가 답 보다 약간 ok 이 라 고 생각한다.
5. 순서 표 에서 그 값 을 삭제 합 니 다. 주어진 값 s 와 t 사이 (s 와 t 포함, 요구 s 포함)
알고리즘 사상: 이전 문제 와 마찬가지 로 제거 하면 s 와 t 와 같다.

bool del_s_t(SeqList &L, int s, int t, int &e)
{
	if (L.length<1 || s>=t)return false;
	int k = 0;
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] t) {
			L.data[k] = L.data[i];
			k++;
		}
	}
	L.length = k;
	return true;
}

6. 질서 있 는 순서 표 에서 모든 값 이 중복 되 는 요 소 를 삭제 하여 표 의 모든 요소 의 값 을 다 르 게 합 니 다.
사고: 값 배열 을 만 들 고 순서 표를 옮 겨 다 니 며 값 배열 을 누적 합 니 다. > 1 을 만나면 삭 제 됩 니 다.

void del_same(SeqList &L)
{
	int sa[10000];
	int k = 0;
	memset(sa ,0 , sizeof(sa));
	for (int i = 0; i < L.length; i++)
	{
		sa[L.data[i]]++;
		if (sa[L.data[i]] > 1) {
			k++;
			for (int j = i; j < L.length; j++)
			{
				L.data[j - 1] = L.data[j];
			}
			i--;
		}
	}
	L.length = L.length - k;
}

표준 답안:
(나 는 문제 의 중요 한 부분 을 질서 라 고 빠 뜨 렸 지만, 나의 답 은 사실 질서 표 에 도 적용 된다. 그러나 표준 답안 은 좀 더 간결 하 다.)

bool Delete_Same(SeqList& L)
{
	if (L.length == 0)
		return false;
	int i, j;
	for (i = 0,j = 1; j < L.length; j++)
		if (L.data[i] != L.data[j])
			L.data[++i] = L.data[j];
	L.length = i + 1;
	return true;
}

7. 두 개의 질서 있 는 순서 표를 새로운 질서 있 는 순서 표 로 합 쳐 함수 에서 결과 순서 표를 되 돌려 줍 니 다.
사고: 두 개의 시 계 를 옮 겨 다 니 며 작은 것 을 골 라 세 번 째 시 계 를 넣는다.

SeqList uni(SeqList &L1, SeqList &L2)
{
	SeqList L;
	for (int i = 0,j = 0,k = 0; i < L1.length+L2.length; i++)
	{
		if (L1.data[j] < L2.data[k])
		{
			L.data[i] = L1.data[j];
			j++;
		}
		else {
			L.data[i] = L2.data[k];
			k++;
		}
	}
	L.length = L1.length + L2.length;
	return L;
}

표준 답안:
건장 성 이 제 코드 보다 좋아 서 예 판 을 많이 늘 렸 습 니 다. 그리고 제 코드 에 bug 가 있 습 니 다. L1 을 다 쓴 후에 도 j 는 + 에 있 습 니 다. 그 후에 읽 은 값 에 문제 가 생 길 수 있 습 니 다.

bool Merge(SeqList A, SeqList B, SeqList &C) {
	if (A.length + B.length > C.maxSize)
		return false;
	int i = 0, j = 0, k = 0;
	while (i < A.length&&j < B.length) {
		if (A.data[i] <= B.data[j])
			C.data[k++] = A.data[i++];
		else
			C.data[k++] = B.data[j++];
	}
	while (i < A.length)
		C.data[k++] = A.data[i++];
	while (j < B.length)
		C.data[k++] = B.data[j++];
	C.length = k;
	return true;
}

8. 1 차원 배열 A [m + n] 에 두 개의 선형 표 (a1, a2, a3. am) 와 (b1, b2, b3. bn) 를 순서대로 저장 합 니 다. 함 수 를 만들어 서 배열 의 두 순서 표 의 위 치 를 바 꾸 십시오. 곧 (b1, b2, b3. bn) 을 (a1, a2, a3. am) 앞 에 놓 을 것 입 니 다.
사고: 실수 로 답 을 보고 답 이 너무 훌륭 하 다 고 생각해 서 바로 답 을 썼 다.

typedef int DataType;
void Reverse(DataType A[], int left, int right, int arraySize) {
	if (left >= right || right >= arraySize)
		return;
	int mid = (left + right) / 2;
	for (int i = 0; i <= mid - left; i++)
	{
		DataType temp = A[left + i];
		A[left + i] = A[right - i];
		A[right - i] = temp;
	}
}
void Exchange(DateType A[], int m, int n, int arraySize) {
	Reverse(A, 0, m + n - 1, arraySize);
	Reverse(A, 0, n - 1, arraySize);
	Reverse(A, n, m + n - 1, arraySize);
}

(미 완성 계속)