顺序表-动态顺序表

顺序表是逻辑上相邻的元素物理也相邻的。

静态内存是指在程序开始运行时由编译器分配的内存，它的分配是在程序开始编译时完成的，基本类型，数组。
动态内存用户无法确定空间大小，或者空间太大，栈上无法分配时，会采用动态内存分配。

顺序表的初始化

#define MaxSize 50
typedef int ElemType;

typedef struct seqList {
    int *head; //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表分配的存储容量
}Seqlist, *pSeqlist;


//初始化
void InitSeqlist(pSeqlist plist) {
    assert(NULL != plist);
    plist->head = (ElemType *)malloc(sizeof(ElemType)*MaxSize);
    memset(plist->head, 0, sizeof(ElemType)*MaxSize);
    plist->length = 0;  //空表的长度初始化为0
    plist->size = MaxSize; //空表的初始化储存空间为Maxsize
}

顺序表的插入

//尾插
void InsertBack(pSeqlist plist, ElemType e) {
    assert(NULL != plist);
    CheckCapacity(plist);
    if (plist->length == plist->size) {
        printf("Seqlist is Full...\n");
        return;
    }
    plist->head[plist->length++] = e;
}


//首插
void InsertFirst(pSeqlist plist, ElemType e) {
    assert(NULL != plist);
    CheckCapacity(plist);
    if (plist->length == plist->size) {
        printf("Seqlist is Full...\n");
        return;
    }
    int i = plist->size;
    for (; i>0; i--) {
        plist->head[i] = plist->head[i-1];
    }
    plist->head[i] = e;
    plist->length ++;
}


//在指定位置i插入e
void InsertPos(pSeqlist plist, ElemType e, int pos) {
    assert(NULL != plist);
    CheckCapacity(plist);
    if (pos >= plist->size  && pos <0) {
        printf("Error...\n");
        return;
    }
    for (int i=plist->length; i>pos; i--) {
        plist->head[i] = plist->head[i-1];
    }
    plist->head[pos] = e;
    plist->length ++;
}

顺序表的删除

//尾删
void RemoveBack(pSeqlist plist) {
    assert(NULL != plist);
    if (plist->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    plist->length --;
}


//首删
void RemooveFrist(pSeqlist plist) {
    assert(NULL != plist);
    if (plist->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    for (int i=0; i<plist->length; i++) {
        plist->head[i] = plist->head[i+1];
    }
    plist->length --;
}

//在指定位置i删除
void RemovePos(pSeqlist plist, int pos) {
    assert(NULL != plist);
    if (plist ->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    for (int i=pos; i<plist->length; i++) {
        plist->head[i] = plist->head[i+1];
    }
    plist->length --;
}

//查找元素
int FindNum(Seqlist splist, ElemType e) {
    if (splist.length == 0) {
        printf("Seqlist is Empty...\n");
        return -1;
    }
    int i=0;
    for (; i<splist.length; i++) {
        if (splist.head[i] == e) {
            return i;
        }
    }
    return -1;
}


//删除指定元素(唯一)
void RemoveNum(pSeqlist pliist, ElemType e) {
    assert(NULL != pliist);
    if (pliist->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    int index = FindNum(*pliist, e);
    RemovePos(pliist, index);
}


//删除所有指定元素(有重复的值)
void RemoveNumAll(pSeqlist plist, ElemType e) {
    assert(NULL != plist);
    if (plist->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    int isFind = 0;
    while ((isFind=FindNum(*plist, e)) != -1 ) {
        RemovePos(plist, isFind);
    }
}

顺序表逆置

//逆置
void ReverseSeqlist(pSeqlist plist) {
    assert(NULL != plist);
    if (plist->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    int i=0;
    int j=plist->length-1;
    for (i, j; i<j; i++, j--) {
        int temp = plist->head[i];
        plist->head[i] = plist->head[j];
        plist->head[j] = temp;
    }
}

顺序表冒泡排序

//冒泡排序
void BubbleSSort(pSeqlist plist) {
    assert(NULL != plist);
    if (plist->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    for (int i=0; i<plist->length; i++) {
        for (int j=i; j<plist->length; j++) {
            if (plist->head[j] < plist->head[i]) {
                int temp = plist->head[j];
                plist->head[j] = plist->head[i];
                plist->head[i] = temp;
            }
        }
    }
}

有序表拼接

//拼接，有序表1+有序表2=有序表3
void Join(pSeqlist plist1, pSeqlist plist2, pSeqlist plist) {
    assert(NULL != plist1);
    assert(NULL != plist2);
    if (plist2->length ==0 && plist1->length == 0) {
        printf("Seqlist is Empty...\n");
        return;
    }
    int i=0, j=0, k=0;
    while (i<plist1->length && j<plist2->length) {
        if (plist1->head[i] <= plist2->head[j]) {
            plist->head[k++] = plist1->head[i++];
        }
        else
            plist->head[k++] = plist2->head[j++];
    }
    //将有序表1插入到新表剩余的元素，直接尾插到新表
    if (i<plist1->length) {
        plist->head[k++] = plist1->head[i++];
    }
    //将有序表2插入到新表剩余的元素，直接尾插到新表
    if (j<plist2->length) {
        plist->head[k++] = plist2->head[j++];
    }
    plist->length = k;
}

扩容

//检查顺序表的容量， 若不够则扩容
void CheckCapacity(pSeqlist plist) {
    assert(NULL != plist);
    if(plist->size == plist->length) {
        ElemType *temp = (ElemType *)realloc(plist->head, sizeof(ElemType)*(plist->size + MaxSize));
        plist->head = temp;
        plist->size += MaxSize;
    }
}