我嘗試使用冒泡排序演算法對鏈表進行排序，但最后一個節點似乎未在串列中排序。串列中的每個元素都可以排序，但最后一個除外。誰能建議我哪里做錯了以及如何解決？非常感謝！（抱歉英語不好），這是我的代碼：
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->
uj5u.com熱心網友回復：
首先，
j->next將是0如果j是在串列的最后一個元素。所以j會跳過最后一個元素。
其次，如果您讓j迭代從i到串列的末尾并i每次都增加，您將跳過元素。您需要將終點向左移動（也就是減少結束索引）而不是向右移動起點（也就是增加開始索引）。
編輯：要明白我的意思，你可能想簽這出
這很難做到，因為您的串列是由指向下一個元素的指標組成的，而不是反向的。但絕對可以通過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);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/363468.html
上一篇：添加到位元組而不會溢位
下一篇：就地重新排序簡單的二維矩陣