程序要求在双向链表上实现快速排序的递归算法

1、一、程序要求：在双向链表上实现快速排序的递归算法。二、程序主体/在双向链表上实现快速排序的递归算法。#include<iostream.h>struct doulinklisttp int key; doulinklisttp *pre; doulinklisttp *next;void initiate(doulinklisttp &dulist)/初始化链表 dulist.next=NULL; dulist.pre=NULL;void create(doulinklisttp &dulist)/建立链表 int n;doulinklisttp *p1,*p2;c

2、out<<"please input some numbersn"<<"ended the number list with "-1"n"cin>>n; p1=new doulinklisttp;/读入第一个数，建立头结点p1->key=n;dulist.next=p1;p1->pre=NULL; cin>>n;while (n>=0) /读入剩下的数字，建立完整的链表 p2=new doulinklisttp; p2->key=n;p2->pre=p1;p

3、2->next=NULL;p1->next=p2;p1=p1->next;cin>>n; ;void search(doulinklisttp dulist,doulinklisttp *&l,doulinklisttp *&h)/查找新建链表的第一个结点和尾结点 l=dulist.next; h=dulist.next; while (h->next!=NULL) h=h->next;void quickpass(doulinklisttp *l,doulinklisttp *h,doulinklisttp *&i)/对链表进

4、行第一趟排序 doulinklisttp *j; int p; i=l; j=h; p=i->key; while (i!=j) /当当前数大于枢轴记录关键字，指针向前移 while (i!=j)&&(j->key>=p) j=j->pre; if (j->key<p) i->key=j->key; /当当前数小于枢轴记录关键字，前移当前关键字/当当前数小于枢轴记录关键字，指针向后移while (i!=j)&&(i->key<=p) i=i->next; if (i->key>p) j

5、->key=i->key; /当当前数大于枢轴记录关键字，后移当前关键字 i->key=p;void quicksort(doulinklisttp *l,doulinklisttp *h,doulinklisttp *&i)/对整个链表第归排序 doulinklisttp *t2; if (l!=h) quickpass(l,h,i); if (i!=l) quicksort(l,i->pre,t2); if (i!=h) quicksort(i->next,h,t2); void write(doulinklisttp dulist)doulinklisttp *w2;w2=dulist.next;while(w2!=NULL)cout<<w2->key<<" " w2=w2->next;cout<<endl;void main() doulinklisttp doulist,*low,*high,*q; initiate(doulist); create(doulist); cout<<"the input number list isn" write(doulist); search(doulist,low,high); qu