AnyView DC01-04

/**********
【题目】试写一算法，如果三个整数a，b和c的值
不是依次非递增的，则通过交换，令其为非递增。
***********/

void swp(int &a,int &b)
{
    a=a^b;
    b=a^b;
    a=a^b;    
}

void Descend(int &a, int &b, int &c)
/* 通过交换，令 a >= b >= c */
{
    int d;
    if(a<b) swp(a,b);
    if(a<c) swp(a,c);
    if(b<c) swp(b,c);
}


/**********
【题目】试编写算法求一元多项式
    P(x) = a0 + a1x + a2x^2 + ... + anx^n
的值P(x0)，并确定算法中每一语句的执行次数和整个算法
的时间复杂度。
**********/
float Polynomial(int n, int a[], float x)
/* 求一元多项式的值P(x)。                  */
/* 数组a的元素a[i]为i次项的系数，i=0,...,n */
{
    float sum=a[0],d=1;
    for(int i=1;i<=n;++i)
    {
        d*=x;
        sum+=a[i]*d;
    }
    return sum;
}


/**********
【题目】已知k阶裴波那契序列的定义为
    f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;
    f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
**********/
Status Fibonacci(int k, int m, int &f) 
/* 求k阶斐波那契序列的第m项的值f */
{
    if(k<2 || m<0) return ERROR;
    if(m<k)
    {
        f=(m==k-1)?1:0;
        return OK;
    }
    int d[1000]={0};
    for(int i=0;i<k;++i) d[i]=0;
    d[k-1]=1; d[k]=1;    
    for(int j=k+1;j<=m;++j)
    {
        d[j]=d[j-1]*2-d[j-k-1];
    }
    f=d[m];
    return OK;
}


/**********
【题目】试编写算法，计算i!×2^i的值并存入数组
a[0..n-1]的第i-1个分量中 (i=1,2,…,n)。假设计
算机中允许的整数最大值为MAXINT，则当对某个k
(1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意
选择你认为较好的出错处理方法。
**********/
Status Series(int a[], int n) 
/* 求i!*2^i序列的值并依次存入长度为n的数组a；     */
/* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */
{
    int b=2; int i;
    for(i=1;b<=MAXINT && i<=n;++i)
    {
        a[i-1]=b; b=b*(i+1)*2;
    }
    if(i==n+1) return OK; else return OVERFLOW;
}


/**********
【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，
各院校的单项成绩均以存入计算机并构成一张表，表中每一行
的形式为：
        项目名称   性别   校名   成绩   得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体
总分，并输出。
**********/

void Scores(ResultType *result, ScoreType *score)
/* 求各校的男、女总分和团体总分, 并依次存入数组score */
/* 假设比赛结果已经储存在result[ ]数组中,            */
/* 并以特殊记录 {"", male, ' ', "", 0 }（域scorce=0）*/
/* 表示结束                                          */
{
    for(int i=0;result[i].score!=NULL;++i)
    {
        int ss=result[i].score;
        Sex sd=result[i].gender;
        int sc=result[i].schoolname-'A';
        score[sc].totalscore+=ss;
        if(sd==male) score[sc].malescore+=ss;
        else score[sc].femalescore+=ss;
    }
}            


/**********
【题目】试写一算法，对序列S的第i个元素赋以值e。
序列的类型定义为：
typedef struct {
  ElemType  *elem;
  int  length;
} Sequence;
***********/
Status Assign(Sequence &S, int i, ElemType e) 
/* 对序列S的第i个元素赋以值e，并返回OK。 */
/* 若S或i不合法，则赋值失败，返回ERROR   */
{
    if(S.elem==NULL || i>=S.length || i<0) return ERROR;
    S.elem[i]=e; return OK;
}


/**********
【题目】试写一算法，由长度为n的一维数组a构建一个序列S。
序列的类型定义为：
typedef struct {
  ElemType  *elem;
  int  length;
} Sequence;
***********/
Status CreateSequence(Sequence &S, int n, ElemType *a) 
/* 由长度为n的一维数组a构建一个序列S，并返回OK。 */
/* 若构建失败，则返回ERROR                       */
{
    if(a==NULL || n<=0) return ERROR;
    S.length=n; S.elem=a; return OK;    
}

