顺序表操作（书本）

#include<stdio.h> 
#include<stdlib.h>  
#define OVERFLOW 0  
#define ERROR 0
#define OK  1  
#define LIST_INIT_SIZE  10 
#define LISTINCREMENT  10  
typedef int Status;
typedef int ElemType;
typedef struct{  
    ElemType *elem;  
    int length;  
    int listsize;  
}SqList;  
/////////////////初始化函数////////////////////////////////////////////////////////////// 
Status InitList_Sq(SqList &L){    //顺序表的初始化
    L.elem =(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));  
    if(!L.elem ) exit(OVERFLOW);  
    L.length =0;  
    L.listsize=LIST_INIT_SIZE;  
    return OK;  
}   
/////////////////插入函数/////////////////////////////////////////////////////////////// 
Status ListInsert_Sq(SqList &L,int i,ElemType e){    //顺序表插入 
    //在顺序表L中第i个位置之前插入新的元素e
    
    if(i<1||i>L.length+1){    //i值不合法 
        printf("插入时位置不合法\n");
        return ERROR;
    } 

    if(L.length>=L.listsize){    //如果顺序表已经存满，则增加分配 
         ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
         if(!newbase){    //存储分配失败 
             exit(OVERFLOW);
         }
         L.elem=newbase;
         L.listsize+=LISTINCREMENT;
         
        
    }
    
    
    ElemType *q=&L.elem[i-1];    //插入位置 
    
    for(ElemType *p=&L.elem[L.length-1];p>=q;--p){     

        *(p+1)=*p;

    }
    
    *q=e;
    ++L.length;
    printf("插入后顺序表为：\n");
    for(int i=0;i<L.length;i++){
        printf("%d  ",L.elem[i]);
    }
    
    return OK;
} 

/////////////////删除函数/////////////////////////////////////////////////////////// 

Status ListDelete_Sq(SqList &L,int i,ElemType &e){    //删除第i个元素，并用e返回其值 
    if(i<1||i>L.length){    //i值不合法 
        printf("删除时位置不合法\n");
        return ERROR;
    } 
    ElemType *p=&(L.elem[i-1]);    //p为被删除元素的位置 
    e=*p;    //被删除的元素赋给e 
    printf("\n被删除的是%d\n",e);
    //ElemType *q=L.elem+(L.length-1)*sizeof(ElemType);    //表尾元素的位置  这个是错误的，因为指针的偏移本来就会乘类型所占字节数的，这就是指针为什么会有类型 
    ElemType *q=L.elem+L.length-1;    //表尾元素的位置 
    for(++p;p<=q;++p){    //被删除元素后的元素左移 
        *(p-1)=*p;
    } 
    --L.length;
    
    printf("\n删除后顺序表为：\n");
    for(int i=0;i<L.length;i++){
        printf("%d  ",L.elem[i]);
    }
    
    return OK; 
} 
/////////////////合并函数/////////////////////////////////////////////////////////// 

Status MergeList_Sq(SqList &La,SqList &Lb){    //合并有序表La和Lb至La中
    if(La.elem==NULL||Lb.elem==NULL) {    //判断两表是否存在 
        return ERROR;
    }
    
    
    La.elem=(ElemType *)realloc(La.elem,(La.length+Lb.length)*sizeof(ElemType));
    if(!La.elem||!Lb.elem) exit(OVERFLOW); 
    La.listsize=La.length+Lb.length;
                                                                                        
    for(int i=0,j=0;j<Lb.length;    ){
        if(La.elem[La.length-1-i]>Lb.elem[Lb.length-1-j]&&La.length-1-i>-1){    //La.length-1-i>-1这个条件是防止下标小于0 
            La.elem[La.listsize-1-i-j]=La.elem[La.length-1-i];
            i++;
        }
        else{
            La.elem[La.listsize-1-i-j]=Lb.elem[Lb.length-1-j];
//            printf("La.elem[%d]=%d  ",La.listsize-1-j,La.elem[La.listsize-1-i]);
            j++;
        }
    }
    
    La.length=La.length+Lb.length;
    
    printf("\n合并后顺序表为：\n");
    for(int i=0;i<La.length;i++){
        printf("%d  ",La.elem[i]);
    }
    

    
    return OK;
}
















/////////////////主函数////////////////////////////////////////////////////////// 

int main(){  
    printf("\n----------------------------初始化操作---------------------------------\n");
    //////////////顺序表的初始化/////////////////////////
    SqList L;  
    InitList_Sq(L);    //问题：将这条注释掉使用下面两行以后为什么就不再输出0,1,2…… 可能是因为上面一条只是声明结构体，并未向其分配存储空间所以无法赋值 
//    ElemType a[]={0,1,2,3,4,5,6,7,8,9};
//    L.elem=a;
    
    for(int i=0;i<LIST_INIT_SIZE;i++){    //初始化为顺序表赋个值 
         L.elem[i]=i;
         L.length++; 
    }
    
    printf("线性表Sqlist初始化成功\n\n");  
    //system("pause"); 
    printf("初始化为:\n");
    for(int i=0;i<L.length;i++){
        printf("%d  ",L.elem[i]);
    }
    printf("\n");
    
    
    
    
    
    ////////////////////顺序表的插入/////////////////////
    printf("\n----------------------------插入操作-----------------------------------\n");
    ListInsert_Sq(L,2,666);    //在第二个位置插入666 
     
        

     
    
    ///////////////////顺序表的删除//////////////////////
    printf("\n----------------------------删除操作-----------------------------------\n");
     
    ElemType s;    //存放被删除的元素 
    ListDelete_Sq(L,5,s);
     
     
    ///////////////////顺序表的合并//////////////////////
    printf("\n----------------------------合并操作-----------------------------------\n");
    
    ///////先创建两个表并初始化 
    SqList La,Lb;  
    InitList_Sq(La);
    InitList_Sq(Lb);
    for(int i=0;i<LIST_INIT_SIZE;i++){    //初始化为顺序表赋个值 
         La.elem[i]=i*2+1;
         La.length++; 
    }
    for(int i=0;i<LIST_INIT_SIZE;i++){    //初始化为顺序表赋个值 
         Lb.elem[i]=i*2;
         Lb.length++; 
    }
    

    printf("两表分别初始化为:\n");
    for(int i=0;i<La.length;i++){
        printf("%d  ",La.elem[i]);
    }
    printf("\n");
    for(int i=0;i<Lb.length;i++){
        printf("%d  ",Lb.elem[i]);
    }
    printf("\n");
    
    ///////////完成初始化 开始合并 
    
    MergeList_Sq(La,Lb); 
     
     
     
     
     
     
     
     
     
     
     
    printf("\n");
    system("pause"); 
    return 0;  

}