会python真的可以为所欲为0(回)
349天前
这里还有人吗1(回)
534天前这里还有人吗0(回)
534天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
759天前到处都是羊，不想上班0(回)
839天前
鸽子
0(回)
843天前#include <iostream> |
using namespace std; |
#include <iostream> |
using namespace std; |
typedef int KeyType; |
struct LElemType |
{ |
KeyType key; |
}; |
struct SElemType |
{ |
int a; |
int b; |
}; |
struct SList |
{ |
LElemType *r; |
int length; |
}; |
const int StackInitSize=10; |
const int StackInc=15; |
struct SStack |
{ |
SElemType *base,*top; |
int stacksize; |
}; |
bool StackInit (SStack &S);//构造栈 |
bool Push(SStack &S,SElemType &e);//入栈 |
bool Pop(SStack &S,SElemType &e);//出栈 |
bool StackEmpty(SStack &S);//空栈 |
bool ListCreate(SList &L,int n,LElemType a[]);//创建顺序表 |
void Listshow(SList &L);//显示表 |
void quicksort(SList &L);//非递归的快速排序 |
void InsertSort(SList &L) ; |
int Partition(SList &L, int a, int b); |
int main() |
{ |
const int i=13; |
LElemType a[i]={3,7,1,5,9,6,4,10,15,12,14,19,16}; |
SList L; |
ListCreate(L,i,a); |
cout<<"待排序的元素序列为"<<endl; |
Listshow(L); |
quicksort(L); |
cout<<endl<<"非递归的快速排序后元素序列为"<<endl; |
Listshow(L); |
cout<<endl; |
return 0; |
} |
bool ListCreate(SList &L,int n,LElemType a[]) |
{ |
int i; |
L.r=new LElemType[n]; |
if(!L.r) return false; |
L.length=n; |
for(i=0;i<n;i++) |
{ |
L.r[i]=a[i]; |
} |
return true; |
} |
void Listshow(SList &L) |
{ |
int i=L.length; |
for(int j=0;j<i;j++) |
{ |
cout<<L.r[j].key<<" "; |
} |
} |
bool StackInit (SStack &S) |
{ |
S.base=new SElemType[StackInitSize]; |
if(!S.base) return false; |
S.top=S.base; |
S.stacksize=StackInc; |
return true; |
} |
bool StackEmpty(SStack &S) |
{ |
return S.top==S.base; |
} |
bool Push(SStack &S,SElemType &e) |
{ |
SElemType *base; |
if(S.top-S.base==S.stacksize) |
{ |
base=(SElemType*)realloc(S.base,(S.stacksize+StackInc)*sizeof(SElemType)); |
if(!base) return false; |
S.base=base; |
S.top=S.base+S.stacksize; |
S.stacksize+=StackInc; |
} |
*S.top=e; |
S.top++; |
return true; |
} |
bool Pop(SStack &S,SElemType &e) |
{ |
if(S.top==S.base) return false; |
S.top--; |
e=*S.top; |
return true; |
} |
int Partition(SList &L, int a, int b) |
{ |
LElemType x = L.r[a]; |
while (a < b) { |
while (a < b && L.r[b].key >= x.key) { |
b--; |
} |
L.r[a] = L.r[b]; |
while (a < b && L.r[a].key <= x.key) { |
a++; |
} |
L.r[b] = L.r[a]; |
} |
L.r[a] = x; return a; |
} |
void quicksort(SList &L) |
{ |
SStack S; StackInit(S); |
SElemType e, p; |
e.a = 0; e.b = L.length-1; |
Push(S, e); int t; |
while (Pop(S, e)) { |
if (e.b-e.a<7) { |
continue; |
} |
t = Partition(L, e.a, e.b); |
p.a = e.a; p.b = t - 1; |
Push(S, p); |
p.a = t + 1; p.b = e.b; |
Push(S, p); |
} |
InsertSort(L); |
} |
void InsertSort(SList &L) |
{ |
int i, j; LElemType x; |
for (i = 1; i < L.length; i++) { |
for (x = L.r[i], j = i - 1; j >= 0 && x.key < L.r[j].key; j--) { |
L.r[j + 1] = L.r[j]; |
} |
L.r[j + 1] = x; |
} |
} |