/**********
【题目】链表的结点和指针类型定义如下
    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;
试写一函数，构建一个值为x的结点。
***********/
LinkList MakeNode(ElemType x)
/* 构建一个值为x的结点，并返回其指针。*/
/* 若构建失败，则返回NULL。           */
{
    LNode *X;
    X=(LNode*)malloc(sizeof(LNode));
    if(X==NULL) return NULL;
    X->data=x;    
    return X;
}

/**********
【题目】链表的结点和指针类型定义如下
    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;
试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
**********/
LinkList CreateLinkList(ElemType x, ElemType y) 
/* 构建其两个结点的值依次为x和y的链表。*/
/* 若构建失败，则返回NULL。            */
{
    LNode *X,*Y;
    X=(LNode*)malloc(sizeof(LNode));
    Y=(LNode*)malloc(sizeof(LNode));
    if(X==NULL || Y==NULL) return NULL;
    X->data=x; Y->data=y;
    X->next=Y;    
    return X;
}

/**********
【题目】链表的结点和指针类型定义如下
    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;
试写一函数，构建长度为2的升序链表，两个结点的值
分别为x和y，但应小的在前，大的在后。
**********/
LinkList CreateOrdLList(ElemType x, ElemType y)
/* 构建长度为2的升序链表。  */
/* 若构建失败，则返回NULL。 */
{
    if(x>y)
    {
        x=x^y; y=y^x; x=x^y;
    } 
    LNode *X,*Y;
    X=(LNode*)malloc(sizeof(LNode));
    Y=(LNode*)malloc(sizeof(LNode));
    if(X==NULL || Y==NULL) return NULL;
    X->data=x; Y->data=y;
    X->next=Y;
    return X;
}

/**********
【题目】试写一算法，实现顺序栈的判空操作
StackEmpty_Sq(SqStack S)。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem; // 存储空间的基址
  int top;        // 栈顶元素的下一个位置，简称栈顶位标
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack;        // 顺序栈
***********/
Status StackEmpty_Sq(SqStack S)
/* 对顺序栈S判空。                      */ 
/* 若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(!S.top) return TRUE;
    return FALSE;
}


/**********
【题目】试写一算法，实现顺序栈的取栈顶元素操作
GetTop_Sq(SqStack S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem;  // 存储空间的基址
  int top;         // 栈顶元素的下一个位置，简称栈顶位标
  int size;        // 当前分配的存储容量
  int increment;   // 扩容时，增加的存储容量
} SqStack;         // 顺序栈
***********/
Status GetTop_Sq(SqStack S, ElemType &e) 
/* 取顺序栈S的栈顶元素到e，并返回OK； */ 
/* 若失败，则返回ERROR。              */
{
    if(S.top)
    {
        e=*(S.elem+S.top-1);
        return OK;
    }
    return ERROR; 
}

/**********
【题目】试写一算法，实现顺序栈的出栈操作
Pop_Sq(SqStack &S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem;  // 存储空间的基址
  int top;         // 栈顶元素的下一个位置，简称栈顶位标
  int size;        // 当前分配的存储容量
  int increment;   // 扩容时，增加的存储容量
} SqStack;         // 顺序栈
***********/
Status Pop_Sq(SqStack &S, ElemType &e) 
/* 顺序栈S的栈顶元素出栈到e，并返回OK；*/ 
/* 若失败，则返回ERROR。               */
{
    if(S.top)
    {
        e=*(S.elem+S.top-1);
        --S.top;
        return OK;
    }
    return ERROR; 
}

/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status InitStack_Sq2(SqStack2 &S, int size, int inc)
/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/ 
/* 若成功，则返回OK；否则返回ERROR。                 */
{
    if(size<=0 || inc<=0) return ERROR;
    S.elem=(ElemType*)malloc(size*sizeof(ElemType));    
    if(S.elem==NULL) return ERROR;
    S.size=size; S.increment=inc; S.top=S.elem;
    return OK;
}


