華東師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)踐報(bào)告（期中）

四、調(diào)試過程

在調(diào)試過程中有些時(shí)候會(huì)出現(xiàn)“typeredefine”的error,不知道到底是為什么，經(jīng)過詢

問同學(xué)，查老師代碼，發(fā)現(xiàn)是include文件是出問題了。最后總結(jié)了一下，凡是.cpp文件都要

include相應(yīng)的.h文件。而.h文件中應(yīng)該include其中會(huì)用到的.h或.cpp文件。例如在

Sortable_List.cpp中就不僅#include"Record.h”,還要加上#include"List.cpp"。而Main.cpp中往

往只用include一個(gè)核心.cpp就可以了，不過還是要“具體情況，具體分析”。

五、總結(jié)

在半學(xué)期的學(xué)習(xí)中，我們學(xué)習(xí)了堆棧、隊(duì)列，并且用數(shù)組和指針分別進(jìn)行實(shí)現(xiàn)，解決了

一些實(shí)際問題，比如說“數(shù)制轉(zhuǎn)換”“多項(xiàng)式的運(yùn)算”等；運(yùn)用這些數(shù)據(jù)結(jié)構(gòu)又和遞歸算法

聯(lián)系在一起，解決了“漢諾塔問題”和“八皇后問題”等；繼而又對(duì)鏈表進(jìn)行了更深意層次

的學(xué)習(xí)，對(duì)其中的操作如插入，刪除，查找，排序又進(jìn)行了更多更深的算法學(xué)習(xí)，例如在排

序方法中涉及到了六種方法：插入法排序、選擇法排序、希爾排序、歸并法排序、快速法排

序以及堆排序。這些學(xué)習(xí)不僅讓我明白和理解了數(shù)據(jù)結(jié)構(gòu)與算法的基本思想、實(shí)現(xiàn)過程，還

讓我知道了在衡量一個(gè)算法是否好時(shí)，要綜合考慮其時(shí)間復(fù)雜度和空間復(fù)雜度，達(dá)到最佳的

狀態(tài)。

六、附錄1：代碼集

1)P53E3:逆序輸出

#include<iostream>

#include<stack>

usingnamespacestd;

voidmain()

