C 中的合并排序，我不断收到错误。我的方法正确吗？
Mergesort in C and I keep getting errors. Is my approach correct?
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// PURPOSE:
const int LINE_LEN = 256;
#define STOP_CMD "quit"
const int STOP_CMD_LEN = sizeof(STOP_CMD) - 1;
// PURPOSE: To hold a node in a linked list of integers.
struct Node {
int value_;
struct Node *nextPtr_;
};
// PURPOSE: To create and return a linked list of integer pairs.
struct Node *makeList() {
struct Node *list = NULL;
struct Node *end = NULL;
struct Node *next;
int value;
char line[LINE_LEN];
while (1) {
printf("Integer (or %s) to quit: ", STOP_CMD);
fgets(line, LINE_LEN, stdin);
if (strncmp(line, STOP_CMD, STOP_CMD_LEN) == 0)
break;
value = strtol(line,NULL,10);
next = (struct Node *)malloc(sizeof(struct Node));
if (list == NULL) {
list = next;
} else {
end->nextPtr_ = next;
}
end = next;
next->value_ = value;
next->nextPtr_ = NULL;
}
return (list);
}
// PURPOSE: To print the 'value_' values found in 'list'. No return value.
void print(const struct Node *list) {
const struct Node *run;
for (run = list; run != NULL; run = run->nextPtr_)
printf("%d\n", run->value_);
}
// PURPOSE: To sort the items in 'list' in ascending order according to
// their value for 'value_'. Returns sorted list.
struct Node *sort(struct Node *list) {
// Merge-sort is recursive, so there is/are base case(s):
// For merge-sort, the base cases are when 'list' has either 0 or 1
// node it it. If 'list' points to either 0 or 1 thing then return 'list':
// YOUR CODE HERE
if (list == NULL || list->nextPtr_ == NULL) {
return list;
}
// This is the beginning of the recursive case.
// We have to split 'list' into two lists of approximately the same length.
// A straight-forward way to do that is with loop and 3 pointer variables:
// (*) 'full' races through the list starting at 'list' 2 nodes at a time.
// The loop should stop when either 'full' lands on 'NULL', or the
// next of 'full' is 'NULL'.
// (*) 'half' starts at 'list' but goes through at 1/2 the speed by only
// getting the next (not the next-next like 'full'). When 'full'
// reaches the end then 'half' will point to the *beginning* of the
// second list. We need this node, but we *also* need the one just
// before 'half'. So that is why there is also . . .
// (*) 'prevHalf', whose job is to take the value 'half' just had.
// Just before advancing 'half' to its next, give 'prevHalf' the old
// value of 'half'.
struct Node *full;
struct Node *half;
struct Node *prevHalf = NULL;
// YOUR CODE HERE
full = list;
half = list;
while (full != NULL) {
full = full->nextPtr_;
if (full != NULL){
prevHalf = half;
half = half->nextPtr_;
}
}
// Here we separate both sublists:
prevHalf->nextPtr_ = NULL;
// Here we recursively sort both sublists:
struct Node *firstHalf = sort(list);
struct Node *secondHalf = sort(half);
struct Node *end = NULL;
// Here we merge the lists pointed to by 'firstHalf' and 'secondHalf'.
// Make 'list' point to the beginning of the combined list, and use 'end'
// to keep track of the end.
// Use a loop to while both 'firstHalf' and 'secondHalf' are both not yet
// at the end of their lists, then compare the values that both point to.
// If 'firstHalf' points to the lower value then put it at the end of the
// combined list. Else put 'secondHalf' at the end.
// You do not have to remove the node from the old list, but you *do* have
// to advance which ever pointer you used (either 'firstHalf' or
// 'secondHalf') to point to the next node in the list.
// When either 'firstHalf' or 'secondHalf' are 'NULL' then quit the loop:
list = NULL;
// YOUR CODE HERE
// if (firstHalf value_->secondHalf->value_) {
if (firstHalf->value_ & secondHalf->value_) {
list = firstHalf;
end = firstHalf;
firstHalf = firstHalf->nextPtr_;
} else {
list = secondHalf;
end = secondHalf;
secondHalf = secondHalf->nextPtr_;
}
while ((firstHalf != NULL) && (secondHalf != NULL)) {
if (firstHalf->value_ & secondHalf->value_) {
list->nextPtr_ = firstHalf;
end->nextPtr_ = firstHalf;
firstHalf = firstHalf->nextPtr_;
end = end->nextPtr_;
} else {
list->nextPtr_ = secondHalf;
end->nextPtr_ = secondHalf;
secondHalf = secondHalf->nextPtr_;
end = end->nextPtr_;
}
}
// Almost finished!
// You made it to the end of one list, but there still is the other one.
// Make the node pointed to by 'end' point to which ever list that you did
// *not* go all the way through.
// YOUR CODE HERE
while (firstHalf != NULL && secondHalf == NULL) {
list->nextPtr_ = firstHalf;
end->nextPtr_ = firstHalf;
firstHalf = firstHalf->nextPtr_;
end = end->nextPtr_;
}
while (firstHalf == NULL && secondHalf != NULL) {
list->nextPtr_ = secondHalf;
end->nextPtr_ = secondHalf;
secondHalf = secondHalf->nextPtr_;
end = end->nextPtr_;
}
return (list);
}
// PURPOSE: To do nothing if 'list' is NULL. Otherwise to 'free()' both
// 'nextPtr_' and 'namePtr_' for 'list', and all of 'nextPtr_' successors.
// No return value.
void release(struct Node *list) {
if (list == NULL)
return;
release(list->nextPtr_);
free(list);
}
// PURPOSE: To create, print, and 'free()' a linked list of the 'argc-1'
// items on 'argv[]', from 'argv[1]' to 'argv[argc-1]'. Returns
// 'EXIT_SUCCESS' to OS.
int main(int argc, char *argv[]) {
// I.
// II. :
struct Node *list;
list = makeList();
printf("Before sort:\n");
print(list);
list = sort(list);
printf("After sort:\n");
print(list);
release(list);
// III. Finished:
return (EXIT_SUCCESS);
}
程序要求用户输入，然后在排序和显示之前显示用户输入
预期输出应该是
$ ./mergeSort
Integer (or quit) to quit: 9
Integer (or quit) to quit: 8
Integer (or quit) to quit: 7
Integer (or quit) to quit: 1
Integer (or quit) to quit: 2
Integer (or quit) to quit: 3
Integer (or quit) to quit: 6
Integer (or quit) to quit: 4
Integer (or quit) to quit: 5
Integer (or quit) to quit: quit
Before sort:
9
8
7
1
2
3
6
4
5
After sort:
1
2
3
4
5
6
7
8
9
修复这些错误是否会得到预期的结果？如果不是，我可以做些什么来生成相同的输出？
我不知道我的做法是否正确。任何帮助将不胜感激。
现在修复了一些错误。我明白了
Integer (or quit) to quit: 1
Integer (or quit) to quit: 2
Integer (or quit) to quit: 3
Integer (or quit) to quit: 4
Integer (or quit) to quit: 5
Integer (or quit) to quit: 6
Integer (or quit) to quit: 7
Integer (or quit) to quit: 8
Integer (or quit) to quit: 9
Integer (or quit) to quit: quit
Before sort:
1
2
3
4
5
6
7
8
9
After sort:
8
9
为什么不对所有输入开始进行排序？
您的代码中存在一些问题：
在 makelist() 中，您应该检查 fgets() 的 return 值以避免文件意外结束时的无限循环。
您还应该检查 malloc() 失败以避免未定义的行为。
您的 release() 实现递归的层次数与列表中的节点数一样多。任何足够长的列表都会导致 堆栈溢出 。最好使用非递归版本。
拆分列表的循环不正确：full 跳过速度不是 half 的两倍。
你应该这样修改：
full = list;
half = list;
while (full != NULL) {
full = full->nextPtr_;
if (full != NULL) {
prevHalf = half;
half = half->nextPtr_;
full = full->nextPtr_;
}
}
比较节点值时，必须使用<=而不是&:
if (firstHalf->value_ <= secondHalf->value_)
在主合并循环中，你不应该修改list->nextPtr_，只修改end->nextPtr_。
最后的合并循环没有用。您应该根据哪个列表为空将 end->nextPtr_ 设置为 leftHalf 或 rightHalf。
这是一个正确的版本：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// PURPOSE:
const int LINE_LEN = 256;
#define STOP_CMD "quit"
const int STOP_CMD_LEN = sizeof(STOP_CMD) - 1;
// PURPOSE: To hold a node in a linked list of integers.
struct Node {
int value_;
struct Node *nextPtr_;
};
// PURPOSE: To create and return a linked list of integer pairs.
struct Node *makeList(void) {
struct Node *list = NULL;
struct Node *end = NULL;
struct Node *next;
int value;
char line[LINE_LEN];
while (1) {
printf("Integer (or %s) to quit: ", STOP_CMD);
if (!fgets(line, LINE_LEN, stdin))
break;
if (strncmp(line, STOP_CMD, STOP_CMD_LEN) == 0)
break;
value = strtol(line, NULL, 10);
next = (struct Node *)malloc(sizeof(struct Node));
if (next == NULL) {
fprintf(stderr, "out of memory\n");
exit(EXIT_FAILURE);
}
next->value_ = value;
next->nextPtr_ = NULL;
if (list == NULL) {
list = next;
} else {
end->nextPtr_ = next;
}
end = next;
}
return list;
}
// PURPOSE: To print the 'value_' values found in 'list'. No return value.
void print(const struct Node *list) {
const struct Node *run;
for (run = list; run != NULL; run = run->nextPtr_)
printf("%d\n", run->value_);
}
// PURPOSE: To sort the items in 'list' in ascending order according to
// their value for 'value_'. Returns sorted list.
struct Node *sort(struct Node *list) {
// Merge-sort is recursive, so there is/are base case(s):
// For merge-sort, the base cases are when 'list' has either 0 or 1
// node it it. If 'list' points to either 0 or 1 thing then return 'list':
// YOUR CODE HERE
if (list == NULL || list->nextPtr_ == NULL) {
return list;
}
// This is the beginning of the recursive case.
// We have to split 'list' into two lists of approximately the same length.
// A straight-forward way to do that is with loop and 3 pointer variables:
// (*) 'full' races through the list starting at 'list' 2 nodes at a time.
// The loop should stop when either 'full' lands on 'NULL', or the
// next of 'full' is 'NULL'.
// (*) 'half' starts at 'list' but goes through at 1/2 the speed by only
// getting the next (not the next-next like 'full'). When 'full'
// reaches the end then 'half' will point to the *beginning* of the
// second list. We need this node, but we *also* need the one just
// before 'half'. So that is why there is also . . .
// (*) 'prevHalf', whose job is to take the value 'half' just had.
// Just before advancing 'half' to its next, give 'prevHalf' the old
// value of 'half'.
struct Node *full;
struct Node *half;
struct Node *prevHalf = list;
// YOUR CODE HERE
full = list;
half = list;
while (full != NULL) {
full = full->nextPtr_;
if (full != NULL) {
prevHalf = half;
half = half->nextPtr_;
full = full->nextPtr_;
}
}
// Here we separate both sublists:
prevHalf->nextPtr_ = NULL;
// Here we recursively sort both sublists:
struct Node *firstHalf = sort(list);
struct Node *secondHalf = sort(half);
struct Node *end = NULL;
// Here we merge the lists pointed to by 'firstHalf' and 'secondHalf'.
// Make 'list' point to the beginning of the combined list, and use 'end'
// to keep track of the end.
// Use a loop to while both 'firstHalf' and 'secondHalf' are both not yet
// at the end of their lists, then compare the values that both point to.
// If 'firstHalf' points to the lower value then put it at the end of the
// combined list. Else put 'secondHalf' at the end.
// You do not have to remove the node from the old list, but you *do* have
// to advance which ever pointer you used (either 'firstHalf' or
// 'secondHalf') to point to the next node in the list.
// When either 'firstHalf' or 'secondHalf' are 'NULL' then quit the loop:
list = NULL;
// YOUR CODE HERE
if (firstHalf->value_ <= secondHalf->value_) {
list = firstHalf;
end = firstHalf;
firstHalf = firstHalf->nextPtr_;
} else {
list = secondHalf;
end = secondHalf;
secondHalf = secondHalf->nextPtr_;
}
while ((firstHalf != NULL) && (secondHalf != NULL)) {
if (firstHalf->value_ <= secondHalf->value_) {
end->nextPtr_ = firstHalf;
end = end->nextPtr_;
firstHalf = firstHalf->nextPtr_;
} else {
end->nextPtr_ = secondHalf;
end = end->nextPtr_;
secondHalf = secondHalf->nextPtr_;
}
}
// Almost finished!
// You made it to the end of one list, but there still is the other one.
// Make the node pointed to by 'end' point to which ever list that you did
// *not* go all the way through.
// YOUR CODE HERE
if (firstHalf != NULL) {
end->nextPtr_ = firstHalf;
} else {
end->nextPtr_ = secondHalf;
}
return list;
}
// PURPOSE: To do nothing if 'list' is NULL. Otherwise to 'free()' both
// 'nextPtr_' and 'namePtr_' for 'list', and all of 'nextPtr_' successors.
// No return value.
void release(struct Node *list) {
while (list != NULL) {
struct Node *next = list->nextPtr_;
free(list);
list = next;
}
}
// PURPOSE: To create, print, and 'free()' a linked list of the 'argc-1'
// items on 'argv[]', from 'argv[1]' to 'argv[argc-1]'. Returns
// 'EXIT_SUCCESS' to OS.
int main(int argc, char *argv[]) {
// I.
// II. :
struct Node *list;
list = makeList();
printf("Before sort:\n");
print(list);
list = sort(list);
printf("After sort:\n");
print(list);
release(list);
// III. Finished:
return EXIT_SUCCESS;
}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// PURPOSE:
const int LINE_LEN = 256;
#define STOP_CMD "quit"
const int STOP_CMD_LEN = sizeof(STOP_CMD) - 1;
// PURPOSE: To hold a node in a linked list of integers.
struct Node {
int value_;
struct Node *nextPtr_;
};
// PURPOSE: To create and return a linked list of integer pairs.
struct Node *makeList() {
struct Node *list = NULL;
struct Node *end = NULL;
struct Node *next;
int value;
char line[LINE_LEN];
while (1) {
printf("Integer (or %s) to quit: ", STOP_CMD);
fgets(line, LINE_LEN, stdin);
if (strncmp(line, STOP_CMD, STOP_CMD_LEN) == 0)
break;
value = strtol(line,NULL,10);
next = (struct Node *)malloc(sizeof(struct Node));
if (list == NULL) {
list = next;
} else {
end->nextPtr_ = next;
}
end = next;
next->value_ = value;
next->nextPtr_ = NULL;
}
return (list);
}
// PURPOSE: To print the 'value_' values found in 'list'. No return value.
void print(const struct Node *list) {
const struct Node *run;
for (run = list; run != NULL; run = run->nextPtr_)
printf("%d\n", run->value_);
}
// PURPOSE: To sort the items in 'list' in ascending order according to
// their value for 'value_'. Returns sorted list.
struct Node *sort(struct Node *list) {
// Merge-sort is recursive, so there is/are base case(s):
// For merge-sort, the base cases are when 'list' has either 0 or 1
// node it it. If 'list' points to either 0 or 1 thing then return 'list':
// YOUR CODE HERE
if (list == NULL || list->nextPtr_ == NULL) {
return list;
}
// This is the beginning of the recursive case.
// We have to split 'list' into two lists of approximately the same length.
// A straight-forward way to do that is with loop and 3 pointer variables:
// (*) 'full' races through the list starting at 'list' 2 nodes at a time.
// The loop should stop when either 'full' lands on 'NULL', or the
// next of 'full' is 'NULL'.
// (*) 'half' starts at 'list' but goes through at 1/2 the speed by only
// getting the next (not the next-next like 'full'). When 'full'
// reaches the end then 'half' will point to the *beginning* of the
// second list. We need this node, but we *also* need the one just
// before 'half'. So that is why there is also . . .
// (*) 'prevHalf', whose job is to take the value 'half' just had.
// Just before advancing 'half' to its next, give 'prevHalf' the old
// value of 'half'.
struct Node *full;
struct Node *half;
struct Node *prevHalf = NULL;
// YOUR CODE HERE
full = list;
half = list;
while (full != NULL) {
full = full->nextPtr_;
if (full != NULL){
prevHalf = half;
half = half->nextPtr_;
}
}
// Here we separate both sublists:
prevHalf->nextPtr_ = NULL;
// Here we recursively sort both sublists:
struct Node *firstHalf = sort(list);
struct Node *secondHalf = sort(half);
struct Node *end = NULL;
// Here we merge the lists pointed to by 'firstHalf' and 'secondHalf'.
// Make 'list' point to the beginning of the combined list, and use 'end'
// to keep track of the end.
// Use a loop to while both 'firstHalf' and 'secondHalf' are both not yet
// at the end of their lists, then compare the values that both point to.
// If 'firstHalf' points to the lower value then put it at the end of the
// combined list. Else put 'secondHalf' at the end.
// You do not have to remove the node from the old list, but you *do* have
// to advance which ever pointer you used (either 'firstHalf' or
// 'secondHalf') to point to the next node in the list.
// When either 'firstHalf' or 'secondHalf' are 'NULL' then quit the loop:
list = NULL;
// YOUR CODE HERE
// if (firstHalf value_->secondHalf->value_) {
if (firstHalf->value_ & secondHalf->value_) {
list = firstHalf;
end = firstHalf;
firstHalf = firstHalf->nextPtr_;
} else {
list = secondHalf;
end = secondHalf;
secondHalf = secondHalf->nextPtr_;
}
while ((firstHalf != NULL) && (secondHalf != NULL)) {
if (firstHalf->value_ & secondHalf->value_) {
list->nextPtr_ = firstHalf;
end->nextPtr_ = firstHalf;
firstHalf = firstHalf->nextPtr_;
end = end->nextPtr_;
} else {
list->nextPtr_ = secondHalf;
end->nextPtr_ = secondHalf;
secondHalf = secondHalf->nextPtr_;
end = end->nextPtr_;
}
}
// Almost finished!
// You made it to the end of one list, but there still is the other one.
// Make the node pointed to by 'end' point to which ever list that you did
// *not* go all the way through.
// YOUR CODE HERE
while (firstHalf != NULL && secondHalf == NULL) {
list->nextPtr_ = firstHalf;
end->nextPtr_ = firstHalf;
firstHalf = firstHalf->nextPtr_;
end = end->nextPtr_;
}
while (firstHalf == NULL && secondHalf != NULL) {
list->nextPtr_ = secondHalf;
end->nextPtr_ = secondHalf;
secondHalf = secondHalf->nextPtr_;
end = end->nextPtr_;
}
return (list);
}
// PURPOSE: To do nothing if 'list' is NULL. Otherwise to 'free()' both
// 'nextPtr_' and 'namePtr_' for 'list', and all of 'nextPtr_' successors.
// No return value.
void release(struct Node *list) {
if (list == NULL)
return;
release(list->nextPtr_);
free(list);
}
// PURPOSE: To create, print, and 'free()' a linked list of the 'argc-1'
// items on 'argv[]', from 'argv[1]' to 'argv[argc-1]'. Returns
// 'EXIT_SUCCESS' to OS.
int main(int argc, char *argv[]) {
// I.
// II. :
struct Node *list;
list = makeList();
printf("Before sort:\n");
print(list);
list = sort(list);
printf("After sort:\n");
print(list);
release(list);
// III. Finished:
return (EXIT_SUCCESS);
}
程序要求用户输入，然后在排序和显示之前显示用户输入 预期输出应该是
$ ./mergeSort
Integer (or quit) to quit: 9
Integer (or quit) to quit: 8
Integer (or quit) to quit: 7
Integer (or quit) to quit: 1
Integer (or quit) to quit: 2
Integer (or quit) to quit: 3
Integer (or quit) to quit: 6
Integer (or quit) to quit: 4
Integer (or quit) to quit: 5
Integer (or quit) to quit: quit
Before sort:
9
8
7
1
2
3
6
4
5
After sort:
1
2
3
4
5
6
7
8
9
修复这些错误是否会得到预期的结果？如果不是，我可以做些什么来生成相同的输出？ 我不知道我的做法是否正确。任何帮助将不胜感激。
现在修复了一些错误。我明白了
Integer (or quit) to quit: 1
Integer (or quit) to quit: 2
Integer (or quit) to quit: 3
Integer (or quit) to quit: 4
Integer (or quit) to quit: 5
Integer (or quit) to quit: 6
Integer (or quit) to quit: 7
Integer (or quit) to quit: 8
Integer (or quit) to quit: 9
Integer (or quit) to quit: quit
Before sort:
1
2
3
4
5
6
7
8
9
After sort:
8
9
为什么不对所有输入开始进行排序？
您的代码中存在一些问题：
在
makelist()中，您应该检查fgets()的 return 值以避免文件意外结束时的无限循环。您还应该检查
malloc()失败以避免未定义的行为。您的
release()实现递归的层次数与列表中的节点数一样多。任何足够长的列表都会导致 堆栈溢出 。最好使用非递归版本。拆分列表的循环不正确：
full跳过速度不是half的两倍。 你应该这样修改：full = list; half = list; while (full != NULL) { full = full->nextPtr_; if (full != NULL) { prevHalf = half; half = half->nextPtr_; full = full->nextPtr_; } }比较节点值时，必须使用
<=而不是&:if (firstHalf->value_ <= secondHalf->value_)在主合并循环中，你不应该修改
list->nextPtr_，只修改end->nextPtr_。最后的合并循环没有用。您应该根据哪个列表为空将
end->nextPtr_设置为leftHalf或rightHalf。
这是一个正确的版本：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// PURPOSE:
const int LINE_LEN = 256;
#define STOP_CMD "quit"
const int STOP_CMD_LEN = sizeof(STOP_CMD) - 1;
// PURPOSE: To hold a node in a linked list of integers.
struct Node {
int value_;
struct Node *nextPtr_;
};
// PURPOSE: To create and return a linked list of integer pairs.
struct Node *makeList(void) {
struct Node *list = NULL;
struct Node *end = NULL;
struct Node *next;
int value;
char line[LINE_LEN];
while (1) {
printf("Integer (or %s) to quit: ", STOP_CMD);
if (!fgets(line, LINE_LEN, stdin))
break;
if (strncmp(line, STOP_CMD, STOP_CMD_LEN) == 0)
break;
value = strtol(line, NULL, 10);
next = (struct Node *)malloc(sizeof(struct Node));
if (next == NULL) {
fprintf(stderr, "out of memory\n");
exit(EXIT_FAILURE);
}
next->value_ = value;
next->nextPtr_ = NULL;
if (list == NULL) {
list = next;
} else {
end->nextPtr_ = next;
}
end = next;
}
return list;
}
// PURPOSE: To print the 'value_' values found in 'list'. No return value.
void print(const struct Node *list) {
const struct Node *run;
for (run = list; run != NULL; run = run->nextPtr_)
printf("%d\n", run->value_);
}
// PURPOSE: To sort the items in 'list' in ascending order according to
// their value for 'value_'. Returns sorted list.
struct Node *sort(struct Node *list) {
// Merge-sort is recursive, so there is/are base case(s):
// For merge-sort, the base cases are when 'list' has either 0 or 1
// node it it. If 'list' points to either 0 or 1 thing then return 'list':
// YOUR CODE HERE
if (list == NULL || list->nextPtr_ == NULL) {
return list;
}
// This is the beginning of the recursive case.
// We have to split 'list' into two lists of approximately the same length.
// A straight-forward way to do that is with loop and 3 pointer variables:
// (*) 'full' races through the list starting at 'list' 2 nodes at a time.
// The loop should stop when either 'full' lands on 'NULL', or the
// next of 'full' is 'NULL'.
// (*) 'half' starts at 'list' but goes through at 1/2 the speed by only
// getting the next (not the next-next like 'full'). When 'full'
// reaches the end then 'half' will point to the *beginning* of the
// second list. We need this node, but we *also* need the one just
// before 'half'. So that is why there is also . . .
// (*) 'prevHalf', whose job is to take the value 'half' just had.
// Just before advancing 'half' to its next, give 'prevHalf' the old
// value of 'half'.
struct Node *full;
struct Node *half;
struct Node *prevHalf = list;
// YOUR CODE HERE
full = list;
half = list;
while (full != NULL) {
full = full->nextPtr_;
if (full != NULL) {
prevHalf = half;
half = half->nextPtr_;
full = full->nextPtr_;
}
}
// Here we separate both sublists:
prevHalf->nextPtr_ = NULL;
// Here we recursively sort both sublists:
struct Node *firstHalf = sort(list);
struct Node *secondHalf = sort(half);
struct Node *end = NULL;
// Here we merge the lists pointed to by 'firstHalf' and 'secondHalf'.
// Make 'list' point to the beginning of the combined list, and use 'end'
// to keep track of the end.
// Use a loop to while both 'firstHalf' and 'secondHalf' are both not yet
// at the end of their lists, then compare the values that both point to.
// If 'firstHalf' points to the lower value then put it at the end of the
// combined list. Else put 'secondHalf' at the end.
// You do not have to remove the node from the old list, but you *do* have
// to advance which ever pointer you used (either 'firstHalf' or
// 'secondHalf') to point to the next node in the list.
// When either 'firstHalf' or 'secondHalf' are 'NULL' then quit the loop:
list = NULL;
// YOUR CODE HERE
if (firstHalf->value_ <= secondHalf->value_) {
list = firstHalf;
end = firstHalf;
firstHalf = firstHalf->nextPtr_;
} else {
list = secondHalf;
end = secondHalf;
secondHalf = secondHalf->nextPtr_;
}
while ((firstHalf != NULL) && (secondHalf != NULL)) {
if (firstHalf->value_ <= secondHalf->value_) {
end->nextPtr_ = firstHalf;
end = end->nextPtr_;
firstHalf = firstHalf->nextPtr_;
} else {
end->nextPtr_ = secondHalf;
end = end->nextPtr_;
secondHalf = secondHalf->nextPtr_;
}
}
// Almost finished!
// You made it to the end of one list, but there still is the other one.
// Make the node pointed to by 'end' point to which ever list that you did
// *not* go all the way through.
// YOUR CODE HERE
if (firstHalf != NULL) {
end->nextPtr_ = firstHalf;
} else {
end->nextPtr_ = secondHalf;
}
return list;
}
// PURPOSE: To do nothing if 'list' is NULL. Otherwise to 'free()' both
// 'nextPtr_' and 'namePtr_' for 'list', and all of 'nextPtr_' successors.
// No return value.
void release(struct Node *list) {
while (list != NULL) {
struct Node *next = list->nextPtr_;
free(list);
list = next;
}
}
// PURPOSE: To create, print, and 'free()' a linked list of the 'argc-1'
// items on 'argv[]', from 'argv[1]' to 'argv[argc-1]'. Returns
// 'EXIT_SUCCESS' to OS.
int main(int argc, char *argv[]) {
// I.
// II. :
struct Node *list;
list = makeList();
printf("Before sort:\n");
print(list);
list = sort(list);
printf("After sort:\n");
print(list);
release(list);
// III. Finished:
return EXIT_SUCCESS;
}