厂工数据结构Anyview（C语言版）第二章答案

女爷i 2023-01-09 01:13 156阅读 0赞

### 第二章 ###

*  一、实现顺序栈的判空操作
 *  二、实现顺序栈的取栈顶元素操作
 *  三、实现顺序栈的出栈操作
 *  四、构建初始容量和扩容增量分别为size和inc的空顺序栈S
 *  五、实现顺序栈的判空操作
 *  六、实现顺序栈的入栈操作
 *  七、实现顺序栈的出栈操作
 *  八、借助辅助栈，复制顺序栈S1得到S2
 *  九、求循环队列的长度
 *  十、编写入队列和出队列的算法
 *  十一、写出循环队列的入队列和出队列的算法
 *  十二、利用循环队列编写求k阶斐波那契序列中第n+1项fn的算法
 *  十三、试写一个比较A和B大小的算法
 *  十四、试写一算法，实现顺序表的就地逆置
 *  十五、试写一算法，求并集A＝A∪B
 *  十六、试写一算法，实现链栈的判空操作
 *  十七、试写一算法，实现链栈的取栈顶元素操作
 *  十八、实现链队列的判空操作
 *  十九、实现链队列的求队列长度操作
 *  二十、编写队列初始化、入队列和出队列的算法
 *  二十一、实现带头结点单链表的判空操作
 *  二十一、实现带头结点单链表的销毁操作
 *  二十二、实现带头结点单链表的清空操作
 *  二十三、实现带头结点单链表的求表长度操作
 *  二十四、在带头结点单链表L插入第i元素e
 *  二十五、在带头结点单链表删除第i元素到e
 *  二十六、在带头结点单链表的第i元素起的所有元素从链表移除，并构成一个带头结点的新链表
 *  二十七、试写一算法，在带头结点单链表删除第i元素起的所有元素
 *  二十八、删除带头结点单链表中所有值为x的元素
 *  二十九、删除带头结点单链表中所有值小于x的元素

# 一、实现顺序栈的判空操作 #

【题目】试写一算法，实现顺序栈的判空操作  
StackEmpty\_Sq(SqStack S)。

要求实现下列函数：  
Status StackEmpty\_Sq(SqStack S);  
/\* 对顺序栈S判空。 */  
/* 若S是空栈，则返回TRUE；否则返回FALSE \*/

顺序栈的类型定义为：  
typedef struct \{  
ElemType \*elem; // 存储空间的基址  
int top; // 栈顶元素的下一个位置，简称栈顶位标  
int size; // 当前分配的存储容量  
int increment; // 扩容时，增加的存储容量  
\} SqStack; // 顺序栈

#include "allinclude.h"  //DO NOT edit this line
    Status StackEmpty_Sq(SqStack S) {
         
        //Add your code here
        
        return S.top == 0;
    }

# 二、实现顺序栈的取栈顶元素操作 #

【题目】试写一算法，实现顺序栈的取栈顶元素操作  
GetTop\_Sq(SqStack S, ElemType &e)。

要求实现下列函数：  
Status GetTop\_Sq(SqStack S, ElemType &e);  
/\* 取顺序栈S的栈顶元素到e，并返回OK； */  
/* 若失败，则返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status GetTop_Sq(SqStack S, ElemType &e) {
         
        // Add your code here
        
        if(S.top == 0) return ERROR;
        
        e = S.elem[S.top - 1];
        
        return OK;
    }

# 三、实现顺序栈的出栈操作 #

【题目】试写一算法，实现顺序栈的出栈操作  
Pop\_Sq(SqStack &S, ElemType &e)。

要求实现下列函数：  
Status Pop\_Sq(SqStack &S, ElemType &e);  
/\* 顺序栈S的栈顶元素出栈到e，并返回OK；*/  
/* 若失败，则返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Pop_Sq(SqStack &S, ElemType &e) {
         
        // Add your code here
        
        //判空
        if(S.top == 0) return ERROR;
        
        e = S.elem[S.top - 1];
        
        S.top = S.top - 1;
        
        return OK;
    }

# 四、构建初始容量和扩容增量分别为size和inc的空顺序栈S #

【题目】若顺序栈的类型重新定义如下。试编写算法，构建初始容量和扩容增量分别为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。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status InitStack_Sq2(SqStack2 &S, int size, int inc) {
         
        // Add your code here
        
        S.elem = (ElemType *)malloc(size*sizeof(ElemType));
        
        if(NULL == S.elem||size <= 0||inc <= 0) return ERROR;
        
        S.top = S.elem;//置S为空栈，这里不能写S.top = 0，S.top是指针变量
        
        S.size = size;
        
        S.increment = inc;
        
        return OK;
    }

# 五、实现顺序栈的判空操作 #

【题目】若顺序栈的类型重新定义如下。试编写算法，  
实现顺序栈的判空操作。  
typedef struct \{  
ElemType \*elem; // 存储空间的基址  
ElemType \*top; // 栈顶元素的下一个位置  
int size; // 当前分配的存储容量  
int increment; // 扩容时，增加的存储容量  
\} SqStack2;

要求实现下列函数：  
Status StackEmpty\_Sq2(SqStack2 S);  
/\* 对顺序栈S判空。 */  
/* 若S是空栈，则返回TRUE；否则返回FALSE \*/

