用链表将数字升序排序.doc

2问题分析：将链表中的元素进行升序排序，再用查找找出排在最后的一位输出该元素值算法描述：Step1 p 为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到step5直至最后一个结点Step8输出最后一个链表的元素值源程序：#include/cout,cin#includeprocess.h/exit()#define Max 20typedef struct int exp;PolyArrayMax;struct PolyNode int exp; PolyNode *next;class Polyprivate:public:PolyNode *head;Poly();/构造函数，建立空链表Poly();/析构函数，释放链表void Create(PolyArray a,int n);/键盘输入，创建数值链表void Disp();/多项式显示void Sort();/有序表排序int GetMax();Poly:Poly() /创建一空链表head=new PolyNode;head-next=NULL;Poly:Poly()/释放链表所占空间PolyNode *p;while(head!=NULL)/从头结点开始，依次释放结点p=head;head=head-next; delete p;head=NULL;/头结点指向空void Poly:Disp ()PolyNode *p;p=head-next;while(p!=NULL)coutexpnext ;coutendl;void Poly:Create (PolyArray a,int n)/由数值数组创建链表PolyNode *s,*r;int i;r=head;for(i=0;iexp =ai.exp;s-next =NULL;r-next =s;r=s;void Poly:Sort()PolyNode *p,*q,*r;p=head-next ;if(p!=NULL)r=p-next ;/r指向p的后继结点p-next =NULL;/构造只有一个结点的有序表p=r;while(p!=NULL)r=p-next;q=head;while(q-next!=NULL & q-next -exp exp )q=q-next ;/在有序表中插入*p的前驱结点*qp-next =q-next ;/*p插入到*q之后q-next =p;p=r;int Poly:GetMax()PolyNode *p;p=head;while(p-next!=NULL)p=p-next;return p-exp;void main()Poly LA; PolyNode *p; int x;/p1=LA.head; PolyArray a=0,7,6,0;LA.Create (a,4);cout原数值表A为：;LA.Disp ();cout有序数值表A为：;LA.Sort();L