1. DSeqList.h

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DSDataType;

typedef struct DSeqList {
    DSDataType* arr;
    int capacity;
    int size;
}DSeqList;

// 初始化动态顺序表
void DSeqListInit(DSeqList* pDS, int capacity);

// 销毁动态顺序表
void DSeqListDestroy(DSeqList* pDS);

// 检查动态顺序表是否满了,满了则扩容,容量翻倍
void CheckCapacity(DSeqList* pDS);

// 尾插
void DSeqListPushBack(DSeqList* pDS, DSDataType data);

// 头插
void DSeqListPushFront(DSeqList* pDS, DSDataType data);

// 尾删
void DSeqListPopBack(DSeqList* pDS);

// 头删
void DSeqListPopFront(DSeqList* pDS);

// 任意插入
void DSeqListInsert(DSeqList* pDS, int pos, DSDataType data);

// 任意删除
void DSeqListDelete(DSeqList* pDS, int pos);

// 查找元素,成功找到则返回下标,没找到返回-1
int DSeqListFind(DSeqList* pDS, DSDataType data);

// 打印顺序表
void DSeqListPrint(DSeqList* pDS);

// 检查顺序表是否为空,为空返回1,否则返回0
int DSeqListEmpty(DSeqList* pDS);

// 清空顺序表
void DSeqListClear(DSeqList* pDS);

void Test();

2. DSeqList.c

#include "DSeqList.h"

void DSeqListInit(DSeqList* pDS, int capacity) {
    assert(pDS != NULL);

    DSDataType* tmp = (DSDataType *)malloc(sizeof(DSDataType) * capacity);
    assert(tmp != NULL);

    pDS->arr = tmp;
    pDS->capacity = capacity;
    pDS->size = 0;
}

void DSeqListDestroy(DSeqList* pDS) {
    assert(pDS != NULL);

    free(pDS->arr);
    pDS->arr = NULL;
    pDS->capacity = 0;
    pDS->size = 0;
}

void CheckCapacity(DSeqList* pDS) {
    assert(pDS != NULL);

    if (pDS->capacity == pDS->size) {  // 如果满了
        int newCapacity = pDS->capacity * 2;
        DSDataType* tmp = (DSDataType *)realloc(pDS->arr, newCapacity);
        assert(tmp != NULL);

        pDS->arr = tmp;
        pDS->capacity = newCapacity;
    }
}

void DSeqListPushBack(DSeqList* pDS, DSDataType data) {
    assert(pDS != NULL);

    // 检查顺序表是否满了
    CheckCapacity(pDS);

    pDS->arr[pDS->size] = data;
    pDS->size++;
}

void DSeqListPushFront(DSeqList* pDS, DSDataType data) {
    assert(pDS != NULL);

    // 检查顺序表是否满了
    CheckCapacity(pDS);

    // 搬移数据
    int index = pDS->size - 1;
    while (index >= 0) {
        pDS->arr[index + 1] = pDS->arr[index];
        index--;
    }
    pDS->arr[0] = data;
    pDS->size++;
}

void DSeqListPopBack(DSeqList* pDS) {
    assert(pDS != NULL);

    if (pDS->size > 0) {
        pDS->size--;
    }
}

void DSeqListPopFront(DSeqList* pDS) {
    assert(pDS != NULL);

    // 搬移数据
    int index = 1;
    while (index < pDS->size) {
        pDS->arr[index - 1] = pDS->arr[index];
        index++;
    }
    pDS->size--;
}

void DSeqListInsert(DSeqList* pDS, int pos, DSDataType data) {
    assert(pDS != NULL);

    // 检查输入合法性
    if (pos < 0 || pos > pDS->size) {
        assert(0);
        return;
    }

    // 检查顺序表是否满了
    CheckCapacity(pDS);

    // 搬移数据
    int index = pDS->size - 1;
    while (index >= pos) {
        pDS->arr[index + 1] = pDS->arr[index];
        index--;
    }
    pDS->arr[pos] = data;
    pDS->size++;
}

void DSeqListDelete(DSeqList* pDS, int pos) {
    assert(pDS != NULL);

    // 检查输入合法性
    if (pos < 0 || pos >= pDS->size) {
        assert(0);
        return;
    }

    // 搬运数据
    int index = pos + 1;
    while (index < pDS->size) {
        pDS->arr[index - 1] = pDS->arr[index];
        index++;
    }
    pDS->size--;
}

int DSeqListFind(DSeqList* pDS, DSDataType data) {
    assert(pDS != NULL);

    // 遍历查找 
    int index = 0;
    while (index < pDS->size) {
        if (pDS->arr[index] == data) {
            return index;
        }
        index++;
    }

    return -1;
}

void DSeqListPrint(DSeqList* pDS) {
    assert(pDS != NULL);

    int index = 0;
    while (index < pDS->size) {
        printf("%d ", pDS->arr[index]);
        index++;
    }
    printf("\n");
}

int DSeqListEmpty(DSeqList* pDS) {
    assert(pDS != NULL);

    return (pDS->size == 0);
}

void DSeqListClear(DSeqList* pDS) {
    assert(pDS != NULL);

    pDS->size = 0;
}

void Test() {
    DSeqList ds;
    DSeqListInit(&ds, 10);

    DSeqListPushBack(&ds, 4);
    DSeqListPushBack(&ds, 3);
    DSeqListPushFront(&ds, 2);
    DSeqListPushFront(&ds, 1);
    DSeqListPrint(&ds);

    DSeqListPopBack(&ds);
    DSeqListPopFront(&ds);
    DSeqListPrint(&ds);

    DSeqListInsert(&ds, 0, 6);
    DSeqListDelete(&ds, 1);
    DSeqListPrint(&ds);
}
Last modification:November 10th, 2019 at 10:08 am