链表中的最后一个节点在冒泡排序中不起作用
The last node in linked list not working in Bubble sort
我尝试使用冒泡排序算法对链表进行排序,但最后一个节点似乎没有在列表中排序。列表中的每个元素都可以排序,但最后一个元素除外。谁能建议我哪里做错了以及如何解决?非常感谢!
(抱歉英语不好),这是我的代码:
struct Node{
int data;
Node *next;
};
bool isEmpty(Node *head){
if (head == NULL){
return true;
}
else{
return false;
}
}
void insertAsFirstElement(Node *&head, Node *&last, int number){
Node *temp = new Node;
temp -> data = number;
temp -> next = NULL;
head = temp;
last = temp;
}
void insert(Node *&head, Node *&last, int number){
if (isEmpty(head)){
insertAsFirstElement(head , last , number);
}
else{
Node *temp = new Node;
temp->data = number;
temp->next = NULL;
last->next = temp;
last = temp;
}
}
void BubleSort(Node *&head){
struct Node *i ,*j;
int num;
for (i = head; i-> next != NULL;i=i->next){
for (j = i->next; j->next != NULL; j = j->next){
if (i->data > j-> data){
num = j->data;
j->data = i->data;
i->data = num;
}
}
}
}
void display(Node *current){
if (current == NULL){
cout<<"Nothing to display ";
}
while(current!= NULL){
cout<<current -> data<<"-> ";
current = current -> next;
}
}
int main(){
Node *head = NULL;
Node *last = NULL;
int T;cin>>T;
for (int i=0 ;i<T;i++){
int number;cin>>number;
insert(head,last,number);
}
BubleSort(head);
display(head);
}
输入:
6
1 7 4 6 9 3
输出:
1-> 4-> 6-> 7-> 9-> 3->
首先,
如果 j
是列表中的最后一个元素,j->next
将是 0
。所以 j
将跳过最后一个元素。
其次,如果您让 j
从 i
迭代到列表末尾并每次增加 i
,您将跳过元素。您需要将结束点向左移动(也就是减少结束索引)而不是将起点向右移动(也就是增加开始索引)。
编辑:要明白我的意思,您可能想查看 this
这很难做到,因为您的列表是用指向下一个元素的指针构建的,而不是反向的。但绝对可以通过在到达终点之前停止 j
(取消固定第一个点)并将 i
替换为 j
.
来进行管理
void BubleSort(Node*& head) {
struct Node* i, * j;
//move i to the end
for (i = head; i->next != NULL; i = i->next)
{
}
do {
//loop from the start to i
for (j = head; ; j = j->next) {
//compare the element 'at index' j with the next element ('j + 1')
if (j->data > j->next->data) {
//nice simple function to do swapping, provided by the std library.
std::swap(j->data, j->next->data);
}
if (j->next == i)
{
//move i one to the 'left' aka decrease by it by one aka move it up one step in the recursion
i = j;
break;
}
}
} while (i != head);
}
我尝试使用冒泡排序算法对链表进行排序,但最后一个节点似乎没有在列表中排序。列表中的每个元素都可以排序,但最后一个元素除外。谁能建议我哪里做错了以及如何解决?非常感谢! (抱歉英语不好),这是我的代码:
struct Node{
int data;
Node *next;
};
bool isEmpty(Node *head){
if (head == NULL){
return true;
}
else{
return false;
}
}
void insertAsFirstElement(Node *&head, Node *&last, int number){
Node *temp = new Node;
temp -> data = number;
temp -> next = NULL;
head = temp;
last = temp;
}
void insert(Node *&head, Node *&last, int number){
if (isEmpty(head)){
insertAsFirstElement(head , last , number);
}
else{
Node *temp = new Node;
temp->data = number;
temp->next = NULL;
last->next = temp;
last = temp;
}
}
void BubleSort(Node *&head){
struct Node *i ,*j;
int num;
for (i = head; i-> next != NULL;i=i->next){
for (j = i->next; j->next != NULL; j = j->next){
if (i->data > j-> data){
num = j->data;
j->data = i->data;
i->data = num;
}
}
}
}
void display(Node *current){
if (current == NULL){
cout<<"Nothing to display ";
}
while(current!= NULL){
cout<<current -> data<<"-> ";
current = current -> next;
}
}
int main(){
Node *head = NULL;
Node *last = NULL;
int T;cin>>T;
for (int i=0 ;i<T;i++){
int number;cin>>number;
insert(head,last,number);
}
BubleSort(head);
display(head);
}
输入:
6
1 7 4 6 9 3
输出:
1-> 4-> 6-> 7-> 9-> 3->
首先,
如果 j
是列表中的最后一个元素,j->next
将是 0
。所以 j
将跳过最后一个元素。
其次,如果您让 j
从 i
迭代到列表末尾并每次增加 i
,您将跳过元素。您需要将结束点向左移动(也就是减少结束索引)而不是将起点向右移动(也就是增加开始索引)。
编辑:要明白我的意思,您可能想查看 this
这很难做到,因为您的列表是用指向下一个元素的指针构建的,而不是反向的。但绝对可以通过在到达终点之前停止 j
(取消固定第一个点)并将 i
替换为 j
.
void BubleSort(Node*& head) {
struct Node* i, * j;
//move i to the end
for (i = head; i->next != NULL; i = i->next)
{
}
do {
//loop from the start to i
for (j = head; ; j = j->next) {
//compare the element 'at index' j with the next element ('j + 1')
if (j->data > j->next->data) {
//nice simple function to do swapping, provided by the std library.
std::swap(j->data, j->next->data);
}
if (j->next == i)
{
//move i one to the 'left' aka decrease by it by one aka move it up one step in the recursion
i = j;
break;
}
}
} while (i != head);
}