이번 주 내 실험실 과제에 대한 안녕하세요, 저는 연결된 목록에 대해 배웠습니다. 다음 랩 프롬프트이다C++ 연결된 목록 정렬, 나누기 및 인쇄 문제
각 요소는 0 ~ 99 인쇄 목록 사이의 임의의 정수를 보유하고 적어도 20 요소의 순방향 링크 된리스트를 생성하는 프로그램을 작성한다.
"returnMiddleList"함수를 작성하여 링크 된 목록의 중간 요소를 한 번에 찾습니다. 이 요소의 정수 값과이 요소의 위치 (0에서 시작)를 머리에 대해 출력합니다 (여기서 head = 0, head가 가리키는 요소 = 1, 이전 요소가 가리키는 요소 = 2 , 등).
가운데 요소에서 목록을 절반으로 분할하여 거의 동일한 크기 (+/- 1)의 완전히 별개의 * 연결된 목록을 만들고 두 목록을 인쇄하십시오. 이를 달성하기 위해 "returnMiddleList"함수를 수정하여 두 번째 연결된 목록의 머리글을 반환하고 해당 머리글을 가리키는 요소의 링크를 null로 설정하십시오. 그런 다음 두 목록의 요소에 저장된 정수의 두 합계를 인쇄하십시오.
두 목록을 최소에서 최대로 정렬하고 인쇄하십시오 (이 단계에서의 인쇄는 정렬 방법에 따라 선택 사항입니다). 그런 다음 두 목록을 결합하여 최소 순위에서 최대 순위로 다시 정렬하고 새 목록을 인쇄하십시오. (힌트 :. 당신이 더 목록을 세분화 정렬 및 처음 두 정렬되지 않은 목록을 결합하기 전에 한 두 요소 목록의 규모에이를 정렬 할 수 있습니다 불리는 이런 종류의 무엇입니까?)
나는 # 1을 가지고있다 # 2는 작동하지만 # 3과 # 4는 문제가 시작되는 곳입니다. 링크 목록을 두 개의 목록으로 나누고 개별 목록을 인쇄 할 때 첫 번째 목록은 10을 인쇄 할 때 9 개의 숫자를 인쇄합니다 (10 번째 숫자는 어떻게 든 사라 집니까?). 그러나 첫 번째 목록의 합계를 계산하면 그 직후, 사라진 숫자가 합계에 추가됩니다! 나는 그것이 왜 사라지고 있는지 모릅니다. 그리고 이것은 하나의 문제입니다. 두 번째 목록에 또 다른 문제가 있습니다. 임의의 "0"이 목록에 추가되고 숫자 중 하나가 손실됩니다. 내가 사용한 병합 알고리즘이 작동하지 않는 것처럼 마지막 문제는 # 4에 관한 것입니다. 정렬하는 동안 목록을 함께 병합하고 있지만 아직 배운 적이 없기 때문에 재귀 정렬을 사용하지 않습니다. 모든 입력과 도움을 주시면 대단히 감사하겠습니다! 감사!
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct nodeType {
int data;
nodeType *link;
};
void populateList(nodeType *head) {
// srand(time(NULL));
nodeType *temp;
nodeType *current = head;
for (int i = 0; i < 20; i++) {
temp = new nodeType;
current->data = rand() % 100;
current->link = temp;
current = temp;
}
temp->link = NULL;
}
void print(nodeType *head) {
int i = 1;
while (head->link != NULL) {
cout << "#" << i++ << ": " << head->data << endl;
head = head->link;
}
}
nodeType* returnMiddleList(nodeType *head) {
nodeType *p1 = head, *p2 = head;
int count = 0;
int middle = 1;
while (p1->link->link != NULL) {
p1 = p1->link;
count++;
if (count % 2 == 0) {
p2 = p2->link;
middle++;
}
}
cout << "Middle #" << middle << ": " << p2->data << endl;
p1 = p2->link;
p2->link = NULL;
return p1;
}
void add(nodeType *head) {
int sum = 0;
while (head != NULL) {
sum = sum + head->data;
head = head->link;
}
cout << sum << endl;
}
void sort(nodeType *head) {
nodeType *temp = head;
while (temp != NULL) {
nodeType *temp2 = temp;
while (temp2 != NULL) {
if (temp->data > temp2->data) {
int temp3;
temp3 = temp->data;
temp->data = temp2->data;
temp2->data = temp3;
}
temp2 = temp2->link;
}
temp = temp->link;
}
}
nodeType* merge(nodeType* head1, nodeType* head2) {
nodeType *head3 = new nodeType, *current1 = head1, *current2 = head2;
while (current1 != NULL || current2 != NULL) {
if (current1 == NULL) {
while (current2 != NULL) {
//logic
current2 = current2->link; //dumps list 2
head3->data = current2->data;
}
break;
}
if (current2 == NULL) {
while (current1 != NULL) {
//Logic
current1 = current1->link; //dumps list 1
head3->data = current1->data;
}
break;
}
if (current1->data < current2->data) {
//logic
current1 = current1->link; //increments list 1
head3->data = current1->data;
} else {
//logic
current2 = current2->link; //increments list 2
head3->data = current2->data;
}
}
return head3;
}
int main() {
nodeType *head = new nodeType, *head2, *head3;
populateList(head);
print(head);
cout << endl;
head2 = returnMiddleList(head);
cout << endl << "List #1 Sum: ";
add(head);
cout << endl << "List #2 Sum: ";
add(head2);
sort(head);
cout << endl << "List #1 Sorted" << endl;
print(head);
sort(head2);
cout << endl << "List #2 Sorted" << endl;
print(head2);
head3 = merge(head, head2);
print(head3);
}
디버거를 사용하는 법을 배워야 할 때입니다. – PaulMcKenzie
나는 포럼에 도움을 받기 전에 혼란의 정도까지 그것을 사용했다. – Twigler
그냥 디버깅 이외에, * 이름 * 것들을하는 것이 좋습니다. 이름 조작. 이름 데이터. –