#include<cstdio>
#define MaxSize 50
typedef int Elemtype;
typedef struct {
    Elemtype data[MaxSize];
    int length;
}SqList;
int main(void)
{
    return 0;
}
*******************************************
#define InitSize 100;
typedef struct {
    ElemType *data;
    int MaxSize,length;
}SqList; 
******************************************* 

bool ListInsert(SqList &L,int i,Elemtype e)
{
    if(i<1 || i>L.length+1) return false;
    if(L.length>=MaxSize) return false;
    for(int j=L.length;j>=i;j--) 
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;    
} 
******************************************** 
bool ListDelete(SqList &L,int i,int e)
{
    if(i<1 || i>L.length) return false;
    e = L.data[i-1];
    for(int j=i;j<L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true; 
}
*******************************************
int LocateElem(SqList L,Elemtype e)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        if(L.data[i]==e) return i+1;    
    }   
    return 0;
} 
******************************************


題目部分：
018頁1題 
bool deleteMin(SqList&L,Elemtype e)//沒有使用引用類型 
{
    if(L.length==0) return false;
    int index=0;
    for(int i=1;i<L.length;i++) 
        if(L.data[i]<L.data[index]) index=i;
    e=L.data[index];
    for(int i=index;i+1<L.length;i++) L.data[i]=L.data[i+1];
    //題目要求是使用最后一個元素填充杨耙，審題嚴重錯誤叹放，粗心 
    L.length--; 
    return true;
}
答案：
bool del_Min(SqList&L,Elemtype &value)
{
    if(L.length==0) return false;
    value = L.data[0];
    int pos=0;
    //這里使用value這個變量進行數(shù)據(jù)暫存可以省略漱逸，使用pos足矣 
    for(int i=1;i<L.length;i++)
        if(L.data[i]<value)
        {
            value = L.data[i];
            pos=i;  
        }
    L.data[pos]=L.data[L.length-1];
    L.length--;
    return true;    
} 
018頁2題
void reverse(SqList&L)
{
    Elemtype temp;
    int len=L.length;
    if(len==0) return ;
    //作為程序已經(jīng)可以藕筋，作為紙質(zhì)的答案，可以參考最簡潔寫法银伟，但差別不大
    for(int i=0;i<=(len-1)/2;i++) 
    {
        temp=L.data[i];
        L.data[i]=L.data[len-i+1];//下標錯誤恭应，fuck 
        L.data[len-i+1]=temp;
    }
} 
答案：
void Reverse(SqList&L)
{
    Elemtype temp;
    for(int i=0;i<L.length;i++) 
    {
        temp = L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=temp;
    }
} 
018頁3題
void deleteX(SqList &L,int n,ElemType x)//按照題目要求用了n 
{
    int k=0;
    for(int i=0;i<n;i++)
        if(L.data[i]!=x) L.data[k++]=L.data[i];
    L.length=k;
}
答案：
void del_1(SqList&L,Elemtype x)
{
    int k=0;
    for(int i=0;i<L.length;i++)
        if(L.data[i]!=x)
        {
            L.data[k]=L.data[i];
            k++;
        }
    L.length=k;
}
void del_2(SqList&L,Elemtype e)
{
    int k=0,i=0;
    while(i<L.length)
    {
        if(L.data[i]==x) k++;
        else L.data[i-k]=L.data[i];
        i++;
    }
    L.length=L.length-k;
}
018頁4題
bool Del(SqList&L,Elemtype s,Elemtype t)
{
    //審題錯誤敛纲，題目是有序表 
    int k=0;
    if(L.length==0) return false;
    if(s>=t) return false;
    for(int i=0;i<L.length;i++) 
    {
        if(L.data[i]>=s && L.data[i]=<t) ;
        else L.data[k++]=L.data[i]; 
    }
    L.length=k;
    return true;
}
答案：
void Del(SqList &L,Elemtype s,Elemtype t)
{
    int i,j;
    if(s>=t || L.length==0) return false;
    for(i=0;i<L.length&&L.data[i]<s;i++) ;
    if(i>=L.length) return false;
    for(j=i;j<L.length&&L.data[j]<=t;j++) ;
    for(;j<L.length;j++,i++) 
        L.data[i]=L.data[j];
    L.length=i;
    return true;
} 
018頁5題
void Del(SqList&L,Elemtype s,Elemtype t)
{
    int k=0,i=0;
    if(L.length==0 || s>=t ) return false;
    for(i=0;i<L.length;i++) 
        if(L.data[i]<s || L.data[i]>t)
            L.data[k++]=L.data[i];
    L.length=k;
    return true;
}
答案：
bool Del(SqList&L,Elemtype s,Elemtype t)
{
    int k=0,i=0;
    if( L.length==0 || s>=t ) return false;
    for(int i=0;i<L.length;i++)
        if(L.data[i]>=s && L.data[i]<=t ) k++;
        else L.data[i-k]=L.data[i];
    L.length-=k;
    return true;
}
018頁6題
void removeRepeat(SqList&L)
{
    int k=1; 
    if(L.length==0) return ;
    for(int i=1;i<L.length;i++)
    {
        if(L.data[i]!=L.data[k-1])
            L.data[k++]=L.data[i];
    }
    L.length=k;
}
答案：
bool Delete_Same(SqList &L)
{
    if(L.length==0) return false;
    int i,j;
    for(i=0,j=1;j<L.length;j++)
        if(L.data[i]!=L.data[j])
            L.data[++i]=L.data[j];
    L.length=i+1;
    return true; 
} 
018頁7題
//返回數(shù)值可以提倡使用引用類型 
SqList union(SqList&L1,SqList&L2)
{
    SqList L;
    int i=0,j=0;
    L.length=0;
    while(i<L1.length && j<L2.length) 
    {
        if(L1.data[i]<=L2.data[j]) L.data[L.length++]=L1.data[i++];
        else L.data[L.length++]=L2.data[j++];
    }
    while(i<L1) L.data[L.length++]=L1.data[i];
    while(j<L2) L.data[L.length++]=L2.data[j];
    return L;
}
答案：
bool Merge(SqList A,SqList B,SqList &C)
{
    //  自己沒有進行這個判斷，因為忽略了會超出范圍這個錯誤
    //  原因：記住線性表的三個重要的元素
    //  1.首地址2.存儲空間的大小3.表長 
    if(A.length+B.length>C.MaxSize) return false;
    //線性表處理需要注意存儲空間的大小
    
    int i=0,j=0,k=0; 
    while( i<A.length && j<B.length )
    {
        if(A.data[i]<=B.data[j]) C.data[k++]=A.data[i++];
        else C.data[k++]=B.data[j++];
    }
    
    while( i<A.length ) C.data[k++]=A.data[i++];
    while( j<B.length ) C.data[k++]=B.data[j++];
    
    C.length=A.length + B.length;
    //  C.length=k; 備用寫法    
    return true;
}
018頁8題
bool Exchange(int A[],int m,int n)
{
    //  int B[]=new int[m+n]; 
    int* B = (int*)malloc( (m+n) * sizeof(int) );
    
    //  如果分配失敗像云，返回false
    if( B == NULL ) return false;
    
    //  保存數(shù)據(jù)到B數(shù)組     
    for(int i=0;i<m+n;i++) B[i]=A[i];
    
    //  把題目中的b1-bn 放到前面 
    for(int i=m;i<m+n;i++) A[i-m]=B[i];
    
    // 把題目中的a1-am放到后面 
    for(int i=0;i<m;i++) A[i+n]=B[i];
    
    return true;
    
} 
答案：
typedef int DataType;
//考場不寫typedef盡量锌雀，不形象
//這里使用bool作為返回值更好 
void reverse(DataType A[],int left,int right,int arraySize)
{
    if(left >= right || right >= arraySize ) return ;
    int mid = (left+right)/2;
    for(int i=0;i<=mid-left;i++)
    {
        DataType temp = A[left+i];
        A[left+i]=A[right-i];
        A[right-i]=temp;            
    }  
} 
void Exchange(DataType A[],int m,int n,int arraySize)
{
    reverse(A,0,m+n-1,arraySize);
    reverse(A,0,n-1,arraySize);
    reverse(A,n,m+n-1,arraySize);
}
018頁9題
//  牢記三要素 
bool find(SqList &L,ElemType x)
{
    if( L.length == 0 ) return false;
    
    int left=0,right=L.length-1;
    //這里考慮復雜了，題目是找到迅诬，但是沒有要求是第一個的Ｒ改妗！３薮３颓浮！ 
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(L.data[mid]<=x) L=mid+1;
        if(L.data[mid]>x) R=mid-1;  
    } 
    //這里的思路全部錯了俏蛮，什么垃圾代碼撑蚌，我靠 
    if( L.data[right] == x ) 
    {
        //  如果是最后一個元素 
        if( right==L.length-1)
        {
            return false;
        }
        else 
        {
            //   如果不能繼續(xù)插入數(shù)據(jù) 
            if( L.length>=L.MaxSize ) return false;
            else 
            {
                //移動元素 
                for(int i=L.length;i>right;i--) 
                    L.data[i]=L.data[i-1];
                L.data[right]=x;
                L.length++;
            }
        }
    }
    return true;
}
答案：
void SearchExchangeInsert(ElemType A[],ElemType x)
{
    //  這里最好能夠有一個參數(shù)n 
    int low=0,high=n-1,mid;
    
    while(low<=high)
    {
        mid=(low+high)/2;
        if(A[mid]==x) break;
        else if( A[mid] > x ) low=mid+1;
        else high = mid -1;
    } 
    
    if(A[mid]==x && mid!=n-1)
    {
        ElemType temp=A[mid];
        A[mid]=A[mid+1];
        A[mid+1]=temp;  
    } 
    
    if(low>high)//說明退出while循環(huán)不是因為break 
    {
        for(int i=n-1;i>high;i--) A[i+1]=A[i];
        A[i+1]=x;
    }
} 
018頁10題
方法一：
bool reverse(ElemType A[],int L,int R)
{
    if( L > R ) return false;
    
    int mid=(L+R)/2;
    for(int i=0;i<=mid-L;i++)
    {
        ElemType tmp;
        tmp = A[left+i];
        A[left+i]=A[right-i];
        A[right-i]=tmp;
    }   
    return true;
} 
void leftp(ElemType A[],int n)
{
    //沒有答案那么的方便 
    reverse(A,0,n-1);
    reverse(A,0,n-p-1);
    reverse(A,n-p,n-1);
}
答案：
void reverse(int R[],int from,int to)
{
    int i,temp;
    for(i=0;i<(to-from+1)/2;i++)
    {
        temp=R[from+i],R[from+i]=R[to-i],R[to-i]=temp;
    }
}
void Converse(int R[],int n,int p)
{
    reverse(R,0,p-1);
    reverse(R,p,n-1);
    reverse(R,0,n-1);
}
018頁11題
//  時間復雜度0(n) 
bool midNumber(ElemType A[],ElemTypde B[],int m,int n,ElemType& ans)
{
    if( n==0 || m == 0 ) return false;
    int mid = (m+n+1) / 2 , cnt = 0 , i = 0 , j = 0 ;
    while( i<m && j<n && cnt<mid )
    {
        if(A[i]<B[j])
        {
            cnt++;
            if(cnt==mid) ans=A[i];
            i++;
        }
        else 
        {
            cnt++;
            if(cnt==mid) ans=B[j];
            j++;
        }
    }
    while(i<m && cnt<mid )
    {
        cnt++;
        if(cnt==mid) ans=A[i]; 
        i++;
    }
    while(j<n && cnt<mid )
    {
        cnt++;
        if(cnt==mid) ans=B[j];
        j++;
    }
    return true;
} 
答案：
int M_search(int a,int b,int n)
{
    int s1=0 , s2=0 , d1=n-1 , d2=n-1 , m1 , m2;
    while( s1!=d1 || s2!=d2 )
    {
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(a[m1]==b[m2]) return a[m1];
        else if(a[m1]<b[m2])
        {
            if( (d1-s1)%2 == 0 )
            {
                s1=m1;
                d2=m2;
            }
            else
            {
                s1=m1+1;
                d2=m2;
            }
        }
        else if(a[m1]>b[m2])
        {
            if( (d2-s2)%2 == 0)
            {
                s2=m2;
                d1=m1;  
            } 
            else
            {
                d1=m1;
                s2=m2+1;    
            } 
        }
    }
    return A[s1]<B[s2]?A[s1]:B[s2];
}
018頁12題
int Find(int A[],int n)
{
    if( n==0 ) return -1;
    
    int* B = (int*)malloc( n * sizeof(int) );
    
    for(int i=0;i<n;i++) B[i]=0;
    for(int i=0;i<n;i++)
    {
        B[A[i]]++;
        if(B[A[i]]>n/2) return A[i];
    }
    return -1;
}
答案：
int major(int A[],int n)
{
    int i,c,count=1;
    c=A[0];
    for(i=1;i<n;i++)
    {
        if(A[i]==c) count++;
        else
        {
            if(count>0) count--;
            else
            {
                c=A[i];
                count=1;
            }
        }
    }
    if(count>0)
    {
        for(i=count=0;i<n;i++)
            if(A[i]==c) count++;
    }
    if(count>n/2) return c;
    return -1;
}