/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的判空操作。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status StackEmpty_Sq2(SqStack2 S)
/* 对顺序栈S判空。                      */ 
/* 若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(S.top==S.elem) return TRUE; else return FALSE;
}


/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的入栈操作。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status Push_Sq2(SqStack2 &S, ElemType e)
/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/
/* 将e压入S，返回OK。                          */
{
    if(S.top-S.elem>S.size)
    {
        ElemType* ad;
        if(S.increment<0) return ERROR;
        ad=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));
        if(ad==NULL) return ERROR;
    }
    *S.top=e; S.top++;
    return OK;
}

/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的出栈操作。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status Pop_Sq2(SqStack2 &S, ElemType &e) 
/* 若顺序栈S是空的，则返回ERROR；    */ 
/* 否则将S的栈顶元素出栈到e，返回OK。*/
{
    if(S.top==S.elem) return ERROR;
    e=*(S.top-1);
    S.top--;
    return OK;
}

/**********
【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem; // 存储空间的基址
  int top;        // 栈顶元素的下一个位置，简称栈顶位标
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack;        // 顺序栈
可调用顺序栈接口中下列函数：
Status InitStack_Sq(SqStack &S, int size, int inc); // 初始化顺序栈S
Status DestroyStack_Sq(SqStack &S); // 销毁顺序栈S
Status StackEmpty_Sq(SqStack S);    // 栈S判空，若空则返回TRUE，否则FALSE
Status Push_Sq(SqStack &S, ElemType e); // 将元素e压入栈S
Status Pop_Sq(SqStack &S, ElemType &e); // 栈S的栈顶元素出栈到e
***********/
Status CopyStack_Sq(SqStack S1, SqStack &S2) 
/* 借助辅助栈，复制顺序栈S1得到S2。    */ 
/* 若复制成功，则返回TRUE；否则FALSE。 */
{
    SqStack S3; ElemType a;
    InitStack_Sq(S3,S1.size,S1.increment);
    InitStack_Sq(S2,S1.size,S1.increment);
    while(!StackEmpty_Sq(S1))
    {
        Pop_Sq(S1,a);
        Push_Sq(S3,a);
    }
    while(!StackEmpty_Sq(S3))
    {
        Pop_Sq(S3,a);
        Push_Sq(S2,a);
    }
    return TRUE;
}

/**********
【题目】试写一算法，求循环队列的长度。
循环队列的类型定义为：
typedef struct {
  ElemType *base;  // 存储空间的基址
  int front;       // 队头位标
  int rear;        // 队尾位标，指示队尾元素的下一位置
  int maxSize;     // 最大长度
} SqQueue;
***********/
int QueueLength_Sq(SqQueue Q)
/* 返回队列Q中元素个数，即队列的长度。 */ 
{
    return (Q.rear-Q.front+Q.maxSize)%Q.maxSize;
}

/**********
【题目】如果希望循环队列中的元素都能得到利用，
则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是"空"还是"满"。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：
typedef struct {
  ElemType elem[MAXQSIZE];
  int tag;
  int front;
  int rear;
} CTagQueue;
**********/
Status EnCQueue(CTagQueue &Q, ElemType x)
/* 将元素x加入队列Q，并返回OK；*/
/* 若失败，则返回ERROR。       */
{
    if(Q.front==Q.rear && Q.tag) return ERROR;
    Q.elem[Q.rear]=x; Q.rear=(Q.rear+1)%MAXQSIZE;
    if(Q.rear==Q.front) Q.tag=1;
    return OK;
}

