【数据结构c实现】顺序表实现

线性表

在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继

线性表的顺序实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

顺序表结构

#define SEQLIST_INIT_SIZE 8

typedef struct SeqList {
    ElemType *base; // 线性表首地址
    int capacity; // 开辟的内存空间
    int size; // 有效存储
} SeqList;

顺序表初始化

开辟出一段空间（给定空间大小）

void InitSeqList(SeqList *list) {
    list->base = (ElemType *) malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);//开辟空间
    assert(list->base != NULL);
    list->capacity = SEQLIST_INIT_SIZE;
    list->size = 0;
}

①malloc动态内存分配函数，用于申请一块连续的指定大小的内存块区域以ElementType *类型返回分配的内存区域地址：格式：指针名=(指针类型*）malloc（sizeof（指针类型）*数据数量）

②如果表达式的结果为“假”，assert()会打印出断言失败的信息Assertion failed:...，并调用abort()函数终止程序的执行Process finished with exit code 3；如果表达式的结果为“真”，assert()就什么也不做，程序继续往后执行

增配空间Inc

1.重新开辟内存空间，并判断是否增配空间成功，失败则增配失败返回false

2.更新结点线性表首地址和开辟的内存空间

3.之后每次插入数据操作前，添加判断条件：分配给表内存是否足够。不够则进行增配空间，增配空间失败时，才是真正的内存不足

#define INC_SIZE 3

bool Inc(SeqList *list) {
    //对已有的空间进行分配，原来表开辟内存8，进行重新分配，即开辟8+3内存
    ElemType *newbase = (ElemType *) realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));
    if (newbase == NULL) {
        printf("增配空间失败，内存不足\n");
        return false;
    }
    list->base = newbase;
    list->capacity += INC_SIZE;

    return true;
}

①realloc函数指向在堆区重新开辟的内存块的起始地址:realloc(先前开辟的内存块的指针--也就是malloc之前申请的那块内存空间，即需要调整大小的内存空间,新开辟的那块内存空间的字节数)，返回值为调整之后的内存的起始地址

打印顺序表show_list

void show_list(SeqList *list) {
    for (int i = 0; i < list->size; i++) {
        printf("%d", list->base[i]);
    }
    printf("\n");
}

线性表长度length

int length(SeqList *list) {
    return list->size;
}

尾部插入push_back

插入6 7 9后顺序表中数据顺序为：6 7 9

1.判断有效存储是否小于开辟的内存空间，即判断开辟的空间是否已满，满了不能插入数据

2.通过下标赋值，即插入数据

3.更新顺序表有效存储长度

void push_back(SeqList *list, ElemType x) {
    if (list->size >= list->capacity && !Inc(list)) {
        printf("顺序表空间已满，%d不能尾部插入数据\n", x);
        return;
    }
    list->base[list->size] = x;
    list->size++;
}

头部插入push_front

插入6 9 1后顺序表中数据顺序为：1 9 6

1.判断有效存储是否小于开辟的内存空间，即判断开辟的空间是否已满，满了不能插入数据

2.size-1即表中最后一个数据的下标，从最后一个数据开始依次向后移动

3.赋值到下标为0的地址，即插入数据

4.更新顺序表有效存储长度

void push_front(SeqList *list, ElemType x) {
    if (list->size >= list->capacity && !Inc(list)) {
        printf("顺序表空间已满，%d不能头部插入数据\n", x);
        return;
    }
    for (int i = list->size; i > 0; i--) {
        list->base[i] = list->base[i - 1];
    }
    list->base[0] = x;
    list->size++;
}

尾部删除pop_back

有顺序表1 6 9进行尾部删除后：1 6

1.判断size是否为0，即表是否为空，空表不能删除数据

2.有效长度减1

void pop_back(SeqList *list) {
    if (list->size == 0) {
        printf("顺序表空间已空，不能尾部删除数据\n");
        return;
    }
    list->size--;
}

头部删除pop_front

有顺序表5 6 0进行头部删除后：6 0

1.判断size是否为0，即表是否为空，空表不能删除数据

2.从第二个数据开始，依次往前移动

3.有效长度减1

void pop_front(SeqList *list) {
    if (list->size == 0) {
        printf("顺序表空间已空，不能头部删除数据\n");
        return;
    }
    for (int i = 0; i < list->size - 1; i++) {
        list->base[i] = list->base[i + 1];
    }
    list->size--;
}

按位置插入insert_pos

在顺序表5 3 0下标为2的位置插入数据7为：5 3 7 0

1.判断pos是否正确并小于有效存储长度，即判断插入位置是否合法，位置非法不能插入数据

2.判断有效存储是否小于开辟的内存空间，即判断开辟的空间是否已满，满了不能插入数据

3.从最后一个数据开始依次向后移动，直到要插入数据的位置移动结束

4.通过下标赋值，即插入数据

5.更新顺序表有效存储长度

