数据结构实验

冒泡排序法：
#include
#include
#define maxsize 100
void qsort(int a[],int low,int high);
int partion(int a[],int low,int high);
void qsort(int a[],int low,int high)
{
int piv;
if(low{
piv=partion(a,low,high);
qsort(a,low,piv-1);
qsort(a,piv+1,high);
}
}
int partion(int a[],int low,int high)
{
int piv=a[low], i=low+1, j=high, temp;
while(1)
{
while(a[i]while(a[j]> piv) --j;
if(i>=j) break;
temp=a[i]; a[i]=a[j]; a[j]=temp;
}
a[low]=a[j];
a[j]=piv;
return j;
}

void maopao(int a[],int N)
{
int i,j,t;
for(j=0;jfor(i=0;iif(a[i]>a[i+1])
{
t=a[i];a[i]=a[i+1];
a[i+1]=t;
}


}
void main ()
{
int a[maxsize],b[maxsize];
int i,N;
printf("输入该数组元素的个数N：\n");
scanf("%d",&N);
printf("输入数组各个数字：\n");
for(i=0;i{ scanf("%d",&a[i]);
b[i]=a[i];
}
maopao(a,N);
printf("冒泡法排序的结果：\n");
for(i=0;iprintf("%5d",a[i]);
printf("\n");
qsort(b,0,N-1);
printf("快速排序法排序结果：\n");
for(i=0;iprintf("%5d",b[i]);
printf("\n");
printf("冒泡法排序的时间复杂度为：\n");
printf("%d\n",N*N);
printf("快速排序法时间复杂度为：\n");
printf("%4f\n",N*log(N));
printf("通过比较可得出快速排序的算法要比冒泡法排序的算法性能好。\n");

}



二叉树排序法

#include
using namespace std;
#define NULL 0
typedef struct BiTNode {
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree create(BiTree bt,int n)
{
BiTree s,p,q;
int x,i;
scanf("%d",&x);
s=(BiTree)malloc(sizeof(BiTNode));
s->data=x;
s->lchild=s->rchild=NULL;
bt=s;
for(i=1;i{
scanf("%d",&x);
s=(BiTree)malloc(sizeof(BiTNode));
s->data=x;
s->lchild=s->rchild=NULL;
p=bt;
while (p)
{
if (p->data>x)
{q=p;p=p->lchild;}
else
{q=p;p=p->rchild;}
}
if (q->data>x) q->lchild=s;
else
q->rchild=s;
}

return bt;
}
void intraverse(BiTree bt)
{
if (bt)
{
intraverse(bt->lchild);
printf("%4d",bt->data);
intraverse(bt->rchild);
printf("\n");
}
}
int main()
{ BiTree bt,t;
int m;
scanf("%d",&m);
t=NULL;
bt=create(t,m);
intraverse(bt);
return EXIT_SUCCESS;
}