程序要求在雙向鏈表上實現(xiàn)快速排序的遞歸算法

1、一、程序要求：在雙向鏈表上實現(xiàn)快速排序的遞歸算法。二、程序主體/在雙向鏈表上實現(xiàn)快速排序的遞歸算法。#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;/讀入第一個數(shù)，建立頭結點p1->key=n;dulist.next=p1;p1->pre=NULL; cin>>n;while (n>=0) /讀入剩下的數(shù)字，建立完整的鏈表 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) /當當前數(shù)大于樞軸記錄關鍵字，指針向前移 while (i!=j)&&(j->key>=p) j=j->pre; if (j->key<p) i->key=j->key; /當當前數(shù)小于樞軸記錄關鍵字，前移當前關鍵字/當當前數(shù)小于樞軸記錄關鍵字，指針向后移while (i!=j)&&(i->key<=p) i=i->next; if (i->key>p) j

5、->key=i->key; /當當前數(shù)大于樞軸記錄關鍵字，后移當前關鍵字 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