#include "allinclude.h"  //DO NOT edit this line
    Status StackEmpty_Sq2(SqStack2 S) {
         
        // Add your code here
        
        return S.top == S.elem;
    }

# 六、实现顺序栈的入栈操作 #

【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的入栈操作。  
typedef struct \{  
ElemType \*elem; // 存储空间的基址  
ElemType \*top; // 栈顶元素的下一个位置  
int size; // 当前分配的存储容量  
int increment; // 扩容时，增加的存储容量  
\} SqStack2;

要求实现下列函数：  
Status Push\_Sq2(SqStack2 &S, ElemType e);  
/\* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/  
/* 将e压入S，返回OK。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Push_Sq2(SqStack2 &S, ElemType e) {
         
        // Add your code here
        
        ElemType *newbase;
        
        //if(S.increment <= 0) return ERROR;//可有可无
        
        if(*(S.top) >= S.size){
        
          
          newbase = (ElemType *)realloc(S.elem,(S.size + S.increment)*sizeof(ElemType));
          
          if(!newbase) return ERROR;
        
          S.elem = newbase;
          
          S.size += S.increment;
        }
        
        *(S.top) = e;//由于S.top也是指针（地址），故不用写S.elem[]
        
        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。\*/

#include "allinclude.h"  //DO NOT edit this line
    Status Pop_Sq2(SqStack2 &S, ElemType &e) {
         
        // Add your code here
        
        //判空
        if(S.top == S.elem) return ERROR;
        
        e = *(S.top - 1);
        
        S.top--;//出栈后栈顶位标要下移
        
        return OK;
    }

# 八、借助辅助栈，复制顺序栈S1得到S2 #

【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。  
Status CopyStack\_Sq(SqStack S1, SqStack &S2)。

要求实现下列函数：  
Status CopyStack\_Sq(SqStack S1, SqStack &S2);  
/\* 借助辅助栈，复制顺序栈S1得到S2。 */  
/* 若复制成功，则返回TRUE；否则FALSE。 \*/

顺序栈的类型定义为：  
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

#include "allinclude.h"  //DO NOT edit this line
    Status CopyStack_Sq(SqStack S1, SqStack &S2) {
         
        // Add your code here
        
        SqStack S0;//创建辅助栈
        
        InitStack_Sq(S0,S1.size,S1.increment);//初始化辅助栈
        InitStack_Sq(S2,S1.size,S1.increment);
        
        S0.top = 0;//把辅助栈置空
        S2.top = 0;
        
        int i,l;
        ElemType e;
        
        l = S1.top;//用l记住S1原始的元素个数，因为下面用Pop_Sq函数后，top会改变
        
        if(StackEmpty_Sq(S1)) return TRUE;
        
        //先把S1复制到S0
        for(i = 0;i < l;i++){
        
          
          Pop_Sq(S1,e);
          Push_Sq(S0,e);
        }
        
        //在把辅助栈S0复制到S2
        for(i = 0;i < l;i++){
        
          
          Pop_Sq(S0,e);
          Push_Sq(S2,e);
        }
        
        DestroyStack_Sq(S0);
        
        return TRUE;
    }

# 九、求循环队列的长度 #

【题目】试编写算法，求循环队列的长度。  
循环队列的类型定义为：  
typedef struct \{  
ElemType \*base; // 存储空间的基址  
int front; // 队头位标  
int rear; // 队尾位标，指示队尾元素的下一位置  
int maxSize; // 最大长度  
\} SqQueue;