Status DeCQueue(CTagQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK；*/
/* 若失败，则返回ERROR。               */
{
    if(Q.front==Q.rear)
    {
        if(!Q.tag) return ERROR;
        Q.tag=0;
    }                             
    x=Q.elem[Q.front]; Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}

/**********
【题目】假设将循环队列定义为：以域变量rear
和length分别指示循环队列中队尾元素的位置和内
含元素的个数。试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法（在出队列的算
法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下：
typedef struct {
  ElemType elem[MAXQSIZE];
  int length;
  int rear;
} CLenQueue;
**********/
Status EnCQueue(CLenQueue &Q, ElemType x)
  /* 将元素x加入队列Q，并返回OK；*/
  /* 若失败，则返回ERROR。       */
{
    if(Q.length>=MAXQSIZE) return ERROR;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    Q.elem[Q.rear]=x; Q.length++; return OK;
}
Status DeCQueue(CLenQueue &Q, ElemType &x)
  /* 将队列Q的队头元素退队到x，并返回OK；*/
  /* 若失败，则返回ERROR。               */
{
    if(Q.length<=0) return ERROR;
    int a=(Q.rear-Q.length+1+MAXQSIZE)%MAXQSIZE;
    x=Q.elem[a]; Q.length--; return OK;
}

/**********
【题目】已知k阶斐波那契序列的定义为:
    f0=0,  f1=0,  …,  fk-2=0,  fk-1=1;
    fn=fn-1+fn-2+…+fn-k,  n=k,k+1,…
试利用循环队列编写求k阶斐波那契序列中第
n+1项fn的算法。

本题的循环队列的类型定义如下：
typedef struct {
  ElemType *base; // 存储空间的基址
  int front;      // 队头位标
  int rear;       // 队尾位标，指示队尾元素的下一位置
  int maxSize;    // 最大长度
} SqQueue;
**********/
long Fib(int k, int n)
/* 求k阶斐波那契序列的第n+1项fn */
{
    if(k<=1 || n<0) return ERROR;
    SqQueue A;
    A.base=(ElemType*)malloc(100*sizeof(ElemType));
    A.front=0; A.rear=k-1; A.maxSize=100;
    for(int i=0;i<k;++i) A.base[i]=0;
    A.base[k-1]=1;    
    for(int o=k;o<=n;++o)
    {
        int re=A.rear,sum=0;
        for(int j=0;j<k;++j)
        {
            sum+=A.base[re];
            re=(re+A.maxSize-1)%A.maxSize;
        }
        A.rear=(A.rear+1)%A.maxSize;
        A.base[A.rear]=sum;
    }
    return A.base[(n<k)?n:A.rear];
}


/**********
【题目】设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，
A'和B'分别为A和B中除去最大共同前缀后的子表（例如，
A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大
的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后
的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，
则A=B；若A'=空表，而B'≠ 空表，或者两者均不为空表，
且A'的首元小于B'的首元，则A<B；否则A>B。试写一个比
较A和B大小的算法。（注意：在算法中，不要破坏原表A
和B，也不一定先求得A'和B'才进行比较）。
顺序表类型定义如下：
typedef struct {
  ElemType *elem;
  int       length;
  int       size;
  int       increment;
} SqList;
**********/
char Compare(SqList A, SqList B)
/* 比较顺序表A和B,      */
/*   返回'<', 若A<B;    */
/*       '=', 若A=B;    */
/*       '>', 若A>B     */
{
    int mn=(A.length<B.length)?A.length:B.length;
    for(int i=0;i<mn;++i)
    {
        if(A.elem[i]<B.elem[i]) return '<';
        if(A.elem[i]>B.elem[i]) return '>';
    }
    if(A.length<B.length) return '<';
    if(A.length>B.length) return '>';
    return '=';
}

/**********
【题目】试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。
顺序表类型定义如下：
typedef struct {
  ElemType *elem;
  int       length;
  int       size;
  int       increment;
} SqList;
**********/
void Inverse(SqList &L)
{
    ElemType c;
    for(int i=0;(i<<1)<(L.length-1);++i)
    {
        c=L.elem[L.length-i-1];
        L.elem[L.length-i-1]=L.elem[i];
        L.elem[i]=c;
    }
}


/**********
【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式
项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0
为给定值）。

一元稀疏多项式的顺序存储结构:
typedef struct {
  int  coef;  // 系数
  int   exp;  // 指数
} Term;

typedef struct {
  Term  *elem;   // 存储空间基址
  int    length; // 长度（项数）
} Poly;
**********/
float Pow(float x,int y)
{
    float s=1;
    for(;y;y>>=1,x=x*x)
    if(y&1) s=s*x;
    return s; 
}

float Evaluate(Poly P, float x)
/* P.elem[i].coef 存放ai，                        */
/* P.elem[i].exp存放ei (i=1,2,...,m)              */
/* 本算法计算并返回多项式的值。不判别溢出。       */
/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证 */
{
    int las=0; float lax=1;
    float sum=0;
    for(int i=0;i<P.length;++i)
    {
        lax=lax*Pow(x,P.elem[i].exp-las);
        las=P.elem[i].exp;
        sum+=lax*P.elem[i].coef;
    }
    return sum;
}

/**********
【题目】假设有两个集合A和B分别用两个线性表LA和LB
表示(即：线性表中的数据元素即为集合中的成员），
试写一算法，求并集A＝A∪B。
顺序表类型定义如下
typedef struct {
  ElemType *elem;     // 存储空间的基址
  int length;    // 当前长度
  int size;      // 存储容量 
  int increment; // 空间不够增加空间大小
} SqList;  // 顺序表
可调用顺序表的以下接口函数：   
Status InitList_Sq(SqList &L, int size, int inc); // 初始化顺序表L
int ListLength_Sq(SqList L);  // 返回顺序表L中元素个数
Status GetElem_Sq(SqList L, int i, ElemType &e); 
// 用e返回顺序表L中第i个元素的值
int Search_Sq(SqList L, ElemType e); 
// 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1
Status Append_Sq(SqList &L, ElemType e);  // 在顺序表L表尾添加元素e
**********/
void Union(SqList &La, SqList Lb)
{
    ElemType e;
    for(int i=1;i<=Lb.length;++i)
    {
        GetElem_Sq(Lb,i,e);
        if(Search_Sq(La,e)==-1)
        Append_Sq(La,e);
    }
    La.length=ListLength_Sq(La);
}


/**********
【题目】试写一算法，实现链栈的判空操作。
链栈的类型定义为：
typedef struct LSNode {
  ElemType data;       // 数据域
  struct LSNode *next; // 指针域
} LSNode, *LStack;    // 结点和链栈类型
***********/
Status StackEmpty_L(LStack S)
/* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(S==NULL) return TRUE; else return FALSE;
}

/**********
【题目】试写一算法，实现链栈的取栈顶元素操作。
链栈的类型定义为：
typedef struct LSNode {
  ElemType data;       // 数据域
  struct LSNode *next; // 指针域
} LSNode, *LStack;    // 结点和链栈类型
***********/
Status GetTop_L(LStack S, ElemType &e) 
/* 取链栈S的栈顶元素到e，并返回OK; */
/* 若S是空栈，则失败，返回ERROR。  */
{
    if(S==NULL) return ERROR;
    e=(*S).data; return OK;
}

/**********
【题目】试写一算法，实现链队列的判空操作。
链队列的类型定义为：
typedef struct LQNode {     
  ElemType  data;  
  struct LQNode  *next;  
} LQNode, *QueuePtr; // 结点和结点指针类型
typedef struct {     
  QueuePtr  front;  // 队头指针
  QueuePtr  rear;   // 队尾指针
} LQueue;  // 链队列类型
***********/
Status QueueEmpty_LQ(LQueue Q)
/* 判定链队列Q是否为空队列。           */
/* 若Q是空队列，则返回TRUE，否则FALSE。*/
{
    if(Q.front==NULL) return TRUE; else return FALSE;
}

/**********
【题目】试写一算法，实现链队列的求队列长度操作。
链队列的类型定义为：
typedef struct LQNode {     
  ElemType  data;  
  struct LQNode  *next;  
} LQNode, *QueuePtr; // 结点和结点指针类型
typedef struct {     
  QueuePtr  front;  // 队头指针
  QueuePtr  rear;   // 队尾指针
} LQueue;  // 链队列类型
***********/
int QueueLength_LQ(LQueue Q)
/* 求链队列Q的长度并返回其值 */
{
    if(Q.front==NULL) return 0;
    int len=1;
    LQNode* a=Q.front;
    while(a->next!=NULL && a!=Q.rear)
    {
        a=a->next; ++len;        
    }
    return len;
}

/**********
【题目】假设以带头结点的循环链表表示队列，并且
只设一个指针指向队尾元素结点(注意不设头指针)，
试编写相应的队列初始化、入队列和出队列的算法。
带头结点循环链队列CLQueue的类型定义为：
typedef struct LQNode {
  ElemType data;
  struct LQNode *next;
} LQNode, *CLQueue;
**********/
Status InitCLQueue(CLQueue &rear) // 初始化空队列
{
    LQNode* Q; 
    Q=(LQNode*)malloc(sizeof(LQNode));
    if(Q==NULL) return ERROR;
    Q->next=Q;
    rear=Q; return OK;
}

Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
{ 
    LQNode* Q; 
    Q=(LQNode*)malloc(sizeof(LQNode));
    if(Q==NULL) return ERROR;
    Q->next=rear->next;
    Q->data=x;
    rear=rear->next=Q;
    return OK;
}

Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
{ 
    if(rear==NULL || rear->next==rear) return ERROR;
    x=rear->next->next->data;
    rear->next->next=rear->next->next->next;
    return OK;
}

/**********
【题目】试写一算法，实现带头结点单链表的判空操作。

单链表的类型定义为：
typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status ListEmpty_L(LinkList L)
/* 判定带头结点单链表L是否为空链表。   */
/* 若L是空链表，则返回TRUE，否则FALSE。*/
{
    if(L->next==NULL) return TRUE; else return FALSE;
}

/**********
【题目】试写一算法，实现带头结点单链表的销毁操作。
单链表的类型定义为：
typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status DestroyList_L(LinkList &L)
/* 销毁带头结点单链表L，并返回OK。*/
{
    L=NULL;
    L->next=NULL;
    return OK;
}

/**********
【题目】试写一算法，实现带头结点单链表的清空操作。

单链表的类型定义为：
typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status ClearList_L(LinkList &L)
/* 将带头结点单链表L置为空表，并返回OK。*/
/* 若L不是带头结点单链表，则返回ERROR。 */
{
    if(L==NULL) return ERROR;
    L->next=NULL; return OK;
}

/**********
【题目】试写一算法，实现带头结点单链表的求表长度操作。
单链表的类型定义为：
typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
int ListLength_L(LinkList L)
/* 求带头结点单链表L的长度，并返回长度值。*/
/* 若L不是带头结点单链表，则返回-1。      */
{
    int len=0;
    if(L==NULL) return -1;
    for(LNode *i=L->next;i!=NULL;i=i->next) ++len;
    return len;
}

/**********
【题目】试写一算法，在带头结点单链表L插入第i元素e。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/
/* 若参数不合理，则返回ERROR。              */
{
    if(i<=0) return ERROR;
    LNode* p;
    p=(LNode*)malloc(sizeof(LNode));
    p->data=e;
    int now=1;
    if(now==i)
    {
        p->next=L->next;
        L->next=p;
        return OK;
    }
    for(LNode* j=L->next;j!=NULL;j=j->next)
    {
        ++now;
        if(now==i)
        {
            p->next=j->next;
            j->next=p;
            return OK;
        }
    }
    return ERROR;
}

/**********
【题目】试写一算法，在带头结点单链表删除第i元素到e。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Delete_L(LinkList L, int i, ElemType &e)
/* 在带头结点单链表L删除第i元素到e，并返回OK。*/
/* 若参数不合理，则返回ERROR。                */
{
    if(i<=0) return ERROR;
    int now=1;
    if(now==i)
    {
        if(L->next==NULL) return ERROR;
        e=L->next->data;
        L->next=L->next->next;
        return OK;
    }
    for(LNode* j=L->next;j!=NULL;j=j->next)
    {
        ++now;
        if(now==i)
        {
            if(j->next==NULL) return ERROR;
            e=j->next->data;
            j->next=j->next->next;
            return OK;
        } else
        if(now>i) return ERROR;
    }
    return ERROR;
}

/**********
【题目】试写一算法，在带头结点单链表的第i元素起的
所有元素从链表移除，并构成一个带头结点的新链表。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Split_L(LinkList L, LinkList &Li, int i)
/* 在带头结点单链表L的第i元素起的所有元素 */
/* 移除，并构成带头结点链表Li，返回OK。   */
/* 若参数不合理，则Li为NULL，返回ERROR。  */
{
    if(i==0)
    {
        Li=NULL;
        return ERROR;
    }
    LNode *p=L; int len=0;
    Li=(LNode*)malloc(sizeof(LNode));
    Li->data=0;
    Li->next=NULL;
    while(p->next!=NULL)
    {
        ++len;
        if(len==i)
        {
            Li->next=p->next;
            p->next=NULL;
            return OK;
        }
        p=p->next;        
    }
    Li=NULL;
    return ERROR;
}

/**********
【题目】试写一算法，在带头结点单链表删除第i元素
起的所有元素。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Cut_L(LinkList L, int i)
/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/
/* 若参数不合理，则返回ERROR。                         */
{
    if(i<=0) return ERROR;
    LNode* p=L; int len=0;
    while(p->next!=NULL)
    {
        ++len;
        if(len==i)
        {
            p->next=NULL;
            return OK;
        }
        p=p->next;
        
    }
    return ERROR;
}

/**********
【题目】试写一算法，删除带头结点单链表中所有值
为x的元素，并释放被删结点空间。
单链表类型定义如下：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status DeleteX_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值为x的元素，      */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
    if(L==NULL) return ERROR;
    LNode *p=L,*q=L;
    int s=0;
    while(p->next!=NULL)
    {
        if(p->next->data==x)
        {
            LNode *tmp=p->next;
            q->next=p->next->next;
            //tmp->next=NULL;
            free(tmp);
            ++s;
        } else
        {
            p=p->next;
            q=q->next;
        }
    }
    return s;
}

