线性数据结构——顺序表

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

顺序表的定义

struct SeqList //静态顺序表
{
    int data[10];
    int size;
}

在这里，我们对代码进行类型重命名和宏定义

#define MAX 10
typedef int DataType;
typedef struct SeqList
{
    DataType data[MAX]; //存放数据
    DataType size;  //数据个数
}SeqList, *PSeqList;
//SeqList表示结构体变量
//PSeqList表示结构体指针

定义顺序表之后，我们对顺序表进行操作

顺序表初始化

将顺序表初始化为0

//初始化 
void InitSeqList(PSeqList pSeq)
{
    assert(pSeq != NULL);
    pSeq->size = 0;
    memset(pSeq->data, 0, sizeof(pSeq->data));
}

//memset函数作用：在一段内存块中填充某个给定的值

打印顺序表

//打印 
void PrintSeqList(PSeqList pSeq)
{
    for (int i = 0; i < pSeq->size; i++)
    {
        printf("%d ", pSeq->data[i]);
    }
    printf("\n");
}

尾部插入元素

在数组data[]最后插入一个元素，并且使size加1

//尾部插入 
void PushBack(PSeqList pSeq, DataType data)
{
    assert(pSeq != NULL);
    if (pSeq->size == MAX)
    {
        printf("error");
        return;
    }
    pSeq->data[pSeq->size] = data;
    pSeq->size++;
}

尾部删除元素

直接使size减1

//尾部删除 
void PopBack(PSeqList pSeq)
{
    assert(pSeq != NULL);
    if (pSeq->size == 0)
    {
        printf("error");
        return;
    }
    pSeq->size--;
}

头部插入元素

先将所有元素向后挪动一个，然后再在第一个插入元素，并且使size加1

//头部插入 
void PushFront(PSeqList pSeq, DataType data)
{
    assert(pSeq != NULL);
    if (pSeq->size == MAX)
    {
        printf("error");
        return;
    }
    int i = 0;
    for (i = pSeq->size; i > 0; i--)
    {
        pSeq->data[i] = pSeq->data[i - 1];
    }
    pSeq->data[0] = data;
    pSeq->size++;
}

头部删除元素

先将所有元素向前挪动一个，然后size减1

//头部删除 
void PopFront(PSeqList pSeq)
{
    assert(pSeq != NULL);
    if (pSeq->size == 0)
    {
        printf("error");
        return;
    }
    int i = 0;
    for (i = 0; i < pSeq->size - 1; i++)
    {
        pSeq->data[i] = pSeq->data[i + 1];
    }
    pSeq->size--;
}

查找指定元素

对顺序表进行遍历，如果找到相同元素，则返回下标，否则返回 -1

//查找指定元素 
int Find(PSeqList pSeq, DataType data)
{
    assert(pSeq != NULL);
    if (pSeq->size == 0)
    {
        printf("error");
        return -1;
    }
    int i = 0;
    for (i = 0; i < pSeq->size; i++)
    {
        if (pSeq->data[i] == data)
        {
            return i;
        }
    }
    return -1;
}

指定位置插入

先将指定位置之后的所有元素向后挪动一个，然后将元素插入指定位置，并且使size加1

//指定位置插入 
void Insert(PSeqList pSeq, int pos, DataType data)
{
    assert(pSeq != NULL);
    if (pSeq->size == MAX)
    {
        printf("error");
        return;
    }
    int i = 0;
    for (i = pSeq->size; i > pos; i--)
    {
        pSeq->data[i] = pSeq->data[i - 1];
    }
    pSeq->data[pos] = data;
    pSeq->size++;
}

删除指定位置元素

先将指定位置之后的所有元素向前挪动一个，然后使size减1

//删除指定位置元素 
void Erase(PSeqList pSeq, int pos)
{
    assert(pSeq != NULL);
    if (pSeq->size == 0)
    {
        printf("error");
        return;
    }
    int i = 0;
    for (i = pos; i < pSeq->size - 1; i++)
    {
        pSeq->data[i] = pSeq->data[i + 1];
    }
    pSeq->size--;
}

删除指定元素

先找到指定的元素，再将指定元素之后的元素都向前挪动一位，并且让size加1

