概述

 
#define LIST_INIT_SIZE 100 
#define LIST_INCREMENT 50 

struct SqList 
{
    /* data */
    ElemType* elem; // addr 
    int length; //当前长度
    int listsize; //容量，最大可存长度，以sizeof(ElemType)为单位 
};

    
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
内存中分配连续的空间
然后对这些元素进行查找，增加，删除，插入等操作

 
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <limits.h>
#include <stdio.h>  //aioi(),exit() 

#include <stdlib.h>
// #include <io.h>
#include <math.h>
#include <sys/timeb.h>
#include <stdarg.h>
#define TRUE 1 
#define FALSE 0
#define OK 1 
#define ERROR 1 
#define OVERFLOW -2 //math.h中可能已经定义OVERFLOW的值为3,math.h中是否有这个，要看环境，有的有，有的没有 

typedef int Status;
typedef int Boolean;
typedef int ElemType;


#define LIST_INIT_SIZE 100 
#define LIST_INCREMENT 50 

struct SqList 
{
    /* data */
    ElemType* elem; // addr 
    int length; //当前长度
    int listsize; //容量，最大可存长度，以sizeof(ElemType)为单位 
};



//顺序表在初始化时就初始化了固定的长度,后续这个长度不可更改 
void InitList(SqList &L){
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)
        exit(OVERFLOW);
    L.length =0;
    L.listsize = LIST_INIT_SIZE;
}

void DestroyList(SqList &L){
    free(L.elem);
    L.elem = NULL;
    L.length = 0;
    L.listsize =0;
}

void ClearList(SqList &L){
    L.length = 0;
}

Status ListEmpyt(SqList &L){
    if (L.length ==0){
        return TRUE;
    }else{
        return FALSE;
    }
}


int ListLength(SqList &L){
    return L.length;
}


Status GetItem(SqList &L,int i,ElemType &e){
    if(i<0||i>(L.length -1))
        return ERROR;
    e = *(L.elem + i);
    return OK; 
}


// 定位;把…安置在(或建造于);创办于(某地);确定…的准确地点;找出…的准确位置
// 返回指定元素的索引位置，无返回-1 
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)){

    int i =0;
    ElemType *p = L.elem;
    while(i<(L.length-1) && !compare(*p++,e))
        i++;
    if (i<(L.length-1))
        return i;
    else
        return -1;
}

//从首个等值元素开始
Status PreElem(SqList L,ElemType cur_e,ElemType &pre_e){
    //初始条件：线性表L已存在
    //操作结果：若cur_e是L上的数据元素，且不是第一个，则用pre_e返回它的前驱；否则操作失败，pre_e无定义
    int i = 1;
    ElemType *p = L.elem+1; //第二个元素 
    while(i<=L.length-1 && *p!= cur_e){
        p++;
        i++;
    }
    if (i>=L.length){
        return ERROR;
    }else{
        pre_e = *--p;
        return OK;
    }

}

//从首个等值元素开始
Status NextElem(SqList L,ElemType cur_e,ElemType &pre_e){
    //初始条件：线性表L已存在
    //操作结果：若cur_e是L上的数据元素，且不是第一个，则用pre_e返回它的前驱；否则操作失败，pre_e无定义
    int i = 0;
    ElemType *p = L.elem; //第1个元素 
    while(i<=L.length-1 && *p!= cur_e){
        p++;
        i++;
    }
    if (i>=L.length){
        return ERROR;
    }else{
        pre_e = *++p;
        return OK;
    }

}

Status ListInsert(SqList &L, int i, ElemType e){
    ElemType *newbase,*q,*p;
    // printf("------1");
    if(i<0||i>L.length){
        return ERROR;
    }
    // printf("------2");

    if(L.length == L.listsize){ //容量已满 
    // printf("------3\n");
        newbase = (ElemType *)realloc(L.elem,(LIST_INIT_SIZE+LIST_INCREMENT)*sizeof(ElemType));
        if(!newbase)
            exit(OVERFLOW);
        L.elem = newbase;
    }
    q = L.elem + i;//插入位置
    // printf("before:%d\n",*q);
    for(p=L.elem+L.length-1;p>=q;--p){//向高位移动一位 
        *(p+1) = *p;
    }
    *q = e;
    L.length++;
    return OK; 

}

Status ListDelete(SqList &L, int i, ElemType e){
    ElemType *p,*q;
    if(i<0||i>L.length-1){
        return ERROR;
    }
    p = L.elem + i; 
    e=*p;
    q = L.elem + L.length - 1;
    for(p++;p<=q;p++){
        *(p-1) = *p;
    }
    L.length--;
    return OK;
}


void ListTraverse(SqList L, void(*visit)(ElemType&)){
    ElemType* p = L.elem;
    int i;
    for (i=0;i<L.length;i++)
        visit(*p++);
}


Status equal(ElemType e1,ElemType e2){
    if (e1 == e2 )
        return TRUE;
    else 
        return FALSE;
}


int comp(ElemType a,ElemType b){
    if(a==b)
        return 0;
    else 
        return (a-b)/abs(a-b);
}

void print(ElemType e){
    printf("%d\n",e);
}

void print1(ElemType &e){
    printf("%d",e);
}

void print2(ElemType e){
    printf("%c",e);
}


//平方判断
Status sq(ElemType e1,ElemType e2){
    if(e1==e2*e2){
        return TRUE;
    }else{
        return FALSE;
    }
}

//加倍
void db1(ElemType &e){
    e *=2;
}


int main(){
    SqList L;
    ElemType e,e0;
    Status i;
    int j,k;
    InitList(L);
    printf("init,L.length=%d,L.listsize=%d,L.elem=%d\n",L.length,L.listsize,*L.elem);


    for(j=0;j<5;j++){
        i = ListInsert(L,0,j);
    }
    printf("aftr inster:\n");
    for(j=0;j<5;j++){
        printf("idnex:%d,%d\n",j,*(L.elem+j));
    }



    
    return 0;
}