/**********
【题目】试写一算法，删除带头结点单链表中所有值
小于x的元素，并释放被删结点空间。
单链表类型定义如下：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status DeleteSome_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值小于x的元素，    */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
    if(L==NULL) return ERROR;
    LNode *p=L,*q=L;
    int s=0;
    while(p->next!=NULL)
    {
        if(p->next->data<x)
        {
            LNode *tmp=p->next;
            q->next=p->next->next;
            //tmp->next=NULL;
            free(tmp);
            ++s;
        } else
        {
            p=p->next;
            q=q->next;
        }
    }
    return s;
}

/**********
【题目】试以顺序表L的L.rcd[L.length+1]作为监视哨，
改写教材3.2节中给出的升序直接插入排序算法。
顺序表的类型RcdSqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
   int length;
} RcdSqList;
**********/
void InsertSort(RcdSqList &L)
{
    int len=L.length+1;
    for(int i=1;i<L.length;++i)
    if(L.rcd[i+1].key<L.rcd[i].key)
    {
        L.rcd[len]=L.rcd[i+1];
        int j=i+1;
        do
        {
            --j; L.rcd[j+1]=L.rcd[j];            
        }while(L.rcd[len].key<L.rcd[j-1].key);
        L.rcd[j]=L.rcd[len];
    }
}


