首页 > 代码库 > 数组排序 链表

数组排序 链表

2024-07-13 03:24:29   228人阅读

/*主要思路；

用一个链表存储数组信息，然后依次找出这个链表中最小的数字，然后插入到另外一个链表中，并删除原来链表中最小数字这个节点，一共循环n次，然后另外一个链表中的数字就是排序好的数组，依次输出即可；

*/


#include<iostream>

using namespace std;
#include<cstdlib>
class Node                                  //定义类，结构体也可以，存储每个节点的信息和下一个节点的地址；
{
public :
int a;
Node *next;
};
int main()
{
Node *first1,*p,*first2,*r;
int i,n,x[1000];
cin>>n;                                                  //输入要排序的数字个数
for(i=0;i<n;i++)
cin>>x[i];                                      //输入要排序的n个数
first1=new Node();
first2=new Node();
r=first1;
for(i=0;i<n;i++)
{
p=new Node();                      //用尾插法把一个数组中的元素插入到这个链表中。本来可以直接把数组中的最小值依次插入链表，但是这样就没有意义了，所以，故意用                                                                  //两个链表来完成排序
p->a=x[i];
r->next=p;
r=p;
}
r->next=NULL;
r=new Node();
r=first2;
Node *q,*w,*e;
for(i=0;i<n;i++)
{
p=new Node();
p=first1;
q=new Node();
w=new Node();
int min=p->next->a;
while(p->next!=NULL)
{
if((p->next->a)<=min)           //找出最小值
{
min=p->next->a;
q=p;
   w=p->next;
}
p=p->next;
}
e=new Node();
e->a=min;
r->next=e;
r=e;                                              //用尾插法将最小值依次插入到另外一个数组中。
q->next=w->next;                      //删除原来链表中的这个最小值
delete w;
}
r->next=NULL;
p=new Node();
p=first2;
while(p->next!=NULL)                 //依次输出排序好了的数组元素
{
cout<<p->next->a<<" ";
p=p->next;
}

cout<<endl;

        system("pause");

}

数组排序 链表


联系
我们