线性表的顺序表——增、删、查、改、排序

顺序表——用一段地址连续的存储单元一次存储数据元素的线性结构。

SeqLIst.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<Windows.h>

#define MAX 10
typedef int DataType;

typedef struct SeqList
{
    DataType* _a;
    size_t _size;
    size_t _capacity;
}SeqList;


void SeqPrint(SeqList* pSeq);//打印
void SeqInit(SeqList* pSeq);//初始化
void SeqDestory(SeqList* pSeq);//释放
SeqList* CheckFull(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 SelectSort(SeqList* pSeq);//选择排序
void BubbleSort(SeqList* pSeq);//冒泡排序
int BinarySearch(SeqList* pSeq, DataType x);

---

---

SeqList.c

顺序表的结构体创建

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 = MAX_SIZE;
    (*pSeq)->_a = (DataType*)malloc(sizeof(DataType)*MAX_SIZE);
    memset((*pSeq)->_a, 0, sizeof(DataType)*MAX_SIZE);
    (*pSeq)->_size = 0;
}

---

顺序表的输出

void SeqPrint(SeqList*pSeq)//顺序表输出
{
    size_t i = 0;
    assert(pSeq);
    for (i = 0; i < pSeq->_size; i++)
    {
        printf("%d", pSeq->_a[i]);
    }
    printf("\n");
}

---

使用完后，对顺序表所占空间进行销毁

void SeqDestory(SeqList*pSeq)//销毁
{
    free(pSeq->_a);
    pSeq->_a = NULL;
}

---

验满——满则扩容

void SeqCheckFull(SeqList*pSeq)
    if (pSeq->_size >= pSeq->_capacity)
    {
        DataType*temp = (DataType*)realloc(pSeq->_a, sizeof(DataType)*(pSeq->_capacity * 2+3));

        if (NULL == temp)
        {
            printf("To enrich the capacity is failed\n");
            return;
        }
        pSeq->_capacity *= 2;
        pSeq->_a = temp;
    }
    return;
}

---

顺序表的插入——任意位置

void SeqInsert(SeqList* pSeq, size_t pos, DataType x)//指定位置插入
{
    assert(pSeq != NULL);
    pSeq = CheckFull(pSeq);
    if (pSeq != NULL)
    {
        if (0 == pSeq->_size)
        {
            pSeq->_a[pSeq->_size] = x;
            pSeq->_size++;
        }
        else
        {
            int end = pSeq->_size - 1;

            for (; (int)pos <= end; end--)
            {
                pSeq->_a[end + 1] = pSeq->_a[end];
            }

            pSeq->_a[end + 1] = x;
            ++pSeq->_size;
        }
    }
}

顺序表的插入——尾插

void SeqPushBack(SeqList*pSeq, DataType x)
{
    assert(pSeq);
    SeqInsert(pSeq, pSeq->_size, x);
}

---

顺序表的插入——头插

void SeqPushFront(SeqList*pSeq, DataType x)//头插
{
    assert(pSeq);
    SeqInsert(pSeq, pSeq->_size, 0);
}

---

---

顺序表的删除——任意位置

void SeqErase(SeqList* pSeq, size_t pos)//指定位置删除
{
    assert(pSeq != NULL);
    //assert(pos < pSeq->_size);//删除的位置必须在[0,pSeq->_size-1]

    if (0 == pSeq->_size)
    {
        printf("SeqList is empty\n");
        return;
    }

    else
    {
        size_t end = pSeq->_size-1;
        for (pos; pos <= end; pos++)
        {
            pSeq->_a[pos-1] = pSeq->_a[pos];
        }
        --pSeq->_size;
    }
}

---

顺序表的删除——尾删

void SeqPopBack(SeqList*pSeq)//尾删
{
    assert(pSeq);
    SeqErase(pSeq, pSeq->_size - 1);
}

---

顺序表的删除——头删

void SeqPopFront(SeqList*pSeq)//头删
{
    assert(pSeq);
    SeqErase(pSeq, 0);
}

---

---

顺序表的查找