要求实现下列函数：  
int QueueLength\_Sq(SqQueue Q);  
/\* 返回队列Q中元素个数，即队列的长度。\*/

#include "allinclude.h"  //DO NOT edit this line
    int QueueLength_Sq(SqQueue Q) {
         
        // Add your code here
        
        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。 */  
Status DeCQueue(CTagQueue &Q, ElemType &x);  
/* 将队列Q的队头元素退队到x，并返回OK；*/  
/* 若失败，则返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    
    //入队
    Status EnCQueue(CTagQueue &Q, ElemType x) {
         
        // Add your code here
        
        if(Q.tag == 1&&Q.front == Q.rear) return ERROR;
        
        Q.elem[Q.rear] = x;
        Q.rear = (Q.rear + 1)%MAXQSIZE;
        
        Q.tag = 1;
        
        return OK;
    }
    
    //出队
    Status DeCQueue(CTagQueue &Q, ElemType &x){
        
      
      if(Q.tag == 0&&Q.front == Q.rear) return ERROR;
      
      x = Q.elem[Q.front];
      Q.front = (Q.front + 1)%MAXQSIZE;
      
      Q.tag = 0;
      
      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。 */  
Status DeCQueue(CLenQueue &Q, ElemType &x);  
/* 将队列Q的队头元素退队到x，并返回OK；*/  
/* 若失败，则返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    
    //入队
    Status EnCQueue(CLenQueue &Q, ElemType x) {
         
        // Add your code here
        
        if(Q.elem == NULL||Q.length == MAXQSIZE) return ERROR;
        
        Q.elem[Q.rear+1] = x;
        
        Q.rear = (Q.rear+1)%MAXQSIZE;
        
        Q.length = Q.length+1;
        
        return OK;
    }
    
    //出队
    Status DeCQueue(CLenQueue &Q, ElemType &x){
        
        // Add your code here
        
        if(Q.elem == NULL||Q.length == 0) return ERROR;
        
        if(Q.rear >= Q.length-1) x = Q.elem[Q.rear-Q.length+1];
        else x = Q.elem[MAXQSIZE+1-Q.length+Q.rear];
        
        Q.length = Q.length-1;
        
        return OK;
    }

# 十二、利用循环队列编写求k阶斐波那契序列中第n+1项fn的算法 #

【题目】已知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 \*/

#include "allinclude.h"  //DO NOT edit this line
    long Fib(int k, int n) {
         
        // Add your code here
        
        //if(k < 2||n < -1) return 0;
        
        int sum,i,j;
        SqQueue *Q = (SqQueue *)malloc(sizeof(SqQueue));
        
        //初始化队列Q
        Q->maxSize = n+2;
        Q->base = (ElemType *)malloc(Q->maxSize*sizeof(ElemType));
        //if(NULL == Q.base) return 0;..
        Q->rear = Q->front = 0;
        
        if(n+1 < k) return 0;
        else{
        
          
          if(n+1 == k) return 1;
          else{
        
            
            for(i = 0;i < k-1;i++){
        
              
              Q->base[Q->rear] = 0;
              Q->rear++;
            }
            
            Q->base[k-1] = 1;
            Q->rear = Q->rear+1;
            
            for(i = k;i <= n;i++){
        
              
              sum = 0;
              
              for(j = i-k;j < i;j++) sum += Q->base[j];
              
              Q->base[i] = sum;
              Q->rear = Q->rear+1;
            }
            }
          }
    
          return Q->base[n];
    }

# 十三、试写一个比较A和B大小的算法 #

【题目】设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 \*/

#include "allinclude.h"  //DO NOT edit this line
    char Compare(SqList A, SqList B) {
         
        // Add your code here
        
        int L,i;
        
        L = (A.length < B.length)?A.length:B.length;
        
        for(i = 0;i < L;i++){
        
          
          if(A.elem[i] == B.elem[i]) continue;
          else break;
        }
        
        //刚好遍历完长度较小那个表
        if(i == L){
        
          
          if(B.length == A.length) return '=';
          else 
          if(L == A.length) return '<';
          else return '>';
        }else{
        //没遍历完
          
          if(A.elem[i] > B.elem[i]) return '>';
          else return '<';
        }
    }

# 十四、试写一算法，实现顺序表的就地逆置 #

【题目】试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。

顺序表类型定义如下：  
typedef struct \{  
ElemType \*elem;  
int length;  
int size;  
int increment;  
\} SqList;

实现下列函数：  
void Inverse(SqList &L);

#include "allinclude.h"  //DO NOT edit this line
    void Inverse(SqList &L) {
         
        // Add your code here
        
        ElemType t;
        
        for(int i = 0;i < L.length/2;i++){
        
          
          t = L.elem[i];
          L.elem[i] = L.elem[L.length-i-1];
          L.elem[L.length-i-1] = t;
        }
    }

# 十五、试写一算法，求并集A＝A∪B #

【题目】假设有两个集合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, List Lb)。

