数据结构——线性表

定义

//顺序表的的静态分配
#define MaxSize 10                //定义最大长度
typedef struct{
    ElemType data[MaxSize];       //用静态“数组”存放数据元素
    int length;                   //顺序表的当前长度
}SqList;                          //顺序表的类型定义

//初始化       
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;            //将所有数据元素设初值0
    L.length=0;                 //顺序表初试长度为0
}

int main(){
    SqList L;                   //声明一个顺序表
    InitList(L);                //初始化顺序表
    ....
    reurn 0;
}

//顺序表的动态分配
#define InitSize 10             //顺序表的初始长度
typedef struct{
    ElemType *date;             //用静态“数组”存放数据元素
    int MaxSize;                //顺序表的最大容量
    int length;                 //顺序表的当前长度
}SeqList;                       //顺序表的类型定义

//初始化
void InitList(SeList &L){
    L.date=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
    int *p=L.data;
    L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0;i<L.length; i++){
        L.data[i]=p[i];         //malloc是在内存中申请一个新的内存区域，所以把数据复制到新的区域上
    }
    L.MaxSize=l.MaxSize+len;
    free(p);                    //释放旧的内存区域
}

---

插入

//在L的位序i处插入元素e
bool ListInsert(SqList &L,int i,int e){
    if(i<1||i>L.length+1)                 //判断i的范围是否有效
        return false;
    if(L.length>=MaxSize)                 //当前存储空间已满。不能插入
        return false;
    for(int j=L.length;J>=i;j--)          //将第i个元素以及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;                        //在位置i处放入e
    l.length++;                           //长度+1
    return ture;
}

最好情况 O(1)
最坏情况 O(n)
平均情况 O(n)

---

删除

//删除表L中第i个位置元素，并返回给e
bool ListDelete(SqList &L,int i,int &e){
    if(i<1||i>L.length)                 //判断i的范围是否有效
       return false;
    e=L.data[i-1];                      //将被删除的元素赋值给e
    for(int j=i;j<l.length;i++)         //将第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    l.length--;                         //线性表长度-1
    return ture;
}

最好情况 O(1)
最坏情况 O(n)
平均情况 O(n)

---

查找

//按位查找,静态分配与动态分配一致
ElemType GetElem(SeqList L,int i){
    return L.data[i-1];
}

//按值查找
int LocateElem(SeqList L,int e){
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

最好情况 O(1)
最坏情况 O(n)
平均情况 O(n)