快速排序的非递归算法.txt

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include <stdio.h>
#include <conio.h>
#include <math.h>
#define MAX 100

typedef struct
{
   int ll;
   int lr;
}STR;

typedef struct       /*结构体定义*/
{
   STR help[MAX];
   int top;
}SQSTACK;


void initstack(SQSTACK *s) /*栈的初始化*/
{
   (*s).top = -1;
}

int stackempty(SQSTACK s) /*判断栈是否为空*/
{
   if (s.top == -1)
       return 1;
   else
       return 0;
}

void push(SQSTACK *s, int ll, int lr)  /*入栈*/
{
   if ((*s).top == MAX - 1) {printf("stack is full!");return;}
   (*s).top++;
   (*s).help[(*s).top].ll = ll;
   (*s).help[(*s).top].lr = lr;

}

void pop(SQSTACK*s, int *ll,int *lr)   /*出栈*/
{
   if ((*s).top == -1) {printf("stack is empty!");return;}
   *ll = (*s).help[(*s).top].ll;
   *lr = (*s).help[(*s).top].lr;
   (*s).top--;
}

void part(int r[], int ll, int lr, int *pivotloc) /*划分子表*/
{
   int temp,i,j;
   i = ll;
   j = lr;
   temp = r[ll];
   while (i != j)
   {
       while (j>i && r[j]>=temp)
           j--;
       if (i < j)
       {
           r[i] = r[j];
           i++;
       }
       while (j>i && r[i]<temp)
           i++;
       if (i < j)
       {
           r[j] = r[i];
           j--;
       }
   }
   r[i] = temp;
   *pivotloc = i;
}


void QuickSort(int a[], int n)  /*快排序*/
{
   int ll = 0;
   int lr = n - 1;
   int first = 0;

   SQSTACK use;
   initstack(&use);
   push(&use, ll, lr);

   while (!stackempty(use))
   {
       pop(&use, &ll, &lr);
       part(a, ll, lr, &first);

       if (ll!=(first-1) && first!=ll)
       {
           push(&use, ll, first - 1);
       }
       if (lr!=(first+1) && first!=lr)
       {
           push(&use, first + 1, lr);
       }
   }    
}


void InputArray(int a[], int *n)   /*输入数组*/
{
   int i;
   printf("Please input the numbers of the array:");
   scanf("%d",n);
   for (i=0; i<(*n); i++)
   {
       scanf("%d",&a[i]);
   }
}

void OutputArray(int a[],int n)   /*输出数组*/
{
   int i;
   for(i=0; i<n; i++)
   {
       printf("%4d",a[i]);
   }
}



void main()
{
   int n;
   int a[MAX];
   InputArray(a, &n);
   QuickSort(a, n);
   OutputArray(a, n);
   getch();
}