用链表将数字升序排序

《用链表将数字升序排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2问题分析：将链表中的元素进行升序排序，再用查找找出排在最后的一位输出该元素值算法描述：Step1p为head后的头结点，r指向p的后继结点Step2构造只有一个结点的有序表即将p结点与r结点断开Step3p后移到r，如果p不为空链表，r后移一个，将设置为头指针Step4当q后面不为空链表并且q所指结点中的数小于p结点中的数时，q由头指针指向第一个结点，否则执行step7Step5p结点与后面结点断开，q结点与p结点相链接，p指针指到r位置Step6重复step3到step5直至最后一个结点Step7将p所指结点插到head后面，重复step3

2、到step5直至最后一个结点Step8输出最后一个链表的元素值源程序：#include//cout,cin#include"process.h"//exit()#defineMax20typedefstruct{intexp;}PolyArray[Max];structPolyNode{intexp;PolyNode*next;};classPoly{private:public:PolyNode*head;Poly();//构造函数，建立空链表~Poly();//析构函数，释放链表voidCreate(PolyArra

3、ya,intn);//键盘输入，创建数值链表voidDisp();//多项式显示voidSort();//有序表排序intGetMax();};Poly::Poly(){//创建一空链表head=newPolyNode;head->next=NULL;}Poly::~Poly(){//释放链表所占空间PolyNode*p;while(head!=NULL){//从头结点开始，依次释放结点p=head;head=head->next;deletep;}head=NULL;//头结点指向空}voidPoly::Disp(){PolyNode*p;p

4、=head->next;while(p!=NULL){cout<exp<<'t';p=p->next;}cout<exp=a[i].exp;s->next=NULL;r->next=s;r=s;}}voidPoly::Sort(){PolyNode*p,*q,*r;p=head->next;if(p!=NULL){

5、r=p->next;//r指向p的后继结点p->next=NULL;//构造只有一个结点的有序表p=r;while(p!=NULL){r=p->next;q=head;while(q->next!=NULL&&q->next->expexp)q=q->next;//在有序表中插入*p的前驱结点*qp->next=q->next;//*p插入到*q之后q->next=p;p=r;}}}intPoly::GetMax(){PolyNode*p;p=head;while(p->next!=NULL){p=p->next;}returnp->e

6、xp;}voidmain(){PolyLA;PolyNode*p;intx;//p1=LA.head;PolyArraya={{0},{7},{6},{0}};LA.Create(a,4);cout<<"原数值表A为：";LA.Disp();cout<<"有序数值表A为：";LA.Sort();LA.Disp();x=LA.GetMax();cout<<"最大元素为"<next;deletep;}运行截

7、图：网络工程102沈清1013072058