/**********
【题目】如下所述，改写教材1.3.2节例1-10的冒泡排序算法：
将算法中用以起控制作用的布尔变量change改为一个整型
变量，指示每一趟排序中进行交换的最后一个记录的位置，
并以它作为下一趟起泡排序循环终止的控制值。
顺序表的类型RcdSqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
   int length;
} RcdSqList;
**********/
void BubbleSort(RcdSqList &L)
/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"        */
/* Status GT(RedType a, RedType b);   比较：">"        */
/* void Swap(RedType &a, RedType &b); 交换             */
{
    for(int i=1,c=L.length-1;i<L.length && c;--i)
    {
        int d=c; c=0;        
        for(int j=1;j<=d;++j)
        if(GT(L.rcd[j],L.rcd[j+1]))
        {
            Swap(L.rcd[j],L.rcd[j+1]);
            c=j-1;
        }
    }
}

/**********
【题目】已知记录序列L.rcd[1..L.length]中的关键
字各不相同，可按如下所述实现计数排序：另设数组
c[1..n]，对每个记录a[i]， 统计序列中关键字比它
小的记录个数存于c[i]，则c[i]=0的记录必为关键字
最小的记录，然后依c[i]值的大小对序列中记录进行
重新排列。试编写算法实现上述排序方法。
顺序表的类型RcdSqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
   int     length;
} RcdSqList;
**********/
void CountSort(RcdSqList &L)
/* 采用顺序表存储结构，在函数内自行定义计数数组c */
{
    int n=L.length,i;
    if(n<=0) return;
    KeyType n1=L.rcd[1].key,n2=L.rcd[1].key;
    for(i=2;i<=n;++i)
    {
        if(L.rcd[i].key<n1) n1=L.rcd[i].key;
        if(L.rcd[i].key>n2) n2=L.rcd[i].key;
    }
    int *c; RcdType *p;
    int nn=(int)n2-(int)n1+1;
    c=(int*)malloc(nn*sizeof(int));
    p=(RcdType*)malloc(n*sizeof(RcdType));
    //动态构造表
    
    for(i=0;i<nn;++i) c[i]=0;
    for(i=0;i<n;++i) p[i]=L.rcd[i+1];
    for(i=0;i<n;++i) ++c[p[i].key-n1];
    for(i=1;i<nn;++i) c[i]+=c[i-1];
    for(i=n-1;i>=0;--i)
    {
        L.rcd[c[p[i].key-n1]]=p[i];
        --c[p[i].key-n1];
    }
    //线性复杂度排序-计数排序
}