#include "allinclude.h"  //DO NOT edit this line
    void Union(SqList &La, List Lb){
         
        // Add your code here
        
        int lb,i;
        ElemType m;
        
        lb = ListLength_Sq(Lb);
        
        for(i = 1;i <= lb;i++){
        //i从1到lb开始，不是从0开始
          
          GetElem_Sq(Lb,i,m);
          
          if(Search_Sq(La,m) == -1) Append_Sq(La,m);
          else continue;
        }
    }

# 十六、试写一算法，实现链栈的判空操作 #

【题目】试写一算法，实现链栈的判空操作。  
链栈的类型定义为：  
typedef struct LSNode \{  
ElemType data; // 数据域  
struct LSNode \*next; // 指针域  
\} LSNode, \*LStack; // 结点和链栈类型

要求实现下列函数：  
Status StackEmpty\_L(LStack S);  
/\* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE \*/

#include "allinclude.h"  //DO NOT edit this line
    Status StackEmpty_L(LStack S){
         
        // Add your code here
        
        return S == NULL;
    }

# 十七、试写一算法，实现链栈的取栈顶元素操作 #

【题目】试写一算法，实现链栈的取栈顶元素操作。  
链栈的类型定义为：  
typedef struct LSNode \{  
ElemType data; // 数据域  
struct LSNode \*next; // 指针域  
\} LSNode, \*LStack; // 结点和链栈类型

要求实现下列函数：  
Status GetTop\_L(LStack S, ElemType &e);  
/\* 取链栈S的栈顶元素到e，并返回OK; */  
/* 若S是空栈，则失败，返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status GetTop_L(LStack S, ElemType &e){
         
        // Add your code here
        
        LStack t;
        
        if(!S) return ERROR;
        
        t = S;
        e = S->data;
        S = S->next;
        //free(t);不知道为啥写free就不行
        t = NULL;
        
        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。\*/

#include "allinclude.h"  //DO NOT edit this line
    Status QueueEmpty_LQ(LQueue Q){
         
        // Add your code here
        
        return !Q.front&&!Q.rear;
    }

# 十九、实现链队列的求队列长度操作 #

【题目】试写一算法，实现链队列的求队列长度操作。

要求实现下列函数：  
int QueueLength\_LQ(LQueue Q);  
/\* 求链队列Q的长度并返回其值 \*/

#include "allinclude.h"  //DO NOT edit this line
    int QueueLength_LQ(LQueue Q){
         
        // Add your code here
        
        QueuePtr p;
        int sum = 0;
        
        p = Q.front;
        
        while(p){
        
          
          sum++;
          p=p->next;
        }
        
        return sum;
    }

# 二十、编写队列初始化、入队列和出队列的算法 #

【题目】假设以带头结点的循环链表表示队列，并且  
只设一个指针指向队尾元素结点(注意不设头指针)，  
试编写相应的队列初始化、入队列和出队列的算法。

带头结点循环链队列CLQueue的类型定义为：  
typedef struct LQNode \{  
ElemType data;  
struct LQNode \*next;  
\} LQNode, \*CLQueue;

实现下列函数：  
Status InitCLQueue(CLQueue &rear); // 初始化空队列  
Status EnCLQueue(CLQueue &rear, ElemType x); // 入队  
Status DeCLQueue(CLQueue &rear, ElemType &x); // 出队

