/**
一、带头结点的顺序表。删除所有值为x的结点，并释放其空间
算法思想：
1.找遍历顺序表，找到值为x的元素,并用k记录其个数
2.删除（移动）
**/
/*法一：遍历顺序表，用k记录x的个数，将其中不为x的元素向前移动k个单位*/
void Del_x(SqList &L,ElemType x){
    int i;
    for(i=0;i
        int k=0;
        if(L.data[i]==x){
            k++;
        }
        else{
            L.data[i-k]=L.data[i];//非x元素向前移动k个单位
        }     
    }
    L.length=L.length-k;
}
/*法二：遍历顺序表，只需保留下不是x的值*/
void Del_x(SqList &L,ElemType x){
    int k=0;
    for(i=0;i         if(L.data[i]!=x){
            L.data[k]=L.data[i]
            k++;
        }   
    }
    L.length=k;
}

/**
二、将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
思想：
将A、B中较小值一次值依次存入C
**/

bool Merge(SqList A,SqList B){
    if(A.length + B.length > C.length) return false;
    int i=0,j=0,k=0;
    while(i
        if(A.data[i] < B.data[j]){
            C.data[k]=A.data[i];
            i++;
            k++;
        }
        else{
            C.data[k]=B.data[j];
            j++;
            k++;
        }
    }
     //如果A中有剩余，依次写入C中
       while(i
        C.data[k++]=A.data[i++];
       }

       while(j
        C.data[k++]=B.data[j++];
       }
       C.length=k;
       return true;
}

/**
三、设计一个高效算法，将顺序表L的所有元素逆置，要求算法空间复杂度为O(1)
思想：第i个数与n-i个数交换即 L.data[i]与L.data[L.length-1-i]交换
**/
法一：常规方法
void reverse(SqList &L){
    ElemType temp;
    for(int i=0;i
        temp =L.data[i];
        L.data[i]=L.data[L.length-1-i];
        L.data[L.length-1-i]=temp;
    }
}
法二：递归（递归空间复杂度不符合O(1)）
void reverse(int *A, int i,int j){
    if(i
        swap(A[i],A[j]);
        reverse(A,i+1;j-1;)
    }
}

/**
四、带头结点的单链表。删除所有值为x的结点，并释放其空间
算法思想：扫描单链表，遇到值为想的结点就将其删除
1.需要三个指针：p：当前结点，pre：p的前驱；q:用来保存p
**/
typedef struct LinkNode{
    int data;
    struct *next;
}LinkNode,*SqList;
void Del_x(LinkList &L, ElemType x){
    LNode *p=L->next, *pre=L, *q;
    while(!p){
        if(p->data==x){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }
        else{//如果不等于x，pre和p都向后移
            pre=p;
            p=p->next;
        }
    }
}

/**
五、从顺序表中删除其值在s与t之间的所有元素，如果s或t不合理或顺序表为空，显示错误信息并返回
思想：
**/
法一：移动
bool Dels_t(SqList &L,int s,int t){
    int k=0;
    for(i=0;i
        if(L.data[i]>=s && L.data[i]<=t){
            k++;
        }else{
            L.data[i-k]=L.data[i];
        }
    }
    L.length -= k;
    return true;
}

法二：保留不在s与t之间的数
 bool Dec_s_t(SqList &L,int s, int t){
    int i=0,k=0;
    if(L.length==0) {
        cout<<"L 不能为空！";
        return false;
    }
    if(s>t) {
        cout<<"s与t输入错误！";
        return false;
    }
    for(i=0;i
        if(L.data[i]<=s ||L.data[i]>=t){
            L.data[k++]=L.data[i]
        }
    }
    L.length=k;
    return true;
}

/**
六、从有序顺序表中删除所有重复元素
思想：利用两个工作指针遍历,不重复就保留，重复就不保留（删除）。
1.首先i指向L.data[0], j指向L.data[1]，
2.如果两数不相同，保留，j后移
  如果相同，不保留，j后移
**/
void del_same(SqList &L){
    for(i=0;j=1;j     if(L.data[i]!=L.data[j]){
        L.data[++i]=L.data[j];//保留之前要i++
    }
}