int SeqFind(SeqList* pSeq, DataType x)//查
{
    assert(pSeq);
    int i = 0;
    for (; i <(int)pSeq->_size; i++)
    {
        if (pSeq->_a[i] == x)
            return i;
    }
    return -1;
}

---

顺序表的改动——替换指定元素下标的内容

void SeqAt(SeqList* pSeq, size_t pos, DataType x)
{
    assert(pSeq);
    assert(pSeq->_size > pos);
    pSeq->_a[pos - 1] = x;
}

---

---

交换函数

void Swap(DataType* x, DataType* y)
//要实现真正的交换，需要用指针传参，不能单纯的传值
{
    DataType temp = *x;
    *x = *y;
    *y = temp;
}

---

顺序表的调整——冒泡查找法

void BubbleSort(SeqList* pSeq)//冒泡查找
{
    size_t i = 0;
    size_t j = 0;
    int flag = 0;//判断是否经过交换
    for (; i < pSeq->_size - 1; i++)
    {
        for (; 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 (flag == 0)//若顺序表有序，无需交换
            return;
    }
}

---

顺序表的调整——选择排序法

void SelectSort(SeqList* pSeq)//选择排序
{
    assert(pSeq);
    size_t left = 0;
    size_t right = pSeq->_size - 1;
    size_t min = left;//存储最小值的下标
    size_t max = left;//存储最大值的下标

    while (left < right)
    {
        for (size_t i = left; i < pSeq->_size; 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)
        {
            swap(&(pSeq->_a[right]), &(pSeq->_a[max]));

        }
        else if (right != 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)
    {
        int mid = left+((right-left) >> 1);
        if (x < pSeq->_a[mid])
        {
            right = mid - 1;
        }

        else if (x > pSeq->_a[mid])
        {
            left = mid + 1;
        }

        else
        {
            return mid;

        }
    }

    return -1;
}

Test.c

#include"SeqList.c"

SeqList list;
void testSeqPushBack()//测试用例1：尾插
{
    SeqInit(&list);
    SeqPushBack(&list, 0);
    SeqPushBack(&list, 1);
    SeqPushBack(&list, 2);
    SeqPushBack(&list, 3);
    SeqPrint(&list);
}


void testSeqPopBack()//测试用例2：尾删
{
    SeqInit(&list);
    SeqPushBack(&list, 0);
    SeqPushBack(&list, 1);
    SeqPushBack(&list, 2);
    SeqPushBack(&list, 3);
    SeqPrint(&list);
    printf("\n");

    SeqPopBack(&list);
    SeqPrint(&list);
    printf("\n");

    SeqPopBack(&list);
    SeqPrint(&list);
    printf("\n");

    SeqPopBack(&list);
    SeqPrint(&list);
    printf("\n");

}


void testSeqPushFront()//测试用例3：头插
{
    SeqInit(&list);
    SeqPushFront(&list, 0);
    SeqPushFront(&list, 1);
    SeqPushFront(&list, 2);
    SeqPushFront(&list, 3);

    SeqPrint(&list);
    printf("\n");

}


void testSeqPopFront()//测试用例4：头删
{
    SeqInit(&list);
    SeqPushFront(&list, 0);
    SeqPushFront(&list, 1);
    SeqPushFront(&list, 2);
    SeqPushFront(&list, 3);
    SeqPrint(&list);
    printf("\n");

    SeqPopFront(&list);
    SeqPrint(&list);
    printf("\n");

    SeqPopFront(&list);
    SeqPrint(&list);
    printf("\n");

    SeqPopFront(&list);
    SeqPrint(&list);
    printf("\n");

}



void testSeqInsert()//测试用例5：任意位置插入
{
    SeqInit(&list);
    SeqInsert(&list, 0, 1);
    SeqInsert(&list, 1, 3);
    SeqInsert(&list, 2, 5);
    SeqInsert(&list, 3, 7);
    SeqInsert(&list, 4, 9);
    SeqPrint(&list);
    printf("\n");



    SeqInsert(&list, 1, 2);
    SeqPrint(&list);
    printf("\n");


    SeqInsert(&list, 3, 4);
    SeqInsert(&list, 5, 6);
    SeqInsert(&list, 7, 8);
    SeqInsert(&list, 9, 10);
    SeqPrint(&list);

    printf("\n");


}


void testSeqErase()//测试用例6：任意位置删除
{
    SeqInit(&list);
    SeqInsert(&list, 0, 1);
    SeqInsert(&list, 1, 3);
    SeqInsert(&list, 2, 5);
    SeqInsert(&list, 3, 7);
    SeqInsert(&list, 4, 9);
    SeqPrint(&list);
    printf("\n");

    SeqErase(&list, 0);
    SeqPrint(&list);
    printf("\n");


    SeqErase(&list, 2);
    SeqPrint(&list);
    printf("\n");


    SeqErase(&list, 4);
    SeqPrint(&list);
    printf("\n");
}



void testSeqFind()//测试用例7：查找
{
    SeqInsert(&list, 0, 11);
    SeqInsert(&list, 1, 22);
    SeqInsert(&list, 2, 33);
    SeqInsert(&list, 3, 44);
    SeqInsert(&list, 4, 55);
    SeqPrint(&list);
    printf("\n");

    printf("%d\n", SeqFind(&list, 11));
    printf("%d\n", SeqFind(&list, 22));
    printf("%d\n", SeqFind(&list, 33));
    printf("%d\n", SeqFind(&list, 44));
    printf("%d\n", SeqFind(&list, 55));
    printf("%d\n", SeqFind(&list, 66)); 

}


void testSeqAt()//测试用例8：替换
{
    SeqInsert(&list, 0, 11);
    SeqInsert(&list, 1, 22);
    SeqInsert(&list, 2, 33);
    SeqInsert(&list, 3, 44);
    SeqInsert(&list, 4, 55);
    SeqPrint(&list);
    printf("\n");

    SeqAt(&list, 0, 1);
    SeqPrint(&list);
    printf("\n");

    SeqAt(&list, 1, 1);
    SeqPrint(&list);
    printf("\n");

    SeqAt(&list, 2, 1);
    SeqPrint(&list);
    printf("\n");

    SeqAt(&list, 3, 1);
    SeqPrint(&list);
    printf("\n");

    SeqAt(&list, 4, 1);
    SeqPrint(&list);
    printf("\n");

}


void testSelectSort()//测试用例9：选择排序
{
    SeqInsert(&list, 0, 33);
    SeqInsert(&list, 1, 11);
    SeqInsert(&list, 2, 22);
    SeqInsert(&list, 3, 55);
    SeqInsert(&list, 4, 44);
    SeqPrint(&list);
    printf("\n");

    SelectSort(&list);
    SeqPrint(&list);
}


void testBubbleSort()//测试用例10：冒泡排序
{
    SeqInsert(&list, 0, 33);
    SeqInsert(&list, 1, 11);
    SeqInsert(&list, 2, 22);
    SeqInsert(&list, 3, 55);
    SeqInsert(&list, 4, 44);
    SeqPrint(&list);
    printf("\n");

    BubbleSort(&list);
    SeqPrint(&list);

}



void testBinarySearch()//测试用例11：二分查找
{
    SeqInsert(&list, 0, 11);
    SeqInsert(&list, 1, 22);
    SeqInsert(&list, 2, 33);
    SeqInsert(&list, 3, 44);
    SeqInsert(&list, 4, 55);
    SeqPrint(&list);
    printf("\n");

    //BinarySearch(&list,33);
    printf("%d\n", BinarySearch(&list, 11));
    printf("%d\n", BinarySearch(&list, 22));
    printf("%d\n", BinarySearch(&list, 33));
    printf("%d\n", BinarySearch(&list, 44));
    printf("%d\n", BinarySearch(&list, 55));
    printf("%d\n", BinarySearch(&list, 66));



}





int main()
{
    //testSeqPushBack();
    //testSeqPopBack();
    //testSeqPushFront();
    //testSeqPopFront();
    //testSeqInsert();
    //testSeqErase();
    //testSeqFind();
    //testSeqAt();

    //testSelectSort();
    //testBubbleSort();
    testBinarySearch();

    system("pause");
    return 0;
}