顺序表：插、删、改、排，以及十个测试用例

一时失言乱红尘 2022-06-04 09:35 55阅读 0赞

功能函数：

> ①打印链表  
> ②初始化链表  
> ③释放动态分配的内存  
> ④指定下标插入/删除元素  
> ⑤头插/头删/尾插/尾删  
> ⑥查找  
> ⑦更改  
> ⑧冒泡排序  
> ⑨快排  
> ⑩二分查找

**SeqList.h**

#pragma once
    
    #include <stdio.h>
    #include <windows.h>
    #include <assert.h>
    
    #define M 4
    
    typedef struct SeqList SeqList;
    typedef int DataType;
    
    void SeqPrint(SeqList* pSeq);
    void SeqInit(SeqList** pSeq);
    void SeqDestory(SeqList* pSeq);
    
    void SeqPushBack(SeqList* pSeq, DataType x);
    void SeqPopBack(SeqList* pSeq);
    void SeqPushFront(SeqList* pSeq, DataType x);
    void SeqPopFront(SeqList* pSeq);
    
    void SeqInsert(SeqList* pSeq, size_t pos, DataType x);
    void SeqErase(SeqList* pSeq, size_t pos);
    
    int SeqFind(SeqList* pSeq, DataType x);
    void SeqAt(SeqList* pSeq, size_t pos, DataType x);
    
    void BubbleSort(SeqList* pSeq);
    void SelectSort(SeqList* pSeq);
    int BinarySearch(SeqList* pSeq, DataType x);

**SeqList.c**