/*

Pre:Theusersuppliesanincreasingintegernumbers.

Post:Thenumbersareprintedindecreasingorder.

Uses:TheSTLclassstackanditsmethods

刃

(

intitem;

stack<int>numbers;//declaresandinitializesastackofnumbers

cout?''Typeinanincreasingintegernumbers."?endl

?‘‘Thenumberswillbeprintedindecreasingorder.0?endl;

cin?item;

numbers.push(item);

while(true){

cin?item;

if(item>numbers.top())numbers.push(item);

elsebreak;

}

cout?endl?endl;

while(!numbers.empty()){

cout?numbers.topO?HH;

numbers.popO;

)

cout?endl;

2)編寫ConversionAll

//Convert.h

#include<iostream>

usingnamespacestd;

constintmax=100;

classnewStack{

public:

voidclear();

boolisEmptyO;

voidpush(intel);

voidpop();

inttopEI();

voidprint();

private:

intel;

intlength,count;

intarr[max];

classNumConv:publicnewStack{

public:

voidconvert(intnum,inttoNum);

voidconvertAll(intnum);

private:

intnum;

inttoNum;

}；

//Convert.cpp

#include"Convert.h"

#include<iostream>

usingnamespacestd;

voidnewStack::clear()

(

length=0;

)

boolnewStack::isEmpty()

(

if(length==O)

returntrue;

else

returnfalse;

)

voidnewStack::push(intel)

(

if(length!=max)

(

arr[length]=el;

length++;

else

cout?nFAILTOINSERT!H?endl;

voidnewStack::pop()

(

if(length!=O)

length-;

else

cout?nFAILTODELETE!H?endI;

)

intnewStack::topEl()

(

if(length!=O)

returnarr[length-l];

else

cout?nFAIL!H?endl;

)

voidnewStack::print()

(

if(length!=O)

|

intn;

for(n=0;n<length;n++)

cout?arr[n]?HH;

}

elsecout?TAILTOPRINT!n?endl;

voidNumConv::convert(intnum,inttoNum)

(

inttempi,temp2;

clear();

switch(toNum)

(

case2:

case8:

(

while(num!=0)

templ=num/toNum;

temp2=num%toNum;

push(temp2);

num=templ;

}

while(!isEmpty())

(

cout?topEl();

pop()；

}

//cout?endl;

}

case16:

(

if(num!=0)

(

templ=num/toNum;

temp2=num%toNum;

convert(templ,16);

if(temp2<10)

cout?temp2;

else

(

switch(temp2)

(

case10:cout?,A,;break;

casell:cout?,B,;break;

case12:cout?,C*;break;

case13:cout?,D,;break;

case14:cout?,E,;break;

case15:cout?,F*;break;

elsebreak;

}break;

}

)

voidNumConv::convertAll(intnum)

convert(num,2);

cout?n

convert(num,8);

cout?n

convert(num,16);

//Main.cpp

#include<iostream>

#includenConvert.hH

usingnamespacestd;

voidmain()

(

NumConvnumtonum;

intnuml,numSys;

cout?nPleaseinputyourdecimalsystemnumber:M?endl;

cin?numl;

/*

cout?HWhichnumbersystemdoyouwantthisnumberbeconverted

to?(2/8/16)n?endl;

cin?numSys;

if(numSys!=2&&numSys!=8&&numSys!=16)

cout?nSorry.TheNumberSystemsare2/8/16.Pleaseinputtheright

one.n?endl;

else

(

cout?n10進(jìn)制數(shù)?>''vvnumSysvv''進(jìn)制數(shù)"vvendl;

cout?nH?numl?n

numtonum.convert(numl9numSys);

cout?endl;

產(chǎn)/

cout?endl;

cout?H==AlltheNumberSystemsConvertedResults:==**?endl;

cout?H10進(jìn)制數(shù)“vv”n?n2進(jìn)制數(shù)“vv”H?H8進(jìn)制數(shù)n?n16進(jìn)制數(shù)

n?endl;

cout?nH?numl?Hn;

numtonum.convertAH(numl);

cout?endl;

3)用循環(huán)鏈表求解約瑟夫問題

#include<iostream>

usingnamespacestd;

structNode

(

intentry;

Node*next;

Node();

Node(intitem,Node*add_on=NULL);

)；

Node::Node()

(

next=NULL;

)

Node::Node(intitem,Node*add_on)

(

entry=item;

next=add_on;

intmain()

(

intn,m,count=l;

cout?”Inputthenumberofpeople(>0)H?endl;

cin?n;

while(n<=0){

cout?nERRORH?endl;

cin?n;

)

cout?nInputthenumberofgame(>0)n?endl;

cin?m;

while(m<=0){

cout?HERRORH?endl;

cin?m;

)

Node*h=newNode(l);

Node*p=h;

while(count<n){

p->next=newNode(++count);

p=p->next;

)

p->next=h;〃構(gòu)成循環(huán)鏈表

P=h；

while(n>l){

for(count=l;count<in-l;count++)

p=p->next;

p->next=p->next->next;

p=p->next;

n?；

}

cout?"People#n?p->entry?nwins.u?endl;

return0;

4)P182E4(a)遞歸實(shí)現(xiàn)Ackermann*sFunction

#include<iostream>

usingnamespacestd;

intA(intm,intn);

voidmain()

intm9n;

cout?nThisistheAckermann'sfunction.H?endl;

cout?nPleaseenterthevalueofMandN:H?endl;

cout?nM:

cin?m;

cout?nN:

cin?n;

cout?endl;

cout?^Theresultisf,?A(m,n)?endl?endl;

)

intA(intm9intn)

(

if(n<0||m<0){

cout?Hm,nmustbothbepositiveH?endl;

return-1;

}

elseif(m==0&&n>=0)return(n+1);

elseif(n==0&&m>0)returnA(m-l,l);

elseif(m>0&&n>0)returnA(m-l,A(m,n-l));

)

5)P241E3(c)

//Onesegmenti『theString.h:

intstrstr(constString&text,constString&target);

//OnesegmentintheString.cpp:

intstrstr(constString&text,constString&target){

constchar*ctext=text.c_str();

constcharRetarget=target.c_str();

char*tmp=strstr(ctext,ctarget);〃本來(lái)有char型的strstr的函數(shù)。

cout?tmp?endl;

if(tmp==NULL)return-1;

elsereturn(tmp-ctext);

}

//OnesegmentintheMain.cpp

voidmain(){

Stringtext,target;

cout?nPIeaseenterthetext:H?endl;

text=read_in(cin);

cout?nPleaseenterthetarget:H?endl;

target=read_in(cin);

intm=strstr(text,target);

if(m!=-l)

cout?nThetargetappearattheposition#H?m?Hofthetext.H?endl;

else

cout?nCanftfindthetargetinthetext.H?endl;

6)上機(jī)完成DoubleLinkList

//Node.h

enumEiror_code{underflow,overflow,range_error,success};

template<classNode_entry>

structNode{

//datamembers

Node_entryentry;

Node<Node_entry>*next;

Node<Node_entry>*back;

〃constructors

Node();

Node(Node_entryitem,Node<Node_entry>*link_back=NULL,

Node<Node_entry>*link_next=NULL);

)；

//LinkList.h

#includeHNode.cppH//!!!

template<classList_entry>

classList{

public:

//SpecificationsforthemethodsofthelistADTgohere.

//Thefollowingmethodsreplacecompiler-generateddefaults.

~List();

List();

List(constList<List_entry>©);

voidoperator=(constList<List_entry>©);

intsize()const;

boolfull()const;

boolempty()const;

voidclear();

voidtraverse(void(*visit)(List_entry&));

Error_coderetrieve(intposition,List_entry&x)const;

Error_codereplace(intposition,constList_entry&x);

Error_coderemove(intposition,List_entry&x);

Error_codeinsert(intposition,constList_entry&x);

protected:

//Datamembersforthelinkedlistimplementationnowfollow.

intcount;

mutableintcurrent_position;

mutableNode<List_entry>*current;

Node<List_entry>*head;

//Thefollowingauxiliaryfunctionisusedtolocatelistpositions

voidset_position(intposition)const;

}；

//Node.cpp

#includeHNode.hn

template<classNode_entry>

Node<Node_entry>::Node()

(

back=NULL;

next=NULL;

}

template<classNode_entry>

Node<Node_entry>::Node(Node_entryitem,Node<Node_entry>*link_back,

Node<Node_entry>*link_next)

(

entry=item;

back=link_back;

next=link_next;

}

//LinkList.cpp

#includenLinkList.hn

template<classList_entry>

List<List_entry>::List()

(

count=0;

head=NULL;//pointer

current_position=0;

current=NULL;//pointer

)

template<classList_entry>

List<List_entry>::List(constList<List_entry>©)

(

count=0;

head=NULL;

current_position=0;

current=NULL;

Node<List_entry>*q=copy.head;

inti=0;

while(q){

insert(i,q->entry);

q=q->next;

i++;

template<classList_entry>

voidList<List_entry>::operator=(constList<List_entry>©)

(

List_entryx;

while(!empty())remove(0,x);

Node<List_entry>*q=copy.head;

inti=0;

while(q){

insert(i,q->entry);

q=q->next;

i++；

template<classList_entry>

List<List_entry>::-List()

(

List_entryx;

while(!empty())remove(0,x);

template<classList_entry>

voidList<List_entry>::set_position(intposition)const

/*Pre:positionisavalidpositionintheList:0<=position<count.

Post:ThecurrentNodepointerreferencestheNodeatposition.*/