//删除指定元素 
void Remove(PSeqList pSeq, DataType data)
{
    assert(pSeq != NULL);
    if (pSeq->size == 0)
    {
        printf("error");
        return;
    }
    int i = 0;
    for (i = 0; i < pSeq->size; i++)
    {
        if (pSeq->data[i] == data)
        {
            break;
        }
    }
    if (i < pSeq->size)
    {
        int j = 0;
        for (int j = i; j < pSeq->size - 1; j++)
        {
            pSeq->data[j] = pSeq->data[j + 1];
        }
        pSeq->size--;
    }
}

删除所有的指定元素

使用新的下标保存与指定元素不相等的元素

//删除所有的指定元素 
void RemoveAll(PSeqList pSeq, DataType data)
{
    int i = 0;
    int count = 0;
    for (i = 0; i < pSeq->size; i++)
    {
        if (pSeq->data[i] != data)
        {
            pSeq->data[count] = pSeq->data[i];
            count++;
        }
    }
    pSeq->size = count;
}

返回顺序表的大小

返回size即顺序表的大小

//返回顺序表的大小 
int Size(PSeqList pSeq)
{
    return pSeq->size;
}

判断顺序表是否为空

判断size是否为0，决定顺序表是否为空

//判断顺序表是否为空 
int Empty(PSeqList pSeq)
{
    if (pSeq->size == 0)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

冒泡排序

//冒泡排序 
void BubbleSort(PSeqList pSeq)
{
    int i = 0;
    int j = 0;
    for (i = 0; i < pSeq->size - 1; i++)
    {
        for (j = 0; j < pSeq->size - i - 1; j++)
        {
            if (pSeq->data[j] > pSeq->data[j + 1])
            {
                DataType tmp = pSeq->data[j];
                pSeq->data[j] = pSeq->data[j + 1];
                pSeq->data[j + 1] = tmp;
            }   
        }
    }
}

选择排序

选择排序

//选择排序 
void SelectSort(PSeqList pSeq)
{
    int i = 0;
    int j = 0;
    int min = 0;
    for (i = 0; i < pSeq->size; i++)
    {
        min = i; //k保存最小元素的下标
        for (j = i; j < pSeq->size; j++)
        {
            if (pSeq->data[min] > pSeq->data[j])
            {
                min = j;
            }
        }
        if (min != i)
        {
            //把最小的放在第i个上去
            DataType tmp = pSeq->data[min];
            pSeq->data[min] = pSeq->data[i];
            pSeq->data[i] = tmp;
        }
    }
}

选择排序的优化

//选择排序的优化 
void SelectSortOP(PSeqList pSeq)
{
    int left = 0;
    int right = pSeq->size - 1;
    while (left <= right)
    {
        int i = 0;
        int min = left;
        int max = right;
        for (i = left; i <= right; i++)
        {
            if (pSeq->data[min] > pSeq->data[i])
            {
                min = i;
            }
            if (pSeq->data[max] < pSeq->data[i])
            {
                max = i;
            }
        }
        if (min != left)
        {
            DataType tmp = pSeq->data[min];
            pSeq->data[min] = pSeq->data[left];
            pSeq->data[left] = tmp;
        }
        //考虑修正的情况，最大值在最小位置，最小值在最大位置。
        if (max == left)
        {
            max = min;
        }
        if (max != right)
        {
            DataType tmp = pSeq->data[max];
            pSeq->data[max] = pSeq->data[right];
            pSeq->data[right] = tmp;
        }
        left++;
        right--;
    }
}

二分查找

二分查找非递归

//二分查找非递归
int BinarySearch(PSeqList pSeq, DataType data)
{
    int left = 0;
    int right = pSeq->size - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (pSeq->data[mid] > data)
        {
            right = mid - 1;
        }
        else if (pSeq->data[mid] < data)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

二分查找递归

//二分查找递归写法 
int BinarySearch_R(PSeqList pSeq, int left, int right, DataType data)
{
    if (left > right)
    {
        return -1;
    }
    else
    {
        int mid = (left + right) / 2;
        if (pSeq->data[mid] > data)
        {
            BinarySearch_R(pSeq, left, mid - 1, data);
        }
        else if (pSeq->data[mid] < data)
        {
            BinarySearch_R(pSeq, mid + 1, right, data);
        }
        else
        {
            return mid;
        }
    }
}