데이터 구조 면접 문제

1704 단어
1. 단일 링크 의 정렬
1) 거품 정렬:
typedef struct Node{
	int val;
	node *next;
	Node(){ val = 0; next = NULL; }
}node;

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

int Length(node *head){
	int size = 0;
	while (head)
	{
		size++;
		head = head->next;
	}
	return size;
}
node *sort(node *head){//    ,     ,     ,  
	int n = Length(head);
	node *p = head;
	for (int i = 1; i < n; ++i)
	{
		p = head;
		for (int j = 0; j < n - i; ++j)
		{
			if (p->val>p->next->val) swap(p->val, p->next->val);
			p = p->next;
		}
	}
	return head;
}

2) 빠 른 정렬:
사고: 두 개의 포인터 p 와 q 는 모두 next 방향 으로 이동 합 니 다. 이동 과정 에서 p 전의 값 이 key 보다 적 고 p 와 q 간 의 값 이 key 보다 크 며 q 가 끝까지 갈 때 한 번 의 구분 을 완성 합 니 다.
4. 567913. 주의: 빠 른 배열 은 단일 체인 표 에 적합 하지 않 습 니 다. 그 이 유 는 가장 이상 적 인 상황 에서 도 모든 데 이 터 를 한 번 교환 해 야 하기 때 문 입 니 다.
메모: 호출 형식 은 다음 과 같 습 니 다.
node *Partition(node *pBegin, node *pEnd)
{
	if (pBegin == pEnd) return pBegin;
	int key = pBegin->val;
	node *p = pBegin;
	node *q = p->next;
	while (q != pEnd)
	{
		if (q->val < key)
		{
			p = p->next;
			swap(p->val, q->val);
		}
		q = q->next;
	}
	swap(p->val, pBegin->val);
	return p;
}

node *QuickSort(node *pBegin, node *pEnd)
{
	if (pBegin == pEnd) return pBegin;
	node *partition = Partition(pBegin, pEnd);
	QuickSort(pBegin, partition);
	QuickSort(partition, pEnd);
}

2. 정적 링크
정적 링크 는 배열 로 링크 를 실현 하 는 것 입 니 다. 배열 의 모든 요 소 는 하나의 구조 체 로 data 와 커서 cur 를 포함 합 니 다. 그 중에서 cur 는 링크 의 next 와 유사 하여 다음 요소 가 배열 에 있 는 아래 표 시 를 가리 킵 니 다.
QuickSort(head,NULL);  //NULL     

좋은 웹페이지 즐겨찾기