#include "allinclude.h"  //DO NOT edit this line
    Status InitCLQueue(CLQueue &rear){
        //初始化 
        // Add your code here
        
        rear = (CLQueue)malloc(sizeof(CLQueue));
        if(NULL == rear) return ERROR;
        
        rear->next = rear;//因为是循环链表，所以不是rear->next = NULL
        
        return OK;
    } 
    
    Status EnCLQueue(CLQueue &rear, ElemType x){
        //入队 
        // Add your code here
        
        CLQueue p;
        p = (CLQueue)malloc(sizeof(CLQueue));
        
        if(NULL == p) return ERROR;
        
        p->data = x;
        p->next = rear->next;//因为是循环链表，所以不可以写p->next = NULL:
        
        rear->next = p;
        rear = p;
        
        return OK;
    }
    
    Status DeCLQueue(CLQueue &rear, ElemType &x){
        //出队 
        // Add your code here
        
        CLQueue p;
        
        if(rear == rear->next) return ERROR;//判空操作，不是用NULL
        
        p = rear->next->next;
        rear->next->next = p->next;
        x = p->data;
        p = NULL;
        
        return OK;
    }

# 二十一、实现带头结点单链表的判空操作 #

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

单链表的类型定义为：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList; // 结点和结点指针类型

要求实现下列函数：  
Status ListEmpty\_L(LinkList L);  
/\* 判定带头结点单链表L是否为空链表。 */  
/* 若L是空链表，则返回TRUE，否则FALSE。\*/

#include "allinclude.h"  //DO NOT edit this line
    Status ListEmpty_L(LinkList L){
         
        // Add your code here
        
        return !L||!L->next;
    }

# 二十一、实现带头结点单链表的销毁操作 #

【题目】试写一算法，实现带头结点单链表的销毁操作。

单链表的类型定义为：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList; // 结点和结点指针类型

要求实现下列函数：  
Status DestroyList\_L(LinkList &L);  
/\* 销毁带头结点单链表L，并返回OK。\*/

#include "allinclude.h"  //DO NOT edit this line
    Status DestroyList_L(LinkList &L){
         
        // Add your code here
        
        LinkList p,q;
        
        p = L->next;
        
        if(!p){
        
          
          //free(L);
          L = NULL;
          return OK;
        }
        
        while(p){
        
          
          q = p;
          p = p->next;
          free(q);
        }
        
        L = NULL;
        
        //free(L);
        return OK;
    }

# 二十二、实现带头结点单链表的清空操作 #

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

单链表的类型定义为：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList; // 结点和结点指针类型

要求实现下列函数：  
Status ClearList\_L(LinkList &L);  
/\* 将带头结点单链表L置为空表，并返回OK。*/  
/* 若L不是带头结点单链表，则返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status ClearList_L(LinkList &L){
         
        // Add your code here
        
        if(!L) return ERROR;
        
        LinkList p,q;
        
        p = L->next;
        
        //把后面的结点销毁，以免浪费内存
        while(p != NULL){
        
          
          q = p;
          p = p->next;
          free(q);
        }
        
        L->next = NULL;
        
        return OK;
    }

# 二十三、实现带头结点单链表的求表长度操作 #

【题目】试写一算法，实现带头结点单链表的求表长度操作。

单链表的类型定义为：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList; // 结点和结点指针类型

要求实现下列函数：  
int ListLength\_L(LinkList L);  
/\* 求带头结点单链表L的长度，并返回长度值。*/  
/* 若L不是带头结点单链表，则返回-1。 \*/

#include "allinclude.h"  //DO NOT edit this line
    int ListLength_L(LinkList L){
         
        // Add your code here
        
        if(!L) return -1;
        
        int sum = 0;
        LinkList p;
        
        p = L->next;
        
        while(p != NULL){
        
          
          sum++;
          p = p->next;
        }
        
        return sum;
    }

# 二十四、在带头结点单链表L插入第i元素e #

【题目】试写一算法，在带头结点单链表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。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Insert_L(LinkList L, int i, ElemType e){
         
        // Add your code here
        
        LinkList p = L;
        LinkList q,m;
        int sum = 0;
        
        if(!L||i<1) return ERROR;
        
        while(p&&sum < i){
        
          
          q = p;//用q记住p前一个结点
          p = p->next;
          
          sum++;
        }
        
        if(sum < i) return ERROR;
        
        m->data = e;
        q->next = m;
        m->next = p;
          
        return OK;
    }

# 二十五、在带头结点单链表删除第i元素到e #