#define _CRT_SECURE_NO_WARNINGS -1
    
    #include "SeqList.h"
    
    typedef struct SeqList
    {
        DataType* _a;
        size_t _size;   // 有效数据个数 
        size_t _capacity;   // 容量 
    }SeqList;
    
    void SeqInit(SeqList** pSeq)//初始化顺序表
    {
        *pSeq = (SeqList*)malloc(sizeof(SeqList));
        (*pSeq)->_size = 0;
        (*pSeq)->_capacity = M;
        (*pSeq)->_a = (DataType*)malloc(sizeof(DataType)*M);
    
        memset((*pSeq)->_a, 0, sizeof(DataType)*M);
    }
    
    
    void SeqPrint(SeqList* pSeq)//输出顺序表
    {
        size_t i = 0;
        for (i = 0; i < pSeq->_size; i++)
        {
            printf("%d ", pSeq->_a[i]);
        }
        printf("\n");
    }
    
    void SeqDestory(SeqList* pSeq)//释放内存
    {
        free(pSeq->_a);
        pSeq->_a = NULL;
    }
    
    SeqList* CheckFull(SeqList* pSeq)//满则扩容
    {
        if (pSeq->_size == pSeq->_capacity)
        {
            DataType* tem = (DataType*)realloc(pSeq->_a, sizeof(DataType)*pSeq->_capacity * 2);
    
            if (NULL == tem)
            {
                printf("扩容失败！\n");
                return pSeq;
            }
            pSeq->_capacity *= 2;
            pSeq->_a = tem;
        }
        return pSeq;
    }
    
    void SeqInsert(SeqList* pSeq, size_t pos, DataType x)//插入
    {
        assert(pSeq != NULL);
        assert(pos<=pSeq->_size);
        pSeq = CheckFull(pSeq);
    
        if (0 == pSeq->_size)
        {
            pSeq->_a[pSeq->_size] = x;
            pSeq->_size++;
        }
        else
        {
            int end = pSeq->_size - 1;
            while (end >= (int)pos)
            {
                pSeq->_a[end + 1] = pSeq->_a[end];
                end--;
            }
            pSeq->_a[end + 1] = x;
    
            ++pSeq->_size;
        }
    }
    
    void SeqPushBack(SeqList* pSeq, DataType x)//尾插
    {
        assert(pSeq != NULL);
    
        SeqInsert(pSeq, pSeq->_size, x);
    }
    
    void SeqPushFront(SeqList* pSeq, DataType x)//头插
    {
        assert(pSeq != NULL);
    
        SeqInsert(pSeq, 0, x);
    }
    
    void SeqErase(SeqList* pSeq, size_t pos)//删除指定下标元素
    {
        assert(pSeq != NULL);
        assert(pos<pSeq->_size);
    
        if (0 == pSeq->_size)
        {
            return;
        }
        size_t start = pos;
        while (start < pSeq->_size - 1)
        {
            pSeq->_a[start] = pSeq->_a[start + 1];
            start++;
        }
        --pSeq->_size;
    }
    
    
    void SeqPopBack(SeqList* pSeq)//头删
    {
        assert(pSeq != NULL);
    
        SeqErase(pSeq, pSeq->_size-1);
    }
    
    void SeqPopFront(SeqList* pSeq)//尾删
    {
        assert(pSeq != NULL);
    
        SeqErase(pSeq, 0);
    }
    
    int SeqFind(SeqList* pSeq, DataType x)//查
    {
        assert(pSeq != NULL);
    
        int i = 0;
        for (i = 0; i < pSeq->_size;i++)
        {
            if (x == pSeq->_a[i])
            {
                return i;
            }
        }
        return -1;
    }
    void SeqAt(SeqList* pSeq, size_t pos, DataType x)//替换指定下标元素内容
    {
        assert(pSeq != NULL);
        assert(pos<=pSeq->_size);
    
        pSeq->_a[pos - 1] = x;
    }
    
    void Swap(DataType* x, DataType* y)//交换
    {
        //*x ^= *y;
        //*y ^= *x;
        //*x ^= *y;
        DataType tem = *x;
        *x = *y;
        *y = tem;
    }
    
    void BubbleSort(SeqList* pSeq)//冒泡排序
    {
        size_t i = 0;
        size_t j = 0;
    
        for (i = 0; i < pSeq->_size - 1; i++)
        {
            int flag = 0;
            for (j = 0; j < pSeq->_size - i - 1; j++)
            {
                if (pSeq->_a[j] > pSeq->_a[j + 1])
                {
                    Swap(&(pSeq->_a[j]), &(pSeq->_a[j + 1]));
                    flag = 1;
                }
            }
            if (0 == flag)
            {
                return;
            }
        }
    
    }
    void SelectSort(SeqList* pSeq)//选择排序
    {
        size_t left = 0;
        size_t right = pSeq->_size - 1;
        size_t min = left;//存储最小值的下标
        size_t max = left;//存储最大值的下标
    
        while (left <= right)
        {
            min = left;
            max = left;
            for (size_t i = left; i <= right; ++i)
            {
                if (pSeq->_a[i] < pSeq->_a[min])
                {
                    min = i;
                }
                if (pSeq->_a[i] > pSeq->_a[max])
                {
                    max = i;
                }
            }
            Swap(&(pSeq->_a[left]), &(pSeq->_a[min]));
    
            if (left == max)
                max = min;
            Swap(&(pSeq->_a[right]), &(pSeq->_a[max]));
    
            ++left;
            --right;
        }
    
    }
    int BinarySearch(SeqList* pSeq,DataType x)//二分查找
    {
        int left = 0;
        int right = pSeq->_size - 1;
        int mid = 0;
    
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (x > pSeq->_a[mid])
            {
                left = mid + 1;
            }
            else if (x < pSeq->_a[mid])
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }

test.c