void insert_pos(SeqList *list, int pos, ElemType x) {
    if (pos < 0 || pos > list->size) {
        printf("插入数据的位置非法，不能插入数据\n");
    }
    if (list->size >= list->capacity && !Inc(list)) {
        printf("顺序表空间已满，%d不能按位置插入数据\n", x);
        return;
    }
    for (int i = list->size; i > pos; i--) {
        list->base[i] = list->base[i - 1];
    }
    list->base[pos] = x;
    list->size++;
}

特殊情况：当要插入数据的位置==有效存储长度时，即尾部插入时，不影响效率[特别注意]

按值查找find

（第一个符合条件的）

1.从顺序表第一个数据开始向后遍历

2.每次遍历判断该数据是否是要查找的数据，查找成功返回当前下标

3.遍历结束，即没查到数据，返回-1

int find(SeqList *list, ElemType key) {
    for (int i = 0; i < list->size; i++) {
        if (list->base[i] == key)
            return i;
    }
    return -1;
}

按位置删除delete_pos

顺序表5 3 0删除位置为1的数据后：5 0

1.判断pos是否正确并小于有效存储长度，即判断删除位置是否合法，位置非法不能删除数据

2.从要删除的位置开始，依次将后一个数据前移

3.更新顺序表有效存储长度

void delete_pos(SeqList *list, int pos) {
    if (pos < 0 || pos >= list->size)
        printf("删除数据的位置非法，不能删除数据\n");
    for (int i = pos; i < list->size - 1; i++) {
        list->base[i] = list->base[i + 1];
    }
    list->size--;
}

按值删除delete_val

顺序表5 3 0删除值为0的数据后：5 3

1.判断要删除的数据是否存在，即按值查找，存在得到查找到的数据下标，不存在得到-1

2.判断返回值是否是-1，是则数据不存在无法删除，否则按位置删除

void delete_val(SeqList *list, ElemType key) {
    int pos = find(list, key);
    if (pos == -1) {
        printf("要删除的数据不存在\n");
        return;
    }
    delete_pos(list, pos);
}

排序sort(冒泡；升序)

顺序表5 3 0 1 9 4排序后：0 1 3 4 5 9

1.两层遍历，依次比较两个数据，前面数据大于后面数据则交换

void sort(SeqList *list) {
    for (int i = 0; i < list->size; i++) {
        for (int j = 0; j < list->size - i - 1; j++) {
            if (list->base[j] > list->base[j + 1]) {
                ElemType tmp = list->base[j];
                list->base[j] = list->base[j + 1];
                list->base[j + 1] = tmp;
            }
        }
    }
}

逆置resver

顺序表5 3 0 1 9 4逆置后：4 9 1 0 3 5

1.判断顺序表长度是否可进行逆置操作操作，长度为1或0时不需要

2.设置两个整型指针low和high，分别指向第一个数据和最后一个数据，low指针后移，high指针前移，每次将两个指针指向的数据对换，直到low指针大于或等于high指针为止

void resver(SeqList *list) {
    if (list->size == 0 || list->size == 1)
        return;
    int low = 0;
    int high = list->size - 1;
    ElemType tmp;
    while (low < high) {
        tmp = list->base[low];
        list->base[low] = list->base[high];
        list->base[high] = tmp;
        low++;
        high--;
    }
}

清除表clear

void clear(SeqList *list) {
    list->size = 0;
}

销毁表destroy

void destroy(SeqList *list) {
    free(list->base);
    list->base = NULL;
    list->capacity = 0;
    list->size = 0;
}

①free函数必须和malloc函数同时使用

②free只能释放由malloc动态分配在堆内存的内存，直接在主函数定义结构体变量是分配在栈内存里的内存，所以释放不了

合并表merge

表A1 2 5 6，表B3 4 7 9，合并后：1 2 3 4 5 6 9

1.设置ia、ib、ic三个整型指针，分别用来遍历表A、B、合并表，开辟存放合并表的内存空间，并判断是否开辟成功

2.同时遍历表A和表B，依次判断指针指向的A、B表的数据大小，将较小的数据放入合并表，每存入一个数据，合并表和被存入的数据所在表的整型指针都向后移一次，直到A、B有一个表遍历完

3.如果其中一个表遍历结束，另一个表还有遍历完的数据，则直接将剩余数据依次存入合并表

4.更新合并表有效存储长度

void merge(SeqList *lt, SeqList *la, SeqList *lb) {
    lt->capacity = la->size + la->size;
    lt->base = (ElemType *) malloc(sizeof(ElemType)*lt->capacity);
    assert(lt->base != NULL);
    int ia = 0;
    int ib = 0;
    int ic = 0;

    while(ia<la->size && ib<lb->size)
    {
        if(la->base[ia] < lb->base[ib])
            lt->base[ic++] = la->base[ia++];
        else
            lt->base[ic++] = lb->base[ib++];
    }
    while(ia < la->size)
    {
        lt->base[ic++] = la->base[ia++];
    }
    while(ib < lb->size)
    {
        lt->base[ic++] = lb->base[ib++];
    }
    lt->size = la->size + lb->size;
}