與堆棧

Question

我想實現快速排序與堆在這裏非遞歸快速排序的代碼

#include <iostream> 
#include <cstdlib> 
using namespace std; 
template<class Item> 
class STACK{ 
private: 
    Item *a;int n; 
public: 
    STACK(int maxN){ 

     a=new Item[maxN];n=0; 

    } 
    int empty()const { 
     return n==0; 

    } 
    void push(Item item){ 
     a[n++]=item; 
     } 
    Item pop() { 
     return a[--n]; 

    } 


}; 
template<class Item> 
int partition (Item a[],int l,int r){ 

    int i=l-1; 
    int j=r; 
    Item v=a[r]; 
    for (;;){ 

      while (a[++i]<v); 
      while (v<a[--j]) if (j==i) break; 
      if (i>=j) break; 
      Item t=a[i]; 
      a[i]=a[j]; 
      a[j]=t; 
    } 

     Item s=a[i]; 
     a[i]=a[r]; 
     a[r]=s; 
     return i; 
     } 
inline void push2(STACK<int>&s,int a,int b){ 
    s.push(b); 
    s.push(a); 
    } 

template<class Item> 
    void quicksort(Item a[],int l,int r){ 

     STACK<int> s(50); 
     push2(a,l,r); 
     while (!s.empty()){ 
      int l=s.pop(); 
      int r=s.pop(); 
       if (r<=l) continue; 
       int i=partition(a,l,r); 
       if(i-1>r-1) 
       { push2(a,l,i-1); push2(a,i+1,r); 
       } 
       else{ 
        push2(a,i+1,r); 
        push2(a,l,i-1); 



       } 

     } 



    } 

int main(){ 

    int a[]={45,12,30,67,11,17,50,78}; 
    int n=sizeof(a)/sizeof(a[0]); 
    quicksort(a,0,n-1); 
    for (int i=0;i<n;i++) 
     cout<<a[i]<< " "; 




    return 0; 

} 

但這裏是錯誤

------ Build started: Project: sort_stack, Configuration: Debug Win32 ------ 
1> sort_stack.cpp 
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(65): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &' 
1>   with 
1>   [ 
1>    Item=int 
1>   ] 
1>   c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(92) : see reference to function template instantiation 'void quicksort<int>(Item [],int,int)' being compiled 
1>   with 
1>   [ 
1>    Item=int 
1>   ] 
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(72): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &' 
1>   with 
1>   [ 
1>    Item=int 
1>   ] 
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(72): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &' 
1>   with 
1>   [ 
1>    Item=int 
1>   ] 
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(75): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &' 
1>   with 
1>   [ 
1>    Item=int 
1>   ] 
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(76): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &' 
1>   with 
1>   [ 
1>    Item=int 
1>   ] 
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ========== 

請幫助

Answer 1

你叫

push2(a,i+1,r); 

其中a是項目

void quicksort(Item a[],int l,int r) 

的陣列，但push2()需要一個refenrece到STACK<int>

inline void push2(STACK<int>&s,int a,int b) 

Answer 2

void quicksort(Item a[],int l,int r){ 

     STACK<int> s(50); 
     push2(a,l,r); 

push2接受STACK，你給數組a。

不要自己實現堆棧，請使用std::stack。

Answer 3

push2以STACK<int> &作爲第一個參數。嘗試將其傳遞給它，而不是完全不同的類型。

Answer 4

在快速排序模板函數的定義，同時調用此錯誤後push2更換=>取值

#include <iostream> 
#include <cstdlib> 
using namespace std; 
template<class Item> 
class STACK{ 
private: 
    Item *a;int n; 
public: 
    STACK(int maxN){ 

     a=new Item[maxN];n=0; 

    } 
    int empty()const { 
     return n==0; 

    } 
    void push(Item item){ 
     a[n++]=item; 
     } 
    Item pop() { 
     return a[--n]; 

    } 


}; 
template<class Item> 
int partition (Item a[],int l,int r){ 

    int i=l-1; 
    int j=r; 
    Item v=a[r]; 
     for (;;){ 

      while (a[++i]<v); 
      while (v<a[--j]) if (j==i) break; 
      if (i>=j) break; 
      Item t=a[i]; 
      a[i]=a[j]; 
      a[j]=t; 
     } 

     Item s=a[i]; 
     a[i]=a[r]; 
     a[r]=s; 
     return i; 
     } 
inline void push2(STACK<int>&s,int a,int b){ 
    s.push(b); 
    s.push(a); 
    } 



template<class Item> 
void quicksort(Item a[],int l,int r){ 

    STACK<int> s(50); 
    push2(s,l,r); 
    while (!s.empty()){ 
    int l=s.pop(); 
    int r=s.pop(); 
     if (r<=l) continue; 
     int i=partition(a,l,r); 
     if(i-1>r-1) 
     { push2(s,l,i-1); push2(s,i+1,r); 
     } 
     else{ 
      push2(s,i+1,r); 
      push2(s,l,i-1); 

     } 
    } 
} 

int main(){ 

    int a[]={45,12,30,67,11,17,50,78}; 
    int n=sizeof(a)/sizeof(a[0]); 
    quicksort(a,0,n-1); 
     for (int i=0;i<n;i++) 
      cout<<a[i]<< " "; 
     return 0; 

}