C++单向链表冒泡排序

struct student { long num; float score; student *next; }; 最好有详细讲解

2025-03-07 05:19:57

推荐回答（5个）

回答（1）：

template
class ChainNode{
friend Chain;
template friend ostream& operator<<(ostream& os, const Chain& c);
private:
T data;
ChainNode* link;
};

template
class Chain{
friend ChainIterator;
private:
ChainNode* first;
bool Bubble(ChainNode* current); // 递归函数，从链表的最后一对数开始冒泡至current
pubilc:
void InsertionSort(); //插入算法对链表进行升序排序，不得创建新结点和删除老结点
void BubbleSort(); // 冒泡排序
void SelectionSort(); // 选择排序
void RankSort(); // 计数排序
};

template
void Chain::InsertionSort() //插入算法对链表进行升序排序，不创建新结点和删除老结点
{

if (first)

for (ChainNode* current = first; current->link;){ // current->link为当前要插入的数据

for (ChainNode* p = first; p->data < current->link->data; p = p->link); // p指向表中第一个大于或等于当前要插入数据的数据
if (p == current->link){ // 表中没有比current->link大的数据
current = current->link;
continue; // 继续下一个数据插入
}
if (p!= current){ // 将要插入的数据挪到第一个比它大的数后面
ChainNode* n = current->link->link;
current->link->link = p->link;
p->link = current->link;
current->link = n;
}
else
current = current->link; // 如果已经在第一个比他大的数后面了，更新current->link
T x = p->link->data; //交换要插入元素和他前面那个比它大的元素
p->link->data = p->data;
p->data = x;

}

}
// 问题1：插入排序对于已排好序的链表仍需检验n(n - 1)次，能否及时终止插入排序？

template
bool Chain::Bubble(ChainNode* current) // 递归函数，从链表的最后一对数开始冒泡至current
{
bool sorted = true; // 如果链表已排好序（未发生交换），返回true
if (current && current->link && current->link->link)
sorted = Bubble(current->link);
if (current->data > current->link->data){
T temp = current->data;
current->data = current->link->data;
current->link->data = temp;
sorted = false;
}
return sorted;
}

template
void Chain::BubbleSort() // 冒泡排序
{
bool sorted = false;
for (ChainNode* start = first; start && start->link && !sorted; start = start->link)
sorted = Bubble(start);
}
问题2：不使用递归函数能否以同样的检索次数排序？

template
void Chain::SelectionSort() // 选择排序
{
bool sorted = false;
for (ChainNode* start = first; start && start->link && !sorted; start = start->link){
sorted = true;
for (ChainNode* current = start->link; current; current = current->link){
if (current->data < start->data){ // 交换
T temp = current->data;
current->data = start->data;
start->data = temp;
}
if (sorted && current->link &¤t->data > current->link->data) // 如果在链表中存在比后一项大的项，则表示未排序
sorted = false;
}
}
}

回答（2）：

public void paixu(int a[]){ //首先传入一个数组
Linlist l=new Linlist();
for(int i=0;il.insert(i,new Integer（a[i]）);//用循环调用插入函数插入连表中
//此处添加冒泡法排序代码 //然后再用冒牌法排序
//此处为输出函数代码 //最后再用一个循环输入数组

先实现链表的operator[],再调用
Srot(list,list.Lenght());
template
void Sort(T& arrays[],int const& total)
{
int k=n-1;
for(int i=0;i<(n-1);++i)
{
for(int j=0;j{
if(arrays[j]>arrays[j+1])
{
swap(arrays[j],arrays[j+1]);
}
k--;
}
}
}

回答（3）：

#include
using namespace std;
#define NULL 0

struct student
{
int banji;
student *next;
};

int n;

int main()
{
student *creat(void);
void print(student *);

student *paixu(student *);

student *head;

cout<<"input records:"<head=creat(); //返回头指针
print(head);
head = paixu(head);

print(head);

return 0;
}

student *creat(void)
{
student *head;
student *p1,*p2;
n=0;
p1=p2=new student;
cin>>p1->banji;

head=NULL;
while(p1->banji!=0)
{
n=n+1;
if(n==1) head=p1;
else p2->next=p1;
p2=p1;
p1=new student;
cin>>p1->banji;

}
p2->next=NULL;
return(head);
}

void print(student *head) //输出链表的函数
{
student *p;
cout<<"Now，These "<p=head;
if(head!=NULL)
do
{
cout<banji;
cout<p=p->next;
}while(p!=NULL);
}

student *paixu(student *head)
{
student *q,*tail,*p=(student*)malloc(sizeof(student)),*temp;
p->next=head;
head=p;
tail = NULL;

while(tail!=head->next)
{
p=head;
q=p->next;
while(q->next!=tail)
{
if (p->next->banji > q->next->banji)
{
temp = q->next->next;
p->next=q->next;
p->next->next = q;
q->next = temp;
}
p=p->next;
q=p->next;

}
tail=q;
}
p=head->next;
free(head);
return p;
}

回答（4）：

for(i=0;i<+9;i++)
for(j=i+1;j<9;j++)
if(a[j-1]>=a[j])
{b=a[j-1];a[j-1]=a[j];a[j]=b;}

回答（5）：

你给的结构是按什么排序的？结构里不是有两个值吗？ -。-# 说清楚才能给你编。

最新问答

女娲补天的问题有哪些

大家帮我想想关于横店旅游的广告语啊

高考志愿填报服从调剂是什么意思？什么是服从学校调剂？

如今彩票店前景如何？

梦幻西游普陀装备行云流水符石全身能带几套？

需要一些可爱的繁体QQ签名！！不要爱情的！！

中国海上油田有哪些

dota类单机游戏有哪些类似的？是单机不是网游

上海隽绩实业有限公司怎么样？

大学可以上但录取通知书没发过来又要第二次验兵本人不想当兵怎么办

C++单向链表 冒泡排序

C++单向链表冒泡排序