데이터 구조 면접 중 하나 인 단일 체인 테이블 흔 한 조작
제목: 는 관련 연습 문제 가 있 지만 생각 이 상대 적 으로 뚜렷 하지 않 고 조판 에 오류 가 있 습 니 다. 본 고 는 이에 대해 관련 서적 과 자신의 관점 을 참고 하여 재 작성 하여 여러분 께 참고 하도록 하 겠 습 니 다.
1. 링크 요소 찾기
Step 1: 찾기 태그 bfound = false 설정;링크 가 비어 있 는 지 여 부 를 판단 하 는 것 은 '빈 링크 를 찾 을 수 없습니다' 라 는 것 입 니 다.아니오, step 2 에 들 어 갑 니 다.
Step 2: 링크 헤드 부터 찾 아 보 세 요.
Step 3: 판단 bfound = = true, 예, "힌트 찾기 성공", 아니오, "힌트 찾기 실패".
/
template<typename Type>
void linkedlistType<Type>::search(const Type& searchItem)
{
nodeType<Type> *current;
bool found = false;
if(first == NULL) //1.
{
cout << "WARNING: Can not search an empty list!" << endl;
return;
}
else
{
current = first;
while(!found && current != NULL)
{
if(current->info == searchItem)
{
found = true;
break;
}
else
{
current = current->link;
}
}
if(found)
{
cout << searchItem << " was found in the List! " << endl;
}
else
{
cout << searchItem << " was not found in the List! " << endl;
}
}
}2. 링크 요소 값 삭제
Step 1: 찾기 태그 bfound = false 설정;링크 가 비어 있 는 지 여 부 를 판단 하 는 것 은 '빈 링크 를 삭제 할 수 없습니다' 라 는 것 입 니 다.아니오, step 2 에 들 어 갑 니 다.
Step 2: 삭제 해 야 할 요소 값 이 헤드 노드 요소 값 과 같 는 지 판단 합 니 다. 예, 헤드 노드 지침 을 조정 합 니 다.아니오, step 3 에 들 어 갑 니 다.
Step 3: 링크 에 이 요소 가 존재 하 는 지 여 부 를 판단 합 니 다. "제시 요소 가 존재 하지 않 습 니 다".네, step 4 에 들 어 갑 니 다.
Step 4: 요소 가 끝 노드 요소 값 과 같 는 지 판단 합 니 다. 예, 끝 last 지침 을 조정 합 니 다.아니오, 이 때 는 중간 노드 입 니 다. trailCurrent 와 Current 포인터 의 방향 을 조정 해 야 합 니 다.
//
template<typename Type>
void linkedlistType<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *tempNode = new nodeType<Type>;
nodeType<Type> *current = new nodeType<Type>;
nodeType<Type> *trailCurrent = new nodeType<Type>;
bool found;
// case1
if(first == NULL)
{
cout << "Can not delete an empty List!" << endl;
}
else
{
if( first->info == deleteItem )
{
// ( ， ) case2
tempNode = first;
first = first->link;
if(first == NULL)
{
last = NULL;
}
delete tempNode;
}
else
{
// ， ... case3
found = false;
trailCurrent = first;
current = first->link;
while((!found) && (current != NULL))
{
if(deleteItem != current->info)
{
trailCurrent = current;
current = current->link;
}
else
{
found = true;
}
}
if(found)
{
// ...
trailCurrent ->link = current->link;
if(current == last)
{
last = trailCurrent; //case 3a
}
delete current; //case 3b
}
// ...case4
else
{
cout << "The deleteItem is not Exist in the List! " << endl;
} //end else
}//end else
}//end else
}// end deleteNode3. 단일 체인 표 역 치 [교체 실현]
Step 1: 링크 가 비어 있 는 지 여 부 를 판단 하 는 것 은 '빈 링크 에 대해 역 설정 작업 을 할 수 없다' 는 것 이다. 아니, Step 2 에 들 어 가 는 것 이다.
Step 2: 두 번 째 노드 부터 각 노드 를 첫 번 째 노드 의 앞 에 순서대로 삽입 하여 포인터 가 링크 의 끝 을 가리 키 는 지 판단 합 니 다. 예, 돌아 오 는 포인터 가 끝 났 는 지, 아 닌 지, 뒤의 링크 요 소 를 계속 교체 합 니 다.
template<typename Type>
nodeType<Type>* linkedlistType<Type>::reverseList() //
{
if(first == NULL)
{
cout << "Can't reverse empty List!" << endl;
}
else
{
nodeType<Type>* p = first;
nodeType<Type>* q = p->link;
while(q != NULL)
{
p->link = q->link;
q->link = first;
first = q;
q = p->link;
}
}
return first;
}4. 단일 링크 정렬 [직접 정렬 삽입]
사고방식: 다음 과 같은 몇 가지 상황 으로 나 뉜 다.
1） 단일 체인 시계 가 비어 있 습 니 다.
2） 단일 체인 표 는 비어 있 지 않 지만 하나의 요소 만 포함 하고 정렬 할 필요 가 없습니다.
3） 머리 노드 보다 작은 요 소 를 삽입 할 때;
4） 삽입 할 요 소 는 질서 있 는 중간 요소 값 입 니 다.
5） 삽입 할 요소 앞 에 있 는 모든 요 소 는 그 보다 작 아서 바로 끝 에 꽂 습 니 다.
각각 lastInOrder 로 질서 있 는 마지막 노드 를 기록 합 니 다. firstOutOfOrder 의 첫 번 째 정렬 되 지 않 은 노드 입 니 다. current 는 순환 하 는 노드 를 기록 하고 trailCurrent 는 current 전의 노드 를 기록 합 니 다.
template<typename Type>
void linkedlistType<Type>::sortList() //
{
nodeType<Type>* current;
nodeType<Type>* trailCurrent;
nodeType<Type>* lastInOrder;
nodeType<Type>* firstOutOfOrder;
lastInOrder = first;
//case1, .
if(first == NULL)
{
cout << "Can't Sort of empty List!" << endl;
return;
}
//case2, , 1, 1 .
if(first->link == NULL)
{
cout << "The List Was Already ordered!" << endl;
return;
}
while(lastInOrder->link != NULL)
{
firstOutOfOrder = lastInOrder->link;
//case3, 1 .
if(firstOutOfOrder->info < first->info)
{
lastInOrder->link = firstOutOfOrder->link;
firstOutOfOrder->link = first;
first = firstOutOfOrder;
}
else
{
trailCurrent = first;
current = first->link;
while(current->info < firstOutOfOrder->info)
{
trailCurrent = current;
current = current->link;
}
//case4, .
if(trailCurrent != lastInOrder)
{
lastInOrder->link = firstOutOfOrder->link;
firstOutOfOrder->link = current;
trailCurrent->link = firstOutOfOrder;
}
else
{
//case5, .
lastInOrder = lastInOrder->link;
}//end else
}//end else
}//end while
}
5. 단일 체인 테이블 은 체인 테이블 의 길 이 를 모 르 는 전제 에서 체인 테이블 중간 노드 의 값 을 구한다.
사고방식: 다음 과 같은 몇 가지 상황 으로 나 뉜 다.
1） 링크 가 비어 있 습 니 다.
2） 링크 는 비어 있 지 않 지만 하나 또는 두 개의 노드 만 있 고 첫 번 째 노드 의 요소 값 을 직접 되 돌려 줄 수 있 습 니 다.
3） 링크 가 비어 있 지 않 지만 세 개 이상 의 노드 를 포함 하고 있 습 니 다. 두 개의 지침 을 정의 할 수 있 습 니 다. 한 지침 의 스텝 이 2 번 일 때 다른 지침 의 스텝 은 1 번 입 니 다. 끝까지 뛰 었 을 때 다른 노드 는 중간 에 있 습 니 다.
/ / 표 의 길 이 를 모 르 는 전제 에서 단일 체인 표 중간 요 소 를 구하 십시오.
template<typename Type>
Type linkedlistType<Type>::midValOfList()
{
nodeType<Type> *current;
nodeType<Type> *halfCurrent;
if(first == NULL) //case1,
{
cout << " !" << endl;
return -1;
}
else if(first->link == NULL || first->link->link == NULL) //case2, .
{
return first->info;
}
else //case3, .
{
current = first;
halfCurrent = current;
while(current->link != NULL)
{
current = current->link;
if(current->link != NULL)
{
if(current->link != NULL)
{
halfCurrent = halfCurrent->link;
current = current->link;
}//end if
}
}//end while
return halfCurrent->info;
}//end else
}6. 단일 체인 테이블 구축
사고방식: 단일 체인 테이블 의 구축 은 새로운 노드 를 삽입 하 는 위치 에 따라 두 가지 로 나 눌 수 있다. 1: 체인 테이블 끝 에 요 소 를 삽입 하 는 구축 방식, 2: 체인 테이블 앞 에 요 소 를 삽입 하여 체인 테이블 을 만 드 는 방식 이다.
대응 하 는 1 끝 삽입 은 두 단계 로 나 뉜 다.
Step 1: 현재 링크 가 비어 있 으 면 first = last = new Node 를 설정 합 니 다. 그렇지 않 으 면 Step 2 에 들 어 갑 니 다.
Step 2: 새로운 노드 요 소 를 삽입 하고 last 지침 을 수정 합 니 다.
2. 링크 first 포인터 앞 에 삽입: 요 소 를 삽입 한 후에 first 노드 를 수정 하면 됩 니 다.
//
template<typename Type>
nodeType<Type>* linkedlistType<Type>::buildListForward()
{
nodeType<Type> *newNode;
int num;
cout << " Enter a list of integer end with -999. " << endl;
cin >> num;
while(num != -999)
{
//..add
newNode = new nodeType<Type>;
newNode->info = num;
newNode->link = NULL;
if(first==NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
cin >> num;
}
return first;
}
// ， ...
template<typename Type>
nodeType<Type>* linkedlistType<Type>::buildListBackward()
{
nodeType<Type> *newNode;
int num;
cout << " Enter a list of integer end with -999. " << endl;
cin >> num;
while(num != -999)
{
//..add
newNode = new nodeType<Type>;
newNode->info = num;
newNode->link = first;
first = newNode;
cin >> num;
}
return first;
}7. 싱글 체인 시트 의 길이 측정
사고방식: 체인 테이블 의 길이 등 효 과 는 노드 개수 이 고 바늘 이 비어 있 지 않 으 면 순환 적 으로 판단 하면 된다.
//
template<typename Type>
int linkedlistType<Type>::length()
{
int count = 0;
nodeType<Type> *current;
current = first;
while(current != NULL)
{
count++;
current = current->link;
}
return count; // .
}8. 싱글 체인 시트 의 삽입
사고방식: 체인 테이블 의 삽입 도 체인 테이블 의 구축 과 마찬가지 로 전방 향, 후방 향 삽입 두 가지 형식 으로 나 뉘 는데 first, last 지침 의 지향 문 제 를 주의해 야 한다.
//
template<typename Type>
void linkedlistType<Type>::insertFirst(const Type& newItem)
{
//last no use.
nodeType<Type> *newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = first; // ...
first = newNode;
}
// ...
template<typename Type>
void linkedlistType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL; // ...
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
}다음 에 스 택, 대기 열, 이 진 트 리, 그림, 정렬, 찾기 등 관련 분석 이 있 을 것 입 니 다. 관심 가 져 주 십시오!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
