线性表--顺序表（C语言）

seqlist.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

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

#define MAX 10
typedef int DateType;

typedef struct SeqList
{
    DateType data[MAX];
    int sz;
}SeqList, *pSeqList;

//初始化
void InitSeqList(pSeqList pSeq);
//尾部插入
void PushBack(pSeqList pSeq, DateType data);
//尾部删除 
void PopBack(pSeqList pSeq);
//头部插入 
void PushFront(pSeqList pSeq, DateType data);
//头部删除 
void PopFront(pSeqList pSeq);
//查找指定元素 
int Find(pSeqList pSeq, DateType data);
//指定位置插入 
void Insert(pSeqList pSeq, int pos, DateType data);
//删除指定位置元素 
void Erase(pSeqList pSeq, int pos);
//删除指定元素 
void Remove(pSeqList pSeq, DateType data);
//删除所有的指定元素 
void RemoveAll(pSeqList pSeq, DateType data);
//返回顺序表的大小 
int Size(pSeqList pSeq);
//判断顺序表是否为空 
int Empty(pSeqList pSeq);
//冒泡排序 
void BubbleSort(pSeqList pSeq);
//选择排序 
void SelectSort(pSeqList pSeq);
//选择排序的优化 
void SelectSortOP(pSeqList pSeq);
//二分查找 
int BinarySearch(pSeqList pSeq, DateType data);
//二分查找递归写法 
int BinarySearch_R(pSeqList pSeq, int left, int right, DateType data);
//打印 
void PrintSeqList(pSeqList pSeq);

#endif //__SEQLIST_H__

seqlist.c

#include"SeqList.h"
void InitSeqList(pSeqList pSeq)
{
    assert(pSeq != NULL);
    pSeq->sz = 0;
    memset(pSeq->data, 0, sizeof(pSeq->data));
}

void PushBack(pSeqList pSeq, DateType data)
{
    assert(pSeq != NULL);
    if (pSeq->sz == MAX)
    {
        printf("顺序表已满\n");
        return;
    }
    pSeq->data[pSeq->sz] = data;
    pSeq->sz++;
}

void PopBack(pSeqList pSeq)
{
    assert(pSeq != NULL);
    if (pSeq->sz == 0)
        return;
    pSeq->sz--;
}

void PushFront(pSeqList pSeq, DateType data)
{
    int i = 0;
    assert(pSeq != NULL);
    if (pSeq->sz == MAX)
    {
        printf("顺序表已满\n");
        return;
    }
    for ( i = pSeq->sz-1 ; i >=0; i--)
    {
        pSeq->data[i + 1] = pSeq->data[i];
    }
    pSeq->data[0] = data;
    pSeq->sz++;
}

void PopFront(pSeqList pSeq)
{
    assert(pSeq!=NULL);
    if (pSeq->sz == 0)
        return;
    for (int i = 1; i <= pSeq->sz - 1; i++)
    {
        pSeq->data[i - 1] = pSeq->data[i];
    }
    pSeq->sz--;
}

int Find(pSeqList pSeq, DateType data)
{
    assert(pSeq != NULL);
    for (int i = 0; i < pSeq->sz; i++)
    {
        if (pSeq->data[i] == data)
            return i;
    }
}

void Insert(pSeqList pSeq, int pos, DateType data) //指定位置插入
{
    assert(pSeq!=NULL);
    if (pSeq->sz == MAX)
        return;
    for (int i = pSeq->sz; i>=pos; i--)
    {
        pSeq->data[i+1]=pSeq->data[i];
    }
    pSeq->data[pos] = data;
    pSeq->sz++;
}

void Erase(pSeqList pSeq, int pos)
{
    assert(pSeq != NULL);
    if (pSeq->sz == 0) //顺序表为空
        return;
    for (int i = pos; i < pSeq->sz; i++)
    {
        pSeq->data[i] = pSeq->data[i + 1];
    }
    pSeq->sz--;
}

void Remove(pSeqList pSeq, DateType data)//删除指定元素
{
    int pos = 0;
    assert(pSeq != NULL);
    //查找
    pos=Find(pSeq, data);
    if (pos != -1)
    {
        Erase(pSeq, pos);
    }

}

