【正确答案】(1)数据结构
   typedef int KeyType;
   typedef int DataType;
   typedef struct{
       KeyType key;    /*排序码字段*/
       DataType info;    /*记录的其他字段*/
   }RecordNode;
   typedef struct{
       intn;    /*n为文件中的记录个数*/
       RecordNode  *record;
   }SortObject;
   并采用栈的顺序表示:
   typedef struct{
       int left;    /*区间左端点*/
       int right;    /*区间右端点*/
   }DataType;
   struct SeqStack{
       DataType s[MAXNUM];  /*栈中每个元素是一个区间*/
       int t;
   };
   typedef struct SeqStack*PSeqStack;
   (2)思路
   利用栈，将教材中的递归的快速排序算法转换为与之等价的非递归的算法。需要注意的是栈中的每个元素是一个区间(用两个端点来表示)。
   (3)算法
   void nquicksort(sortobject*pvector){    /*非递归快速排序*/
       int 1,r,pivotindex,i,j;
       DataType temp;
       RecordNode pivot;
       PSeqStack pastack=createEmptyStack_seq();
       /*一个栈,用来存放每个区的两个边界*/
       temp.left=0;
       temp.right=pvector-＞n-1;
       push_seq(pastack,temp);    /*两个边界进栈*/
       while(!isEmptyStack_seq(pastack)){    /*每当栈不空*/
           temp=top_seq(pastack);
           1=temp.left;
           r=temp.right;
           pop_seq(pastack);    /*取栈顸,出栈*/
           if(1＞=r){
               continue;
           }    /*只有一个记录或无记录,无需排序*/
           pivotindex=1;
           pivot=pvector-＞record[pivotindex];    /*取轴值*/
           i=1:
           j=r;
           while(i!=j){    /*寻找轴值的最终位置*/
               while((pvector-＞record[j].key＞=pivot.key)&&(j＞i))
                 j--;
               if(i＜j)
                 pvector-＞record[i++]=pvector-＞record[j];
               while((pvector-＞record[i].key＜=pivot.key)&&(j＞i))
                 i++:
               if(i＜j)
                 pvector-＞record[j--]==pvector-＞record[i];
           }
           pvector-＞record[i]=pivot;    /*找到轴值的最终位置*/
           temp.left=i+1:
           temp.right=r;
           push_seq(pastack.temp);    /*右区两个边界进栈*/
           temp.left=1:
           temp.right=i-1:
           push_seq(pastack,temp);    /*左区两个边界进栈*/
       }
   }
   (4)代价分析
   该非递归算法与教材中的递归的快速排序算法是等价的，平均时间代价为O(nlog₂n)。