线性表——数据结构


存储结构

typedef struct{
    ElemType *elem;//存储空间基址
    int length;//当前线性表长度
    int listsize;//当前分配的存储容量
}Sqlist;

初始化线性表(构造一个新的线性表)

Status chushihua(Sqlist &L){
    L.elem=(ElemType *)malloc(list_init_size*sizeof(ElemType));
    if(!L.elem)
        exit(-2);
    L.length=0;
    L.listsize=list_init_size;
    return 1;
}

判断线性表是否为空

Status ListEmpty(Sqlist &L)
{ 
    if(L.length==0)
        return 1;
    else
        return 0;
}

将线性表重置为空表

Status ClearList(Sqlist &L)
{
    L.length=0;
    return 1;
}

遍历线性表

Status visit(ElemType e)
{
    printf("%d ",e);
    return 1;
}

Status ListTraverse(Sqlist &L)
{
    int i;
    for(i=0;i < L.length;i++)
        visit(L.elem[i]);
    printf("\n");
    return 1;
}

在线性表中的第j个位置插入元素

Status init_Sq(Sqlist &L,int j,ElemType e)
{
    int *newbase,*q,*p;
    //在线性表的第j个位置之前插入新的元素e
    // (1<=i<=ListLength_Sq(L)+1)
    if(j<1||j>L.length+1)
        return 0;
    if(L.length>=L.listsize){//当前存储空间已满,增加空间
        newbase=(ElemType *)realloc(L.elem,(L.listsize+newsize)*sizeof(ElemType));
    if(!newbase)
        exit(-2);//存储空间分配失败
    L.elem=newbase;//新的基址
    L.listsize+=newsize;//增加存储容量
    }
    q=&(L.elem[j-1]);//q为插入地址
    for(p=&(L.elem[L.length-1]);p>=q;p--)
        *(p+1)=*p;//插入位置及之后的元素向右移动
    *q=e;
    L.length++;
    return 1;
}//a(Sqlist &L,int i,ElemType e),线性表插入

线性表删除 删除第i个元素

Status delete_Sq(Sqlist &L,int i,ElemType &e){
    //在线性表L中删除第i个元素,并用e返回其值
    //(1<=i<=ListLength_Sq(L))
    int *p,*q;
    if(i<1||i>L.length)
        return 0;
    p=&(L.elem[i-1]);
    e=*p;
    q=L.elem+L.length-1;
    for(++p;p<=q;++p)
        *(p-1)=*p;
    --L.length;
    return 1;
}//delete_Sq

线性表合并

Status MergeList(Sqlist La,Sqlist Lb,Sqlist &Lc)
{
       //已知线性表La和Lb中的数据元素是非递减排列
       //归并La和Lb得到新的线性表Lc,Lc的数据元素也是非递减排列
       int *pa,*pb,*pa_last,*pb_last,*pc;
       pa=La.elem;
       pb=Lb.elem;
       Lc.listsize=Lc.length=La.length+Lb.length;
       pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
       if(!Lc.elem)
              exit(-2);  //内存分配失败
       pa_last=La.elem+La.length-1;
       pb_last=Lb.elem+Lb.length-1;
       while(pa<=pa_last&&pb<=pb_last)  //归并
       {
              if(*pa<=*pb)
                     *pc++=*pa++;
              else
                     *pc++=*pb++;
       }
       while(pa<=pa_last)  //插入A中剩余的元素
       {
              *pc++=*pa++;
       }
       while(pb<=pb_last)  //插入A中剩余的元素
       {
              *pc++=*pb++;
       }
       return 1;
}

声明:May丶乘剑的部落小阁|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 线性表——数据结构


一个偶尔努力、偶尔懈怠的"搬砖"人