void RemoveAll(pSeqList pSeq, DateType data)//删除全部指定元素
{
    assert(pSeq != NULL);
    if (pSeq->sz == 0) //顺序表为空
        return;
    for (int i = 0; i < pSeq->sz; i++)
    {
        if (pSeq->data[i] == data)
        {
            for (int j = i; j < pSeq->sz; j++)
            {
                pSeq->data[j] = pSeq->data[j + 1];
            }
            pSeq->sz--;
            i--;
        }
    }
}

int Size(pSeqList pSeq)
{
    return pSeq->sz;
}

int Empty(pSeqList pSeq)
{
    return pSeq->sz == 0;
}

void Swap(DateType*px,DateType*py)
{
    DateType tmp = *px;
    *px = *py;
    *py = tmp;
}
void BubbleSort(pSeqList pSeq)  //冒泡排序优化
{
    int tmp = 0;
    int flag = 0;
    assert(pSeq != NULL);
    for (int i = 0; i < pSeq->sz-1; i++)
    {
        flag = 0;
        for (int j = 0; j < pSeq->sz - 1 - i; j++)
        {
            if (pSeq->data[j]>pSeq->data[j+1])
            {
                Swap(pSeq->data + j, pSeq->data + j + 1);
                flag = 1;
            }
            if (flag == 0)
                break;
        }
    }
}

int BinarySearch(pSeqList pSeq, DateType data)
{
    assert(pSeq != NULL);
    int left = 0;
    int right = pSeq->sz - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        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, DateType data)
{
    int mid = 0;
    if (left > right)
        return -1;
    mid = left + (right - left) / 2;
    if (pSeq->data[mid] < data)
    {
        return BinarySearch_R(pSeq, mid + 1, right, data);
    }
    else if (pSeq->data[mid]>data)
    {
        return BinarySearch_R(pSeq, left, mid - 1, data);
    }
    else
        return  mid;
}

void SelectSort(pSeqList pSeq)
{
    assert(pSeq != NULL);
    int pos = 0;
    int tmp = 0;
    for (int i = 0; i < pSeq->sz - 1; i++)
    {
        for (int j = 0; j < pSeq->sz - 1 - i; j++)
        {
            if (pSeq->data[pos] < pSeq->data[j])
            {
                pos = j;
            }
        }
        if (pos != pSeq->sz - 1 - i) //最大元素的下标不是最后一位就交换
        {
            tmp = pSeq->data[pos];
            pSeq->data[pos] = pSeq->data[pSeq->sz - 1 - i-1];
            pSeq->data[pSeq->sz - 1 - i-1] = tmp;
        }
    }
}

void SelectSortOP(pSeqList pSeq)
{
    int temp;
    if (pSeq->sz == 0 || pSeq->sz == 1)
    {
        return;
    }
    for (int i = 0; i < pSeq->sz - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < pSeq->sz; j++)
        {
            if (pSeq->data[j]<pSeq->data[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            temp = pSeq->data[min];
            pSeq->data[min] = pSeq->data[i];
            pSeq->data[i] = temp;
        }
    }
}


void PrintSeqList(pSeqList pSeq)
{
    assert(pSeq != NULL);
    for (int i = 0; i < pSeq->sz; i++)
        printf("%d ", pSeq->data[i]);
    printf("\n");
}

test.c

#include "SeqList.h"

void test()
{
    SeqList seq;
    int pos = 0;
    InitSeqList(&seq);
    PushBack(&seq, 4);
    PushBack(&seq, 6);
    PushBack(&seq, 5);
    PushBack(&seq, 8);
    PrintSeqList(&seq);
    SelectSortOP(&seq);
    PrintSeqList(&seq);

    //测试二分查找
    /*pos = BiarySearch(&seq, 3);
    if (pos == -1)
    {
        printf("未找到该元素\n");
    }
        
    else
    {
        printf("找到了，该元素的下标:%d\n", pos);
    }
    */
     
    ////测试二分查找递归
    //pos = BinarySearch_R(&seq,0,seq.sz,4);
    //if (pos == -1)
    //{
    //  printf("未找到该元素\n");
    //}

    //else
    //{
    //  printf("找到了，该元素的下标:%d\n", pos);
    //}
}

int main()
{
    test();
    return 0;
}

运行结果：

C语言顺序表.png