#define _CRT_SECURE_NO_WARNINGS -1
    
    #include "SeqList.h"
    
    void test1(SeqList* pSeq)//测试用例1：插入指定下标元素
    {
        SeqInsert(pSeq, 0, 0);
        SeqInsert(pSeq, 1, 1);
        SeqInsert(pSeq, 2, 2);
        SeqInsert(pSeq, 3, 3);
        SeqInsert(pSeq, 4, 4);
        SeqPrint(pSeq);
    }
    
    void test2(SeqList* pSeq)//测试用例2：尾插
    {
        SeqPushBack(pSeq, 0);
        SeqPushBack(pSeq, 1);
        SeqPushBack(pSeq, 2);
        SeqPushBack(pSeq, 3);
        SeqPushBack(pSeq, 4);
        SeqPrint(pSeq);
    }
    
    void test3(SeqList* pSeq)//测试用例3：尾删
    {
        test2(pSeq);
    
        SeqPopBack(pSeq);
        SeqPrint(pSeq);
    
        SeqPopBack(pSeq);
        SeqPrint(pSeq);
    
        SeqPopBack(pSeq);
        SeqPrint(pSeq);
    
        SeqPopBack(pSeq);
        SeqPrint(pSeq);
    
        SeqPopBack(pSeq);
        SeqPrint(pSeq);
    }
    
    void test4(SeqList* pSeq)//测试用例4：头插
    {
        SeqPushFront(pSeq, 0);
        SeqPushFront(pSeq, 1);
        SeqPushFront(pSeq, 2);
        SeqPushFront(pSeq, 3);
        SeqPushFront(pSeq, 4);
        SeqPrint(pSeq);
    }
    
    void test5(SeqList* pSeq)//测试用例5：头删
    {
        test2(pSeq);
    
        SeqPopFront(pSeq);
        SeqPrint(pSeq);
    
        SeqPopFront(pSeq);
        SeqPrint(pSeq);
    
        SeqPopFront(pSeq);
        SeqPrint(pSeq);
    
        SeqPopFront(pSeq);
        SeqPrint(pSeq);
    
        SeqPopFront(pSeq);
        SeqPrint(pSeq);
    }
    
    void test6(SeqList* pSeq)//测试用例6，删除指定下标元素
    {
        test1(pSeq);
    
        SeqErase(pSeq, 0);
        SeqPrint(pSeq);
    
        SeqErase(pSeq, 0);
        SeqPrint(pSeq);
    
        SeqErase(pSeq, 2);
        SeqPrint(pSeq);
    
        SeqErase(pSeq, 3);
        SeqPrint(pSeq);
    
        SeqErase(pSeq, 4);
        SeqPrint(pSeq);
    
        SeqErase(pSeq, 5);
        SeqPrint(pSeq);
    }
    
    void test7(SeqList* pSeq)//测试用例7，查找
    {
        test1(pSeq);
        printf("%d\n", SeqFind(pSeq, 0));
        printf("%d\n", SeqFind(pSeq, 1));
        printf("%d\n", SeqFind(pSeq, 2));
        printf("%d\n", SeqFind(pSeq, 3));
        printf("%d\n", SeqFind(pSeq, 4));
        printf("%d\n", SeqFind(pSeq, 5));
    }
    
    void test8(SeqList* pSeq)//测试用例8：冒泡排序
    {
        SeqInsert(pSeq, 0, 9);
        SeqInsert(pSeq, 1, 1);
        SeqInsert(pSeq, 2, 2);
        SeqInsert(pSeq, 3, 5);
        SeqInsert(pSeq, 4, 4);
        SeqPrint(pSeq);
        BubbleSort(pSeq);
        SeqPrint(pSeq);
    }
    
    void test9(SeqList* pSeq)//测试用例9：快排
    {
        SeqInsert(pSeq, 0, 9);
        SeqInsert(pSeq, 1, 1);
        SeqInsert(pSeq, 2, 2);
        SeqInsert(pSeq, 3, 5);
        SeqInsert(pSeq, 4, 4);
        SeqPrint(pSeq);
        SelectSort(pSeq);
        SeqPrint(pSeq);
    }
    
    void test10(SeqList* pSeq)//测试用例10：二分查找
    {
        SeqInsert(pSeq, 0, 0);
        SeqInsert(pSeq, 1, 1);
        SeqInsert(pSeq, 2, 2);
        SeqInsert(pSeq, 3, 3);
        SeqInsert(pSeq, 4, 4);
        SeqPrint(pSeq);
        printf("%d\n", BinarySearch(pSeq, 0));
        printf("%d\n", BinarySearch(pSeq, 1));
        printf("%d\n", BinarySearch(pSeq, 2));
        printf("%d\n", BinarySearch(pSeq, 3));
        printf("%d\n", BinarySearch(pSeq, 4));
        printf("%d\n", BinarySearch(pSeq, 5));
    }
    
    int main()
    {
        SeqList *L=NULL;
        SeqInit(&L);
        //test1(L);
        //test2(L);
        //test3(L);
        //test4(L);
        //test5(L);
        //test6(L);
        //test7(L);
        //test8(L);
        //test9(L);
        test10(L);
    
        SeqDestory(L);
    
        system("pause");
        return 0;
    }