【题目】试写一算法，在带头结点单链表删除第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。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Delete_L(LinkList L, int i, ElemType &e){
         
        // Add your code here
        
        if(!L||!L->next||i < 1) return ERROR;
        
        LinkList p,q;
        int sum = 0;
        
        p = L;
        
        while(p->next != NULL&&sum < i){
        
          
          q = p;
          p = p->next;
          
          sum++;
        }
        
        if(sum < i) return ERROR;
        
        e = p->data;
        q->next = p->next;
        p = NULL;
        
        return OK;
    }

# 二十六、在带头结点单链表的第i元素起的所有元素从链表移除，并构成一个带头结点的新链表 #

【题目】试写一算法，在带头结点单链表的第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。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Split_L(LinkList L, LinkList &Li, int i){
         
        // Add your code here
        
        Li = (LinkList)malloc(sizeof(LinkList));//要先给新头结点申请空间
        
        if(!L||!L->next||i < 1){
        
          
          Li = NULL;
          return ERROR;
        }
        
        int sum = 0;
        LinkList p,q;
        
        p = L;
        
        while(p->next&&sum < i){
        
          
          q = p;
          p = p->next;
          
          sum++;
        }
        
        if(sum < i){
        
          
          Li = NULL;
          return ERROR;
        }
        
        Li->next = p;
        q->next = NULL;
        
        return OK;
    }

# 二十七、试写一算法，在带头结点单链表删除第i元素起的所有元素 #

【题目】试写一算法，在带头结点单链表删除第i元素起的所有元素。

带头结点单链表的类型定义为：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList;

实现下列函数：  
Status Cut\_L(LinkList L, int i);  
/\* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/  
/* 若参数不合理，则返回ERROR。 \*/

#include "allinclude.h"  //DO NOT edit this line
    Status Cut_L(LinkList L, int i){
         
        // Add your code here
        
        if(!L||!L->next||i < 1) return ERROR;
        
        LinkList p,q,m;
        int sum = 0;
        
        p = L;
        
        while(p->next&&sum < i){
        
        
          q = p;
          p = p->next;
          sum++;
        }
        
        if(sum < i) return ERROR;
        
        //把i后面的结点删除掉
        while(p != NULL){
        
          
          m = p;
          p = p->next;
          
          m = NULL;
        }
        
        q->next = NULL;
    
        return OK;
    }

# 二十八、删除带头结点单链表中所有值为x的元素 #

【题目】试写一算法，删除带头结点单链表中所有值为x的元素，并释放被删结点空间。

单链表类型定义如下：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList;

实现下列函数：  
Status DeleteX\_L(LinkList L, ElemType x);  
/\* 删除带头结点单链表L中所有值为x的元素， */  
/* 并释放被删结点空间，返回实际删除的元素个数。\*/

#include "allinclude.h"  //DO NOT edit this line
    Status DeleteX_L(LinkList L, ElemType x) {
         
        // Add your code here
        
        LinkList p;
        
        p = L;
        
        if(!p||!p->next) return ERROR;
        
        LinkList m;
        int sum = 0;
        
        while(p->next){
        
          
          m = p;
          
          if(m->next->data == x){
        
            
            m = m->next;
            p->next = m->next;
            m = NULL;
            
            sum++;
            
            continue;//删除一个结点后不要后移，不然会漏掉结点
          }
          
          p = p->next;
        }
        
        return sum;
    }

# 二十九、删除带头结点单链表中所有值小于x的元素 #

【题目】试写一算法，删除带头结点单链表中所有值小于x的元素，并释放被删结点空间。

单链表类型定义如下：  
typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList;

实现下列函数：  
Status DeleteSome\_L(LinkList L, ElemType x);  
/\* 删除带头结点单链表L中所有值小于x的元素， */  
/* 并释放被删结点空间，返回实际删除的元素个数。\*/

#include "allinclude.h"  //DO NOT edit this line
    Status DeleteSome_L(LinkList L, ElemType x) {
         
        // Add your code here
        
        if(!L||!L->next) return ERROR;
        
        LinkList p,m;
        int sum = 0;
        
        p = L;
        
        while(p->next){
        
          
          m = p;
          
          if(m->next->data < x){
        
            
            m = p->next;
            p->next = m->next;
            m = NULL;
            
            sum++;
            
            continue;
          }
          
          p = p->next;
        }
        
        return sum;
    }