数据结构-线性表的顺序存储

2017-06-25

线性表的顺序存储-顺序表

线性表-数据结构

线性表-静态分配

#define MaxSize 50	//顺序表的最大长度
typedef struct{
	ElemType data[MaxSize];	//顺序表的元素
	int length;	//顺序表当前长度
}SqList;	//顺序表的类型定义

线性表-动态分配

#define InitSize 100	//顺序表的初始定义
typedef struct{
	ElemType *data;	//指示动态分配数组的指针
	int MaxSize,length;	//数组的最大容量和当前个数
}SeqList;	//动态分配数组顺序表的类型定义

线性表-初始化

线性表-静态分配

SqList *CreateSqList(){
    SqList *sq = (SqList *)malloc(sizeof(SqList));
    sq->length = 0;
    return sq;
}

线性表-动态分配

SeqList *CreateSeqList(){
    SeqList *seq = (SeqList *)malloc(sizeof(SeqList));
    seq->data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
    seq->length = 0;
    seq->SqMaxSize = InitSize;
    return seq;
}

线性表-插入

//输入下标为负数，则在末尾插入
void SeqListInsert(SeqList &L,int i,ElemType e){
    if(i>L.length){
        printf("插入下标超出实际长度");
    }
    if(i < 0){
        i = L.length;
    }
    //顺序表存储单元已满，重新分配内存，非动态分配则没有这一步，空间满则不能插入
    if(L.length == L.SqMaxSize){
        ElemType *seq = (ElemType *)realloc(L.data,(InitSize+1)*sizeof(ElemType));
        L.data = seq;
        L.SqMaxSize = InitSize+1;
    }
    //寻找到位置后，将后面的元素位置往后挪
    for(int j = L.length; j > i;j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i] = e;
    L.length++;
}

线性表-删除

//输入下标为负数，则删除值为元素e的内容，否则删除下标为i的内容，并返回e
void SeqListDelete(SeqList &L,int i,ElemType &e){
    if(i>L.length){
        printf("插入下标超出实际长度");
    }
    if(i < 0){
        for(int j = 0;j < L.length;j++){
            if(L.data[j] == e){
                for(int k = j; k < L.length;k++){
                    L.data[k] = L.data[k+1];
                }
                L.length--;
            }
        }
    }else{
        e = L.data[i];
        for(int j = i; j < L.length;j++){
            L.data[j] = L.data[j+1];
        }
        L.length--;
    }
}

线性表-查找

//查找内容为e的元素，返回下标数组
int *SeqListSearch(SeqList &L,ElemType &e){
	int index[20];
    int k = 0;
    for(int j = 0;j < L.length;j++){
        if(L.data[j] == e){
            index[k] = e;
            k++;
        }
    }
    return index;	//返回第一个元素的首地址，*index
}

线性表-销毁

void SeqListDestory(SeqList &L){
    free(L.data);
    L.length = 0;
    L.SqMaxSize = 0;
}