/**********
【题目】已知某哈希表的装载因子小于1，哈希函数H(key)
为关键字(标识符)的第一个字母在字母表中的序号，处理
冲突的方法为线性探测开放定址法。试编写一个按第一个
字母的顺序输出哈希表中所有关键字的算法。
哈希表的类型HashTable定义如下：
#define SUCCESS    1
#define UNSUCCESS  0
#define DUPLICATE -1
typedef char StrKeyType[4];
typedef struct {
   StrKeyType key; // 关键字项
   int    tag;     // 标记 0:空；1:有效; -1:已删除
   void  *any;     // 其他信息
} RcdType;
typedef struct {
  RcdType *rcd;    // 存储空间基址
  int      size;   // 哈希表容量
  int      count;  // 表中当前记录个数
} HashTable;
**********/
void PrintKeys(HashTable ht, void(*print)(StrKeyType))
/* 依题意用print输出关键字 */
{
    for(char ch='A';ch<='Z';++ch)
    {
        bool fd=0; 
        for(int i=0;i<ht.size;++i)
        {
            if(fd && ht.rcd[i].tag==0) break;
            if(ht.rcd[i].tag && ht.rcd[i].key[0]==ch)
            {
                fd=1;
                if(ht.rcd[i].tag==1) print(ht.rcd[i].key);
            }
        }
    }
}