(

if(current_position<=position)

for(;current_position!=position;current_position++)

current=current->next;

else

for(;current_position!=position;current_position—)

current=current->back;

template<classList_entry>

intList<List_entry>::size()const

(

returncount;

template<classList_entry>

boolList<List_entry>::full()const

(

Node<List_entry>*new_node;

new_node=newNode<List_entry>;

if(new_node==NULL)returntrue;

else{

deletenew_node;

returnfalse;

template<classList_entry>

boolList<List_entry>::empty()const

returncount==0;

template<classList_entry>

voidList<List_entry>::clear()

(

List_entryx;

while(!empty())remove(0,x);

template<classList_entry>

voidList<List_entry>::traverse(void(*visit)(List_entry&))

(

Node<List_entry>*p_node=head;

while(p_node){

(*visit)(p_node->entry);

p_node=p_node->next;

template<classList_entr>

Error_codeList<List_entry>::retrieve(intposition,List_entry&x)const

if(position<0||position>=count)

returnrange_error;

Node<List_entry>*p_node;

set_position(position);

x=current->entry;

returnsuccess;

template<classList_entry>

Error_codeList<List_entry>::replace(intposition,constList_entry&x)

(

if(position<0||position>=count)

returnrange_error;

Node<List_entry>*p_node;

set_position(position);

current->entry=x;

returnsuccess;

template<classList_entry>

Error_codeList<List_entry>::remove(intposition,List_entry&x)

(

if(position<0||position>=count)

returnrange_error;

Node<List_entry>^previous,*following;

if(position>0){

set_position(position-1);

previous=current;

following=previous->next;

previous->next=following->next;

if(following->next)

following->next->back=previous;

}

else{

following=head;

head=head->next;

if(head)head->back=NULL;

//shouldbeadded

current_position=0;

current=head;

}

deletefollowing;

count-;

returnsuccess;

template<classList_entry>

Error_codeList<List_entry>::insert(intposition,constList_entry&x)

/*Post:IftheListisnotfulland0<=position<=n,wherenisthenumberof

entriesintheList,thefunctionsucceeds:Anyentryformerlyatpositionand

alllaterentrieshavetheirpositionnumbersincreasedby1,andxisinsertedat

positionoftheList.

Else:Thefunctionfailswithadiagnosticerrorcode.*/

(

Node<List_entry>*new_node,*following,*preceding;

if(position<0||position>count)returnrange_error;

if(position==0){

if(count==0)following=NULL;

else{

set_position(0);

following=current;

)

preceding=NULL;

}

else{

set_position(position-1);

preceding=current;

following=preceding->next;

)

new_node=newNode<List_entry>(x,preceding,following);

if(new_node==NULL)returnoverflow;

if(preceding!=NULL)preceding->next=new_node;

if(following!=NULL)following->back=new_node;

current=new_node;

current_position=position;

//shouldbeadded

if(position==0)head=new_node;

count++;

returnsuccess;

//Main.cpp

#includeHiostream.hH

#includenLinkList.cppn

template<classList_entry>

voidupdate(List_entry&x){

x*=2;

)

template<classList_entry>

voidprint(List_entry&x){

cout?x?endl;

)

voidmain(){

List<int>mylist;

for(inti=0;i<5;i++)mylist.insert(i,i)；

cout?HYourlisthave**?mylist.size()?**elements:H?endl;

mylist.traverse(print);

mylist.remove(l,i);

cout?nAfterremove(l):H?endl;

mylist.traverse(print);

mylist.remove(0,i);

cout?HAfterremove(O):H?endl;

mylist.traverse(print);

//use''copy''togivetheconstructiontomylist2.

List<int>mylist2(mylist);

cout?nAftermylist2(mylist):n?endl;

mylist2.traverse(print);

cout?nAfterupdate:H?endl;

mylist.traverse(update);

mylist.traverse(print);

//usenoperater=ntogivetheconstructiontomylist3

List<int>mylist3;

mylist3=mylist;

cout?HAftermylist3=mylist:n?endl;

mylist3.traverse(print);

)

7)上機(jī)完成Sortable_List

//Record.h

#includeniostream.hn

classRecord{

public:

//operatorKey();//implicitconversionfromRecordtoKey.

Record(intx=0,inty=0);

intthe_key()const;

private:

intkey;

intother;

)；

booloperator>(constRecord&x,constRecord&y);

booloperator>=(constRecord&x,constRecord&y);

booloperator<(constRecord&x,constRecord&y);

booloperator<=(constRecord&x,constRecord&y);

ostream&operator?(ostream&output9Record&x);

//List.h

enumError_code{underflow,overflow,range_error,success};

constintmax_list=30;

template<classList_entry>

classList{

public:

//methodsoftheListADT

List();

intsize()const;

boolfull()const;

boolempty()const;

voidclear();

voidtraverse(void(*visit)(List_entry&));

Error_coderetrieve(intposition,List_entry&x)const;

Error_codereplace(intposition,constList_entry&x);

Error_coderemove(intposition,List_entry&x);

Error_codeinsert(intposition,constList_entry&x);

protected:

Hdatamembersforacontiguouslistimplementation

intcount;

List_entryentry[max_list];

//Sortable_List.h

#includeHList.cppH

#includenRecord.hH

classSortable_list:publicList<Record>{

public://Addprototypesforsortingmethodshere,

voidinsertion_sort();

//forselection_sort.

voidswap(intlow,inthigh);

intmax_key(intlow,inthigh);

voidselection_sort();

//forshell_sort.

voidsort_interval(intstart,intincrement);

voidshell_sort();

//forquick_sort.

voidquick_sort();

voidrecursive_quick_sort(intlow,inthigh);

intpartition(intlow,inthigh);

//forheap_sort.

voidheap_sort();

voidbuild_heap();

voidinsert_heap(constRecord¤t,intlow,inthigh);

}；

//forMergesort

voiddivide_from(Sortable_list&mylist,Sortable_list&secondlist);

voidcombine(Sortable_list&firstsortlist,constSortable_list&secondsortlist);

voidMergesort(Sortable_list&mylist);

//Record.cpp

#includenRecord.hH

Record::Record(intx,inty){

key=x;

other=y;

intRecord::the_key()const{

returnkey;

}

booloperator>(constRecord&x9constRecord&y)

(

returnx.the_key()>y.the_key();

)

booloperator>=(constRecord&x,constRecord&y)

(

returnx.the_key()>=y.the_key();

}

booloperator<(constRecord&x,constRecord&y)

(

returnx.the_key()<y.the_key();

)

booloperator<=(constRecord&x9constRecord&y)

(

returnx.the_key()<=y.the_key();

}

ostream&operator?(ostream&output,Record&x)

(

output?x.the_key();

output?nn;

returnoutput;

)

//List.cpp

#includeHList.hH

template<classList_entry>

List<List_entry>::List()

/*Post:TheListhasbeencreatedandisinitializedtobeempty.*/

(

count=0;

)

template<classList_entry>

intList<List_entry>::size()const

/*Post:ThefunctionreturnsthenumberofentriesintheList,*/

(

returncount;

template<classList_entry>

boolList<List_entry>::full()const

"Post:Thefunctionreturnstrueorfalseaccordingtowhether

theListisfullornot.*/

(

return(count==max_list);

template<classList_entry>

boolList<List_entry>::empty()const

"Post:Thefunctionreturnstrueorfalseaccordingtowhether

theListisemptyornot.*/

returncount==0;

template<classList_entry>

voidList<List_entry>::clear()

/*Post:AllListentrieshavebeenremoved;theListisempty.*/

(

count=0;

template<classList_entry>

Error_codeList<List_entry>::insert(intposition,constList_entry&x)

/*Post:IftheListisnotfulland0<=position<=n;wherenisthenumberof

entriesintheList,thefunctionsucceeds:Anyentryformerlyatpositionand

alllaterentrieshavetheirpositionnumbersincreasedby1andxisinsertedat

positionoftheList.

Else:Thefunctionfailswithadiagnosticerrorcode.*/

(

if(full())returnoverflow;

if(position<0||position>count)returnrange_error;

for(inti=count-1;i>=position;i-)entry[i+1]=entry[i];

entry[position]=x;

count++;

returnsuccess;

template<classList_entry>

Error_codeList<List_entry>::remove(intposition,List_entry&x)

/*Post:If0<=position<n9wherenisthenumberofentriesin

theList,thefunctionsucceeds:Theentryatpositionis

removedfromtheList,andalllaterentrieshavetheir

positionnumbersdecreasedby1.Theparameterx

recordsacopyoftheentryformerlyatposition.

Else:Thefunctionfailswithadiagnosticerrorcode.*/

if(empty())returnunderflow;

if(position<0||position>=count)returnrange_error;

x=entry[position];

for(inti=position;i<count-1;i++)entry[i]=entry[i+l];

count-;

returnsuccess;

template<classList_entry>

Error_codeList<List_entry>::replace(intposition,constList_entry&x)

/*Post:If0<=position<n,wherenisthenumberofentries

intheList,thefunctionsucceeds:Theentryatposition

isreplacedbyx;allotherentriesremainunchanged.

Else:Thefunctionfailswithadiagnosticerrorcode.*/

(

if(position<0||position>=count)returnrange_error;

entry[position]=x;

returnsuccess;

template<classList_entry>

Error_codeList<List_entry>::retrieve(intposition,List_entry&x)const

/*Post:If0<=position<n,wherenisthenumberofentries

intheList,thefunctionsucceeds:Theentryatposition

iscopiedtox;allListentriesremainunchanged.

Else:Thefunctionfailswithadiagnosticerrorcode.*/

if(position<0||position>=count)returnrange_error;

x=entry[position];

returnsuccess;

template<classList_entry>

voidList<List_entry>::traverse(void(*visit)(List_entry&))

/*Post:Theactionspecifiedbyfunction(*visit)hasbeenperformedoneveryentryof

theList,beginningatposition0anddoingeachinturn.*/

(

for(inti=0;i<count;i++)(*visit)(entry[i]);

//Sortable_List.cpp

#includenSortabIe_list.hH

voidSortable_list::insertion_sort()

/*Post:TheentriesoftheSortablelisthavebeenrearrangedsothatthekeysinall

theentriesaresortedintonondecreasingorder.

Uses:MethodsfortheclassRecord;thecontiguousListimplementationofChapter6*/

(

intfirst_unsorted;//positionoffirstunsortedentry

intposition;//searchessortedpartoflist

Recordcurrent;//holdstheentrytemporarilyremovedfromlist

for(first_unsorted=1;first_unsorted<count;first_unsorted++)

if(entry[first_unsorted]<entry[first_unsorted-1]){

position=first_unsorted;

current=entry[first_unsorted];//Pullunsortedentryoutofthelist.

do{//Shiftallentriesuntiltheproperpositionisfound.

entry[position]=entry[position-1];

position-;//positionisempty.

}while(position>0&&entry[position-1]>current);

entry[position]=current;

voidSortable_list::selection_sort()

/*Post:TheentriesoftheSortablelisthavebeenrearrangedsothatthekeys

inalltheentriesaresortedintonondecreasingorder.

Uses:max_key,swap?*/

(

for(intposition=count-1;position>0;position—){

intmax=max_key(0,position);

swap(max,position);

intSortable_list::max_key(intlow,inthigh)

/*Pre:lowandhigharevalidpositionsintheSortablelistandlow<=high.

Post:Thepositionoftheentrybetweenlowandhighwiththelargestkeyis

returned.

Uses:TheclassRecord.ThecontiguousListimplementationofChapter6.*/

(

intlargest,current;

largest=low;

for(current=low+1;current<=high;current++)

if(entry[largest]<entry[current])

largest=current;

returnlargest;

voidSortable_list::swap(intlow,inthigh)

/*Pre:lowandhigharevalidpositionsintheSortablelist.

Post:Theentryatpositionlowisswappedwiththeentryatpositionhigh.

Uses:ThecontiguousListimplementationofChapter6.*/

Recordtemp;

temp=entry[low];

entry[low]=entry[high];

entry[high]=temp;

)

voidSortable_list::shell_sort()

/*Post:TheentriesoftheSortablelisthavebeenrearrangedsothatthekeysinall

theentriesaresortedintonondecreasingorder.

Uses:sort_interval*/

(

intincrement,//spacingofentriesinsublist

start;//startingpointofsublist

increment=count;

do{

increment=increment/3+1;

for(start=0;start<increment;start++)

sort_interval(start,increment);//modifiedinsertionsort

}while(increment>1);

voidSortable_list::sort_interval(intstart,intincrement){

intfirst_unsorted;//positionoffirstunsortedentry

intposition;//searchessortedpartoflist

Recordcurrent;//holdstheentrytemporarilyremovedfromlist

for(first_unsorted=start+increment;first_unsorted<count;first_unsorted+=

increment)

if(entry[first_unsorted]<entry[first_unsorted-increment]){

position=first_unsorted;

current=entry[first_unsorted];//Pullunsortedentryoutofthelist.

do{//Shiftallentriesuntiltheproperpositionisfound.

entry[position]=entry[position-increment];

position-=increment;//positionisempty.

}while(position>start&&entry[position-increment]>current);

entry[position]=current;

voidMergesort(Sortable_list&mylist)

(

Sortable_listsecondlist;

if(mylist.size()>l){

divide_from(mylist,secondlist);

Mergesort(mylist);

Mergesort(secondlist);

combine(mylist,secondlist);

voiddivide_from(Sortable_list&mylist,Sortable_list&secondlist){

intmid=(myIist.size()-l)/2;

intsecondsize=mylist.size()-(mid+l);

for(inti=0;i<secondsize;i++){

Recordx;

if(mylisLretrieve(mid+l,x)==success){

secondlist.insert(i9x);

mylist.remove(mid+l,x);

)

)

)

voidcombine(Sortable_list&firstsortlist,constSortable_list&secondsortlist){

Sortable_listtmp;

intm=0,n=0,i=0;

while(m<firstsortlist.size()&&n<secondsortlist.size()){

Recordx,y;

firstsortlist.retrieve(m,x);

secondsortlist.retrieve(n,y);

if(x<=y){

tmp.insert(i++,x);

m++;

)

else{

tmp.insert(i++,y);

n++;

)

}

while(m<firstsortlist.size()){

Recordx;

firstsortlist.retrieve(m,x);

tmp.insert(i++,x);

m++;

}

while(n<secondsortlist.size()){

Recordy;

secondsortlist.retrieve(n,y);

tmp.insert(i++,y);

n++;

}

firstsortlist=tmp;

)

voidSortable_list::quick_sort()

/*Post:TheentriesoftheSortablelisthavebeenrearrangedsothattheirkeys

aresortedintonondecreasingorder.

Uses:ContiguousListimplementationofChapter6,recursivequicksort.

號(hào)

recursive_quick_sort(0,count-1);

voidSortable_list::recursive_quick_sort(intlow,inthigh)

/*Pre:lowandhigharevalidpositionsintheSortablelist.

Post:TheentriesoftheSortablelisthavebeenrearrangedsothattheirkeys

aresortedintonondecreasingorder.

Uses:ContiguousListimplementationofChapter6,recursivequicksort,

andpartition?*/

(

intpivot_position;

if(low<high){//Otherwise,nosortingisneeded.

pivot_position=partition(low9high);

recursive_quick_sort(low,pivot_position-1);

recursive_quick_sort(pivot_position+1,high);

)

)

intSortable_list::partition(intlow,inthigh)

/*Pre:lowandhigharevalidpositionsoftheSortablelist9withlow<=high.

Post:Thecenter(orleftcenter)entryintherangebetweenindiceslowandhighof

theSortablelisthasbeenchosenasapivot.AllentriesoftheSortablelist

betweenindiceslowandhigh,inclusive,havebeenrearrangedsothatthose

withkeyslessthanthepivotcomebeforethepivotandtheremainingentries

comeafterthepivot.Thefinalpositionofthepivotisreturned.

Uses:swap(inti,intj)(interchangesentriesinpositionsiandjofaSortablelist),

thecontiguousListimplementationofChapter6,andmethodsfortheclass

Record,*/

(

Recordpivot;

inti,//usedtoscanthroughthelist

last_small;//positionofthelastkeylessthanpivot

swap(Iow,(low+high)/2);

pivot=entry[low];//Firstentryisnowpivot.

last_small=low;

for(i=low+1;i<=high;i++)

/*Atthebeginningofeachiterationofthisloop,wehavethefoll