데이터 구조 면접 문제
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.