/**********
【题目】假设哈希表长为m，哈希函数为H(x)，用链地址法
处理冲突。试编写输入一组关键字并建造哈希表的算法。
哈希表的类型ChainHashTab定义如下：
#define NUM         7
#define NULLKEY    -1
#define SUCCESS     1
#define UNSUCCESS   0
#define DUPLICATE  -1
typedef char HKeyType;
typedef struct HNode {
   HKeyType  data;
   struct HNode*  next;
}*HLink;
typedef struct {
   HLink  *rcd;   // 指针存储基址，动态分配数组
   int    count;  // 当前表中含有的记录个数
   int    size;  // 哈希表的当前容量
}ChainHashTab;    // 链地址哈希表
int Hash(ChainHashTab H, HKeyType k) { // 哈希函数
  return k % H.size;
}
Status Collision(ChainHashTab H, HLink &p) {
  // 求得下一个探查地址p 
  if (p && p->next) { 
    p = p->next;
    return SUCCESS;
  } else return UNSUCCESS;
}
**********/
int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) 
/* 直接调用下列函数                             */
/* 哈希函数：                                   */
/*    int Hash(ChainHashTab H, HKeyType k);     */
/* 冲突处理函数：                               */
/*    int Collision(ChainHashTab H, HLink &p);  */
{
    for(int i=0;i<n;++i)
    {
        int has=Hash(H,es[i]);
        HNode *p;
        p=(HNode*)malloc(sizeof(HNode));
        p->data=es[i];
        HNode* q=H.rcd[has];
        if(H.rcd[has]==NULL)
        {
            H.rcd[has]=p;
            ++H.count;
        } else
        {
            bool rep=0;
            q=H.rcd[has];
            do
            {
                if(q->data==es[i]) { rep=1; break; } 
            } while(Collision(H,q)==SUCCESS);
            if(!rep)
            {
                q=H.rcd[has];
                H.rcd[has]=p;
                p->next=q;
                ++H.count;
            }
        } 
    }
}